Algorithmus zur verkleinerten Darstellung von Bildern

Hallo,

ich suche nach Beschreibungen von Algorithmen die es ermöglichen Bilder kleiner darzustellen als sie eigentlich sind, also etwa wie es bei der Kachelansicht von Windows vorkommt, dabei müssen irgendwie die Farbinformationen mehrerer Pixel zu einem zusammengefasst werden ohne dass Unsinn rauskommt

cooky451

[Achtung Halbwissen]
Ich würde mal sagen dass das Verkleinern nicht sonderlich problematisch ist, man guckt sich die umliegenden Pixel an und nimmt den Mittelwert oder sowas..
Problematisch dürfte es allerdings werden Bildformate wie PNG/JPEG etc. überhaupt erstmal zu dekodieren.

Aber haben nicht sowohl DirectX als auch OpenGL fertige Funktionen für sowas? Ich meine.. wo Du schon im Spieleforum fragst..
[/Achtung Halbwissen]

Gregor

Es ist gar nicht so leicht, das richtig zu machen. Das Problem ist, dass in dem großen Bild Frequenzen enthalten sein können, die im verkleinerten Bild nicht mehr darstellbar sind. Das führt dann zu Aliasing-Effekten im verkleinerten Bild.

Ich weiß gar nicht, wie man das typischerweise macht. Im Prinzip könnte man das große Bild erst mit irgendeinem Weichzeichner glätten und dann über entsprechende Interpolation die Farbwerte der Pixel auf dem verkleinerten Bild bestimmen. Vermutlich wird das aber im Frequenzraum besser funktionieren. Also:

1. Fouriertransformation in den Frequenzraum
2. zu hohe Frequenzen Abschneiden (durch Nullen ersetzen und dann aus Bild ausschneiden, so dass man ein kleineres Bild im Frequenzraum hat)
3. Rücktransformation des verkleinerten Bildes in den Ortsraum.

So würde ich es momentan vermutlich versuchen. Kann aber auch sein, dass da Unfug rauskommt.

hustbaer

Es gibt viele viele verschiebenen Möglichkeiten ein Bild zu verkleinern.

Die einfachste ist "nearest pixel" "Interpolation" (in "" weil dabei eigentlich nichts interpoliert wird). Dabei überspringt man beim Verkleinern einfach einige Pixel. Das Resultat ist meist nicht sehr gut. (Ausnahme: bei ganzzahligen Verkleinerungsfaktoren und entsprechend unscharfen Ausgangsbildern sieht es oft ganz OK aus.)

Dann gibt es einige Algorithmen die ganz gut für Grössen bis min. 50% der Originalgrösse funktionieren:
* bilineare Interpolation
* bikubische Interpolation

Und dann gibt es die "echten" Verkleinerungsfilter (bzw. allgemein Resampling-Filter).

Der wohl einfachste ist der sog. Area-Filter. Der bildet die Fläche eines "Ziel-Pixels" auf das Originalbild ab, und berechnet den Durchschnitt aller Original-Pixel die in dieses Rechteck fallen. Mathematisch gesehen ist das nicht so toll, praktisch funktioniert es zum Verkleinern trotzdem ganz gut.
Für ganzzahlige Verkleinerungsfaktoren ist das sehr leicht zu implementieren, für nicht ganzzahlige ist es etwas mehr Aufwand (und auch langsamer).

Wenn man den Ball flach halten will, kann man nun z.B. den Area Filter mit nachfolgender bilinearer Interpolation kombinieren. Im ersten Schritt nimmt man einen Area-Filter mit ganzzahligem Verkleinerungsfaktor. Mit dem macht man das Bild so klein wie möglich, ohne es kleiner zu machen als das gewünschte Ergebnis. Also wenn man z.B. um Faktor 3,789 verkleinern will, dann macht man das Bild erstmal um Faktor 3 kleiner. Die Anpassung auf die genaue gewünschte Grösse macht man dann einfach mit bilinearem Interpolieren. Das geht ganz gut, da das Zwischenergebnis dann auf jeden Fall weniger als doppelt so gross ist wie das gewünschte Ergebnis.

