Registro de puntos

Proceso de búsqueda de una transformación espacial que alinee dos nubes de puntos.

El registro de conjuntos de puntos es el proceso de alinear dos conjuntos de puntos. Aquí, el pescado azul se registra frente al pescado rojo.

En visión por computadora , 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 ( p. ej., 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 (o marco de coordenadas) globalmente consistente y mapear una nueva medición a un conjunto de datos conocido para identificar características o estimar su pose . Los datos sin procesar de nubes de puntos 3D generalmente se obtienen de cámaras Lidar y RGB-D . Las nubes de puntos 3D también se pueden generar a partir de algoritmos de visión por computadora como la triangulación , el ajuste de paquetes y, más recientemente, la estimación de la profundidad de la imagen monocular mediante el aprendizaje profundo . Para el registro de conjunto 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 mediante 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]} costura panorámica , ^[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 escalado ni traslació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 usando una variante del punto más cercano iterativo.

El problema se puede resumir 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 ( p. ej., 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 del "modelo" en movimiento de modo que se minimice la diferencia (normalmente definida en el sentido de distancia euclidiana puntual ) entre el conjunto de "escena" estático y el conjunto . En otras palabras, se desea un mapeo desde hasta que produzca la mejor alineación entre el conjunto "modelo" transformado y el conjunto "escena". El mapeo puede consistir en una transformación rígida o no rígida. El modelo de transformación se puede escribir como , mediante el cual el conjunto de puntos del modelo registrado 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}$

La salida de un algoritmo de registro de conjunto de puntos es, por lo tanto, la transformación óptima que está mejor alineada , de acuerdo con 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 el vector 2-norm , 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 equivale 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 denomina registro por correspondencia . Por otro lado, si se desconocen las correspondencias, entonces se requiere la optimización para descubrir conjuntamente las correspondencias y la transformación. Este tipo de registro se denomina registro de pose simultánea y de 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. Normalmente, dicha transformación consiste en traslación y rotación . ^[12] En casos excepcionales, el punto establecido también puede reflejarse. En robótica y visión por computadora, 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 normalmente 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 se puede parametrizar como una placa spline delgada . ^{[14] [13]}

Otros tipos

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

PCL (Biblioteca de nube de puntos) 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 correspondencia suponen que se dan las supuestas correspondencias para cada punto . Por lo tanto, llegamos a un escenario donde se dan conjuntos de puntos y puntos y se dan las correspondencias . ${\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 sencillo, se puede suponer que todas las correspondencias son correctas, es decir, 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 supone), 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 ( p. ej., ruido gaussiano ). Específicamente, si se supone que el ruido sigue una distribución gaussiana isotrópica 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})}$

Tenga en cuenta que cuando el factor de escala es 1 y el vector de traducció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 fundamental de Berthold KP Horn demostró 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] Arun} et al descubrieron resultados similares . ^[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 a partir 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 ) funciona arbitrariamente mal en presencia de valores atípicos . Una correspondencia atípica es un par de mediciones que se apartan del modelo generativo ( cap.1 ). En este caso, se puede considerar un modelo generativo diferente de la siguiente manera: ^[19] ${\displaystyle s_{i}\leftrightarrow m_{i}}$

donde si el par es un valor interno, entonces obedece al modelo libre de valores atípicos ( cb.1 ), es decir, se obtiene mediante una transformación espacial más un pequeño ruido; sin embargo, si el par es un valor atípico, entonces puede ser cualquier vector arbitrario . Dado que no se sabe de antemano qué correspondencias son valores atípicos, 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 un registro sólido.

Máximo consenso

El consenso máximo busca encontrar el mayor conjunto de correspondencias que sean consistentes con el modelo generativo ( cb.1 ) para alguna elección de transformación espacial . Formalmente hablando, el máximo consenso 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 interior debe tener residuos menores que un umbral predefinido . Desafortunadamente, análisis recientes han demostrado que la resolución global del problema (cb.4) es NP-Hard , y los algoritmos globales generalmente tienen que recurrir a técnicas de ramificación y unión (BnB) que toman 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 exactamente la maximización del consenso 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 Muestra Aleatoria (RANSAC) . ^[26] RANSAC es un método iterativo de hipótesis y verificación. En cada iteración, el método primero toma una muestra aleatoria de 3 del número total de correspondencias y calcula una hipótesis usando 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 tal hipótesis (es decir, calcula el residual y lo compara con el umbral para cada par de mediciones). El algoritmo finaliza después de haber encontrado un conjunto de consenso que tiene 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 realizar 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 índice de valores atípicos bajo ( por ejemplo, a continuación ), porque su tiempo de ejecución crece exponencialmente con respecto al índice 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 esquema RANSAC rápido pero inexacto 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 el número de correspondencias atípicas, manteniendo al mismo tiempo las correspondencias internas, de modo que la optimización de la transformación se vuelva más fácil y más 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 superior). Esta abajo ). ${\displaystyle 95\%}$ ${\displaystyle 50\%}$

