Epipolargeometrie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Zwei Kameras nehmen von unterschiedlichen Standpunkten 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[Bearbeiten]

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 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 xL ab. Ausgehend von diesem Bildpunkt ist es lediglich möglich, den dazugehörigen Strahl, auf dem X liegt, zu bestimmen. Mögliche Objektpunkte X1, X2 oder X3, die ebenso wie X dem Bildpunkt xL 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 xL korrespondierenden Bildpunkt xR 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 selbst 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[Bearbeiten]

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 Punkt im anderen Bild gesucht, 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 schnell und mit geringem Aufwand analysiert werden muss. Wichtige Einsatzgebiete sind das maschinelle Sehen, die Vermessung von Werkstücken zur Qualitätsprüfung, die Gebäudeaufnahme bei der Architekturphotogrammetrie oder die Luftbildphotogrammetrie zur Erstellung von Kartenwerken.

Maschinelles Sehen[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Fig. 1a aus Tafel I im Artikel von Hauck 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_1 und O_2 die zugehörigen Projectionscentren. Die Schnittlinie g_{12} der zwei Projectionsebenen nennen wir Grundschnitt. Die Verbindungslinie O_1O_2 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 Christopher 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[Bearbeiten]

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 einer 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[Bearbeiten]

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), die nicht alle gleichzeitig Null sein dürfen, und (u/w,\, v/w,\, 1)=(x,\, y,\, 1) repräsentieren denselben Punkt im zweidimensionalen projektiven Raum \mathbb{P}^2, der projektiven Ebene. Entsprechendes gilt für den dreidimensionalen Raum.

Jeder Punkt des zweidimensionalen Raumes \R^2 oder des dreidimensionalen Raumes \R^3 kann durch homogene Koordinaten beschrieben werden. Einem Punkt des projektiven Raumes entspricht jedoch nur dann ein Punkt im affinen Raum, wenn w\,\neq\,0 ist. Die Punkte der projektiven Ebene mit w\,=\,0 werden Punkte im Unendlichen genannt. Da sie als Schnittpunkte von parallelen Geraden interpretiert werden können, entfällt in der projektiven Geometrie die Unterscheidung zwischen parallelen und nicht parallelen Geraden. Dies ist in der Perspektive beispielsweise bei der Beschreibung von Fluchtpunkten vorteilhaft. Da die Gleichung w\,=\,0 derjenigen einer Geraden in der projektiven Ebene entspricht,[F 1] wird die Menge der Punkte im Unendlichen Gerade im Unendlichen genannt.

Mit homogenen Koordinaten lässt sich die Abbildung der dreidimensionalen Objektpunkte mit den Koordinaten (X,\, Y,\, Z) 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, wenn w\,\neq\,0 ist. 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 – die Entfernung des Objekts von der Kamera – verlorengeht, ist sie nicht eindeutig umkehrbar.

Beziehung zwischen korrespondierenden Punkten[Bearbeiten]

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 zu \mathbf{x}_1 gehörenden Epipolarlinie in der Bildebene des zweiten Bildes 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örenden Epipolarlinie im zweiten Bild 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,[F 1] wobei \mathbf{l}_2 als Kreuzprodukt aus den beiden angegebenen 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.

Eine 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[Bearbeiten]

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[Bearbeiten]

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_2 x_1 f_{11} + x_2 y_1 f_{12} +x_2 f_{13} + y_2 x_1 f_{21} + y_2 y_1 f_{22} + y_2 f_{23} + x_1 f_{31} + y_1 f_{32} + f_{33} = 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[Bearbeiten]

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 generell kubische Gleichung hat – sofern sie nicht zu einer quadratischen Gleichung entartet – mindestens eine und höchstens drei reelle Lösungen \alpha. Mit jeder Lösung \alpha 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.

Wenn \det(\mathbf{F}_1 - \mathbf{F}_2)=0 ist, ist der kubische Term in \alpha gleich Null, so dass eine quadratische Gleichung vorliegt. Diese Gleichung hat höchstens zwei reelle Lösungen für \alpha, kann aber ohne reelle Lösung sein. Da jedoch die Determinante der Matrix \mathbf{F} = \mathbf{F}_1 - \mathbf{F}_2 verschwindet, ist \mathbf{F} singulär und damit eine Lösung für die gesuchte Fundamentalmatrix, so dass sich insgesamt wieder eine bis drei Fundamentalmatrizen als Lösung finden lassen. Alternativ kann die Matrix \mathbf{F}_2 mit -1 multipliziert werden. Man erhält dann wieder eine kubische Gleichung mit der Lösung \alpha=\tfrac{1}{2}. Dieses Vorgehen kann aus numerischen Gründen auch angewendet werden, wenn der Betrag von \alpha sehr groß ist.

