Introduction à la reconstruction 3D à partir du mouvement — Reconstituer simultanément la 3D et les positions de la caméra à partir d'un ensemble de photos non ordonnées

Rassemblez des centaines de photos prises par des inconnus du même monument dans un lieu touristique, et reconstituez un modèle 3D de ce bâtiment ainsi que chaque point de prise de vue : c’est le principe de la reconstruction 3D par mouvement (SfM). À partir d’un ensemble d’images dont l’ordre de prise de vue, les positions relatives des caméras et même l’objectif utilisé sont inconnus à l’avance, cette technique reconstitue un nuage de points 3D géométriquement cohérent et les poses des caméras. Alors que le SLAM visuel et la vidéo (VO/VIO) suivent la position « actuelle » d’un robot ou d’une caméra en temps réel, la SfM fonctionne principalement hors ligne, privilégiant la précision pour reconstituer une scène complète. Cet article explore la structure interne de la SfM en partant de ses fondements, en s’appuyant sur cette distinction.

0. Résumé en 30 secondes

• La reconstruction 3D par la méthode SfM (Structure-Factory Modeling) est un processus permettant de reconstruire simultanément, à partir de nombreuses images, le nuage de points 3D épars d'une scène ainsi que les paramètres intrinsèques et extrinsèques de chaque caméra, grâce à la mise en correspondance de points caractéristiques et à la vérification géométrique.

• Il existe deux grandes stratégies de reconstruction : la SfM incrémentale, qui ajoute les caméras une à une, et la SfM globale, qui détermine d'abord la pose relative de chaque paire de caméras, puis calcule les poses globales en une seule fois.

