Reconstruction 3D et localisation simultanée de caméras mobiles

La robotique est un domaine scientifique et technologique dans lequel on cherche souvent à reproduire le fonctionnement humain de manière artificielle, à partir de capteurs, de calculateurs et d’actionneurs. Elle est très liée à la vision par ordinateur qui est le domaine précis où l’on analyse les images produites par le capteur caméra pour en extraire des informations importantes. On cherche alors à imiter le système naturel constitué de l’oeil (capteur) et du cerveau (analyse). On arrive déjà à faire mieux dans certaines applications : en métrologie par exemple (domaine quantitatif) où l’on sait mesurer des distances inférieures au millimètre alors qu’on est incapable de le faire à l’oeil nu. Pour d’autres applications (domaine qualitatif), de grands progrès sont encore à réaliser : par exemple en reconnaissance et détection d’objets

Avec la montée en puissance des ordinateurs et la démocratisation des capteurs numériques, la vision par ordinateur ne pouvait que connaître un très grand développement. Il y a une vingtaine d’années, il était impossible de charger une image entière d’un million de pixels dans la mémoire vive d’un ordinateur. Aujourd’hui, même les téléphones mobiles sont équipés d’appareils photos intégrés et sont capables de stocker et de traiter des dizaines d’images. Il s’est vendu un milliard de téléphones portables dans le monde en 2006, dont la moitié étaient équipés d’un appareil photo intégré. De nombreux autres produits intègrent aujourd’hui des caméras numériques (automobiles, ordinateurs de poche, baladeurs, etc …) et cela montre le gigantesque potentiel de diffusion des algorithmes développés dans ce domaine.

Localisation par vision 

Il y a deux manières de concevoir le problème de localisation à partir d’une caméra. La première consiste à considérer la localisation comme un problème global, à la manière d’un positionnement par GPS. Par exemple, si l’image qui provient du capteur est une prise de vue d’un monument, alors il est possible de reconnaître automatiquement de quel monument il s’agit (à partir d’une base de données), et de déterminer ainsi où l’on se trouve. Cela nécessite bien sûr de connaître tous les lieux où l’on peut se déplacer. La deuxième approche est plus locale. Elle consiste non pas à trouver une position absolue mais plutôt une position relative par rapport à une localisation connue. Par exemple, considérons qu’on s’est déplacé d’un point A connu vers un point B inconnu et qu’il n’est pas possible de déterminer la position en B par la méthode globale. On peut tout de même estimer la position B si l’on est capable d’estimer le mouvement réalisé par la caméra pour aller de A à B. C’est cette deuxième approche qui est exploitée dans ces travaux de thèse en calculant une reconstruction 3D.

Localisation et reconstruction 3D 

Le principe est le suivant : on considère une caméra qui se déplace dans un environnement inconnu et qui acquiert des images de cet environnement.

A partir des images, le but est de calculer conjointement la trajectoire de la caméra et la structure 3D de la scène filmée. En effet, les deux calculs sont très liés et si l’on dispose de l’une ou l’autre des informations, la deuxième est facilement calculable. De nombreux algorithmes ont été développés mais ils ne peuvent pas traiter des longues séquences vidéos pour deux principales raisons :
– le manque de précision dû à l’accumulation des erreurs
ou
– l’impossibilité de faire les calculs dans des temps raisonnables.

La caméra perspective

Le modèle sténopé

Les capteurs de vision fréquemment utilisés pour l’acquisition de séquences vidéos peuvent généralement être décrits par le modèle « sténopé » encore appelé « trou d’épingle » ou « perspectif ». Dès l’antiquité, on utilisait le principe du sténopé pour observer les éclipses solaires dans une chambre noire. Tous les rayons de lumière passent par un seul et même point : le centre optique ou centre de projection. l’image se forme sur le plan image (mur ou plaque photosensible) naturellement situé derrière le centre optique à une distance f de celui-ci. L’image obtenue sur ce plan est alors inversée par rapport à la scène .

Pour corriger ce problème, on place artificiellement le plan image devant le centre optique.

Les paramètres intrinsèques

Une caméra décrite par ce modèle est alors caractérisée par ses paramètres internes qui sont  :
– la distance focale f (distance orthogonale du centre optique au plan image).
– le point principal u = (u0, v0) qui est l’intersection de l’axe optique et du plan image (supposés orthogonaux).
– le rapport κ = dy/dx des dimensions verticale et horizontale des pixels du capteur photosensible.

Si on pose fx = f/dx, fy = f/dy et si dx est connu (fourni par le constructeur de la caméra ou fixé arbitrairement à 1), alors le couple de paramètres (f, κ) peut être remplacé par le couple (fx, fy) et les paramètres intrinsèques se ramènent à (fx, fy, u0, v0).

Les paramètres extrinsèques

