Une nouvelle approche de “structure from motion” à partir d’un graphe de triplets

Etat de l’art sur la structure à partir du mouvement

La calibration de caméras à partir d’une scène tridimensionnelle a toujours été un problème central en vision par ordinateur. Le succès de livres tels que [HZ03, FLP01] atteste de cet intérêt. Au cours de ces dernières années, de nombreuses méthodes de calibration ont été proposées. La plupart de ces méthodes supposent que les paramètres internes sont connus ou partiellement connus [SSS06, MP07, SSS08, FP09, BKP09, ASS+09, HTKP09, MLD+09] ou traitent une séquence ordonnée de caméras [FZ98, AS01, PVGV+04, SPM04]. Cependant, dans bien des cas, les paramètres internes des caméras ne sont pas connus, ou le sont mais de manière très imprécise. L’absence d’ordre dans un ensemble de caméras est également très courant, lorsque l’on traite, par exemple, des images à partir du web. Dans ce manuscrit, nous cherchons à calibrer un réseau de caméras non ordonnées, l’objectif principal étant d’obtenir une reconstruction projective de caméras suffisamment précise. Généralement, ceci est effectué par factorisation de la matrice des mesures [TK92, ST96], qui peut avoir des données manquantes [Jac97, MP05, TBT+07] en raison d’occlusions. Dans [TBT+07] la méthode de factorisation proposée permet de traiter des séquences avec 95% de données manquantes. Cette méthode se révèle très efficace comparativement aux autres méthodes similaires, et permet d’introduire facilement des contraintes sur les caméras. Ces contraintes peuvent être que les caméras sont identiques, varient de façon lisse le long de la séquence, ou encore que la configuration de certains points 3D est connue. La méthode proposée dans ce manuscrit est très différente et est basée sur la notion de graphe de tenseurs trifocaux plutôt que sur la factorisation. Les expériences faites sur des jeux de données réelles montrent que notre approche est très compétitive et qu’elle fournit une très bonne initialisation pour l’algorithme de “Bundle adjustment” (BA) [TMHF99],  L’utilisation d’une fusion de triplets pour obtenir une séquence de caméras a déjà été proposé par [FZ98] et [QL02]. Dans [FZ98] les triplets sont fusionnés en estimant les meilleures transformations projectives possibles minimisant une erreur géométrique. Cette erreur étant non linéaire la minimisation est susceptible de rester bloquée dans des minima locaux. D’autre par les tenseurs étant incohérents deux à deux, ce problème n’a pas de solution exacte. Une méthode pour forcer les contraintes de cyclicité, par un ajustement des faisceaux global sur toute la séquence, est également proposée dans ce papier. Dans [QL02] une méthode très similaire de fusion de triplets est également proposé.

Cette fois encore les contraintes de cyclicité sont imposées par un ajustement des faisceaux, mais de façon quasi-dense et non pas avec un ensemble parcimonieux de correspondances. On obtient grâce à cette mise en correspondances quasi-dense une bonne initialisation pour des algorithmes de stéréovision. Il est à noter que cet ajustement des faisceaux est également susceptible de rester bloqué dans des minima locaux et il n’y a aucune garantie d’atteindre les contraintes de cyclicité. Dans ce manuscrit nous proposons une fusion de triplets rendus parfaitement cohérents, c’est-à-dire que les transformations projectives entre deux tenseurs sont obtenues de façon exacte et sont connues sous forme annalytique. Cette fusion de triplets bien posée permet ultérieurement de formuler les contraintes de cyclicité comme étant la solution d’un problème polynomial. En abordant ces contraintes de cyclicité de façon différente nous remarquons que nous pouvons résoudre ces contraintes par la simple résolution de problèmes d’algèbre linéaire.

Même dans le cas de caméras calibrées, la plupart des méthodes citées plus haut sont basées sur un graphe de caméras (dans lequel les arêtes sont les géométries épipolaires 1.3.1) qui est rendu acyclique en retirant certaines arêtes. En revanche, certaines études récentes basées sur la modélisation de villes à partir de voitures ou de vues aériennes, mettent en avant l’intérêt d’utiliser les contraintes de boucles. Le fait de considérer les boucles dans un graphe permet de réduire la dérive des caméras due à l’accumulation d’erreurs lorsque l’on calcule les caméras de façon séquentielle (cf. Fig. 2.1). [KZIS08] fusionne des reconstructions partielles, [SFP10] contraint des rotations cohérentes avec les boucles et un mouvement plan. Adaptées à leurs données d’entrées spécifiques, ces méthodes reposent sur une régularisation de trajectoire ou une mise en correspondance dense [CCVG06, TPD08]. [THP09] est une exception notable, où les contraintes de boucles sont ajoutées à l’algorithme de calibration (“structure from motion”) sparse, en tenant compte cependant, d’une séquence d’image ordonnées et de paramètres internes connus.