• La SfM incrémentale est robuste, mais, étant séquentielle, elle est sujette à la dérive (accumulation d'erreurs). La SfM globale calcule tout en une seule fois et résiste donc à la dérive, mais est moins performante face à des poses relatives comportant de nombreuses valeurs aberrantes.

• Les points 3D et les poses des caméras obtenus par triangulation ne sont, pris individuellement, que des estimations approximatives affectées par le bruit de l'image. La minimisation simultanée de l'erreur de reprojection par Bundle Adjustment détermine en définitive la précision de la SfM.

• La SfM et le Visual-SLAM partagent la même géométrie sous-jacente, mais leur philosophie de conception diffère : la SfM est un traitement par lots hors ligne qui privilégie la précision et l'exhaustivité, tandis que le SLAM est un traitement en ligne et en temps réel qui privilégie l'immédiateté et la continuité.

1. Quelles sont les entrées et les sorties de la SfM ?

Les entrées sont un ensemble d'images \{I_1,\dots,I_N\} dont l'ordre de prise de vue et les positions relatives sont inconnus. Chaque image peut même avoir été prise avec un appareil photo différent, un objectif différent et à un moment différent. Le résultat comprend trois éléments :

• La pose de la caméra de chaque image i (paramètres intrinsèques et extrinsèques)

• Un ensemble de points 3D dans la scène \{\mathbf{X}_j\} (généralement un nuage de points épars correspondant aux points caractéristiques)

• La correspondance (trajectoire) entre les images ayant observé chaque point 3D

Alors que le guide d'étalonnage des caméras (Camera Calibration Primer) permet de récupérer les paramètres intrinsèques d'une seule caméra à partir d'une mire d'étalonnage fixe, la reconstruction 3D par la méthode SfM (Structure-Frame-Modèle) constitue un problème inverse plus vaste : la récupération simultanée des paramètres intrinsèques et extrinsèques de nombreuses caméras non étalonnées ou partiellement étalonnées, ainsi que de la structure de la scène, uniquement à partir des contraintes géométriques entre les points correspondants. Si les métadonnées EXIF incluent une distance focale, celle-ci est utilisée comme valeur initiale, mais la précision finale dépend des contraintes géométriques issues des images elles-mêmes.

Diagram 1 · Use the button to switch views

Dans un visualiseur de résultats, vérifiez d'abord si les caméras se regroupent dans une région anormalement petite, si le nuage de points se divise ou se dédouble, et si des images n'ont pas pu être enregistrées. Une apparence de bâtiment à elle seule ne démontre pas la précision. Évaluez l'erreur de reprojection, la longueur de la trajectoire et le nombre d'images enregistrées ; lorsqu'une longueur mesurée ou des données GNSS sont disponibles, comparez également avec cette échelle externe. Monoculaire La méthode SfM utilise une échelle globale arbitraire ; par conséquent, une distance affichée par le visualiseur de nuage de points n'est pas automatiquement exprimée en mètres.

2. Le pipeline de base

Les étapes précédentes — extraction de caractéristiques, appariement et vérification géométrique — correspondent exactement aux techniques élémentaires décrites dans le guide d'introduction à la détection de caractéristiques et le guide d'introduction à la géométrie épipolaire. Les choix de conception spécifiques à la méthode SfM interviennent après la détermination de chaque relation entre paires d'images : comment assembler chaque image et chaque point dans un système de coordonnées cohérent et sans contradictions ? C'est là que divergent les deux stratégies SfM incrémentale et SfM globale.

3. SfM incrémental : Ajout progressif des caméras

Le SfM incrémental commence par la sélection d'une paire d'images initiale présentant une parallaxe et des correspondances suffisantes, puis par la construction de la première reconstruction à deux vues en estimant la matrice essentielle/fondamentale à partir de la géométrie épipolaire. Le processus se répète ensuite :

1. Sélection d'une nouvelle image possédant déjà des correspondances 2D avec des points 3D enregistrés, et détermination de sa pose via PnP.

2. Triangulation des points non encore reconstruits en 3D, à partir des correspondances entre la nouvelle image et les images existantes.

3. Affinement de la pose et de la structure par ajustement de faisceaux local ou global toutes les X images.

4. Retour à l'étape 1 jusqu'à ce que toutes les images aient été traitées ou qu'il ne soit plus possible d'en ajouter.

Cette approche, largement utilisée depuis l'article de Snavely et al. sur le tourisme photographique (2006), est également adoptée par le pipeline standard de COLMAP sous le nom d'Incremental SfM. Comme elle n'augmente qu'un petit nombre d'inconnues à la fois, de manière séquentielle, il s'agit d'une implémentation robuste, et il est facile de détecter et d'exclure une paire d'images défectueuse. En revanche, comme les poses sont empilées image par image, les petites erreurs initiales se propagent aux images suivantes, et les jeux de données contenant de grandes boucles (un groupe d'images revisitant le même lieu) ont tendance à accumuler une dérive. L'ajustement périodique des faisceaux, associé à une détection de revisite équivalente à la fermeture de boucle, est essentiel pour maîtriser cette erreur accumulée.

4. SfM global : Résolution simultanée de toutes les relations par paires

Le SfM global n'enregistre pas les images séquentiellement ; il détermine d'abord la pose relative (R_{ij},\mathbf{t}_{ij}/\|\mathbf{t}_{ij}\|) pour chaque paire d'images (ou un sous-ensemble sélectionné). Il estime ensuite conjointement le graphe complet en deux étapes.

Moyenne des rotations détermine un ensemble globalement le moins incohérent de rotations de caméra \{R_i\} à partir de l'ensemble des rotations relatives par paires R_{ij}. Une métrique d'erreur couramment utilisée repose sur l'application logarithmique du groupe de Lie SO(3) :

\rho est une fonction de perte robuste, qui atténue l'influence des poses relatives erronées agissant comme des valeurs aberrantes.

Une fois les rotations fixées, le moyennage des translations détermine les positions de la caméra \{\mathbf{t}_i\} à partir de l'ensemble des directions de translation relative \mathbf{t}_{ij}. Puisqu'une translation relative monoculaire ne donne qu'une direction (voir l'ambiguïté d'échelle abordée dans l'introduction à la géométrie épipolaire), il est nécessaire de résoudre un problème de configuration cohérente à partir de nombreuses contraintes directionnelles par paires. Des approches comme 1DSfM, qui inclut l'élimination des valeurs aberrantes, ont été proposées à cet effet.