Parra et al. han propuesto un método llamado Eliminación garantizada de valores atípicos (GORE) que utiliza restricciones geométricas para podar las correspondencias atípicas y al mismo tiempo garantiza preservar 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 traslación y rotación (TRIM) por pares 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 interiores son consistentes por pares en términos de 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 interiores y podar eficazmente los valores atípicos. ^[4] El método de eliminación de valores atípicos basado en la máxima camarilla 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 costos 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 costos robusta. Tenga en cuenta que al elegir se recupera la estimación de mínimos cuadrados en ( cb.2 ). Las funciones de costos robustas populares incluyen pérdida de norma, pérdida de Huber , ^[29] pérdida de Geman-McClure ^[30] y 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 generalmente no son convexas ( por ejemplo, la pérdida de mínimos cuadrados truncada versus la pérdida de mínimos cuadrados), los algoritmos para resolver la estimación M no convexa generalmente se basan en la optimización local , donde primero se 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 los mínimos locales si se proporciona 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 propósito general para resolver problemas de optimización no convexos sin inicialización. Ha logrado el éxito en aplicaciones de visión temprana y aprendizaje automático. ^{[33] [34]} La idea clave detrás de GNC es resolver el problema difícil no convexo comenzando desde un problema convexo fácil. Específicamente, para una función de costos robusta dada , se puede construir una función sustituta con un hiperparámetro , ajuste que puede aumentar gradualmente la no convexidad de la función sustituta hasta que converja con 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. desarrolló el algoritmo de registro global rápido que es robusto contra valores atípicos en las correspondencias. ^[30] Más recientemente, Yang et al. demostró 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 robustos, incluidas las nubes de puntos y el registro de malla. ^[35] ${\displaystyle 80\%}$

Registro certificablemente sólido

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) viene con 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 deseables para aplicaciones críticas para la seguridad como la conducción autónoma.

Muy recientemente, Yang et al. ha 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 optimización 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 de TLS , donde es una constante predefinida que determina los residuos máximos permitidos para ser considerados valores internos. La función objetivo TLS tiene la propiedad de que para correspondencias internas ( ), 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 hasta la optimización global, entonces es equivalente a ejecutar el método de Horn solo en las correspondencias internas. ${\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 manera 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 de Horn original; (ii) Se aplica la misma estimación TLS 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 exacto en la práctica, ^[8] incluso con una gran cantidad de valores atípicos; El problema de traducción TLS se puede resolver mediante votación adaptativa por componentes. Aquí se encuentra una implementación rápida que aprovecha GNC y es de código abierto. En la práctica, TEASER puede tolerar más que correspondencias atípicas y se ejecuta en milisegundos. ${\displaystyle 99\%}$

Además de desarrollar TEASER, Yang et al. También prueba que, bajo algunas condiciones leves en los datos de la nube de puntos, la transformación estimada de TEASER tiene errores acotados de la transformación de la verdad terrestre. ^[19]

Registro simultáneo de pose y correspondencia.

Punto más cercano iterativo

Besl y McKay introdujeron el algoritmo iterativo del punto más cercano (ICP). ^[36] El algoritmo realiza un registro rígido de forma iterativa alternando en (i) dada la transformación, encontrando el punto más cercano en para cada punto en ; y (ii) dadas las correspondencias, encontrar 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 lo 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 a cada punto en , puede cambiar a medida que se ejecuta el algoritmo. Como tal, es difícil demostrar que el PIC 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 costos. ^[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 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 sólida

Gold et al. introdujeron el emparejamiento robusto de puntos (RPM). ^[39] El método realiza el registro mediante 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 de 0 a 1, aunque finalmente converge a 0 o 1. Las correspondencias encontradas en RPM es siempre uno a uno, lo que no siempre es el caso en ICP. ^[14] Sea el enésimo punto en y sea el enésimo punto en . La matriz de coincidencias se define como tal: ${\displaystyle m_{i}}$ ${\displaystyle i}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle s_{j}}$ ${\displaystyle j}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle \mathbf {\mu } }$