8-Punkt-Algorithmus[Bearbeiten]

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. Durch die Verwendung von mehr Punkten, als für eine eindeutige Lösung erforderlich sind, kann außerdem geprüft werden, ob falsche Korrespondenzen oder andere Ausreißer vorliegen.

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 und falsche Korrespondenzen. 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[Bearbeiten]

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. Auf Grund von unterschiedlichen Perspektiven, mit denen die beiden Kameras die Szene betrachten, von ähnlichen Bildausschnitten, die nicht dasselbe Objekt darstellen, und von Bildrauschen enthält die Menge korrespondierender Punkte im Allgemeinen eine größere Anzahl von Fehlzuordnungen und kann daher nicht direkt zur Berechnung der Fundamentalmatrix benutzt werden.

Die folgenden Darstellungen zeigen eine Kirche, die von zwei Standpunkten aufgenommen wurde. Die zweite Kameraposition liegt weiter rechts und ist etwas weiter vom Kirchturm entfernt als die erste. Die Bilder 1 und 2 zeigen markante Punkte und Bild 3 das Ergebnis der Korrespondenzanalyse, bei der ähnliche Bildausschnitte – ohne Berücksichtigung der Aufnahmegeometrie – miteinander verglichen wurden. Es ist deutlich zu erkennen, dass nicht alle Korrespondenzen richtig bestimmt wurden. Gerade im Bereich der Bäume ist dies nicht der Fall, da hier die Zweige alle eine ähnliche Form und Helligkeit haben und damit die Korrespondenzanalyse zu falschen Ergebnissen führt. So werden beispielsweise Korrespondenzen zu markanten Punkten des im zweiten Bild rechten Baumes gefunden, obwohl er im anderen Bild gar nicht sichtbar ist.

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 Punktpaaren aufspüren. Auf die Berechnung von \mathbf{F} angewandt, besteht er aus folgenden Schritten:

  1. Wähle zufällig 7 oder 8 Punktkorrespondenzen aus den Datenpunkten. Das geschieht in der Erwartung, dass diese Korrespondenzen frei von Fehlern sind.
  2. Ermittle aus den gewählten Korrespondenzen mittels des 7- oder 8-Punkt-Algorithmus \mathbf{F}.
  3. Bestimme alle korrespondierenden Punkte, für die gilt: \mathbf{x}^\text{T}_2\mathbf{Fx}_1 \leq \epsilon und speichere diese. Der Schwellwert \epsilon ist notwendig, da auf Grund von Mess- und Rechenungenauigkeiten die Epipolargleichung \mathbf{x}^\text{T}_2\mathbf{Fx}_1 = 0 so gut wie nie exakt erfüllt ist. Je mehr Punktpaare die Ungleichung erfüllen, umso 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 zufällig ausgewählten Punktkorrespondenzen keine Fehler enthalten.

Die Fundamentalmatrix \mathbf{F} wird anschließend mittels der größten Menge Punktepaare aus Schritt 3 und dem 8-Punkt-Algorithmus bestimmt. Danach kann nochmals 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 Bild 1 als rote Vektoren eingezeichnet. In Bild 2 sind ausgewählte Punkte und deren Epipolarlinien im rechten Bild eingezeichnet. Korrekt zugeordnete markante Punkte und deren Epipolarlinien sind rot dargestellt. Punkte der Korrespondenzanalyse, die die Epipolargleichung nicht erfüllen, bei denen der Punkt im rechten Bild also nicht auf der entsprechenden Epipolarlinie liegt, sind grün gezeichnet. Falsche Korrespondenzen sind blau dargestellt. Diese Punkte erfüllen zwar die Epipolargleichung und zeigen ähnliche Bildausschnitte, sie sind jedoch nicht Bildpunkte desselben Objektpunktes. Der Epipol im rechten Bild ist der Schnittpunkt der Epipolarlinien und liegt links außerhalb des Bildes.

Sonderfälle[Bearbeiten]

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 Sonderfällen kommen. Dabei sind zwei Anordnungen insbesondere beim maschinellen Sehen praxisrelevant:

  1. Befinden sich die beiden Bildebenen der Kameras A und B (mit gleicher Kammerkonstante) in einer Ebene, sind also die Aufnahmerichtungen exakt parallel zueinander, verschieben sich die Epipole ins Unendliche und die Epipolarlinien werden zu Geradenscharen. Durch die Verwendung von homogenen Koordinaten ist es besonders einfach, diese Punkte im Unendlichen zu behandeln. In der Abbildung sind die Epipolarlinien der Kugelmittelpunkte und -tangenten exakt horizontal. Diese Konfiguration – Stereonormalfall genannt – ist in der Luftbildphotogrammetrie und 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. Je näher die Objekte den Kameras sind, desto weiter sind die Bildpunkte von der Position im anderen Bild entfernt: dieser Parallaxeneffekt gibt den Abstand der Objekte, kurz die dritte Dimension an.
    Dieser Sonderfall liegt auch beim menschlichen Sehen vor: Trotz der Beweglichkeit der Augen ist es fast unmöglich, die Augen in Richtungen zu lenken, die nicht in einer Ebene mit der Verbindungslinie zwischen den Augen liegen. Sie können eben nur in solchen Richtungen Korrespondenzen suchen.
  2. Befinden sich die beiden Kameras voreinander, sind sie also in Blickrichtung gegeneinander verschoben, verschieben sich die 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. Auch in diesem Fall ist der Abstand von der Kameraposition aus dem Parallaxeneffekt bestimmbar. Wenn der Roboter in einer Kurve die Kamera schwenkt, verschieben sich die Epipole horizontal, der vordere zur Kurvenaußenseite und der hintere nach innen, so dass der Sonderfall nicht mehr vorliegt.

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[Bearbeiten]