Noch besser wäre vielleicht den ganzzahligen Verkleinerungsfaktor für den Area-Filter so zu wählen, dass man für die folgende bilineare Interpolation möglichst nahe an die 50% kommt, aber nicht darunter. D.h. in dem Beispiel oben würde man im ersten Schritt nur mit Faktor 2 verkleinern statt mit Faktor 3.

BTW: das ist im Prinzip das selbe, was man bei 3D Grafiken mit MIP Mapping macht: erst ganzzahlig (im Fall von MIP Mapping immer Power-of-2) auf eine "benachbarte" Grösse verkleinern, und das so erhaltene Bild dann bilinear oder bikubisch interpolieren.

----

Und dann gibt es noch die "guten" echten Verkleinerungsfilter. Diese hier (vollständig) zu beschreiben würde erstens den Rahmen sprengen, und zweitens bin ich da auch nicht mehr wirklich kompetent. Das grundlegende Prinzip ist einfach: man rechnet sich für jeden Ziel-Pixel als, welche Original-Pixel zu welchem Anteil in das Ergebnis eingehen sollen (die "Anteile" - Koeffizienten - können dabei auch negativ werden). Dann multipliziert man die Farben der Originalpixel mit diesen Anteilen, addiert sie zusammen, und das Ergebnis ist die Farbe für den Ziel-Pixel. Und das macht man für jeden Ziel-Pixel einzeln.
Das Schwierigste dabei ist, eine geeignete Filterfunktion zu finden, mit der man die "Anteile" ausrechnet.

Wenn's dich interessiert, hier ein sehr gutes Paper zum Thema Image Resampling:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.6734&rep=rep1&type=pdf
(Ich glaub sogar ich hab' den Link hier aus dem Forum, weiss aber nimmer von wem)

Und falls du mit meinen Ausführungen nix anfangen kannst, solltest du jetzt wenigstens ein paar Stichworte zum Googeln haben.

Gregor

cooky451 schrieb:

[Achtung Halbwissen]
Ich würde mal sagen dass das Verkleinern nicht sonderlich problematisch ist, man guckt sich die umliegenden Pixel an und nimmt den Mittelwert oder sowas..
Problematisch dürfte es allerdings werden Bildformate wie PNG/JPEG etc. überhaupt erstmal zu dekodieren.

Aber haben nicht sowohl DirectX als auch OpenGL fertige Funktionen für sowas? Ich meine.. wo Du schon im Spieleforum fragst..
[/Achtung Halbwissen]

Lustig, ich sehe das genau andersherum. Vor allem würde ich als erstes sagen "Nimm irgendwelche Bibliotheken um die Bilder zu laden!". ...aber das Programmieren des Verkleinerungsalgorithmus muss man selbst machen, weil das interessant ist, Spaß macht und eine Herausforderung ist.

hustbaer

@Gregor:
Die "unterwünschten" Frequenzen im Frequenzraum einfach wegzuschnippseln würde einem "unbeschränkten" sinc Filter entsprechen, und das führt zu mächtig viel "Ringing".

Filter mit schlechterer Sperrdämpfung sind - wie so oft - für die meisten Anwendungen besser geeignet
Und da die dann auch mit (viel) weniger "Taps" auskommen, kann man sie ruhig gleich im Ortsraum berechnen - macht die Sache einfacher und meist auch schneller.

Gregor

hustbaer schrieb:

@Gregor:
Die "unterwünschten" Frequenzen im Frequenzraum einfach wegzuschnippseln würde einem "unbeschränkten" sinc Filter entsprechen, und das führt zu mächtig viel "Ringing".

Ok, das sehe ich ein. Schade. Ich fand die Idee sooo toll. Also braucht man wohl am Besten einen Gaussfilter zur Glättung, der weder in Orts- noch Frequenzraum oszilliert. Was hältst Du davon, es so zu machen, wie oben beschrieben, sich aber dann im Frequenzraum einen Gauss-Filter zu suchen, der die hohen Frequenzen gerade so unter einen vorgegebenen Wert drückt und dann alles zu verkleinern. Naja, irgendwie ist das dann wahrscheinlich schon unnötig kompliziert.

EDIT: Wenn man so etwas über eine Glättung macht, dann wäre es vermutlich ganz gut, die Parameter für die Glättung lokal an bestimmte Regionen im Bild anzupassen. Dann kann man das aber nicht mehr so einfach im Fourierraum machen, da man dort keine Ortsinformationen mehr hat. Im Prinzip möchte man ja so wenig Glättung wie möglich betreiben. Man muss sich also praktisch die lokalen Frequenzen rund um einen Pixel herum ansehen. Dann landet man wohl bei Wavelets. Gibt es Wavelet-basierte Verkleinerungsalgorithmen?

hustbaer

k.A. ob es da was mit Wavelets gibt. Vermutlich schon. Wavelets waren mal mächtig in, da hat sicher irgendwer irgendwas probiert

Die "klassischen" Verfahren arbeiten aber alle ohne "lokales Tuning".

Für diese ist Gauss glaube ich auch kein guter Kernel, weil zu unscharf. Lies mal das von mir verlinkte Paper, das finde ich wirklich gut. Viel von der Mathematik verstehe ich nicht, aber das was ich verstehe macht Sinn. Und es ist einerseits nicht so oberflächlich dass ich mir denke "na und?", und andrerseits kommt trotzdem genug vor, was ich auch ohne den nötigen Mathematischen Background halbwegs nachvollziehen kann oder zumindest interessant finde. Und es hat Bilder
(Wobei gemeinerweise auf Len(n)a verzichtet wurde, k.A. wie man sowas machen kann wenn es auch nur im entferntesten um Bildverarbeitung geht *grummel* ;))