Luego, el problema se define como: Dados dos conjuntos de puntos , encuentre la transformación afín y la matriz de coincidencia que mejor los relacione. ^[39] Conocer la transformación óptima facilita la determinación de la matriz de coincidencia, y viceversa. Sin embargo, el algoritmo RPM determina ambos simultáneamente. La transformación se puede descomponer en un vector de traducció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 separados , que son escala, rotación y componentes de corte vertical y horizontal respectivamente. La función de costos 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. La función sirve para regularizar la transformación afín penalizando valores grandes de los componentes de escala y 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 costos utilizando el algoritmo Softassign. El caso 1D se derivará aquí. Dado un conjunto de variables donde . A cada uno se le asocia una variable tal 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 aumenta lentamente a medida que se ejecuta el algoritmo. Permitir : ${\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 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 de son restricciones matriciales doblemente estocásticas : y . Como tal, el denominador de la ecuación ( rpm.3 ) no se puede expresar simplemente para el caso 2D. Para satisfacer las restricciones, es posible utilizar un resultado debido a Sinkhorn, ^[39] que establece que se obtiene una matriz doblemente estocástica a partir de cualquier matriz cuadrada con todas las entradas positivas mediante el proceso iterativo de normalización alterna de filas y columnas. Por tanto, el algoritmo se escribe como tal: ^[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:  // actualiza los parámetros de correspondencia mediante softassign // aplica 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 una 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 y aumenta factorialmente hasta alcanzar el valor máximo . Las sumas en los pasos de normalización suman a y en lugar de justo y porque las restricciones son desigualdades. Como tales, los elementos th y th son variables flojas . ${\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 de la matriz de correspondencia son las mismas en el caso 3D que en el caso 2D. Por tanto, la estructura del algoritmo permanece sin cambios, siendo la principal diferencia cómo se resuelven las matrices de rotación y traslación. ^[39] ${\displaystyle \mathbf {\mu } }$

Coincidencia de puntos robusta con estrías de placa delgada

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

El algoritmo de coincidencia de puntos robustos de spline de placa delgada (TPS-RPM) de Chui y Rangarajan aumenta el método RPM para realizar un registro no rígido al parametrizar la transformación como una spline de placa delgada . ^[14] Sin embargo, debido a que la parametrización 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

Tsin y Kanade introdujeron el enfoque de correlación del núcleo (KC) para el registro de conjuntos de puntos. ^[37] En comparación con ICP, el algoritmo KC es más robusto contra datos ruidosos. A diferencia de ICP, donde, para cada punto del modelo, solo se considera el punto de la escena más cercano, aquí cada punto de la escena afecta a cada punto del modelo. ^[37] Como tal, se trata de un algoritmo de registro de enlaces múltiples . Para algunas funciones del núcleo , la correlación del núcleo de dos puntos se define así: ^[37] ${\displaystyle K}$ ${\displaystyle KC}$ ${\displaystyle x_{i},x_{j}}$

La función kernel elegida para el registro del conjunto de puntos suele ser un kernel simétrico y no negativo, similar a los utilizados en la estimación de densidad de la ventana de Parzen . Se suele utilizar el núcleo gaussiano por su simplicidad, aunque se pueden sustituir por otros como el núcleo de Epanechnikov y el núcleo tricube. ^[37] La ​​correlación del núcleo de un conjunto de puntos completo se define como la suma de las correlaciones del núcleo de cada punto del conjunto con todos los demás 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 así: ${\displaystyle \theta }$

Alguna manipulación algebraica produce:

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

Las estimaciones de densidad del núcleo 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)}$

Luego se puede demostrar que la función de costo es la correlación de las dos estimaciones de densidad del núcleo:

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 la función de costo ( kc.6 ). Las estimaciones de densidad del núcleo pueden evaluarse en puntos de la cuadrícula y almacenarse en una tabla de búsqueda . A diferencia del ICP y métodos relacionados, no es necesario encontrar el vecino más cercano, lo que permite que el algoritmo KC sea comparativamente simple de implementar. ${\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 gaussianos 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 estrías de placa delgada .

Deriva de puntos coherentes

Registro rígido (con la adición de escala) de un punto azul establecido en el punto rojo establecido utilizando el algoritmo Coherent Point Drift. Ambos conjuntos de puntos se han corrompido con puntos eliminados y puntos atípicos falsos aleatorios. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

Registro afín de un punto azul establecido con el punto rojo establecido utilizando el algoritmo Coherent Point Drift. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

Registro no rígido de un punto azul establecido en el punto rojo establecido utilizando el algoritmo Coherent Point Drift. Ambos conjuntos de puntos se han corrompido con puntos eliminados y puntos atípicos falsos aleatorios. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {S}}}$

