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 dans ce stage 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.
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 ...
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.
Contact
Bertrand Neveu Bertrand.Neveu@enpc.fr 0164152175
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 378–383, 2009
R. Schnabel, R. Wahl, and R. Klein,
Efficient ransac for point-cloud shape detection.
Computer Graphics Forum, 26(2) :214–226, 2007.
G. Chabert and L. Jaulin.
Contractor Programming.
Artificial Intelligence,173 :1079–1100, 2009.