Introduction à l'ajustement par faisceaux — La méthode des moindres carrés non linéaires qui optimise simultanément les poses de caméra et les points 3D

Les poses de caméra et les points 3D obtenus par Structure from Motion et Visual-SLAM via triangulation et PnP ne sont, au mieux, que des valeurs initiales approximatives issues d'approximations linéaires et d'un traitement séquentiel. Le bruit par image, l'erreur de quantification des points de correspondance et l'erreur propagée due à l'estimation séquentielle s'accumulent, aboutissant à une reconstruction incohérente. L'ajustement par faisceaux (BA) est l'optimisation finale qui corrige cette incohérence en déplaçant simultanément chaque paramètre de caméra et chaque point 3D, minimisant ainsi la somme des erreurs de reprojection sur tous les points observés. Le terme « faisceau » provient de l'ajustement simultané du faisceau de rayons lumineux reliant chaque point 3D à chaque caméra, afin qu'ils correspondent aux positions observées.

0. Résumé en 30 secondes

• L'ajustement de faisceaux est un problème de moindres carrés non linéaires dont les inconnues sont les paramètres intrinsèques et extrinsèques des caméras et les coordonnées des points 3D. Il s'agit de minimiser la somme des carrés des erreurs de reprojection sur toutes les observations.

• Il est résolu itérativement par la méthode de Gauss-Newton ou par l'algorithme de Levenberg-Marquardt (LM). LM effectue une interpolation continue, via un paramètre \lambda, entre la méthode de Gauss-Newton, instable mais rapide, et la méthode de la plus forte pente, lente mais stable.

• Puisqu'une caméra est toujours associée uniquement aux points qu'elle a effectivement observés, l'approximation du jacobien et du hessien prend une forme creuse, structurée en blocs et organisée par caméra × point. Cette structure creuse est essentielle pour rendre les problèmes à grande échelle traitables. La technique du complément de Schur exploite l'indépendance des blocs de points 3D (diagonale des blocs), en éliminant d'abord les points superflus pour résoudre un système de caméras réduit, composé uniquement des caméras. C'est ce qui permet de résoudre des problèmes à l'échelle de dizaines de milliers de points et de milliers de caméras dans un délai raisonnable.

L'ajustement de faisceaux est étroitement lié à l'optimisation du graphe de poses du SLAM, à la différence que ses inconnues incluent les points 3D eux-mêmes. Il s'agit d'une technologie fondamentale commune, utilisée à la fois pour finaliser la SfM et pour l'optimisation locale/globale du SLAM.

1. Quelles sont ses entrées et quel problème résout-elle ?

Les données d'entrée comprennent les trois estimations initiales suivantes, obtenues comme résultats intermédiaires de SfM ou Visual-SLAM :

• Valeurs initiales des poses de caméra \{K_i, R_i, \mathbf{t}_i\} (i=1,\dots,m ; dans de nombreux cas, les paramètres intrinsèques K_i sont connus ou fixes)

• Valeurs initiales des points 3D \{\mathbf{X}_j\} (j=1,\dots,n ; coordonnées approximatives obtenues par triangulation)

• Correspondance entre la caméra ayant observé chaque point — c'est-à-dire les coordonnées image \mathbf{u}_{ij} pour chaque observation (la position du pixel où la caméra i a observé le point j)

Les données de sortie sont les poses de caméra et les points 3D, ajustés simultanément avec précision, ce qui assure une meilleure cohérence interne. Remarque : Le fait que l’ajustement par faisceaux ne soit pas une méthode de construction d’une solution à partir de zéro, mais plutôt une optimisation de finition qui affine localement une valeur initiale déjà « approximativement correcte », est important pour la discussion sur la convergence ci-dessous.

2. Fonction de coût : Erreur de reprojection

L’écart entre la projection d’un point 3D \mathbf{X}_j sur la caméra i et les coordonnées de l’image réellement observée \mathbf{u}_{ij} est appelé erreur de reprojection. En notant la pose de la caméra i R_i, \mathbf{t}_i et la fonction de projection \pi(\cdot) (l’application non linéaire convertissant les coordonnées homogènes en coordonnées de pixels), le résidu pour une observation est :

L’ajustement par faisceaux minimise la somme des carrés de ce résidu sur l’ensemble des paires observées \mathcal{O}=\{(i,j)\}.

\rho est une fonction de perte robuste, telle que la perte de Huber, qui empêche une seule valeur aberrante importante due à un décalage de fausser l'optimisation globale. Cette équation est exactement la même que celle déjà vue dans le guide SfM — L'ajustement de faisceaux traite du cœur de calcul de la résolution de ce problème de minimisation.

