Registro de conjunto de puntos

Process of finding a spatial transformation that aligns two point clouds

El registro de conjuntos de puntos es el proceso de alinear dos conjuntos de puntos. Aquí, el pez azul se registra con el pez rojo.

En visión artificial , reconocimiento de patrones y robótica , el registro de conjuntos de puntos , también conocido como registro de nubes de puntos o coincidencia de escaneo , es el proceso de encontrar una transformación espacial ( por ejemplo, escalado , rotación y traslación ) que alinea dos nubes de puntos . El propósito de encontrar dicha transformación incluye fusionar múltiples conjuntos de datos en un modelo globalmente consistente (o marco de coordenadas) y mapear una nueva medición a un conjunto de datos conocido para identificar características o estimar su posición . Los datos de nubes de puntos 3D sin procesar generalmente se obtienen de lidares y cámaras RGB-D . Las nubes de puntos 3D también se pueden generar a partir de algoritmos de visión artificial, como triangulación , ajuste de paquetes y, más recientemente, estimación de profundidad de imagen monocular mediante aprendizaje profundo . Para el registro de conjuntos de puntos 2D utilizado en el procesamiento de imágenes y el registro de imágenes basado en características , un conjunto de puntos puede ser coordenadas de píxeles 2D obtenidas por extracción de características de una imagen, por ejemplo , detección de esquinas . El registro de nubes de puntos tiene amplias aplicaciones en conducción autónoma , ^[1] estimación de movimiento y reconstrucción 3D , ^[2] detección de objetos y estimación de pose , ^{[3] [4]} manipulación robótica , ^[5] localización y mapeo simultáneos (SLAM), ^{[6] [7]} unión de panoramas , ^[8] realidad virtual y aumentada , ^[9] e imágenes médicas . ^[10]

Como caso especial, el registro de dos conjuntos de puntos que solo difieren en una rotación 3D ( es decir, no hay escala ni traducción) se denomina problema de Wahba y también está relacionado con el problema de Procrustes ortogonal .

Formulación

Los datos de dos escaneos 3D del mismo entorno deben alinearse mediante el registro de conjuntos de puntos.

Datos de arriba, registrados exitosamente utilizando una variante del punto más cercano iterativo.

El problema puede resumirse de la siguiente manera: ^[11] Sean dos conjuntos de puntos de tamaño finito en un espacio vectorial real de dimensión finita , que contienen puntos y respectivamente ( por ejemplo, recupera el caso típico de cuando y son conjuntos de puntos 3D). El problema es encontrar una transformación que se aplique al conjunto de puntos "modelo" en movimiento de manera que la diferencia (normalmente definida en el sentido de distancia euclidiana puntual ) entre y el conjunto "escena" estático se minimice. En otras palabras, se desea una aplicación de a que produzca la mejor alineación entre el conjunto "modelo" transformado y el conjunto "escena". La aplicación puede consistir en una transformación rígida o no rígida. El modelo de transformación puede escribirse como , utilizando el cual el conjunto de puntos modelo registrado y transformado es: ${\displaystyle \lbrace {\mathcal {M}},{\mathcal {S}}\rbrace }$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle d=3}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle T}$

Por lo tanto, la salida de un algoritmo de registro de conjuntos de puntos es la transformación óptima que está mejor alineada con , según alguna noción definida de función de distancia : ${\displaystyle T^{\star }}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle \operatorname {dist} (\cdot ,\cdot )}$

donde se utiliza para indicar el conjunto de todas las transformaciones posibles que la optimización intenta buscar. La opción más popular de la función de distancia es tomar el cuadrado de la distancia euclidiana para cada par de puntos: ${\displaystyle {\mathcal {T}}}$

donde denota la norma 2 del vector , es el punto correspondiente en el conjunto que alcanza la distancia más corta a un punto dado en el conjunto después de la transformación. Minimizar dicha función en un registro rígido es equivalente a resolver un problema de mínimos cuadrados . ${\displaystyle \|\cdot \|_{2}}$ ${\displaystyle s_{m}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {M}}}$

Tipos de algoritmos

Cuando las correspondencias ( es decir, ) se dan antes de la optimización, por ejemplo, utilizando técnicas de coincidencia de características , entonces la optimización solo necesita estimar la transformación. Este tipo de registro se llama registro basado en correspondencias . Por otro lado, si las correspondencias son desconocidas, entonces se requiere la optimización para descubrir conjuntamente las correspondencias y la transformación. Este tipo de registro se llama registro simultáneo de pose y correspondencia . ${\displaystyle s_{m}\leftrightarrow m}$

Registro rígido

Dados dos conjuntos de puntos, el registro rígido produce una transformación rígida que asigna un conjunto de puntos al otro. Una transformación rígida se define como una transformación que no cambia la distancia entre dos puntos. Por lo general, una transformación de este tipo consiste en una traslación y una rotación . ^[12] En casos excepcionales, el conjunto de puntos también puede reflejarse. En robótica y visión artificial, el registro rígido tiene la mayor cantidad de aplicaciones.

Registro no rígido

Nube de puntos registrada desde un lidar montado en un automóvil en movimiento.

Dados dos conjuntos de puntos, el registro no rígido produce una transformación no rígida que asigna un conjunto de puntos al otro. Las transformaciones no rígidas incluyen transformaciones afines como el escalado y el mapeo de corte . Sin embargo, en el contexto del registro de conjuntos de puntos, el registro no rígido generalmente implica una transformación no lineal. Si se conocen los modos propios de variación del conjunto de puntos, la transformación no lineal puede parametrizarse mediante los valores propios. ^[13] Una transformación no lineal también puede parametrizarse como una spline de placa delgada . ^{[14] [13]}

Otros tipos

Algunos enfoques para el registro de conjuntos de puntos utilizan algoritmos que resuelven el problema más general de correspondencia de grafos . ^[11] Sin embargo, la complejidad computacional de dichos métodos tiende a ser alta y se limitan a registros rígidos. En este artículo, solo consideraremos algoritmos para el registro rígido, donde se supone que la transformación contiene rotaciones y traslaciones 3D (posiblemente también incluya un escalamiento uniforme).

La biblioteca de nubes de puntos (PCL) es un marco de código abierto para el procesamiento de nubes de puntos n-dimensionales y geometría 3D. Incluye varios algoritmos de registro de puntos. ^[15]

Registro por correspondencia

Los métodos basados ​​en correspondencias suponen que las supuestas correspondencias están dadas para cada punto . Por lo tanto, llegamos a una situación en la que ambos conjuntos de puntos tienen puntos y las correspondencias están dadas. ${\displaystyle m\leftrightarrow s_{m}}$ ${\displaystyle m\in {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle N}$ ${\displaystyle m_{i}\leftrightarrow s_{i},i=1,\dots ,N}$

Registro sin valores atípicos

En el caso más simple, se puede asumir que todas las correspondencias son correctas, lo que significa que los puntos se generan de la siguiente manera: ${\displaystyle m_{i},s_{i}\in \mathbb {R} ^{3}}$

donde es un factor de escala uniforme (en muchos casos se asume), es una matriz de rotación 3D adecuada ( es el grupo ortogonal especial de grado ), es un vector de traslación 3D y modela el ruido aditivo desconocido ( por ejemplo, ruido gaussiano ). Específicamente, si se supone que el ruido sigue una distribución gaussiana isótropa de media cero con desviación estándar , es decir, , entonces se puede demostrar que la siguiente optimización produce la estimación de máxima verosimilitud para la escala, rotación y traslación desconocidas: ${\displaystyle l>0}$ ${\displaystyle l=1}$ ${\displaystyle R\in {\text{SO}}(3)}$ ${\displaystyle {\text{SO}}(d)}$ ${\displaystyle d}$ ${\displaystyle t\in \mathbb {R} ^{3}}$ ${\displaystyle \epsilon _{i}\in \mathbb {R} ^{3}}$ ${\displaystyle \epsilon _{i}}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle \epsilon _{i}\sim {\mathcal {N}}(0,\sigma _{i}^{2}I_{3})}$

