Einführung in die Strukturierung aus Bewegung – Gemeinsame Rekonstruktion von 3D-Modellen und Kamerapositionen aus einer ungeordneten Fotoserie

Man sammelt Hunderte von Fotos, die Fremde von derselben Sehenswürdigkeit an einem Touristenort aufgenommen haben, und erstellt daraus ein 3D-Modell des Gebäudes inklusive aller Aufnahmepositionen – das ist Structure from Motion (SfM). Aus einer Reihe von Bildern, deren Aufnahmereihenfolge, relative Kamerapositionen und sogar das verwendete Objektiv im Voraus unbekannt sind, rekonstruiert SfM gemeinsam eine geometrisch konsistente 3D-Punktwolke und die Kamerapositionen. Während Visual-SLAM und VO/VIO die aktuelle Position eines Roboters oder einer Kamera in Echtzeit verfolgen, wird SfM größtenteils offline ausgeführt, wobei die Genauigkeit beim Aufbau einer kompletten Szene im Vordergrund steht. Dieser Artikel erläutert die interne Struktur von SfM von Grund auf und konzentriert sich dabei auf diesen Unterschied. ... ## 0. 30-Sekunden-Zusammenfassung

• SfM ist das Verfahren zur simultanen Rekonstruktion der spärlichen 3D-Punktwolke einer Szene sowie der intrinsischen und extrinsischen Parameter jeder Kamera aus vielen Bildern mittels Merkmals-Punkt-Matching und geometrischer Verifizierung.

• Grundsätzlich gibt es zwei Rekonstruktionsstrategien: Inkrementelles SfM, bei dem die Kameras nacheinander hinzugefügt werden, und globales SfM, bei dem zunächst die relative Pose jedes Kamerapaares ermittelt und anschließend die globalen Posen aller Kameras gleichzeitig berechnet werden.

• Inkrementelles SfM ist robust, aber aufgrund seiner sequenziellen Vorgehensweise anfällig für Drift (akkumulierte Fehler). Globales SfM berechnet alle Werte gleichzeitig und ist daher weniger anfällig für Drift, reagiert jedoch schlechter auf relative Posen mit vielen Ausreißern.

• Die durch Triangulation gewonnenen 3D-Punkte und Kameraposen sind für sich genommen nur grobe Schätzungen, die durch Bildrauschen beeinflusst werden. Die gleichzeitige Minimierung des Reprojektionsfehlers durch Bundle Adjustment bestimmt letztendlich die Genauigkeit von SfM.

SfM und Visual-SLAM basieren auf derselben Geometrie, unterscheiden sich aber in ihrer Designphilosophie: SfM ist eine Offline-Stapelverarbeitung, die Genauigkeit und Vollständigkeit priorisiert, während SLAM eine Online-Echtzeitverarbeitung ist, die Schnelligkeit und Kontinuität in den Vordergrund stellt.

1. Was benötigt SfM als Eingabe und was gibt es aus?

Die Eingabe besteht aus einem Satz von Bildern \{I_1,\dots,I_N\}, deren Aufnahmereihenfolge und relative Positionen unbekannt sind. Jedes Bild kann sogar mit einer anderen Kamera, einem anderen Objektiv und zu einem anderen Zeitpunkt aufgenommen worden sein. Die Ausgabe besteht aus drei Elementen:

• Die Kamerapose jedes Bildes i P_i=K_i[R_i\mid\mathbf{t}_i] (intrinsische und extrinsische Parameter)

• Eine Menge von 3D-Punkten in der Szene \{\mathbf{X}_j\} (meist eine spärliche Punktwolke, die Merkmalspunkten entspricht)

• Die Korrespondenz (Track), welche Bilder welche 3D-Punkte erfasst haben

Während die Kamerakalibrierungs-Einführung die intrinsischen Parameter einer einzelnen Kamera anhand eines festen Kalibrierungsmusters ermittelt, stellt SfM ein größeres inverses Problem dar: die gleichzeitige Bestimmung der intrinsischen und extrinsischen Parameter vieler unkalibrierter oder teilweise kalibrierter Kameras sowie der Szenenstruktur, ausschließlich aus geometrischen Abhängigkeiten zwischen korrespondierenden Punkten. Falls die EXIF-Metadaten eine Brennweite enthalten, wird diese als Anfangswert verwendet, die endgültige Genauigkeit hängt jedoch von den geometrischen Abhängigkeiten der Bilder selbst ab.