Myronenko y Song introdujeron la deriva de puntos coherentes (CPD). ^{[13] [41]} El algoritmo adopta un enfoque probabilístico para alinear conjuntos de puntos, similar al método GMM KC. A diferencia de enfoques anteriores de registro no rígido que asumen un modelo de transformación spline de placa delgada , 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). 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 determinado. Para preservar la estructura topológica de los conjuntos de puntos, los centroides del GMM se ven obligados a moverse coherentemente como grupo. El algoritmo de maximización de expectativas se utiliza para optimizar la función de costos. ^[13] ${\displaystyle {\mathcal {M}}}$

Sean M puntos y N puntos . La función de densidad de probabilidad 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 membresía son iguales para todos los componentes de 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 de GMM se reparametrizan mediante un conjunto de parámetros estimados maximizando la probabilidad. Esto equivale a minimizar la función de probabilidad logarítmica negativa : ${\displaystyle \theta }$

donde se supone que los datos son independientes y están distribuidos idénticamente . La probabilidad de correspondencia entre dos puntos y se define como la probabilidad posterior del centroide 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 posteriores de los componentes de la mezcla. En segundo lugar, en el paso M o paso de maximización , los "nuevos" valores de los parámetros se encuentran minimizando la expectativa de la función de probabilidad logarítmica negativa completa, es decir, la función de costo: ${\displaystyle \theta }$ ${\displaystyle \sigma ^{2}}$ ${\displaystyle P^{\text{old}}(i,s_{j})}$

Haciendo caso omiso de 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 sólo si . Las probabilidades posteriores de los componentes de 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 costos en la ecuación ( cpd.5 ) necesariamente disminuye la función de probabilidad logarítmica negativa E en la ecuación ( cpd.3 ) a menos que ya esté en un mínimo local. ^[13] Así, el algoritmo se puede expresar utilizando el siguiente pseudocódigo, donde los conjuntos de puntos y se representan como matrices 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  inicializa 0 ≤ w ≤ 1  mientras no está registrado:  // Paso E, calcula P para i ∊ [1, M ] y j ∊ [1, N ]: // Paso M, resuelve 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 a 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 para el registro rígido se puede escribir 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, el resultado es una matriz de transformación afín y una traducción tal que el conjunto de puntos alineados sea: ${\displaystyle \mathbf {B} }$ ${\displaystyle \mathbf {t} }$

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

La solve_affinefunción para el registro rígido se puede escribir 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 )  N P  := 1 T P1  t  := μ s − B μ m return { B , 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 {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}}$   ${\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}))}$ 

También es posible utilizar CPD con registro no rígido mediante una parametrización derivada mediante cálculo de variaciones . ^[13]

Las sumas de las distribuciones gaussianas se pueden calcular en tiempo lineal utilizando la transformada rápida de Gauss (FGT). ^[13] En consecuencia, la complejidad temporal de CPD es , que es asintóticamente mucho más rápida que los métodos. ^[13] ${\displaystyle O(M+N)}$ ${\displaystyle O(MN)}$

Deriva del punto coherente bayesiano (BCPD)

Una variante de la deriva de puntos coherente, llamada deriva de puntos coherente bayesiana (BCPD), se derivó a través de una formulación bayesiana de registro de conjuntos de puntos. ^[42] BCPD tiene varias ventajas sobre CPD, por ejemplo, (1) los registros rígidos y no rígidos se pueden realizar en un solo algoritmo, (2) el algoritmo se puede acelerar independientemente de la gaussianidad de una matriz de Gram para definir la coherencia del movimiento, (3 ) el algoritmo es más robusto contra valores atípicos debido a una definición más razonable de una distribución de valores atípicos. Además, en la formulación bayesiana, la coherencia del movimiento se introdujo mediante una distribución previa de los vectores de desplazamiento, lo que proporciona una clara diferencia entre los parámetros de ajuste que controlan la coherencia del movimiento. BCPD se aceleró aún más mediante un método llamado BCPD++, que es un procedimiento de tres pasos compuesto por (1) reducción de muestreo de conjuntos de puntos, (2) registro de conjuntos de puntos reducidos y (3) interpolación de un campo de deformación. ^[43] El método puede registrar conjuntos de puntos compuestos por más de 10 millones de puntos manteniendo su precisión de registro.

