En visión por computador, el registro se entiende como el proceso de encontrar una transformación que permita alinear dos o más conjuntos de datos. En este caso vamos a hablar de nubes de puntos 3D, aunque la idea, como os voy a explicar después, es exactamente la misma para cualquier tipo de imagen, ya sea 2D de color o 3D.
También es importante destacar que hay registro rígido, articulado y deformable, y se diferencian en el tipo de transformación que se aplica. En este post hablaremos un poco de cada uno y en dejamos para otros posts profundizar en las características de cada uno.
Formalicemos el proceso de registro
El registro de nubes de puntos 3D es un proceso crítico en visión por computadora y gráficos, que tiene como objetivo alinear dos o más conjuntos de datos de nubes de puntos en un único marco de referencia. Esto implica encontrar la transformación óptima \( T^* \in \tau\) que minimice la distancia entre las nubes de puntos \( M\) y \( S\).
\(T^* = \arg \min_{T \in \tau} dist(T(M), S)\)
Si nos centramos en la transformación \( T\), podemos dividir el problema del registro en dos categorías principales: registro rígido y registro no rígido. La primera se refiere a transformaciones que transforman rígidamente los datos, es decir, todos los puntos en la nube de puntos se «mueven» juntos de la misma manera. La segunda es una transformación no lineal que permite cambiar cada punto en una dirección diferente, permitiendo deformaciones en la geometría de los datos. A continuación, puedes ver dos ejemplos de registro rígido y no rígido respectivamente:
Tipos de Registro
- Registro Rígido: Implica transformaciones lineales donde todos los puntos se mueven uniformemente. Las transformaciones típicas incluyen traslación, rotación y escalado.
- Registro no rígido o deformable: Implica transformaciones no lineales que permiten deformaciones locales, adaptándose a cambios en la geometría y la topología.
Pipeline de registro
El proceso está dividido principalmente en tres fases, la extracción de características, el emparejamiento entre las caracterísitcas de las dos nubes de puntos 3D, y el cálculo de la transformación.
Descripción de nubes de puntos
Basado en la ecuación anterior, necesitamos encontrar la transformación que minimice la distancia entre \( M\) transformado y \( S\). Encontrar la transformación en el espacio infinito de todas las posibles transformaciones es imposible, es decir, tendriamos que probar todas las transformaciones posibles una a una, lo cual es computacionalmente inviable. Para reducir este problema, podemos encontrar buenas correspondencias entre las dos nubes de puntos y, basándonos en ellas, estimar las posibles transformaciones. Para emparejar los puntos que coinciden entre sí, existen diferentes enfoques:
Basado en características
Las características o descriptores resumen, global o localmente, una nube de puntos para reducir la dimensionalidad y también resaltar las partes más distintivas de la misma. En 3D, existen diferentes descriptores, ya sean handcrafted, como el FPFH, o basados en aprendizaje.
- Han, X., Jin, J.S., Xie, J., Wang, M., & Jiang, W. (2018). A comprehensive review of 3D point cloud descriptors. ArXiv, abs/1802.02297.
- Ao, S., Hu, Q., Yang, B., Markham, A., & Guo, Y. (2021). Spinnet: Learning a general surface descriptor for 3d point cloud registration. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (pp. 11753-11762).
Características densas
A pesar de que los métodos basados en características permiten un emparejamiento globalmente consistente y reducen la dimensionalidad, existen otros enfoques que utilizan la información de cada punto en la nube de puntos como característica local. Cada punto puede contener la ubicación 3D, color, orientación normal, etc. Uno de los métodos más conocidos que utilizan cada punto es el Iterative Closest Point (ICP). Utilizar el conjunto de datos completo produce una búsqueda más fina de correspondencias y, en consecuencia, permite encontrar una transformación más precisa.
NOTA: Es la práctica se suele usar una combinación de métodos basados en características y métodos densos uno tras otro para encontrar una alineación global seguida de una transformación refinada.
Grafos
Otra característica que está ganando popularidad actualmente es la descripción basada en grafos de las nubes de puntos. Los métodos tradicionales utilizan Modelos de Mezcla de Gaussianas para extraer la relación entre datos vecinos:
- B. Jian and B. C. Vemuri, «Robust Point Set Registration Using Gaussian Mixture Models,» in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 8, pp. 1633-1645, Aug. 2011, doi: 10.1109/TPAMI.2010.223.
Los enfoques novedosos utilizan redes para crear la estructura de grafos con múltiples propósitos, incluido el registro. Utilizando mecanismos de atención, se pueden generar estructuras tipo grafo a partir de nubes de puntos desorganizadas.
- Fu, K., Liu, S., Luo, X., & Wang, M. (2021). Robust point cloud registration framework based on deep graph matching. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (pp. 8893-8902).
Matching o emparejamiento
Una vez que ambas nubes de puntos se describen utilizando características, dispersas o densamente, el proceso de emparejamiento define las correspondencias actuales entre cada conjunto de características (\( M\) y \( S\) en la ecuación anterior). Existen dos estrategias, asignación binaria y asignación suave (utilizaremos el término en inglés por ser más habitual, soft-assignment).
Emparejamiento binario
La correspondencia binaria se refiere a emparejar los datos más similares en cada nube de puntos. Este enfoque asume una compensación general de todos los puntos, por lo que si una nube de puntos tiene un número diferente de datos, en general, las correspondencias totales compensarán la dirección desigual de la transformación. El método más utilizado es buscar en el espacio de características (recuerda que ICP usa como características la información de cada punto) los puntos más cercanos utilizando una función de similitud (es decir, distancia euclidiana, Mahalanobis, etc.).
Soft-assignment
Una desventaja principal de las correspondencias binarias es que, cuando las nubes de puntos tienen un número significativamente diferente de puntos, un dato puede corresponder a muchos en el otro conjunto. Además, los datos ruidosos afectan más cuando se fuerza una correspondencia uno a uno, en lugar de cuando múltiples correspondencias de datos pueden compensar el ruido.
Modelos de Mezcla de Gaussianas (GMM)
Usando una distribución gaussiana, podemos suponer que para un punto \( m_j \in M\) en la ecuación general de registro, cada punto en \( s_i \in S\) es similar a él en un porcentaje definido por:
\( p(s_i) = \frac{1}{\sqrt{2 \pi \sigma^2}}e-\frac{\left | T(m_j) – s_i \right |}{2 \sigma^2}\)
El algoritmo de registro Coherent Point Drift (CPD) utiliza esta distancia tanto para registros rígidos como no rígidos. Puedes encontrar un tutorial introductorio de CPD en: Coherent Point Drift Tutorial.
Atención Cruzada
Los nuevos algoritmos de registro utilizan mecanismos de atención para estimar la correspondencia entre datos/características. Esta atención cruzada se realiza en muchos casos creando una matriz de covarianza como la mostrada a continuación y utilizando una función Softmax o un algoritmo Sinkhorn para normalizar los datos.
Ejemplos de métodos que utilizan este enfoque incluyen: PCAM3, GeoTransformer4, PointDSC5.
Eliminación de outliers
A pesar de todos los pre-procesamientos para reducir el ruido y los outliers (puntos atípicos) en cada nube de puntos antes del registro, es probable que la etapa de emparejamiento tenga correspondencias incorrectas. Existen diferentes técnicas para abordar este problema, como RANSAC y TopK.
RANdom SAmple Consensus (RANSAC)
RANSAC se desarrolló originalmente para estimar el modelo que mejor representa un conjunto de datos en presencia de ruido y puntos atípicos. En la tarea que nos ocupa, el «modelo» es la transformación (no confundir con el modelo como una de las nubes de puntos) que mejor ajusta un conjunto al otro.
TopK
TopK se refiere a seleccionar los «k» datos/características más similares. Esto se aplica en casos de asignación suave donde se estiman correspondencias de uno a muchos. En lugar de evaluar cada par, solo se utilizan los más similares. Estadísticamente, esto eliminará correspondencias incorrectas.
Estimación de la transformación
Con las correspondencias establecidas, la última etapa es estimar la transformación para mapear las dos nubes de puntos. Esta etapa es donde las grandes familias de métodos rígidos y no rígidos difieren más.
Transformaciones rígidas
Las transformaciones rígidas son un subconjunto de las transformaciones afines, que incluyen Rotación, Traslación y Escalado. Ocurren en el espacio euclideo y preservan la distancia entre cada punto en la nube de puntos, y preservan las líneas paralelas.
Podemos reformular la ecuación anterior restringiéndola a transformaciones rígidas como sigue:
\( T^* = \arg \min_{T \in \tau} \sum_{j=1, i=1}^{N, K} \left | gRm_j+t-s_i \right |\)
donde \( N\) y \( K\) son el número de puntos en \( M\) y \( S\) respectivamente, \( g\) es el factor de escalado, \( R \in SO(3)\) es una matriz de rotación, y \( t\) es el vector de traslación.
Para calcular \( t\), se realiza una sustracción ponderada de cada par de puntos. En el caso de asignación binaria, el peso de cada par es igual a 1, mientras que en el soft-assignment el peso viene dado por la similitud entre cada par.
Para estimar la rotación \( R \in SO(3)\) y el factor de escalado \( g\), se suele utilizar la aproximación de Procrustes mediante Descomposición en Valores Singulares (SVD):
Las rotaciones se representan mediante ángulos de Euler, matrices de rotación o cuaterniones. Las matrices de rotación en 3D tienen la forma de una matriz de 3×3; los ángulos de Euler son la rotación a lo largo de los ejes X, Y y Z, conocidos como Roll, Pitch y Yaw respectivamente; y finalmente, los cuaterniones representan la orientación y las rotaciones usando un vector de 4×1 que evita el bloqueo gimbal (problema presentado en los ángulos de Euler).
La forma general de aplicar transformaciones hace uso de coordenadas homogéneas permiten concatenar múltiples transformaciones. Para datos 3D, tienen la forma de matrices de 4×4:
Transformaciones no rígidas o deformables
El registro no rígido incluye varios niveles de transformaciones. Las transformaciones proyectivas y afines, como el cizallamiento o shear, se consideran casos de mapeo deformable.
Sin embargo, las deformaciones más generales se definen mediante transformaciones no lineales. En casos como el CPD (Coherent Point Drift), se utilizan la Thin Plate Spline y el cálculo de variaciones.
- Deng, B., Yao, Y., Dyke, R. M., & Zhang, J. (2022). A Survey of Non‐Rigid 3D Registration. Computer Graphics Forum, 41(2), 559–589.
Redes End-to-End
Hoy en día, con la llegada del Deep Learning, muchas soluciones end-to-end proporcionan la transformación (o la versión ya transformada de $ latex M$) en una única arquitectura que realiza la extracción de características, el emparejamiento y la estimación de la transformación.
Algunos ejemplos son:
- Predator: Huang, S., Gojcic, Z., Usvyatsov, M., Wieser, A., & Schindler, K. (2021). PREDATOR: Registration of 3D Point Clouds with Low Overlap. 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 4265–4274.
- GeoTransformer: Qin, Z., Yu, H., Wang, C., Guo, Y., Peng, Y., Ilic, S., Hu, D., Xu, K. (2023). GeoTransformer: Fast and Robust Point Cloud Registration With Geometric Transformer. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(8), 9806–9821.
- DeepPRO: Lee, D., Hamsici, O. C., Feng, S., Sharma, P., & Gernoth, T. (2021). DeepPRO: Deep Partial Point Cloud Registration of Objects. 2021 IEEE/CVF International Conference on Computer Vision (ICCV), 5683–5692.