Diagram 1 · Use the button to switch views

Überprüfen Sie in einem Ergebnisbetrachter zunächst, ob die Kameras in einem unrealistisch kleinen Bereich zusammenfallen, ob die Punktwolke sich aufteilt oder verdoppelt und ob Bilder nicht registriert wurden. Ein gebäudeähnliches Erscheinungsbild allein beweist keine Genauigkeit. Bewerten Sie den Reprojektionsfehler, die Spurlänge und die Anzahl der registrierten Bilder; vergleichen Sie, falls eine vermessene Länge oder GNSS-Daten verfügbar sind, diese auch mit der entsprechenden externen Skala. Monokular SfM verwendet eine beliebige globale Skala. Daher entspricht die im Punktwolken-Viewer angezeigte Entfernung nicht automatisch einer Entfernung in Metern.

2. Die grundlegende Pipeline

Die vorherigen Schritte – Merkmalsextraktion, Matching und geometrische Verifizierung – entsprechen exakt den grundlegenden Techniken, die in Feature Detection Primer und Epipolar Geometry Primer beschrieben werden. SfM-spezifische Designentscheidungen kommen ins Spiel, nachdem jede Bildpaarbeziehung gefunden wurde: Wie lassen sich alle Bilder und Punkte in ein konsistentes, widerspruchsfreies Koordinatensystem einfügen? Hier unterscheiden sich die beiden Strategien von inkrementellem SfM und globalem SfM.

Die vorherigen Schritte – Merkmalsextraktion, Matching und geometrische Verifizierung – entsprechen exakt den elementaren Techniken, die in Feature Detection Primer und Epipolar Geometry Primer beschrieben werden. ## 3. Inkrementelles SfM: Hinzufügen von Kameras nacheinander

Das inkrementelle SfM beginnt mit der Auswahl eines initialen Bildpaares mit ausreichender Parallaxe und genügend Korrespondenzen. Die erste Zwei-Ansichten-Rekonstruktion wird durch Schätzung der Essentiellen/Fundamentalen Matrix aus der epipolaren Geometrie erstellt. Anschließend wird Folgendes wiederholt:

1. Auswahl eines neuen Bildes mit bereits vorhandenen 2D-Korrespondenzen zu registrierten 3D-Punkten und Bestimmung der Bildpose mittels PnP.

2. Triangulation der noch nicht in 3D rekonstruierten Punkte anhand der Korrespondenzen zwischen dem neuen Bild und den vorhandenen.

3. Verfeinerung von Pose und Struktur durch lokale oder globale Bündelausgleichung nach jeweils einer bestimmten Anzahl von Bildern.

4. Rückkehr zu Schritt 1, bis alle Bilder verarbeitet wurden oder keine weiteren Bilder mehr hinzugefügt werden können.

Dieser Ansatz, der seit Snavely et al.s „Photo Tourism“ (2006) weit verbreitet ist, wird auch von der Standard-Pipeline von COLMAP als inkrementelles SfM übernommen. Da jeweils nur eine geringe Anzahl unbekannter Variablen sequenziell erhöht wird, ist er robust und ermöglicht die einfache Erkennung und den Ausschluss fehlerhafter Bildpaare. Andererseits können sich kleine Fehler zu Beginn durch die schrittweise Speicherung der Posen auf spätere Bilder übertragen, und Datensätze mit großen Schleifen (Gruppen von Bildern, die denselben Ort wiederholt aufnehmen) neigen zu einer Akkumulation von Drift. Die periodische Bündelausgleichung in Kombination mit der Erkennung wiederholter Aufnahmen, die der Schleifenschließung entspricht, ist der Schlüssel zur Begrenzung dieses akkumulierten Fehlers.

4. Globales SfM: Alle paarweisen Beziehungen gleichzeitig lösen