Trifokalgeometrie

Die Trifokalgeometrie ist die Erweiterung der Epipolargeometrie auf drei Bilder. Ist die Position eines Objektpunktes in zwei Bildern gegeben, so ist seine Position im dritten Bild der Schnittpunkt der beiden Epipolarlinien in diesem Bild. 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.

Abweichungen vom Modell der Lochkamera[Bearbeiten]

Die beschriebene Beziehung zwischen korrespondierenden Bildpunkten, die sich durch die Fundamentalmatrix vollständig beschreiben lässt, gilt nur für Fotoaufnahmen, die durch eine Lochkamera modelliert werden können. Treten beispielsweise Verzerrungen bei der Abbildung auf die Bildebene auf oder ist die Bildfläche keine Ebene, sind diese Abweichungen bei der Epipolargeometrie zu berücksichtigen. Insbesondere sind die Epipolarlinien, auf denen der zu einem Bildpunkt im ersten Bild korrespondierende Bildpunkt im zweiten Bild zu suchen ist, keine Geraden.

Verzeichnung[Bearbeiten]

Nur bei hochwertigen Objektiven tritt kaum eine Verzeichnung auf. Bei anderen Objektiven und entsprechenden Genauigkeitsanforderungen ist die Verzeichnung zu berücksichtigen. Die Verzeichnung kann oft als radiale Verzeichnung modelliert werden, d. h. sie nimmt mit dem Abstand vom Verzeichnungszentrum (meist in der Nähe der Bildmitte) zu.

Ist eine Kamera entsprechend kalibriert und die Verzeichnung bekannt, können die Bilder korrigiert werden. Mit diesen korrigierten Bildern kann dann wie mit verzeichnungsfreien Bildern gearbeitet werden.

Unter bestimmten Voraussetzungen kann die Verzeichnung in einer erweiterten Fundamentalmatrix berücksichtigt werden. Dabei wird für jedes Bild eine Verzeichnung angenommen, die durch jeweils einen (unbekannten) Parameter beschrieben werden kann und die dem Ersetzen der ebenen Bildfläche durch eine quadratische Fläche im dreidimensionalen projektiven Raum entspricht. Die Beziehung zwischen zwei korrespondierenden Punkten wird dann durch eine 4 \times 4-Fundamentalmatrix mit 9 Freiheitsgraden beschrieben.[9]

Panoramakameras[Bearbeiten]

Bei Panoramakameras, die Aufnahmen mit großem Bildwinkel ermöglichen, kann die Aufnahmegeometrie nicht durch eine Lochkamera mit einer ebenen Bildfläche modelliert werden. Die Beschreibung der Epipolargeometrie hängt von der Art der Panoramakamera ab. Besteht die Kamera beispielsweise aus einer Lochkamera und einem hyperbolischem Spiegel, so bilden die Epipolarlinien Kegelschnitte.

Fußnote[Bearbeiten]

  1. a b Eine Gerade wird in homogenen Koordinaten durch eine homogene lineare Gleichung zwischen den homogenen Koordinaten definiert, das heißt alle Punkte \mathbf{x}, die die Geradengleichung \mathbf{l}^\text{T} \mathbf{x} = 0 erfüllen, liegen auf der durch \mathbf{l} bestimmten Geraden. Die Punkte \mathbf{x} der Geraden, die zwei verschiedene Punkte \mathbf{x}_1 und \mathbf{x}_2 enthält, werden durch das Spatprodukt \det(\mathbf{x},\,\mathbf{x}_1,\,\mathbf{x}_2)\,=\,(\mathbf{x}_1 \times \mathbf{x}_2)^\text{T}\mathbf{x}\,=\,0 definiert.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Karl Kraus, 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 (darpa.mil (PDF; 1,3 MB), abgerufen am 23. Juli 2012).
  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, 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, D. Lingrand: Using singular displacements for uncalibrated monocular vision systems. In: Technical Report 2678 I.N.R.I.A. 1995.
  8. Vorlage:Internetquelle/Wartung/Zugriffsdatum nicht im ISO-FormatZhengyou Zhang: Determining the Epipolar Geometry and its Uncertainty: A Review. 1996, abgerufen am 8. August 2007 (PDF; 1,6 MB).
  9. Joao P. Barreto und Kostas Daniilidis: Fundamental Matrix for Cameras with Radial Distortion. In: Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05), 2005, S. 625–632 (PDF)
Dies ist ein als exzellent ausgezeichneter Artikel.
Dieser Artikel wurde am 8. März 2008 in dieser Version in die Liste der exzellenten Artikel aufgenommen.