# A Termination Criterion for Probabilistic Point Clouds Registration
## 3 Materials and Methods
### Termination Criteria
\[MSE(X^{t},X^{t-1})=\frac{\sum_{i}^{N}||x_{i}^{t}-x_{i}^{t-1}||^{2}}{N}. \tag{5}\]  
We stop the algorithm when the MSE drops under a certain relative threshold. With _relative_ we mean that we are not using a fixed absolute threshold, but we want to stop when, for example, the Mean Squared Error becomes smaller than a certain fraction of that at the previous iteration. That is:  
\[MSE(X^{t},X^{t-1})<\frac{MSE(X^{t-1},X^{t-2})}{threshold}. \tag{6}\]  
This means that we are stopping the algorithm when it is not able to move (or it is moving of a negligible amount) the source point cloud any more; thus, it has converged. We use a relative threshold, instead of an absolute, because it is much more flexible and does not have to be tuned for each set of point clouds. However, rather than checking for Equation (6) just once, we ensure that the condition holds for several consecutive iterations. In this way we avoid stopping too early because of a single iteration during which the alignment was not improved, but that could be followed by other successful iterations. Another option we evaluated is the use of the so-called _Cost Drop_. During the execution of the inner loop of the multi-iteration version of PPCR, an optimization problem is solved. This optimization problem is a weighted least squares problem, and the cost we want to minimize is the weighted sum of squared distances between corresponding points, as described in the previous section. Before the optimization, the problem we are going to optimize will have a certain cost. The optimizer will, hopefully, reduce this cost to a lower value. The difference between the initial and the final cost is called _Cost Drop_. We use this value to stop the outer loop when the _cost drop_ of the inner loop drops under a threshold. We want to avoid absolute thresholds, since they need to be specifically tuned for each application. Instead, we express this threshold with respect to the initial cost of the problem: for example we could stop when the cost drop is less than 1% of the initial cost of the problem. This is what we used for our experiments and proved to be a good threshold for obtaining accurate registrations. This condition is expressed by Equation (7). \[\frac{cost_{final}-cost_{initial}}{cost_{initial}}<threshold, \tag{7}\]  
where \(cost_{initial}\) is the initial cost of the optimization problem solved at each iteration of PPCR and \(cost_{final}\) is the corresponding cost after the optimization. Similarly to the MSE, and for the same reasons, this condition should hold for several iterations and not just once. The third criterion we evaluated is the number of successful iterations of the weighted least squares optimization problems. Solving an optimization problem with Levenberg-Marquard is an iterative process. Each step of this process can be successful, if the step managed to reduce the cost of the problem, or, otherwise, unsuccessful. We wanted to test if this value could be used as termination criterion, for example, stopping after too many unsuccessful steps. To evaluate the effectiveness of a termination criterion, we used the following idea. Suppose we have the ground truth for the source point cloud, that is, we know the _true_ rototranslation between the reference frames of the source and target point clouds. At the end of each iteration, we obtain an estimate of this rototranslation. Therefore, we can calculate the Mean Squared Error (as in Equation (6)) between our estimate and the ground truth, since they are the same point cloud in different poses. Theoretically, if the algorithm was working properly, this error should decrease among the steps of the outer loop of the algorithm; therefore, the more the iterations, the smaller the difference becomes. Practically, at some point this difference will cease to decrease, or, more precisely, it will start decreasing of a negligible amount. This is the iteration to which we should stop, since it means that the algorithm has converged to a solution.