Antwort auf Frage 1 aus Ihrem Qualifikationstest.
Von : Menno Rubingh
Datum: 15.09.2011
--------------------------------------------------------------------------
NB: Dieser Text is ISO-8859-1 plain text, formatiert für viewing mit einem
MONOSPACE font.
Notation:
^ = Superscript
T = Transpose. Beispiel: v^T = transpose von Vektor v.
--------------------------------------------------------------------------
Gesehene Literatur:
Trucco & Verri, 1998,
_Introductory Techniques for 3-D Computer Vision_
Cyganek & Siebert, 2009,
_An Introduction to 3D Computer Vision Techniques and Algorithms_
ISBN 978-0-470-01704-3
Wöhler, 2009,
_3D Computer Vision: Efficient Methods and Applications_
ISBN 978-3-642-01731-5
INHALT
0 - Übersicht über diesen Text
1 - Calibrated stereo
2 - Uncalibrated stereo
3 - Das Finden von Korrespondenzen
------------------------------------------------------------------------------
0 -- ÜBERSICHT ÜBER DIESEN TEXT
------------------------------------------------------------------------------
3D-Stereorekonstruktion bedeutet dass man die 3D-Position von Punkten in
einer 3D-Szene feststellt aus Aufnahmen der 3D-Szene die gemacht wurden
aus 2 oder mehr unterschiedlichen Kamerapositionen.
Bei der Einfachsten, und m.E. auch genauesten (most accurate), Art der
3D-Stereorekonstruktion werden die Kameras fest aufgestellt, und werden
die Kameras vorher völlig kalibriert (d.h. sowohl die intrinsic parameters
als auch die Position und Orientierung aller einzelnen Kameras relativ
zum Welt-Koordinatensystem werden vorher festgestellt). Abschnitt 1
erklärt wie diese "calibrated stereo" funktioniert.
Es gibt aber auch Verfahren für 3D-Stereorekonstruktion mit vorher nicht
kalibrierten, oder vorher nur teilweise kalibrierten, Kameras. In jedem
dieser Verfahren werden, aus gefundenen Korrespondenzen, zugleich mit der
3D-Szene auch die für die Rekonstruktion benötigten parameters festgelegt
(nämlich: die intrinsic parameters, und die _relative_ Position und
Orientierung der Kameras zu einander). Abschnitt 2 legt dar was ich bis
jetzt über diese (teilweise) unkalibrierten stereo-Verfahren verstanden
habe.
Alle 3D-Stereorekonstruktion beruht auf das Finden von Korrespondenzen
zwischen den Abbildungen der 3D-Szene gemacht aus den unterschiedlichen
Kamerapositionen. Das finden dieser Korrespondenzen, das vermute ich
der fehleranfälligste Schritt in 3D-Stereorekonstruktion ist, behandle
ich in Abschnitt 3.
Probleme (und Lösungswege) beschreibe ich in jedem Abschnitt separat,
nämlich unter dem Thema wo das jeweilige Problem spielt.
------------------------------------------------------------------------------
1 -- CALIBRATED STEREO
------------------------------------------------------------------------------
"Calibrated stereo" bedeutet dass man die Kameras deren Aufnahmen
man zur 3D-Stereorekonstruktion benutzt, vorher völig kalibriert hat.
(Dadurch dass man mit jeder Kamera eine Aufnahme macht eines bekannten
"calibration rig", das sich auf einer bekannten Position und Orientierung
befindet relativ zu dem Koordinatensystem relativ zu der man die 3D
Szene vermessen möchte.)
D.h. von jeder Kamera sind ihre intrinsic parameters bekannt, und
auch ihre Position und Orientierung relativ zu einem "bekannten"
Koordinatensytem in der 3D Welt.
Bei "calibrated stereo" reichen 2 Kameras aus. Die Kameras sind fest
aufgestellt; und sie sind neben einander aufgestellt (ähnlich wie die
2 Augen eines Menschen).
Die 3D-Szene wird zugleich von den beiden Kameras fotografiert.
Die Aufnahmen der zwei Kameras werden dann abgeglichen: d.h. in den
zwei Aufnahmen werden Bild-Punkte gefunden die (wahrscheinlich) die
Abbildung sind des gleichen Punktes in der 3D-Szene (siehe Abschnitt 3).
Jede gefundene Korrespondenz besteht also aus einem Punkt P1 auf der
Bildfläche der Kamera 1, und einem Punkt P2 auf der Bildfläche der
Kamera 2. Für jede Korrespondenz berechnet man dann folgende zwei Linien
im 3D-Raum:
Linie L1 = die Linie durch P1 und das optische Zentrum von Kamera 1,
Linie L2 = die Linie durch P2 und das optische Zentrum von Kamera 2.
Die 3D Position des 3D-Szenenpunktes das zu dieser Korrespondenz gehört
ist der Schnittpunkt dieser 2 Linien. Jede gefundene Korrespondenz
liefert also die 3D Position eines Punktes in der 3D-Szene.
Für alle Arten von 3D-Stereorekonstruktion gilt noch folgendes:
Die Distanz t zwischen den zwei Kameras sollte nicht zu klein sein und
nicht zu groß. Bei zu kleiner t ist die Tiefen-Auflösung schlecht;
aber bei zu großer t wird es schwieriger, die Bilder der zwei Kameras
abzugleichen (zu matchen).
[Ausweg aus diesem Widerspruch ist m.E. dass man die Szene aus mehr
als 2 Kamerapositionen fotografiert: Entfernt liegende Kamerapositionen
liefern gute Tiefen-Auflösung, und die zwischenliegenden Kamerapositionen
erlauben das matching zwischen den weitest-entfernten Kamerapositionen.]
------------------------------------------------------------------------------
2 -- UNCALIBRATED STEREO
------------------------------------------------------------------------------
Es gibt aber auch Verfahren für 3D-Stereorekonstruktion wobei man Kameras
benutzen kann die vorher nicht, oder nur teilweise, kalibriert sind.
Zur Überschaubarkeit folge ich die Klassifizierung von Trucco&Verri
(p. 161-170) die die folgenden Fälle unterscheiden:
Fall 1:
Die intrinsic parameters (focal length usw.) aller Kameras sind
bekannt, aber von keiner Kamera sind die extrinsic parameters
(= Position und Orientierung des Kamera-Koordinatensystems relativ
zur 3D Szene) bekannt;
Fall 2:
Weder die intrisic noch die extrinsic parameters der Kameras sind
bekannt.
>>> Fall 1: Nur die intrinsic parameters bekannt
In diesem Fall reichen (wie bei calibrated stereo) 2 Kameras aus um
3D-Rekonstruktion machen zu können.
Man geht hier so vor, dass zunächst aus einer Menge Korrespondenzen einige
Parameter-Werte bestimmt werden die noch fehlen um überhaupt irgendeine
Art 3D-Rekonstruktion machen zu können: Das sind die translation t und
die Rotation R der Kamera-Koordinatensystemen der zwei Kameras relativ
zu einander. Man führt dazu nach einander die folgenden Schritte aus:
A- Bestimmen der fundamental matrix F aus K >= 8 Korrespondenzen, über
den Eight-Point-Algorithm. (Trucco&Verri, p. 155-156.) [Note 1]
B- Berechnen der essential matrix E aus F. Dies ist möglich, weil
die matrices M{int,1} und M_{int,2} der intrinsic parameters der
beiden Kameras bekannt sind.
C- Aus E ableiten des translation vector t und der Rotationsmatrix R.
(Trucco&Verri, p. 164-165.)
Die jetzt bekannte t und R erlauben es, eine 3D-Stereorekonstruktion
zu machen für alle gefundenen Korrespondenzen. Dabei kann man
jedoch nur die 3D-Position der Szenenpunkte feststellen relativ zum
Kamera-Koordinatensystem eines der Kameras (wovon man den genauen Bezug
relativ zur 3D-Szene nicht kennt).
Und es gibt noch eine weitere Einschränkung, nämlich: die 3D-Stereo-
rekonstruktion ist in diesem Fall, ohne zusätzliche Information,
nur möglich "up to an unknown scale factor", d.h. der Maßstab der
rekonstruierten 3D-Szene ist unbekannt.
Der Grund dafür ist dass die fundamental und essential matrices F und E
Beziehungen sind zwischen einerseits einem Punkt im image von Kamera 1
und andererseits einem Punkt in image von Kamera 2, wobei diese Punkte
spezifiziert werden in homogenen Koordinaten (im Sensor-Koordinatensystem
für F, und im Kamera-Koordinatensystem für E). Wegen der homogenen
Koordinaten sind F und E nur festgelegt up to a scalar factor.
Dieser unbekannte scalar factor bewirkt dass der translation vector
t in Schritten A,B,C nur festgelegt werden kann up to an unknown
scale factor (Trucco&Verri, p. 164). Die Länge von t ist der Abstand
zwischen den zwei Kameras ("base line"), und ist der Maßstab bei der
3D-Rekonstruktion. Dies bedeutet dass man mit diesem nur als Richtung
bekannten t, ohne weitere Information, nur Rekonstruktion machen kann
"up to an unknown scale factor".
Dieser "unknown scale factor" lässt sich jedoch bestimmen wenn man den
Abstand kennt zwischen zwei der erkannten 3D-Punkten (für "erkannt"
siehe Abschnitt 3). Dazu würde es also z.B. ausreichen wenn man in der
3D-Szene zwei gut erkennbare "Kalibrierpunkte" aufnehmen kann mit einem
bekannten Abstand dazwischen, oder wenn die Szene gut erkennbare Objekte
enthält mit einer bekannten Größe (z.B. Autos).
Am Ende dieses Abschnittes behandle ich einige Probleme die auftreten
im Eight-Point-Algorithm (benutzt in Schritt A oben).
>>> Fall 2: Kameras völlig unkalibriert
Für Fall 2 behaupten Trucco&Verri (p. 161-170) dass dort nur
Rekonstruktion möglich sei "up to an unknown, global projective
transformation"; dies würde m.E. die Rekonstruktion für die meisten
praktischen Zwecke sinnlos machen.
Wöhler, p. 32-40, fasst jedoch einigermaßen ausführlich einen Ansatz
zusammen aus Hartley & Zisserman, 2003, _Multiple View Geometry in
Computer Vision_, der Wöhler "metric self-calibration" nennt, und dessen
Ziel es laut Wöhler ist, diese unbekannte projective transformation
festzustellen. Einfacher gesagt, besteht dieser Ansatz darin, dass
aus einer Menge Korrespondenzen (gefunden in der 3D-Szene) zugleich die
3D-Szene _UND_ auch die intrinsic parameters abgeleitet werden (Wöhler
p. 7-8). Der Name "self-calibration" bedeutet, dass zugleich auch die
intrinsic parameters festgestellt werden (entweder in expliziter oder in
impliziter Form). Die Vorgehensweise bei self-calibration ist ähnlich
zu einer normalen Kalibrierung, und erfordert wieder Minimierung der
Abweichung zwischen Messwerten und Modell-Vorhersage.
Fazit für Fall 2 ist daher m.E. dass dort, über den Mehraufwand der
self-calibration, in prinzip auch Rekonstruktion möglich ist "up to an
unknown scale factor", und ohne Bezug zu einem Koordinatensystem in der
3D-Welt -- d.h. genau wie in Fall 1.
Den (sehr interessanten) Ansatz von Hartley & Zisserman genauer zu
studieren habe ich leider noch keine Zeit gefunden. Sicher scheint
mir, dass sie unmöglich eine _genauere_ Rekonstruktion liefern kann
als Fall 1 (oder als kalibrierte Rekonstruktion). Wöhler p. 35 lässt
mich befürchten, dass metric self-calibration möglicherweise _mehr_
als 2 Aufnahmen der 3D Szene erfordern könnte aus unterschiedlichen
Kamerapositionen.
>>> Fazit über uncalibrated stereo insgesamt
Ich vermute dass es für viele Anwendungen ausreicht, eine 3D Szene zu
rekonstruieren, und unwichtig ist, die Position oder Orientierung der
Szene festzustellen relativ zu einem bekannten Koordinatensystem in
der 3D-Welt.
Für solche Anwendungen scheint mir Fall 1 sehr praktisch: Das
Kalibrieren der intrinsic parameters ist relativ einfach und unafwendig
(geht gemäß Zhang 2000 mit einem "handheld" planaren calibration rig
ohne Bezug zu einem festen 3D-Welt-Koordinatensystem); und man erspart
sich die genaue Postitionierung eines Kalibriermusters (die man benötigt
hätte zur Feststellung der extrinsic parameters).
>>> Probleme im Eight-Point-Algorithm
Der Eight-Point-Algorithm wird benutzt fürs bestimmen der fundamental
matrix F aus K >= 8 Korrespondenzen, in dem Fall 1 wobei die intrinsic
parameters der beiden Kameras bekannt sind. Einige der Probleme die in
diesem Eight-Point-Algorithm auftreten sind folgende: [Note 2]
(1) Die K Korrespondenzen woraus F abgeleitet wird sollten keine
"degenerate configurations" bilden (Trucco&Verri, p. 155).
Bei einer degenerate configuration ist die Berechnung numerisch
instabil und die berechnete F nutzlos. Es geht hier darum, dies in
der Berechnung zu detektieren. Das ist, wie auch bei Kalibrierung,
auch hier m.E. wieder möglich in dem man in der SVD-decomposition die
man sowieso braucht (Trucco&Verro, p. 155-156) überprüft ob es mehr
als nur eine near-zero singular value gibt. Wenn das der Fall ist,
dann sollte die Berechnung zurückgeben dass aus den Korrespondenzen
keine sinnvolle F abgeleitet werden kann.
(2) False matches, d.h. image-Punkte die einander Zugeordnet wurden
aber nicht Abbildung desselben 3D-Szenenpunktes sind.
Lösung: Wenn es mehr als die minimale Anzahl von 8 Korrespondenzen
gibt, ist es möglich die false matches automatisch zu erkennen,
nämlich über die RANSAC Methode (random sample consensus)
(Gyganek&Siebert, p.49-54). Das funktioniert wie folgt:
Man wählt random 8 der Korrespondenzen aus, und berechnet daraus
einen fundamental matrix F. Dann berechnet man fur jede der
restlichen Korrespondenzen eine real Zahl d (siehe unten)
die bewertet wie gut die Korrespondenz passt zum Modell F.
Die Korrespondenzen wofür d größer ist als ein Schwellenwert dTh
(siehe unten) ordnet man ein als outliers (false matches) relativ
zu dem Modell F.
Obiges wiederholt man einige Male, mit unterschiedlichen Mengen
von 8 Korrespondenzen. Die F wofür man unter den restlichen
Korrespondenzen die wenigsten outliers zählt, ist die beste F;
und man verwirft die Korrespondenzen die outliers sind relativ zu
dieser F.
Eine geeignete Bewertungs-Zahl d kann man m.E. wie folgt berechnen.
Gegeben eine Korrespondenz {P1,P2} zwischen einen Punkt P1 im
image der Kamera 1, und einen Punkt P2 im image der Kamera 2.
Zunächst werden beide Punkte P1 und P2 umgerechnet von Sensor-
Koordinaten (= Pixel-Koordinaten) nach Kamera-Koordinaten (= im
Kamera-Koordinatensystem der jeweiligen Kamera). Das umrechnen ist
möglich weil wir die intrinsic parameters der beiden Kameras kennen.
Sensor-Koordinaten für P1 und P2 sind in den Berechnungen unten
unerwünscht weil das die unten berechtenen Abstände verzerren könnte.
Mit P1 und P2 in homogenen Koordinaten müsste dann gelten:
P1^T E P2 = 0, oder P1^T L1 = 0 wo L1 = E P2 die epipolar line ist in
image 1 die korrespondiert mit Punkt P2 in image 2. Die essential
matrix E ist bekannt aus E = M_{int,2}^T F M_{int,1} (wir kennen
die intrinsic parameters).
Dann den Abstand d1 berechnen, in image plane 1, zwischen P1
und L1 (d.h. Abstand zwischen Punkt und Linie in 2D Fläche).
Ähnlich kann man auch den Abstand d2 berechnen, in image plane 2,
zwischen P2 und der Linie L2 = F^T P1. Als Bewertungs-Zahl d,
der bewertet wie gut die Korrespondenz {P1,P2} dem Modell F folgt,
könnten z.B. geeignet sein: d = d1, oder d = d2, oder d = d1 + d2,
oder auch d = d1^2 + d2^2 (wo ich vermute das letztere die Beste
sein dürfte).
Für den benötigten Schwellenwert dTh sollte man dann nehmen:
den kleinsten Wert der einen richtigen match (keinen false match)
noch durchlässt wenn man in P1 und L1 (und P2 und L2) diejenige
Abweichungen einbezieht die man wegen Meßungenauigkeit erwarten kann.
(3) Im Eight-Point-Algorithm (wie beschrieben in Trucco&Verri, p. 155-156)
wird F dadurch bestimmt dass eine "purely algebraic error measure"
minimiert wird, die keine physische Bedeutung hat. Wie dies auch
bei Kalibrierung der Fall war, wird dies (m.E. zu recht) kritisiert
von Wöhler (p. 31).
Lösung: Genau wie bei Kalibrierung, sollte man die gemäß
Trucco&Verri, p. 155-156, bestimmte F nur als initial guess benutzen
für eine anschließende Optimierung wobei man eine physisch sinnvolle
error measure minimiert. Wöhler p. 31 schlägt die folgende error
measure vor:
Eg = SUM [ d1^2 + d2^2 ] (Gleichung U1)
wo
d1 = Abstand in image 1 zwischen Punkten P1 und P1e
d2 = Abstand in image 2 zwischen Punkten P2 und P2e
P1, P2 = Gemessene Korrespondenz-Punkte
P1e, P2e = Estimated Korrespondenz-Punkte
und wo summiert wird über alle Korrespondenzen. Wöhler berichtet
dass Hartley & Zisserman (2003, _Multiple View Geometry in Computer
Vision_) die estimates P1e und P2e wie folgt nehmen:
P1e = M_{ext,1} pW (Gleichung U2a)
P2e = M_{ext,2} pW (Gleichung U2b)
wo
pW = 3D scene point, in Kamera-Koordinatensystem von Kamera 1,
in homogenen Koordinaten
M_{ext,1} = Matrix die pW abbildet auf image plane 1
M_{ext,2} = Matrix die pW abbildet auf image plane 2
+- -+
M_{ext,1} = | I 0 | , I = 3x3 identity matrix
+- -+ 0 = 3x1 zero vector
+- -+
M_{ext,2} = | R t | , R = unknown 3x3 rotation matrix
+- -+ t = unknown 3x1 translation vector.
P1, P2, P1e, P2e sind hier stets in homogenen Koordinaten.
Und wichtig ist dass P1, P2, P1e, P2e -- genau wie in Problem (2)
oben -- auch hier stets spezifiziert sind in Kamera-Koordinaten (in
den Kamera-Koordinatensystemen von Kamera 1 und 2), und nicht
in Sensor-Koordinaten, damit in den d1 und d2 keine Verzerrungen
auftreten. [Note 3]
Die einfache Form von M_{ext,1} kommt daher weil die pW spezifiziert
werden im Kamera-Koordinatensystem von Kamera 1. Dies bewirkt auch,
dass es eine sehr einfache Beziehung gibt zwischen der essential
matrix E und den "Blöcken" R und t aus M_{ext,2} : Wenn E definiert
wird so dass P2^T E P1 = 0, dann gilt E^T = R^T S oder E = - S R,
wobei S = cross product matrix für vector t.
Die unknowns sind: alle unabhängige Parameter in R und t, und alle
Koordinaten der 3D scene points pW die gehören zu den in Betracht
genommenen Korrespondenzen (wo die pW im Kamera-Koordinatensystem
von Kamera 1). Der Fehler Eg ist nicht-linear in diesen unknowns,
so dass nicht- lineare Minimierung eingesetzt werden muss,
d.h. Levenberg-Marquard.
Für die nicht-lineare Minimierung benutzt man als initial guess:
die essential matrix E = M_{int,2}^T F M_{int,1} mit der F
gefunden aus dem Eight-Point-Algorithm, und die Punkte pW die
zugleich gefunden wurden aus dem Eight-Point-Algorithm. Output der
nicht-linearen Minimierung sind: ein verfeinerter E (woraus direkt
der verfeinerte F folgt), und verfeinerte 3D scene points pW.
------------------------------------------------------------------------------
3 -- DAS FINDEN VON KORRESPONDENZEN
------------------------------------------------------------------------------
Das Finden von Korrespondenzen ist der Grundlage (basis, foundation)
worauf alle 3D-Stereorekonstruktion beruht. Und ich würde vermuten,
dass es auch der fehleranfälligste Schritt ist in 3D-Stereorekonstruktion.
Damit die Formulierungen übersichtlich bleiben, gehe ich in diesem
Abschnitt davon aus, dass 2 fest aufgestellte Kameras benutzt werden.
Die Aufnahmen die gleichzeitig von Kameras 1 und 2 gemacht werden
bezeichne ich als "Bild 1" und "Bild 2" (respectively).
Beim finden der Korrespondenzen geht es darum, die _Orte_ P1 und P2
in den zwei Aufnahmen zu finden die (wahrscheinlich) die Abbildung des
gleichen 3D-Szenenpunktes sind. Das finden der Korrespondenzen beruht
notwendigerweise auf das Vergleichen von (kleinen) Bild-Ausschnitten aus
den zwei Kameras auf Ähnlichkeit; es ist eine Suche nach die Positionen
P1 und P2 in den Aufnahmen von Kamera 1 und 2 (respectively) wo ein
Bildausschnitt rund P1 (in Bild 1) die größte Ähnlichkeit hat zu einem
Bildausschnitt rund P2 (in Bild 2). Für das verwendete Ähnlichkeits-Maß
zwischen den zwei Bildausschnitten gibt es viele Möglichkeiten,
z.B. Korrelation, oder Ecken/Kanten-erkennung.
>>> Problem: 2D-Suche
Das größte Problem beim Finden von Korrespondenzen ist, denke ich, dass
es zeitaufwendig ist, über die ganze 2D-Flache eines Bildes zu suchen
nach einer Korrespondenz für eine gegebene Position in dem anderen Bild.
Die wichtigste Hilfe dabei, die Suche nach Korrespondenzen zu
beschleunigen ist der epipolar constraint: Gegeben eine Position P1
in Bild 1, muss die dazugehörende Position P2 in Bild 2 liegen auf
der epipolar line in Bild 2 festgelegt durch P1. Diese epipolar line
kann man berechnen wenn man die relative Position und Orientierung
der beiden Kameras kennt, oder wenn man die fundamental matrix F kennt
(letzteres ist eine schwächere Bedingung weil F nur bekannt sein kann
up to a multiplicative factor). Das beschränkt die Suche nach P2 zu
einer 1D-Suche.
[ Das gleiche gilt natürlich auch umgekehrt: Gegeben P2, muss die
zugehördende P1 liegen auf der epipolar line in Bild 1 festgelegt durch
P2 in Bild 2. ]
Um die Suche noch weiter zu vereinfachen, ist es ist auch möglich,
die beiden Bilder so zu verzerren dass in beiden Bildern alle
mögliche epipolar lines horizontal laufen. Diese Verzerrung (die man
"rectification" nennt) besteht darin, dass man für jede Kamera das
Bild berechnet, dass aufgenommen wäre wenn die Kameras eine "canonical"
Orientierung gehabt hätte, d.h. mit der Bildfäche parallel zur base line
(= Linie zwischen den optical centers der beiden Kameras). Sinn dieser
rectification ist dass die 1D-Suche nach Korrespondenzen vereinfacht
wird. Ich vermute, dass für viele Algorithmen für matching zwischen
Bildausschnitten diese Vereinfachung wirklich sehr hilfreich sein würde.
>>> Problem: Occlusion
In fast allen 3D Szenen gibt es 3D-Szenenpunkte die nur von einer der zwei
Kameras gesehen werden, und von der anderen Kamera nicht sichtbar sind.
Dieses Dies nennt man "occlusion".
Das Problem bei occlusion ist dass es für einige Punkte in Bild 1 keine
Korrespondenz gibt in Bild 2, und/oder umgekehrt. Das bedeutet m.E. dass
die Korrespondenz-Suche nicht einfach nur die beste Korrespondenz P2 in
Bild 2 suchen kann (für einen gegebenen Punkt P1 in Bild 1), sondern
eigentlich auch erkennen können müsste ob es überhaupt in Bild 2 eine
Korrespondenz für P1 gibt.
Folgdende Wege zur Lösung sind mir eingefallen. Jeder Ansatz liefert
dabei einen Beitrag, und die Ansätze sollten m.E. am besten alle zugleich
angewendet werden.
A- Bei der Korrespondenz-Suche könnte man als output nicht nur die
Positionen {P1,P2} der besten gefundenen Korrespondenz
zurückgeben, sondern auch eine real Zahl, die ausdrückt wie gut
die Übereinstimmung (der match) ist. [Diese Zahl wird sowieso
schon von dem verwendeten Bildausschnitt-matching-Verfahren
geliefert.] Das erlaubt es, Korrespondenzen zu verwerfen -- d.h.
zu schliessen dass es für einen gegebenen P1 oder P2 keine
Korrespondenz gibt im anderen Bild -- wenn die matching-Qualitätszahl
schlechter ist als einen Schwellenwert. Ich denke dass jede
praktische 3D-Rekonstruktion mindestens eine einfache Art dieser
filtering braucht
Eine weiterführende Idee wäre, dass die Korrespondenz-Suche
für einen gegebenen Punkt P1 in Bild 1 nicht nur _eine_ Korrespondenz
P2 in Bild 2 zurückgibt, sondern eine Menge; und dabei für jeden P2
die matching-Qualitätszahl. Die Gesamt-output der Korrespondenz-Suche
für zwei Aufnahmen besteht dann aus eine Liste mit Einträgen { P1, P2,
Qualitätszahl }, wo auch Einträge mit gleichen P1 und P2 vorkommen.
Diese Liste wäre dann input für eine Weiterverarbeitung W, die dann
als ihre output schliesslich die endgültige 3D-Stereorekonstruktion
liefert. Sinn dieser Idee ist dass der Weiterverarbeitung W
Information zur verfügung steht über die ganze 3D-Szene (in contrast
zu eine Korrespondenz-Suche, die eine Korrespondenz P2 sucht für
einen gegebenen P1, und die nur lokale information sieht). Eine
Idee für eine vielleicht mögliche Art Weiterverarbeitung W gebe ich
unten in Punkt C.
B- Constraints einbeziehen. (Siehe unten, unter heading "False matches").
Die einzigen "harten" constraints scheinen mir der epipolar
contraint und der uniqueness constraint. Wie unten unter "False
matches" geschrieben, behandelt man m.E. die anderen "constraints"
besser als Ingredienten die einfliessen in der Berechnung der
matching-Qualitätszahl. D.h. diese constraints haben dann ihren
Einfluss Über die Auswertung dieser matching-Qualitätszahl.
C- Vielleicht wäre eine einfache Art Modellierung der rekonstrierten
3D-Welt möglich, wobei man die 3D-Szene modelliert als einer Menge
von möglichst großen und "einfachen" 3D-Objekten (große, glatte
Oberflächen).
Dabei würde man z.B. so vorgehen können dass man beim Aufbau
des 3D-Modells inkrementell vorgeht, nämlich die Korrespondenzen mit
der besten matching Qualität zuerst. Ich "ahne" irgendwie dass es
dann vielleicht möglich sein könnte, beim späteren hinzufügen von
weniger guten Korrespondenzen zu detektieren wenn so eine spätere
Korrespondenz schlecht passt in dem bis dann aufgebauten 3D-Modell.
Eine Variante wäre, ähnlich vorzugehen wie beim RANSAC-Verfahren,
in Abschnitt 2 (heading "Probleme im Eight-Point-Algorithm"), d.h.
aufgrund der besten Korrespondenzen mehrere alternative 3D-Modelle
durchzuprobieren; und dann schliesslich das einfachste Modell
auszuwählen und alle (wenig guten) Korrespondenzen zu verwerfen die
nicht in diesem Modell passen.
[ So eine 3D-Modellierung würde auch dazu beitragen, "Lücken" zu
füllen in der 3D-Rekonstruktion, sowohl Lücken verursacht durch
occlusion als auch durch fehlende Textur (siehe unten). ]
>>> Problem: False matches
Eine "false match" ist eine detektierte aber falsche Korrespondenz
{P1,P2}, d.h. wobei P1 und P2 in Wirklichkeit nicht die Abbildung des
gleichen 3D-Szenenpunktes sind.
Das erste Werkzeug, false matches zu verhindern, ist das Einbeziehen von
constraints für P1 und P2. Der wichtigste nicht-triviale constraint ist
der epipolar constraint (siehe oben unter heading "Problem: 2D-Suche"),
die die zu einer P1 gehördenen P2 einschränkt auf einer Linie in Bild
2 (und umgekehrt). Das heißt dass man eine Korrespondenz {P1,P2} wo
P1 und P2 nicht in der gleichen epipolar plane liegen ohne weiteres
verwerfen kann.
Cyganek & Siebert, p. 66-71, geben eine lange Liste weiterer constraints.
Der einzige weitere harte" constraint scheint mir die triviale "uniqueness
constraint" (für gegebener P1 in Bild 1 kann es höchstens nur eine
zugehörende P2 in Bild 2 geben und umgekehrt). [Note 4]
Alle anderen von Cyganek&Siebert aufgelisteten constraints beleuchten
unterschiedliche Weisen wie die gematchten Bildausschnitte ähnlich sein
müssten wenn sie tatsächlich Abbildungen des gleichen 3D-Szenenpunktes
sind. Diese Art constraint kann man m.E. wahrscheinlich am besten
implementieren direkt in den Routinen die zwei Bildausschnitten machen,
nämlich in der Implementierung der Berechnung der matching-Qualitätszahl,
und in der Berechnung der zugehörenden Schwellenwerte. Unwahrscheinliche
(d.h. unähnliche Bildausschnitte) matches würden dadurch dann automatisch
verworfen werden.
[Bemerkung: Möglich nützlich scheint es mir auch, aus einem
Bildausschnitt- matching-Verfahren nicht nur eine Qualitätszahl
zurückzugeben, sondern einen Vektor von mehreren Qualitätszahlen, nämlich
eine Zahl für jedes unterschiedliche matching-criterion. Dies erlaubt
es, separate Schwellenwerte zu handhaben für die unterschiedlichen
matching criteria.]
In Korrespondenz-Suche (und/oder bei der Auswertung von Korrespondenzen)
würde ich auch immer sicherstellen und automatisch überprüfen wollen dass
für jede Korresponzenz von Bild 1 nach Bild 2 (P1 in Bild 1 gegeben, P2
in Bild 2 gefunden), die gleiche Korrespondenz auch umgekehrt gefunden
wird (P2 in Bild 2 gegeben, P1 in Bild 1 gefunden).
Ein intelligenteres, RANSAC-ähnliches Verfahren (siehe Abschnitt 2,
heading "Probleme im Eight-Point-Algorithm") fürs detektieren von false
matches ist nur dann möglich, wenn man ein fitting macht eines Modells
auf die Korrespondenzen. [RANSAC war in Abschnitt 2 nur möglich
weil die fundamental matrix als Modell auf die Daten gefittet wurde.]
Unter heading "Problem: Occlusion" (Punkt C) nenne ich eine Idee dafür
wie man für _alle_ gefundenen Korrespondenzen ein Modell fitten könnte.
Der Vorteil den das bringt liegt nicht nur im so gefundenen Modell an
sich, sondern m.E. vor allem darin, dass man aufgrund des Modells false
matches detektieren kann.
>>> Problem: Glatte Oberflächen ohne Textur
Korrespondenzsuche beruht darauf, dass Bildausschnitte aus den zwei
Bildern gematcht werden, d.h. auf Ähnlichkeit überprüft werden. Damit ein
"match" erkannt werden kann, ist es notwendig dass die Bildausschnitte
erkennbare "features" enthalten. Glatte Oberflächen ohne Textur enthalten
keinerlei features, und sind daher m.E. unmöglich matchbar.
Das bedeutet dass eine 3D-Szene die große Oberflächen ohne Textur
enthält, in diesen Oberflächen große Lücken aufweisen wird in der
3D-Rekonstruktion. Für einen möglichen Ansatz, diese Lücken zu füllen
greife ich wieder zurück auf meine Idee aus Punkt C in heading "Problem:
Occlusion" oben, über das fitten eines 3D-Modells.
>>> Problem: Specular surfaces
Specular reflection ist Spiegelung in glatten Oberflächen, wie z.B. die
hellen aufleuchtenden Stellen in der glatten Oberfläche eines 3D-Objekts
wo das Licht aus Sonne oder aus artifiziellen Lichtquellen in die Kamera
hineinreflektiert wird.
Das Problem bei dieser Spiegelung ist dass diese hell Aufleuchtenden
Stellen deutlich erkennbare features sind (die daher als Korrespondenz
gut detektiert werden), und dass sie bei der 3D-Rekonstruktion nicht
rekonstriert werden auf der Z-Position (Tiefe, Abstand zur Kamera)
der spiegelnden Oberfläche, sondern auf einer weiter entfernt liegenden
Z-Position -- genau wie bei einem Spiegel.
Hier sollte man m.E. in Betracht ziehen dass auch ein Mensch diese Fehler
macht in seiner 3D-Rekonstruktion : Der Mensch "sieht" in einem Spiegel
nicht die Oberfläche des Spiegels, sondern sieht die gespiegelten Objekte,
und rekonstruiert diese als sich befindend hinter der Spiegel-Oberfläche.
Daher scheint es mir, dass bei _sehr starker_ specular reflection es
auch bei computer vision Verfahren vielleicht erlaubt (oder vielleicht
sogar erwünscht) sein könnte, sich wie der Mensch von der Spiegelung
"tauschen zu lassen".
Damit wäre das Problem beschränkt auf kleinere specular reflections in
nicht extrem stark spiegelden Oberflächen.
Dieses restliche Problem kann man einordnen als das finden von
Ausreisser (outliers): Punkte wofür die rekonstruierte 3D-Position weitab
liegt von der 3D-Position rekonstruiert für die benachbarten Bildpunkte
-- oder sogar auch weitab liegt von der 3D-Position rekonstruiert für
die meisten Bildpunkte im gesamtem Bild. Je weiter die reflektierte
Lichtquelle entfernt ist, desto deutlicher ist der Ausreisser.
Ich vermute dass in der Praxis viele 3D-Szenen so sind dass die
Lichtquellen deutlich entfernt liegen von den Oberflächen worin sie
sich spiegeln. Für Aussenaufnahmen bei Tageslicht ist das klar der
Fall. Das würde die Ausreisser so deutlich machen dass nur ein sehr
einfaches Modell dazu ausreicht (alle 3D-Szenenpunkte begrenzt zu einer
3D "bounding box" begrenzter Abmessungen), die Ausreisser wegfiltern
zu können.
Für Aufnahmen bei artifizieller Beleuchtung würde es ausreichen,
falls es nicht möglich ist specular reflection ganz vorzubeugen (in
dem man die Beleuchting ausschliesslich über indirektem "Streu-Licht"
gestaltet), dass die zu vermessende 3D-Szene begrenzte Abmessungen hat,
und dass die Lichtquellen deutlich entfernt von der 3D-Szene aufgestellt
werden.
Eine andere Idee für artifiziell beleuchteten Szenen ist: Die konstante
Szene mehrmals fotografieren, bei unterschiedlichen Positionen der
Lichtquellen. Für jede Lichtquellenposition die 3D-Rekonstruktion
berechnen. Die rekonstruierten 3D-Szenenpunkte die zwischen den
3D-Rekonstruktionen nicht gleich sind, sind die specular reflections.
------------------------------------------------------------------------------
Anmerkungen
-----------
[Note 1]
Während Schritt A sind die epipoles noch nicht bekannt. Die bei
Schritt A benutzten Korrespondenzen müssen daher gefunden werden
ohne Hilfe von epipolar lines !, d.h. über 2D Suche. (Für epipolar
lines, siehe Abschnitt 3.) Nach Schritt C sind die epipoles bekannt,
wodurch ab dann das Finden von Korrespondenzen beschleunigt wird.
Daher scheint es mir eine Überlegung wert, für Schritt A nur
eine Untermenge der potentiell findbaren Korrespondenzen zu benutzen,
nämlich nur die Korrespondenzen die am leichtesten zu detektieren sind.
Weitere Korrespondenzen kann man dann (leichter) finden nachdem nach
Schritt C die epipoles bekannt sind.
Natürlich würde mann in Fall 1 auf jeden Fall die 3D Positionen
berechnen für _alle_ gefundenen Korrespondenzen (sowohl die initiellen
die man für Schritt A benutzt, als auch die später mit Hilfe der
epipoles gefundenen).
[Note 2]
Weiter gibt es für Schritt A die zwei zu beachtende Sachen die in
Trucco&Verri, p. 155-156, schon deutlich beschrieben werden:
- Um numerische Instabilität vorzubeugen sollte die Matrix A (mit
den Meßwerten, d.h. den Korrespondenzen) in Trucco&Verri p. 155
normiert werden. (Und die gefundene F muss dann nachher natürlich
entsprechend "denormiert" werden.)
- Die berechnete F sollte korrigiert werden so dass sie singular
wird (mit nullspace 1-dimensional). SVD berechnen und den
kleinsten singular value auf 0 setzen.
[Note 3]
Wöhler p. 31 benutzt Gleichungen U2a und U2b, mit matrices
M_{ext,1} und M_{ext,2} wie von mir gegeben, und mit P1e und P2e in
Sensor-Koordinaten, was mir ein Versehen scheint.
[Note 4]
Unter dem uniqueness constraint schreiben Cyganek & Siebert, p. 66,
noch dass dieser constraint nicht gilt für "transparent objects".
Ich vermute jedoch, dass durchsichtige 3D-Objekte in der Praxis
wenig problematisch sein dürften. Grund: Ein Mensch das genau
gleiche Problem, und "löst" es dadurch dass er die durchsichtigen
Objekte eigentlich gar nicht "sieht". In computerisierte
Stereorekonstruktion gelangt man, m.E., automatisch auf die
gleiche Lösung -- d.h. durchsichtige Objekte verschwinden in der
3D-Rekonstruktion -- wenn man das logische Problem der mehrfachen
Korrespondenzen für durchsichtige 3D-Objekte einfach ignoriert.
[NB: Specular reflection von sonst unsichtbaren durchsichtigen
3D-Objekten mit glatten, spiegelnden Oberflächen ist ein völlig anderes
Problem, das nichts mit Durchsichtigkeit zu tun hat. Der Mensch sieht
hier auch nur die specular reflection, und nicht das durchsichtige
Material.]