# A Fast Point Clouds Registration Algorithm Based on ISS-USC Feature for the 3D Laser Scanner
## 3 Algorithm Design
### Improved RANSAC Coarse Registration  
The goal of point clouds registration is to estimate the transformation matrix so that the sum of squared distances between each point \(p\) in the source point clouds \(P\) and the corresponding point \(q\) in the target point clouds \(Q\) is minimized, as shown in Formula (6):  
\[\hat{T}=\underset{T}{\text{argmin}}(T)=\underset{T}{\text{argmin}}\sum_{p\in P} \left(T_{p}-q\right)^{2} \tag{6}\]  
The main steps of the coarse registration of the random sample consensus algorithm are as follows:  
(1) Select \(n\) random sample points \(p_{1}\), \(p_{2}\),..., \(p_{n}\) in the source point clouds \(P\), and search for \(n\) corresponding points \(q_{1}\), \(q_{2}\),..., \(q_{n}\) in the target point clouds \(Q\) through nearest neighbor matching according to the USC descriptor, so that \(n\) corresponding point pairs \((p_{1}\), \(q_{1})\), \((p_{2}\), \(q_{2})\),..., \((p_{n}\), \(q_{n})\) can be obtained, where \(n\geq 3\);  
(2) The pre-exclusion step to avoid incorrect hypothetical poses. First, calculate the Euclidean distance between \(n\) points in their respective spaces, and \(n\) random sample points will form the side lengths of multiple virtual polygons. Second, the dissimilar vector \(\overrightarrow{\delta}\) between the side lengths of virtual polygons is calculated. Finally, compare \(\overrightarrow{\delta}\) with the preset side length similarity threshold \(\varepsilon_{\textit{ploy}}\). If \(\|\overrightarrow{\delta}\|\leq\varepsilon_{\textit{ploy}}\), continue to the next step, otherwise return to the first step. Taking \(n=3\) as an example, the calculation formula \(\overrightarrow{\delta}\) is shown in Formula (7):  
\[\overline{\delta}=\left[\frac{d_{12}^{p}-d_{12}^{q}}{\max(d_{12}^{p},d_{12}^{ q})},\frac{d_{23}^{p}-d_{23}^{q}}{\max(d_{23}^{p},d_{23}^{q})},\frac{d_{13}^{p}-d_{13} ^{q}}{\max(d_{13}^{p},d_{13}^{q})}\right] \tag{7}\]  
The calculation principle of \(\overrightarrow{\delta}\) is shown in Figure 5:  
(3) Use \(n\) corresponding point pairs \((p_{1}\), \(q_{1})\), \((p_{2}\), \(q_{2})\),..., \((p_{n}\), \(q_{n})\) to estimate the transformation matrix \(\hat{T}\), and the source point clouds \(P\) is transformed into point clouds \(P^{\prime}\) after \(\hat{T}\) transformation. The nearest neighbor Euclidean distance between the point clouds \(P^{\prime}\) and the target point clouds \(Q\) is then calculated. Next, let the point which its nearest Euclidean distance in the point clouds \(P^{\prime}\) is less than the preset distance threshold \(\varepsilon_{\textit{RANSAC}}\) as the interior point, and calculate the distance between the interior point and the corresponding point by the formula of \(\varepsilon(T)=\sum\limits_{p^{\prime}\in P^{\prime}}\left(p^{\prime}-q\right) ^{2}\). If the number of interior points is too small, return to the first step;  
(4) Re-estimate the transformation matrix \(\hat{T}\) according to the relationship between the interior point and the corresponding point in the target point clouds \(Q\), and perform continuous iteration. When \(\varepsilon(T)\) reaches the minimum value or reaches the maximum number  
Figure 5: The calculation principal diagram of \(\overrightarrow{\delta}\).  
of iterations \(t_{RANSAC}\), the iteration is stopped, and the optimal transformation matrix \(\hat{T}_{0}\) is obtained at this time. The calculation formula of \(t_{RANSAC}\) is shown in Formula (8):  
\[t_{RANSAC}=\frac{\log(1-\rho)}{\log(1-\omega^{n})} \tag{8}\]  
where \(\rho\) is the given expected success probability and \(\omega\) is the expected inline score. The expected inline score is the percentage of interior points in a data set that contains both interior points (points that are suitable for the model) and exterior points (points that are not suitable for the model).