Stereoanalyse

Zwei Kameras nehmen eine Szene auf. Die Epipolargeometrie beschreibt die Beziehung zwischen den beiden Bildern.

Die Epipolargeometrie (selten auch Kernstrahlgeometrie) ist ein mathematisches Modell aus der Geometrie, das die geometrischen Beziehungen zwischen verschiedenen Kamerabildern des gleichen Objekts darstellt. Mit ihrer Hilfe lässt sich die Abhängigkeit zwischen korrespondierenden Bildpunkten beschreiben – also den Punkten, die ein einzelner Objektpunkt in den beiden Kamerabildern erzeugt. Obwohl ihre Grundlagen bereits 1883 von Guido Hauck und 1908 von Horst von Sanden untersucht wurden, gelangte die Epipolargeometrie erst mit der automatischen Auswertung digitaler Bilder vor allem im Bereich des maschinellen Sehens zu größerer Bedeutung.

Vornehmlich wird die Epipolargeometrie bei der Gewinnung von 3D-Informationen aus Bildern eingesetzt. Dabei unterstützt sie die Korrespondenzanalyse, also die Zuordnung korrespondierender Punkte, und reduziert den erforderlichen Suchaufwand erheblich.

Prinzip

Abbildung bei der Lochkamera

Ein Fotoapparat lässt sich geometrisch durch eine Lochkamera modellieren. Bei dieser liegen während der Aufnahme jeder Punkt des aufgenommenen Objektes, das Projektionszentrum (entspricht dem Objektiv der Kamera) sowie der dazugehörige Bildpunkt auf einer Geraden. Wurde der Objektpunkt zweimal von unterschiedlichen Positionen aus aufgenommen, lassen sich bei einer späteren Auswertung mittels der Orientierungen der Kameras der Schnittpunkt der zwei Geraden und damit die Koordinaten des Objektpunktes berechnen. Eine 3D-Rekonstruktion ist somit möglich, wenn in beiden Bildern die Bildpunkte eines Objektpunktes lokalisiert wurden. Die Epipolargeometrie dient zur Unterstützung dieser Lokalisation: ist der Punkt im ersten Bild gegeben, schränkt sich bei bekannter Epipolargeometrie der Suchbereich im zweiten Bild auf eine Linie ein.

Schematische Darstellung der Epipolargeometrie

In nebenstehender linker Grafik werden die geometrischen Beziehungen verdeutlicht. Dargestellt sind neben den Bild- und Objektpunkten sowie den beiden Projektionszentren die beiden Bildebenen der zwei Kameras. Diese sind vor die Projektionszentren geklappt. Das erleichtert die Darstellung, ändert jedoch nichts an den geometrischen Beziehungen. Der Objektpunkt X bildet sich im Kamerabild 1 auf den Bildpunkt x_L ab. Ausgehend von diesem Bildpunkt ist es lediglich möglich, den dazugehörigen Strahl, auf dem X liegt, zu bestimmen. Mögliche Objektpunkte X₁, X₂ oder X₃, die ebenso wie X dem Bildpunkt x_L entsprechen, liegen auf diesem Strahl. Dieser Strahl und damit alle möglichen Objektpunkte werden bei der Aufnahme des Objekts von einer anderen Position im zweiten Bild auf einer Geraden abgebildet. Auf diese reduziert sich die Suche nach dem zum Bildpunkt x_L korrespondierenden Bildpunkt x_R im zweiten Bild.

Mit Hilfe der Epipolargeometrie kann eine einfache Beziehung zwischen korrespondierenden Punkten ohne Kenntnis der Kamerapositionen hergestellt werden. Aus einer bekannten Epipolargeometrie können zwar Informationen über die relative Position der Kameras zueinander abgeleitet werden, zu ihrer Bestimmung ist es jedoch nicht erforderlich, die Kamerapositionen explizit zu kennen. Die Epipolargeometrie hängt nur von den Parametern der Kameras ab und ist damit unabhängig von der Struktur der aufgenommenen Szene.

Begriffe der Epipolargeometrie

Zur Beschreibung der Epipolargeometrie und ihrer Elemente existiert eine feste Terminologie. Die Ebene, welche die beiden Projektionszentren der Kameras und der aufgenommene Objektpunkt aufspannen, wird Epipolarebene genannt. Diese schneidet die beiden Bilder in jeweils einer Geraden, der sogenannten Epipolarlinie. Nur auf dieser kann ein korrespondierender Bildpunkt zu einem im anderen Bild gegebenen Punkt liegen. Die Gerade, die die beiden Projektionszentren der Kameras verbindet, durchstößt die beiden Bildebenen in jeweils einem Punkt, dem Epipol. Die beiden Epipole ändern ihre Position im jeweiligen Bild nicht, solange die Lage der Kameras zueinander stabil bleibt. Der Epipol eines Bildes ist gleichzeitig die Abbildung des Projektionszentrums der anderen Kamera. Durch ihn laufen alle Epipolarlinien eines Bildes, er selber kann sich aber je nach Lage der Kameras zueinander außerhalb des eigentlichen Bildes befinden.

Im Bereich der Photogrammetrie wurden und werden zum Teil heute noch die Begriffe Kernstrahlgeometrie, Kernpunkt, Kernebene und Kernlinie anstelle von Epipolargeometrie, Epipol, Epipolarebene und Epipolarlinie verwendet. ^[1]

