El algoritmo de punto más cercano iterativo mantiene fija una nube de puntos, la referencia o el objetivo, mientras transforma la otra, la fuente, para que coincida mejor con la referencia. La transformación (combinación de traslación y rotación) se estima de forma iterativa para minimizar una métrica de error, normalmente la suma de diferencias al cuadrado entre las coordenadas de los pares coincidentes. ICP es uno de los algoritmos más utilizados para alinear modelos tridimensionales dada 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 fuente, estimación inicial de la transformación para alinear la fuente con la referencia (opcional), criterios para detener las iteraciones.
Resultado: transformación refinada.
Esencialmente, los pasos del algoritmo son: [5]
Para cada punto (de todo el conjunto de vértices generalmente denominados densos o 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 un conjunto seleccionado).
Estime la combinación de rotación y traslación utilizando una técnica de minimización métrica de distancia punto a punto cuadrática media que alineará mejor cada punto fuente con su coincidencia encontrada en el paso anterior. Este paso también puede implicar ponderar puntos y rechazar valores atípicos antes de la alineación.
Transforme los puntos de origen utilizando la transformación obtenida.
Zhang [4] propone un algoritmo de árbol k -d modificado para un 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 los valores atípicos, la oclusión, la aparición y la desaparición, lo que permite la comparación subconjunto-subconjunto.
Existen muchas variantes de ICP, [6] de las cuales punto a punto y punto a plano son las más populares. Este último suele funcionar mejor en entornos estructurados. [7] [8]
Implementaciones
MeshLab es una herramienta de procesamiento de malla de código abierto que incluye una implementación de Licencia Pública General GNU del algoritmo ICP.
CloudCompare es una herramienta de procesamiento de modelos y puntos de código abierto que incluye una implementación del algoritmo ICP. Publicado bajo la Licencia Pública General GNU.
PCL (Biblioteca de nubes de puntos) es un marco de código abierto para nubes de puntos de n dimensiones y procesamiento de geometría 3D. Incluye varias variantes del algoritmo ICP. [9]
Las implementaciones de código abierto 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.
^ Arun, somaní; Thomas S. Huang; Steven D. Blostein (1987). "Ajuste de mínimos cuadrados de dos conjuntos de puntos 3D". Análisis de patrones IEEE e inteligencia de máquinas . 9 (5): 698–700. CiteSeerX 10.1.1.467.9356 . doi :10.1109/TPAMI.1987.4767965. PMID 21869429. S2CID 8724100.
^ ab Besl, Paul J.; ND McKay (1992). "Un método para el registro de formas tridimensionales". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 14 (2): 239–256. doi : 10.1109/34.121791.
^ ab Chen, Yang; Gérard Medioni (1991). "Modelado de objetos mediante registro de imágenes de rango múltiple". Computación de visión de imágenes . 10 (3): 145-155. doi :10.1016/0262-8856(92)90066-C.
^ ab Zhang, Zhengyou (1994). "Coincidencia de puntos iterativos para el registro de curvas y superficies de forma libre". Revista Internacional de Visión por Computadora . 13 (12): 119-152. CiteSeerX 10.1.1.175.770 . doi :10.1007/BF01427149. S2CID 14673939.
^ ab Rusinkiewicz, Szymon; Marc Levoy (2001). Variantes eficientes del algoritmo ICP . Actas de la Tercera Conferencia Internacional sobre Modelado e Imágenes Digitales 3-D. Ciudad de Quebec, Quebec, Canadá. págs. 145-152. doi :10.1109/IM.2001.924423.
^ Pomerleau, François; Colas, Francisco; Siegwart, Roland (2015). "Una revisión de los algoritmos de registro de nubes de puntos para robótica móvil". Fundamentos y Tendencias en Robótica . 4 (1): 1–104. CiteSeerX 10.1.1.709.2212 . doi :10.1561/2300000035. S2CID 62361231.
^ Kok-Lim Low (febrero de 2004). "Optimización lineal de mínimos cuadrados para el registro de superficie ICP punto a plano" (PDF) . Comp.nys.edu.sg. Informe técnico TR04-004, Departamento de Ciencias de la Computación, Universidad de Carolina del Norte en Chapel Hill . Consultado el 27 de febrero de 2017 .
^ François Pomerleau, Francis Colas, Roland Siegwart y Stéphane Magnenat. Comparación de variantes del ICP en conjuntos de datos del mundo real. En Robots autónomos, 34(3), páginas 133–148, DOI: 10.1007/s10514-013-9327-2, abril de 2013.
^ Holz, Dirk; Ichim, Alexandru E.; Tomari, Federico; Rusu, Radu B.; Behnke, Sven (2015). "Registro en la biblioteca de nubes de puntos: un marco modular para alinear en 3-D". Revista IEEE Robotics Automation . 22 (4): 110-124. doi :10.1109/MRA.2015.2432331. S2CID 2621807.
