Wikipédia

Iterative Closest Point

Page d’aide sur l’homonymie

Pour les articles homonymes, voir ICP.

L'Iterative Closest Point (ICP)[1],[2] est un algorithme utilisé dans le but de mettre en correspondance deux jeux de données, le plus souvent sous la forme de nuages de points ou maillages correspondant à deux vues partielles d'un même objet. Une vue étant constituée d'un ensemble de points (reliés ou non par des arêtes), l'objectif est de minimiser itérativement la distance entre ces points. Les nombreuses évolutions qui ont été apportées à l'algorithme, et notamment l'abandon du critère d'appairage des données basé sur la distance pure, lui valent parfois le nom de Iterative Corresponding Point[3].

Illustration de l'idée derrière l'algorithme itératif du point le plus proche

L'ICP est utilisé dans de très nombreux domaines nécessitant la reconstruction d'objets 3D à partir de vues partielles : vision par ordinateur, robotique ou encore rétro-conception.

Principe modifier

L'algorithme de base est conceptuellement simple : à partir de deux nuages de points, ce dernier va itérativement générer des paires de points correspondants, calculer la transformation optimale (composée d'une rotation et d'une translation) minimisant un critère de distance entre ces points correspondants puis appliquer cette transformation. Le terme source s désigne généralement le nuage de point recalé à chaque itération (mobile) et le terme destination d désigne généralement le nuage de point "de référence" (fixe). L'algorithme fournit finalement la transformation "optimale" permettant de recaler s sur d. Cette transformation est obtenue à la fin d'un nombre initialement fixé d'itérations ou bien d'après un critère sur la convergence de l'algorithme (par exemple une variation d'erreur entre deux itérations passant sous un seuil fixé à l'avance).

L'algorithme ICP a fait l'objet de nombreuses variantes depuis sa publication[3],[4], dans le but d'en améliorer l'efficacité ou de l'adapter à un usage particulier. Une différence notable entre les deux articles considérés comme à l'origine de l'algorithme[1],[2] concerne par exemple le critère de distance à minimiser : les auteurs Besl et McKay proposent de minimiser la somme des distances quadratiques entre les points en correspondance (critère "point-point") alors que les auteurs Chen et Medioni proposent de minimiser la somme des distances quadratiques entre les points de s et les plans consistant des points de d et des vecteurs normaux n associées (critère "point-plan"). Une variante notable consiste également en l'ajout d'un terme de déformation[5] (ici localement affine) permettant le recalage non-rigide des données.

Étapes de l'algorithme modifier

Trois phases principales sont généralement distinguées lors du fonctionnement de l'algorithme : la recherche de correspondances entre les données, l'estimation de la transformation optimale visant à minimiser un critère de distance et l'application de cette transformation. Il est néanmoins possible de faire apparaître un certain nombre d'étapes supplémentaires afin de pouvoir classifier les différentes variantes de l'algorithme ICP.