Une première solution : programmation linéaire séquentielle

Linéarisation de la contrainte de cyclicité

Plutôt que de résoudre le problème d’optimisation obtenu en combinant les contraintes de boucle polynomiales, nous proposons de le remplacer par un problème linéaire. Pour linéariser les contraintes nous nous basons sur une méthode de type Gauss-Newton vue en Annexe B.2.1. Nous commençons avec une estimation initiale de Γ, e.g., en résolvant le problème sans contraintes (convexe) pour un q ≥ 1. Dans notre implémentation nous calculons séparément les 4 inconnues de chaque triplet avec une méthode basée sur un RANSAC pour garantir la robustesse par rapport à d’éventuelles fausses correspondances trifocales. Nous utilisons aussi q = 2 dans notre programme.

Le jeu de données Dinosaur est composé de 36 images. Le jeu de données Detenice Fountain est composé de 34 images. Le jeu de données Calvary est composé de 52 images.  pour les trois jeux de données, sans optimisation sous contraintes, les droites épipolaires dans la dernière image, correspondant à un point cliqué dans l’avant dernière image, sont très précises. ceci est naturel puisque notre méthode calcule les caméras en adéquation parfaite avec les matrices fondamentales calculées précédemment. En revanche on note que les droites épipolaires dans la première image, correspondant à un point cliqué dans l’avant dernière image, sont peu précises lorsque les contraintes de cyclicité ne sont pas utilisées. Ceci est particulièrement vrai pour le Dinosaur, et même encore plus pour le Calvary.

Puisqu’il n’y a pas de vérité terrain disponible pour les jeux de données Detenice Fountain et Calvary, nous utilisons le résultat du BA pour évaluer l’impact des contraintes de cyclicité sur la qualité d’estimation des caméras.  nous remarquons que les positions des caméras estimées sans imposer les contraintes de cyclicité sont très différentes de celles obtenues après BA. Plus particulièrement, la caméra 33 est devant la caméra 00 , alors que suivant l’estimation fournie par le BA elle est légèrement derrière la caméra 00 . En revanche, si l’optimisation sous contraintes est utilisée, les positions relatives des caméras 33 et 00 sont presque les mêmes avant et après BA.

Avec l’optimisation sous contraintes, la caméra 51 est proche de la caméra 00 . Comme on le voit sur les imagettes en haut, la première et la dernière photo sont capturées depuis le même point de vue ou presque. Cette configuration est confirmée par le BA. Afin d’avoir une mesure quantitative de l’amélioration obtenue en forçant les contraintes de cyclicité, nous effectuons un BA avec des estimateurs sans contraintes et avec des estimateurs contraints pour initialiser le BA. La l’erreur de reprojection pixellique “root mean square” sur l’ensemble de la séquence est 0.87 après le BA initialisé avec des estimateurs contraints, alors qu’elle est de 1.61 après le BA initialisé avec des estimateurs non contraints.

Répartition de l’erreur résiduelle de cyclicité par homographies

Etant donné un graphe de Tenseurs Trifocaux, Gtriplet, chaque noeud de ce graphe sera noté v1, v2, . . . , vn. A l’étape précédente nous avons déterminé les paramètres γ1 , . . . , γn , tels que γi caractérise le tenseur trifocal représenté dans le graphe par vi . Une stratégie naïve pour estimer les matrices de caméras est de fixer les 3 caméras d’un triplet v et de retrouver les autres caméras dans l’espace projectif du tenseur v en appliquant successivement des homographies Hγ,γ0 aux matrices des caméras reconstruites à partir des équations (C.30). Cependant, dans la plupart des cas, le vecteur Γ calculé par programmation linéaire séquentielle, comme décrit dans la section précédente, ne satisfait les contraintes de cyclicité qu’à une erreur résiduelle près. Ainsi, la méthode naïve proposée précédemment a le désavantage d’accumuler les erreurs et de dévier légèrement pour un grand nombre d’homographies appliquées. Afin d’éviter cela et de répartir l’erreur résiduelle de cyclicité uniformément parmi les caméras, nous proposons une méthode basée sur l’enregistrement d’homographies par SVD. Le point d’entrée pour cette méthode est un vecteur Γ pour lequel les contraintes de boucle sont satisfaites à une petite erreur près.