Globales SfM registriert Bilder nicht sequenziell – es ermittelt zunächst die relative Pose (R_{ij},\mathbf{t}_{ij}/\|\mathbf{t}_{ij}\|) für jedes (oder eine ausgewählte Teilmenge von) Bildpaaren. Anschließend wird der gesamte Graph in zwei Schritten gemeinsam geschätzt.

Rotationsmittelung findet eine global minimal inkonsistente Menge von Kamerarotationen \{R_i\} aus der Menge der paarweisen relativen Rotationen R_{ij}. Eine häufig verwendete Fehlermetrik verwendet die Logarithmusabbildung auf der Lie-Gruppe SO(3):

\rho ist ein robuster Verlust, der den Einfluss falscher relativer Posen als Ausreißer unterdrückt.

Die Translationsmittelung ermittelt, sobald die Rotationen fixiert sind, die Kamerapositionen \{\mathbf{t}_i\} aus der Menge der relativen Translationsrichtungen \mathbf{t}_{ij}. Da eine monokulare relative Translation nur eine Richtung angibt (siehe die im Epipolar Geometry Primer diskutierte Skalenmehrdeutigkeit), muss eine konsistente Konfiguration aus vielen paarweisen Richtungsbeschränkungen berechnet werden – hierfür wurden Ansätze wie 1DSfM vorgeschlagen, die Ausreißer entfernen.

Da Global SfM Informationen aus jedem Bild gleichzeitig nutzt, ist es prinzipiell weniger anfällig für die sequentielle Drift, die bei Incremental SfM auftritt, und lässt sich zudem leichter parallelisieren. Werden jedoch Ausreißer in die einzelnen relativen Posen eingestreut, wird die gesamte globale Lösung verzerrt, sofern diese nicht im Mittelungsschritt erkannt und ausgeschlossen werden. Die Arbeit von Moulon et al. (ICCV 2013) ist ein repräsentatives Beispiel für die deutliche Verbesserung der Praktikabilität von Global SfM durch die Kombination robuster Rotationsmittelung mit Translationsrichtungsschätzung mittels des trifokalen Tensors.

Rekonstruktionsablauf | Fügt jeweils ein Bild aus einem initialen Paar hinzu | Löst zunächst alle paarweisen Beziehungen und optimiert anschließend gemeinsam |

| Driftresistenz | Anfällig für sequentielle Fehlerfortpflanzung und akkumulierte Fehler | Geringer akkumulierter Fehler, da global optimal | | Unempfindlichkeit gegenüber Ausreißern | Leicht zu erkennen und einzeln zu entfernen beim Hinzufügen eines Bildes | Die Entfernung von Ausreißern vor der Mittelwertbildung bestimmt die Genauigkeit |

Rechenaufwand | Sequentiell in der Anzahl der Bilder, tendenziell hoch bei großen Datenmengen | Parallelisierbar, erfordert jedoch globale Optimierung für die Mittelwertbildung |

Implementierungsschwierigkeiten | Zahlreiche Implementierungsbeispiele, einfache Optimierung der Robustheit | Theorie und Implementierung der Rotations-/Translationsmittelung sind komplexer |

Repräsentative Beispiele | Bundler, COLMAP (Standard), VisualSFM | openMVG (Global SfM-Pipeline), Theia |

In der Praxis werden neben der strikten Entweder-oder-Betrachtung der beiden Ansätze auch hybride Designs erforscht – beispielsweise die Erstellung einer groben globalen Pose mit Global SfM und deren schrittweise Verfeinerung oder die Verwendung von Paaren mit hoher Konfidenz im Global-SfM-Verfahren und die schrittweise Hinzufügung der restlichen Paare.

5. Triangulation und Track-Management

Sobald Posen für eine Gruppe von Bildern gefunden wurden, ist die Triangulation korrespondierender Punkte zur Gewinnung von 3D-Punkten eine Erweiterung der grundlegenden Zwei-Ansichten-Geometrieoperation. SfM-spezifisch ist die Verwaltung der Korrespondenz, des sogenannten „Tracks“, wenn derselbe physikalische Punkt in drei oder mehr Bildern beobachtet wird.