Les étapes les plus communément rencontrées[3],[4] sont :

  1. La sélection des points dans les nuages de départ (utilisation de toutes les données disponibles, sous-échantillonnage uniforme[6] ou aléatoire[7], etc.) ;
  2. La mise en correspondance ou génération de paires de points (critère de plus proche voisin[1], "normal shooting"[2], etc.) ;
  3. La pondération des paires de points (poids constants ou pondérations selon des critères de distance[8], compatibilité des normales[8], couleurs[8], etc.) ;
  4. Le rejet de certaines paires de points (% donné des "pires" paires[9], points sur les bords dans le cas d'un maillage[6], etc.) ;
  5. L'assignation d'un critère de distance à minimiser (critère "point-point"[1], "point-plan"[2], "point-rayon"[10], etc.) ;
  6. La minimisation de ce critère de distance (dépendamment du problème initial : SVD[11] ou quaternions[12] pour un critère "point-point" et forme linéarisée[13] pour un critère "point-plan" par exemple).

Convergence modifier

La preuve théorique de la convergence de l'algorithme ICP - c'est-à-dire sa capacité à converger de façon monotone vers un minimum local de la fonction coût quadratique moyenne - a été apportée par Besl et McKay[1]. Cette preuve de convergence s'appuie sur l'hypothèse que le nombre de points en correspondance est constant. Cette hypothèse est néanmoins difficilement vérifiable dans la pratique, la mise en correspondance des points étant un problème relativement délicat.

Une autre difficulté réside dans le caractère local de la solution ; La transformation obtenue à l'issue de l'algorithme est dépendante de l'alignement initial des deux jeux de données. Une estimation grossière de la transformation entre les vues est souvent nécessaire à la bonne convergence de l'algorithme[3]. Cette estimation peut être réalisée de manière manuelle ou par le biais d'autres algorithmes[14],[15],[16]. Une autre méthode notable de recherche d'un minimum global de l'algorithme ICP consiste en l'utilisation d'un algorithme de séparation et évaluation[17].

Implémentations modifier

Du fait de la variété de ses utilisations, il existe de nombreuses implémentations de l'algorithme ICP. Plusieurs exemples sont listés ci-dessous :

  • Meshlab est un logiciel libre de manipulation de nuages de points et de maillages qui possède une implémentation de l'algorithme ICP ;
  • CloudCompare est un logiciel libre de manipulation de nuages de points et de maillages qui possède une implémentation de l'algorithme ICP.

Voir aussi modifier

Références modifier

  1. ↑ a b c d et e (en) Paul J. Besl et N.D. McKay, « A Method for Registration of 3-D Shapes », IEEE Trans. on Pattern Analysis and Machine Intelligence, Los Alamitos, CA, USA, IEEE Computer Society, vol. 14, no 2,‎ , p. 239–256 (DOI 10.1109/34.121791)
  2. ↑ a b c et d (en) Yang Chen et Gerard Medioni, « Object modelling by registration of multiple range images », Image Vision Comput., Newton, MA, USA, Butterworth-Heinemann,‎ , p. 145--155 (DOI 10.1016/0262-8856(92)90066-C)
  3. ↑ a b c et d (en) Szymon Rusinkiewicz et Marc Levoy, « Efficient Variants of the ICP Algorithm », Proceedings of the Third Intl. Conf. on 3D Digital Imaging and Modeling,‎ , p. 145–152
  4. ↑ a et b (en) François Pomerleau, Francis Colas, Roland Siegwart et Stéphane Magnenat, « Comparing ICP variants on real-world data sets: Open-source library and experimental protocol », Autonomous Robots, vol. 34, no 3,‎ , p. 133–148 (ISSN 0929-5593 et 1573-7527, DOI 10.1007/s10514-013-9327-2, lire en ligne, consulté le )
  5. ↑ Brian Amberg, Sami Romdhani et Thomas Vetter, « Optimal Step Nonrigid ICP Algorithms for Surface Registration », 2007 IEEE Conference on Computer Vision and Pattern Recognition,‎ , p. 1–8 (DOI 10.1109/CVPR.2007.383165, lire en ligne, consulté le )
  6. ↑ a et b (en) « Zippered polygon meshes from range images | Proceedings of the 21st annual conference on Computer graphics and interactive techniques », sur dl.acm.org (DOI 10.1145/192161.192241, consulté le )
  7. ↑ T. Masuda, K. Sakaue et N. Yokoya, « Registration and integration of multiple range images for 3-D model construction », Proceedings of 13th International Conference on Pattern Recognition, vol. 1,‎ , p. 879–883 vol.1 (DOI 10.1109/ICPR.1996.546150, lire en ligne, consulté le )
  8. ↑ a b et c Guy Godin, Marc Rioux et Rejean Baribeau, « Three-dimensional registration using range and intensity information », Videometrics III, International Society for Optics and Photonics, vol. 2350,‎ , p. 279–290 (DOI 10.1117/12.189139, lire en ligne, consulté le )
  9. ↑ K. Pulli, « Multiview registration for large data sets », Second International Conference on 3-D Digital Imaging and Modeling (Cat. No.PR00062), IEEE Comput. Soc,‎ , p. 160–168 (ISBN 978-0-7695-0062-1, DOI 10.1109/IM.1999.805346, lire en ligne, consulté le )
  10. ↑ C. Dorai, G. Wang, A.K. Jain et C. Mercer, « Registration and integration of multiple object views for 3D model construction », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no 1,‎ , p. 83–89 (DOI 10.1109/34.655652, lire en ligne, consulté le )
  11. ↑ (en) Olga Sorkine, « Least-squares rigid motion using svd », Technical notes,‎ (lire en ligne)
  12. ↑ (en) Berthold K. P. Horn, « Closed-form solution of absolute orientation using unit quaternions », JOSA A, vol. 4, no 4,‎ , p. 629–642 (ISSN 1520-8532, DOI 10.1364/JOSAA.4.000629, lire en ligne, consulté le )
  13. ↑ (en) Low, Kok-Lim, « Linear least-squares optimization for point-to-plane icp surface registration », Chapel Hill, University of North Carolina,‎ , p. 1--3 (lire en ligne)
  14. ↑ A.E. Johnson et M. Hebert, « Surface registration by matching oriented points », Proceedings. International Conference on Recent Advances in 3-D Digital Imaging and Modeling (Cat. No.97TB100134), IEEE Comput. Soc. Press,‎ , p. 121–128 (ISBN 978-0-8186-7943-8, DOI 10.1109/IM.1997.603857, lire en ligne, consulté le )
  15. ↑ Chu-Song Chen, Yi-Ping Hung et Jen-Bo Cheng, « RANSAC-based DARCES: a new approach to fast automatic registration of partially overlapping range images », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, no 11,‎ , p. 1229–1234 (DOI 10.1109/34.809117, lire en ligne, consulté le )
  16. ↑ (en) « 4-points congruent sets for robust pairwise surface registration | ACM SIGGRAPH 2008 papers », sur dl.acm.org (DOI 10.1145/1399504.1360684, consulté le )
  17. ↑ Jiaolong Yang, Hongdong Li, Dylan Campbell et Yunde Jia, « Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no 11,‎ , p. 2241–2254 (ISSN 0162-8828 et 2160-9292, DOI 10.1109/TPAMI.2015.2513405, lire en ligne, consulté le )

Liens externes modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Iterative_Closest_Point&oldid=211047644 ».