Table des matières

Introduction
I “structure from motion” d’un réseau de caméras par programmation linéaire
1 La problématique de la structure à partir du mouvement
1.1 Introduction
1.2 Outils fondamentaux pour la structure à partir du mouvement
1.2.1 Géométrie d’une caméra
1.2.2 Rectification métrique
1.2.3 Algorithme RANdom SAmple Consensus
1.2.4 Triangulation et erreur de reprojection
1.2.5 Ajustement des faisceaux
1.3 Concepts fondamentaux de géométrie à plusieurs images
1.3.1 Géométrie à deux images
1.3.2 Géométrie à trois images
2 Une nouvelle approche de “structure from motion” à partir d’un graphe de triplets
2.1 Etat de l’art sur la structure à partir du mouvement
2.2 Objectif : un graphe de triplets cohérents
2.3 Concepts fondamentaux utilisés
2.3.1 Formulation réduite du tenseur trifocal
2.3.2 Graphe de triplets de caméras
2.4 Une première solution : programmation linéaire séquentielle
2.4.1 Linéarisation de la contrainte de cyclicité
2.4.2 Prendre en compte l’hétéroscédasticité
2.4.3 Répartition de l’erreur résiduelle de cyclicité par homographies
2.5 Une seconde solution : minimisation linéaire alternée
2.5.1 Concepts fondamentaux utilisés
2.5.2 Algorithme de minimisation alternée
2.6 Résultats Expérimentaux
2.6.1 Implémentation
2.6.2 Jeux de données
2.6.3 Mesures de qualité
2.6.4 Résultats
2.7 Pour aller plus loin
2.7.1 Une formulation relaxée du tenseur trifocal
2.7.2 Raffiner les matrices fondamentales
2.7.3 Vers une formulation symétrique du tenseur trifocal
II Reconstruction spatio-temporelle
3 Etat de l’art de la reconstruction spatio-temporelle
3.1 Forme 3D précise
3.2 Estimation précise du mouvement 3D
3.3 Estimation couplée de la forme 3D et du mouvement 3D
4 Approche proposée
4.1 Discrétiser puis optimiser
4.2 Représentation par maillage animé
4.3 Reconstruction par minimisation d’une énergie
4.3.1 Formulation de l’énergie
4.3.2 Calcul du gradient
4.4 Résultats
4.4.1 Implémentation
4.4.2 Résultats expérimentaux
4.5 Pour aller plus loin
4.5.1 Maillage 4D à partir d’une optimisation globale
4.5.2 Mise en correspondance de maillages
A Descripteurs SIFT
A.1 Étude de détecteurs de points d’intérêts
A.1.1 Détecteur Laplacien
A.1.2 Détecteur DOG
A.2 Étude des descripteurs SIFT
A.2.1 Descripteur SIFT et histogramme de gradient
A.2.2 Expériences
B Optimisation
B.1 Solution aux moindres carrés d’équations linéaires
B.1.1 Décomposition en valeurs singulières
B.1.2 Solution aux moindres carrés d’équations linéaires homogènes
B.1.3 Solution aux moindres carrés d’équations linéaires non homogènes
B.1.4 Minimisation sous contraintes
B.2 Méthodes itératives
B.2.1 Itérations de Gauss-Newton
B.2.2 Descente de gradient
B.2.3 Itérations de Levenberg-Marquardt
B.3 Optimisation discrète : Les Graph-cut
C Preuves spécifiques à nos méthodes de calibration linéaire
C.1 Preuve de la proposition 14
C.2 Preuves des équations (2.4) et (2.5)
C.3 Preuve de la proposition 15
C.4 Preuve de la proposition 17
C.5 Preuve de la proposition 16
C.6 Preuve de la proposition 18
D Transformation de maillages et Applications
D.1 Introduction à la Triangulation de Delaunay
D.1.1 Enveloppe convexe, Polytopes, Simplexes, et Complexes
D.1.2 Diagramme de Voronoi
D.1.3 Triangulation de Delaunay
D.2 Une application à la transformation de maillage
D.3 Une application à la stéréovision spatio-temporelle
D.3.1 Génération d’un nuage de points 4D, triangulation de Delaunay 4D
D.3.2 Extraction de l’hyper-surface 4D
Conclusion
Publications
Bibliographie

Lire le rapport complet