Anwendungen

Die Epipolargeometrie wird vor allem in der projektiven Geometrie, der Photogrammetrie und dem maschinellen Sehen genutzt. Ihr Haupteinsatzzweck ist dabei die Korrespondenzanalyse. Wird zu einem markanten Punkt in einem Bild der korrespondierende im anderen Bild gesucht, so muss bei unbekannter Epipolargeometrie das gesamte Bild untersucht werden. Ist die Epipolargeometrie bekannt, lässt sich die Suche nach dem korrespondierenden Punkt auf die Epipolarlinie einschränken. Das bewirkt eine erhebliche Verkleinerung des Suchraums. Aus diesem Grunde wird die Epipolargeometrie vor allem dort eingesetzt, wo mittels Kameras eine Szene oder ein Objekt dreidimensional analysiert werden muss. Wichtige Einsatzgebiete sind die Vermessung von Werkstücken zur Qualitätsprüfung, die Gebäudeaufnahme bei der Architekturphotogrammetrie oder die Luftbildphotogrammetrie zur Erstellung von Kartenwerken.

Maschinelles Sehen

Stanley, Gewinner der DARPA Grand Challenge 2005

Die Epipolargeometrie schränkt bei der Korrespondenzsuche zur Objektidentifikation den Suchbereich auf die Epipolarlinien ein und bedingt dadurch eine enorme Rechenzeitersparnis. Gleichzeitig verringert sie die Anzahl von falschen Zuordnungen korrespondierender Punkte durch die Suchraumeinschränkung. Beides ist von großem Vorteil beim maschinellen Sehen. Insbesondere in der autonomen Robotik sind einfache Berechnungen für eine hohe Performance erforderlich, zum Einen wegen der begrenzten Hardware auf mobilen Plattformen und zum Anderen wegen der Notwendigkeit schneller Reaktionen zur Kollisionsvermeidung. So kam bei einem Teilnehmer der DARPA Grand Challenge, ein Wettbewerb unbemannter Landfahrzeuge, die Programmbibliothek OpenCV zum Einsatz, die schnelle Routinen zur Berechnung der Epipolargeometrie und ihrer Anwendung bei der Korrespondenzanalyse beinhaltet.^[2]

Selbstkalibrierung von Kameras

Die 3D-Rekonstruktion einer Szene aus Fotografien setzt voraus, dass die Kalibrierung der Kameras bekannt ist. Da die Epipolargeometrie die projektive Beziehung zwischen zwei Bildern beschreibt, wird sie bei der so genannten Selbstkalibrierung, also der automatischen Ermittlung der Kameraparameter, eingesetzt. Dabei wird die Epipolargeometrie nicht zur Korrespondenzsuche benutzt, sondern rekonstruiert umgekehrt aus bekannten Korrespondenzen die vollständige Kamerakalibrierung.

Geschichte

Tafel Ⅰ aus dem Artikel von Hauck. Fig. 1a illustriert das Zitat.

Die Geschichte der Epipolargeometrie ist eng verbunden mit der Geschichte der Photogrammetrie. Der erste, der die ihr zugrunde liegenden geometrischen Beziehungen analysierte, war der Mathematiker Guido Hauck. Er publiziert 1883 im Journal für die reine und angewandte Mathematik einen Artikel, in dem zum ersten Mal der Begriff Kernpunkt verwendet wurde:

„Es seien (Fig. 1a) S' und S'' zwei Projectionsebenen, O₁ und O₂ die zugehörigen Projectionscentren. Die Schnittlinie g₁₂ der zwei Projectionsebenen nennen wir Grundschnitt. Die Verbindungslinie O₁O₂ möge die zwei Projectionsebenen in den Punkten $o^'_2$ und $o^{''}_1$ schneiden, welche wir die Kernpunkte der zwei Ebenen nennen.“

– Guido Hauck: Neue Constructionen der Perspective und Photogrammetrie Journal für reine und angewandte Mathematik, Band 95, 1883, Seiten 1–35

Eine erste umfangreichere Darstellung verfasste 1908 Horst von Sanden im Rahmen seiner Dissertation „Die Bestimmung der Kernpunkte in der Photogrammetrie“.^[3] Er beschrieb in dieser Arbeit Methoden zu einer einfacheren und genaueren Bestimmung der Kernpunkte.

Bei der bis zur Einführung der Digitaltechnik vorherrschenden so genannten analogen Photogrammetrie mit optisch-mechanischer Fotografie und Auswertung wurde die Korrespondenzanalyse manuell durchgeführt. Da ein menschlicher Operateur bei genügend Szenenstruktur problemlos korrespondierende Punkte zuordnen kann, wurden die Erkenntnisse kaum angewandt. Erst das Aufkommen der digitalen Photogrammetrie mit digitaler Fotografie und rechnergestützter Offline-Auswertung ab den 1980er Jahren sowie der steigende Bedarf einer automatisierten Bildauswertung im Bereich des maschinellen Sehens bewirkte eine erneute intensivere Beschäftigung mit der Epipolargeometrie und ihrer Anwendung. Eine erste Arbeit, welche die Neuentdeckung der Thematik belegt, war die Veröffentlichung von Longuet-Higgins in der Zeitschrift Nature.^[4] Seitdem beschäftigen sich viele Wissenschaftler mit der Epipolargeometrie, darunter Huang und Faugeras^[5], Horn^[6] sowie Vieville und Lingrand.^[7]

