# A Termination Criterion for Probabilistic Point Clouds Registration
## 3 Materials and Methods  
### Probabilistic Point Clouds Registration  
We already presented PPCR in a previous work [4]; however, since we present an extension to the original version, we briefly summarize its working. PPCR is a closest-point based algorithm for local point clouds registration. This means that it is aimed at fine-aligning two point clouds that are already roughly aligned. It does not use any feature to estimate correspondences between two point clouds; instead, similarly to ICP, it approximates the true, unknown, correspondences by using a data-association policy based on the closest distance. However, the PPCR data association policy differs from that of ICP (and many of its variants)--in ICP each point in the source point cloud is associated with only a single point in the target point cloud, while PPCR associates a point in the source point cloud with a set of points in the target cloud. Moreover, each association is weighted. The weights represent the probability of an association of being the right data-association for a particular point. The two different data association methods are depicted in Figure 1.  
Figure 1: The two different data association policies. (**a**) Iterative Closest Point (ICP) Data Association (**b**) Probabilistic Data Association  
For each point \(x_{j}\) in the source point cloud, we look for the \(n\) nearest points, \(y_{0},...,y_{n}\), in the target cloud. For each of these points \(y_{k}\), with \(0\leq k\leq n\), we define an error term given by  
\[\|y_{k}-(Rx_{j}+T)\|^{2}, \tag{1}\]  
where \(R\) is a rotation matrix and \(T\) a translation vector. Equation (1) represents the squared error between the point \(y_{k}\) in the target point cloud and the associated point \(x_{j}\) from the source point cloud, transformed using the current estimate of the rotation \(R\) and translation \(T\). Summing all the error terms, calculated according to Equation (1), we build a Least Squares optimization problem which is solved using a suitable method (such as Levenberg-Marquardt). However, given a set of points associated to \(x_{j}\), not all the corresponding error terms should have the same weight. Intuitively we want to give more importance to the associations which are in accordance with the current estimate of the transformation and lower importance to the others. Thus, the weight \(w_{kj}\) of the error term \(\|y_{k}-(Rx_{j}+T)\|^{2}\) is given by  
\[w_{kj}\propto e^{-\frac{\|y_{k}-(Rx_{j}+T)\|^{2}}{2}}, \tag{2}\]  
where the proportionality implies a normalization among all the error terms associated with \(x_{j}\) so that their weights represent a probability distribution (therefore they must sum to 1). Equation (2) was derived from an Expectation-Maximization algorithm [26], with an additive Gaussian noise model [4]. The Gaussian probability density function (pdf) used in Equation (2) is appropriate assuming that there are no outliers and all points in the source point cloud have a corresponding point in the target point cloud. However, a t-distribution is a better choice in presence of outliers, especially when there is lot of distortion in one of the point clouds that, thus, cannot be aligned perfectly. Consequently, we decided to use a more robust formulation for the weights, basing on the t-distribution. A t-distribution is very similar to a Gaussian, but its tails have a higher probability; therefore, it better represents a population with a higher probability of having outliers. The weight \(w_{kj}\) of the association between \(x_{j}\) and \(y_{k}\) is given by:  
\[w_{kj}=p_{kj}\frac{\
u+d}{\
u+\|y_{k}-(Rx_{j}+T)\|^{2}}, \tag{3}\]  
with  
\[p_{kj}\propto\left(1+\frac{\|y_{k}-(Rx_{j}+T)\|^{2}}{\
u}\right)^{-\frac{\
u+ d}{2}}, \tag{4}\]  
where \(\
u\) the is number of degrees of freedom of the t-distribution (which is a parameter of our algorithm) and \(d\) is the dimension of the error terms (in our case 3, since we are operating with points in the 3D space).