Iterative Closest Point

• Também chamado: ICP, ICP registration
• Categoria: State estimation & navigation › Localisation
• Tags: point-cloud, registration, lidar, localization, 3d-perception

Um algoritmo que alinha duas nuvens de pontos emparelhando repetidamente cada ponto com seu vizinho mais próximo na outra nuvem e calculando a transformação rígida que melhor se ajusta a esses pares.

Definição

Iterative Closest Point (ICP) é um algoritmo para registrar dois conjuntos de pontos 3D, isto é, encontrar a rotação e a translação que melhor alinham um ao outro. Foi apresentado por Besl e McKay em 1992, e um método muito semelhante foi publicado por Chen e Medioni mais ou menos na mesma época. O ICP é uma ferramenta básica para odometria por LiDAR, casamento de varreduras (scan matching), reconstrução 3D e refinamento da pose de objetos.

O algoritmo alterna duas etapas. Primeiro, para cada ponto da nuvem de origem, ele encontra o ponto mais próximo na nuvem de destino, o que gera um conjunto de correspondências provisórias. Segundo, calcula a transformação rígida que minimiza a distância entre esses pares; para distâncias ponto a ponto, isso tem uma solução em forma fechada usando a decomposição em valores singulares. A nuvem de origem é movida por essa transformação, e o processo se repete até que a mudança entre iterações fique pequena.

O ICP converge apenas para um mínimo local, então precisa de uma estimativa inicial razoável, normalmente vinda da odometria, de uma unidade de medição inercial (IMU) ou de um método de registro global grosseiro. Se o desalinhamento inicial for grande, os vizinhos mais próximos estarão errados e o algoritmo pode se fixar em um alinhamento incorreto.

Muitas variantes melhoram a velocidade e a robustez. O ICP ponto a plano mede a distância de cada ponto ao plano tangente em seu correspondente, o que geralmente converge mais rápido em cenas estruturadas. O Generalized ICP modela a covariância da superfície local nas duas nuvens. Implementações práticas também subamostram os pontos, usam árvores k-d para a busca de vizinhos e rejeitam pares muito distantes ou com normais de superfície inconsistentes.

Por que importa

A maioria dos sistemas de localização e mapeamento baseados em LiDAR usa o ICP ou uma de suas variantes para estimar como o robô se moveu entre varreduras e para verificar fechamentos de loop. Também é uma forma padrão de refinar a pose de um objeto antes da preensão quando há um modelo 3D do objeto disponível.

Principais aplicações

• Odometria por LiDAR e casamento de varreduras para robôs móveis
• Verificação de fechamentos de loop em SLAM
• Refinamento da pose de objetos para preensão a partir de dados de profundidade
• Fusão de várias varreduras em um único modelo 3D
• Alinhamento de dados de sensores ao vivo com um mapa prévio para localização

Na prática

Uma equipe que desenvolve odometria por LiDAR para um robô móvel normalmente subamostra cada varredura com uma grade de voxels, usa a estimativa de movimento anterior ou dados integrados da unidade de medição inercial (IMU) como estimativa inicial e roda ICP ponto a plano contra a varredura anterior ou um mapa local. Bibliotecas como PCL, Open3D e libpointmatcher oferecem implementações prontas. Os principais parâmetros de ajuste são a distância máxima de correspondência, o limiar de convergência e o limite de iterações, e os engenheiros verificam a pontuação final de ajuste para detectar falhas em locais sem características geométricas, como corredores longos ou campos abertos, onde o ICP pode deslizar ao longo da direção que não tem restrição.

Equívocos comuns

• O ICP encontra o melhor alinhamento global — ele converge para um mínimo local e precisa de uma boa estimativa inicial
• O ICP funciona com qualquer geometria — em cenas degeneradas, como pisos planos ou túneis longos, algumas direções ficam sem restrição e o resultado pode derivar
• O ICP lida com escala e deformação — o ICP padrão estima apenas uma transformação rígida; alinhamento com escala ou não rígido exige outros métodos

Quem deve saber

• Engenheiros de percepção que trabalham com LiDAR e câmeras de profundidade
• Desenvolvedores de SLAM e localização
• Engenheiros de manipulação que fazem estimativa de pose de objetos baseada em modelos
• Profissionais de escaneamento e reconstrução 3D

Tecnologias relacionadas

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

Termos relacionados

• Point Cloud
• LIDAR
• SLAM
• Transform

Projetos relacionados

• 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

Vídeos

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