Comme la méthode SfM globale utilise simultanément les informations de chaque image, elle est, en principe, moins sujette à la dérive séquentielle que la méthode SfM incrémentale, et sa parallélisation est également plus aisée. Cependant, si des valeurs aberrantes sont intégrées aux poses relatives individuelles, la solution globale est faussée, à moins qu'elles ne soient détectées et exclues lors du moyennage. Les travaux de Moulon et al. (ICCV 2013) constituent un exemple représentatif d'amélioration significative de la praticité de la reconstruction 3D globale (SfM), grâce à la combinaison d'un moyennage robuste des rotations et d'une estimation de la direction de translation à l'aide du tenseur trifocal.

Exemples représentatifs : Bundler, COLMAP (par défaut), VisualSFM ; openMVG (pipeline SfM global), Theia.

En pratique, plutôt que de considérer les deux approches comme strictement exclusives, des conceptions hybrides sont également étudiées : la construction d’une pose globale approximative avec Global SfM, puis son affinement progressif, ou l’utilisation exclusive des paires à haute confiance de manière globale, les autres étant ajoutées progressivement.

5. Triangulation et gestion des pistes

Une fois les poses déterminées pour un groupe d’images, la triangulation des points correspondants pour obtenir des points 3D est une extension de l’opération géométrique de base à deux vues. La spécificité du SfM réside dans la gestion de la correspondance, appelée « piste », lorsqu’un même point physique est observé sur trois images ou plus.

• Étant donné que la mise en correspondance des caractéristiques s'effectue par paires, les correspondances entre les images A et B, et entre B et C, devraient idéalement impliquer également une correspondance entre A et C. Cependant, en pratique, cela n'est pas toujours le cas compte tenu des distances réelles entre les descripteurs. Un contrôle de cohérence trifocal garantit la qualité des trajectoires.

• Plus une trajectoire contient d'observations, plus la triangulation est stable. Toutefois, une trajectoire composée uniquement d'images présentant une faible parallaxe entre elles aboutit toujours à une profondeur instable.

• Une seule correspondance erronée au sein d'une trajectoire ne se contente pas de déformer la position 3D du point concerné ; elle affecte également les résidus de l'ajustement de faisceau en aval. Une vérification de type RANSAC pour chaque trajectoire, ainsi que le rejet des trajectoires présentant une erreur de reprojection importante, sont tous deux nécessaires.

6. Transition vers l'ajustement de faisceau

La pose et la structure obtenues par triangulation linéaire ou par PnP séquentiel ne sont, au mieux, que des valeurs initiales. Minimiser simultanément l'erreur de reprojection sur toutes les images —

— est l'ajustement de faisceaux, et c'est ce qui détermine en fin de compte la précision finale de la reconstruction 3D par image (SfM). La raison pour laquelle cette optimisation présente une structure creuse, et pourquoi le complément de Schur la rend résoluble même à grande échelle, sont des questions de calcul abordées en détail dans le guide d'introduction à l'ajustement de faisceaux. Il est important de noter ici la différence dans son utilisation : la SfM incrémentale effectue un ajustement de faisceaux local toutes les quelques images ajoutées, tandis que la SfM globale effectue un ajustement de faisceaux complet une fois que toutes les poses globales sont établies.

7. Différences et points communs avec Visual-SLAM

SfM et Visual-SLAM partagent les mêmes outils mathématiques : la mise en correspondance de caractéristiques, la géométrie épipolaire, le placement et le regroupement (PnP) et l’ajustement de faisceaux. La différence réside dans leurs objectifs et leurs contraintes.

Implémentations représentatives | COLMAP, openMVG, Bundler | Famille ORB-SLAM, famille VINS |

En pratique, il est courant d'utiliser une carte 3D haute précision construite par SfM comme carte initiale ou référence d'échelle pour SLAM, ou encore de post-traiter hors ligne la trajectoire des images clés de SLAM avec SfM pour améliorer la précision. Ces deux technologies ne sont pas concurrentes ; elles se complètent sur l'axe temporel hors ligne/en ligne.

8. Implémentations représentatives