3. Résolution par moindres carrés non linéaires : de Gauss-Newton à Levenberg-Marquardt

En regroupant toutes les inconnues dans un seul vecteur \mathbf{x} (toutes les poses de la caméra et tous les points 3D regroupés), et en écrivant l'ensemble des résidus dans \mathbf{r}(\mathbf{x}), la cible de minimisation est \|\mathbf{r}(\mathbf{x})\|^2. Puisque \mathbf{r} est non linéaire, nous utilisons un développement de Taylor au premier ordre autour de l'estimation actuelle \mathbf{x}_k : \mathbf{r}(\mathbf{x}_k+\Delta\mathbf{x})\approx \mathbf{r}(\mathbf{x}_k)+J\Delta\mathbf{x}. J=\partial \mathbf{r}/\partial \mathbf{x} est le jacobien. En le substituant dans l'équation et en résolvant pour \Delta\mathbf{x}, on obtient l'équation normale de la méthode de Gauss-Newton :

H=J^\mathsf{T}J est l'approximation hessienne (l'approximation de Gauss-Newton, en négligeant les termes du second ordre). La procédure complète consiste à résoudre cette équation pour \Delta\mathbf{x}, à mettre à jour \mathbf{x}_{k+1}=\mathbf{x}_k+\Delta\mathbf{x} et à répéter cette opération jusqu'à convergence du résidu.

La méthode de Gauss-Newton converge rapidement lorsque la valeur initiale est proche de la solution, mais tend à diverger avec une mauvaise valeur initiale. L'algorithme de Levenberg-Marquardt (LM), proposé indépendamment par Levenberg (1944) et Marquardt (1963), atténue ce problème en ajoutant un terme d'amortissement à l'équation normale.

D est généralement la matrice diagonale de J^\mathsf{T}J (ou d'une matrice d'échelle équivalente), et \lambda est le coefficient d'amortissement. Lorsque \lambda est petit, l'algorithme se comporte comme l'algorithme de Gauss-Newton et converge rapidement ; lorsque \lambda est grand, la convergence se fait par petits pas prudents, se rapprochant de la pente la plus forte. Grâce à un système de contrôle adaptatif — qui consiste à réduire le pas pour accélérer lorsque le coût diminue à chaque itération, et à l'augmenter pour le rejeter et le raccourcir lorsque le coût augmente —, l'ajustement de faisceau (LM) combine la vitesse de Gauss-Newton avec la stabilité de la méthode de la plus forte pente. Presque toutes les implémentations pratiques de l'ajustement de faisceau (Ceres Solver, g2o, SBA, etc., présentées ci-dessous) utilisent LM ou une méthode de région de confiance similaire.

4. Pourquoi la matrice jacobienne est-elle creuse ?

Les inconnues de l'ajustement de faisceau sont la pose de la caméra (6 degrés de liberté — 3 rotations et 3 translations, si les paramètres intrinsèques sont fixés) × m caméras, et les points 3D (3 degrés de liberté) × n points, ce qui représente jusqu'à 6m+3n dimensions. Dans les problèmes SfM réels comportant des dizaines de milliers d'observations, voire plus, traiter naïvement cette matrice J^\mathsf{T}J comme une matrice dense a un coût O((6m+3n)^3) — irrésoluble dans un temps réaliste.

La solution réside ici dans la structure selon laquelle l'erreur de reprojection r_{ij} « dépend uniquement des paramètres de la caméra i et des paramètres du point j ». Les dérivées partielles par rapport à toute autre caméra k\neq i ou tout autre point l\neq j sont identiquement nulles.

Autrement dit, la ligne du jacobien générée par une observation unique ne comporte d'éléments non nuls que dans le bloc correspondant à la caméra et dans le bloc correspondant au point. Le nombre de lignes augmente proportionnellement au nombre d'observations, mais le nombre d'éléments non nuls par ligne reste constant (caméra 6 + point 3, ou légèrement supérieur si les paramètres intrinsèques sont inclus). Cette faible densité se manifeste, lorsqu'on examine J^\mathsf{T}J, par la structure de blocs suivante :

• B : interactions entre les paramètres des caméras. Cette valeur est nulle sauf si les caméras i et k observent un point commun ; sa structure de blocs est donc clairsemée.

• C : interactions entre les paramètres des points 3D. Puisqu'un point (j) possède trois degrés de liberté qui ne sont jamais couplés à aucun autre point, il s'agit d'une matrice diagonale par blocs — condition préalable à l'astuce du complément de Schur présentée dans la section suivante. - E : interactions entre les caméras et les points (un bloc non nul apparaît pour chaque observation (i,j)).

5. Le pipeline de base

Diagram 1 · Use the button to switch views