Dans ce paragraphe, il convient de définir deux différents repères tridimensionnels : le repère du monde noté Rw qui est le repère global contenant la scène, et le repère lié à la caméra noté Rc. Le changement de repère Rw → Rc correspond à la position ou « pose » de la caméra dans le repère du monde au moment de la prise de vue. Cette pose est modélisée par les paramètres extrinsèques de la caméra. Ils peuvent être représentés par :
– un vecteur de translation t de taille 3×1 indiquant la position du centre optique de la caméra dans le repère du monde.
– une matrice de rotation R de taille 3 × 3 indiquant l’orientation de la caméra dans le même repère. Elle peut être déterminée à partir des angles d’Euler : α, β et γ.

Changement de repère monde/caméra

Un vecteur Vc dans le repère caméra s’écrit Vw = RVc + t dans le repère monde et à l’inverse, un vecteur Vw dans le repère monde s’écrit Vc = Rt (Vw − t) dans le repère caméra.

Paramètres de distorsion

Le modèle de projection perspective correspond à une approximation du modèle optique des lentilles minces. Cependant, les systèmes de vision actuels ne correspondent pas exactement à ce modèle, notamment si l’objectif utilisé est un objectif grand angle à courte focale. Dans ce cas, l’optique introduit des distorsions dans l’image et le modèle sténopé atteint ses limites. La distorsion se manifeste visuellement par des déformations dans l’image, et notamment les droites qui deviennent courbes. Pour pouvoir modéliser correctement la projection, il est indispensable de tenir compte de ces distorsions. Pour une caméra réelle, le rayon lumineux qui vient frapper le capteur au point p diffère du point psd qui serait excité par la même caméra sans l’effet de distorsion (sténopé parfait).

Modéliser la distorsion revient à déterminer la fonction qui à p = (x, y) associe psd = (xsd, ysd) (corrigé de la distorsion). La distorsion a une composante tangentielle et une composante radiale par rapport au point principal u. Afin de simplifier le modèle, on considère que la distorsion tangentielle est négligeable et on s’intéresse uniquement à la composante radiale de la distorsion.

Le problème de la reconstruction 3D 

Principe

La reconstruction 3D consiste à retrouver l’information tridimensionnelle des objets perdue lors de l’acquisition d’images, c’est-à-dire la projection de la scène sur un plan. En effet, une caméra se déplaçant dans un monde 3D collecte un ensemble d’images qui sont des données bidimensionnelles. Pourtant, à la fois la trajectoire de la caméra et le monde dans lequel elle évolue sont en 3D. Le processus de reconstruction consiste souvent à déterminer conjointement la structure de la scène et la position des caméras, uniquement à partir des images .

Selon le contexte, trois types de reconstruction peuvent être considérés, sans lien avec le modèle de caméra utilisé. La notion de reconstruction « projective » est utilisée lorsque les coordonnées des objets sont définies dans un repère projectif. La reconstruction est alors définie à une transformation projective près et ne contient pas d’information d’angle, de longueur, ou de parallélisme. De même, une reconstruction « affine »est définie à une transformation affine près et ne contient que des informations affines (rapport de longueurs et parallélisme). Enfin, le dernier type de reconstruction et celui qui nous intéresse particulièrement est la reconstruction « euclidienne ». Tous les éléments 3D sont référencés dans un repère euclidien, qui nous est plus familier et où les notions d’angle et de distance sont présentes. Dans le cas idéal, une reconstruction serait totale et permettrait de modéliser entièrement l’environnement 3D. Pour cela, il faudrait observer l’ensemble des points de l’espace. En effet, il est bien sûr possible de reconstruire uniquement les objets observés par la caméra, c’est-à-dire situés dans le champ de vue et sans subir d’occultation par d’autres objets. Une telle reconstruction totale est difficilement concevable. Par exemple, notre cerveau sait que lorsqu’on observe une maison, on se trouve devant un objet volumique en 3 dimensions. L’ordinateur équipé d’une caméra, lui ne verra par exemple qu’une façade complètement plane. Même s’il est envisageable d’utiliser l’information d’intensité lumineuse d’une seule image pour déterminer la forme des objets (on parle alors de « Shape from Shading » [106]), la vision tridimensionnelle n’est souvent possible que si l’on a deux points de vue différents d’une même scène. C’est probablement ce que fait le cerveau humain en combinant les informations provenant des deux yeux. On peut alors employer plusieurs caméras (stéréo vision, vision trinoculaire, etc) ou bien utiliser le mouvement d’une seule et même caméra. Dans ce cas, on parle de « structure à partir du mouvement » ou plus communément de SfM pour « Structure from Motion » en anglais. Pour un objet détecté dans une image, il faut alors être capable de dire si cet objet est visible dans une autre image, et quelle est sa nouvelle position dans cette image. Encore une fois, cette tâche est évidente pour le cerveau, mais très compliquée à réaliser avec un ordinateur. En effet, il nous est immédiat de voir si un objet vu par l’oeil gauche est le même qu’un objet vu par l’oeil droit. En vision par ordinateur, on parle de « recalage » ou « mise en correspondance » d’images et c’est un problème fondamental, objet de nombreux travaux. C’est l’étape de traitement d’image initiale pour la plupart des algorithmes de reconstruction. Une fois la mise en correspondance réalisée, on dispose de disparités 2D (positions différentes des mêmes objets dans les images) qui vont permettre d’accéder simultanément ou indépendamment au calcul du déplacement de la caméra (ego-motion estimation ou pose relative) et au calcul de la position 3D des objets (triangulation) – les deux calculs étant souvent liés. Dans cette section nous allons définir la notion de primitive et nous intéresser particulièrement à la primitive la plus simple qui est le point. Nous allons voir comment il est possible de détecter des points particuliers et les mettre en correspondances entre plusieurs images. Ensuite, nous pourrons formuler le problème de la reconstruction 3D d’un nuage de points à partir d’une séquence d’images.

