## 3 Methodology
### Accurate Transformation Estimation
#### 3.3.2 Coarse Transformation Estimation  
So far, a correspondence set \(\mathbf{\mathcal{C}}\) is constructed between \(\mathbf{\mathcal{P}_{S}}\) and \(\mathbf{\mathcal{P}_{T}}\). The goal of coarse transformation estimation is to find an optimal rigid transformation \(\mathbf{\mathcal{T}_{\theta}}\) from \(\mathbf{\mathcal{C}}\). The RANSAC algorithm and its variants [29; 30] are popular approaches to solving the problem. However, they face challenges due to a lack of robustness and a high time consumption. To estimate \(\mathbf{\mathcal{T}}_{o}\), we put forward a coarse transformation estimation method based on clustering. The steps are outlined below in detail.
* Generate a \(\mathbf{\mathcal{T}}_{i}\) from a correspondence \(\mathbf{\mathcal{C}}_{i}\). In theory, a correspondence \(\mathbf{\mathcal{C}}_{i}\) is inadequate to estimate a rigid transformation between a pair of point clouds. Yet, if a correspondence is oriented with a local reference frame (LRF), estimating a rigid transformation is adequate [34]. We have constructed the LRF for each point during the keypoint detection with boundary removal, and we can utilize the LRFs to estimate transformations. The following are the formulas for estimating a rigid transformation: \[R_{i}=\Big{(}LRF_{S}^{f^{\prime}}\Big{)}^{\mathrm{T}}LRF_{T}^{i}\] (28) \[t_{i}=kp_{T}^{i}-kp_{S}^{f^{\prime}}R_{i}\] (29) where \((kp_{T}^{i},kp_{S}^{f^{\prime}})\) is a matched keypoint pair, \(LRF_{S}^{f^{\prime}}\) and \(LRF_{T}^{i}\) are local reference frames of \(kp_{S}^{f^{\prime}}\) and \(kp_{T}^{i}\), respectively, and \(R_{i}\) and \(t_{i}\) signify a rotation matrix and a translation vector. The advantage of correspondence over traditional RANSAC is that the computational complex is lowered from \(O\big{(}n^{3}\big{)}\) to \(O(n)\), where \(n\) is the number of correspondences.
* Estimate an optimal rigid transformation based on clustering. Each rotation matrix \(R_{i}\) is transformed to Euler angle rotations and concatenated with the corresponding translation vector \(t_{i}\) to generate a six-dimensional vector before clustering. Each 6D vector denotes six degrees of freedom, consisting of three rotations and three translations along the x, y, and z axes. The k-means clustering algorithm is then used to cluster these 6D vectors and construct \(\kappa\) clusters, with each cluster center being a transformation \(\mathbf{\mathcal{T}}\) that includes a rotation and translation. The next step is to extract a translation vector and a rotation matrix from the cluster center. Then, we transform the source point cloud \(\mathcal{P}_{S}\) using the transformation described above, naming it \(\mathcal{P}_{S}^{f^{\prime}}\). For every point in \(\mathcal{P}_{S}^{f}\), we find its nearest point in \(\mathcal{P}_{T}\), and we consider a point \(p_{S}^{f^{\prime}}\) in \(\mathcal{P}_{S}^{f}\) to be an inlier if the distance between \(p_{S}^{f^{\prime}}\) and its nearest point \(p_{T}^{j}\) in \(p_{T}^{j}\) is less than a threshold, i.e., \[\left\|p_{S}^{f^{\prime}}-p_{T}^{j}\right\|<c_{d}\] (30) and, after that, the definition of the ratio of inliers is shown as follows: \[rt_{inliers}=n_{inlines}/n_{s}\] (31) in which \(n_{inlines}\) represents the number of inliers and \(n_{s}\) represents the number of points in \(\mathcal{P}_{S}\). Finally, we choose an optimal \(\mathcal{T}\) as \(\mathcal{T}_{o}\), whose \(rt_{inliers}\) is the highest.