Chaque itération recalcule l'erreur de reprojection, assemble le jacobien creux et résout le problème. Le système, basé uniquement sur la caméra, est réduit grâce au complément de Schur et mis à jour par la commande pas à pas du modèle de Langeid. Ce processus se répète jusqu'à ce que la variation de coût descende en dessous d'un seuil ou qu'un nombre maximal d'itérations soit atteint.

6. L'astuce du complément de Schur : Transformer la parcimonie en calcul réduit

En utilisant la structure par blocs de la section précédente, nous pouvons écrire l'équation normale (J^\mathsf{T}J+\lambda D)\Delta\mathbf{x}=-J^\mathsf{T}\mathbf{r} en deux parties : la mise à jour de la caméra \Delta\mathbf{c} et la mise à jour des points \Delta\mathbf{p}.

(où B', C' représentent les blocs après l'ajout du terme d'amortissement). Puisque C' est une matrice diagonale par blocs, indépendante pour chaque point 3D, chaque bloc 3×3 peut être inversé individuellement, à un coût approximativement proportionnel au nombre de points n. L'utilisation de C'^{-1} pour éliminer \Delta\mathbf{p} permet d'obtenir le système de caméra réduit, ne comportant que des caméras :

Le B'-EC'^{-1}E^\mathsf{T} du membre de gauche est appelé complément de Schur. Cette matrice a une taille 6m\times 6m (dépendant uniquement du nombre de caméras, et non du nombre de points n). Une fois \Delta\mathbf{c} résolu, la mise à jour de chaque point peut être récupérée à moindre coût avec :

Dans un problème SfM typique, le nombre de points n peut être des dizaines de fois supérieur au nombre de caméras m. Ainsi, au lieu de résoudre naïvement un système de dimensions 6m+3n, il suffit de traiter le complément de Schur, de dimension 6m. C'est l'idée fondamentale qui rend l'ajustement de faisceaux pratiquement résoluble, même à l'échelle de dizaines de milliers de points. Cette méthode a été théoriquement organisée par Triggs et al. dans leur article « Bundle Adjustment — A Modern Synthesis » (2000), et constitue l'implémentation interne standard des bibliothèques actuelles telles que Ceres Solver et g2o.

