sitemap

contact

University of Stuttgart

	Institute for Visualization and Interactive Systems
	Bericht

Sorry, this document is only available in German.

Software Praktikum SS 2000

Thema: Visuell optimaler Zoom

Universität Stuttgart

Fakultät Informatik - Institut für Informatik

Abteilung Visualisierung und Interaktive Systeme

Prof. Dr. T. Ertl

Betreuer: Martin Kraus

Bearbeiter: Edmund Buchal, Pierre Hein, Robert Sauter

Inhaltverzeichnis:

Aufgabe
Überblick
Bericht
Conclusio

Aufgabe

Der Kern der Aufgabe bestand darin, einen Vergrösserungsalgorithmus für Bilder zu implementieren. Als Interpolationsfunktion sollte dabei das Shannontheorem Verwendung finden. Eine hohe Geschwindigkeit stand dabei im Vordergrund.
Im gesamten sollte eine kleine Anwendung realisiert werden, mit der ein JPEG-Bild geladen und ein Ausschnitt davon gezoomt werden kann. Um eine grosse Plattformunabhängigkeit zu gewährleisten, war das Programm in C/C++ und mit Hilfe von OpenGL zu implementieren. Um das Ergebnis der Interpolation zu vergleichen, sollten auch noch weitere Zoomalgorithmen realisiert werden.

Überblick

Beim Vergrössern von Bildern müssen die neuen Punkte zwischen den Originalpixeln "intelligent geraten", d.h. irgendwie sinnvoll berechnet werden. Diesen Vorgang nennt man Interpolation.
Im folgenden seien:
sw/sh
die Breite/Höhe des Quellsbildes
dw/dh
die Breite/Höhe des Ausgabebildes
f[m, n] m,n eN, 0<=x<sw, 0<=n<sh
ein zweidimensionales Array, welches das Quellbild darstellt
F(x, y) x,y eQ, 0<=x<sw, 0<=y<sh, x e {i*sw/dw| 0<=i<dw, ieN}, y e {i*sh/dh| 0<=i<dh, ieN}
eine Funktion, welche die Punkte für das Ausgabebild liefert

Eine sehr einfache (und schnelle) Vorgehensweise besteht darin, einfach den im Quellbild nächstliegenden Punkt zu wählen:

F(x, y)=f[floor(x+0.5), floor(y+0.5)]

Dieser Algorithmus ("nearest") liefert bei kleinen Zoomfaktoren noch erstaunlich gute Ergebnisse. Bei stärkeren Vergrösserungen neigt er aber stark zu Blockbildung (Riesenpixel).

Bild der Funktion Die lineare Interpolation dagegen betrachtet die 4 umliegenden Punkte und gewichtet deren Einfluss auf das Resultat anhand ihere Entfernung zum Zielpixel.

fx=x-floor(x); fy=y-floor(y);
F(x, y)=f[int(x),   int(y)]   * (1-fx) * (1-fy) +
        f[int(x)+1, int(y)]   * (fx)   * (1-fy) +
        f[int(x),   int(y)+1] * (1-fx) * (fy)   +
        f[int(x)+1, int(y)+1] * (fx)   * (fy)

Diese Vorgehensweise liefert schon recht gute Ergebnisse, aber leider verlieren die Vergrösserungen an Schärfe.

Weitere Möglichkeiten sind die kubischen Interpolationen, bei denen 16 umliegende Punkte mittels eines Polynoms vom Grad 3 betrachtet werden. Zur Errechnung der Koeffizienten kann z.B. das Lagrange Verfahren verwendet werden.
Bei der kubischen Splineinterpolation, die in vielen (besseren) Bildbearbeitungsprogrammen als Alternative zur linearen Interpolation angeboten wird, wird statt des einfachen Polynoms eine Splinefunktion (ebenfalls vom Grad 3) verwendet.

Der hier realisierte Algorithmus basiert auf dem Shannon-Theorem, mit dessen Hilfe sich aus einer Anzahl von diskreten Werten die ursprüngliche Wellenfunktion berechnen lassen soll. Die Funktion F wird damit zu:

        sh-1 sw-1           sin(pi*(x-m))  *  sin(pi*(y-n))
