12.2: El algoritmo de punto más cercano iterativo (ICP)

El algoritmo Punto Más Cercano Iterativo (ICP) se presentó a principios de la década de 1990 para el registro de datos de rango 3D a modelos CAD de objetos. Una visión más profunda de lo que aquí se describe se da en (Rusinkiewicz & Levoy 2001). El problema clave se puede reducir para encontrar la mejor transformación que minimice la distancia entre dos nubes de puntos. Este es el caso cuando se hacen coincidir instantáneas de un sensor de rango o se hace coincidir una imagen de rango con una nube de puntos muestreada a partir de una representación 3D de un objeto.

En robótica, ICP encontró una aplicación para igualar escaneos de escáneres de rango láser 2D. Por ejemplo, la transformación que minimiza el error entre dos instantáneas consecutivas del entorno es proporcional al movimiento del robot. Este es un problema duro ya que no está claro, qué puntos en las dos instantáneas consecutivas son “pares”, cuáles de los puntos son valores atípicos (debido a sensores ruidosos), y qué puntos deben descartarse ya que no todos los puntos se superponen en ambas instantáneas. Unir una serie de instantáneas teóricamente permite crear un mapa 2D del entorno. Esto es difícil, sin embargo, ya que se acumula el error entre cada instantánea —similar a la odometría—. El algoritmo ICP también funciona en 3D donde permite inferir el cambio en la pose 6D de una cámara y la creación de mapas 3D. Además, ICP ha demostrado ser útil para identificar objetos de una base de datos de objetos 3D.

Antes de proporcionar una solución al problema de mapeo, nos centraremos en el algoritmo ICP para que coincida con 2 fotogramas consecutivos. Las variantes del algoritmo ICP se pueden dividir en 6 pasos consecutivos:

1. Selección de puntos en una o ambas mallas o nubes de puntos.
2. Emparejamiento/Emparejamiento de estos puntos con muestras en la otra nubo/malla de puntos.
3. Ponderando los pares correspondientes.
4. Rechazando ciertos pares.
5. Asignar una métrica de error basada en los pares de puntos.
6. Minimizar la métrica de error.
7. Selección de puntos

Dependiendo del número de puntos generados por el sensor de rango, podría tener sentido usar solo unos pocos puntos seleccionados para calcular la transformación óptima entre dos nubes de puntos, y luego probar esta transformación en todos los puntos. Dependiendo de la fuente de los datos, también resulta que algunos puntos son más adecuados que otros ya que es más fácil identificar coincidencias para ellos. Este es el caso de los datos RGB-D, donde las características SIFT se han utilizado con éxito. Este es también el caso de los objetos planos con ranuras, donde el muestreo debe garantizar que los ángulos de los vectores normales de los puntos de muestreo se distribuyan ampliamente. Por lo tanto, qué método utilizar depende en gran medida del tipo de datos que se utilicen y se debe considerar para cada problema específico.

12.2.1. Puntos coincidentes

El paso clave en ICP es hacer coincidir un punto con su punto correspondiente. Por ejemplo, un escáner láser golpea cierto punto en una pared con su rayo 67. Después de que el escáner se haya movido 10 cm, el impacto más cercano en la pared a este punto podría haber sido por el tercer rayo del láser. Aquí, en realidad es muy poco probable que el láser golpee exactamente el mismo punto en la pared dos veces, por lo tanto, introduciendo un error distinto de cero incluso para un emparejamiento óptimo. Los métodos prominentes son encontrar el punto más cercano en la otra nube de puntos o encontrar la intersección de los puntos de origen normales con la superficie de destino (para hacer coincidir las nubes de puntos con las mallas). Más recientemente, SIFT ha permitido igualar puntos en función de su apariencia visual. De manera similar a la clasificación a través de entidades SIFT, encontrar el punto coincidente más cercano se puede acelerar representando la nube de puntos en un árbol k-d.

