Korrespondenzproblem (Bildverarbeitung)
Das Korrespondenzproblem betrifft als Basis für die Berechnung des optischen Flusses (optical flow) und des Stereosehens (stereo matching) ein fundamentales Problem der Bildverarbeitung.[1]
Grundlagen Bearbeiten
Sowohl in der Stereoskopie als auch beim Berechnen des optischen Flusses werden in zwei digitalen Bildern diejenigen Punkte (Pixel) gesucht, welche jeweils die Projektion desselben Elements derselben Szene darstellen. Solche Bildpunkte, die vom selben Objektpunkt einer räumlichen Szene stammen, werden als korrespondierende Bildpunkte bezeichnet. Das Auffinden korrespondierender Bildpunkte in Stereobildern wird als Korrespondenzproblem bezeichnet. Das Ergebnis ist üblicherweise eine Disparitätenkarte (disparity map), worin für jeden Pixel des einen Bildes ein Verschiebungsvektor zum korrespondierenden Pixel des anderen Bildes ermittelt wird. Zu diesem Zweck muss eine eindeutige Korrespondenz zwischen den Punkten der einzelnen Bilder hergestellt werden. Da die Zuordnung der Bildpunkte zum einen stark mehrdeutig sein kann und zum anderen nicht immer möglich ist, wird nach der Hadamard’schen Definition das Korrespondenzproblem auch als „schlecht gestelltes“ Problem bezeichnet.[2] Zusätzlich wird die Lösung des Korrespondenzproblems durch perspektive Verzerrungen, Rauschprozesse sowie Beleuchtungs- und Kontrastunterschiede zwischen den Bildern erschwert.
Okklusionen Bearbeiten
Eine der bedeutendsten Fehlerursachen in der stereoskopischen Korrespondenzbestimmung stellen Bereiche in einer betrachteten Szene dar, die nur aus einer Kameraperspektive zu sehen sind. Zu den Bildbereichen, in die diese Regionen der Szene abgebildet werden, existieren keine Korrespondenzpartner im anderen Stereobild. Diese Bildbereiche werden als Okklusionen (Verdeckungen) bezeichnet. Werden Okklusionen bei der Korrespondenzbestimmung nicht geeignet berücksichtigt, so kommt es je nach Ansatz zu mehr oder weniger starken Fehlkorrespondenzen und damit zu einer fehlerbehafteten Tiefenrekonstruktion. Okklusionen stellen daher ein schwerwiegendes Problem in der Stereoskopie dar.[3]
Blendenproblem Bearbeiten
Bei einer Stereogeometrie mit parallelen optischen Achsen ist die Verschiebung korrespondierender Bildpunkte in einem Stereobildpaar immer parallel zur Stereobasis gerichtet. Bei einer genauen Kenntnis der Kamerageometrie kann aufgrund dieser Tatsache die Richtung der Disparität im Vorfeld ermittelt und somit die Suche nach korrespondierenden Bildpunkten erheblich erleichtert werden. Problematisch sind jedoch Bildregionen, in denen keine Strukturen oder Intensitätsänderungen in Richtung der Stereobasis auftreten. In diesem Fall kann eine Verschiebung korrespondierender Bildpunkte nicht festgestellt werden. Da die Detektion der Verschiebung in der Stereoskopie meist durch einen lokalen Operator erfolgt, wobei der übrige Teil der Szene ausgeblendet wird, wird dieses Problem auch als ein Spezialfall des sogenannten Blendenproblems betrachtet, dem in der Bewegungsanalyse (optischer Fluss) eine besondere Bedeutung zukommt.[5]
Einschränkungen in der Stereoskopie Bearbeiten
Bedingt durch seine spezielle Natur kann das Korrespondenzproblem, ebenso wie viele andere schlecht gestellte Probleme, nur unter Ausnutzung geeigneten Vorwissens eindeutig gelöst werden. Mit Hilfe dieses Vorwissens wird der Lösungsraum entsprechend eingeschränkt und das Problem in ein „gut gestelltes“ Problem umgewandelt.[2] Die Einschränkungen des Lösungsraums beziehen sich zum einen auf den Abbildungsprozess und die Geometrie der verwendeten Kameras (Epipolar- und Eindeutigkeitseinschränkung) und zum anderen auf postulierte Eigenschaften der beobachteten Szene (Kontinuitäts-, Ordnungs- und Gradienteneinschränkung).[6]
Algorithmen Bearbeiten
Die Zuordnung von korrespondierenden Bildelementen kann in der digitalen Bildverarbeitung durch verschiedene Algorithmen und mathematische Verfahren erfolgen. Die einzelnen Verfahren unterscheiden sich hinsichtlich ihrer Fehleranfälligkeit und des erforderlichen Berechnungsaufwandes teilweise erheblich.
Lokale Verfahren Bearbeiten
Bei den lokalen Verfahren erfolgt die Zuordnung einzelner Bildbereiche der Stereobilder anhand der Grauwerte bzw. der lokalen Umgebung eines Pixel (Grauwertmatrix). Üblicherweise wird die Übereinstimmung der Bildbereiche über die Berechnung eines Ähnlichkeitsmaßes wie z. B. einer lokalen Kreuzkorrelation bestimmt. Die Disparität ergibt sich im einfachsten Fall durch die Verschiebung der Bildregionen zwischen linkem und rechtem Bild, die sich durch das größte Maß an Übereinstimmung auszeichnen. Einige dieser Verfahren selektieren durch einen sogenannten Interest-Operator vor der Korrespondenzbestimmung zunächst aus jedem Bild Gebiete mit besonderen Eigenschaften, die anschließend miteinander verrechnet werden.[7]
Merkmalsbasierte Verfahren Bearbeiten
Die meisten der existierenden stereoskopischen Ansätze können in die Kategorie der merkmalsbasierten Verfahren eingeordnet werden. Bei dieser Technik werden zunächst Merkmale aus den Bilddaten extrahiert, die das Bild auf einer abstrakteren Ebene beschreiben. Anschließend wird in einem weiteren Schritt eine Korrespondenzbestimmung auf der Ebene der Merkmale durchgeführt. Häufig verwendete Merkmale sind hierbei Kanten, Linien- oder Eckenpunkte oder auch Kanten- bzw. Liniensegmente. Große Bedeutung kommt bei diesen Verfahren den differenzierenden Filtern zu, die Grauwertänderungen wie Kanten oder Linien aus den Bildsignalen herausfiltern.[8]
Phasenbasierte Verfahren Bearbeiten
Die Grundlage für die sogenannten phasenbasierten Methoden zur Disparitätsmessung liefert der Verschiebungssatz der Fouriertransformation. In der Stereobildverarbeitung ist jedoch im Allgemeinen nicht mit einer ausschließlich globalen Verschiebung zwischen den Bildern zu rechnen, da unterschiedlich weit vom Kamerasystem entfernte Objekte unterschiedliche Disparitätswerte in den Stereobildern aufweisen. Folglich müssen die Verschiebungen korrespondierender Bildbereiche in dem Stereobildpaar durch lokale Operatoren ermittelt werden, so dass eine Phasenkorrelation generell nur in Verbindung mit einer auf kleinere Bildbereiche begrenzte Fouriertransformation sinnvoll ist. Die größte Bedeutung innerhalb der phasenbasierten Verfahren kommt den sogenannten Phasendifferenzmethoden zu. Die Phaseninformation ergibt sich bei diesen Techniken aus der Antwort von komplexen Filterpaaren, mit denen die Eingangsbilder gefiltert werden. Eine wesentliche Voraussetzung für dieses Verfahren ist, dass die Phase der Filterantworten näherungsweise eine lineare Funktion des Ortes ist. Diese Eigenschaft kann dann erreicht werden, wenn die Filterübertragungsfunktion keinen Gleichanteil aufweist und für negative Frequenzen verschwindet. Diese Eigenschaft wird als Quadraturverhalten bezeichnet.[9] Da die Phaseninformation invariant bezüglich der Amplitude der Filterantworten ist, sind phasenbasierte Verfahren darüber hinaus relativ robust bezüglich interokulären Beleuchtungs- und Kontrastdifferenzen. Durch die Mehrdeutigkeit bei der Phasenberechnung können jedoch nur Disparitätswerte bis zur halben Modulationswellenlänge des verwendeten Filters gemessen werden. Wie viele andere Ansätze reagieren auch phasenbasierte Verfahren sehr empfindlich auf Okklusionen.[4]
Auflösung der Mehrdeutigkeiten Bearbeiten
Nach der Eindeutigkeitseinschränkung darf jedem Bildpunkt nur eine Disparität und damit nur maximal einem Ort im betrachteten Raum zugeordnet werden (dies schließt übrigens semitransparente Oberflächen aus). Bei allen lokalen und merkmalsbasierten Verfahren können jedoch Mehrdeutigkeiten nicht ausgeschlossen werden (die ähnlichsten Bereiche in den Stereobildern müssen nicht zwangsläufig zusammengehören). Zur Lösung dieses Problems kommen, je nach Ansatz unterschiedliche Methoden zum Einsatz: Bei den sogenannten Regularisierungsmethoden werden unter Berücksichtigung der Einschränkungen (siehe Grundlagen) Kosten- oder Energiefunktionen formuliert, in denen anschließend das globale Minimum gesucht wird. Einen anderen Ansatz stellen die sogenannten Relaxationsverfahren dar. Bei den meisten Ansätzen, die dieses Verfahren in der Stereoskopie anwenden, werden zunächst Merkmale oder Bildregionen mit besonderen Eigenschaften aus den Bilddaten extrahiert. Den Bildkoordinaten, an denen die erwähnten Elemente auftreten, werden anschließend sogenannte Knoten zugeordnet. Jeder dieser Knoten wird weiterhin mit einem Satz von Variablen versehen, die jeweils eine Korrespondenz des betreffenden Knotens mit unterschiedlichen Elementen im anderen Bild repräsentieren. Diese Variablen werden je nach Ansatz als Wahrscheinlichkeit[7] oder als Neuronenaktivität[6] (neuronale Netze) interpretiert. Zu Beginn des eigentlichen Relaxationsprozesses werden die Variablen in Abhängigkeit der Ähnlichkeit der entsprechenden Merkmale oder Pixelwerte initialisiert. Anschließend werden die Variablenwerte in einem dynamischen Prozess iterativ aktualisiert, wobei Verletzungen der Einschränkungen hemmend bzw. reduzierend und Berücksichtigung der Einschränkungen verstärkend wirken. Eine eindeutige Disparitätenkarte liegt vor, wenn ein stationärer Zustand erreicht ist. Über eine geeignete Kopplung können auf diese Weise auch durch Okklusionen verursachte Falschzuweisungen unterdrückt werden.[3]
Anwendungen Bearbeiten
Optischer Fluss Bearbeiten
Das Korrespondenzproblem stellt sich auch bei der Berechnung des optischen Flusses, welches eine Abschätzung der Bewegungen von Gegenständen in einem Bild darstellt („approximation to image motion defined as the projection of velocities of 3D surface points onto the image plane of a visual sensor“[10]).
Die kontinuierliche Ermittlung des optischen Flusses in optischen Abbildungen kann zur Verfolgung von bewegten Objekten und zur automatisierten Nachführung der entsprechenden Entfernungseinstellung eingesetzt werden.[11]
Autonomes Fahren Bearbeiten
Mit Hilfe von Stereokameras die im Normalfall angeordnet sind, lassen sich zunächst Disparitätenkarten erstellen und können anschließend Tiefenbilder in der Sichtrichtung bestimmt werden,[12] was eine Grundlage des vollautomatischen Fahrens darstellt.
Reduktion der Schärfentiefe Bearbeiten
Die Korrespondenzanalyse kann zur rechnerischen Reduktion der Schärfentiefe eingesetzt werden.
3D-Rekonstruktion Bearbeiten
Stereobilder sind ferner weit verbreitet, um die bei der Abbildung verloren gegangenen Tiefeninformation mit Hilfe einer 3D-Rekonstruktion wieder herzustellen. Dies ist unter anderem in der Robotik ein wichtiges Anwendungsgebiet[4] wie bei der Erkundung unseres Nachbarplaneten Mars mit Landefahrzeugen:
- NASA Mission Mars Exploration Rover (MER)
- NASA Mission Mars Science Laboratory (kurz MSL)
- NASA Mission Mars 2020.
Nach dem gleichen Prinzip arbeitet man in der Fernerkundung mit Satelliten um ein 3D-Modell der Erde zu erstellen oder andere Planeten zu erforschen.
Ein Vorteil von Kameras als Messmittel ist, dass sie berührungslos arbeiten. Daher kommen bei der Archäologie gerne Stereokameras zum Einsatz zur Erzeugung eines 3D-Modells.
-
Stereobildpaar eines Mikrofossils kleiner als 1 mm groß. -
3D-Rekonstruktion des Mikrofossils.
.gif)
Einzelnachweise Bearbeiten
- ↑ Ramin Zabih, John Woodfill: Non-parametric local transforms for computing visual correspondence. In: Computer Vision — ECCV '94 (= Lecture Notes in Computer Science). Springer, Berlin, Heidelberg, 1994, ISBN 3-540-57957-5, S. 151–158, doi:10.1007/bfb0028345.
- ↑ a b Bertero, M.; Poggio, T. A.; Torre, V.: Ill-Posed Problems in Early Vision. In: Proceedings of the IEEE. Band 76, Nr. 8, August 1988, S. 869–889, doi:10.1109/5.5962.
- ↑ a b c Ralph Trapp, Siegbert Drüe, Georg Hartmann: Stereo Matching with Implicit Detection of Occlusions. In: Hans Burkhardt, Bernd Neumann (Hrsg.): ECCV 1998: Computer Vision — ECCV’98. Band 1407. Springer, Berlin / Heidelberg / New York 1998, ISBN 3-540-64613-2, S. 17–33, doi:10.1007/BFb0054731.
- ↑ a b c Ralph Trapp: Stereoskopische Korrespondenzbestimmung mit impliziter Detektion von Okklusionen. Hrsg.: Georg Hartmann: HNI-Verlagsschriftenreihe. Band 43. HNI-Verlag, 1998, ISBN 3-931466-42-6, urn:nbn:de:hbz:466:2-27002.
- ↑ Bernd Jähne: Digitale Bildverarbeitung. Springer, Berlin 1993, ISBN 3-662-22662-6, doi:10.1007/978-3-662-22662-9.
- ↑ a b D. Marr, T. Poggio: Cooperative Computation of Stereo Disparity. In: Science. Band 194, 1976, S. 283–287, doi:10.1126/science.968482.
- ↑ a b Stephen T. Barnard, William B. Thompson: Disparity Analysis of Images. In: Transactions on Pattern Analysis and Machine Intelligence. PAMI-2, Nr. 4, Juli 1980, S. 333–340, doi:10.1109/TPAMI.1980.4767032.
- ↑ D. Marr, E. Hildreth: Theory of edge detection. In: Proceedings of the Royal Society of London. B 207, 1980, S. 187–217, doi:10.1098/rspb.1980.0020.
- ↑ C. Westelius, H. Knutson, J. Wiklund, C. Westin: Phase-based Disparity Estimation. Hrsg.: L. Crowley, H. I. Christensen: Vision as Process. Springer-Verlag, 1995, ISBN 3-540-58143-X, S. 157–178, urn:nbn:se:liu:diva-51434.
- ↑ Steven S. Beauchemin, John L. Barron: The computation of optical flow. ACM computing surveys (CSUR), 27. Jg., Nr. 3, 1995, S. 433–466, doi:10.1145/212094.212141.
- ↑ Advanced Depth From Defocus Autofocus - Lumix DC-GH5 - Technical Director Interview. YouTube-Video. Panasonic Newsroom vom 12. Juli 2017, abgerufen am 5. Oktober 2017.
- ↑ Daniel Scharstein, Richard Szeliski: A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. In: International journal of computer vision, 47. Jg., Nr. 1–3, 2002, S. 7–42, doi:10.1023/A:1014573219977.