Da der Merkmalsabgleich paarweise erfolgt, sollte eine Übereinstimmung zwischen den Bildern A–B und B–C idealerweise auch eine Übereinstimmung zwischen A–C implizieren. In der Praxis ist dies jedoch bei realen Deskriptorabständen nicht immer gegeben. Eine trifokale Konsistenzprüfung sichert die Qualität der Tracks.

Je mehr Beobachtungen ein Track enthält, desto stabiler wird die Triangulation. Ein Track, der nur aus Bildern mit geringer Parallaxe besteht, führt jedoch dennoch zu einer instabilen Tiefeninformation.

Selbst eine einzelne fehlerhafte Übereinstimmung in einem Track verzerrt nicht nur die 3D-Position dieses Punktes, sondern beeinflusst auch die Residuen der nachfolgenden Bündelausgleichung insgesamt. Eine RANSAC-ähnliche Überprüfung pro Track und das Verwerfen von Tracks mit großem Reprojektionsfehler sind daher notwendig.

6. Die Brücke zur Bündelausgleichung

Die durch lineare Triangulation oder sequentielle PnP erhaltenen Pose- und Strukturwerte sind bestenfalls Ausgangswerte. Gleichzeitige Minimierung des Reprojektionsfehlers über alle Bilder –

– ist die sogenannte Bundle Adjustment, die letztendlich die Genauigkeit von SfM bestimmt. Warum diese Optimierung eine spärliche Struktur aufweist und warum das Schur-Komplement ihre Lösbarkeit auch bei großen Datenmengen ermöglicht, sind Rechenfragen, die im Bundle Adjustment Primer ausführlich behandelt werden. Wichtig ist hierbei der Unterschied in der Anwendung: Inkrementelles SfM führt nach jeweils einigen hinzugefügten Bildern eine lokale Bundle Adjustment durch, während globales SfM eine vollständige Bundle Adjustment durchführt, sobald alle globalen Posen vorliegen.

7. Unterschiede und Gemeinsamkeiten mit Visual-SLAM

SfM und Visual-SLAM verwenden dieselben mathematischen Werkzeuge: Feature Matching, Epipolargeometrie, PnP und Bundle Adjustment. Der Unterschied liegt in ihren Zielen und Einschränkungen.

In der Praxis sind Kombinationen wie die Verwendung einer hochpräzisen, mittels SfM erstellten 3D-Karte als Ausgangskarte oder Maßstabsreferenz für SLAM oder die Offline-Nachbearbeitung der SLAM-Keyframe-Trajektorie mit SfM zur Genauigkeitssteigerung ebenfalls üblich. Die beiden Technologien stehen nicht im Wettbewerb zueinander, sondern ergänzen sich im Offline-/Online-Zeitraum.

8. Repräsentative Implementierungen

• COLMAP: Basierend auf inkrementellem SfM ist dies die derzeit am häufigsten referenzierte Forschungs- und Produktionsimplementierung. Sie bietet eine konsistente Pipeline von der Merkmalsextraktion über Matching, geometrische Verifizierung und Rekonstruktion bis hin zu Bundle Adjustment und Multi-View Stereo.

• openMVG (open Multiple View Geometry): Eine Bibliothek, die sowohl inkrementelle als auch globale SfM-Pipelines implementiert. Wird häufig mit openMVS für die dichte Rekonstruktion kombiniert.

• Bundler: Die wegweisende inkrementelle SfM-Implementierung, die die Ergebnisse des Fototourismus öffentlich machte und als Vergleichsgrundlage für viele nachfolgende Arbeiten diente.

• Meshroom (AliceVision): Ein Open-Source-Photogrammetrie-Tool mit einer grafischen Benutzeroberfläche, das alle Schritte von SfM über MVS bis hin zur Texturierung in einem Durchgang durchführt.

