Interpolationen und Bildtransformationen

Bei der Bearbeitung von Bildern sind Transformationen häufig. Dies können Drehungen, Spiegelungen, oder Verschiebungen (Translationen) sein. Es geht hierbei nicht um Transformationen der Bildinformationen in eine neue Darstellung (etwa Fourier- oder Hough-Transformationen).

Durch diese Transformationen sind die neu berechneten Pixel im Allgemeinen nicht mehr ganzzahlig. Wie geht man damit um?

Zunächst einmal schlägt der naive Versuch, die ursprünglichen Pixel einfach in ein neues Bild zu transformieren fehl, da im neuen Bild nicht alle Bildelemente (pixel) durch die Transformation erreicht werden. MathematikerInnen sprechen hierbei von fehlender Surjektivität der Abbildung. Dies liegt an der diskreten, ganzzahligen Darstellung mittels Pixel. Würde man den Wertebereich der Transformation mit Paaren reeller Zahlen verstehen, wäre diese Abbildung wieder surjektiv, wenn man sie geeignet auf das Bild einschränkt. Dies spielt im späteren Verlauf noch eine Rolle.

Als ich selbst diese Lösung versucht hatte, war ich von dem Ergebnis (schwarze Streifen im neuen Bild) verblüfft (und auch ein wenig frustiert).

Wenn man sich mit seinen Fehlern aber auseinandersetzt, kann man daraus tatsächlich etwas lernen 😉 Warum die Sache also nicht rückwärts angehen? Rückwärts-Arbeiten ist im Übrigen eine oft hilfreiche Vorgehensweise beim Problemlösen. Mehr hierzu unter [1].

Da die Transformationen in geeigneter Weise bijektiv sind, existieren Umkehrabbildungen (bsp. ist die Umkehrung einer 30°-Drehung die Drehung um -30°). Damit kann man nun für jedes leeres Pixel im neuen Bild fragen, welchem Wert es im ursprünglichen entspräche? (Manche Fragen sind wichtiger als ihre Antworten; und andere bringen die Antwort gleich mit. )

Unbenannt

Welcher Wert bekommt nun das blau markierte Pixel?

Auf diese Frage gibt es mehrere Antworten. Die einfachste ist eine einfache Rundung, um aus den reellen Werten wieder ganzzahlige zu machen.

In diesem Fall entspräche der Wert dem des Pixels (\begin{array}{c}3\\1\end{array}), also 47. Diese Form der Interpolation heißt „Nearest-Neighbour“, man richtet sich nach dem nächst entfernten Nachbarpixel.

Betrachtet man das Ergebnis einer Interpolation (Bild unten), kann man noch nicht ganz zufrieden sein. Warum sieht das Ergebnis so körnig aus?

Unbenannt
Links: Originalbild, Mitte: NN-Interpolation, Rechts: Bilineare Interpolation

Würde man das Pixel (\begin{array}{c}3.45\\0.50\end{array})= betrachten, wäre das Ergebnis das selbe, obwohl es sehr viel näher am Pixel (\begin{array}{c}3\\0\end{array})= liegt, dessen Wert zumal besonders klein ist. Große Ungerechtigkeit ist im Spiel 😉

Aushilfe schafft hier die bilineare Interpolation, sie betrachtet die Nachbarschaft und gibt ihnen den linearen Anteil, der ihnen zusteht:

 

Unbenannt
Idee der bilinearen Interpolation, Quelle: [2]
Der Name erklärt sich durch zweimalige lineare Interpolation. Zunächst ermitteln wir in der Horizontalen:

Die Funktion f gibt den (Farb-)Wert für das Pixel an: Für unser Beispiel ist (r,c) = (2,1) sowie (r‘,c‘) = (3.45, 0.87) sowie r_1=3,r_2=4,c_1=0,c_2=1

Nun müssen wir nur noch die Werte einsetzen:

f(p)=f(r_1,c_1)+(r‘-r_1)(f(r_2,c_1)-f(r_1,c_1)=f(3,0)+0.45 (f(4,0)-f(3,0)=3+0.45(6-3) =4.35

f(q)=f(r_1,c_2)+(r‘-r_1)(f(r_2,c_2)-f(r_1,c_2)=f(3,1)+0.45 (f(4,1)-f(3,1)=47+0.45(47-47) =47 Damit ergibt sich insgesamt

g(r,c)=f(r‘,c‘)=f(p)+(c‘-c_1)(f(q)-f(p))=4.35+0.87 (47-4.35)=41.4555\sim 41

Die Interpolation erfordert zwar ein wenig mehr Rechenaufwand, dieser scheint bei Betrachtung des Ergebnisses aber allemal gerechtfertigt! 🙂

[1] Problemlösen – Regina Bruder, Soltau

[2] Vorlesungsskript Computer Vision, Jiang 2013

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.