Mathematische Beschreibung

Die Epipolargeometrie stellt eine Beziehung zwischen den Bildkoordinaten korrespondierender Punkte her. Die Bildkoordinaten werden oft in kartesischen Koordinaten, können jedoch auch in affinen Koordinaten angegeben werden. Der Ursprung des Bildkoordinatensystems eines Bildes liegt meist in der Mitte oder der Ecke des Bildes. Bei digitalen Bildern (CCD-Aufnahmen oder gescannte Bilder) können zum Beispiel die Zeile und Spalte der Pixel als Koordinaten verwendet werden. Wenn sich Zeilen- und Spaltenauflösung unterscheiden oder die Achsen des Koordinatensystems nicht rechtwinklig aufeinander stehen, sind diese Koordinaten affin.

Die Beziehung zwischen den Bildkoordinaten korrespondierender Punkte wird durch eine Fundamentalmatrix beschrieben. Mit ihr lässt sich zu einem gegebenen Punkt im ersten Bild die dazugehörige Epipolarlinie im zweiten Bild bestimmen, auf der sich der korrespondierende Punkt befindet.

Homogene Koordinaten und Projektionsmatrix

Die Abbildung der Objektpunkte auf die Bildebene kann mit den in der projektiven Geometrie benutzten homogenen Koordinaten beschrieben werden. Homogene Koordinaten sind gegenüber kartesischen oder affinen Koordinaten um eine Koordinate erweitert und nur bis auf einen Skalierungsfaktor eindeutig. Den zweidimensionalen kartesischen oder affinen Koordinaten $(x,\, y)$ entsprechen die homogenen Koordinaten $(u,\, v,\, w)=(wx,\, wy,\, w)$. Die homogenen Koordinaten $(u,\, v,\, w)$ und $(u/w,\, v/w,\, 1)=(x,\, y,\, 1)$ repräsentieren denselben Punkt. Entsprechendes gilt für den dreidimensionalen Raum.

Mit homogenen Koordinaten lässt sich die Abbildung der dreidimensionalen Objektpunkte auf die zweidimensionale Bildebene als lineare Funktion beschreiben:

$\mathbf{x} = \begin{pmatrix} u \\ v \\ w \end{pmatrix} = \mathbf{P} \mathbf{X} = \begin{pmatrix} p_{11} & p_{12} & p_{13} & p_{14} \\ p_{21} & p_{22} & p_{23} & p_{24} \\ p_{31} & p_{32} & p_{33} & p_{34} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix}.$

Die kartesischen (oder affinen) Bildkoordinaten erhält man aus x = u / w und y = v / w. Die 3×4-Projektionsmatrix $\mathbf{P}$ beschreibt die perspektivische Abbildung der Objektpunkte auf die Bildebene. Sie enthält die Daten der Orientierung der Kamera. Da bei dieser Abbildung eine Dimension verlorengeht, ist sie nicht (eindeutig) umkehrbar.

Beziehung zwischen korrespondierenden Punkten

Die Herleitung der Fundamentalmatrix beruht auf der Idee, im ersten Bild einen Punkt $\mathbf{x}_1$ auszuwählen, dann einen beliebigen Objektpunkt $\mathbf{X}$ zu bestimmen, der auf diesen Bildpunkt abgebildet wird, und schließlich dessen Bildpunkt $\mathbf{x}_2$ im zweiten Bild zu berechnen. Dieser Punkt $\mathbf{x}_2$ und der Epipol $\mathbf{e}_2$ befinden sich auf der in der zweiten Bildebene liegenden und zu $\mathbf{x}_1$ gehörigen Epipolarlinie und beschreiben sie damit eindeutig.

Ist ein Punkt $\mathbf{x}_1$ im ersten Bild gegeben, lässt sich mit Hilfe der zugehörigen Projektionsmatrix $\mathbf{P}_1$ der Strahl, auf dem der dazugehörige Objektpunkt liegt, angeben. Der Objektpunkt selbst kann nicht bestimmt werden, da die Entfernung von der Kamera unbekannt ist. Ein beliebiger Punkt auf dem Strahl lässt sich mit der Pseudoinversen $\mathbf{P}_1^+$ berechnen:

$\mathbf{X} = \mathbf{P}_1^+ \mathbf{x}_1.$

Dieser Punkt kann mit der Projektionsmatrix $\mathbf{P}_2$ der zweiten Kamera in das zweite Bild abgebildet werden:

$\mathbf{x}_2 = \mathbf{P}_2 \mathbf{X} = \mathbf{P}_2 \mathbf{P}_1^+ \mathbf{x}_1.$

Damit ist ein Punkt auf der zu $\mathbf{x}_1$ gehörigen Epipolarlinie in Bild 2 bekannt. Ein weiterer Punkt auf dieser Epipolarlinie ist der Epipol $\mathbf{e}_2$, der das Bild des Projektionszentrums $\mathbf{O}_1$ der ersten Kamera ist:

$\mathbf{e}_2 = \mathbf{P}_2 \mathbf{O}_1.$