Bei der Auswahl einer Bibliothek ist „neuer bedeutet genauer“ nicht das richtige Kriterium. Berücksichtigen Sie stattdessen die Anzahl der zu verarbeitenden Bilder, die GPU-/CPU-Ressourcen, die Zuverlässigkeit der EXIF-Brennweite, die Matching-Strategie (erschöpfend/sequenziell/Vokabularbaum) und ob Sie eine durchgängig konsistente Pipeline für MVS und Texturgenerierung benötigen.

9. Schwierige Bedingungen und häufige Fehlerfälle

• Texturarme oder stark repetitive Szenen: Gleichförmige Wände, geflieste Oberflächen und Feldreihen liefern entweder gar keine Entsprechungen oder führen zu häufigen Fehlzuordnungen.

• Bildserien mit extrem geringer Parallaxe: Fotos einer entfernten Szene, aufgenommen mit einem Teleobjektiv, machen die Triangulation instabil und führen zu großen Tiefenfehlern.

• Bewegte Objekte und wechselnde Lichtverhältnisse: Fotoserien von Touristenattraktionen enthalten Personen, Fahrzeuge und saisonale oder tageszeitliche Unterschiede. Dadurch entstehen Korrespondenzen, die die Annahme einer statischen Szene verletzen.

• Isolierte Bildgruppen: Wenn sich Aufnahmen in zwei Gruppen ohne überlappendes Sichtfeld aufteilen, kann SfM sie nicht zu einem konsistenten Koordinatensystem zusammenführen, und die Rekonstruktion zerfällt in mehrere unzusammenhängende Teile.

• Symmetrische Szenen: Symmetrische Gebäudefassaden können beispielsweise zu einer geometrisch konsistenten, aber physikalisch falschen Spiegellösung führen.

10. Praktische Entscheidungen

• Bei vollständig geordneten Aufnahmen (Video oder kontinuierliche Bilder eines Roboters) ist die Auswahl des ersten Bildpaares bei inkrementellem SfM einfach, und die Standard-Pipeline von COLMAP ist oft ausreichend.

• Bei großen Bildersammlungen wie Internet-Touristenfotos, bei denen Aufnahmereihenfolge und Überlappung unbekannt sind, bietet die Skalierbarkeit von Global SfM oft Vorteile.

Für Anwendungen, die Echtzeitfähigkeit erfordern (Robotik, AR, Automobilindustrie), sollten Sie Visual-SLAM oder VIO anstelle von SfM in Betracht ziehen. SfM konzentriert sich hauptsächlich auf die Offline-Rekonstruktion mit hoher Präzision.

Wenn Sie eine dichte 3D-Form (ein Mesh oder ein texturiertes Modell) benötigen, beginnen Sie mit der spärlichen Punktwolke und Pose von SfM und verwenden Sie anschließend Multi-View Stereo (MVS).

11. Zusammenfassung

Structure from Motion (SfM) ist eine Technologie, die Kameraposen und 3D-Strukturen gemeinsam aus einem ungeordneten Bilddatensatz rekonstruiert. Dies geschieht durch Merkmalsabgleich und geometrische Verifizierung mithilfe der inkrementellen oder globalen SfM-Strategie. Inkrementelle Verfahren sind robust, aber anfällig für Drift, während globale Verfahren driftresistent, aber empfindlich gegenüber Ausreißern sind – ein symmetrischer Kompromiss. Bei beiden Strategien wird die endgültige Genauigkeit durch Bündelausgleichung erreicht, der direkt mit Visual-SLAM, der verwandten Technologie, die auf einer anderen Zeitachse arbeitet, und mit Multi-View Stereo, einer Technologie zur dichten Rekonstruktion, verbunden ist.

Referenzen

• Snavely, Seitz & Szeliski, Photo Tourism: Exploring Photo Collections in 3D (SIGGRAPH 2006)
• Schönberger & Frahm, Structure-from-Motion Revisited (CVPR 2016)
• Moulon, Monasse & Marlet, Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion (ICCV 2013)
• Wilson & Snavely, Robust Global Translations with 1DSfM (ECCV 2014)
• Offizielle COLMAP-Dokumentation

• Offizielle openMVG-Dokumentation

• Hartley & Zisserman, Multiple View Geometry in Computer Vision (Offizielle Autorenseite)