Las distribuciones normales transforman

La transformación de distribuciones normales ( NDT ) es un algoritmo de registro de nubes de puntos introducido por Peter Biber y Wolfgang Straßer en 2003, mientras trabajaban en la Universidad de Tübingen .

El algoritmo registra dos nubes de puntos asociando primero una distribución normal por partes a la primera nube de puntos, que proporciona la probabilidad de muestrear un punto perteneciente a la nube en una coordenada espacial dada, y luego encontrando una transformación que mapea la segunda nube de puntos a la primera maximizando la probabilidad de la segunda nube de puntos en dicha distribución en función de los parámetros de la transformación.

Originalmente introducido para la correspondencia de mapas de nubes de puntos 2D en localización y mapeo simultáneos (SLAM) y seguimiento de posición relativa, ^{[ 1 ]} el algoritmo se extendió a nubes de puntos 3D ^{[ 2 ]} y tiene amplias aplicaciones en visión por computadora y robótica . NDT es muy rápido y preciso, lo que lo hace adecuado para su aplicación a grandes conjuntos de datos, pero también es sensible a la inicialización, requiriendo una estimación inicial suficientemente precisa, y por esta razón se usa típicamente en una estrategia de alineación de grueso a fino. ^{[ 3 ] [ 4 ] [ 5 ]}

La función NDT asociada a una nube de puntos se construye dividiendo el espacio en celdas regulares. Para cada celda, es posible definir la media.${\displaystyle \textstyle \mathbf {q} ={\frac {1}{n}}\sum _{i}\mathbf {x_{i}} }$y covarianza${\displaystyle \textstyle \mathbf {S} ={\frac {1}{n}}\sum _{i}\left(\mathbf {x} _{i}-\mathbf {q} \right)\left(\mathbf {x} _{i}-\mathbf {q} \right)^{\top }}$del${\displaystyle n}$puntos de la nube${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}$que caen dentro de la celda. La densidad de probabilidad de muestrear un punto en una ubicación espacial dada${\displaystyle \mathbf {x} }$El contenido dentro de la célula viene dado entonces por la distribución normal.

${\displaystyle e^{-{\frac {1}{2}}\left(\mathbf {x} -\mathbf {q} \right)^{\top }\mathbf {S} ^{-1}\left(\mathbf {x} -\mathbf {q} \right)}}$.

Dos nubes de puntos pueden representarse mediante una transformación euclidiana.${\displaystyle f}$con matriz de rotación${\displaystyle \mathbf {R} }$y vector de traslación${\displaystyle \mathbf {t} }$

${\displaystyle f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )=\mathbf {R} \mathbf {x} +\mathbf {t} }$

que se corresponde con la primera nube de puntos, parametrizada por los ángulos de rotación y los componentes de traslación.

El algoritmo registra las dos nubes de puntos optimizando los parámetros de la transformación que mapea la segunda nube a la primera, con respecto a una función de pérdida basada en la NDT de la primera nube de puntos, resolviendo el siguiente problema

${\displaystyle \arg \min _{\mathbf {R} ,\mathbf {t} }\left\{-\sum _{i}\operatorname {NDT} \left(f_{\mathbf {R} ,\mathbf {t} }\left(\mathbf {x_{i}} \right)\right)\right\}}$

donde la función de pérdida representa la probabilidad negada, obtenida al aplicar la transformación a todos los puntos de la segunda nube y sumar el valor del NDT en cada punto transformado.${\displaystyle f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )}$La pérdida es continua por partes y diferenciable , y puede optimizarse con métodos basados ​​en gradientes (en la formulación original, los autores utilizan el método de Newton ).

Para reducir el efecto de la discretización de celdas, una técnica consiste en particionar el espacio en múltiples cuadrículas superpuestas, desplazadas en la mitad del tamaño de la celda a lo largo de las direcciones espaciales, y calcular la probabilidad en una ubicación dada como la suma de los NDT inducidos por cada cuadrícula. ^{[ 1 ]}

• Biber, Peter; Straßer, Wolfgang (2003). "La transformación de distribuciones normales: un nuevo enfoque para la correspondencia de escaneo láser". Actas de la Conferencia Internacional IEEE/RSJ de 2003 sobre Robots y Sistemas Inteligentes (IROS 2003) (Cat. No. 03CH37453) . Vol.  3.
• Cheng, Liang; Chen, Song; Liu, Xiaoqiang; Xu, Hao; Wu, Yang; Li, Manchun; Chen, Yanming (2018). "Registro de nubes de puntos de escaneo láser: una revisión" . Sensors . 18 (5). Multidisciplinary Digital Publishing Institute: 1641. Bibcode : 2018Senso..18.1641C . doi : 10.3390/s18051641 . PMC 5981425. PMID 29883397 .  
• Dong, Zhen; Liang, Fuxun; Yang, Bisheng; Xu, Yusheng; Zang, Yufu; Li, Jianping; Wang, Yuan; Dai, Wenxia; Fan, Hongchao; Hyyppä, Juha (2020). "Registro de nubes de puntos de escáner láser terrestre a gran escala: una revisión y evaluación comparativa". ISPRS Journal of Photogrammetry and Remote Sensing . 163. Elsevier: 327–342 . Bibcode : 2020JPRS..163..327D . doi : 10.1016/j.isprsjprs.2020.03.013 . S2CID 216449537 . 
• Li, Leihui; Wang, Riwei; Zhang, Xuping (2021). "Una revisión tutorial sobre registros de nubes de puntos: principio, clasificación, comparación y desafíos tecnológicos". Problemas matemáticos en ingeniería . 2021. Hindawi.
• Magnusson, Martin (2009). La transformación de distribuciones normales tridimensionales: una representación eficiente para el registro, el análisis de superficies y la detección de bucles (Ph.D.). Örebro universitet.

• "Registrar dos nubes de puntos usando el algoritmo NDT" . MathWorks.