12.2.2. Ponderación de Pares

Como algunos pares son mejores coincidencias que otros, ponderarlos de alguna manera inteligente podría mejorar drásticamente la calidad de la transformación resultante. Un enfoque es darle más peso a los puntos que tienen distancias menores entre sí. Otro enfoque es tomar en cuenta el color del punto (en imágenes RGBD) o utilizar la distancia de sus características SIFT (ponderando pares con distancias bajas superiores a pares con distancias altas). Finalmente, el ruido esperado se puede utilizar para ponderar los emparejamientos. Por ejemplo, las estimaciones realizadas por un escáner láser son mucho más fieles cuando se toman ortogonalmente a un plano que cuando se toman en un ángulo pronunciado.

12.2.3. Rechazo de Pares

Un problema clave en ICP son los valores atípicos ya sea del ruido del sensor o simplemente de la superposición incompleta entre dos imágenes de rango consecutivas. Un enfoque primordial al tratar este problema es rechazar los emparejamientos de los cuales uno de los puntos se encuentra en un límite de la nube de puntos, ya que es probable que estos puntos coincidan con puntos en regiones no superpuestas. En función de los datos subyacentes, también podría tener sentido rechazar emparejamientos con una distancia demasiado alta. Esto es un equivalente basado en umbrales a la ponderación basada en distancia como se describió anteriormente.

12.2.4. Métrica de error y algoritmo de minimización

Después de seleccionar y emparejar los puntos, los pares se han ponderado y rechazado, la coincidencia entre dos nubes de puntos debe expresarse mediante una métrica de error adecuada, que luego debe minimizarse. Un enfoque sencillo es considerar la suma de distancias cuadradas entre cada par. Esta formulación a menudo se puede resolver analíticamente. Vamos

\[A=\{a_{1},...,a_{n}\}\]

\[B=\{b_{1},...,b_{n}\}\]

ser nubes de puntos en R ⁿ. El objetivo ahora es encontrar un vector t ∈ R ⁿ para que se minimice una función de error φ (A+t, B). En 6D (traslación y rotación), se puede encontrar una notación equivalente para una transformación (ver cinemática hacia adelante). Una función de error para la distancia al cuadrado viene dada por

\[\phi (A+t, B)=\frac{1}{n}\sum_{a\in A}^{}\left \| a+t-N_{B}(a+t) \right \|^{2}\]

Aquí N _B (a+t) es una función que proporciona el vecino más cercano de a traducido por b en B. Un problema clave ahora es que el valor real de t afecta el resultado del emparejamiento. Lo que podría parecer un buen partido inicialmente a menudo resulta no ser el emparejamiento final. Un enfoque numérico simple para este problema es encontrar t iterativamente.

Inicialmente t = 0 y se establecen vecinos/emparejamientos más cercanos. Ahora podemos calcular un δt que optimiza el problema de mínimos cuadrados en base a esta coincidencia utilizando cualquier solucionador disponible para el problema de optimización (para una solución de mínimos cuadrados δt se puede obtener analíticamente resolviendo para el mínimo del polinomio estableciendo su derivada en cero). Entonces podemos desplazar todos los puntos en A por δt y empezar de nuevo. Es decir, calculamos nuevos emparejamientos y derivamos un nuevo δt. Podemos seguir haciendo esto, hasta que la función de costo alcance un mínimo local.

En lugar de formular la función de costo como una distancia “punto a punto”, se ha popularizado un “punto a plano”. Aquí, la función de costo consiste en la suma de distancias cuadradas desde cada punto de origen hasta el plano que contiene el punto de destino y está orientado perpendicular a la normal de destino. Esto tiene especial sentido cuando se hace coincidir una nube de puntos con un modelo de malla/CAD de un objeto. En este caso no existen soluciones analíticas para encontrar la transformación óptima, pero se puede utilizar cualquier método de optimización como Levenberg-Marquardt.