Die Epipolarlinie wird in homogenen Koordinaten durch die Geradengleichung $\mathbf{l}_2^\text{T} \mathbf{x}_2 = 0$ beschrieben, wobei $\mathbf{l}_2$ als Kreuzprodukt aus zwei Geradenpunkten berechnet werden kann:

$\mathbf{l}_2 = \mathbf{e}_2 \times \mathbf{x}_2 = (\mathbf{P}_2 \mathbf{O}_1) \times (\mathbf{P}_2 \mathbf{P}_1^+ \mathbf{x}_1).$

Dieses Kreuzprodukt kann mit einer schiefsymmetrischen Matrix $\mathbf{S}$ auch als Matrizenmultiplikation geschrieben werden:

$\mathbf{l}_2 = (\mathbf{S}_{\mathbf{P}_2 \mathbf{O}_1} \mathbf{P}_2 \mathbf{P}_1^+) \mathbf{x}_1 =\mathbf{F} \mathbf{x}_1,$

wobei der Klammerausdruck zu der Fundamentalmatrix $\mathbf{F}$ zusammengefasst ist. Damit lautet die Gleichung der Epipolarlinie und die Beziehung zwischen korrespondierenden Punkten:

$\mathbf{l}_2^\text{T} \mathbf{x}_2 = \mathbf{x}_2^\text{T} \mathbf{l}_2 = \mathbf{x}_2^\text{T} \mathbf{F} \mathbf{x}_1 = 0$

oder:

$\begin{pmatrix} x_2 & y_2 & 1 \end{pmatrix} \begin{pmatrix} f_{11} & f_{12} & f_{13} \\ f_{21} & f_{22} & f_{23} \\ f_{31} & f_{32} & f_{33} \end{pmatrix} \begin{pmatrix} x_1 \\ y_1 \\ 1 \end{pmatrix} = 0$.

Diese Gleichung wird als Epipolargleichung bezeichnet.

Ein Spezialisierung der Fundamentalmatrix ist die essentielle Matrix. Diese ergibt sich, wenn normierte Bildkoordinaten verwendet werden, bei denen der Ursprung des kartesischen Bildkoordinatensystems im Hauptpunkt des Bildes liegt. Da diese Bedingung bei der Fundamentalmatrix nicht erfüllt sein muss, kommt sie im Vergleich zur essentiellen Matrix mit weniger Annahmen aus.

Eigenschaften der Fundamentalmatrix

Die Fundamentalmatrix $\mathbf{F}$ (auch Bifokal-Tensor genannt) enthält die gesamte Information über die Epipolargeometrie. Sie kann auch ohne Kenntnis der Orientierung der Kameras (das heißt ohne Kenntnis der Projektionsmatrizen $\mathbf{P}_1$ und $\mathbf{P}_2$ sowie des Projektionszentrums $\mathbf{O}_1$) aus den Bildkoordinaten korrespondierender Punkte bestimmt werden.

Die 3×3-Fundamentalmatrix ist nur bis auf einen Skalierungsfaktor eindeutig bestimmbar, da die Multiplikation der Fundamentalmatrix $\mathbf{F}$ mit einer beliebigen Zahl ungleich 0 nichts an der Gültigkeit der Epipolargleichung $\mathbf{x}_2^\text{T} \mathbf{F} \mathbf{x}_1 = 0$ ändert. Damit sind zunächst nur 8 der 9 Elemente unabhängig. Da die Matrix $\mathbf{S}_{\mathbf{P}_2 \mathbf{O}_1}$ – wie jede schiefsymmetrische $n \times n$-Matrix mit ungeradem n – singulär ist, ist $\mathbf{F}$ singulär, so dass die Determinante 0 ist. Durch diese zusätzliche Bedingung reduziert sich der Freiheitsgrad der Fundamentalmatrix auf 7.

Mittels der Fundamentalmatrix kann zu einem Punkt $\mathbf{x}_1$ im ersten Bild die dazugehörige Epipolarlinie $\mathbf{l}_2$ im zweiten Bild berechnet werden:

$\mathbf{l}_2=\mathbf{F} \mathbf{x}_1,$

und umgekehrt zu einem Punkt $\mathbf{x}_2$ im zweiten Bild die Epipolarlinie $\mathbf{l}_1$ im ersten Bild:

$\mathbf{l}_1=\mathbf{F}^\text{T} \mathbf{x}_2.$

Aus einer gegebenen Epipolarlinie in einem Bild lässt sich nicht der ursprünglichen Punkt im anderen Bild berechnen. Dazu müsste die Fundamentalmatrix invertiert werden, was auf Grund ihrer Singularität nicht möglich ist.

Da der Epipol $\mathbf{e}_2$ auf allen Epipolarlinien $\mathbf{l}_2$ liegt, muss

$\mathbf{l}_2^\text{T} \mathbf{e}_2 = (\mathbf{F} \mathbf{x}_1)^\text{T} \mathbf{e}_2 = \mathbf{x}_1^\text{T} \mathbf{F}^\text{T} \mathbf{e}_2 = 0$

für alle $\mathbf{x}_1$ gelten, so dass der Epipol $\mathbf{e}_2$ und entsprechend der Epipol $\mathbf{e}_1$ aus den Gleichungen

$\mathbf{F}^\text{T} \mathbf{e}_2=\mathbf{0} \qquad \text{und} \qquad \mathbf{F} \mathbf{e}_1=\mathbf{0}$

