Punto más cercano iterativo

El método iterativo de punto más cercano ( ICP ) ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} es un algoritmo de registro de nubes de puntos que se emplea para minimizar la diferencia entre dos nubes de puntos . El ICP se utiliza a menudo para reconstruir superficies 2D o 3D a partir de diferentes escaneos, para localizar robots y lograr una planificación de trayectoria óptima (especialmente cuando la odometría de las ruedas no es fiable debido a terrenos resbaladizos), para corregistrar modelos óseos , etc.

El algoritmo de Punto Más Cercano Iterativo (ICP) mantiene fija una nube de puntos, la de referencia o destino, mientras transforma la otra, la de origen, para que coincida lo mejor posible con la de referencia. La transformación (combinación de traslación y rotación) se estima iterativamente para minimizar una métrica de error, típicamente la suma de las diferencias cuadráticas entre las coordenadas de los pares coincidentes. ICP es uno de los algoritmos más utilizados para alinear modelos tridimensionales a partir de una estimación inicial de la transformación rígida requerida. ^{[ 5 ]} El algoritmo ICP fue introducido por primera vez por Chen y Medioni, ^{[ 3 ]} y Besl y McKay. ^{[ 2 ]}

Entradas: nubes de puntos de referencia y de origen, estimación inicial de la transformación para alinear el origen con la referencia (opcional), criterios para detener las iteraciones.

Salida: transformación refinada.

Esencialmente, los pasos del algoritmo son: ^{[ 5 ]}

1. Para cada punto (del conjunto completo de vértices, generalmente denominado denso, o de una selección de pares de vértices de cada modelo) en la nube de puntos de origen, haga coincidir el punto más cercano en la nube de puntos de referencia (o en un conjunto seleccionado).
2. Estimar la combinación de rotación y traslación mediante una técnica de minimización de la distancia cuadrática media punto a punto, que permita alinear de la mejor manera cada punto de origen con su correspondiente punto hallado en el paso anterior. Este paso también puede implicar ponderar los puntos y descartar los valores atípicos antes de la alineación.
3. Transforma los puntos de origen utilizando la transformación obtenida.
4. Iterar (reasociar los puntos, etc.).

Zhang ^{[ 4 ]} propone un algoritmo de árbol k -d modificado para el cálculo eficiente del punto más cercano. En este trabajo se utiliza un método estadístico basado en la distribución de distancias para tratar valores atípicos, oclusiones, apariciones y desapariciones, lo que permite la coincidencia entre subconjuntos.

Existen muchas variantes de ICP, ^{[ 6 ]} de las cuales las de punto a punto y punto a plano son las más populares. Esta última suele tener un mejor rendimiento en entornos estructurados. ^{[ 7 ] [ 8 ]}

ICP no rígido

Si bien el ICP tradicional asume transformaciones rígidas, los métodos ICP no rígidos extienden el algoritmo para manejar objetos deformables y escenarios de registro no rígido. Estos métodos incorporan restricciones adicionales y términos de regularización para modelar deformaciones locales manteniendo la coherencia de la superficie.

• MeshLab es una herramienta de procesamiento de mallas de código abierto que incluye una implementación del algoritmo ICP bajo la Licencia Pública General de GNU.
• CloudCompare es una herramienta de código abierto para el procesamiento de puntos y modelos que incluye una implementación del algoritmo ICP. Se distribuye bajo la Licencia Pública General de GNU.
• PCL (Point Cloud Library) es un marco de código abierto para el procesamiento de nubes de puntos n-dimensionales y geometría 3D. Incluye varias variantes del algoritmo ICP. ^{[ 9 ]}
• Las implementaciones de código abierto en C++ del algoritmo ICP están disponibles en las bibliotecas VTK , ITK y Open3D .
• libpointmatcher es una implementación de ICP punto a punto y punto a plano, publicada bajo una licencia BSD.
• simpleICP es una implementación de una versión bastante simple del algoritmo ICP en varios lenguajes.
• 3D-nonrigid-ICP es una implementación de código abierto de un método ICP no rígido.

• Las distribuciones normales transforman