Nótese que cuando el factor de escala es 1 y el vector de traslación es cero, entonces la optimización recupera la formulación del problema de Wahba . A pesar de la no convexidad de la optimización ( cb.2 ) debido a la no convexidad del conjunto , el trabajo seminal de Berthold KP Horn mostró que ( cb.2 ) en realidad admite una solución de forma cerrada, al desacoplar la estimación de escala, rotación y traslación. ^[16] Resultados similares fueron descubiertos por Arun et al . ^[17] Además, para encontrar una transformación única , se requieren al menos puntos no colineales en cada conjunto de puntos. ${\displaystyle {\text{SO}}(3)}$ ${\displaystyle (l,R,t)}$ ${\displaystyle N=3}$

Más recientemente, Briales y González-Jiménez han desarrollado una relajación semidefinida utilizando la dualidad lagrangiana , para el caso en que el conjunto de modelos contiene diferentes primitivas 3D como puntos, líneas y planos (que es el caso cuando el modelo es una malla 3D). ^[18] Curiosamente, la relajación semidefinida es empíricamente estricta, es decir, se puede extraer una solución globalmente óptima certificable de la solución de la relajación semidefinida. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$

Registro robusto

Se sabe que la formulación de mínimos cuadrados ( cb.2 ) tiene un rendimiento arbitrario deficiente en presencia de valores atípicos . Una correspondencia de valores atípicos es un par de mediciones que se aparta del modelo generativo ( cb.1 ). En este caso, se puede considerar un modelo generativo diferente, como se indica a continuación: ^[19] ${\displaystyle s_{i}\leftrightarrow m_{i}}$

donde si el par th es un inlier, entonces obedece al modelo libre de valores atípicos ( cb.1 ), es decir, se obtiene de mediante una transformación espacial más un pequeño ruido; sin embargo, si el par th es un valor atípico, entonces puede ser cualquier vector arbitrario . Dado que uno no sabe qué correspondencias son valores atípicos de antemano, el registro robusto bajo el modelo generativo ( cb.3 ) es de suma importancia para la visión por computadora y la robótica implementadas en el mundo real, porque las técnicas actuales de coincidencia de características tienden a generar correspondencias altamente corruptas donde más de las correspondencias pueden ser valores atípicos. ^[20] ${\displaystyle i-}$ ${\displaystyle s_{i}\leftrightarrow m_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle m_{i}}$ ${\displaystyle i-}$ ${\displaystyle s_{i}\leftrightarrow m_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle o_{i}}$ ${\displaystyle 95\%}$

A continuación, describimos varios paradigmas comunes para el registro robusto.

Máximo consenso

El consenso máximo busca encontrar el conjunto más grande de correspondencias que sean consistentes con el modelo generativo ( cb.1 ) para alguna elección de transformación espacial . Formalmente hablando, el consenso máximo resuelve la siguiente optimización: ${\displaystyle (l,R,t)}$

donde denota la cardinalidad del conjunto . La restricción en ( cb.4 ) impone que cada par de mediciones en el conjunto interno debe tener residuos menores que un umbral predefinido . Desafortunadamente, análisis recientes han demostrado que resolver globalmente el problema (cb.4) es NP-Hard , y los algoritmos globales normalmente tienen que recurrir a técnicas de ramificación y acotación (BnB) que toman una complejidad de tiempo exponencial en el peor de los casos. ^{[21] [22] [23] [24] [25]} ${\displaystyle \vert {\mathcal {I}}\vert }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \xi }$

Aunque resolver la maximización del consenso con exactitud es difícil, existen heurísticas eficientes que funcionan bastante bien en la práctica. Una de las heurísticas más populares es el esquema de consenso de muestras aleatorias (RANSAC) . ^[26] RANSAC es un método iterativo de hipótesis y verificación. En cada iteración, el método primero toma aleatoriamente 3 muestras del número total de correspondencias y calcula una hipótesis utilizando el método de Horn, ^[16] luego el método evalúa las restricciones en ( cb.4 ) para contar cuántas correspondencias realmente concuerdan con dicha hipótesis (es decir, calcula el residuo y lo compara con el umbral para cada par de mediciones). El algoritmo termina después de haber encontrado un conjunto de consenso que tenga suficientes correspondencias, o después de haber alcanzado el número total de iteraciones permitidas. RANSAC es altamente eficiente porque el cálculo principal de cada iteración es llevar a cabo la solución de forma cerrada en el método de Horn. Sin embargo, RANSAC no es determinista y solo funciona bien en el régimen de baja relación de valores atípicos ( por ejemplo, a continuación ), porque su tiempo de ejecución crece exponencialmente con respecto a la relación de valores atípicos. ^[20] ${\displaystyle N}$ ${\displaystyle (l,R,t)}$ ${\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}}$ ${\displaystyle \xi }$ ${\displaystyle 50\%}$

Para llenar el vacío entre el rápido pero inexacto esquema RANSAC y la optimización BnB exacta pero exhaustiva, investigaciones recientes han desarrollado métodos aproximados deterministas para resolver la maximización del consenso. ^{[21] [22] [27] [23]}

Eliminación de valores atípicos

Los métodos de eliminación de valores atípicos buscan preprocesar el conjunto de correspondencias altamente corruptas antes de estimar la transformación espacial. La motivación de la eliminación de valores atípicos es reducir significativamente la cantidad de correspondencias atípicas, mientras se mantienen las correspondencias internas, de modo que la optimización sobre la transformación se vuelva más fácil y eficiente ( por ejemplo, RANSAC funciona mal cuando la relación de valores atípicos es superior, pero funciona bastante bien cuando la relación de valores atípicos es inferior ). ${\displaystyle 95\%}$ ${\displaystyle 50\%}$

Parra et al. han propuesto un método llamado Eliminación de valores atípicos garantizada (GORE) que utiliza restricciones geométricas para podar las correspondencias de valores atípicos al tiempo que garantiza la conservación de las correspondencias internas. ^[20] Se ha demostrado que GORE puede reducir drásticamente la proporción de valores atípicos, lo que puede aumentar significativamente el rendimiento de la maximización del consenso utilizando RANSAC o BnB. Yang y Carlone han propuesto construir mediciones invariantes de rotación y traducción por pares (TRIM) a partir del conjunto original de mediciones e incrustar TRIM como los bordes de un gráfico cuyos nodos son los puntos 3D. Dado que los valores internos son consistentes por pares en términos de la escala, deben formar una camarilla dentro del gráfico. Por lo tanto, el uso de algoritmos eficientes para calcular la camarilla máxima de un gráfico puede encontrar los valores internos y podar eficazmente los valores atípicos. ^[4] El método de eliminación de valores atípicos basado en la camarilla máxima también ha demostrado ser bastante útil en problemas de registro de conjuntos de puntos del mundo real. ^{[19] Parra} et al . también propusieron ideas similares de eliminación de valores atípicos . ^[28]

Estimación M

La estimación M reemplaza la función objetivo de mínimos cuadrados en ( cb.2 ) con una función de costo robusta que es menos sensible a los valores atípicos. Formalmente, la estimación M busca resolver el siguiente problema:

donde representa la elección de la función de costo robusta. Nótese que la elección recupera la estimación de mínimos cuadrados en ( cb.2 ). Las funciones de costo robustas populares incluyen la pérdida de norma, la pérdida de Huber , ^[29] la pérdida de Geman-McClure ^[30] y la pérdida de mínimos cuadrados truncados . ^{[19] [8] [4]} La estimación M ha sido uno de los paradigmas más populares para la estimación robusta en robótica y visión por computadora. ^{[31] [32]} Debido a que las funciones objetivo robustas son típicamente no convexas ( por ejemplo, la pérdida de mínimos cuadrados truncados vs. la pérdida de mínimos cuadrados), los algoritmos para resolver la estimación M no convexa se basan típicamente en la optimización local , donde primero se proporciona una estimación inicial, seguida de refinamientos iterativos de la transformación para seguir disminuyendo la función objetivo. La optimización local tiende a funcionar bien cuando la estimación inicial está cerca del mínimo global, pero también es propensa a quedarse atascada en mínimos locales si se proporciona con una inicialización deficiente. ${\displaystyle \rho (\cdot )}$ ${\displaystyle \rho (x)=x^{2}}$ ${\displaystyle \ell _{1}}$

No convexidad graduada

La no convexidad graduada (GNC) es un marco de trabajo de propósito general para resolver problemas de optimización no convexos sin inicialización. Ha logrado el éxito en las primeras aplicaciones de visión y aprendizaje automático. ^{[33] [34]} La idea clave detrás de GNC es resolver el problema no convexo difícil comenzando desde un problema convexo fácil. Específicamente, para una función de costo robusta dada , se puede construir una función sustituta con un hiperparámetro , ajustándola para aumentar gradualmente la no convexidad de la función sustituta hasta que converja a la función objetivo . ^{[34] [35]} Por lo tanto, en cada nivel del hiperparámetro , se resuelve la siguiente optimización: ${\displaystyle \rho (\cdot )}$ ${\displaystyle \rho _{\mu }(\cdot )}$ ${\displaystyle \mu }$ ${\displaystyle \rho _{\mu }(\cdot )}$ ${\displaystyle \rho (\cdot )}$ ${\displaystyle \mu }$

Black y Rangarajan demostraron que la función objetivo de cada optimización ( cb.6 ) se puede dualizar en una suma de mínimos cuadrados ponderados y una llamada función de proceso de valores atípicos sobre los pesos que determinan la confianza de la optimización en cada par de mediciones. ^[33] Utilizando la dualidad Black-Rangarajan y GNC adaptado a la función Geman-McClure, Zhou et al. desarrollaron el algoritmo de registro global rápido que es robusto frente a valores atípicos en las correspondencias. ^[30] Más recientemente, Yang et al. demostraron que el uso conjunto de GNC (adaptado a la función Geman-McClure y la función de mínimos cuadrados truncados) y la dualidad Black-Rangarajan puede conducir a un solucionador de propósito general para problemas de registro robusto, incluyendo nubes de puntos y registro de malla. ^[35] ${\displaystyle 80\%}$

Registro certificablemente robusto

Casi ninguno de los algoritmos de registro robustos mencionados anteriormente (excepto el algoritmo BnB que se ejecuta en tiempo exponencial en el peor de los casos) ofrece garantías de rendimiento , lo que significa que estos algoritmos pueden devolver estimaciones completamente incorrectas sin previo aviso. Por lo tanto, estos algoritmos no son recomendables para aplicaciones críticas para la seguridad, como la conducción autónoma.

Recientemente, Yang et al. han desarrollado el primer algoritmo de registro certificablemente robusto, denominado Estimación de mínimos cuadrados truncados y relajación semidefinida (TEASER). ^[19] Para el registro de nubes de puntos, TEASER no solo genera una estimación de la transformación, sino que también cuantifica la optimalidad de la estimación dada. TEASER adopta el siguiente estimador de mínimos cuadrados truncados (TLS):

que se obtiene eligiendo la función de costo robusta TLS , donde es una constante predefinida que determina los residuos máximos permitidos para ser considerados inliers. La función objetivo TLS tiene la propiedad de que para las correspondencias inliers ( ), se aplica la penalización de mínimos cuadrados habitual; mientras que para las correspondencias atípicas ( ), no se aplica ninguna penalización y los valores atípicos se descartan. Si la optimización TLS ( cb.7 ) se resuelve a optimalidad global, entonces es equivalente a ejecutar el método de Horn solo en las correspondencias inlier. ${\displaystyle \rho (x)=\min(x^{2},{\bar {c}}^{2})}$ ${\displaystyle {\bar {c}}^{2}}$ ${\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}}$ ${\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}>{\bar {c}}^{2}}$

Sin embargo, resolver ( cb.7 ) es bastante desafiante debido a su naturaleza combinatoria. TEASER resuelve ( cb.7 ) de la siguiente manera: (i) Construye mediciones invariantes de modo que la estimación de escala, rotación y traslación se pueda desacoplar y resolver por separado, una estrategia que está inspirada en el método original de Horn; (ii) La misma estimación TLS se aplica para cada uno de los tres subproblemas, donde el problema TLS de escala se puede resolver exactamente usando un algoritmo llamado votación adaptativa, el problema TLS de rotación se puede relajar a un programa semidefinido (SDP) donde la relajación es exacta en la práctica, ^[8] incluso con una gran cantidad de valores atípicos; el problema TLS de traslación se puede resolver usando votación adaptativa componente por componente. Una implementación rápida que aprovecha GNC se encuentra disponible en código abierto aquí. En la práctica, TEASER puede tolerar más que correspondencias de valores atípicos y se ejecuta en milisegundos. ${\displaystyle 99\%}$

Además de desarrollar TEASER, Yang et al. también prueban que, bajo algunas condiciones moderadas en los datos de la nube de puntos, la transformación estimada de TEASER tiene errores limitados con respecto a la transformación de la verdad fundamental. ^[19]

Registro simultáneo de pose y correspondencia

Punto más cercano iterativo

El algoritmo iterativo de punto más cercano (ICP) fue introducido por Besl y McKay. ^[36] El algoritmo realiza un registro rígido de manera iterativa alternando en (i) dada la transformación, encontrando el punto más cercano en para cada punto en ; y (ii) dadas las correspondencias, encontrando la mejor transformación rígida resolviendo el problema de mínimos cuadrados ( cb.2 ). Como tal, funciona mejor si la pose inicial de es suficientemente cercana a . En pseudocódigo , el algoritmo básico se implementa de la siguiente manera: ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

algoritmo  ICP( M , S )  θ  := θ 0  mientras no esté registrado: X  := ∅  para  m i ∊ T ( M , θ ):  ŝ i  := punto más cercano en S a m i  X  := X + ⟨ m i , ŝ i ⟩  θ  := mínimos_cuadrados( X ) devuelve  θ

Aquí, la función least_squaresrealiza una optimización de mínimos cuadrados para minimizar la distancia en cada uno de los pares, utilizando las soluciones de forma cerrada de Horn ^[16] y Arun. ^[17] ${\displaystyle \langle m_{i},{\hat {s}}_{i}\rangle }$

Debido a que la función de costo del registro depende de encontrar el punto más cercano en a cada punto en , puede cambiar mientras se ejecuta el algoritmo. Como tal, es difícil probar que ICP de hecho convergerá exactamente al óptimo local. ^[37] De hecho, empíricamente, ICP y EM-ICP no convergen al mínimo local de la función de costo. ^[37] No obstante, debido a que ICP es intuitivo de entender y sencillo de implementar, sigue siendo el algoritmo de registro de conjuntos de puntos más comúnmente utilizado. ^[37] Se han propuesto muchas variantes de ICP, que afectan a todas las fases del algoritmo desde la selección y coincidencia de puntos hasta la estrategia de minimización. ^{[13] [38]} Por ejemplo, el algoritmo de maximización de expectativas se aplica al algoritmo ICP para formar el método EM-ICP, y el algoritmo Levenberg-Marquardt se aplica al algoritmo ICP para formar el método LM-ICP. ^[12] ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {M}}}$

