Shaderprogrammierung für Entzerrung in Echtzeit – Teil 3

Im Teil 1 dieser Reihe führte ich in die grundlegenden Werkzeuge für unsere Aufgabenstellung ein und zeigte das nun entstehende Anwendungsprogramm.

Teil 2 widmete sich den optischen Grundlagen unserer Modellbildung.

In diesem Teil beginnen wir mit der mathematischen Modellierung. Zunächst fassen wir die bisherigen Schritte in einer Übersicht zusammen:

Die Übersicht zeigt auch noch einmal deutlich die Besonderheit der Entzerrung: Wir bleiben im zweidimensionalen Raum, es ist nicht unsere Intention, die globalen Koordinaten der Objektpunkte zu rekonstruieren.

Stattdessen wird aus dem zweidimensionalen Abbild der Hausfassade ein anderes zweidimensionales Abbild erstellt, die Entzerrung der Fassade. Dazu wird der Berechnungsprozess quasi umgekehrt, wir haben es mit der Umkehrung unserer Umkehrung zu tun:

Diesen Punkt sollte man im Hinterkopf behalten, um Denkfallen zu entgehen. Bei der Entzerrung gehen wir mathematisch eben nicht den physikalischen Abbildungsvorgang rückwärts, sondern analog diesem vorwärts. So invertieren wir beispielsweise eben NICHT die Verzeichnung.

Unser Endergebnis ist ein Pixel-Farb-Bild der entzerrten Fassade. Nicht mehr. Keine Semantik, keine Punkte (außer Punkten, aus denen die nötigen Parameter der Entzerrung gewonnen werden, aber dazu später).

Und jedes Pixel dieses Bildes wird aus Pixeln des Ausgangsbildes berechnet. Letztendlich mündet alles in eine Funktion $f:\left(x,y\right) \rightarrow \left(u,v\right)$, wobei $\left(x,y\right)$ für die Pixelposition des entzerrten Bildes und $\left(u,v\right)$ für die Pixelposition des Ausgangsbildes steht.

Pixel sind in der IT diskret, ihre Farbe wird digital festgehalten. Ein Pixel hat dabei eine Ganzzahlposition in unserem Pixelkoordinatensystem. Die Abbildung $f:\left(x,y\right) \rightarrow \left(u,v\right)$ trifft aber in der Regel eben keine Ganzzahlen für $\left(u,v\right)$. Stattdessen muss die Farbe für ein Pixel $\left(x,y\right)$ aus den diskreten Nachbarschaftspixeln einer Position $\left(u,v\right)$ berechnet werden. Daher benötigen wir nun zusätzlich ein lokales, zur Problemstruktur passendes Modell dieser Bildfunktion.

Die bekanntesten Verfahren dazu sind:

• nearest: es wird einfach das nächstliegende Pixel genutzt
• bilinear: der Farbwert wird flächenanteilig aus den Farben der vier angrenzenden Pixeln berechnet
• bikubisch: ähnlich bilinear, aber aus 16 umliegenden Pixeln berechnet

Und hier kommt uns die mathematische Natur unserer Entzerrung erneut entgegen. Für die Farbberechnung eines Pixels betrachten wir nur eine sehr kleine Umgebung der ermittelten Position im Ausgangsbild – typischerweise die unmittelbar benachbarten Pixel. Gegenüber den Abmessungen des gesamten Bildes haben wir es also mit einem sehr kleinen $\Delta x$ und $\Delta y$ zu tun.

Unsere Koordinatentransformation ist über das gesamte Bild keineswegs linear. Die Homographie ist eine projektive Abbildung, und durch die Verzeichnung kommt eine weitere Nichtlinearität hinzu. Entscheidend ist jedoch die Größenordnung, auf der wir diese Funktionen betrachten. Für eine hinreichend kleine Umgebung um einen Punkt $p$ kann eine glatte Abbildung $f$ durch ihre lokale Linearisierung beschrieben werden:

Dabei beschreibt $J_f(p)$ die Jacobi-Matrix der Abbildung an dieser Stelle. Die eigentliche Nichtlinearität steckt in den Termen höherer Ordnung. Sind $\Delta x$ und $\Delta y$ nur von der Größenordnung weniger Pixel, sind diese Terme bei unserer Entzerrung gegenüber dem linearen Anteil praktisch vernachlässigbar.

Das gilt auch für die Verzeichnung. Über das gesamte Bild kann sie deutlich sichtbar sein; zwischen unmittelbar benachbarten Pixelpositionen verändert sich ihr Einfluss dagegen nur minimal. Die charakteristische Größenordnung, auf der sich Homographie und Verzeichnung merklich ändern, ist bei unserer Anwendung wesentlich größer als der Pixelabstand.

Damit kann die geometrische Abbildung innerhalb der kleinen Umgebung, aus der wir einen Farbwert bestimmen, praktisch als lokal linear angesehen werden. Es ist also keine stark gekrümmte Abbildungsgeometrie innerhalb dieser Pixelnachbarschaft zu berücksichtigen. Und daher können wir hier Verfahren wie z.B. die bilineare Interpolation durchaus einsetzen.

Die globale Abbildung kann also durchaus stark von einer linearen Transformation abweichen, ohne dass dies gegen eine lokale lineare Näherung auf Pixelebene spricht. Entscheidend ist nicht, ob eine Funktion global nichtlinear ist, sondern ob sich ihre Nichtlinearität bereits innerhalb des betrachteten kleinen $\Delta$ merklich auswirkt. Bei anderen Auswertungen wie etwa Echtzeitvisualisierungen aus 360-Grad-Aufnahmen spielt die Natur nicht so gnädig mit.

An dieser Stelle haben wir etwas Unangenehmes: Wir müssen ein nicht verlustfrei umkehrbares Resampling machen. Wir entscheiden uns bei der Farbberechnung für ein Verfahren, z.B. bilinear, und müssen den Informationsverlust bezüglich des Ausgangsbildes hier in Kauf nehmen. Daher sollte ein solcher Vorgang nur erfolgen, wenn er unbedingt nötig ist. Und damit kommen wir zu einem Punkt, wo unsere Kette noch unvollständig ist: Wir wollen bewusst sowohl im Ausgangsbild als auch im entzerrten Bild frei zoomen können. Bei unserem jetzigen Ansatz würden wir aber auf einem berechneten Pixelbild mit bereits erfolgtem Informationsverlust zoomen, und das ohne jede technische Notwendigkeit. Viel besser ist es, diesen Schritt noch weiter hinauszuzögern, auf die wirkliche jeweilige Ansicht am Monitor:

Technisch schwer nachvollziehbar ist für mich, dass verschiedene Programme tatsächlich nach dem ersten beschriebenen Ansatz arbeiten, also mit einem entzerrten Zwischenbild. Unser Ansatz erhält dagegen so viel wie möglich Information des Ausgangsbildes bei jeder aktuellen Ansicht.

Jetzt ist bekannt, welche Transformationskette für jedes dargestellte Pixel durchlaufen werden muss. Im nächsten Teil formulieren wir diese Schritte mathematisch und führen sie zu der Funktion zusammen, die später im Shader ausgeführt wird.