Iterative Closest Point

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

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

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

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

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.