Iterative Closest Point

• Detto anche: ICP, ICP registration
• Categoria: State estimation & navigation › Localisation
• Tag: point-cloud, registration, lidar, localization, 3d-perception

Un algoritmo che allinea due nuvole di punti accoppiando ripetutamente ogni punto con il suo vicino più prossimo nell'altra nuvola e calcolando la trasformazione rigida che meglio si adatta a quelle coppie.

Definizione

Iterative Closest Point (ICP) è un algoritmo per registrare due insiemi di punti 3D, cioè trovare la rotazione e la traslazione che allineano al meglio l'uno all'altro. È stato introdotto da Besl e McKay nel 1992, e un metodo strettamente affine è stato pubblicato da Chen e Medioni più o meno nello stesso periodo. ICP è uno strumento di base per l'odometria LiDAR, lo scan matching, la ricostruzione 3D e il raffinamento della posa degli oggetti.

L'algoritmo alterna due passi. Primo, per ogni punto della nuvola sorgente trova il punto più vicino nella nuvola di destinazione, ottenendo un insieme di corrispondenze provvisorie. Secondo, calcola la trasformazione rigida che minimizza la distanza tra quelle coppie; per le distanze punto-punto questo ha una soluzione in forma chiusa che usa la decomposizione ai valori singolari. La sorgente viene spostata secondo quella trasformazione, e il processo si ripete finché la variazione tra un'iterazione e l'altra diventa piccola.

ICP converge solo a un minimo locale, quindi ha bisogno di una stima iniziale ragionevole, di solito fornita dall'odometria, da un'unità di misura inerziale (IMU) o da un metodo di registrazione globale approssimativo. Se il disallineamento di partenza è grande, i vicini più prossimi saranno sbagliati e l'algoritmo può agganciarsi a un allineamento errato.

Molte varianti migliorano velocità e robustezza. L'ICP punto-piano misura la distanza di ogni punto dal piano tangente nel punto corrispondente, il che di solito converge più in fretta nelle scene strutturate. Generalized ICP modella la covarianza della superficie locale su entrambe le nuvole. Le implementazioni pratiche inoltre sottocampionano i punti, usano alberi k-d per la ricerca dei vicini e scartano le coppie troppo distanti o con normali di superficie incoerenti.

Perché è importante

La maggior parte dei sistemi di localizzazione e mappatura basati su LiDAR usa ICP o una sua variante per stimare come si è mosso il robot tra una scansione e l'altra e per verificare le chiusure del loop. È anche un modo standard per raffinare la posa di un oggetto prima della presa quando è disponibile un modello 3D dell'oggetto.

Applicazioni principali

• Odometria LiDAR e scan matching per robot mobili
• Verifica delle chiusure del loop nello SLAM
• Raffinamento della posa degli oggetti per la presa a partire da dati di profondità
• Unione di più scansioni in un unico modello 3D
• Allineamento dei dati dei sensori in tempo reale con una mappa preesistente per la localizzazione

In pratica

Un team che sviluppa l'odometria LiDAR per un robot mobile di solito sottocampiona ogni scansione con una griglia di voxel, usa come stima iniziale la stima di moto precedente o i dati integrati dell'unità di misura inerziale (IMU) ed esegue ICP punto-piano rispetto alla scansione precedente o a una mappa locale. Librerie come PCL, Open3D e libpointmatcher forniscono implementazioni pronte. I principali parametri da regolare sono la distanza massima di corrispondenza, la soglia di convergenza e il limite di iterazioni, e gli ingegneri controllano il punteggio di fitness finale per individuare i fallimenti in luoghi privi di caratteristiche geometriche, come lunghi corridoi o campi aperti, dove ICP può scivolare lungo la direzione priva di vincoli.

Idee sbagliate comuni

• ICP trova l'allineamento migliore in assoluto — converge a un minimo locale e ha bisogno di una buona stima iniziale
• ICP funziona su qualsiasi geometria — in scene degeneri come pavimenti piani o lunghi tunnel alcune direzioni non sono vincolate e il risultato può andare alla deriva
• ICP gestisce scala e deformazione — l'ICP standard stima solo una trasformazione rigida; l'allineamento con scala o non rigido richiede altri metodi

Chi dovrebbe saperlo

• Ingegneri della percezione che lavorano con LiDAR e telecamere di profondità
• Sviluppatori di SLAM e localizzazione
• Ingegneri di manipolazione che stimano la posa degli oggetti a partire da modelli
• Professionisti della scansione e ricostruzione 3D

Tecnologie correlate

• Point Cloud Library (PCL)
• Open3D
• Normal Distributions Transform (NDT)
• Generalized ICP
• Albero k-d (k-d Tree)
• RANSAC

Termini correlati

• Point Cloud
• LIDAR
• SLAM
• Transform

Progetti correlati

• 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

Video

• Iterative Closest Point (ICP) - Computerphile: Computerphile
• Iterative Closest Point (ICP) - 5 Minutes with Cyrill: Cyrill Stachniss