bestimmt werden können. Auch aus diesen Gleichungen ist ersichtlich, dass die Determinante der Fundamentalmatrix 0 sein muss, da sonst die Gleichungen nur die Lösungen $\mathbf{e}_1 = \mathbf{e}_2 = \mathbf{0}$ hätten.

Berechnung

Die Fundamentalmatrix und damit die Epipolargeometrie lässt sich – wie im Abschnitt Beziehung zwischen korrespondierenden Punkten gezeigt – bei bekannter Kalibrierung der beiden Kameras direkt aus beiden Projektionsmatrizen und einem Projektionszentrum berechnen. Da die Berechnung der Fundamentalmatrix meist vor einer Bestimmung der Projektionsmatrizen durchgeführt wird, tritt dieser Fall selten auf. Im Folgenden wird erläutert, wie $\mathbf{F}$ nur mit Hilfe von Punktkorrespondenzen berechnet werden kann.

Um aus einer Menge korrespondierender Bildpunkte die Fundamentalmatrix zu bestimmen, wird die Epipolargleichung $\mathbf{x}^\text{T}_2\mathbf{Fx}_1=0$ ausmultipliziert:

x₂x₁f₁₁ + x₂y₁f₁₂ + x₂f₁₃ + y₂x₁f₂₁ + y₂y₁f₂₂ + y₂f₂₃ + x₁f₃₁ + y₁f₃₂ + f₃₃ = 0

oder in vektorieller Schreibweise:

$\begin{pmatrix} x_2 x_1 & x_2y_1 & x_2 & y_2x_1 & y_2y_1 & y_2 & x_1 & y_1 & 1 \end{pmatrix} \cdot \mathbf{f} = 0$

mit

$\mathbf{f} = \begin{pmatrix} f_{11} & f_{12} & f_{13} & f_{21} & f_{22} & f_{23} & f_{31} & f_{32} & f_{33} \end{pmatrix}^{\text{T}}.$

Aus n Punktkorrespondenzen kann das folgende homogene lineare Gleichungssystem aufgestellt werden (der obere Index gibt die Punktnummer an):

$\begin{pmatrix} x_2^1 x_1^1 & x_2^1y_1^1 & x_2^1 & y_2^1x_1^1 & y_2^1y_1^1 & y_2^1 & x_1^1 & y_1^1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ x_2^n x_1^n & x_2^ny_1^n & x_2^n & y_2^nx_1^n & y_2^ny_1^n & y_2^n & x_1^n & y_1^n & 1 \end{pmatrix} \cdot \mathbf{f} = \mathbf{A} \cdot \mathbf{f} = \mathbf{0}.$

Da die Koordinaten korrespondierender Punkte die Epipolargleichung erfüllen, sind die Spalten von $\mathbf{A}$ linear abhängig. Die Matrix $\mathbf{A}$ hat also im Idealfall höchstens den Rang 8. Dies gilt allerdings bei mehr als 8 Zeilen nur, wenn keine Messungenauigkeiten in den Koordinaten und keine falsch zugeordneten Punktpaare vorliegen. Da $\mathbf{A}$ nicht vollen Spaltenrang hat, existiert für $\mathbf{f}$ (abgesehen von der trivialen Lösung $\mathbf{f}=\mathbf{0}$) eine Lösung aus dem Nullraum von $\mathbf{A}$.

Im Allgemeinen treten bei der Bestimmung der Korrespondenzen kleinere Messungenauigkeiten auf, da die Bildpunkte nur mit einer endlichen Genauigkeit lokalisiert werden können. Die aus dem Lösungsvektor $\mathbf{f}$ ermittelte Fundamentalmatrix $\mathbf{F}$ hat dadurch nicht den Rang 2 und ist somit nicht singulär. Das führt dazu, dass sich die mit dieser Fundamentalmatrix bestimmten Epipolarlinien eines Bildes nicht mehr alle im Epipol schneiden.

In der Praxis kommen zwei Verfahren zur Berechnung der Fundamentalmatrix zur Anwendung, die diese Singularitätsbedingung beachten: der 7-Punkt-Algorithmus und der 8-Punkt-Algorithmus. Bei beiden Verfahren werden meist nicht direkt die gemessenen Koordinaten der Bildpunkte verwendet, sondern die Koordinaten vorher normiert. Dabei werden die Koordinatensysteme in beiden Bildern so verschoben, dass der Ursprung jeweils im Schwerpunkt der Bildpunkte liegt, und dann die Koordinaten so skaliert, dass ihre Werte in der Größenordnung 1 liegen. Mit dieser Normierung kann eine deutliche Verbesserung der Ergebnisse erreicht werden.

7-Punkt-Algorithmus

Dieses Verfahren benutzt 7 Punktkorrespondenzen zur Berechnung der Fundamentalmatrix $\mathbf{F}$. Da $\mathbf{F}$ nur bis auf einen Faktor eindeutig ist, reichen 7 Punkte zusammen mit der Bedingung $\det(\mathbf{F})=0$ aus, um die 9 Elemente von $\mathbf{F}$ zu bestimmen. Bei 7 Punktkorrespondenzen enthält das Gleichungssystem $\mathbf{A}\mathbf{f}=\mathbf{0}$ nur 7 Gleichungen. Es gibt daher zwei linear unabhängige Lösungen $\mathbf{f}_1$ und $\mathbf{f}_2$ aus dem Nullraum von $\mathbf{A}$. Die Fundamentalmatrix $\mathbf{F}$ wird als Linearkombination der aus $\mathbf{f}_1$ und $\mathbf{f}_2$ gebildeten Matrizen $\mathbf{F}_1$ und $\mathbf{F}_2$ bestimmt:

