Punto más cercano iterativo

Algoritmo

Idea detrás del algoritmo iterativo del punto más cercano

El punto más cercano iterativo ( ICP ) ^{[1] [2] [3] [4]} es un algoritmo empleado 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 óptima de la ruta (especialmente cuando la odometría de las ruedas no es confiable debido a un terreno resbaladizo), para registrar conjuntamente modelos óseos , etc.

Descripción general

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 las diferencias al cuadrado entre las coordenadas de los pares coincidentes. El ICP es uno de los algoritmos más utilizados para alinear modelos tridimensionales, dado un cálculo 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 a la referencia (opcional), criterios para detener las iteraciones.

Salida: transformación refinada.

Básicamente, los pasos del algoritmo son: ^[5]

1. 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).
2. Calcule la combinación de rotación y traslación utilizando una técnica de minimización de la distancia entre puntos mediante 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 la ponderación de los puntos y el rechazo de los valores atípicos antes de la alineación.
3. Transforme 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 calcular de manera eficiente el 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 correspondencia entre subconjuntos.

Existen muchas variantes de ICP, ^[6] de las cuales las más populares son la de punto a punto y la de punto a plano. Esta última 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 puntos y modelos de código abierto que incluye una implementación del algoritmo ICP. Publicada bajo la Licencia Pública General de 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 C++ de código abierto 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.

Véase también

• Registro de conjunto de puntos

Referencias

1. Arun, Somani; Thomas S. Huang; Steven D. Blostein (1987). "Ajuste de mínimos cuadrados de dos conjuntos de puntos 3-D". IEEE Pattern Analysis and Machine Intelligence . 9 (5): 698–700. CiteSeerX  10.1.1.467.9356 . doi :10.1109/TPAMI.1987.4767965. PMID  21869429. S2CID  8724100.
2. Besl, Paul J.; ND McKay (1992). "Un método para el registro de formas 3-D". IEEE Transactions on Pattern Analysis and Machine Intelligence . 14 (2): 239–256. doi :10.1109/34.121791.
3. Chen, Yang; Gerard Medioni (1991). "Modelado de objetos mediante el registro de imágenes de rango múltiple". Image Vision Comput . 10 (3): 145–155. doi :10.1016/0262-8856(92)90066-C.
4. Zhang, Zhengyou (1994). "Coincidencia iterativa de puntos para el registro de curvas y superficies de forma libre". Revista internacional de visión artificial . 13 (12): 119–152. CiteSeerX 10.1.1.175.770 . doi :10.1007/BF01427149. S2CID  14673939. 
5. Rusinkiewicz, Szymon; Marc Levoy (2001). Variantes eficientes del algoritmo ICP . Actas de la Tercera Conferencia Internacional sobre Imágenes y Modelado Digital 3D. Ciudad de Quebec, Quebec, Canadá. págs. 145–152. doi :10.1109/IM.2001.924423.
6. 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. S2CID  62361231. 
7. Kok-Lim Low (febrero de 2004). "Optimización lineal de mínimos cuadrados 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 .
8. 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.
9. 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 la alineación en 3-D". Revista IEEE Robotics Automation . 22 (4): 110–124. doi :10.1109/MRA.2015.2432331. S2CID  2621807.