El punto más cercano iterativo ( ICP ) [1] [2] [3] [4] es un algoritmo empleado para minimizar la diferencia entre dos nubes de puntos . 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 ruta óptima (especialmente cuando la odometría de la rueda no es confiable debido a un terreno resbaladizo), para co-registrar modelos óseos , etc.
Descripción general
En el punto más cercano iterativo o, en algunas fuentes, el punto correspondiente iterativo, una nube de puntos (nube de vértices), la referencia u objetivo , se mantiene fija, mientras que el otro, la fuente , se transforma para que coincida mejor con la referencia. El algoritmo revisa iterativamente la transformación (combinación de traslación y rotación) necesaria para minimizar una métrica de error, generalmente una distancia desde la fuente a la nube de puntos de referencia, como la suma de las diferencias cuadradas entre las coordenadas de los pares emparejados. ICP es uno de los algoritmos más utilizados en la alineación de modelos tridimensionales dada una suposició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]
El algoritmo de punto más cercano iterativo contrasta con el algoritmo de Kabsch y otras soluciones al problema ortogonal de Procrustes en que el algoritmo de Kabsch requiere la correspondencia entre conjuntos de puntos como entrada, mientras que el punto más cercano iterativo trata la correspondencia como una variable a estimar.
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.
Básicamente, los pasos del algoritmo son: [5]
- Para cada punto (de todo el conjunto de vértices generalmente denominado denso 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 la distancia de punto a punto de la raíz cuadrada media que alineará mejor cada punto de origen 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.
- Transforma los puntos de origen utilizando la transformación obtenida.
- Iterar (volver a asociar los puntos, etc.).
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 apariencia y la desaparición, lo que permite la coincidencia de subconjuntos y subconjuntos.
Existen muchas variantes de ICP, [6] de las cuales el punto a punto y el punto a plano son los 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 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 (Point Cloud Library) es un marco de código abierto para nubes de puntos n-dimensionales 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 lanzada bajo una licencia BSD.
- simpleICP es una implementación de una versión bastante simple del algoritmo ICP en varios idiomas.
Ver también
Referencias
- ^ Arun, Somani; Thomas S. Huang; Steven D. Blostein (1987). "Ajuste por mínimos cuadrados de dos conjuntos de puntos 3D". Análisis de patrones IEEE e inteligencia de máquinas . 9 (5): 698–700. doi : 10.1109 / TPAMI.1987.4767965 . PMID 21869429 .
- ^ a b Besl, Paul J .; ND McKay (1992). "Un método para el registro de formas 3D". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 14 (2): 239-256. doi : 10.1109 / 34.121791 .
- ^ a b Chen, Yang; Gerard Medioni (1991). "Modelado de objetos por registro de imágenes de rango múltiple". Computación de visión de imagen . 10 (3): 145-155. doi : 10.1016 / 0262-8856 (92) 90066-C .
- ^ a b Zhang, Zhengyou (1994). "Coincidencia de puntos iterativos para el registro de curvas y superficies de forma libre". Revista Internacional de Visión por Computador . 13 (12): 119-152. CiteSeerX 10.1.1.175.770 . doi : 10.1007 / BF01427149 .
- ^ a b Rusinkiewicz, Szymon; Marc Levoy (2001). Variantes eficientes del algoritmo ICP . Actas de la Tercera Conferencia Internacional sobre Modelado y Imagen Digital 3D. Ciudad de Quebec, Quebec, Canadá. págs. 145-152. doi : 10.1109 / IM.2001.924423 .
- ^ Pomerleau, François; Colas, Francis; 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 .
- ^ Kok-Lim Low (febrero de 2004). "Optimización de mínimos cuadrados lineales para el registro de superficies 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 de ICP en conjuntos de datos del mundo real. En Autonomous Robots, 34 (3), páginas 133-148, DOI: 10.1007 / s10514-013-9327-2, abril de 2013.
- ^ Holz, Dirk; Ichim, Alexandru E .; Tombari, Federico; Rusu, Radu B .; Behnke, Sven (2015). "Registro con 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 .