Bundle Adjustment

Auch genannt: BA
Kategorie: State estimation & navigation › Localisation
Schlagwörter: slam, nonlinear-optimization, computer-vision, 3d-reconstruction, state-estimation

Gemeinsame nichtlineare Kleinste-Quadrate-Verfeinerung von Kameraposen und 3D-Landmarkenpositionen, manchmal auch von Kameraparametern, die den Reprojektionsfehler aller beobachteten Merkmale minimiert.

Definition

Bündelblockausgleichung (Bundle adjustment, BA) verfeinert eine 3D-Rekonstruktion, indem Kameraposen und die Positionen von 3D-Punkten gemeinsam so angepasst werden, dass die Punkte, in jedes Bild projiziert, so nah wie möglich dort landen, wo die Merkmale tatsächlich beobachtet wurden. Minimiert wird die Summe der quadrierten Reprojektionsfehler (reprojection errors), der Pixelabstände zwischen vorhergesagten und gemessenen Merkmalspositionen, meist gewichtet mit der Messunsicherheit und in eine robuste Verlustfunktion wie Huber oder Cauchy eingebettet, um den Einfluss falscher Zuordnungen zu begrenzen. Der Name bezieht sich auf die Bündel von Lichtstrahlen, die jeden 3D-Punkt mit den Kamerazentren verbinden, die ihn beobachten; die Optimierung passt diese Bündel an, bis sie übereinstimmen. Das Verfahren stammt aus der Photogrammetrie, und eine viel zitierte moderne Darstellung ist der Übersichtsartikel von Triggs, McLauchlan, Hartley und Fitzgibbon (2000).

Das Problem ist wegen der Rotationen und der perspektivischen Projektion nichtlinear und wird daher iterativ gelöst, typischerweise mit Levenberg-Marquardt. Seine Struktur macht es auch in großem Maßstab handhabbar: Jedes Residuum betrifft nur eine Kamera und einen Punkt, sodass das System dünn besetzt ist, und die Punkte lassen sich mit dem Schur-Komplement (Schur complement) eliminieren, wodurch ein viel kleineres System allein in den Kameravariablen übrig bleibt. Die Lösung ist nur bis auf eine Eichfreiheit bestimmt, eine globale Rotation und Translation und, bei einer einzelnen Kamera ohne weitere Sensoren, einen globalen Maßstab, daher werden einige Variablen festgehalten oder ein Prior hinzugefügt. Intrinsische Kameraparameter und Verzeichnung können gleichzeitig verfeinert werden, wenn sie nicht gut kalibriert sind.

In der Robotik ist BA der Kern von Structure from Motion und von keyframe-basiertem visuellem SLAM. Globale BA (Global BA) optimiert die gesamte Karte und läuft offline oder nach Loop Closures; lokale (local) BA oder Sliding-Window-BA optimiert nur die jüngsten Keyframes und die Landmarken, die sie sehen, und hält ältere Zustände fest oder marginalisiert sie, sodass sie in Echtzeit laufen kann. Visuell-inertiale Systeme erweitern sie um IMU-Präintegrationsfaktoren, und weitere Sensorfaktoren können im selben Faktorgraphen hinzugefügt werden. BA unterscheidet sich von der Posengraph-Optimierung (pose graph optimization) dadurch, dass sie Landmarken als Variablen behält und die rohen Bildmessungen nutzt; ein Posengraph behält nur Posen und relative Nebenbedingungen, was schneller und kleiner ist, aber Information verwirft.

Warum es wichtig ist

Die Bündelblockausgleichung macht aus verrauschten Merkmalsspuren genaue Kameratrajektorien und 3D-Karten. Die meisten Pipelines für visuelle Odometrie, visuelles SLAM und Photogrammetrie stützen sich darauf, und die Wahl zwischen globaler, lokaler und Sliding-Window-BA bestimmt in diesen Systemen weitgehend den Kompromiss zwischen Genauigkeit und Echtzeitfähigkeit.

Wichtige Anwendungen

Structure from Motion und Photogrammetrie
Backends von keyframe-basiertem visuellem und visuell-inertialem SLAM
Visuelle Sliding-Window-Odometrie auf Drohnen, Fahrzeugen und Unterwasserrobotern
Verfeinerung der Kalibrierung von Mehrkamera- und Kamera-Lidar-Systemen
3D-Rekonstruktion für Inspektion, Kartierung und digitale Zwillinge

In der Praxis

In einem visuell-inertialen SLAM-System auf einem Unterwasser- oder Flugroboter wird jedes Mal ein neues Keyframe erzeugt, wenn sich die Kamera weit genug bewegt hat. Ein Sliding-Window-Optimierer verfeinert dann die jüngsten Keyframe-Posen, ihre Geschwindigkeiten und IMU-Biases sowie alle in diesen Keyframes gesehenen Landmarken, mithilfe von Reprojektionsfaktoren aus den verfolgten Merkmalen und präintegrierten IMU-Faktoren zwischen Keyframes. Ältere Keyframes werden in einen Prior marginalisiert, sodass das Fenster eine feste Größe behält. Ein Huber-Verlust begrenzt den Effekt falsch zugeordneter Merkmale, die durch bewegte Objekte oder Spiegelungen entstehen. Wird eine Loop Closure erkannt, korrigiert eine Posengraph-Optimierung oder eine vollständige globale BA die Drift über die gesamte Trajektorie, meist in einem Hintergrund-Thread.

Häufige Missverständnisse

Bündelblockausgleichung ist dasselbe wie Posengraph-Optimierung — BA optimiert auch Landmarkenpositionen gegen Bildmessungen, während ein Posengraph nur Posen und relative Nebenbedingungen behält
BA behebt eine schlechte Initialisierung — sie ist ein lokaler Optimierer und braucht eine vernünftige Startschätzung von Posen und Punkten, um zur richtigen Lösung zu konvergieren
Monokulare BA stellt den wahren Maßstab wieder her — ohne weiteren Sensor oder bekannte Abmessung ist der Maßstab nicht beobachtbar und kann driften
BA ist nur für Offline-Rekonstruktion — lokale und Sliding-Window-Varianten laufen in vielen SLAM-Systemen in Echtzeit

Wer das wissen sollte

Ingenieure für visuelles SLAM und visuelle Odometrie
Computer-Vision- und Photogrammetrie-Ingenieure
Ingenieure für Zustandsschätzung, die Kameras mit anderen Sensoren fusionieren
Robotikstudierende, die Kartierung und Lokalisierung lernen

Videos

Bundle Adjustment - 5 Minutes with Cyrill: Cyrill Stachniss
The Basics about Bundle Adjustment (Cyrill Stachniss): Cyrill Stachniss

Open Source Robotics