Was das erst unscharf machen und dann verkleinern angeht: wie genau willst du dann verkleinern? Nearest-Pixel? Bilinear? Im Prinzip stehst du wieder vor dem gleichen Problem wie vorher.

Natürlich könntest du das Bild erstmal so weit vergrössern, dass danach eine Verkleinerung mit ganzzahligem Faktor möglich ist. (Beim vergrössern musst du auch mit ganzzahligen Faktoren arbeiten, denn sonst hast du wieder das selbe Problem, nämlich wie man ein Bild sauber um nicht ganzzahlige Faktoren vergrössert) Dann filterst du es, und danach machst du Verkleinerung mit Nearest-Pixel. Das funktioniert auch 1A, nur der nötige zwischenzeitliche Vergrösserungsschritt kann gigantisch sein (z.B. wenn Original und Zielgrösse relativ prim sind). Ausserdem musst du dann ein viel grösseres Bild mit einem viel grösseren Kernel filtern.

Man kann (fast) das selbe aber in einem Schritt machen, und genau das macht man im Normalfall auch. Fast das selbe deswegen, weil man normalerweise mit einem "sampled kernel" arbeitet, und nicht mit einem "integrierten". BTW: Sorry an alle Mathematiker und/oder Signalverarbeitungsspezialisten die sich jetzt vielleicht an den Kopf greifen, aber mir fehlen hier a) die passenden Fachbegriffe und b) bewege ich mich hier auch ein gutes Stück in einem Bereich, wo ich mich nichtmehr wirklich 100% auskenne. Ich hoffe es ist kein kompletter Quatsch was ich geschrieben habe :^)

----

Nochwas...
Was Verfahren mit "lokalem Tuning" angeht ... die versuchen soweit ich weiss Kanten zu erkennen und dergleichen, d.h. die würden dann nicht bloss den Radius (bzw. die Grenzfrequenz) eines Filters ändern der auf alle Richtungen gleich wirkt, sondern gleich richtungsabhängig filtern.
p.S.: wenn dir DAZU was gutes (neues) einfällt, kannst du vermutlich sogar Geld damit verdienen. Upscaling von Videos oder auch nur für Photoshop ist ein Bereich in dem kaum gute Freeware findet. (Downscaling ist da aber weniger gefragt)

hustbaer schrieb:

Und falls du mit meinen Ausführungen nix anfangen kannst, solltest du jetzt wenigstens ein paar Stichworte zum Googeln haben.

Genau darum gehts mir Vielen Dank an alle dann weiß ich wonach ich suchen muss^^
Das Laden von Bildern ist nicht das Problem, plane nur ne GUI bei der Bilder nicht in der Originalgröße angezeigt werden sollen sondern eben verkleinert und dafür mehrere auf einmal.

Nexus

Vielleicht hilft dir auch Pixel Art Scaling Algorithms weiter.