Coincidencia de puntos robusta

El emparejamiento de puntos robusto (RPM) fue introducido por Gold et al. ^[39] El método realiza el registro utilizando recocido determinista y asignación suave de correspondencias entre conjuntos de puntos. Mientras que en ICP la correspondencia generada por la heurística del vecino más cercano es binaria, RPM utiliza una correspondencia suave donde la correspondencia entre dos puntos cualesquiera puede ser cualquier valor entre 0 y 1, aunque finalmente converge a 0 o 1. Las correspondencias encontradas en RPM son siempre uno a uno, lo que no siempre es el caso en ICP. ^[14] Sea el punto n y el punto n . La matriz de emparejamiento se define como tal: ${\displaystyle m_{i}}$ ${\displaystyle i}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle s_{j}}$ ${\displaystyle j}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle \mathbf {\mu } }$

El problema se define entonces como: Dados dos conjuntos de puntos , encontrar la transformación afín y la matriz de coincidencia que mejor los relaciona. ^[39] Conocer la transformación óptima facilita la determinación de la matriz de coincidencia y viceversa. Sin embargo, el algoritmo RPM determina ambas simultáneamente. La transformación se puede descomponer en un vector de traslación y una matriz de transformación: ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle T}$ ${\displaystyle \mathbf {\mu } }$

${\displaystyle T(m)=\mathbf {A} m+\mathbf {t} }$

La matriz en 2D se compone de cuatro parámetros independientes , que son la escala, la rotación y los componentes de corte vertical y horizontal respectivamente. La función de costo es entonces: ${\displaystyle \mathbf {A} }$ ${\displaystyle \lbrace a,\theta ,b,c\rbrace }$

sujeto a , , . El término sesga el objetivo hacia una correlación más fuerte al disminuir el costo si la matriz de coincidencia tiene más unos en ella. La función sirve para regularizar la transformación afín al penalizar valores grandes de los componentes de escala y de corte: ${\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}\leq 1}$ ${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}\leq 1}$ ${\textstyle \forall ij~\mu _{ij}\in \lbrace 0,1\rbrace }$ ${\displaystyle \alpha }$ ${\displaystyle g(\mathbf {A} )}$

${\displaystyle g(\mathbf {A} (a,\theta ,b,c))=\gamma (a^{2}+b^{2}+c^{2})}$

para algún parámetro de regularización . ${\displaystyle \gamma }$

El método RPM optimiza la función de costo utilizando el algoritmo Softassign. Aquí se derivará el caso 1D. Dado un conjunto de variables donde . Se asocia una variable con cada una de ellas de manera que . El objetivo es encontrar que maximice . Esto se puede formular como un problema continuo introduciendo un parámetro de control . En el método de recocido determinista , el parámetro de control se incrementa lentamente a medida que se ejecuta el algoritmo. Sea : ${\displaystyle \lbrace Q_{j}\rbrace }$ ${\displaystyle Q_{j}\in \mathbb {R} ^{1}}$ ${\displaystyle \mu _{j}}$ ${\displaystyle Q_{j}}$ ${\textstyle \sum _{j=1}^{J}\mu _{j}=1}$ ${\displaystyle \mathbf {\mu } }$ ${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}$ ${\displaystyle \beta >0}$ ${\displaystyle \beta }$ ${\displaystyle \mathbf {\mu } }$

Esto se conoce como la función softmax . A medida que aumenta, se acerca a un valor binario como se desea en la ecuación ( rpm.1 ). El problema ahora se puede generalizar al caso 2D, donde en lugar de maximizar , se maximiza lo siguiente: ${\displaystyle \beta }$ ${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}$

dónde

${\displaystyle Q_{ij}=-(\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}-\alpha )=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}$

Esto es sencillo, excepto que ahora las restricciones en son restricciones de matriz doblemente estocásticas : y . Como tal, el denominador de la ecuación ( rpm.3 ) no se puede expresar para el caso 2D de manera simple. Para satisfacer las restricciones, es posible utilizar un resultado debido a Sinkhorn, ^[39] que establece que una matriz doblemente estocástica se obtiene a partir de cualquier matriz cuadrada con todas las entradas positivas mediante el proceso iterativo de normalizaciones alternas de filas y columnas. Por lo tanto, el algoritmo se escribe de la siguiente manera: ^[39] ${\displaystyle \mu }$ ${\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}=1}$ ${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}=1}$

algoritmo RPM2D  ${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$ t  := 0  a , θ  b , c  := 0  β  := β 0  mientras β < β f : mientras μ no ha convergido:  // actualizar los parámetros de correspondencia por softassign // aplicar el método de Sinkhorn mientras no ha convergido: // actualizar normalizando en todas las filas: // actualizar normalizando en todas las columnas: // actualizar los parámetros de pose por descenso de coordenadas actualizar θ usando una solución analítica ${\displaystyle {\hat {\mu }}_{ij}:=1+\epsilon }$      ${\displaystyle Q_{ij}:=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}$  ${\displaystyle \mu _{ij}^{0}:=\exp(\beta Q_{ij})}$    ${\displaystyle {\hat {\mu }}}$  ${\displaystyle {\hat {\mu }}}$  ${\displaystyle {\hat {\mu }}_{ij}^{1}:={\frac {{\hat {\mu }}_{ij}^{0}}{\sum _{i=1}^{M+1}{\hat {\mu }}_{ij}^{0}}}}$  ${\displaystyle {\hat {\mu }}}$  ${\displaystyle {\hat {\mu }}_{ij}^{0}:={\frac {{\hat {\mu }}_{ij}^{1}}{\sum _{j=1}^{N+1}{\hat {\mu }}_{ij}^{1}}}}$  actualizar t usando solución analítica Actualizar a, b, c usando el método de Newton.  Devolver a, b, c, θ y t. ${\displaystyle \beta :=\beta _{r}\beta }$  ${\displaystyle \gamma :={\frac {\gamma }{\beta _{r}}}}$  

donde el parámetro de control de recocido determinista se establece inicialmente en y aumenta por factor hasta que alcanza el valor máximo . Las sumas en los pasos de normalización suman y en lugar de solo y porque las restricciones en son desigualdades. Como tal, los elementos th y th son variables de holgura . ${\displaystyle \beta }$ ${\displaystyle \beta _{0}}$ ${\displaystyle \beta _{r}}$ ${\displaystyle \beta _{f}}$ ${\displaystyle M+1}$ ${\displaystyle N+1}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle \mu }$ ${\displaystyle M+1}$ ${\displaystyle N+1}$

El algoritmo también se puede ampliar para conjuntos de puntos en 3D o dimensiones superiores. Las restricciones sobre la matriz de correspondencia son las mismas en el caso 3D que en el caso 2D. Por lo tanto, la estructura del algoritmo permanece inalterada, siendo la principal diferencia la forma en que se resuelven las matrices de rotación y traslación. ^[39] ${\displaystyle \mathbf {\mu } }$

Placa delgada con ranuras para emparejamiento de puntos robusto

Animación de un registro no rígido en 2D del conjunto de puntos verdes con el conjunto de puntos magenta, corrompido por valores atípicos ruidosos. El tamaño de los círculos azules es inversamente proporcional al parámetro de control . Las líneas amarillas indican correspondencia. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle \beta }$

El algoritmo de coincidencia robusta de puntos de spline de placa delgada (TPS-RPM) de Chui y Rangarajan amplía el método RPM para realizar un registro no rígido al parametrizar la transformación como un spline de placa delgada . ^[14] Sin embargo, debido a que la parametrización del spline de placa delgada solo existe en tres dimensiones, el método no se puede extender a problemas que involucran cuatro o más dimensiones.

Correlación del núcleo