• COLMAP : centrée sur le SfM incrémental, cette implémentation est actuellement la plus citée en recherche et en production. Elle fournit un pipeline cohérent, de l'extraction de caractéristiques à la reconstruction, en passant par la mise en correspondance, la vérification géométrique et l'ajustement de faisceaux (ou « bundle adjustment ») et la stéréovision multi-vues (ou « multi-view stereo »).

• openMVG (Open Multiple View Geometry) : une bibliothèque implémentant des pipelines SfM incrémentaux et globaux. Elle est souvent associée à openMVS pour la reconstruction dense.

• Bundler : l’implémentation SfM incrémentale pionnière qui a rendu publics les résultats de Photo Tourism et qui a servi de référence pour de nombreux travaux ultérieurs.

• Meshroom (AliceVision) : un outil de photogrammétrie open source doté d’une interface graphique qui gère l’ensemble du processus, de la numérisation SfM à la texturation, en passant par la numérisation MVS, en une seule passe.

Lors du choix d’une bibliothèque, le critère « plus récent signifie plus précis » n’est pas pertinent. Il convient plutôt de se baser sur le nombre d’images traitées, les ressources GPU/CPU, la fiabilité des données EXIF de focale, la stratégie de correspondance (exhaustive, séquentielle ou arborescente) et la nécessité d’un pipeline unique et cohérent, de la numérisation MVS à la génération de textures.

9. Conditions difficiles et cas d'échec fréquents

• Scènes pauvres en textures ou très répétitives : les murs uniformes, les surfaces carrelées et les rangées de cultures dans un champ ne donnent aucune correspondance ou produisent de fréquentes incohérences.

• Séries d'images à parallaxe extrêmement faible : les photos d'une scène éloignée prises avec un téléobjectif rendent la triangulation instable, entraînant d'importantes erreurs de profondeur.

• Objets en mouvement et variations d'éclairage : les séries de photos de sites touristiques mêlent personnes, véhicules et variations saisonnières ou horaires, introduisant des correspondances qui contreviennent à l'hypothèse de scène statique.

• Groupes d'images isolés : si les prises de vue se divisent en deux groupes sans champ de vision commun, la méthode SfM ne peut pas les unifier dans un système de coordonnées cohérent et la reconstruction se fragmente en plusieurs morceaux disjoints.

• Scènes symétriques : les façades de bâtiments symétriques, par exemple, peuvent converger vers une solution symétrique géométriquement cohérente mais physiquement incorrecte.

10. Choix pratiques

• Si la prise de vue est entièrement ordonnée (vidéo ou images continues d'un robot), la sélection de la paire initiale pour Incremental SfM est simplifiée et le pipeline par défaut de COLMAP est souvent suffisant.

• Pour les collections d'images à grande échelle, comme les photos touristiques sur Internet, où l'ordre de prise de vue et le chevauchement sont inconnus, la scalabilité de Global SfM est généralement un avantage.

• Pour les applications exigeant des performances en temps réel (robots, RA, automobile), privilégiez Visual-SLAM ou VIO à SfM. Le principal domaine d'application de SfM est la reconstruction hors ligne de haute précision.

• Si vous avez besoin d'une forme 3D dense (un maillage ou un modèle texturé), partez du nuage de points épars et de la pose de SfM, puis passez à la Stéréo Multi-Vues.

11. Résumé

La reconstruction 3D à partir du mouvement (SfM) est une technologie qui permet de reconstruire simultanément les poses de la caméra et la structure 3D, par appariement de caractéristiques et vérification géométrique, à partir d'un ensemble non ordonné d'images, en utilisant soit la stratégie SfM incrémentale, soit la stratégie SfM globale. La stratégie incrémentale est robuste mais sujette à la dérive, tandis que la stratégie globale y résiste mais est sensible aux valeurs aberrantes — un compromis symétrique. Quelle que soit la stratégie, la précision finale est assurée par l'ajustement de faisceaux, qui se connecte directement à Visual-SLAM, sa technologie sœur opérant sur un axe temporel différent, et à la stéréovision multi-vues, une technologie de reconstruction dense.