# Robust Registration of 2D and 3D Point Sets

##### Posted on (Update: )

This note is for Fitzgibbon, A. W. (2003). Robust registration of 2D and 3D point sets. Image and Vision Computing, 21(13), 1145–1153.

A cloud of point samples from the surface of an object is obtained from two or more points of view, in different reference frames. **The task of registration** is to place the data into a common reference frame by estimating the transformations between the datasets.

The error to be minimized is

\[E(a, \phi) = \sum_{i=1}^{N_d}w_i\Vert m_{\phi(i)} - T(a;d_i)\Vert^2\]In ICP-like algorithms $\phi(i)$ is chosen as the point which minimizes the distance between model and data, yielding the error function

\[E(a) = \sum_{i=1}^{N_d}w_i\min_j\Vert m_j - T(a; d_i)\Vert^2\]and finally the estimate of the optimal registration is given by minimizing over $a$

\[\hat a=\argmin_a \sum_{i=1}^{N_d}w_i\min_j\Vert m_j-T(a;d_i)\Vert^2\]The simplest ICP algorithm iterates two steps,

Beginning with an initial estimate of the registration parameters, $a_0$, the algorithm forms a sequence of estimates $a_k$, which progressively reduce the error $E(a)$. In each iteration,

- compute correspondence $\phi$: set \(\phi(i) = \argmin_{j\in\{1,\ldots,N_m\}}\Vert m_j-T(a_k;d_i)\Vert\,,\quad i=1,\ldots,N_d\)
- update transformation $a$: set \(a_{k+1} = \argmin_a\sum_{i=1}^{N_d}\Vert m_{\phi(i)} - T(a;d_i)\Vert\)

LM algorithm: rewrite

\[E(a) = \sum_{i=1}^{N_d}E_i^2(a)\]where

\[E_i(a)=\sqrt{w_i}\min_j\Vert m_j-T(a;d_i)\Vert\]and consider the vector of residuals $e(a) = \{E_i(a)\}_{i=1}^{N_d}$, then $E(a) = \Vert e(a)\Vert^2$

The LM algorithm combines the gradient descent and Gauss-Newton approaches to function minimization.

Difference between Gauss-Newton and Newton

For $f(x) = r^2(x)$, the derivatives are $f’(x)=2r(x)r’(x)$ and $f^{\prime\prime}(x)=2(r(x)r^{\prime\prime}(x)+(r’(x))^2)$. Newton’s method uses the second derivative, while Gauss-Newton uses the approximation $f^{\prime\prime}(x)\approx 2(r’(x))^2$.

It is trivial to modify the error function to include a robust kernel for LM-ICP. The kernel can be

- Lorentzian: $\epsilon(r) = \log\left(1+\frac{r^2}{\sigma}\right)$
- Huber: $\epsilon(r)=\begin{cases}r^2 & r<\sigma\\ 2\sigma\vert r\vert - \sigma^2& r\ge \sigma\end{cases}$

## Fast ICP using the distance transform

The Euclidean distance transform of a set of points $\{m_j\}_{j=1}^{N_m}$,

\[D_E(x) = \min_j\Vert m_j - x\Vert\]Analogously define the $\epsilon$-distance transform $D_\epsilon$ by

\[D_\epsilon(x) = \min_j\epsilon^2(\vert m_j-x\vert)\]If the mapping $\Vert x\Vert \mapsto \epsilon^2(\vert x\vert)$ is monotonic, then $D_\epsilon(x) = \epsilon^2(\vert D_E(x)\vert)$.