Deriva de puntos coherente con geometría de superficie local (LSG-CPD)

Una variante de la deriva de puntos coherente llamada CPD con geometría de superficie local (LSG-CPD) para el registro de nubes de puntos rígidas. ^[44] El método agrega de forma adaptativa diferentes niveles de penalización de punto a plano además de la penalización de punto a punto en función de la planitud de la superficie local. Esto da como resultado componentes GMM con covarianzas anisotrópicas, en lugar de las covarianzas isotrópicas del CPD original. ^[13] La matriz de covarianza anisotrópica se modela como:

dónde

${\displaystyle \Sigma _{m}}$es la matriz de covarianza anisotrópica del punto m en el conjunto de objetivos; es el vector normal correspondiente al mismo punto; es una matriz de identidad, que sirve como regularizador, alejando el problema del mal planteamiento. es el coeficiente de penalización (una función sigmoidea modificada), que se establece de forma adaptativa para agregar diferentes niveles de penalización de punto a plano dependiendo de qué tan plana sea la superficie local. Esto se logra evaluando la variación de la superficie ^[45] dentro de la vecindad del punto objetivo m. es el límite superior de la penalización. ${\displaystyle \mathbf {n} _{m}}$ ${\displaystyle \mathbf {I} }$ ${\displaystyle \alpha _{m}}$ ${\displaystyle \kappa _{m}}$ ${\displaystyle \alpha _{max}}$

El registro de la nube de puntos se formula como un problema de estimación de máxima verosimilitud (MLE) y se resuelve con el algoritmo de Maximización de Expectativas (EM). En el paso E, el cálculo de la correspondencia se transforma en manipulaciones matriciales simples y se calcula de manera eficiente en una GPU. En el paso M, se diseña una optimización sin restricciones en un grupo de Lie matricial para actualizar de manera eficiente la transformación rígida del registro. Aprovechando las covarianzas geométricas locales, el método muestra un rendimiento superior en precisión y robustez al ruido y los valores atípicos, en comparación con el CPD de referencia. ^[46] Se espera un rendimiento de tiempo de ejecución mejorado gracias al cálculo de correspondencia acelerado por GPU. Aquí se encuentra una implementación de código abierto de LSG-CPD.

Ordenar el espacio de correspondencia (SCS)

Este algoritmo fue introducido en 2013 por H. Assalih para adaptarse al registro de imágenes de sonar. ^[47] Este tipo de imágenes tienden a tener grandes cantidades de ruido, por lo que se espera que haya muchos valores atípicos en los conjuntos de puntos para coincidir. SCS ofrece una gran solidez frente a valores atípicos y puede superar el rendimiento de ICP y CPD en presencia de valores atípicos. SCS no utiliza optimización iterativa en espacios de alta dimensión y no es probabilístico ni espectral. SCS puede igualar transformaciones rígidas y no rígidas y funciona mejor cuando la transformación objetivo tiene entre tres y seis grados de libertad .

Ver también

• Coincidencia de características de puntos
• Triangulación de puntos
• Las distribuciones normales se transforman

Referencias