$\mathbf{F} =\alpha\mathbf{F}_1 + (1-\alpha)\mathbf{F}_2 \quad \text{mit} \quad \alpha \in \R .$

Um jetzt aus der Menge der Lösungen ein $\mathbf{F}$ auszuwählen, welches den Rang 2 hat, wird ausgenutzt, dass auf Grund der Singularitätsbedingung die Determinante von $\mathbf{F}$ gleich 0 sein muss:

$\det(\mathbf{F})=\det(\alpha\mathbf{F}_1 + (1-\alpha)\mathbf{F}_2)=0 .$

Diese kubische Gleichung hat mindestens eine und höchstens drei reelle Lösungen α. Mit jeder Lösung α kann eine Fundamentalmatrix berechnet werden. Wenn mehrere Lösungen existieren, sind weitere Punkte erforderlich, um eine eindeutige Lösung zu bestimmen. Es wird die Lösung ausgewählt, bei der auch für weitere Punkte die Epipolargleichung erfüllt oder bei Messungenauigkeiten in den Koordinaten näherungsweise erfüllt ist.

8-Punkt-Algorithmus

In der Regel sind mehr als 7 Punktkorrespondenzen vorhanden. Der im Folgenden beschriebene 8-Punkt-Algorithmus benötigt mindestens 8 korrespondierende Punktpaare, es können jedoch auch mehr Punkte verwendet werden. Die Idee für dieses Verfahren stammt von Longuet-Higgins.^[4]

Im ersten Schritt wird nur das Gleichungssystem $\mathbf{A}\mathbf{f}=\mathbf{0}$ betrachtet, ohne die Bedingung $\det(\mathbf{F})=0$ zu berücksichtigen. Im Idealfall hat die Matrix $\mathbf{A}$ den Rang 8, in der Praxis ist das jedoch bei mehr als 8 Punkten wegen Messungenauigkeiten nicht der Fall, so dass die Lösung $\mathbf{f}$ nicht aus dem Nullraum von $\mathbf{A}$ bestimmt werden kann. Stattdessen wird die Lösung mit der Methode der kleinsten Quadrate oder durch die Bestimmung von Eigenwerten ermittelt.

Bei der Methode der kleinsten Quadrate wird $\mathbf{f}$ so bestimmt, dass $\|\mathbf{A}\mathbf{f}\|$ minimal ist. Da $\mathbf{f}$ nur bis auf einen Faktor eindeutig ist, muss eine Bedingung eingeführt werden, z. B. indem ein Element von $\mathbf{f}$ gleich 1 gesetzt wird. Das Problem hierbei ist, dass dies nicht gerade ein Element sein darf, das 0 oder sehr klein ist, was a-priori nicht bekannt ist. Man kann jedoch mehrere Möglichkeiten ausprobieren. Bei der zweiten Methode wird ebenfalls $\|\mathbf{A}\mathbf{f}\|$ minimiert, jedoch mit der Bedingung $\|\mathbf{f}\|=1$. Dies führt zu dem Ergebnis, dass die Lösung $\mathbf{f}$ der Eigenvektor zum kleinsten Eigenwert der Matrix $\mathbf{A}^{\text{T}}\mathbf{A}$ ist.

Die aus der Lösung $\mathbf{f}$ gebildete Fundamentalmatrix $\mathbf{F}$ ist im Allgemeinen nicht singulär. Daher muss diese Bedingung in einem zweiten Schritt erfüllt werden. Dazu wird $\mathbf{F}$ durch eine Singulärwertzerlegung in $\mathbf{F}=\mathbf{U}\mathbf{S}\mathbf{V}^{\text{T}}$ zerlegt. $\mathbf{S}$ ist eine Diagonalmatrix, die die Singulärwerte enthält. Der kleinste wird gleich 0 gesetzt, und dann wird aus den Matrizen $\mathbf{U}$, $\mathbf{S}$ und $\mathbf{V}$ wieder die Fundamentalmatrix berechnet. Da jetzt ein Singulärwert gleich 0 ist, erfüllt die Fundamentalmatrix die Singularitätsbedingung.

Der 8-Punkt-Algorithmus ist ein einfaches Verfahren zur Bestimmung der Fundamentalmatrix, er ist jedoch anfällig gegen Messungenauigkeiten. Dies liegt daran, dass die Singularitätsbedingung der Fundamentalmatrix erst nachträglich erfüllt wird, und dass die minimierte Größe $\|\mathbf{A}\mathbf{f}\|$ keine physikalische Bedeutung hat. Es gibt weitere Verfahren, die diese Nachteile nicht haben. ^[8] Diese Verfahren sind jedoch aufwändiger und werden in der Praxis seltener eingesetzt.

Automatische Berechnung

