Epipolargeometrie

Die Epipolargeometrie ist ein Begriff aus der projektiven Geometrie, der Photogrammetrie und dem maschinellen Sehen und stellt die projektive Beziehung zwischen Punkten in zwei Kamerabildern her. Sie hängt nur von den Parametern der Kameras ab und ist damit unabhängig von Struktur der aufgenommenen Szene. Mathematisch beschrieben wird sie mit Hilfe der Fundamentalmatrix.

Grundlagen

Nimmt man mit zwei Kameras einen Objektpunkt P auf, dann existieren einige grundlegende Beziehungen, die mittels der Epipolargeometrie beschrieben werden können. Während der Aufnahme befinden sich die Projektionszentren der Kameras und ein aufgenommener Objektpunkt in einer Ebene, der sogenannten Epipolarebene. Diese schneidet die beiden Bilder in jeweils einer Geraden, der Epipolarlinie. Der Schnittpunkt zwischen Epipolarlinie und der Verbindung zwischen den beiden Projektionszentren wird Epipol genannt. Durch ihn laufen alle Epipolarlinien eines Bildes.

Im Bereich der Photogrammetrie spricht man zum Teil anstelle von Epipol, Epipolarebene und Epipolarlinie von Kernpunkt, Kernebene und Kernlinie.

Sehr hilfreich ist die Epipolargeometrie bei der Korrespondenzanalyse. Sucht man zu einem Punkt m in Bild 1 den korrespondierenden Punkt m' in Bild 2, so kann sich dieser nur auf der Epipolarlinie befinden. Dadurch schränkt sich der Suchbereich vom eigentlich zweidimensionalen Bildbereich auf die eindimensionale Epipolarlinie ein. Dies bedeutet eine erhebliche Rechenzeitersparnis.

Die Epipolargeometrie bei zwei Ansichten

Die Epipolargeometrie beinhaltet die geometrischen Zusammenhänge zwischen zwei Bildern. Sie wird mathematisch durch die Fundamentalmatrix beschrieben.

Die Fundamentalmatrix

Die Fundamentalmatrix ist eine singuläre 3x3-Matrix vom Rang 2 mit 7 Freiheitsgraden. Bezeichnet man mit F die Fundamentalmatrix und mit m bzw. m' die korrespondierenden Punkte in homogener Darstellung , so gilt:

$\mathbf {m} ^{'{\text{T}}}\mathbf {F} \mathbf {m} =0$.

6 der 7 Freiheitsgrade resultieren aus den linear unabhängigen Spaltenvektoren $f_{1}$ und $f_{2}$ von F. Der dritte Spaltenvektor $f_{3}$ ist eine Linearkombination aus $f_{1}$ und $f_{2}$: $f_{3}=\alpha f_{1}+\beta f_{2}$. Da die Fundamentalmatrix aber nur bis auf einen skalaren Faktor bestimmt ist (das heisst, die gesamte Matrix kann mit einem beliebigen Faktor multipliziert werden, ohne das Ergebnis der Epipolargleichung zu verändern), kann man die Linearkombination durch $\alpha$ teilen und kommt damit von zwei auf einen Parameter:

$f_{3}=f_{1}+{\frac {\beta }{\alpha }}f_{2}$.

Die Epipolarlinie $l_{\mathbf {m'} }$ im Bild 2 eines Bildpunktes m im Bild 1, auf der sich der korrespondierende Bildpunkt m' befindet, lässt sich über die Gleichung

$l_{\mathbf {m'} }=\mathbf {Fm}$

berechnen.

Berechnung der Fundamentalmatrix

Wenn für ein Kamerasystem die inneren und äußeren Parameter nicht bekannt sind, kann die Fundamentalmatrix über den 7-Punkt oder den 8-Punkt Algorithmus analytisch bestimmt werden. Beide Verfahren basieren auf der Epipolargleichung. $\mathbf {m} =[x\quad y\quad 1]$ und $\mathbf {m'} =[x'\quad y'\quad 1]$ sind die korrespondierenden Punkte in den beiden Bildern.

Aus

$(x'\quad y'\quad 1){\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\\y\\1\end{pmatrix}}=0$

ergibt sich

$x'xf_{11}+x'yf_{12}+x'f_{13}+y'yf_{21}+y'yf_{22}+y'f_{23}+xf_{31}+yf_{32}+f_{33}=0$

Mit n Punktkorrespondenzen kann man dann folgendes Gleichungssystem aufstellen:

$\mathbf {Af} ={\begin{bmatrix}x'_{1}x_{1}&x'_{1}y_{1}&x'_{1}&y'_{1}x_{1}&y'_{1}y_{1}&y'_{1}&x_{1}&y_{1}&1\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\x'_{n}x_{n}&x'_{n}y_{n}&x'_{n}&y'_{n}x_{n}&y'_{n}y_{n}&y'_{n}&x_{n}&y_{n}&1\end{bmatrix}}\mathbf {f} =0$

Da die Fundamentalmatrix 7 Freiheitsgrade besitzt, ist es möglich, dieses Gleichungssystem mit einer minimalen Anzahl von 7 Punkte zu lösen.

7-Punkt Algorithmus

Mit 7 Punktkorrespondenzen ergibt sich eine 7×9-Matrix A vom Rang 7. Die Lösung der Gleichung Af=0 lässt sich aus dem zweidimensionalen Nullraum von A berechnen. u und v sind die rechten Nullvektoren von A, die dem Singulärwert 0 entsprechen. U und V sind die 3×3-Matrix-Repräsentationen dieser beiden Vektoren. Die gesuchte Fundamentalmatrix F kann dann berechnet werden mit

$\mathbf {F_{t}} =t\mathbf {U} +(1-t)\mathbf {V} ,\quad t\in \mathbb {R}$

Da die Matrix F singulär ist, ergibt sich zusätzlich folgende Bedingung:

$\det(\mathbf {F_{t}} )=\det(t\mathbf {U} +(1-t)\mathbf {V} )=0.$

Durch Ausmultiplizieren der 3×3-Determinante erhält man ein kubisches Polynom. Die Nullstellen dieses Polynoms sind dann die drei Lösungen für F. Man wählt von diesen drei Lösungen diejenige aus, welche den geringsten geometrischen Fehler besitzt.

8-Punkt Algorithmus

Die Idee für dieses Verfahren stammt von Longuet-Higgins. Beim 8-Punkt Algorithmus liegen gleich oder mehr als 8 homologe Bildpunkte vor. Das Ziel ist, eine Matrix F zu finden, welche die Epipolargleichung erfüllt.

Als erstes werden die Punkte normalisiert. Dabei werden alle Punkte so verschoben, dass ihr Schwerpunkt im Ursprung des Koordinatensystems liegt. Danach werden sie so skaliert, dass der durchschnittliche Abstand zum Ursprung √2 beträgt. Diese Vorgehensweise führt zu numerisch stabileren Ergebnissen. Beide Transformationen werden für jedes Bild unabhängig durchgeführt. Die jeweiligen Transformationsmatrizen T und T' müssen gespeichert werden.

Anschließend löst man für die normalisierten Koordinaten das Gleichungssystem Af=0. Dazu wird die Matrx A mittels der Singulärwertzerlegung (auch singular value decomposition, SVD) in die Matrizen U, Σ und V zerlegt. Im Idealfall bildet die letzte Spalte von V den Kern von A. Dies ist aber auf Grund der Messfehlern in den Bildpunkten nur bei genau 8 Punkten der Fall. In Folge dessen wird die Singularität dadurch erzwungen, dass F aus der letzten Spalte von V gebildet wird. Das ermittelte F wird per SVD zerlegt und der kleinste Singulärwert=0 gesetzt. Mit der neuen Matrix Σ und den Matrizen U und V, die bei der zweiten SVD entstanden sind, wird Ḟ=U Σ V'ᵀ berechnet. So kann die Singularität erzwungen werden. Anschließend müssen die Transformationen rückgängig gemacht werden. Dazu erfolgt die Denormalisierung F=T'ᵀ Ḟ T.

Vorgehen in der Praxis

In der Praxis wird zur Berechnung der Fundamentalmatrix eine Kombination aus 7-Punkt, 8-Punkt Algorithmus und RANSAC verwendet. Zuerst werden markante Punkte in beiden Bildern mit Hilfe eines Interest-Operators bestimmt. Danach wird mittels einer Korrespondenzanalyse jeweils homologe Punkte gesucht. Dazu wird zwischen einem Punkt im ersten Bild und nacheinander allen Punkte im zweiten Bild ein Ähnlichkeitsmaß berechnet. Der Punkt im Bild 2 mit der größten Ähnlichkeit wird als korrespondierend angenommen, wenn das Ähnlichkeitsmaß einen bestimmten Wert überschreitet. Dies führt man mit allen Punkten im Bild 1 durch.

Das Ergebnis der Korrespondenzanalyse enthält häufig eine größere Anzahl Fehlzuordnungen. Diese müssen vor der Berechnung der Fundamentalmatrix ausgeschlossen werden. Dazu wird der RANSAC-Algorithmus benutzt, mit dessen Hilfe diese detektiert werden können. Anschließend berechnet man mit der übrig gebliebenen Menge an Korrespondenzen die Fundamentalmatrix. Ist diese berechnet, verkleinert sich wie beschrieben der Suchbereich nach korrespondierenden Punkten auf die Epipolarlinie. Daher führt man jetzt nochmalig eine Korrespondenzanalyse durch, bei der die berechnete Fundamentalmatrix zum Einsatz kommt 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.

Pseudocode

Eingabe

Zwei Bilder

Ausgabe

Fundamentalmatrix, welche die Beziehung zwischen den beiden Bilder beschreibt

Ablauf

 Suche in beiden Bildern markante Punkte
 Bestimme korrespondierende Punkte

-

 RANSAC
 Wiederhole N mal
   Wähle zufällig 7 Punktkorrespondenzen
   Berechne daraus F mit dem 7-Punkte Algorithmus
   Berechne die Menge Punktepaare, für die gilt m'Fm=0 und speichere diese
 Ende
 Berechne mit der größten Menge Punktepaare und dem 8-Punkt Algorithmus F

-

 Suche mit Hilfe von F weitere Punktkorrespondenzen und berechne F mit allen neu

Beispiel

Im folgenden ist eine beispielhafte, illustrierte Berechnung dargestellt. Bild 1 und 2 stellen das linke beziehungsweise rechte Bild mit eingezeichneten markanten Punkten dar. Im dritten sind die Korrespondenzen dargestellt, darunter auch viele Fehlkorrespondenzen, vor allem im Bereich des Baumes am linken Bildrand. Das vierte zeigt die Korrespondenzen nach dem RANSAC-Algorithmus. Nur diese werden dann zur Berechnung von F herangezogen. Im letzten Bild sind eine Auswahl von Epipolarlinien markanter Punkte eingezeichnet.

• Ablauf und Ergebnis der Berechnung der Fundamentalmatrix
• 
  1. Linkes Bild mit markanten Punkten.
• 
  2. Rechtes Bild mit markanten Punkten.
• 
  3. Mutmassliche Korrespondenzen
• 
  4. Korrespondenzen nach RANSAC, mit denen F berechnet wird.
• 
  5. Einige Epipolarlinien, berechnet mit F

Die Trifokalgeometrie

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

Der Trifokaltensor

Der Trifokaltensor τ ist ein Tensor, der die geometrischen Beziehungen zwischen den 3 Kameras enthält. Er besteht aus drei homogenen 3×3-Matrizen und besitzt 18 Freiheitsgrade.

Berechnung des Trifokaltensor

Zur Berechnung des Trifokaltensors müssen die drei Projektionsmatrizen P der Kameras bekannt sein. Eine Projektionsmatrix beschreibt die perspektivische Abbildung eines dreidimensionalen Objektpunktes X=[X Y Z] an die Bildposition m=[x y w]:

$\mathbf {x} =\mathbf {PX}$

beziehungsweise

${\begin{bmatrix}x\\y\\w\end{bmatrix}}={\begin{bmatrix}p_{11}&p_{11}&p_{13}&p_{14}\\p_{21}&p_{21}&p_{23}&p_{24}\\p_{31}&p_{31}&p_{33}&p_{34}\end{bmatrix}}{\begin{bmatrix}X\\Y\\Z\end{bmatrix}}$

Bezeichnet man nun die drei Projektionsmatrizen mit $\mathbf {P} _{1}=[\mathbf {I} |\mathbf {0} ]$, $\mathbf {P} _{2}=[a_{i}j]$ und $\mathbf {P} _{3}=[b_{i}j]$ (I ist dabei die Einheitsmatrix und 0 der Nullvektor), so berechnet sich der Trifokaltensor τ mit

$\tau _{ijk}=a_{ji}b_{k4}-a_{j4}b_{ki}\quad {\text{mit}}\quad i,j,k=1,2,3$

Erweiterungen auf mehr als drei Bilder

Es ist auch möglich, die Epipolargeometrie auf mehr als drei Bilder auszuweiten. Dies ist in der Praxis aber nur bei vier Ansichten üblich. Hier existiert der sog. quadrifokale Tensor, der die Beziehung von Bildpunkten und Linien zwischen diesen Ansichten beschreibt. Für mehr als vier Ansichten existieren jedoch keine weiteren mathematischen Beziehungen.

Literatur

• Zhengyou Zhang: Determining the Epipolar Geometry and its Uncertainty: A Review. 1996, abgerufen am 8. August 2007. 

• Peter Kovesi: MATLAB and Octave Functions for Computer Vision and Image Processing. 2007, abgerufen am 9. August 2007. 

• Richard Hartley and Andrew Zisserman: Multiple View Geometry in computer vision. Cambridge University Press, Cambridge 2003, ISBN ISBN 0-521-54051-8(?!). 

• Volker Rodehorst: Photogrammetrische 3D-Rekonstruktion. Wissenschaftlicher Verlag Berlin, Berlin 2004, ISBN ISBN 3-936846-83-9(?!). 

• Oliver Schreer: Stereoanalyse und Bildsynthese. Springer, Berlin 2006, ISBN ISBN 978-3540234395(?!).