1. Zhang, Ji; Singh, Sanjiv (mayo de 2015). "Mapeo y odometría visual-lidar: baja deriva, robusto y rápido". Conferencia Internacional IEEE 2015 sobre Robótica y Automatización (ICRA) . págs. 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). "Reconstrucción robusta de escenas interiores" (PDF) . Actas de la Conferencia IEEE sobre visión por computadora y reconocimiento de patrones (CVPR) : 5556–5565.
3. Lai, Kevin; Bo, Liefeng; Ren, Xiaofeng; Fox, Dieter (mayo de 2011). "Un conjunto de datos de objetos RGB-D de vistas múltiples jerárquicas a gran escala". Conferencia Internacional IEEE 2011 sobre Robótica y Automatización . págs. 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). "Una solución de tiempo polinomial para un registro sólido con tasas de valores atípicos extremos". Robótica: ciencia y sistemas . 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, Aarón; Konolige, Kurt; Srinivasa, Siddhartha; Abbeel, Pieter; Dólar, Aaron M (1 de marzo de 2017). "Conjunto de datos de Yale-CMU-Berkeley para la investigación de manipulación robótica". La Revista Internacional de Investigación en Robótica . 36 (3): 261–268. doi :10.1177/0278364917700714. ISSN  0278-3649. S2CID  6522002.
6. Cadena, César; Carlone, Luca; Carrillo, Enrique; Latif, Yasir; Scaramuzza, Davide; Neira, José; Reid, Ian; Leonard, John J. (diciembre de 2016). "Pasado, presente y futuro de la localización y el mapeo simultáneos: hacia la era de la percepción sólida". Transacciones IEEE sobre robótica . 32 (6): 1309-1332. arXiv : 1606.05830 . Código Bib : 2016arXiv160605830C. doi :10.1109/TRO.2016.2624754. ISSN  1941-0468. S2CID  2596787.
7. Mur-Artal, Raúl; Montiel, JMM; Tardós, Juan D. (octubre 2015). "ORB-SLAM: un sistema SLAM monocular versátil y preciso". Transacciones IEEE sobre robótica . 31 (5): 1147-1163. arXiv : 1502.00956 . Código Bib : 2015arXiv150200956M. doi :10.1109/TRO.2015.2463671. ISSN  1941-0468. S2CID  206775100.
8. Yang, Heng; Carlone, Luca (2019). "Una solución certificablemente óptima basada en cuaterniones para el problema de Wahba con valores atípicos" (PDF) . Actas de la Conferencia Internacional IEEE sobre Visión por Computadora (ICCV) : 1665–1674. arXiv : 1905.12536 . Código Bib : 2019arXiv190512536Y.
9. Newcombe, Richard A.; Izadi, Shahram; Hilliges, Otmar; Molyneaux, David; Kim, David; Davison, Andrew J.; Kohi, Pushmeet; Shotton, Jamie; Hodges, Steve; Fitzgibbon, Andrew (octubre de 2011). "KinectFusion: mapeo y seguimiento de superficies densas en tiempo real". 2011 Décimo Simposio Internacional IEEE sobre Realidad Mixta y Aumentada . págs. 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. (1 de septiembre de 2000). "Una descripción algorítmica de las técnicas de registro de superficies para imágenes médicas". Análisis de Imágenes Médicas . 4 (3): 201–217. doi :10.1016/S1361-8415(00)00014-1. ISSN  1361-8415. PMID  11145309.
11. Jian, Bing; Vemuri, Baba C. (2011). "Registro robusto de conjuntos de puntos utilizando modelos de mezcla gaussiana". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 33 (8): 1633-1645. doi :10.1109/tpami.2010.223. PMID  21173443. S2CID  10923565.
12. Fitzgibbon, Andrew W. (2003). "Registro robusto de conjuntos de puntos 2D y 3D". Computación de Imagen y Visión . 21 (13): 1145-1153. CiteSeerX 10.1.1.335.116 . doi :10.1016/j.imavis.2003.09.004. 
13. Myronenko, Andriy; Canción, Xubo (2010). "Registro de conjunto de puntos: deriva de puntos coherentes". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 32 (2): 2262–2275. arXiv : 0905.2635 . doi :10.1109/tpami.2010.46. PMID  20975122. S2CID  10809031.
14. Chui, Haili; Rangarajan, Anand (2003). "Un nuevo algoritmo de coincidencia de puntos para registro no rígido". Visión por computadora y comprensión de imágenes . 89 (2): 114-141. CiteSeerX 10.1.1.7.4365 . doi :10.1016/S1077-3142(03)00009-2. 
15. 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.
16. Horn, Berthold KP (1 de abril de 1987). "Solución de forma cerrada de orientación absoluta utilizando cuaterniones unitarios". JOSA A. 4 (4): 629–642. Código Bib : 1987JOSAA...4..629H. doi :10.1364/JOSAA.4.000629. ISSN  1520-8532. S2CID  11038004.
17. Arun, KS; Huang, TS; Blostein, SD (septiembre de 1987). "Ajuste de mínimos cuadrados de dos conjuntos de puntos tridimensionales". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . PAMI-9 (5): 698–700. doi :10.1109/TPAMI.1987.4767965. ISSN  1939-3539. PMID  21869429. S2CID  8724100.
18. Briales, Jesús; González-Jiménez, Javier (julio de 2017). "Registro 3D global convexo con dualidad lagrangiana". Conferencia IEEE 2017 sobre visión por computadora y reconocimiento de patrones (CVPR) . págs. 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 (21/01/2020). "TEASER: Registro de Nube de Puntos Rápido y Certificable". arXiv : 2001.07715 [cs.RO].
20. Parra Bustos, Álvaro; Chin, Tat-Jun (diciembre de 2018). "Eliminación garantizada de valores atípicos para el registro de nubes de puntos con correspondencias". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 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 (27 de febrero de 2017). "El problema del máximo consenso: avances algorítmicos recientes". Conferencias de Síntesis sobre Visión por Computador . 7 (2): 1–194. doi :10.2200/s00757ed1v01y201702cov011. ISSN  2153-1056.
22. Wen, Fei; Ying, Rendong; Gong, Zheng; Liu, Peilin (febrero de 2020). "Algoritmos eficientes para un ajuste robusto con máximo consenso". Transacciones IEEE sobre robótica . 36 (1): 92-106. doi :10.1109/TRO.2019.2943061. ISSN  1941-0468. S2CID  209976632.
23. Cai, Zhipeng; Chin, Tat-Jun; Koltun, Vladlen (2019). "Revisión de la búsqueda del árbol de maximización del consenso". Actas de la Conferencia Internacional IEEE sobre Visión por Computadora (ICCV) : 1637–1645. arXiv : 1908.02021 . Código Bib : 2019arXiv190802021C.
24. Bazin, Jean-Charles; Seo, Yongduek; Pollefeys, Marc (2013). "Maximización del conjunto de consenso globalmente óptimo mediante búsqueda de rotación". En Lee, Kyoung Mu; Matsushita, Yasuyuki; Rehg, James M.; Hu, Zhanyi (eds.). Visión por Computador – ACCV 2012 . Apuntes de conferencias sobre informática. vol. 7725. Berlín, Heidelberg: Springer. págs. 539–551. doi :10.1007/978-3-642-37444-9_42. ISBN 978-3-642-37444-9.
25. Hartley, Ricardo I.; Kahl, Fredrik (1 de abril de 2009). "Optimización global mediante búsqueda de espacio de rotación". Revista Internacional de Visión por Computadora . 82 (1): 64–79. doi :10.1007/s11263-008-0186-9. hdl : 1885/50831 . ISSN  1573-1405. S2CID  509788.
26. Fischler, Martín; Bolles, Robert (1981). "Consenso de muestra aleatoria: un paradigma para el ajuste de modelos con aplicaciones de análisis de imágenes y cartografía automatizada". Comunicaciones de la ACM . 24 (6): 381–395. doi : 10.1145/358669.358692 . S2CID  972888.
27. Le, Huu Minh; Chin, Tat-Jun; Eriksson, Anders; Hazlo, Thanh-Toan; Suter, David (2019). "Métodos aproximados deterministas para un ajuste robusto de máximo consenso". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 43 (3): 842–857. arXiv : 1710.10003 . doi :10.1109/TPAMI.2019.2939307. ISSN  1939-3539. PMID  31494545. S2CID  29346470.
28. Bustos, Álvaro Parra; Chin, Tat-Jun; Neumann, Frank; Friedrich, Tobías; Katzmann, Maximiliano (4 de febrero de 2019). "Un algoritmo práctico de camarilla máxima para hacer coincidir restricciones por pares". arXiv : 1902.01534 [cs.CV].
29. Huber, Peter J.; Ronchetti, Elvezio M. (29 de enero de 2009). Estadísticas sólidas . Serie Wiley en probabilidad y estadística. Hoboken, Nueva Jersey, EE. UU.: John Wiley & Sons, Inc. doi :10.1002/9780470434697. ISBN 978-0-470-43469-7.
30. Zhou, Qian-Yi; Parque, Jaesik; Koltun, Vladlen (2016). "Registro global rápido". En Leibe, Bastián; Matas, Jiri; Sebe, Nicu; Welling, Max (eds.). Visión por Computador – ECCV 2016 . Apuntes de conferencias sobre informática. vol. 9906. Cham: Editorial Internacional Springer. págs. 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). "A toda costa: una comparación de funciones de costos sólidas para valores atípicos de correspondencia de cámaras". 2015 XII Congreso sobre Visión por Computador y Robot . págs. 62–69. doi :10.1109/CRV.2015.52. ISBN 978-1-4799-1986-4. S2CID  9305263.
32. Bosse, Michael; Agamennoni, Gabriel; Gilitschenski, Igor (2016). "Estimación robusta y aplicaciones en robótica". Fundamentos y Tendencias en Robótica . 4 (4). ahora: 225–269. doi :10.1561/2300000047.
33. Negro, Michael J.; Rangarajan, Anand (1 de julio de 1996). "Sobre la unificación de procesos de línea, rechazo de valores atípicos y estadísticas robustas con aplicaciones en visión temprana". Revista Internacional de Visión por Computadora . 19 (1): 57–91. doi :10.1007/BF00131148. ISSN  1573-1405. S2CID  7510079.
34. Blake, Andrés; Zisserman, Andrés (1987). Reconstrucción visual. La prensa del MIT. ISBN 9780262524063.
35. Yang, Heng; Antonante, Pasquale; Tzoumas, Vasileios; Carlone, Luca (2020). "No convexidad graduada para una percepción espacial sólida: de solucionadores no mínimos al rechazo global de valores atípicos". Cartas de robótica y automatización IEEE . 5 (2): 1127-1134. arXiv : 1909.08605 . doi :10.1109/LRA.2020.2965893. ISSN  2377-3774. S2CID  202660784.
36. Besl, Pablo; McKay, Neil (1992). "Un método para el registro de formas tridimensionales". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 14 (2): 239–256. Código bibliográfico : 1992SPIE.1611..586B. doi :10.1109/34.121791.
37. Tsin, Yanghai; Kanade, Takeo (2004). "Un enfoque basado en la correlación para un registro sólido de conjuntos de puntos". Visión por Computador - ECCV 2004 . Apuntes de conferencias sobre informática. vol. 3023. Springer Berlín Heidelberg. págs. 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=ignorado ( ayuda )
38. Rusinkiewicz, Szymon; Levoy, Marc (2001). Variantes eficientes del algoritmo ICP . Actas de la Tercera Conferencia Internacional sobre Modelado e Imágenes Digitales 3-D, 2001. IEEE. págs. 145-152. doi :10.1109/IM.2001.924423.
39. oro, Steven; Rangarajan, Anand; Lu, Chien-Ping; Suguna, Pappu; Mjolsness, Eric (1998). "Nuevos algoritmos para la coincidencia de puntos 2D y 3D: estimación de pose y correspondencia". Reconocimiento de patrones . 38 (8): 1019-1031. Código Bib : 1998PatRe..31.1019G. doi : 10.1016/S0031-3203(98)80010-1 .
40. Jian, Bing; Vemuri, Baba C. (2005). Un algoritmo robusto para el registro de conjuntos de puntos utilizando una mezcla de gaussianos . Décima Conferencia Internacional IEEE sobre Visión por Computadora 2005. Vol. núm. 2. págs. 1246-1251.
41. Myronenko, Andriy; Canción, Xubo; Carriera-Perpinán, Miguel A. (2006). "Registro de conjunto de puntos no rígidos: deriva de puntos coherente". Avances en los sistemas de procesamiento de información neuronal . 19 : 1009-1016 . Consultado el 31 de mayo de 2014 .
42. Hirose, Osamu (2021). "Una formulación bayesiana de deriva de puntos coherente". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 43 (7): 2269–2286. doi : 10.1109/TPAMI.2020.2971687 . PMID  32031931.
43. Hirose, Osamu (2021). "Aceleración del registro de conjuntos de puntos no rígidos con reducción de resolución y regresión del proceso gaussiano". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 43 (8): 2858–2865. doi : 10.1109/TPAMI.2020.3043769 . PMID  33301401.
44. Liu, Weixiao; Wu, Hongtao; Chirikjian, Gregory S. (2021). "LSG-CPD: deriva de puntos coherente con geometría de superficie local para el registro de nubes de puntos". Conferencia internacional IEEE/CVF 2021 sobre visión por computadora (ICCV) . págs. 15273-15282. arXiv : 2103.15039 . doi :10.1109/ICCV48922.2021.01501. ISBN 978-1-6654-2812-5. S2CID  232404480.
45. Pauly, M.; Bruto, M.; Kobbelt, LP (2002). "Simplificación eficiente de superficies muestreadas puntualmente". Visualización IEEE, 2002. VIS 2002 (PDF) . págs. 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: deriva de puntos coherente con geometría de superficie local para el registro de nubes de puntos". Conferencia internacional IEEE/CVF 2021 sobre visión por computadora (ICCV) . págs. 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: Ordenación del espacio de correspondencia" (PDF) . Reconstrucción 3D y estimación de movimiento mediante sonar de visión frontal (Ph.D.). Universidad Heriot-Watt.

enlaces externos

• Implementación de referencia de coincidencia de puntos robusta con spline de placa delgada
• Implementación de referencia del registro del conjunto de puntos de correlación del kernel
• Implementación de referencia de la deriva de puntos coherente
• Implementación de referencia de variantes de ICP.
• Implementación de referencia de la deriva del punto coherente bayesiano
• Implementación de referencia de LSG-CPD