Vor allem beim maschinellen Sehen ist eine automatische Berechnung der Epipolargeometrie notwendig, da zum Beispiel autonome Roboter ohne menschliche Hilfe agieren sollen. Dafür wird im ersten Schritt eine Menge korrespondierender Punkte bestimmt. Dies geschieht mit Hilfe eines Interest-Operators, mit welchem markante Punkte in einem Bild lokalisiert werden können. Sind diese gefunden, wird zu jedem Punkt im ersten Bild der ihm ähnlichste im zweiten Bild bestimmt. Eine Korrespondenzanalyse liefert ein Maß für die Ähnlichkeit. Die Menge korrespondierender Punkte enthält im Allgemeinen auf Grund von Bildrauschen und der unterschiedlichen Perspektive, mit der die beiden Kameras die Szene betrachten, eine größere Anzahl von Fehlzuordnungen und kann daher nicht direkt zur Berechnung der Fundamentalmatrix benutzt werden.

In den folgenden Darstellungen werden markante Punkte sowie das Ergebnis der Korrespondenzanalyse beispielhaft gezeigt. In Bild 3 ist deutlich zu erkennen, dass nicht alle Korrespondenzen richtig bestimmt wurden. Da die Kamera nach der ersten Aufnahme nach rechts geschwenkt wurde, müssten die grünen Striche, welche den Vektor zwischen korrespondierenden Punkten darstellen, etwa horizontal sein. Gerade im Bereich des Baumes links ist dies nicht der Fall, da hier die Blätter alle eine ähnliche Form und Helligkeit haben und damit die Korrespondenzanalyse zu falschen Ergebnissen führt.

Korrespondenzanalyse

1. Erstes Bild mit markanten Punkten.

2. Zweites Bild mit markanten Punkten.

3. Mutmaßliche Korrespondenzen als Vektor

Die Fehlzuordnungen müssen vor der Berechnung mittels geeigneter Verfahren zur Separierung und Eliminierung von Ausreißern ausgeschlossen werden. Häufig wird dazu der so genannte RANSAC-Algorithmus verwendet. Dieser Algorithmus kann Fehlzuordnungen in den Punktepaaren aufspüren. Auf die Berechnung von $\mathbf{F}$ angewandt, besteht er aus folgenden Schritten:

1. Wähle zufällig 7 Punktkorrespondenzen aus den Datenpunkten. Das geschieht in Erwartung, dass diese 7 Korrespondenzen frei von Fehlern sind.
2. Ermittle aus den gewählten Korrespondenzen mittels des 7-Punkt-Algorithmus $\mathbf{F}$.
3. Bestimme alle korrespondierenden Punkte, für die gilt: $\mathbf{x}^\text{T}_2\mathbf{Fx}_1=0$ und speichere diese. Je mehr Punktepaare diese Gleichung erfüllen, um so wahrscheinlicher enthielten die ursprünglich gewählten Punkte keine Fehlzuordnungen.
4. Wiederhole die Schritte 1–3 so oft, dass mit genügend großer Wahrscheinlichkeit die 7 Punktkorrespondenzen keine Fehler enthielten.

Die Fundamentalmatrix $\mathbf{F}$ wird anschließend mittels der größten Menge Punktepaare aus Schritt 2 und dem 8-Punkt-Algorithmus bestimmt. Danach kann nochmalig eine Korrespondenzanalyse durchgeführt werden, bei der die berechnete Fundamentalmatrix zum Einsatz kommt (wie beschrieben verkleinert sich der Suchbereich nach korrespondierenden Punkten dadurch auf die Epipolarlinie) und ein niedrigerer Wert für das Ähnlichkeitsmaß akzeptiert wird. Diese letzten beiden Schritte können iterativ wiederholt werden, bis die Zahl der Korrespondenzen stabil ist.

Die folgenden beiden Darstellungen illustrieren das Ergebnis. Die akzeptierten Korrespondenzen sind in der linken wieder als Vektor eingezeichnet. In der rechten Darstellung wurden die Epipolarlinien der markanten Punkte eingezeichnet.

Ergebnis der Berechnung

1. Korrespondenzen nach RANSAC, mit denen $\mathbf{F}$ berechnet wird.

2. Einige Epipolarlinien, berechnet mit $\mathbf{F}$.

Sonderfälle

Sonderfälle der Epipolargeometrie
Links die Kamera-Objekt-Konfiguration, rechts die beiden überlagerten Kamerabilder a und b mit den Epipolarlinien (rot).

Bei bestimmten Positionen der Kameras zueinander kann es zu Singularitäten kommen. Dabei sind zwei Anordnungen insbesondere beim maschinellen Sehen praxisrelevant:

1. Befinden sich die beiden Bildebenen der Kameras A und B in einer Ebene, stehen also exakt parallel zueinander, verschieben sich die Epipole ins Unendliche; in diesem Fall werden die Epipolarlinien exakt horizontal. Diese Konfiguration – Stereonormalfall genannt – ist in der Stereovision häufig näherungsweise anzutreffen und bietet bei der Korrespondenzsuche den Vorteil, dass aufgrund der horizontalen Epipolarlinien die Epipolargeometrie bekannt ist und eine Bildkorrespondenz lediglich in der Horizontalen, bei Digitalkameras also entlang einer Pixelzeile, gesucht werden muss.
2. Befinden sich die beiden Kameras voreinander, sind also in Blickrichtung gegeneinander verschoben, verschieben sich alle Epipole in die Bildmitte; die Epipolarlinien verlaufen also ausgehend vom Bildzentrum sternförmig nach außen. Diese Konfiguration tritt häufig bei mobilen Robotern auf, wenn eine einzelne Kamera in Fahrtrichtung ausgerichtet ist und zu verschiedenen Zeitpunkten Bilder aufnimmt. Die Bildkorrespondenzen werden dann in den aufeinander folgenden Bildern der Kamera gesucht.

