# A Fast Point Clouds Registration Algorithm for Laser Scanners
## 2 Proposed Method
### RANSAC Coarse Registration  
The RANSAC algorithm proposed by [PERSON] and [PERSON] [18] can automatically fit the model in data, and the solution to the location determination problem shows that RANSAC can also calculate the position of the corresponding points, so it can be used for 3D point cloud registration. In our approach, we use an improved RANSAC algorithm [19] to calculate the initial transformation matrix \(\hat{T}\in SE(3)\), which minimizes the sum of the squared distances between the corresponding points of the two point clouds, as shown in Equation (7):  
\[\hat{T}\ =\ \underset{T}{argmin}\ \text{g}(T)\ =\ \underset{T}{argmin}\sum_{p\in P }(Tp-q)^{2} \tag{7}\]  
This algorithm needs to input the down-sampled source point cloud \(P^{\prime}\) and target point cloud \(Q^{\prime}\) and the corresponding descriptors. The main steps are as follows:  
Step 1, corresponding point searching. Select \(n(n\geq 3)\) points \(\{p_{1},p_{2},\ldots,p_{n}\}\) randomly in \(P^{\prime}\) for each iteration to find its corresponding point \(\{q_{1},q_{2},\ldots,q_{n}\}\) in \(Q^{\prime}\) by nearest neighbors matching of five feature descriptors.  
Step 2, difference vector of corresponding sides calculating. Compute the Euclidean distance between the \(n\) sampling points at first. Then, calculate the ratio of the difference between the two corresponding side lengths to the bigger side length to form a vector \(\vec{\eta}\). If \(\|\vec{\eta}\|\) is smaller than edge length similarity threshold \(\varepsilon_{ploy}\), continue the next step, otherwise, return to the first step. Set \(n=3\) as a sample, \(\vec{\eta}\) is calculated as Equation (8) and the schematic diagram of computing \(\vec{\eta}\) is shown as Figure 8.  
\[\vec{\eta}=\left[\frac{\left|d_{12}^{p}-d_{12}^{q}\right|}{max\left(d_{12}^{p},d_{12}^{q}\right)},\frac{\left|d_{23}^{p}-d_{23}^{q}\right|}{max\left(d_{23}^ {p},d_{23}^{q}\right)},\frac{\left|d_{13}^{p}-d_{13}^{q}\right|}{max\left(d_{1 3}^{p},d_{13}^{q}\right)}\right] \tag{8}\]  
Step 3, corresponding points transforming. Estimate a temporary transformation matrix \(T_{i}\) from corresponding point pairs and transform \(P^{\prime}\) into \(P_{i}^{\prime}\).  
Step 4, inlier points judging. Compute the Euclidean distances of the nearest neighbors between \(P_{i}^{\prime}\) and \(Q^{\prime}\), and take the points whose nearest neighbor distance is lower than the set distance threshold \(\varepsilon_{ransac}\) as inlier points. If the number of inlier points is too small, go back to Step 1.  
Step 5, transformation matrix computing. Compute the transformation matrix according to the corresponding relationship of the interior points. The iteration number \(k\) of RANSAC is obtained by a presumed success probability \(p\) and a preset inlier fraction \(w\), which is shown as Equation (9):  
\[k=\frac{\log(1-p)}{\log(1-w^{n})} \tag{9}\]  
Step 6, model estimating and updating. Use the inlier points fitting a parameterized model to test other points, and update the inlier points to continue iterative calculations until the best estimation model is obtained or max iteration number \(R_{iter}\) is reached. When the value of \(\text{g}\big{(}\hat{T}\big{)}\) is the smallest, set \(\hat{T}\) as the best estimation result and stop the iteration.  
Figure 8: The schematic diagram of computing \(\vec{\eta}\).