El enfoque de correlación de kernel (KC) del registro de conjuntos de puntos fue introducido por Tsin y Kanade. ^[37] En comparación con ICP, el algoritmo KC es más robusto frente a datos ruidosos. A diferencia de ICP, donde, para cada punto del modelo, solo se considera el punto de escena más cercano, aquí cada punto de escena afecta a todos los puntos del modelo. ^[37] Como tal, este es un algoritmo de registro de múltiples enlaces . Para alguna función de kernel , la correlación de kernel de dos puntos se define de la siguiente manera: ^[37] ${\displaystyle K}$ ${\displaystyle KC}$ ${\displaystyle x_{i},x_{j}}$

La función kernel elegida para el registro de conjuntos de puntos es típicamente un kernel simétrico y no negativo, similar a los utilizados en la estimación de densidad de la ventana de Parzen . El kernel gaussiano se utiliza típicamente por su simplicidad, aunque otros como el kernel de Epanechnikov y el kernel tricube pueden sustituirse. ^[37] La ​​correlación kernel de un conjunto de puntos completo se define como la suma de las correlaciones kernel de cada punto del conjunto con cada uno de los otros puntos del conjunto: ^[37] ${\displaystyle K}$ ${\displaystyle {\mathcal {\chi }}}$

El logaritmo de KC de un conjunto de puntos es proporcional, dentro de un factor constante, a la entropía de la información . Observe que el KC es una medida de la "compacidad" del conjunto de puntos; trivialmente, si todos los puntos del conjunto de puntos estuvieran en la misma ubicación, el KC se evaluaría como un valor grande. La función de costo del algoritmo de registro de conjuntos de puntos para algún parámetro de transformación se define de la siguiente manera: ${\displaystyle \theta }$

Algunas manipulaciones algebraicas dan como resultado:

La expresión se simplifica observando que es independiente de . Además, suponiendo un registro rígido, es invariante cuando cambia porque la distancia euclidiana entre cada par de puntos permanece igual bajo la transformación rígida . Por lo tanto, la ecuación anterior puede reescribirse como: ${\displaystyle KC({\mathcal {S}})}$ ${\displaystyle \theta }$ ${\displaystyle KC(T({\mathcal {M}},\theta ))}$ ${\displaystyle \theta }$

Las estimaciones de densidad del kernel se definen como:

${\displaystyle P_{\mathcal {M}}(x,\theta )={\frac {1}{M}}\sum _{m\in {\mathcal {M}}}K(x,T(m,\theta ))}$

${\displaystyle P_{\mathcal {S}}(x)={\frac {1}{N}}\sum _{s\in {\mathcal {S}}}K(x,s)}$

Se puede entonces demostrar que la función de costo es la correlación de las dos estimaciones de densidad del kernel:

Una vez establecida la función de costo , el algoritmo simplemente utiliza el descenso de gradiente para encontrar la transformación óptima. Es computacionalmente costoso calcular la función de costo desde cero en cada iteración, por lo que se utiliza una versión discreta de la ecuación de función de costo ( kc.6 ). Las estimaciones de densidad de kernel se pueden evaluar en puntos de la cuadrícula y almacenar en una tabla de búsqueda . A diferencia del ICP y los métodos relacionados, no es necesario encontrar el vecino más cercano, lo que permite que el algoritmo KC sea comparativamente simple en su implementación. ${\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}$

En comparación con ICP y EM-ICP para conjuntos de puntos 2D y 3D ruidosos, el algoritmo KC es menos sensible al ruido y da como resultado un registro correcto con mayor frecuencia. ^[37]

Modelo de mezcla gaussiana

Las estimaciones de densidad del núcleo son sumas de gaussianas y, por lo tanto, pueden representarse como modelos de mezcla gaussiana (GMM). ^[40] Jian y Vemuri utilizan la versión GMM del algoritmo de registro KC para realizar un registro no rígido parametrizado por splines de placa delgada .

Deriva de puntos coherentes

Registro rígido (con la adición de escala) de un conjunto de puntos azules en un conjunto de puntos rojos mediante el algoritmo Coherent Point Drift. Ambos conjuntos de puntos se han corrompido con puntos eliminados y puntos atípicos espurios aleatorios. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

Registro afín de un conjunto de puntos azules al conjunto de puntos rojos utilizando el algoritmo Coherent Point Drift. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

Registro no rígido de un conjunto de puntos azules en un conjunto de puntos rojos mediante el algoritmo Coherent Point Drift. Ambos conjuntos de puntos se han corrompido con puntos eliminados y puntos atípicos espurios aleatorios. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

Myronenko y Song introdujeron el método de deriva de puntos coherente (CPD, por sus siglas en inglés). ^{[13] [41]} El algoritmo adopta un enfoque probabilístico para alinear conjuntos de puntos, similar al método KC de GMM. A diferencia de los enfoques anteriores para el registro no rígido que suponen un modelo de transformación de spline de placa delgada , el CPD es agnóstico con respecto al modelo de transformación utilizado. El conjunto de puntos representa los centroides del modelo de mezcla gaussiana (GMM, por sus siglas en inglés). Cuando los dos conjuntos de puntos están alineados de manera óptima, la correspondencia es el máximo de la probabilidad posterior de GMM para un punto de datos dado. Para preservar la estructura topológica de los conjuntos de puntos, los centroides de GMM se ven obligados a moverse coherentemente como un grupo. El algoritmo de maximización de expectativas se utiliza para optimizar la función de costo. ^[13] ${\displaystyle {\mathcal {M}}}$

Sea M puntos en y N puntos en . La función de densidad de probabilidad del GMM para un punto s es: ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

donde, en D dimensiones, es la distribución gaussiana centrada en el punto . ${\displaystyle p(s|i)}$ ${\displaystyle m_{i}\in {\mathcal {M}}}$

${\displaystyle p(s|i)={\frac {1}{(2\pi \sigma ^{2})^{D/2}}}\exp {\left(-{\frac {\lVert s-m_{i}\rVert ^{2}}{2\sigma ^{2}}}\right)}}$

Las probabilidades de pertenencia son iguales para todos los componentes del GMM. El peso de la distribución uniforme se denota como . El modelo de mezcla es entonces: ${\displaystyle P(i)={\frac {1}{M}}}$ ${\displaystyle w\in [0,1]}$

Los centroides del GMM se parametrizan nuevamente mediante un conjunto de parámetros estimados maximizando la verosimilitud. Esto es equivalente a minimizar la función de verosimilitud negativa : ${\displaystyle \theta }$

donde se supone que los datos son independientes y se distribuyen de forma idéntica . La probabilidad de correspondencia entre dos puntos y se define como la probabilidad posterior del centroide del GMM dado el punto de datos: ${\displaystyle m_{i}}$ ${\displaystyle s_{j}}$

${\displaystyle P(i|s_{j})={\frac {P(i)p(s_{j}|i)}{p(s_{j})}}}$

El algoritmo de maximización de expectativas (EM) se utiliza para encontrar y . El algoritmo EM consta de dos pasos. Primero, en el paso E o paso de estimación , adivina los valores de los parámetros (valores de parámetros "antiguos") y luego utiliza el teorema de Bayes para calcular las distribuciones de probabilidad posterior de los componentes de la mezcla. Segundo, en el paso M o paso de maximización , los valores de los parámetros "nuevos" se encuentran minimizando la expectativa de la función de log-verosimilitud negativa completa, es decir, la función de costo: ${\displaystyle \theta }$ ${\displaystyle \sigma ^{2}}$ ${\displaystyle P^{\text{old}}(i,s_{j})}$

Ignorando las constantes independientes de y , la ecuación ( cpd.4 ) se puede expresar así: ${\displaystyle \theta }$ ${\displaystyle \sigma }$

dónde

${\displaystyle N_{\mathbf {P} }=\sum _{j=0}^{N}\sum _{i=0}^{M}P^{\text{old}}(i|s_{j})\leq N}$