Bei diesen Sonderfällen vereinfacht sich die Korrespondenzsuche, da die Epipolargeometrie bekannt ist. Bei Konfigurationen, in denen Kameraansichten nur näherungsweise parallel sind, kann dieser Zustand durch nachträgliche Rektifizierung hergestellt werden.

Erweiterung auf mehr als zwei Bilder

Trifokalgeometrie

Die Trifokalgeometrie ist die Erweiterung der Epipolargeometrie auf drei Bilder. Ist die Position eines Objektpunktes in zwei Bildern bekannt, so ist seine Position im dritten Bild der Schnittpunkt der beiden Epipolarlinien. Damit existiert im Unterschied zum Bildpaar ein eindeutiges Ergebnis, sofern der Punkt nicht in der Trifokalebene (die Ebene, die aus den drei Projektionszentren gebildet wird) liegt oder die drei Projektionszentren auf einer Linie liegen. Die Anordnung, bei der ein 3D-Punkt auf der Trifokalebene liegt, wird als singulärer Fall bezeichnet.

Es ist möglich, die Epipolargeometrie auf mehr als drei Bilder auszuweiten. Dies ist in der Praxis nur bei vier Ansichten üblich. Hier existiert der sogenannte quadrifokale Tensor, der die Beziehung von Bildpunkten und Linien zwischen diesen Bildern beschreibt. Für mehr als vier Ansichten wurden jedoch keine mathematischen Beziehungen untersucht, da die Komplexität der Modellierung und Berechnung wesentlich höher ist und in den meisten Anwendungen beginnend mit der fünften Kamera der zusätzliche Informationsgewinn nur noch gering ist.

Literatur

• Richard Hartley, Andrew Zisserman: Multiple View Geometry in Computer Vision. 2. Auflage. Cambridge University Press, 2004, ISBN 978-0-5215-4051-3. 
• Olivier Faugeras: Three-Dimensional Computer Vision – A Geometric Viewpoint. MIT Press, Cambridge (Massachusetts) 1993, ISBN 978-0-262-06158-2. 
• Volker Rodehorst: Photogrammetrische 3D-Rekonstruktion im Nahbereich durch Auto-Kalibrierung mit projektiver Geometrie. wvb Wissenschaftlicher Verlag Berlin, 2004, ISBN 978-3-9368-4683-6. 
• Oliver Schreer: Stereoanalyse und Bildsynthese. Springer, Berlin, 2008, ISBN 978-3-5402-3439-5. 
• Richard Hartley und Andrew Zisserman: Kapitel 9 aus Multiple View Geometry in computer vision. 2007. Abgerufen am 18. August 2007.
• Zhengyou Zhang: Determining the Epipolar Geometry and its Uncertainty: A Review. 1996. Abgerufen am 8. August 2007.
• Andrew Zisserman: MATLAB Functions for Multiple View Geometry. 2007. Abgerufen am 14. August 2007.

Weblinks

• Universität Bonn: Epipolargeometrie – Java-Applet zur Veranschaulichung der Epipolargeometrie
• SRI International – Java-Applets zur Illustration der Abbildungsgesetze bei einem, zwei oder drei Kameras
• Universität Siena – Epipolar Geometry Toolbox (Matlab-Routinen)
• Der Fundamental Matrix Song – Ein Song, welcher die Fundamentalmatrix und Epipolargeometrie kurz gefasst erklärt (von Daniel Wedge)

Einzelnachweise

1. ↑ Karl Kraus und Peter Waldhäusl: Photogrammetrie, Band 1. Ferd. Dümmler, Bonn 1997, ISBN 3-427-78646-3. 
2. ↑ Ephrahim Garcia: Technical Review of Team Cornell’s Spider DARPA Grand Challenge 2005. 28. August 2005 (online ; Stand: 17. Januar 2008). 
3. ↑ Horst von Sanden: Die Bestimmung der Kernpunkte in der Photogrammetrie (Dissertation an der Universität Göttingen). Göttingen 1908. 
4. ↑ ^{a b} H. C. Longuet-Higgins: A computer algorithm for reconstructing a scene from two projections. In: Nature. 293, 1981, S. 133-135. 
5. ↑ T. S. Huang and O. D. Faugeras: Some Properties of the E-matrix in two-view motion estimation. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. 11, 1989, S. 1310–1312. 
6. ↑ B. K. P. Horn: Relative Orientation. In: International Journal of Computer Vision. 4, 1990, S. 59-78. 
7. ↑ T. Vieville and D. Lingrand: Using singular displacements for uncalibrated monocular vision systems. In: Technical Report 2678 I.N.R.I.A. 1995. 
8. ↑ Zhengyou Zhang: Determining the Epipolar Geometry and its Uncertainty: A Review. 1996. Abgerufen am 8. August 2007.