Calibration par programmation linéaire et reconstruction spatio-temporelle à partir de réseaux d’images

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  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 . [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.

Les deux méthodes proposées dans ce manuscrit sont constituées des différentes étapes indiquées ci-dessous :

1. Notre point de départ est un ensemble de géométries épipolaires. Celles-ci sont calculées à l’aide d’une version du RANSAC 1.2.3 correspondant à l’état de l’art, le PROSAC [CM05], puis elles sont raffinées à l’aide d’une méthode basée sur le maximum de vraisemblance expliquée dans [PVGV+04]. Par l’intermédiaire du RANSAC, nous avons filtré les correspondances “outliers” et nous pouvons supposer que nous avons conservé des correspondances épipolaires, point-point, correctes. Enfin nous fusionnons ces correspondances épipolaires en correspondances à trois vues. En effet si nous avons une correspondance épipolaire entre i et j et une autre entre j et k, si les coordonnées sont identiques sur l’image j, alors nous les fusionnons en une correspondance pointpoint-point.

2. Nous regroupons les vues en triplets. Trois vues (i, j, k) sont considérées comme formant un triplet valide si (a) les géométries épipolaires entre i et j mais également entre j et k ont été calculées avec succès lors de l’étape précédente, et (b) il y a au moins quatre correspondances à trois vues, point-point-point, dans ces images. Afin de réduire le nombre d’arêtes épipolaires dans le graphe des caméras, certaines des géométries épipolaires estimées, sont ignorées, de telles sorte que pour un triplet donné, seulement deux matrices fondamentales sont supposées connues et fixées. L’avantage de cette stratégie est que nous n’avons pas besoin de forcer la cohérence entre les matrices fondamentales. A première vue on pourrait considérer cela comme une perte d’information. Ce n’est pas le cas car cette information est retrouvée en calculant par la suite les tenseurs trifocaux.

3. Nous définissons un graphe ayant pour noeuds les triplets de caméras valides. Nous avons donc deux matrices fondamentales valides pour chaque noeud. Deux noeuds sont connectés par une arête si ils ont en commun une matrice fondamentale. Nous montrons que pour chaque noeud il existe un vecteur de taille 4 γ, tel que les entrées des caméras associées au triplet sont fonctions affines de ce vecteur. Nous proposons une méthode qui permet de calculer ces 4 inconnues à partir de quatre correspondances point-point-point par programmation linéaire. Aussi nous calculons donc ces 4 inconnues par RANSAC, en éliminant ainsi les correspondances à trois vues “outliers”.. Ainsi nous obtenons un ensemble de correspondances à trois vues que nous considérons comme particulièrement fiable. D’autre part, les homographies permettant de relier deux noeuds adjacents ν et ν’ dans le graphe des triplets sont également fonctions affines de 4 des 8 paramètres inconnus correspondant aux deux vecteurs de taille 4 liés à ν et ν’.

4. Si le graphe des triplets est acyclique, l’estimation des γ faite à l’étape précédente, permet de retrouver directement l’ensemble des caméras avec existence et unicité. Dans le cas où, le graphe des triplets a un ou plusieurs cycles, chaque boucle mène à un ensemble de contraintes polynômiales par rapport aux inconnues γ. En partant des valeurs préalablement calculées pour les γ, nous linéarisons les contraintes de cyclicité par un procédé séquentiel. Pour linéariser les contraintes non linéaires . Ainsi nous résolvons de manière itérative des systèmes parcimonieux sous contraintes linéaires. En pratique, cette méthode converge rapidement, mais les contraintes de cyclicité ne sont que partiellement atteintes.

5. Dans le cas où les contraintes de cyclicité ne sont pas parfaitement atteintes, nous procédons à un répartition de l’erreur résiduelle de cyclicité par enregistrement d’homographies et estimation des matrices de caméras par programmation linéaire sous contraintes de norme.  Nous obtenons ainsi l’ensemble des caméras dans un même espace projectif.

6. En remplacement des étapes 4 et 5, nous proposons également une seconde approche.

Cette méthode est basée sur une minimisation alternée, qui pour toutes nos expériences, sans exception, nous a permis de converger exactement vers les contraintes de cyclicité. Cette méthode utilise le fait que, si l’on réduit une boucle, à une boucle faite de 4 tenseurs trifocaux choisis alternativement, alors les contraintes de cyclicité peuvent s’écrire comme un problème linéaire.  Cette méthode permet d’obtenir de très bons résultats et est intéressante pour appréhender les contraintes de cyclicité d’une manière différente, en les envisageant d’avantage comme étant des contraintes de cohérence.

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
Conclusion
Annexe

Télécharger le rapport complet