con solo si . Las probabilidades posteriores de los componentes del GMM calculadas utilizando valores de parámetros anteriores son: ${\displaystyle N=N_{\mathbf {P} }}$ ${\displaystyle w=0}$ ${\displaystyle P^{\text{old}}}$

Minimizar la función de costo en la ecuación ( cpd.5 ) necesariamente disminuye la función de log-verosimilitud negativa E en la ecuación ( cpd.3 ) a menos que ya esté en un mínimo local. ^[13] Por lo tanto, el algoritmo se puede expresar utilizando el siguiente pseudocódigo, donde los conjuntos de puntos y se representan como matrices y y respectivamente: ^[13] ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle M\times D}$ ${\displaystyle N\times D}$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {S} }$

algoritmo CPD  ${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$ θ  := θ 0  inicializar 0 ≤ w ≤ 1  mientras no esté registrado:  // Paso E, calcular P para i ∊ [1, M ] y j ∊ [1, N ]: // Paso M, resolver para la transformación óptima { θ , σ 2 } := resolver ( S , M , P ) devolver θ ${\displaystyle \sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}}$     ${\displaystyle p_{ij}:={\frac {\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{k},\theta )\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}}$    

donde el vector es un vector columna de unos. La función difiere según el tipo de registro realizado. Por ejemplo, en el registro rígido, la salida es una escala a , una matriz de rotación y un vector de traslación . El parámetro se puede escribir como una tupla de estos: ${\displaystyle \mathbf {1} }$solve ${\displaystyle \mathbf {R} }$ ${\displaystyle \mathbf {t} }$ ${\displaystyle \theta }$

${\displaystyle \theta =\lbrace a,\mathbf {R} ,\mathbf {t} \rbrace }$

que se inicializa en uno, la matriz identidad y un vector columna de ceros:

${\displaystyle \theta _{0}=\lbrace 1,\mathbf {I} ,\mathbf {0} \rbrace }$

El conjunto de puntos alineados es:

${\displaystyle T(\mathbf {M} )=a\mathbf {M} \mathbf {R} ^{T}+\mathbf {1} \mathbf {t} ^{T}}$

La solve_rigidfunción de registro rígido puede entonces escribirse de la siguiente manera, con la derivación del álgebra explicada en el artículo de Myronenko de 2010. ^[13]

solve_rigid ( S , M , P )  N P  := 1 T P1  U , V  := svd ( A ) // la descomposición en valores singulares de A = UΣV T C  := diag(1, …, 1, det( UV T )) // diag( ξ ) es la matriz diagonal formada a partir del vector ξ R  := UCV T // tr es la traza de una matriz t  := μ s − a R μ m return { a , R , t }, σ 2 ${\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }$  ${\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }$  ${\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}$  ${\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}$  ${\displaystyle \mathbf {A} :={\hat {\mathbf {S} ^{T}}}\mathbf {P} ^{T}{\hat {\mathbf {M} }}}$        ${\displaystyle a:={\frac {\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} )}{\operatorname {tr} (\mathbf {{\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }}} )}}}$      ${\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} (\mathbf {{\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }}} )-a\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} ))}$ 

Para el registro afín, donde el objetivo es encontrar una transformación afín en lugar de una rígida, la salida es una matriz de transformación afín y una traducción tal que el conjunto de puntos alineados es: ${\displaystyle \mathbf {B} }$ ${\displaystyle \mathbf {t} }$

${\displaystyle T(\mathbf {M} )=\mathbf {M} \mathbf {B} ^{T}+\mathbf {1} \mathbf {t} ^{T}}$

La solve_affinefunción de registro rígido puede entonces escribirse de la siguiente manera, con la derivación del álgebra explicada en el artículo de Myronenko de 2010. ^[13]

solve_affine(S, M, P) NP := 1TP1  ${\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }$  ${\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }$  ${\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}$  ${\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}$  ${\displaystyle \mathbf {B} :=({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }})({\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }})^{-1}}$ t := μs − Bμm  ${\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }})-\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }}\mathbf {B} ^{T}))}$ return {B, t}, σ2

It is also possible to use CPD with non-rigid registration using a parametrization derived using calculus of variations.^[13]

Sums of Gaussian distributions can be computed in linear time using the fast Gauss transform (FGT).^[13] Consequently, the time complexity of CPD is ${\displaystyle O(M+N)}$, which is asymptotically much faster than ${\displaystyle O(MN)}$ methods.^[13]

Bayesian coherent point drift (BCPD)

A variant of coherent point drift, called Bayesian coherent point drift (BCPD), was derived through a Bayesian formulation of point set registration.^[42]BCPD has several advantages over CPD, e.g., (1) nonrigid and rigid registrations can be performed in a single algorithm, (2) the algorithm can be accelerated regardless of the Gaussianity of a Gram matrix to define motion coherence, (3) the algorithm is more robust against outliers because of a more reasonable definition of an outlier distribution. Additionally, in the Bayesian formulation, motion coherence was introduced through a prior distribution of displacement vectors, providing a clear difference between tuning parameters that control motion coherence. BCPD was further accelerated by a method called BCPD++, which is a three-step procedure composed of (1) downsampling of point sets, (2) registration of downsampled point sets, and (3) interpolation of a deformation field.^[43]The method can register point sets composed of more than 10M points while maintaining its registration accuracy.

Coherent point drift with local surface geometry (LSG-CPD)

An variant of coherent point drift called CPD with Local Surface Geometry (LSG-CPD) for rigid point cloud registration.^[44] The method adaptively adds different levels of point-to-plane penalization on top of the point-to-point penalization based on the flatness of the local surface. This results in GMM components with anisotropic covariances, instead of the isotropic covariances in the original CPD.^[13] The anisotropic covariance matrix is modeled as:

where

${\displaystyle \Sigma _{m}}$ is the anisotropic covariance matrix of the m-th point in the target set; ${\displaystyle \mathbf {n} _{m}}$ is the normal vector corresponding to the same point; ${\displaystyle \mathbf {I} }$ is an identity matrix, serving as a regularizer, pulling the problem away from ill-posedness. ${\displaystyle \alpha _{m}}$ is penalization coefficient (a modified sigmoid function), which is set adaptively to add different levels of point-to-plane penalization depending on how flat the local surface is. This is realized by evaluating the surface variation ${\displaystyle \kappa _{m}}$^[45] within the neighborhood of the m-th target point. ${\displaystyle \alpha _{max}}$ is the upper bound of the penalization.

The point cloud registration is formulated as a maximum likelihood estimation (MLE) problem and solve it with the Expectation-Maximization (EM) algorithm. In the E step, the correspondence computation is recast into simple matrix manipulations and efficiently computed on a GPU. In the M step, an unconstrained optimization on a matrix Lie group is designed to efficiently update the rigid transformation of the registration. Taking advantage of the local geometric covariances, the method shows a superior performance in accuracy and robustness to noise and outliers, compared with the baseline CPD.^[46] An enhanced runtime performance is expected thanks to the GPU accelerated correspondence calculation. An implementation of the LSG-CPD is open-sourced here.

Sorting the Correspondence Space (SCS)

This algorithm was introduced in 2013 by H. Assalih to accommodate sonar image registration.^[47] These types of images tend to have high amounts of noise, so it is expected to have many outliers in the point sets to match. SCS delivers high robustness against outliers and can surpass ICP and CPD performance in the presence of outliers. SCS doesn't use iterative optimization in high dimensional space and is neither probabilistic nor spectral. SCS can match rigid and non-rigid transformations, and performs best when the target transformation is between three and six degrees of freedom.

See also

• Point feature matching
• Point-set triangulation
• Normal distributions transform

References