Table des matières

Introduction
1 Principes et méthodes de base
1.1 La caméra perspective
1.1.1 Le modèle sténopé
1.1.2 Les paramètres intrinsèques
1.1.3 Les paramètres extrinsèques
1.1.4 Changement de repère monde/caméra
1.1.5 La projection perspective d’un point 3D
1.1.6 Paramètres de distorsion
1.1.7 Étalonnage des caméras
1.2 Le problème de la reconstruction 3D
1.2.1 Principe
1.2.2 Les primitives
1.2.3 Détection et mise en correspondance de points d’intérêt
1.2.4 Formulation du problème
1.3 Calculs de la géométrie 3D (méthodes directes)
1.3.1 La géométrie de deux images
1.3.2 Reconstruction 3D d’un nuage de points
1.3.3 Calcul de pose
1.4 Solutions optimales (méthodes itératives)
1.4.1 Moindres carrés non-linéaires
1.4.2 L’erreur de reprojection
1.4.3 Intersection – Résection – Ajustement de faisceaux
1.4.4 Méthodes robustes
1.5 Ajustement de faisceaux par minimisation non-linéaire
1.5.1 Introduction
1.5.2 Formulation
1.5.3 L’itération de Gauss-Newton
1.5.4 L’itération de descente de Gradient
1.5.5 L’algorithme de Levenberg-Marquardt
1.5.6 Mise en oeuvre de l’ajustement de faisceaux
1.5.7 L’algorithme « Dog Leg » de Powell
2 Systèmes de reconstruction 3D automatique existants
2.1 Les algorithmes de « SLAM »
2.2 Les algorithmes de « SfM »
2.2.1 Les algorithmes rapides sans ajustement de faisceaux
2.2.2 Les algorithmes avec ajustement de faisceaux global
2.2.3 Les algorithmes avec ajustement de faisceaux modifié
2.3 Discussion et positionnement
3 Reconstruction 3D incrémentale par ajustement de faisceaux local : cas d’une caméra perspective
3.1 Aperçu de l’approche
3.2 Mise en correspondance d’images : choix techniques
3.2.1 Détection de points d’intérêt
3.2.2 Appariements des points
3.2.3 Mise en correspondance de l’image courante avec la dernière image clef
3.3 Initialisation robuste avec trois vues
3.3.1 Choix du premier triplet d’images clef
3.3.2 Initialisation de la géométrie
3.4 Méthode de reconstruction 3D incrémentale
3.4.1 Calcul de la pose courante
3.4.2 Sélection des images clef et triangulation de points
3.5 Reconstruction 3D par ajustement de faisceaux local
3.5.1 Principe et mise en oeuvre
3.5.2 Complexité de calcul pour l’ajustement de faisceaux local et global
3.6 Résumé de l’algorithme
3.7 Résultats et performances
3.7.1 Comparaison avec l’ajustement de faisceaux global (méthode de reconstruction hiérarchique)
3.7.2 Comparaison avec la vérité terrain (GPS différentiel)
3.7.3 Temps de calcul
3.7.4 Longues séquences en milieu urbain
3.7.5 Influence du calibrage
3.7.6 Influence du sous-échantillonnage
3.8 Applications de la méthode de reconstruction 3D incrémentale
3.8.1 Odométrie visuelle temps-réel pour l’automobile en milieu urbain
3.8.2 Localisation d’un robot mobile ou « véhicule intelligent »
3.8.3 Localisation de véhicule pour le stationnement automatique
3.8.4 Calibrage des systèmes multi-caméras
4 Reconstruction 3D incrémentale par ajustement de faisceaux local : généralisation aux caméras génériques
4.1 Introduction aux caméras génériques
4.2 Le modèle de caméra générique
4.3 Raffiner la géométrie
4.3.1 Erreur générique
4.3.2 Choix de l’erreur angulaire
4.3.3 Comparaison Erreur angulaire/Erreur image pour unecaméra perspective
4.4 Initialisation générique
4.4.1 Les coordonnées de Plücker
4.4.2 Contrainte épipolaire généralisée (ou équation de Pless)
4.4.3 Résolution de l’équation de Pless
4.4.4 Initialisation robuste pour trois vues
4.4.5 Estimation de pose robuste
4.5 Résultats
4.5.1 Comparaison avec la vérité terrain (GPS différentiel)
4.5.2 Comparaison avec un ajustement de faisceaux global et spécifique
Conclusion

Lire le rapport complet