Iterative Closest Point
- Aussi appelé: ICP, ICP registration
- Catégorie: State estimation & navigation › Localisation
- Mots-clés: point-cloud, registration, lidar, localization, 3d-perception
Un algorithme qui aligne deux nuages de points en appariant à plusieurs reprises chaque point à son plus proche voisin dans l'autre nuage et en calculant la transformation rigide qui correspond le mieux à ces paires.
Définition
Iterative Closest Point (ICP) : algorithme de recalage de deux ensembles de points 3D, c'est-à-dire de recherche de la rotation et de la translation qui alignent au mieux l'un sur l'autre. Il a été introduit par Besl et McKay en 1992, et une méthode étroitement apparentée a été publiée par Chen et Medioni à peu près à la même époque. ICP est un outil de base pour l'odométrie LiDAR, la mise en correspondance de scans, la reconstruction 3D et l'affinage de la pose d'objets.
L'algorithme alterne deux étapes. D'abord, pour chaque point du nuage de points source, il trouve le point le plus proche dans le nuage cible, ce qui donne un ensemble de correspondances provisoires. Ensuite, il calcule la transformation rigide qui minimise la distance entre ces paires ; pour les distances point à point, elle a une solution analytique fondée sur la décomposition en valeurs singulières. La source est déplacée par cette transformation, et le processus se répète jusqu'à ce que la variation entre itérations devienne faible.
ICP ne converge que vers un minimum local, il a donc besoin d'une estimation initiale raisonnable, provenant généralement de l'odométrie, d'une IMU ou d'une méthode de recalage global grossier. Si le désalignement de départ est important, les plus proches voisins seront faux et l'algorithme peut se bloquer sur un alignement incorrect.
De nombreuses variantes améliorent la vitesse et la robustesse. ICP point à plan mesure la distance de chaque point au plan tangent en son correspondant, ce qui converge généralement plus vite sur les scènes structurées. Generalized ICP modélise la covariance locale de la surface dans les deux nuages. Les implémentations pratiques sous-échantillonnent aussi les points, utilisent des arbres k-d pour la recherche de voisins, et rejettent les paires trop éloignées ou dont les normales de surface sont incohérentes.
Pourquoi c'est important
La plupart des systèmes de localisation et de cartographie fondés sur le LiDAR utilisent ICP ou l'une de ses variantes pour estimer comment le robot s'est déplacé entre deux scans et pour vérifier les fermetures de boucle. C'est aussi un moyen standard d'affiner la pose d'un objet avant de le saisir lorsqu'un modèle 3D de l'objet est disponible.
Applications principales
- Odométrie LiDAR et mise en correspondance de scans pour les robots mobiles
- Vérification des fermetures de boucle en SLAM
- Affinage de la pose d'objets pour la préhension à partir de données de profondeur
- Fusion de plusieurs scans en un seul modèle 3D
- Alignement des données capteurs en direct sur une carte existante pour la localisation
En pratique
Une équipe qui développe une odométrie LiDAR pour un robot mobile sous-échantillonne généralement chaque scan avec une grille de voxels, utilise l'estimation de mouvement précédente ou des données IMU intégrées comme estimation initiale, et exécute un ICP point à plan contre le scan précédent ou une carte locale. Des bibliothèques comme PCL, Open3D et libpointmatcher fournissent des implémentations prêtes à l'emploi. Les principaux paramètres de réglage sont la distance de correspondance maximale, le seuil de convergence et la limite d'itérations, et les ingénieurs vérifient le score d'ajustement final pour repérer les échecs dans les lieux géométriquement pauvres en caractéristiques, comme les longs couloirs ou les champs ouverts, où ICP peut glisser le long de la direction qui n'a aucune contrainte.
Idées reçues
- ICP trouve l'alignement globalement optimal — il converge vers un minimum local et a besoin d'une bonne estimation initiale
- ICP fonctionne sur n'importe quelle géométrie — dans les scènes dégénérées comme les sols plats ou les longs tunnels, certaines directions ne sont pas contraintes et le résultat peut dériver
- ICP gère le changement d'échelle et la déformation — ICP standard n'estime qu'une transformation rigide ; un alignement avec changement d'échelle ou non rigide nécessite d'autres méthodes
Qui devrait le savoir
- Ingénieurs en perception travaillant avec des LiDAR et des caméras de profondeur
- Développeurs SLAM et localisation
- Ingénieurs en manipulation pratiquant l'estimation de pose d'objets fondée sur un modèle
- Praticiens de la numérisation et de la reconstruction 3D
Technologies associées
- Point Cloud Library (PCL)
- Open3D
- Normal Distributions Transform (NDT)
- Generalized ICP
- Arbre k-d (k-d Tree)
- RANSAC
Termes associés
Projets associés
- Open3D: Modern library for 3D point cloud processing, mesh operations, and 3D machine learning
- oomwoo: Open-source DIY robot vacuum: 3D-printed, ROS2 + 2D LiDAR, fully local.
- PCL: Industry-standard C++ library for point cloud processing in robotics perception
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
Vidéos
- Iterative Closest Point (ICP) - Computerphile: Computerphile
- Iterative Closest Point (ICP) - 5 Minutes with Cyrill: Cyrill Stachniss