1. Zhang, Ji; Singh, Sanjiv (May 2015). "Visual-lidar odometry and mapping: Low-drift, robust, and fast". 2015 IEEE International Conference on Robotics and Automation (ICRA). pp. 2174–2181. doi:10.1109/ICRA.2015.7139486. ISBN 978-1-4799-6923-4. S2CID 6054487.
2. Choi, Sungjoon; Zhou, Qian-Yi; Koltun, Vladlen (2015). "Robust reconstruction of indoor scenes" (PDF). Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR): 5556–5565.
3. Lai, Kevin; Bo, Liefeng; Ren, Xiaofeng; Fox, Dieter (May 2011). "A large-scale hierarchical multi-view RGB-D object dataset". 2011 IEEE International Conference on Robotics and Automation. pp. 1817–1824. CiteSeerX 10.1.1.190.1598. doi:10.1109/ICRA.2011.5980382. ISBN 978-1-61284-386-5. S2CID 14986048.
4. Yang, Heng; Carlone, Luca (2019). "A polynomial-time solution for robust registration with extreme outlier rates". Robotics: Science and Systems. arXiv:1903.08588. doi:10.15607/RSS.2019.XV.003. ISBN 978-0-9923747-5-4. S2CID 84186750.
5. Calli, Berk; Singh, Arjun; Bruce, James; Walsman, Aaron; Konolige, Kurt; Srinivasa, Siddhartha; Abbeel, Pieter; Dollar, Aaron M (2017-03-01). "Yale-CMU-Berkeley dataset for robotic manipulation research". The International Journal of Robotics Research. 36 (3): 261–268. doi:10.1177/0278364917700714. ISSN 0278-3649. S2CID 6522002.
6. Cadena, Cesar; Carlone, Luca; Carrillo, Henry; Latif, Yasir; Scaramuzza, Davide; Neira, José; Reid, Ian; Leonard, John J. (December 2016). "Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age". IEEE Transactions on Robotics. 32 (6): 1309–1332. arXiv:1606.05830. Bibcode:2016arXiv160605830C. doi:10.1109/TRO.2016.2624754. ISSN 1941-0468. S2CID 2596787.
7. Mur-Artal, Raúl; Montiel, J. M. M.; Tardós, Juan D. (October 2015). "ORB-SLAM: A Versatile and Accurate Monocular SLAM System". IEEE Transactions on Robotics. 31 (5): 1147–1163. arXiv:1502.00956. Bibcode:2015arXiv150200956M. doi:10.1109/TRO.2015.2463671. ISSN 1941-0468. S2CID 206775100.
8. Yang, Heng; Carlone, Luca (2019). "A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers" (PDF). Proceedings of the IEEE International Conference on Computer Vision (ICCV): 1665–1674. arXiv:1905.12536. Bibcode:2019arXiv190512536Y.
9. Newcombe, Richard A.; Izadi, Shahram; Hilliges, Otmar; Molyneaux, David; Kim, David; Davison, Andrew J.; Kohi, Pushmeet; Shotton, Jamie; Hodges, Steve; Fitzgibbon, Andrew (October 2011). "KinectFusion: Real-time dense surface mapping and tracking". 2011 10th IEEE International Symposium on Mixed and Augmented Reality. pp. 127–136. CiteSeerX 10.1.1.453.53. doi:10.1109/ISMAR.2011.6092378. ISBN 978-1-4577-2183-0. S2CID 11830123.
10. Audette, Michel A.; Ferrie, Frank P.; Peters, Terry M. (2000-09-01). "An algorithmic overview of surface registration techniques for medical imaging". Medical Image Analysis. 4 (3): 201–217. doi:10.1016/S1361-8415(00)00014-1. ISSN 1361-8415. PMID 11145309.
11. Jian, Bing; Vemuri, Baba C. (2011). "Robust Point Set Registration Using Gaussian Mixture Models". IEEE Transactions on Pattern Analysis and Machine Intelligence. 33 (8): 1633–1645. doi:10.1109/tpami.2010.223. PMID 21173443. S2CID 10923565.
12. Fitzgibbon, Andrew W. (2003). "Robust registration of 2D and 3D point sets". Image and Vision Computing. 21 (13): 1145–1153. CiteSeerX 10.1.1.335.116. doi:10.1016/j.imavis.2003.09.004.
13. Myronenko, Andriy; Song, Xubo (2010). "Point set registration: Coherent Point drift". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 2262–2275. arXiv:0905.2635. doi:10.1109/tpami.2010.46. PMID 20975122. S2CID 10809031.
14. Chui, Haili; Rangarajan, Anand (2003). "A new point matching algorithm for non-rigid registration". Computer Vision and Image Understanding. 89 (2): 114–141. CiteSeerX 10.1.1.7.4365. doi:10.1016/S1077-3142(03)00009-2.
15. Holz, Dirk; Ichim, Alexandru E.; Tombari, Federico; Rusu, Radu B.; Behnke, Sven (2015). "Registration with the Point Cloud Library: A Modular Framework for Aligning in 3-D". IEEE Robotics Automation Magazine. 22 (4): 110–124. doi:10.1109/MRA.2015.2432331. S2CID 2621807.
16. Horn, Berthold K. P. (1987-04-01). "Closed-form solution of absolute orientation using unit quaternions". JOSA A. 4 (4): 629–642. Bibcode:1987JOSAA...4..629H. doi:10.1364/JOSAA.4.000629. ISSN 1520-8532. S2CID 11038004.
17. Arun, K. S.; Huang, T. S.; Blostein, S. D. (September 1987). "Least-Squares Fitting of Two 3-D Point Sets". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-9 (5): 698–700. doi:10.1109/TPAMI.1987.4767965. ISSN 1939-3539. PMID 21869429. S2CID 8724100.
18. Briales, Jesus; Gonzalez-Jimenez, Javier (July 2017). "Convex Global 3D Registration with Lagrangian Duality". 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 5612–5621. doi:10.1109/CVPR.2017.595. hdl:10630/14599. ISBN 978-1-5386-0457-1. S2CID 11549421.
19. Yang, Heng; Shi, Jingnan; Carlone, Luca (2020-01-21). "TEASER: Fast and Certifiable Point Cloud Registration". arXiv:2001.07715 [cs.RO].
20. Parra Bustos, Álvaro; Chin, Tat-Jun (December 2018). "Guaranteed Outlier Removal for Point Cloud Registration with Correspondences". IEEE Transactions on Pattern Analysis and Machine Intelligence. 40 (12): 2868–2882. arXiv:1711.10209. doi:10.1109/TPAMI.2017.2773482. ISSN 1939-3539. PMID 29990122. S2CID 3331003.
21. Chin, Tat-Jun; Suter, David (2017-02-27). "The Maximum Consensus Problem: Recent Algorithmic Advances". Synthesis Lectures on Computer Vision. 7 (2): 1–194. doi:10.2200/s00757ed1v01y201702cov011. ISSN 2153-1056.
22. Wen, Fei; Ying, Rendong; Gong, Zheng; Liu, Peilin (February 2020). "Efficient Algorithms for Maximum Consensus Robust Fitting". IEEE Transactions on Robotics. 36 (1): 92–106. doi:10.1109/TRO.2019.2943061. ISSN 1941-0468. S2CID 209976632.
23. Cai, Zhipeng; Chin, Tat-Jun; Koltun, Vladlen (2019). "Consensus Maximization Tree Search Revisited". Proceedings of IEEE International Conference on Computer Vision (ICCV): 1637–1645. arXiv:1908.02021. Bibcode:2019arXiv190802021C.
24. Bazin, Jean-Charles; Seo, Yongduek; Pollefeys, Marc (2013). "Globally Optimal Consensus Set Maximization through Rotation Search". In Lee, Kyoung Mu; Matsushita, Yasuyuki; Rehg, James M.; Hu, Zhanyi (eds.). Computer Vision – ACCV 2012. Lecture Notes in Computer Science. Vol. 7725. Berlin, Heidelberg: Springer. pp. 539–551. doi:10.1007/978-3-642-37444-9_42. ISBN 978-3-642-37444-9.
25. Hartley, Richard I.; Kahl, Fredrik (2009-04-01). "Global Optimization through Rotation Space Search". International Journal of Computer Vision. 82 (1): 64–79. doi:10.1007/s11263-008-0186-9. hdl:1885/50831. ISSN 1573-1405. S2CID 509788.
26. Fischler, Martin; Bolles, Robert (1981). "Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography". Communications of the ACM. 24 (6): 381–395. doi:10.1145/358669.358692. S2CID 972888.
27. Le, Huu Minh; Chin, Tat-Jun; Eriksson, Anders; Do, Thanh-Toan; Suter, David (2019). "Deterministic Approximate Methods for Maximum Consensus Robust Fitting". IEEE Transactions on Pattern Analysis and Machine Intelligence. 43 (3): 842–857. arXiv:1710.10003. doi:10.1109/TPAMI.2019.2939307. ISSN 1939-3539. PMID 31494545. S2CID 29346470.
28. Bustos, Alvaro Parra; Chin, Tat-Jun; Neumann, Frank; Friedrich, Tobias; Katzmann, Maximilian (2019-02-04). "A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints". arXiv:1902.01534 [cs.CV].
29. Huber, Peter J.; Ronchetti, Elvezio M. (2009-01-29). Robust Statistics. Wiley Series in Probability and Statistics. Hoboken, NJ, USA: John Wiley & Sons, Inc. doi:10.1002/9780470434697. ISBN 978-0-470-43469-7.
30. Zhou, Qian-Yi; Park, Jaesik; Koltun, Vladlen (2016). "Fast Global Registration". In Leibe, Bastian; Matas, Jiri; Sebe, Nicu; Welling, Max (eds.). Computer Vision – ECCV 2016. Lecture Notes in Computer Science. Vol. 9906. Cham: Springer International Publishing. pp. 766–782. doi:10.1007/978-3-319-46475-6_47. ISBN 978-3-319-46475-6. S2CID 27362942.
31. MacTavish, Kirk; Barfoot, Timothy D. (2015). "At all Costs: A Comparison of Robust Cost Functions for Camera Correspondence Outliers". 2015 12th Conference on Computer and Robot Vision. pp. 62–69. doi:10.1109/CRV.2015.52. ISBN 978-1-4799-1986-4. S2CID 9305263.
32. Bosse, Michael; Agamennoni, Gabriel; Gilitschenski, Igor (2016). "Robust Estimation and Applications in Robotics". Foundations and Trends in Robotics. 4 (4). now: 225–269. doi:10.1561/2300000047.
33. Black, Michael J.; Rangarajan, Anand (1996-07-01). "On the unification of line processes, outlier rejection, and robust statistics with applications in early vision". International Journal of Computer Vision. 19 (1): 57–91. doi:10.1007/BF00131148. ISSN 1573-1405. S2CID 7510079.
34. Blake, Andrew; Zisserman, Andrew (1987). Visual reconstruction. The MIT Press. ISBN 9780262524063.
35. Yang, Heng; Antonante, Pasquale; Tzoumas, Vasileios; Carlone, Luca (2020). "Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection". IEEE Robotics and Automation Letters. 5 (2): 1127–1134. arXiv:1909.08605. doi:10.1109/LRA.2020.2965893. ISSN 2377-3774. S2CID 202660784.
36. Besl, Paul; McKay, Neil (1992). "A Method for Registration of 3-D Shapes". IEEE Transactions on Pattern Analysis and Machine Intelligence. 14 (2): 239–256. Bibcode:1992SPIE.1611..586B. doi:10.1109/34.121791.
37. Tsin, Yanghai; Kanade, Takeo (2004). "A Correlation-Based Approach to Robust Point Set Registration". Computer Vision - ECCV 2004. Lecture Notes in Computer Science. Vol. 3023. Springer Berlin Heidelberg. pp. 558–569. CiteSeerX 10.1.1.156.6729. doi:10.1007/978-3-540-24672-5_44. ISBN 978-3-540-21982-8. {{cite book}}: |journal= ignored (help)
38. Rusinkiewicz, Szymon; Levoy, Marc (2001). Efficient variants of the ICP algorithm. Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling, 2001. IEEE. pp. 145–152. doi:10.1109/IM.2001.924423.
39. Gold, Steven; Rangarajan, Anand; Lu, Chien-Ping; Suguna, Pappu; Mjolsness, Eric (1998). "New algorithms for 2d and 3d point matching:: pose estimation and correspondence". Pattern Recognition. 38 (8): 1019–1031. Bibcode:1998PatRe..31.1019G. doi:10.1016/S0031-3203(98)80010-1.
40. Jian, Bing; Vemuri, Baba C. (2005). A robust algorithm for point set registration using mixture of Gaussians. Tenth IEEE International Conference on Computer Vision 2005. Vol. 2. pp. 1246–1251.
41. Myronenko, Andriy; Song, Xubo; Carriera-Perpinán, Miguel A. (2006). "Non-rigid point set registration: Coherent point drift". Advances in Neural Information Processing Systems. 19: 1009–1016. Retrieved 31 May 2014.
42. Hirose, Osamu (2021). "A Bayesian formulation of coherent point drift". IEEE Transactions on Pattern Analysis and Machine Intelligence. 43 (7): 2269–2286. doi:10.1109/TPAMI.2020.2971687. PMID 32031931.
43. Hirose, Osamu (2021). "Acceleration of non-rigid point set registration with downsampling and Gaussian process regression". IEEE Transactions on Pattern Analysis and Machine Intelligence. 43 (8): 2858–2865. doi:10.1109/TPAMI.2020.3043769. PMID 33301401.
44. Liu, Weixiao; Wu, Hongtao; Chirikjian, Gregory S. (2021). "LSG-CPD: Coherent Point Drift with Local Surface Geometry for Point Cloud Registration". 2021 IEEE/CVF International Conference on Computer Vision (ICCV). pp. 15273–15282. arXiv:2103.15039. doi:10.1109/ICCV48922.2021.01501. ISBN 978-1-6654-2812-5. S2CID 232404480.
45. Pauly, M.; Gross, M.; Kobbelt, L.P. (2002). "Efficient simplification of point-sampled surfaces". IEEE Visualization, 2002. VIS 2002 (PDF). pp. 163–170. doi:10.1109/VISUAL.2002.1183771. ISBN 0-7803-7498-3. S2CID 14952977.
46. Liu, Weixiao; Wu, Hongtao; Chirikjian, Gregory S. (2021). "LSG-CPD: Coherent Point Drift with Local Surface Geometry for Point Cloud Registration". 2021 IEEE/CVF International Conference on Computer Vision (ICCV). pp. 15273–15282. arXiv:2103.15039. doi:10.1109/ICCV48922.2021.01501. ISBN 978-1-6654-2812-5. S2CID 232404480.
47. Assalih, Hassan. (2013). "Capítulo 6: Ordenamiento del espacio de correspondencia" (PDF) . Reconstrucción 3D y estimación de movimiento mediante sonar de visión hacia adelante (Ph.D.). Universidad Heriot-Watt.

Enlaces externos

• Implementación de referencia de coincidencia de puntos robusta de spline de placa delgada
• Implementación de referencia del registro del conjunto de puntos de correlación del núcleo
• Implementación de referencia de la deriva de puntos coherentes
• Implementación de referencia de las variantes del ICP
• Implementación de referencia de la deriva de puntos coherente bayesiana
• Implementación de referencia de LSG-CPD