Epipolargeometrie

Schematische Darstellung der Epipolargeometrie
Die Korrespondenz zum Bildpunkt (rot) im linken Bild ist im rechten Bild auf der Epipolarlinie (rot) zu finden.

Bei der Aufnahme eines Objekts oder einer Szene von zwei Kamerapositionen beschreibt die Epipolargeometrie die geometrische Beziehung korrespondierender Bildpunkte, also der beiden Bildpunkte eines Objektpunktes, in den beiden Bildern.

Aus den zwei Aufnahmen eines Objekts von unterschiedlichen Kamerapositionen kann das Objekt dreidimensional rekonstruiert werden. Dazu müssen korrespondierende Bildpunkte eines Objektpunktes einander zugeordnet werden.

In nebenstehender Grafik wird der Zusammenhang, der sich aus der Epipolargeometrie ergibt, verdeutlicht. Es ist allgemein nicht möglich, ausgehend von einem Bildpunkt xL mittels der Orientierung der Kamera den dazugehörigen Objektpunkt X zu rekonstruieren, da dessen Entfernung zur Kamera unbekannt ist. Es ist nur möglich, den 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. Alle diese möglichen Objektpunkte werden bei der Aufnahme des Objekts von einer anderen Position im zweiten Bild auf einer Geraden abgebildet, der Epipolarlinie. Bei bekannter Epipolargeometrie reduziert sich die Suche nach dem zum Bildpunkt xL korrespondierende Bildpunkt XR im zweiten Bild auf diese Epipolarlinie. Mit Hilfe der Epipolargeometrie kann folglich eine einfache Beziehung zwischen korrespondierenden Punkte ohne Kenntnis der Kameraposition hergestellt werden.

Die Grundlagen der Epipolargeometrie sind schon seit dem Anfang des 20. Jahrhunderts in der Photogrammetrie bekannt. Ihre Bedeutung nahm jedoch erst mit der automatischen Auswertung digitaler Bilder zu. Bei der manuellen Auswertung von Bildern konnten korrespondierende Punkte vom menschlichen Operateur meist problemlos zugeordnet werden. Bei der automatisierten Bildauswertung sollen diese Punkte automatisiert gefunden werden. Durch die Epipolargeometrie reduziert sich der Suchbereich bei der Korrespondenzanalyse auf die Epipolarlinie, wodurch der Rechenaufwand deutlich geringer wird.

Grundlagen und Begriffe

Nehmen zwei Kameras eine Szene von unterschiedlichen Positionen auf, befinden sich die beiden Projektionszentren der Kameras und ein aufgenommener Objektpunkt in einer Ebene, der sogenannten Epipolarebene. Diese Ebene schneidet die beiden Bilder in jeweils einer Geraden, den Epipolarlinien. Während der Aufnahme liegen die beiden Projektionszentren der Kameras auf einer Geraden. Diese Gerade durchstößt die beiden Bildebenen in jeweils einem Punkt, dem Epipol. Der Epipol des einen Bildes ist die Abbildung des Projektionszentrums der anderen Kamera und umgekehrt. Durch den Epipol laufen alle Epipolarlinien eines Bildes.

Die Epipolargeometrie hängt nur von den Parametern der Kameras ab und ist damit unabhängig von der Struktur der aufgenommenen Szene. Im Bereich der Photogrammetrie wurden zum Teil die Begriffe Kernstrahlgeometrie, Kernpunkt, Kernebene und Kernlinie anstelle von Epipolargeometrie, Epipol, Epipolarebene und Epipolarlinie verwandt. [1]

Zwei für das Verständnis der Thematik wichtige Begriffe sind homogene Koordinaten und die so genannten Projektionsmatrizen.