F(x, y)= S     S  f[m,n] * ---------------------------------
        n=0   m=0             pi*(x-m)     *    (pi*(y-n)

Es wird also das gesamte Bild in die Berechnung jedes Zielpunktes einbezogen.
Der Quotient ergibt sich aus einer 2-Dimensionalen Überlagerung der rechts zu sehenden Funktion, wobei aber immer nur diskrete Werte ...x-2,x-1,x,x+1,x+2,... daraus entnommen werden. Unten sind noch zwei Ansichten der 2-Dimensionalen Funktion zu sehen.

Der 1. Versuch

In der ersten Realisierung wurde pro Zielpunkt über den gesamten zu zoomenden Bildausschnitt iteriert. (zur Vereinfachung gehe ich im folgenden von einem Farbwert pro Pixel aus, auch ist es nicht die genaue Implementierung)

for (i=0; i<dh; i++) {
	dx=0;
	for (j=0; j<dw; j++) {
		res=0;
		for (n=0; n<sh; n++) {
			if (dy==n) fy=1; else fy=((sin(pi*(dy-n)))/(pi*(dy-n)));
			for (m=0; m<sw; m++) {
				if (dx==m) fx=1; else fx=((sin(pi*(dx-m)))/(pi*(dx-m)));
				f=fy*fx;
				res+=f*img(m, n);
			}
		}
		*(d++)=res<0 ? 0 : (res>255 ? 255 : (unsigned char)(resr));
		dx+=(double)sw/(double)w;
	}
	dy+=(double)sh/(double)h;
}

Besonders im einfachen grauen Bild (s.u.) sind die Randartefakte, die sich dabei ergeben haben sehr deutlich. Das liegt natürlich im wesentlichen am Ausschneiden des zu vergrössernden Ausschnitts. Nichtsdestotrotz sollen natürlich auch Ecken des Bildes gut verarbeitet werden.
Diese Implementierung ist außerordentlich langsam. Um einen 100x100 Pixel großen Bildausschnitt auf 400x400 zu zoomen, benötigte das Programm über 10 min! (auf einem PIII/650).
Als Ergebnis dieses ersten Versuches wurde in der folgenden Bearbeitung des Themas etwas mehr Wert auf eine Verbesserung der Qualität des Ergebnisses gelegt.

Qualität

Das Hauptproblem der Qualität des Ergebnisses lag in der Behandlung von Punkten am Rand des gezoomten Bereiches. Nachdem die Implementierung die Selektion nicht mehr ausschnitt, war die Qualität über das gesamte Ausgabebild hinweg gleich. Ein Problem stellen dann nur noch Bildausschnitte am Rande des Originalbildes dar. Um dort ein besseres Ergebnis zu erreichen, musste eine intelligente Simulation eines nicht vorhanden Randes gesucht werden. Im wesentlichen boten sich dabei zwei Möglichkeiten:

Die Farben der äußeren Punkte bestimmen auch das Aussehen des Randes. Wird auf einen Pixel ausserhalb des Originalbildes zugegriffen, erhält dieser die Farbe des ihm am nächsten liegenden vorhanden Punktes (s. linke Abb.).

Der Rand entsteht durch Spiegelung des Originalbildes(s. rechte Abb.).

Versuche haben gezeigt, daß sich die Ergebnisse dabei subjektiv nicht unterscheiden. In der Anwendung besteht aber die Möglichkeit zwischen beiden Methoden (und zusätzlich einem schwarzen Rand) zu wählen.
Ein weiteres, aber wohl dem Algorithmus innewohnendes, Problem ist das "Ausstreuen" von dunklen Flächen in helle hinein (natürlich auch umgekehrt, aber so fällt es stärker auf). Das liegt einfach an der großen Reichweite des Algorithmus. Es werden nicht nur wenige (bilinear: 4, bikubisch: 16, ...), sondern sehr viele (typisch etwa 400) umliegenden Punkte betrachtet. Besonders gut sieht man das beim zoomen eines einzelnen schwarzen Punktes auf weißem Hintergrund. Der Punkt "sendet" dunkle Wellen in die umliegenden Bereiche aus. Bei weniger kontrastreichen Bildern fältt es aber weniger auf. (s. Abb.: links=linear, rechts=shannon)

Geschwindigkeit

Nachdem sich also gezeigt hatte, daß dieser Algorithmus ansprechende Ergebnisse liefern kann, war es dringend nötig sich mit seiner Beschleunigung zu beschäftigen.
Mit der größte Geschwindigkeitsgewinn dürfte durch die Einengung des betrachteten Bereiches (auf Vorschlag von Martin Kraus) erzielt worden sein. Dabei macht man sich den fallenden Verlauf (wenn man nur die benutzen absoluten Werte betrachtet) der Quotientenfunktion zunutze. Ein Punkt der weiter vom Zielpunkt entfernt ist, trägt auch weniger zu seinem Farbwert (positiv oder negativ) bei. Als besonders effizient erweist sich dabei die Erweiterung dieser Idee, den Bereich abhängig vom Nachkommteil des aktuellen Punktes dynamisch noch weiter einzugrenzen. (Im folgenden wird die Betrachtung der Einfachheit halber eindimensional fortgesetzt, sie ist aber natürlich direkt auf zwei Dimensionen erweiterbar) Wenn man sich den Funktionsverlauf von sin(pi*x) anschaut fällt einem auf, daß die Periodenlänge der Funktion geschickterweise 2 beträgt. Damit bleibt der Zähler des Quotienten sin(pi*(x-m)) bis auf das Vorzeichen für einen Zielpunkt gleich. Nur bei einem Nachkommawert von 0,5 ist dieser Wert maximal (±1) und damit ist auch nur für diesen Wert der maximale umliegende Bereich zu betrachten. Das beste Beispiel ist der Nachkommawert 0,0 , d.h. ein Zielpunkt liegt genau auf einem Quellpunkt, da dann eben nur dieser, also ein Bereich der Länge 1 Einfluß auf den Zielpunkt hat. Alle anderen Punkte werden mit 0 multipliziert und fallen damit weg (der Quellpunkt wird wegen dem Grenzwert sin(x)/x->1 mit 1 multipliziert). Der Bereich wird dadurch bestimmt, daß ein Punkt noch min. 1/n (z.B. 1/128) am Resultat ändern können muß. Folgende Tabelle zeigt für n=128 die Bereiche die je nach Wert des Nachkommateils (x) betrachtet werden müssen (für x>0.5 ergibt sich das Resultat aus 0.5-x)

Nachkommateil	0.05	0.10	0.15	0.20	0.25	0.30	0.35	0.40	0.45	0.50
Relevante Punkte pro Richtung	6.37	12.59	18.50	23.95	28.81	32.96	36.30	38.75	40.24	40.74

Bei einer dreifachen Vergrößerung müssen somit statt 40-40-... nur 1-34-34-1-34-34... Punkte betrachtet werden, was eine Ersparnis von über 40% bedeutet.
Als angenehmer Nebeneffekt ist die Zeit dann auch nicht mehr von der Größe des Quellbildes abhängig (bis auf den evt. langsameren Speicherzugriff bei weiter auseinaderliegenden Daten).
Die Betrachtungen des Sinusverlaufs zeigen auch, daß es ausreicht einen einzigen Sinus zu berechnen, da der Zähler (bis auf das Vorzeichen) für einen Nachkommawert gleichbleibt.
Da die Spaltenquotienten in jeder Zeile gleich sind, wird ihre Berechnung aus der innersten (der 4.)Schleife in die 2. verlegt. Ebenso wird die Berechnung der y-Quotienten in der 2. Schleife erledigt. Das bedeutet zwar keinen Geschwindigkeitsvorteil, erleichtert aber das Auslagern der umfangreicher (aber schneller) gewordenen Bestimmung der Faktoren in eine gemeinsame (mit den x-Quot.) Funktion.
Eine weiter kleinere Beschleunigung wurde durch das Verschieben der Berechnung des Gesamtfaktors (f=fx*fy in die 3. Schleife erreicht. In der Inneren Schleife wird nur noch ein für eine Zeile gültiges Resultat (per Multiplikation mit fx) errechnet, dieses fließt dann, mit dem y-Faktor malgenommen, in das Gesamtresultat ein (Anwendung des Distributivgesetzes).
Die Geschwindigkeit wird dann noch durch Standardverbesserungen, beipielsweise Zeigerarithmetik statt Array und das Vorausberechnen von Werten (Differenz zwischen zwei Zeilenanfängen, u.s.w.) erhöt. Ein kleiner Trick besteht noch darin, das Array im passenden Format (normalerweise float) anzulegen. Es lohnt sich auch eine Konvertierung vor dem eigentlichen Berechnen, da während des Zoomens wiederholt auf die einzelnen Punkte zugegriffen wird. In diesem Zug wird dann auch der Simulierte Rand erzeugt.
Damit wird aus der inneren Schleife:

for (m=mw, fxtp=fxt; m>0; m--) {
	f=(*fxtp++);
	xresr+=f*(*s++);
	xresg+=f*(*s++);
	xresb+=f*(*s++);
}

Und diese stellt dann auch den Flaschenhals des Algorithmus dar. Die Berechnung der Quotienten nimmt weniger als 10% der Zeit in Anspruch, alles andere ist sowieso vernachlässigbar.
Zur Information: jede dieser inneren Zeilen wird bei der Vergrößerung auf ein 800x800 Punkte großes Bild über 346 Mio Mal ausgefürt.
Das Ergebnis dieser Bemühungen: 100x100 -> 400x400 in etwa 4 sek

Conclusio

Die Geschwindigkeit der Implementierung ist annehmbar, wenn auch für echte interaktive Programme noch zu langsam.
Die Qualität hägt sehr vom Quellbild ab. Bei eher dunklen, nicht zu kontrastreichen Bildausschnitten ist das Ergebnis gut. Unserer subjektiver Meinung nach ist es etwas (ein kleines Bißchen!) besser als die anderen Algorithmen. Die Verbesserung rechtfertigt die Langsamkeit aber nicht. Besonders kubische Interpolationen bieten bei bedeutend höherer Geschwindigkeit (unoptimiert!) ein praktisch gleich gutes Ergebnis. Bei kontrastreichen Bereichen stört das "Ausstrahlen" der dunklen Bereiche in die hellen doch stark. Das abschließende Urteil sollte der Betrachter aber selber fällen.

Noch ein paar abschließende Beispiele (Shannon, bikubische Splines, 2.Reihe: linear, nearest):