Le 14/12/2015 par bneveu :
Stage de Master 2 proposé à l'Ecole des Ponts - LIGM Equipe Imagine
Titre
Détection de plans dans un nuage de points 3D avec un algorithme complet d'exploration par arbre de recherche.
Contexte
La détection de formes est une tâche de base en traitement d'images et il existe des algorithmes randomisés comme RANSAC pour trouver dans un nuage de points 3D le plan (ou une autre forme comme un cylindre pu une sphère) qui maximise le nombre de points se trouvant à une distance inférieure à une distance donnée. Plusieurs extensions de RANSAC ont été réaliséq pour trouver plusieurs formes de manière gloutonne.
Nous proposons d'étudier une technique alternative nouvelle, basée sur une recherche arborescente complète dans l'espace des paramètres décrivant le plan, capable de trouver tous les plans comprenant Q points à une distance inférieure à une distance donnée. Quelques résultats préliminiares ont été obtenus sur des nuages de points artificiels, mais une validation de la méthode sur des scènes réelles reste à faire.
Objectifs
Un plan est décrit par un ensemble de paramètres, qui le définissent (par exemple vecteur normal et distance à l'origine).
L'algorithme déterminant ces plans effectuera une recherche arborescente dans cet espace de paramètres en utilisant une contraction de la boite courante par Q-intersection.
la Q-intersection détermine la boite dans l'espace des paramètres compatible avec au moins Q points du nuage.
Dans une première partie du stage, on étudiera les algorithmes de Q-intersection existants, les différentes paramétrisations d'un plan et on en sélectionnera quelques uns.
La tache principale consistera à adapter cette méthode à des scènes réelles, déterminer les limites de cette approche, d'étudier la sensibilité au bruit dans l'image et les problèmes de précision :
comment arrêter le découpage des boites pour éviter d'obtenir trop de solutions proches, comment regrouper les solutions contenant les mêmes points ...
On étudiera aussi comment régler les différents paramètres de l'algorithme
(le seuil Q, la tolérance dans les équations, le critère d'arrêt).
Toute l'implantation sera réalisée en C++, en utilisant la bibliothèque logicielle Ibex.
Profil
Connaissances en algorithmique, C++, optimisation combinatoire, quelques connaissances en traitement d'images utiles mais non obligatoires.
Références
G. Trombettoni, I. Araya, B. Neveu, G. Chabert
Inner Regions and Interval Linearizations for Global Optimization
Proc. of AAAI 2011, pages 99-104, San Francisco, CA, USA
C. Carbonnel, G. Trombettoni, P. Vismara, and G. Chabert.
Q-intersection algorithms for constrained-based robust parameter estimation.
Proc. of AAAI 2014.
A. Bethencourt and L. Jaulin
3D Reconstruction Using Interval Methods on the
Kinect Device Coupled with an IMU. Int. Journal of Advanced Robotic Systems, 10,2013.
L. Jaulin and S. Bazeille.
Image Shape Extraction using Interval Methods.
Proc.of the 16th IFAC Symposium on System, pages 378383, 2009
R. Schnabel, R. Wahl, and R. Klein,
Efficient ransac for point-cloud shape detection.
Computer Graphics Forum, 26(2) :214226, 2007.
G. Chabert and L. Jaulin.
Contractor Programming.
Artificial Intelligence,173 :10791100, 2009.
B. Neveu, M. de la Gorce, G. Trombettoni
Improving a Constraint Programming Approach for Parameter Estimation
ICTAI 2015, Nov 9-11, Vietri sul mare, Italy
Contact
Bertrand Neveu Bertrand.Neveu@enpc.fr 0164152175