Die Lage eines Punktes in einem Kamerabild wird in der uns vertrauten Euklidischen Geometrie mit Hilfe von zweidimensionalen Bildkoordinaten beschrieben. Der Ursprung des Koordinatensystemes wird meist in eine Bildecke oder in die Bildmitte gelegt. Der Ort eines Punktes x im Bild kann mit einer zweidimensionalen Koordinate [x y] angegeben werden. In der projektiven Geometrie werden Punkte in sogenannten homogenen Koordinaten angegeben. Dafür wird eine zusätzliche Dimension eingeführt: ein zweidimensionaler Punkt wird hier durch 3 reele Zahlen x, y und w, ein dreidimensionaler Objektpunkt entsprechend mit 4 reellen Zahlen x, y, z und w beschrieben. Eine Transformation von homogenen Koordinaten in kartesische Koordinaten ist möglich, indem einfach x, y und w durch w geteilt wird.

Eine Projektionsmatrix ist eine 3×4-Matrix und beschreibt die perspektivische Abbildung eines dreidimensionalen Objektpunktes X=[ X Y Z W ] durch eine Kamera an die zweidimensionale Bildposition x=[ x y w ]:

Ist die Projektionsmatrix einer Kamera bekannt (sie ist damit kalibriert), so lässt sich mit Ihrer Hilfe die Bildposition, an der ein Objektpunkt abgebildet wird, berechnen. Da bei der Abbildung des dreidimensionalen Objektpunktes auf das zweidimensionale Kamerabild eine Dimension verloren geht, lässt sich umgekehrt bei bekannter Bildkoordinate x lediglich der Strahl, auf dem der abgebildete Objektpunkt X liegt, durch Umstellen der Gleichung bestimmen:

P-1 ist dabei die Pseudoinverse von P und C das Projektionszentrum der Kamera.

Geschichte

Die grundlegenden geometrischen Beziehungen waren schon am Anfang des 20. Jahrhunderts bekannt. So wurden sie unter anderen 1908 von Horst von Sanden in seiner DissertationDie Bestimmung der Kernpunkte in der Photogrammetrie“ untersucht.[2] Die Auswertung von photogrammetrisch aufgenommenen Bildern geschah bis zum Anfang der 1980er Jahre noch manuell. Da ein menschlicher Operateur bei genügend Szenenstruktur problemlos korrespondierende Punkte identifizieren kann, wurden die Erkenntnisse kaum angewandt. Erst das Aufkommen der digitalen Photogrammetrie und der automatisierten Bildauswertung bewirkte eine erneute intensivere Beschäftigung mit der Epipolargeometrie und ihrer Anwendung. Eine erste Arbeit, die das neu aufkommende Interesse zeigt, war die Dissertation von Longuet-Higgins[3]. In dieser Arbeit wurde zum ersten mal der Begriff fundamental matrix verwendet. Danach beschäftigen sich viele Wissenschaftler bis heute mit der Epipolargeometrie. Dazu gehören unter anderen Richard Harltey, Andrew Zisserman, Berthold K. P. Horn und Steve J. Maybank.

Anwendungen

Datei:Stanleyrobot.jpg
Stanley, Gewinner der DARPA Grand Challenge 2005

Die Epipolargeometrie wird vor allem in der projektiven Geometrie, der Photogrammetrie und dem maschinellen Sehen genutzt.

Maschinelles Sehen

Anwendung findet die Epipolargeometrie unter Anderem im Bereich des maschinellen Sehens. Insbesondere in der autonomen Robotik sind einfache Berechnungen für eine hohe Performance erforderlich, was zum Einen durch begrenzte Hardware auf mobilen Plattformen und zum Anderen durch die Notwendigkeit schneller Reaktionen zur Kollisionsvermeidung gegeben ist. 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, da der Suchraum eingeschränkt wird. So kam zum Beispiel bei der DARPA Grand Challenge die Programmbibliothek OpenCV zum Einsatz, die unter anderem schnelle Routinen zur Berechnung der Epipolargeometrie beinhaltet.[4]

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.

Mathematische Beschreibung

Um die Epipolargeometrie nutzen zu können, muss sie mittels einer Gleichung beschrieben werden, mit deren Hilfe man bei gegebenen Koordinaten eines Punktes im Bild 1 die dazugehörige Epipolarlinie im Bild 2 berechnen kann. Dies leistet die so genannte Fundamentalmatrix , die eine Darstellung der Art ergibt. Die Herleitung der gesuchten Gleichung kann auf zwei Arten geschehen: über geometrische Gesetzmäßigkeiten oder algebraisch.

