# A Termination Criterion for Probabilistic Point Clouds Registration
## 2 Related Work  
Point clouds registration algorithms could be divided into two categories: global and local. Global registration is the problem of aligning two point clouds without any prior assumption on their misplacement. Traditionally, this problem has been solved using feature-based techniques, such as PFH [7] and their faster variant FPFH [8], or angular-invariant features, [9]. Usually the matches are found using algorithms such as RANSAC [10]; the matches are then used to estimate the rototranslation between the two point clouds. As an alternative to _hand-crafted_ descriptors, solutions based on neural networks, that aim at enhancing the discriminative capacity of the features, have been proposed. Examples are 3 dMatch [11] and 3 DSmoothNet [12]. Networks that combines both the feature matching and the transformation estimation steps together have been proposed too, such as Pointnetlk [13] and Pcrnet [14]. The drawback of global registration approaches is that they usually cannot provide an accurate alignment, mainly because of the high number of spurious matches; therefore, they are rather used to obtain a coarse registration that is later refined with a fine registration algorithm [5]. For this reason, techniques aimed at estimating a rototranslation from matches with a high number of outliers have been proposed. Notable examples are Fast Global Registration [15] and TEASER++ [16], that can even work without any feature, but using an all-to-all association strategy. Local registration algorithms, instead, (also known as _fine_ registration) aim at finding the rototranslation that best aligns two point cloud that are already roughly aligned. Therefore, they refine a pre-existing alignment, that can be obtained in different ways, for example, with a global algorithm, with an inertial system, or manually. One of the most important algorithms in this category is Iterative Closest Point (ICP). ICP was developed independently by [PERSON] and [PERSON] [1], [PERSON] [2], and [PERSON] [3] and is still one of the most used technique. The most critical problem a registration algorithm has to solve is the data association problem, that is, associating one point in a point clouds, to one or more in the another. ICP solves this issue by associating a point in the source point cloud to the closest in the target. The best transformation resulting from this data association is found and this process is repeated until convergence. Many different variants of ICP have been proposed. Usually, they aim at speeding up the algorithm or at improving the accuracy [17]. One of the most important of these variants is Generalized ICP (G-ICP) [18], which greatly improves the quality of the results by using a probabilistic framework with a point-to-plane data association. Probabilistic Point Clouds Registration (PPCR) [4] uses the same closest-point based data association of ICP, in conjunction with a probabilistic model, to improve both the accuracy and, most important, the robustness against noise and outliers. While it was originally developed to deal with the problem of aligning a sparse point cloud with a dense one, it was shown to perform very well also on traditional registration problems. Another important technique used for local point clouds registration is called Normal Distribution Transform (NDT) [19]. This technique was originally developed to register 2D laser scans, but has been successfully applied also to 3D point clouds [20]. Differently from ICP, it does not establish any explicit correspondence between points. Instead, the source point cloud or laser scan is subdivided into cells and a normal distribution is assigned to each cell, so that the points are represented by a probability distribution. The matching problem is then solved as a maximization problem, using [PERSON]'s algorithm. ICP-like algorithms are usually iterative, that is, they perform several iterations, each composed of an optimization problem that should improve the previous solution.