Bundle Adjustment

• Aussi appelé: BA
• Catégorie: State estimation & navigation › Localisation
• Mots-clés: slam, nonlinear-optimization, computer-vision, 3d-reconstruction, state-estimation

Affinage conjoint par moindres carrés non linéaires des poses des caméras et des positions des amers 3D, et parfois des paramètres des caméras, qui minimise l'erreur de reprojection de toutes les caractéristiques observées.

Définition

L'ajustement de faisceaux (Bundle adjustment, BA) affine une reconstruction 3D en ajustant conjointement les poses des caméras et les positions des points 3D, de sorte que les points, projetés dans chaque image, tombent aussi près que possible de l'endroit où les caractéristiques ont réellement été observées. La quantité minimisée est la somme des carrés des erreurs de reprojection (reprojection errors), les distances en pixels entre positions prédites et mesurées des caractéristiques, généralement pondérées par l'incertitude de mesure et enveloppées dans une perte robuste comme Huber ou Cauchy pour limiter l'influence des mauvais appariements. Le nom fait référence aux faisceaux de rayons lumineux qui relient chaque point 3D aux centres des caméras qui l'observent ; l'optimisation ajuste ces faisceaux jusqu'à ce qu'ils concordent. La technique vient de la photogrammétrie, et une présentation moderne très citée est la synthèse de Triggs, McLauchlan, Hartley et Fitzgibbon (2000).

Le problème est non linéaire à cause des rotations et de la projection perspective ; il est donc résolu de façon itérative, typiquement avec Levenberg-Marquardt. Sa structure le rend traitable à grande échelle : chaque résidu ne fait intervenir qu'une caméra et un point, donc le système est creux, et les points peuvent être éliminés par le complément de Schur (Schur complement), ce qui laisse un système beaucoup plus petit portant sur les seules variables des caméras. La solution n'est définie qu'à une liberté de jauge près, une rotation et une translation globales et, pour une seule caméra sans autres capteurs, une échelle globale ; on fixe donc certaines variables ou on ajoute un a priori. Les paramètres intrinsèques de la caméra et la distorsion peuvent être affinés en même temps lorsqu'ils ne sont pas bien étalonnés.

En robotique, le BA est au cœur de la Structure from Motion et du SLAM visuel à images clés. Le BA global (Global BA) optimise toute la carte et s'exécute hors ligne ou après les fermetures de boucle ; le BA local ou à fenêtre glissante (sliding-window BA) n'optimise que les images clés les plus récentes et les amers qu'elles voient, en gardant les états plus anciens fixes ou marginalisés, ce qui lui permet de fonctionner en temps réel. Les systèmes visuels-inertiels l'étendent avec des facteurs de préintégration IMU, et d'autres facteurs de capteurs peuvent être ajoutés dans le même graphe de facteurs. Le BA diffère de l'optimisation de graphe de poses (pose graph optimization) en ce qu'il conserve les amers comme variables et utilise les mesures brutes des images ; un graphe de poses ne garde que les poses et des contraintes relatives, ce qui est plus rapide et plus compact mais perd de l'information.

Pourquoi c'est important

L'ajustement de faisceaux est ce qui transforme des pistes de caractéristiques bruitées en trajectoires de caméra et en cartes 3D précises. La plupart des chaînes d'odométrie visuelle, de SLAM visuel et de photogrammétrie en dépendent, et le choix entre BA global, local et à fenêtre glissante fixe en grande partie le compromis entre précision et performance temps réel dans ces systèmes.

Applications principales

• Structure from Motion et photogrammétrie
• Back-ends de SLAM visuel et visuel-inertiel à images clés
• Odométrie visuelle à fenêtre glissante sur des drones, des véhicules et des robots sous-marins
• Affinage de l'étalonnage multi-caméras et caméra-lidar
• Reconstruction 3D pour l'inspection, la cartographie et les jumeaux numériques

En pratique

Dans un système de SLAM visuel-inertiel embarqué sur un robot sous-marin ou aérien, une nouvelle image clé est créée chaque fois que la caméra s'est suffisamment déplacée. Un optimiseur à fenêtre glissante affine alors les poses des images clés les plus récentes, leurs vitesses et les biais de l'IMU, ainsi que tous les amers vus dans ces images clés, à l'aide de facteurs de reprojection issus des caractéristiques suivies et de facteurs IMU préintégrés entre images clés. Les images clés plus anciennes sont marginalisées en un a priori pour que la fenêtre garde une taille fixe. Une perte de Huber limite l'effet des caractéristiques mal appariées dues à des objets en mouvement ou à des reflets. Lorsqu'une fermeture de boucle est détectée, une optimisation de graphe de poses ou un BA global complet corrige la dérive sur toute la trajectoire, généralement dans un thread d'arrière-plan.

Idées reçues

• L'ajustement de faisceaux est la même chose que l'optimisation de graphe de poses — le BA optimise aussi les positions des amers par rapport aux mesures dans les images, alors qu'un graphe de poses ne garde que les poses et des contraintes relatives
• Le BA corrige une mauvaise initialisation — c'est un optimiseur local qui a besoin d'une estimation de départ raisonnable des poses et des points pour converger vers la bonne réponse
• Le BA monoculaire retrouve la vraie échelle — sans autre capteur ni dimension connue, l'échelle est inobservable et peut dériver
• Le BA ne sert qu'à la reconstruction hors ligne — les variantes locales et à fenêtre glissante fonctionnent en temps réel dans de nombreux systèmes de SLAM

Qui devrait le savoir

• Ingénieurs en SLAM visuel et en odométrie visuelle
• Ingénieurs en vision par ordinateur et en photogrammétrie
• Ingénieurs en estimation d'état fusionnant des caméras avec d'autres capteurs
• Étudiants en robotique qui étudient la cartographie et la localisation

Technologies associées

• Structure from Motion
• Algorithme de Levenberg-Marquardt (Levenberg-Marquardt Algorithm)
• Ceres Solver
• g2o
• GTSAM
• COLMAP

Termes associés

• Pose Graph Optimization
• Factor Graph
• Keyframe
• SLAM
• Visual-Inertial Odometry
• Camera Intrinsics

Projets associés

• LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
• oomwoo: Open-source DIY robot vacuum: 3D-printed, ROS2 + 2D LiDAR, fully local.
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
• FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
• DimOS: Python robotics runtime with agents, SLAM and teleop, no ROS required

Vidéos

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