Geometrische Herleitung

Die geometrische Herleitung geschieht in zwei Schritten:

  1. Für ein Punkt x1 in Kamerabild 1 wird der korrespondierende Punkt x2 im Bild 2 bestimmt. Dieser liegt notwendiger Weise auf der Epipolarlinie.
  2. Es wird die Gerade bestimmt, die x2 mit dem Epipol im Bild 2 verbindet. Genau diese Gerade ist die gesuchte Epipolarlinie l.

Zuerst wird ein zu x1 korrespondierender Punkt im Bild 2 gesucht. Im Allgemeinen lässt sich aus der Bildkoordinate x eines Punktes im ersten Bild und der Projektionsmatrix nur der Strahl bestimmen, auf dem sich der dazugehörige Objektpunkt X befinden muss. Ist aber bekannt, dass X gleichzeitig auf einer bestimmten, bekannten Ebene im Raum liegt, so ist es möglich, den Strahl mit dieser Ebene zu schneiden. Mit dem so erhaltenen Schnittpunkt liegt direkt die Koordinate des Objektpunktes vor. Mittels der Projektionsmatrix der anderen Kamera kann der dazugehörige Bildpunkt im zweiten Bild bestimmt werden. Diese drei Schritte — Berechnung des Strahles, Schnitt mit der Ebene, Rückprojektion des Punktes ins andere Bild — lassen sich rechnerisch zusammenfassen. Aus der Ebenengleichung und den beiden Projektionsmatrizen kann eine so genannte Homographie H abgeleitet werden. Das ist eine 3×3-Matrix. Es gilt:

Bezeichnet e2 den Epipol im Bild 2, so ist die Epipolarlinie l das Kreuzprodukt vom Epipol e2 und x2:

Die Schreibweise [e2]x wird benutzt, um das Kreuzprodukt als Matrixmultiplikation ausdrücken zu können. Damit ist die Epipolargeometrie mathematisch beschrieben. Der Term [e2]x·H wird in der Fundamentalmatrix F zusammengefasst:

Algebraische Herleitung

Diese alternative Herleitung beruht auf der Idee, einen beliebigen Punkt x 1 im Bild 1 auszuwählen und mittels der Projektionsmatrizen P1 und P2 der beiden Kameras zwei korrespondierende Punkt im Bild 2 zu berechnen. Liegen diese vor, so lässt sich die Epipolarlinie aus diesen beiden Punkten berechnen.

Ist ein Punkt x1 im Kamerabild 1 gegeben, lässt sich mit Hilfe der Projektionsmatrix der Kamera 1 der Strahl, auf dem der dazugehörige Objektpunkt X liegt, berechnen. Zwei Punkt auf diesem Strahl sind P1+x1 und das Projektionszentrum der Kamera 1, C1. Diese zwei Punkte bilden sich im Kamerabild 2 auf P2P1+x1 und P2C1 ab. Die Epipolarlinie l muss notwendiger Weise durch diese zwei Punkte verlaufen:

Somit ist der mathematische Zusammenhang gefunden. Auch hier wird der Term P2C1xP2P1+x1 durch F subtituiert werden. Es ergibt sich wiederum:

Der Term P2C1 ist die Abbildung des Projektionszentrums der Kamera 1 im Kamerabild 2 und damit der Epipol:

Somit erhält man den gleichen Zusammenhang wie bei der geometrischen Herleitung mit der Spezialisierung H=P2P1+.

Eigenschaften der Fundamentalmatrix

Die Fundamentalmatrix (auch Bifokal-Tensor genannt) enthält die gesamte Information über die Epipolargeometrie. F ist zunächst eine 3x3-Matrix mit 9 Elementen. Sie ist auf Grund der homogenen Koordinaten nur bis auf einen Skalierungsfaktor bestimmt (die Bildkoordinaten können immer durch w geteilt werden). Damit sind zunächst nur 8 Parameter relevant. Da sich aber alle Epipolarlinien in einem Punkt schneiden müssen, sind diese 8 Elemente von F nicht unabhängig, sondern durch die Singularitätsbedingung (die Determinante muss gleich 0 sein) miteinander verknüpft. Die Fundamentalmatrix hat damit 7 Freiheitsgrade.