Ceres Solver propose plusieurs options pour résoudre ce système réduit : DENSE_SCHUR, qui le résout comme une matrice dense (jusqu'à quelques centaines de caméras) ; SPARSE_SCHUR, qui exploite la sparsité par réordonnancement (plusieurs milliers de caméras) ; et ITERATIVE_SCHUR, qui applique le gradient conjugué au complément de Schur (pour des problèmes à plus grande échelle). Le choix de l'option en fonction de l'échelle du problème est une règle pratique.

7. Liberté de jauge : les directions selon lesquelles la solution n'est pas déterminée de manière unique

L'ajustement de faisceau conserve un degré de liberté permettant de déplacer l'ensemble des paramètres sans modifier la valeur de la fonction de coût. Déplacer simultanément chaque caméra et chaque point 3D selon la même rotation, translation et échelle ne modifie pas l'erreur de reprojection (dans le cas d'une vision monoculaire, l'échelle absolue est également indéterminée). Ce degré de liberté est appelé liberté de jauge. S'il n'est pas pris en compte, il rend J^\mathsf{T}J singulière (de rang insuffisant), ce qui rend l'équation normale soit insoluble, soit numériquement instable.

En pratique, on contourne ce problème en fixant la pose des deux premières caméras ou une longueur de base, ou en s'appuyant sur le fait que le terme d'amortissement \lambda D du modèle linéaire régularise implicitement cette direction singulière. Lorsque des informations sur l'échelle ou la pose absolues sont disponibles (provenant par exemple d'un GPS ou d'une centrale inertielle), il est naturel de les utiliser comme contrainte supplémentaire pour fixer la jauge.

8. Différence avec l'optimisation par graphe de pose

L'optimisation par graphe de pose, abordée dans le guide de fermeture de boucle, appartient au même cadre mathématique que l'ajustement de faisceaux, car elle minimise, avec une fonction de perte robuste, un résidu des moindres carrés non linéaires construit à partir de l'application \mathrm{Log}. La différence réside dans la nature des inconnues.

Dans les systèmes Visual-SLAM réels, on observe généralement une division du travail : l’ajustement de faisceaux local (BA local), incluant les points 3D, affine la zone autour des images clés image par image, tandis que l’optimisation légère du graphe de pose, sans points 3D explicites, corrige rapidement la trajectoire globale dès qu’une fermeture de boucle est détectée. L’ajustement de faisceaux complet, incluant les points 3D (BA global), est plus précis mais plus coûteux en calcul ; il ne peut donc pas être exécuté fréquemment dans des situations exigeant des performances en temps réel.

9. Implémentations représentatives

• Ceres Solver : bibliothèque de moindres carrés non linéaires à usage général développée par Google et utilisée en production depuis 2010. Elle intègre des solveurs basés sur l'algorithme de Schur et sert de moteur d'ajustement de faisceaux pour de nombreuses implémentations SfM/SLAM, dont COLMAP.

• g2o : framework d'optimisation de graphes publié par Kümmerle et al. à ICRA 2011, capable de gérer à la fois l'optimisation du graphe de pose SLAM et l'ajustement de faisceaux au sein d'un même environnement. Il a été largement utilisé comme moteur de la famille ORB-SLAM.

• SBA (Sparse Bundle Adjustment) : une des premières implémentations publiques spécialisées dans l'ajustement de faisceaux épars, publiée par Lourakis et Argyros dans ACM Transactions on Mathematical Software en 2009. Elle est souvent citée comme exemple représentatif implémentant explicitement l'astuce du complément de Schur. - Ajustement de faisceaux intégré à COLMAP : utilise en interne le solveur Ceres, basculant automatiquement entre l'ajustement de faisceaux local et global à chaque étape de la modélisation incrémentale par structure (SfM).

10. Conditions difficiles et cas d'échec courants

• Mauvaises valeurs initiales : l'ajustement de faisceaux est une optimisation locale. Si la valeur initiale est éloignée de la solution exacte, elle peut converger vers une solution locale erronée, voire ne pas converger du tout. La qualité de la valeur initiale obtenue par triangulation ou par pointage-point (PnP) détermine la précision finale.

• Points avec peu d'observations ou faible parallaxe : un point observé sur un nombre très restreint d'images, ou présentant une faible parallaxe, a tendance à avoir un jacobien mal conditionné et peut laisser une erreur résiduelle importante concentrée uniquement dans la direction de la profondeur.

• Forte contamination par des valeurs aberrantes : en présence de nombreuses erreurs d'appariement, même une fonction de perte robuste ne peut pas les absorber complètement, et les points voisins corrects peuvent également se retrouver déformés. - Problèmes à très grande échelle : pour les reconstructions à l'échelle d'une ville avec des millions d'observations, même avec le complément de Schur, les coûts de calcul et de mémoire deviennent non négligeables. Il est alors nécessaire de diviser et de paralléliser le problème, ou de le combiner avec des techniques d'approximation (comme le grossissement de la région de confiance du modèle de Langelier).

• Liberté de jauge non gérée : comme indiqué précédemment, oublier de fixer la jauge provoque une instabilité numérique, pouvant entraîner une absence de convergence ou une solution non physique.

11. Choix pratiques

• Si une précision élevée est requise pour l'étape finale de la reconstruction 3D par image (SfM), il est recommandé d'effectuer un ajustement complet des faisceaux à la fin, quelle que soit la stratégie utilisée (incrémentale ou globale). Conserver les paramètres par défaut d'une implémentation existante comme COLMAP ne devrait pas poser de problème majeur.

• Pour le SLAM en temps réel, un ajustement complet des faisceaux sur chaque image est trop coûteux en calcul. Une conception pratique combine un ajustement local des faisceaux, appliqué uniquement à l'ensemble d'images clés le plus récent, avec une optimisation du graphe de poses déclenchée uniquement à la fermeture de la boucle.

• Si vous développez votre propre pipeline, il est judicieux de l'appuyer sur une bibliothèque comme Ceres Solver ou g2o. Implémenter le complément de Schur à partir de zéro n'apporte que peu d'avantages en termes d'apprentissage, compte tenu du coût de la vérification de son exactitude.

• Pour la reconstruction à grande échelle, à l'échelle d'une ville, plutôt que de se fier à un seul ajustement des faisceaux, envisagez des méthodes qui divisent le problème par région et intègrent hiérarchiquement (cette approche est également courante comme étape préliminaire à la vision stéréo multi-vues, abordée ci-dessous).

12. Résumé

L'ajustement des faisceaux est un problème de moindres carrés non linéaires qui minimise simultanément l'erreur de reprojection pour chaque caméra et chaque point 3D. Il est résolu itérativement par la méthode de Levenberg-Marquardt. L'astuce du complément de Schur, qui exploite la rareté des données dans la relation caméra-point d'observation, permet de résoudre cette optimisation dans un délai raisonnable, même à l'échelle de dizaines de milliers de points. Bien qu'elle partage un cadre mathématique avec l'optimisation par graphe de pose, le choix entre les deux dépend de la conservation explicite ou non des points 3D. Il s'agit d'une technologie fondamentale commune qui sous-tend la précision de la SfM et du SLAM.