Mittels der Fundamentalmatrix kann man zu einem Punkt im Bild 1 die dazugehörige Epipolarlinie im Bild 2 berechnen:

beziehungsweise vom Bild 2 ausgehend

Es ist nicht möglich, aus einer gegebenen Epipolarlinie l den ursprünglichen Punkt x zu berechnen (einen Invertierung von F ist auf Grund der Singularität nicht möglich).

Die Berechnung der beiden Epipole kann erfolgen über die Beziehung

Für die Epipolarlinie eines Punktes aus Bild 1 im gleichen Bild 1 (entsprechend auch für einen Punkt im Bild 2) gilt

Die Projektion des Punktes fällt quasi auf ihn selbst zurück. Daraus und aus l2=Fx1 lässt sich die sogenannte Epipolargleichung herleiten. Diese lautet für jedes korrespondierende Punktepaar x1 - x2:

.

Berechnung

Die Fundamentalmatrix und damit die Epipolargeometrie lässt sich wie gezeigt bei bekannter Kalibrierung der beiden Kameras direkt aus den Projektionsmatrizen berechnen. Da die Berechnung der Fundamentalmatrix meist vor einer Bestimmung der Projektionsmatrizen durchgeführt wird, tritt dieser Fall selten auf. Es ist jedoch möglich, F nur mit Hilfe von Punktkorrespondenzen zu berechnen. Dieses wird im Folgenden erläutert.

Um aus einer Menge korrespondierender Bildpunkten die Fundamentalmatrix zu bestimmen, wird die Epipolargleichung ausmultipliziert. Es ergibt sich für jede Punktkorrespondenz folgende Gleichung:

beziehungsweise in Vektorschreibweise:

mit

Es ist möglich, mit n Punktkorrespondenzen n Gleichungen aufzustellen. Es ergibt sich folgendes lineares Gleichungssystem:

(Der obere Index gibt die Punktnummer an.) Da die Fundamentalmatrix 7 Freiheitsgrade besitzt, ist es möglich, dieses Gleichungssystem mit einer minimalen Anzahl von 7 Punkten zu lösen. In der Praxis existieren zur Berechnung von F zwei Verfahren: der 7-Punkt-Algorithmus und der 8-Punkt-Algorithmus.

7-Punkt-Algorithmus

Da die Fundamentalmatrix lediglich 7 Freiheitsgrade besitzt, reichen 7 Punktkorrespondenzen zur Berechnung von F aus. Allerdings ist das Gleichungssystem Af=0 mit lediglich 7 Korrespondenzen und daraus resultierenden 7 Gleichungen unterbestimmt. Eine Lösung lässt sich jedoch aus dem so genannten Nullraum von A berechnen. Es ergibt sich für F ein Lösungsraum in der Form

F1 und F2 sind die aus den beiden Nullvektoren f1 und f2 von A berechneten Fundamentalmatrizen. Diese sind wiederum diejenigen rechten Nullvektoren von A, die dem Singulärwert 0 entsprechen.

Da bei der Detektion der 7 korrespondierenden Punkte im Allgemeinen kleinere Abweichungen auftreten (das Bild kann nur mit einer bestimmten Genauigkeit ausgemessen werden, die Kamera besitzt Abbildungsfehler oder die Bildpunkte werden nicht exakt lokalisiert), hat die ermittelte Fundamentalmatrix nicht den Rang 2. Das hat die Konsequenz, dass sich die Epipolarlinien eines Bildes nicht mehr alle im Epipol schneiden. Um jetzt aus der Menge der Lösungen ein F auszuwählen, welches den Rang 2 hat, wird ausgenutzt, dass F singulär ist und damit die Determinante von F gleich 0 sein muss. Es ergibt sich aus dieser Singularitätsbedingung:

Diese Formel wird nach aufgelöst. Es ergibt sich ein kubisches Polynom mit einer oder drei Lösungen. Ergeben sich drei Lösungen, wählt man diejenige Lösung aus, die den geringsten geometrischen Fehler besitzt.

8-Punkt-Algorithmus

Die Idee für dieses Verfahren stammt von Longuet-Higgins.[5] Beim 8-Punkt-Algorithmus liegen mindestens 8 korrespondierende Bildpunktpaare vor. Das Ziel ist, eine Matrix F zu finden, welche die Epipolargleichung erfüllt. Dazu wird das Gleichungssystem Af=0 mittels einer Singulärwertzerlegung gelöst. Man erhält einen Vektor f, der umgestellt die gesuchte Fundamentalmatrix F ergibt.

Die so gewonnenen Fundamantalmatrix ist jedoch im Allgemeinen auf Grund von Messfehlern in den Bildpunkten nicht singulär. Daher werden in einem weiteren Schritt alle Singulärwerte von F bestimmt (meist wieder mittels einer Singulärwertzerlegung). Dabei wird F in drei Matrizen zerlegt, von der eine explizit die drei Singulärwerte von F enthält. Der kleinste Singulärwert, der 0 sein sollte, wird gleich 0 gesetzt. Anschließend wird F wieder aus den drei Matrizen zusammengesetzt. Da jetzt ein Singulärwert gleich 0 ist, erfüllt die Fundamentalmatrix die Singularitätsbedingung.

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 werden 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, werden zu jedem Punkt im ersten Bild der ihm ähnlichste im zweiten Bild bestimmt. Eine Korrespondenzanalyse liefert dafür 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. Die Lokalisation markanter Punkte sowie die Korrespondenzanalyse sind in den nächsten Bildern dargestellt. Es ist deutlich zu erkennen, dass nicht alle Korrespondenzen richtig bestimmt wurden.

Die Fehlzuordnungen müssen vor der Berechnung ausgeschlossen werden. Zu diesem Zweck wird der so genannten RANSAC-Algorithmus eingesetzt. Mit diesem ist es möglich, Fehlzuordnungen in den Punktepaaren aufzuspüren. Auf die Berechnung von F angewandt besteht dieser Algorithmus 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 F.
  3. Bestimme alle korrespondierenden Punkte, für die gilt: x2TFx1=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 N mal.

Die Fundamentalmatrix 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.

Das Ergebnis ist in den folgenden zwei Bildern dargestellt:

Pseudocode

Der gesamte Algorithmus ist hier als Pseudocode dargestellt.

Eingabe

Zwei Bilder

Ausgabe

Fundamentalmatrix, welche die Beziehung zwischen den beiden Bildern beschreibt

Ablauf

 Suche in beiden Bildern markante Punkte 
 Bestimme korrespondierende Punkte x1 <--> x2
 --------------------------------------------
 RANSAC
  Wiederhole N mal
    Wähle zufällig 7 Punktkorrespondenzen
    Berechne daraus F mit dem 7-Punkt-Algorithmus
    Berechne die Menge Punktepaare, für die gilt x2TFx1=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

Erweiterung

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 eine 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 mit 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 Ansichten beschreibt. Für mehr als vier Ansichten wurden jedoch keine mathematischen Beziehungen untersucht.

Einzelnachweise

  1. Karl Kraus und Peter Waldhäusl: Photogrammetrie, Band 1. Ferd. Dümmler, Bonn 1997, ISBN 3-427-78646-3.
  2. Horst von Sanden: Die Bestimmung der Kernpunkte in der Photogrammetrie (Dissertation an der Universität Göttingen). Göttingen 1908.
  3. Q. T. Luong: Fundamental matrix and self-calibration (PhD Thesis, University of Paris). Orsay 1992.
  4. Ephrahim Garcia: Technical Review of Team Cornell’s Spider DARPA Grand Challenge 2005. 28. August 2005 (online [PDF; abgerufen am 17. Januar 2008]).
  5. H.C. Longuet-Higgins: A Computer Algorithm for Reconstructing a Scene from Two Projections. In: Nature. Band 293, September 1981, S. 133–135 (visionbib.com).

Literatur

  • Faugeras, O.: Three-Dimensional Computer Vision - A Geometric Viewpoint. Cambridge MA: MIT Press, Cambridge 1993, ISBN ISBN 978-0-262-06158-2(?!).
  • 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(?!).

Vorlage:Lesenswert Kandidat