Fast Robust Point Cloud Registration Based on Compatibility Graph and Accelerated Guided Sampling

Abstract

Point cloud registration is a crucial technique in photogrammetry, remote sensing, etc. A generalized 3D point cloud registration framework has been developed to estimate the optimal rigid transformation between two point clouds using 3D key point correspondences. However, challenges arise due to the uncertainty in 3D key point detection techniques and the similarity of local surface features. These factors often lead to feature descriptors establishing correspondences containing significant outliers. Current point cloud registration algorithms are typically hindered by these outliers, affecting both their efficiency and accuracy. In this paper, we propose a fast and robust point cloud registration method based on a compatibility graph and accelerated guided sampling. By constructing a compatible graph with correspondences, a minimum subset sampling method combining compatible edge sampling and compatible vertex sampling is proposed to reduce the influence of outliers on the estimation of the registration parameters. Additionally, an accelerated guided sampling strategy based on preference scores is presented, which effectively utilizes model parameters generated during the iterative process to guide the sampling toward inliers, thereby enhancing computational efficiency and the probability of estimating optimal parameters. Experiments are carried out on both synthetic and real-world data. The experimental results demonstrate that our proposed algorithm achieves a significant balance between registration accuracy and efficiency compared to state-of-the-art registration algorithms such as RANSIC and GROR. Even with up to 2000 initial correspondences and an outlier ratio of 99%, our algorithm achieves a minimum rotation error of 0.737° and a minimum translation error of 0.0201 m, completing the registration process within 1 s.

1. Introduction

Point cloud registration is a fundamental task in remote sensing [1,2], robot perception [3,4], photogrammetry [5], and other fields, and has been applied to a variety of technologies such as 3D reconstruction [6], structural health monitoring [7,8], target recognition and localization [9], simultaneous localization, and mapping [10]. Due to the fixed limitations of the laser scanner in terms of field of view and viewpoints, a single data acquisition with fixed viewpoints can only capture part of the point cloud of a scene. In order to obtain a complete 3D representation of the scene, it is necessary to fuse and splice the point clouds with different viewpoints. The goal of point cloud registration lies in estimating the optimal rigid transformation between the two point clouds in order to accurately align the point clouds under different viewpoints.

The feature-based global registration method is the mainstream method for point cloud registration [11]. It generally consists of two stages: the feature extraction stage and the robust transform estimation stage. The feature extraction stage extracts key points and generates feature descriptors, and establishes the correspondence between two point clouds based on the similarity of the feature descriptors between the points. The robust transform estimation stage estimates the transformation parameters between two point clouds based on the correspondence. Many well-differentiated point cloud description methods have been proposed, such as FPFH [12], RoPS [13], SDASS [14], etc. However, noise is still unavoidable, mainly due to (1) Most of the point clouds partially overlapping, so the established correspondences may be inliers only if they are located in overlapping regions, while correspondences in non-overlapping regions introduce a large number of outliers. (2) The presence of many similar local surfaces in the point cloud, resulting in very similar corresponding feature descriptors, and forming false correspondences. Since the correspondences established in the feature extraction stage usually have a large number of outliers, the reliability of the robust transform estimation is seriously affected. Therefore, one of the difficulties in feature-based point cloud registration is how to select inliers from the correspondence containing a large number of outliers and then accurately estimate the transformation parameters.

In recent years, a large number of robust transform estimation methods have been proposed. Random sampling consistency (RANSAC) [15] is the most commonly used method in robust transform estimation. RANSAC solves the transform parameters by iteratively sampling the minimum subset, and then selects the hypothesis of the maximum number of inliers as the estimation parameter. RANSAC requires a large number of iterations and does not guarantee obtaining the optimal solution, and, moreover, it cannot deal with the situation where the outlier ratio is very high. In order to cope with the problem of a very high outlier ratio in the correspondence, many methods choose to use the geometric properties corresponding to the inliers to identify the inliers. GORE [16] utilizes geometric consistency to exclude outliers. VODRAC [17] and RANSIC [18] establish the minimum subset by judging the compatibility between the sampled points, and use the compatible subset to generate the hypothesis transformation matrix. However, pairwise consistency is not sufficient since outliers are equally likely to occasionally satisfy length consistency. SC2-PCR [19] is further used to distinguish between inliers and outliers by computing second-order spatial compatibility. These methods have been shown to be effective in improving the parameter estimation problem in the case of a high outlier ratio, but there are still some limitations, such as the extremely low computational efficiency of RANSIC when the outlier ratio is too high, which limits the practical application of the algorithm.

Despite the great progress made in current research, it is still a challenging task to determine the inliers from correspondences containing a large number of outliers. Currently, feature-based point cloud registration algorithms suffer from the following problems: (1) Due to the diversity of scenes, the outlier ratio varies in different scenes, which limits the robustness and adaptability of the algorithms. (2) When the number of correspondences is high or the outlier ratio is too high, the parameter estimation process becomes very time-consuming and inefficient. (3) How to select the inliers from a large number of outliers and estimate the transformation parameters accurately is very difficult. To address the problem of fast robust point cloud registration containing a large number of outliers, we propose a fast robust point cloud registration algorithm based on a compatibility graph and accelerated guided sampling, which can realize the accurate registration of the corresponding point cloud that is seriously contaminated by the outliers, and, at the same time, has a high computational efficiency. The contribution of this paper is mainly:

• Constructing a compatibility graph based on the compatibility between inliers and proposing a minimum subset sampling method combining graph edge sampling and graph vertex sampling to reduce the influence of outliers on the registration results.
• Introducing a preference-based accelerated guided sampling strategy that utilizes the hypothetical model generated during the iterative process to guide the subsequent samples to be biased toward the inliers, achieving efficient and robust point cloud registration.
• Compared to many existing state-of-the-art methods, the proposed algorithm is able to cope with a very high outlier ratio (outlier ratio > 99%) and strikes a remarkable balance between registration accuracy and efficiency.

2. Related Works

A key step in feature-based point cloud registration algorithms is to establish the correspondences between the source and target point clouds based on local feature descriptors. Feature descriptors have been widely studied in the past decades, and traditional descriptors such as PFH [20], FPFH [12], SHOT [21], and RoPS [13] describe the local geometric structure of the point cloud from different measurements. In order to further improve the descriptive performance of descriptors, TOLDI [22], SDASS [14], and KDD [23], introducing additional information such as local reference frame or point density features can more effectively describe the local features of the point cloud and generate more reliable correspondences. With the rapid development of deep learning technology, learning-based descriptors have received more attention due to their excellent differentiation and robustness. Learning-based local feature extraction modules usually use frameworks such as point-pair features [24,25], local reference frame [26], and rotationally invariant networks [27]. These learning-based feature description methods have good generalization but are usually computationally inefficient. Recently, Transformer [28] has also been successfully applied to 3D feature matching with promising results. Predator [29] introduces an overlap-aware module based on self-crossing and self-attention. CoFiNet [30] utilizes an attentional mechanism to aggregate the contextual information between two piece point clouds. GeoTrans [31] employs a geometric Transformer module to encode rotationally invariant geometric features of point clouds, which generates model assumptions using local correspondences and performs model validation using global fitness, thus accomplishing local-to-global alignment. These algorithms are effective in detecting overlapping regions and are shown to have the potential to solve the low overlap rate registration problem. Although current feature-matching methods can establish robust correspondences, a large number of outliers in the constructed correspondence set still inevitably exist. Therefore, it is necessary to rely on model-fitting methods for robust rigid transformation estimation.

The main robust estimation methods that have been used to solve the point cloud registration problem include M-estimation [32], truncated least squares [33], Lp-paradigm [34], and RANSAC family [15]. Since a large number of outliers will inevitably exist in the initial correspondence, how to estimate the accurate model parameters from the data containing a large number of outliers is the difficulty of robust transformation. In order to solve this problem, many researchers have proposed registration algorithms based on outlier filtering, and the core of these methods lies in removing the wrong matches in the correspondences, so as to avoid dealing with outliers in the registration process. Fast global registration (FGR) [35] is one of the typical algorithms that removes outlier points by geometric tests, then uses Geman McClure as the objective function and proposes a global method that combines a line process with robust estimation to optimize the model parameter estimation process. Similarly, Li et al. [36] constructed a topological graph based on correspondences, then proposed a side-voting strategy to remove outliers, and proposed a Cauchy-weighted Lq-paradigm as the cost function to achieve robust registration with a 90% outlier rate. A guaranteed outlier removal strategy was introduced in GORE [16], which removes outliers from correspondences by computing a simple geometric consistency test. A cleaner set of correspondences is obtained, which guarantees a globally optimal solution, but its high computational complexity leads to very low efficiency. CLIPPER [37] incorporated the concept of geometric consistency into the graph theoretic framework by finding dense subgraphs to determine the inliers. In order to improve the registration efficiency, Yang et al. [38] introduced a truncated least squares cost that is insensitive to the outliers to deal with the transformation parameter estimation problem, and rewrote the problem as a quadratically constrained quadratic programming problem. They proposed a convex semidefinite programming relaxation for the optimal solution, which can achieve the computation of the verifiable optimal solution under the condition of 95% outliers while guaranteeing efficiency. Zhang et al. [39] proposed a point cloud registration approach based on a Maximal cluster (MAC). MAC first constructs the initial correspondence compatibility graph, then searches for the largest clusters in the graph, and finally selects the largest clusters with large weights to calculate the transformation assumptions in combination with the SVD algorithm. While this approach accurately obtains the optimal transformation parameters, it suffers from low computational efficiency. Li et al. [40] use the correspondence matrix and the generalized correspondence matrix to seek the corresponding tight upper bounds and lower bounds, and then combine them with an adaptive Cauchy’s estimator for optimal parameter estimation. Yao et al. [41] proposed a global-to-local registration method and introduced a hypergraph consistency module to learn the high-order consistency of guided sampling to obtain more reliable clusters of inliers. Second-order spatial compatibility was proposed in SC2-PCR++ [19] to distinguish the inliers from the outliers at an early stage. GROR [42] introduced the concepts of graph node reliability and graph edge reliability by constructing a correspondence graph to quickly and accurately remove the inliers from the outliers. Li et al. [43] proposed a maximum group correspondence selection strategy based on reliable edges, which combines the adaptive Maxwell–Boltzmann (AMB) algorithm and confidence intervals to estimate the rotation and translation parameters.

The RANSAC algorithm is another pipeline widely used in correspondence-based point cloud registration, but the randomness of the algorithm itself leads to its low accuracy and the need for a large number of samples in order to find a relatively correct solution, which is likely to fail on the data with serious contamination of outliers. Many improved algorithms have been proposed to address the problems of RANSAC [44,45,46]. Maximum Likelihood Estimated Sample Consistency (MLESAC) [47] improves the robustness of RANSAC by replacing the cost function from the size of the consistent samples to maximize the likelihood. Locally Optimized RANSAC (LO-RANSAC) [45] performs local optimization by deriving solutions from random samples, which improves speed by two to three times compared to standard RANSAC. Wu et al. [48] introduced a particle swarm optimization algorithm in RANSAC to directly sample the model parameters and achieved good results in image alignment. GESAC [49] introduced a graph to enhance the sample consistency and achieved effective registration even if there are outliers in the smallest subset of the sampled points. ICOS [50] accelerated the search for inliers by constructing a compatibility structure. One-Point RANSAC [32] introduced a scale-annealing bi-weighted estimator to stepwise optimize the estimation of the transform parameters. Invariant and compatible random selection of minimum subsets are introduced in RANSIC [18]. Hu et al. [17] proposed a fast robust point cloud registration algorithm based on election-compatible weighted two-point random sampling (VODRAC), which combines scale-invariant constraints with a two-point random sampling framework, and can achieve fast candidate inliers search. Cheng et al. [51] proposed a point cloud registration algorithm based on local sampling and global hypothesis generation. Gentner et al. [52] proposed a graph-based maximum consistency alignment algorithm (GMCR), in which a novel consistency function was introduced specifically to translate the consistency maximizing objective into the graph domain. The algorithm is robust to various types of outliers. C-RANSAC [53] introduces a scale histogram-based outlier filtering method and involves a master–slave handshake mechanism for optimal parameter estimation, which achieves high-accuracy registration and fast convergence.

3. Methods

In this Section, we propose a novel fast robust point cloud registration based on a compatibility graph and accelerated guided sampling. We first introduce the problem formulation of registration and describe the framework of the proposed method. Then, we introduce in detail the key processes, including the correspondence compatibility graph construction, the minimum compatible subset sampling, the preference-based guided sampling strategy, and the complete registration algorithm.

3.1. Problem Formulation

The procedure of the feature-based point cloud registration algorithm is to establish the correspondences between the source and target point clouds based on the local feature descriptors, and then estimate the registration parameters based on the correspondences. We first give the method of the correspondence establishment. Assume that the two point clouds to be aligned are called source point cloud $P_s$ and target point cloud $P_t$. (1) Due to the excessive number of points in the initial point cloud, which contains a large amount of redundant information, the key point estimation technique is first used to estimate the key points $P_{sf}$ = $\left\{x_i|1\le i\le N\right\}$ and $P_{tf}$ = $\left\{y_j|1\le j\le N\right\}$ of the source and target point clouds, respectively. (2) Generate feature description vectors for key points using feature descriptors, e.g., classical FPFH, learning-based GeoTrans. (3) For each key point $x_i$ in $P_{sf}$, the nearest neighbor $y_i$ corresponding to $x_i$ in $P_{tf}$ is obtained based on the feature description vectors using a KD-Tree, so that the initial correspondence set C = $\left\{\left(x_i, y_i\right)|1\le i\le N\right\}$ of $P_s$ and $P_t$ can be established.

Since $P_s$ and $P_t$ are usually partially overlapping, and the feature descriptors cannot completely and accurately distinguish each point in $P_s$ and $P_t$, a large number of incorrect correspondences inevitably exist in C. The purpose of the feature-based point cloud registration method is to estimate the transformation parameters of the source and target point clouds based on the correspondence set. The objective function is denoted as

$$\underset{R,t}{minimize}{\displaystyle \sum _{i=1}^N\left|\right|y_i-(R{x}_i+t)|{|}^2}$$

(1)

where R∈SO(3) is an orthogonal rotation matrix, t is a 3 × 1 translation vector, ($x_i$,$y_i$) is a correspondence in the correspondence set C, $\parallel ·\parallel$ denotes L2-norm.

Due to the large number of wrong correspondences in the initial correspondences, the above objective function can be further expressed as a maximizing consensus problem, denoted as

$$\begin{array}{l}\underset{R,t,I\subset C}{maximize}\left|I\right|\\ Subject to \left|\right|y_i-(R{x}_i+t)\left|\right|<\epsilon ,\forall (x_i,y_i)\in I\end{array}$$

(2)

where I is called the consensus set, |I| denotes the size of the consensus set, ε is an inliers threshold, and (R, t) corresponding to the consensus set is considered to be the optimal transformation parameter. In order to search for the maximum consensus set in the initial correspondences, the commonly adopted approach is to sample a series of minimum subsets (a subset consisting of three points) from the initial correspondences for estimating (R, t), and then to compute the correspondences in the initial correspondences that are consistent with the minimum subset, i.e., correspondences that satisfy $\left|\right|y_i-\left(R{x}_i+t\right)\left|\right|<\epsilon$. Finally, the set with the most consensus correspondences is selected as the maximum consensus set. To address the above question, we propose a sampling consistency algorithm that combines a compatibility graph and accelerated guided sampling. The overall framework of the algorithm is shown in Figure 1, by constructing the compatibility graph structure of the initial correspondences, combining graph edge sampling and graph vertex sampling to obtain the minimum compatible subset, and introducing a preference-based accelerated guided sampling strategy to search for the optimal minimum subset so as to determine the maximum consensus set and estimate the transformation parameters.

3.2. Correspondence Compatibility Graph Construction

In our approach, the selection of the inliers of the correspondences will be performed on a graph structure, which is a better representation of the compatibility degree between correspondences than the Euclidean distance space. Therefore, it is first necessary to construct an undirected graph of the initial correspondences, where each correspondence is represented as a graph vertex, and geometrically compatible nodes are connected by graph edges.

For the initial correspondence set C, suppose that two elements in C are $c_i$ = ($p_{si}$, $p_{ti}$) and $c_j$ = ($p_{sj}$, $p_{tj}$), where $p_{si}$, $p_{sj}$ denote two points in the source point cloud and $p_{ti}$, $p_{tj}$ denote two points in the target point cloud corresponding to $p_{si}$, $p_{sj}$. The compatibility between $c_i$ and $c_j$ can be quantitatively measured as

$$d_{cmp}(c_i,c_j)=\left| ‖p_{si}-p_{sj}‖-‖p_{ti}-p_{tj}‖ \right|.$$

(3)

When $c_i$ and $c_j$ are ideal inliers, $d_{cmp}$($c_i$, $c_j$) = 0. Noise inevitably exists in the point cloud, and $d_{cmp}$($c_i$, $c_j$) cannot be strictly 0. Therefore, when $d_{cmp}$($c_i$, $c_j$) < ε, it indicates that $c_i$ and $c_j$ are compatible and considered to be inliers.

Construct a compatibility graph based on the compatibility between any vertices, given an initial set of correspondences C = $\left\{c_i\right|1\le i\le N\}$, the graph formed by them denoted as G = (V, E), with V being the vertices of the graph and V = $\left\{c_i\right|1\le i\le N\}$, E being the edges of the graph and E = $\left\{e_{ij}\right|1\le i\le N,1\le i\le N\}$, where $e_{ij}$ = ($c_i$, $c_j$). In the process of constructing the graph, for two correspondences $c_i$ and $c_j$, they are considered compatible so that $e_{ij}$ is in E only when $d_{cmp}$($c_i$, $c_j$) < ε, and in this way the compatibility graph of C is constructed. At the same time, we build an N × N compatibility matrix $M_C$, and when $d_{cmp}$($c_i$, $c_j$) < ε, the corresponding positional element of $M_C$, $M_C$(i, j) = 1, which indicates that the correspondences $c_i$ and $c_j$ are compatible, and $M_C$(i, j) = 0, otherwise denoted as:

$$M_C(i,j)=\left\{\begin{array}{c}1, if d_{cmp}(c_i,c_j)<\epsilon \\ 0, otherwise\end{array}\right.$$

(4)

3.3. Minimum Compatible Subset Sampling

In the traditional RANSAC algorithm, point cloud registration requires randomly selecting three correspondences to form a minimum subset, and then combining them with Horn’s triad-based method [54] to estimate the transformation parameters between two point clouds. Due to the presence of a large number of outliers, the probability of RANSAC sampling to a minimum subset of all inliers is extremely low. According to [17], when the outlier ratio in the correspondences is certain, the number of iterations required for RANSAC to sample a subset of all inliers grows exponentially with the size of the minimum subset, and a large number of iterations are often required to obtain a more optimal solution. In order to reduce the influence of the outliers, this paper introduces a compatible minimum subset sampling method based on the constructed compatibility graph, and the method consists of two layers, the edge sampling layer, and the vertex sampling layer.

In the edge sampling layer, we first randomly select an edge $e_{ij}$ = ($c_i$, $c_j$) in the compatibility graph, and search the vertices connected to this edge to form a triangle as the candidate correspondence set Φ = {$c_k$|0 ≤ k ≤ K}. Then, enter the vertex sampling layer and randomly select a point $c_k$ in Φ, with $e_{ij}$ forming a minimal subset $s_k$ = {$c_i$, $c_j$, $c_k$}. Next, we use Horn’s method to compute the rotation and translation parameters, and compute the consensus set $L_k$ corresponding to the smallest subset $s_k$ of the candidate correspondence set Φ from the estimated transformation parameters. Repeat sampling in Φ until reaching the set maximum iteration number of vertex sampling $M{I}_v$ to obtain a series of consensus sets $L_V$ = {$L_k$|0 ≤ k ≤ $M{I}_v$}, and always retain the largest consensus set in $L_V$ as the best consensus set for the vertex sampling layer, i.e., $L_{best}=\underset{L_k\in L_v}{argmax}\left(\left|L_k\right|\right)$. To avoid too much redundant computation, each time we obtain a new $L_{best}$, we update $M{I}_v$ according to $L_{best}$. After the vertex sampling layer is completed, return to the edge sampling layer and use $L_{best}$ to compute the transformation parameters, and calculate the consensus set $G_n$ corresponding to the currently sampled edge in the initial correspondence C. Repeat the edge sampling until reaching the set maximum iteration number $M{I}_e$ of edge sampling, and the iterative process generates a series of consensus sets $G_E$ = {$G_n$|0 ≤ n ≤ $M{I}_e$}. Always retain the maximum consensus set $G_{best}=\underset{G_n\in G_E}{argmax}\left(\left|G_n\right|\right)$ during the iterative process. Similarly, each time we obtain a new $G_{best}$, we update $M{I}_e$ according to $G_{best}$. Finally, estimate the registration parameters using SVD [55] based on $G_{best}$. We dynamically adjust the maximum iteration number $M{I}_e$ of edge sampling and the maximum iteration number $M{I}_v$ of vertex sampling according to the consensus set size. Similarly to RANSAC [15], the maximum iteration number is updated by the following rule.

$$M{I}_v={\displaystyle \frac{\log (1-P_1)}{\log \left(1-\frac{\left|L_{best}\right|}{|\Phi |}\right)}}$$

(5)

$$M{I}_e={\displaystyle \frac{\log (1-P_2)}{\log \left(1-{\left(\frac{\left|G_{best}\right|}{N}\right)}^2\right)}}$$

(6)

where $\left|·\right|$ denotes the set size. $P_1$ and $P_2$ denote the probability of sampling at least one all-inlier subset for vertex sampling and edge sampling, respectively, and we set $P_1$ = $P_2$ = 0.99.

3.4. Preference-Based Guided Sampling Strategy

For an established compatibility graph, given a vertex $c_n$ ∈ G in the graph and $c_n$ denotes a correspondence, define the set of vertices in the compatibility graph that are compatible with $c_n$ as

$$N_{c_n}=\left\{c_{n^{\prime }}\right|M_C(n,n^{\prime })=1\}.$$

(7)

Based on the constructed compatibility graph G, according to the introduced minimum compatible subset sampling method, compatible edges are sampled in the graph and combined with compatible vertices to estimate the model, and a locally optimal model hypothesis can be obtained for each compatible edge sampled. Assuming that M edges are initially sampled through iterations, M model hypotheses are generated accordingly, denoted as H = $\left\{h_m\right|1\le m\le M\}$, where $h_m$ = ($R_m$, $t_m$), and the M+1th model is generated by the guided sampling strategy. Specifically, for each data $c_n$ = ($x_n$, $y_n$), we compute the residual distance r($c_n$, $h_m$) = $\left|\right|y_n-\left(R_m{x}_n+t_m\right)\left|\right|$ of $c_n$ with respect to the mth model hypothesis based on the Euclidean distance. We then introduce the preference function, which represents the degree of preference of a correspondence $c_n$ over a model hypothesis $h_m$, as follows:

$$f_m^n=\left\{\begin{array}{c}{e}^{-r^2(c_n,h_m)/{\delta }^2},if r(c_n,h_m)<{\tau }_m\\ 0,otherwise\end{array}\right.$$

(8)

where ${\tau }_m$ is an inlier threshold and δ is a regularization constant. Thus, the preferences of a correspondence $c_n$ for M model hypotheses in the set of model hypotheses H can be expressed as a set $f^n=\left[f_1^n, f_2^n,\cdots ,f_M^n\right]$. For any two correspondences $c_n$ and $c_{n^{\prime }}$, whose preference vectors are computed as $f^n$ and $f^{n^{\prime }}$, respectively. We use cosine similarity to compute the residual correlation between the two correspondences, denoted as

$$\phi (c_n,c_{n^{\prime }})={\displaystyle \frac{〈f^n,f^{n^{\prime }}〉}{\left|\right|f^n\left|\right|\times \left|\right|f^{n^{\prime }}\left|\right|}}$$

(9)

where $\langle ·,·\rangle$ and $\parallel ·\parallel$ denote the inner product and L2 norm, respectively. It is intuitive that inliers should be compatible with each other, and inliers should share many of the same modeling assumptions with each other. Thus, if two correspondences $c_n$ and $c_{n^{\prime }}$ are inliers, the corresponding similarity scores of them are high. Otherwise, if $c_n$ and $c_{n^{\prime }}$ are outliers, they do not have similar preferences for different modeling assumptions, so the corresponding similarity scores will be low.

Based on the mutual compatibility between inliers, high similarity scores of inliers should be accompanied by the existence of edge connections, so the similarity between $c_n$ and $c_{n^{\prime }}$ is further defined as

$$w(c_n,c_{n^{\prime }})=\left\{\begin{array}{c}\phi (c_n,c_{n^{\prime }}),c_{n^{\prime }}\in N_{c_n}\\ 0,c_{n^{\prime }}\notin N_{c_n}\end{array}\right.$$

(10)

where $N_{c_n}$ donates the set of vertices in the compatibility graph that are compatible with $c_n$, and satisfies Equation (7). Thus, the similarity scores of the spatially incompatible correspondences are set to 0, in which case the similarity matrix $M_s$ between the correspondences can be obtained and $M_s\left(n,n^{\prime }\right)$ = $w\left(c_n,c_{n^{\prime }}\right)$. Assuming that $c_n$ is fixed, the similarity score between $c_n$ and the jth corresponding $c_j$ in C is $D_{nj}=M_s\left(n,j\right)$. Finally, the similarity between $c_n$ and the rest of the data in C constitutes an association vector $D_n$

$$D_n=[D_{n1},D_{n2},\dots ,D_{nj},\dots ,D_{nN}].$$

(11)

As in [56], define the gap ${\gamma }_j$ as the difference between the maximum value of $D_n$ and $D_{nj}$

$${\gamma }_j=\max (D_n)-D_{nj}$$

(12)

${\gamma }_j$ is not less than 0, the smaller ${\gamma }_j$ is, the more similar $c_n$ is to $c_j$. Define the probability of ${\gamma }_j$ as

$$\eta ({\gamma }_j)={\gamma }_j/{\displaystyle \sum _{k=1}^N{\gamma }_k}$$

(13)

According to [57], the information provided by the jth correspondence is denoted as

$$e_j=-\log (\eta ({\gamma }_j)+\xi )$$

(14)

where ξ is a small positive value, and the sum of the information entropies of the remaining points in C on $c_n$ is

$$E{P}_n={\displaystyle \sum _{j=1}^N\eta ({\gamma }_j)e_j}.$$

(15)

The information entropy is computed for each vertex in G to form the vector $EP={\left[E{P}_n\right]}_{n=1}^N$. The smaller $E{P}_n$ indicates that $c_n$ is more likely to be an inlier, so the vertex with smaller information entropy is selected according to EP as the set of vertices participating in the subsequent sampling of the compatible edges for the next model estimation. The vertex selection strategy is denoted as follows.

$$\chi =\left\{c_n\right|E{P}_n<mean(EP)\}.$$

(16)

Using this method to select significant vertices that are more likely to be inliers, and sampling compatible edges in the set of significant vertices in the next iteration, effectively increases the probability of sampling the smallest subset of all inliers and speeds up the estimation of the optimal model.

3.5. Complete Registration Algorithm

Based on the compatibility graph and preference-guided sampling, we further propose a complete correspondence-based point cloud registration algorithm for clouds with a high outlier ratio. In order to control the selection process of significant vertices, we define a batch size b as well as a maximum inlier update time max_up. b controls the frequency of vertex information entropy computation; i.e., we perform the vertex information entropy computation only for every b model hypothesis generated. And max_up is used as the end condition of the algorithm; i.e., after significant vertices have been selected max_up times, it is considered that the inliers have been involved in enough iterations to have obtained the exact transformation parameters; i.e., it is considered that the optimal solution has been obtained and the iteration is ended. The flow of the algorithm is shown in Algorithm 1.

Algorithm 1. Proposed Method

4. Experimental Results

To validate the effectiveness of the proposed algorithm, we conducted a series of experiments on several datasets, including the synthetic dataset Stanford 3D Scanning Repository dataset, the indoor dataset 3DMatch, the low-overlap indoor dataset 3DLoMatch, and the outdoor dataset KITTI. The addresses of all datasets can be seen in the Data Availability Statement.

The Stanford 3D Scanning Repository dataset contains several mesh models, which were obtained by scanning with a range scanner, followed by registration and surface reconstruction techniques. In order to verify the basic performance of our algorithm, we constructed test data pairs by randomly generating rotation matrices and translation vectors as ground truth transformations. 3Dmatch [58] is a point cloud dataset of eight indoor scenes obtained from RGBD sequences, containing a total of 1623 test pairs, each with a real camera pose and an overlap of more than 30%. 3DLoMatch [29] is a dataset of the same eight scenes with an overlap of between 10% and 30%, containing a total of 1781 pairs. KITTI [59] is a large-scale outdoor LIDAR dataset, which provides 11 sequences with pose annotations. Its ground truth transformations are obtained by GPS with refinement by the standard iterative closest point (ICP) algorithm [60]. This dataset contains several thousand frames of data in each sequence, and data in the same sequence have a high overlap rate.

4.1. Synthetic Data Experiment

We use the armadillo [61] point cloud model from the Stanford 3D Scanning Repository dataset for basic performance validation of the algorithm. First, 1000 points are sampled in the initial point cloud model as key points $P_s$, then its scale is changed so that the point cloud is inside a 1m×1m×1m enclosing box. And then rigid transformation R∈SO(3) and t∈R³ are randomly generated and the initial point cloud model is transformed to obtain the transformed point cloud, where the transformed key points are $P_t$. To make the experiment closer to the real situation, we add Gaussian noise with a mean value of 0 and a standard deviation σ = 0.01 to the transformed key points $P_t$ to simulate the noise present in the actual collected data, and obtain an inlier set $C_{in}$ = ($P_s$, $P_t$). To obtain the outliers, we generate $N_{out}$ random points $Q_{out}$ in a spherical space with the center of gravity of $P_t$ as the spherical center and the length of the diagonal of the bounding box of $P_t$ as the radius. Then, randomly select $N_{out}$ points $P_{out}$ in $P_s$ and release $P_{out}$ from matching with the corresponding points in $P_t$. Next, establish the correspondence between $P_{out}$ and $Q_{out}$ to form the outlier set $C_{out}$ = ($P_{out}$, $Q_{out}$), and the corresponding set C containing outliers is obtained by replacing the positions in $C_{in}$ with the same index as $C_{out}$. In order to simulate the case of different outlier ratios, by changing the value of $N_{out}$, set the outlier ratio at {20%, 40%, 60%, 80%, 90%, 92%, 94%, 96%, 98%, 99%}. Figure 2 shows the key points obtained by subsampling the point cloud and the initial correspondences of different outlier ratios, respectively. Due to the randomness of the noise distribution, each experiment is repeated 50 times to ensure the stability of the results.

In order to quantitatively assess the performance of the registration algorithms, the widely used rotation error ($E_R$) and translation error ($E_t$) are used as evaluation criteria [62], which are respectively

$$\left\{\begin{array}{c}{E}_R=\left|\arccos {\displaystyle \frac{tr(R_{GT}^{\mathrm{T}}{R}_e)-1}{2}}\right|\cdot {\displaystyle \frac{180°}{\pi }}\\ E_t=\left|\right|t_{GT}-t_e\left|\right|\end{array}\right.$$

(17)

where $R_{GT}$ and $t_{GT}$ denote the true values of the rotation and translation matrices, respectively. $R_e$ and $t_e$ denote the estimated values of the rotation and translation matrices, respectively, computed by the registration algorithm. tr(·) denotes the trace of the matrix. $E_R$ is used to measure the angular difference between $R_{GT}$ and $R_e$, and $E_t$ is used to measure the Euclidean distance between $t_{GT}$ and $t_e$. In addition, we evaluate the efficiency of the algorithm by comparing the running time ($T_c$) required for the registration.

In order to test the influence of the algorithm parameters on the experimental results, parameter analysis experiments are carried out. The main parameters involved in the proposed algorithm are the batch size b and the maximum number of updates of the inliers set max_up. For b, we first set max_up = 3, and increase b from 10 to 50 in steps of 10. Then we fix b to 20, and increase max_up from 2 to 6 in steps of 1. Experiments were carried out on data with different outlier ratios, and each parameter condition was run 50 times to record the mean rotation error, mean translation error, and mean time cost. The results of the experiments are shown in Figure 3.

According to the results, it can be seen that when b = 10, the rotation error and translation error are large; this is because at this time it is not possible to fully sample the inliers, resulting in the results having a larger error. When b = 20, the rotation and translation errors are relatively small, while the computational efficiency is high, and the accuracy and efficiency are in good balance. The time cost will increase significantly if b continues to increase. For max_up, when the outlier ratio is less than 98%, max_up has less influence on the experimental results. When the outlier ratio is 99%, max_up = 3 corresponds to a small mean rotation error and mean translation error. At the same time, the time cost is very little, which achieves a good balance in terms of accuracy and efficiency. Therefore, in this paper, b and max_up are set to 20 and 3, respectively.

In order to verify the performance of our algorithm equivalent to advanced robust point cloud registration algorithms, we compare the proposed method with six state-of-the-art algorithms, namely, RANSAC [15], GORE [16], One-Point RANSAC [32], GROR [42], RANSIC [18], and VODRAC [17]. Among these algorithms, RANSAC is the widely used initial registration algorithm, GORE and GROR are the most recently proposed provable and have good outlier filtering performance. One-Point RANSAC, RANSIC, and VODRAC are recently proposed state-of-the-art algorithms and show excellent performance in point cloud registration tasks heavily contaminated by outliers. Specifically, we set the maximum number of iterations to ${10}^5$ for all RANSAC-type algorithms and set the inlier threshold to 6pr for all algorithms, where pr denotes the resolution of the input point cloud [63]. pr is obtained by summing and averaging the distances between each point and its nearest neighbor. The parameters of the different algorithms are shown in

Table 1. Detailed Settings of the Compared Algorithms.

Method	Parameters
RANSAC	Maximum number of iterations: 105; inlier threshold: 6pr
GORE	Lower bound: 0; repeat: true; consistent threshold: 6pr
One-Point RANSAC	Confidence: 0.99; subset size: 1; Maximum number of iterations: 105; step size: 1.3
GROR	reliable set size: 800; inlier threshold: 6pr
RANSIC	Maximum number of iterations: 105; Confidence: 0.99
VODRAC	Maximum number of iterations: 105; Confidence: 0.99; inlier threshold: 6pr
Ours	Maximum number of iterations: 105; inlier threshold: 6pr P1 = P2 = 0.99; b = 20; max_up = 3; δ = 10pr; ξ = 10−6

and are the same for the rest of the experiments.

The registration results of different algorithms are shown in Figure 4 and some visualization results are shown in Figure 5. From the results, it can be seen that RANSAC can be useful when the outlier ratio is lower than 80%. The algorithm fails when the outlier ratio continues to increase, and the rotation and translation errors of the parameters estimated by RANSAC are large. GORE maintains a stable performance under different outlier ratios due to its ability to reliably remove the outliers and its robustness to noise. However, it exhibits limited registration accuracy, and the computational complexity of GORE is high. The time it takes to complete registration is usually several orders of magnitude higher compared to the other algorithms. When the outlier ratio is lower than 98%, One-Point RANSAC shows competitive performance in terms of registration accuracy and registration efficiency, but when the outlier ratio is 99%, the registration accuracy of the algorithm decreases rapidly, and the algorithm usually fails to estimate the correct registration parameters. GROR maintains good registration accuracy at different outlier ratios. While the registration efficiency decreases with the increase in the outlier ratio, the algorithm takes a long time to complete the registration. Both RANSIC and VODRAC have good robustness to outliers, and maintain high registration accuracy even when the outlier ratio is very high. When the outlier ratio is as high as 99%, the rotation and translation errors of the parameter estimated by RANSIC are about 1.221° and 0.0061 m, respectively, and the rotation and translation errors of the parameter estimated by VODRAC are about 1.655° and 0.0075 m. The registration efficiency of VODRAC increases first and then decreases with the increase in the outlier ratio. When the outlier ratio is 80%, the registration efficiency is highest, and it takes about 0.085 s to complete the registration. When the outlier ratio is lower than 96%, the registration efficiency of RANSIC is very high, and is higher than that of VODRAC. When the outlier ratio is higher than 96%, the time required for RANSIC to complete the registration increases significantly, and when the outlier ratio is 99%, RANSIC takes about 20.46 s to complete the registration.

As can be seen from the results, the proposed algorithm has excellent performance in terms of rotation error, translation error, and time cost. When the outlier ratio is lower than 96%, compared with other algorithms, the proposed algorithm exhibits remarkably low levels of both rotation and translation errors, and its time cost remains consistently stable at 0.035 s. When the outlier ratio is higher than 96%, the proposed algorithm still maintains a very high registration accuracy. When the outlier ratio is 96% and 98%, the proposed algorithm efficiency is significantly higher than the RANSIC and VODRAC algorithms. When the outlier ratio is 99%, One-Point RANSAC is no longer able to accurately estimate the registration parameters despite its low time cost, while the proposed algorithm still has a high accuracy. The excellent performance of the algorithm proposed in this paper can be attributed to the following factors: (1) The compatibility graph is constructed with full consideration of the compatibility relationship between the inliers, which can avoid the influence of the outliers on the registration results and ensure the accuracy of the algorithm. (2) The minimum subset sampling is split from three-point random sampling into compatible edge sampling and candidate subset sampling, which effectively reduces the computational complexity. (3) A guided accelerated sampling strategy is introduced, by calculating the preference between the correspondence and the estimated parameter to determine the inliers faster, which effectively improves the speed of convergence of the parameter estimation.

4.2. Challenging Real-World Data Experiments

To evaluate the registration performance of the proposed algorithm on real-world data, we conduct registration experiments using the 3DMatch dataset [58], which contains a total of 8 scenes, namely, Kitchen, Home1, Home2, Hotel1, Hotel2, Hotel3, Studyroom, and Lab. In each scene, we select 20 data pairs that overlap as test data. For each data pair, we adopt the Harris3D key point detection algorithm [64] to sample about 2000 key points in the source and target point clouds, respectively. Then, we use the FPFH [12] descriptor to obtain the feature vectors of the key points, and then further establish the initial correspondences between the two point clouds based on the feature descriptors. A pair of data is selected from each scene, and the initial correspondences are shown in Figure 6, where the red lines indicate the wrong correspondences, i.e., the outliers, and the green lines indicate the correct correspondences, i.e., the inliers. It can be seen that the initial correspondence set is contaminated by a large number of outliers, which makes it extremely challenging to align accurately.

The registration experiments on the 3DMatch dataset also compare six registration algorithms, including RANSAC, GORE, GROR, One-Point RANSAC, RANSIC, and VODRAC. We compare the rotation error, translation error, and time cost of the different algorithms. In order to qualitatively demonstrate the performance of the different algorithms, we select a pair of data pairs with low overlap between the source and the target point clouds from each scene for visualization, and the results of the different algorithms are shown in Figure 7. Visually, RANSAC can only roughly align the Lab scene, and similarly, GORE performs poorly, One-Point RANSAC performs slightly better and can effectively align two scenes, and GROR has a large improvement in performance, effectively aligning six scenes, but the algorithm fails for Home2 and Hotel3. Both RANSIC and VODRAC can complete the registration of all scenes, but RANSIC takes a lot of time to align each scene, and VODRAC is more efficient but still less efficient when the initial number of correspondences is very large. Our algorithm efficiently completes the registration of all the scenes, and the registration efficiency is very high in all cases, which proves the robustness and efficiency of the proposed algorithm.

Since FPFH is a manually designed feature descriptor, the correspondences established by it usually contain a large number of outliers with an outlier ratio of up to 99%. We record the rotation error, translation error, and time consumption of different algorithms. The experimental results are shown in Figure 8. The average outlier ratios and registration results of the experimental data for different scenarios are shown in

Table 2. Quantitative results on 3DMatch dataset.

	Kitchen	Home1	Home2	Hotel1	Hotel2	Hotel3	Studyroom	Lab
Mean outlier ratio	98.55%	98.74%	98.70%	98.96%	98.93%	98.83%	98.69%	98.74%
Mean Rotation Error (°)
RANSAC	60.854	70.984	86.465	60.237	72.172	70.028	86.584	71.358
GORE	56.389	62.745	65.342	42.885	38.998	47.645	42.732	89.329
One-Point RANSAC	50.128	65.939	79.379	44.533	45.151	45.930	45.533	72.256
GROR	14.382	6.920	19.685	9.135	0.943	7.842	24.886	12.356
RANSIC	1.794	1.173	1.189	1.133	0.984	1.029	1.079	1.022
VODRAC	1.395	1.040	1.004	0.842	0.949	1.047	1.194	1.142
Ours	1.147	0.909	0.999	0.737	0.933	0.931	1.122	0.921
Mean Translation Error (m)
RANSAC	1.4804	1.8729	1.9635	1.8119	1.7625	1.7233	2.1161	2.8324
GORE	1.5556	2.1000	2.1068	1.7491	1.8869	1.8829	1.4261	2.5204
One-Point RANSAC	1.1090	1.6728	2.1970	1.1921	0.9329	1.0032	1.4640	1.8214
GROR	0.2562	0.2826	0.5506	0.2687	0.0316	0.2386	0.6235	0.3536
RANSIC	0.0472	0.0469	0.0494	0.0490	0.0406	0.0417	0.0463	0.0540
VODRAC	0.0327	0.0321	0.0333	0.0302	0.0315	0.0357	0.0386	0.0461
Ours	0.0201	0.0327	0.0339	0.0304	0.0326	0.0327	0.0362	0.0407
Mean Time Cost (s)
RANSAC	3.398	4.967	6.426	8.389	7.457	8.276	4.134	11.439
GORE	0.469	1.697	1.867	0.921	0.494	1.370	1.618	2.154
One-Point RANSAC	0.299	0.354	0.364	0.434	0.432	0.430	0.283	0.446
GROR	2.778	3.554	3.332	4.069	3.828	3.857	2.829	3.494
RANSIC	69.001	57.093	151.787	182.039	183.542	119.140	116.414	326.279
VODRAC	1.983	2.643	2.773	3.300	3.246	3.260	2.013	2.989
Ours	0.759	1.129	1.121	0.948	1.155	0.826	0.804	2.001

.

Registration Accuracy Analysis: As shown in Table 2, the initial correspondences contain a large number of outliers, and the average outlier ratio of each scene is close to 99%. RANSAC can only achieve approximate registration for a few scenes, and the rotation and translation errors of most of the scenes are very large. This limitation is due to the fact that RANSAC needs to sample randomly in a large number of initial correspondences, which results in its inability to achieve effective registration within the set number of iterations. Its rotation and translation errors reach a maximum of 86.584° and 2.116 m. According to Figure 8a,b, under this condition of the number of correspondence sets and the outlier ratio, GORE and One-point RANSAC are also ineffective for most of the data pairs. They can only achieve accurate registration for a small portion of pairs, and the robustness of the algorithms needs to be further improved. In contrast, the performance of GROR is greatly improved. For most of the correspondences that are heavily contaminated by outliers, GROR can achieve accurate registration. As can be seen, many of the GROR registration results have a rotation error of less than 1°, and a translation error of less than 0.05 m. However, GROR still faces failures for individual data pairs. We speculate that this is due to the fact that an excessive number of outlier points affect the reliability of the algorithms in terms of graph node reliability and graph edge reliability, which leads to inaccurate final registration results. Under the condition that the correspondence set is heavily contaminated, RANSIC and VODRAC show excellent performance. Both of them can achieve accurate registration for each scene, in which the mean rotation error of RANSIC reaches a minimum of 0.984°, and the mean translation error reaches a minimum of 0.041 m. The mean rotation error of VODRAC reaches a minimum of 0.842° and the mean translation error reaches a minimum of 0.0302 m, which are significantly better than those of RANSAC, GORE, and One-Point RANSAC. According to the experimental results, the registration algorithm proposed in this paper reaches the advanced level in terms of registration accuracy, and can complete the accurate registration of all data pairs. The algorithm has good robustness to outliers, the mean rotation error of the registration results reaches 0.737° at the lowest level, and the mean translation error reaches 0.0201 m at the lowest level, which has a very high accuracy.

Registration efficiency analysis: Figure 8c shows the registration time distribution of different algorithms on eight scenes, and Table 2 records the average registration time of different algorithms for each scene. According to the results, it can be seen that the registration efficiency of RANSAC is low, and its running time is mainly related to the preset number of iterations, which requires a large number of iterative calculations to obtain relatively better results. The running time of GORE is very short because there are too few inliers in the correspondence. The algorithm cannot efficiently compute the upper and lower bounds, and it skips the computation of the parameter updating process. One-Point RANSAC has high running efficiency, which is due to the fact that the algorithm decomposes the registration problem, and the parameter space is drastically reduced, allowing it to quickly find what it considers to be the optimal solution. GROR has a high registration efficiency, generally taking 2~4 s to complete the registration. VODRAC has a slightly higher registration efficiency than that of GROR, which is due to the fact that it has the step of random sampling consistency decomposition. In the case of high outlier ratios, despite achieving accurate registration, the registration efficiency of RANSIC is very low, usually requiring tens or hundreds of seconds to complete the registration. In contrast, our algorithm has very high registration efficiency, and even if the initial number of correspondences reaches 2000 and is heavily contaminated by outliers, it can still compute very accurate registration results in less than 1 s in most cases.

4.3. Low-Overlap Point Cloud Registration Experiments

In order to verify the ability of the proposed algorithm to handle point cloud pairs with low overlap rate, we carried out experiments on 3DLoMatch, which contains 1781 test point cloud pairs and has a low overlap rate between point cloud pairs, with the overlap rate ranging from 10% to 30%. It is difficult to establish correspondences between these point cloud pairs by handcrafted descriptors. Recently, Transformer-based correspondence estimators have shown excellent performance on point clouds with low overlap rates to establish reliable correspondences between point cloud pairs. We use GeoTrans [31] to establish the correspondences of 3DLoMatch data and incorporate the proposed parameter estimation method to improve the registration performance. We evaluate the performance of the algorithm by using $E_R$, $E_t$ and registration recall (RR) [65]. RR is the proportion of the results with $E_R$, $E_t$ under the error threshold to the total number of test samples, i.e., the rate of successful registration, and we set the threshold to (15°, 0.3 m). As correspondences established using GeoTrans usually contain enough inliers, most data pairs can be successfully aligned. Following [65], since part of the failed registration can generate large rotation and translation errors, we only computed the mean rotation error (${\overline{E}}_R$) and translation error (${\overline{E}}_t$) of successfully registered point cloud pairs of each method to avoid unreliable metrics. A local-to-global (LGR) parameter estimation method is proposed in GeoTrans, and the experiments are compared with this method. The basic RANSAC algorithm and advanced algorithms including GROR and RANSAIC are also compared.

The experimental results obtained are shown in

Table 3. Registration results on 3DLoMatch with learning-based correspondences.

Method	${\overline{\mathit{E}}}_{\mathit{R} }$(°)	${\overline{\mathit{E}}}_{\mathit{t}}$(m)	RR (%)
LGR	2.992	0.0867	77.50
RANSAC	4.516	0.1385	61.93
GROR	3.186	0.1012	80.85
RANSIC	3.549	0.1143	79.79
Ours	2.967	0.0962	80.91

, and some qualitative results are shown in Figure 9. According to the experimental results, it can be seen that the proposed algorithm can effectively improve the registration recall by 3.41% compared to LGR, due to the more effective handling of the case of fewer inliers within the correspondences. As GROR and RANSIC are able to detect inliers in the correspondences, both of them provide some performance gains, while RANSAC has a poorer performance. The experiments illustrate that the proposed algorithm can effectively align point cloud pairs with very low overlap and achieve significant performance in conjunction with the learning-based descriptor.

4.4. Outdoor Scene Registration Experiments

To further validate the ability of the proposed algorithm to handle more complex scenarios, we conducted experiments on the outdoor LIDAR dataset KITTI, where the data scale of the outdoor scene is much larger than that of the indoor scene. As in [66], we selected scenes 8 to 10 as the test dataset and obtained a total of 555 test data pairs. Again, we used GeoTrans to establish the correspondences between the point cloud pairs and then combined the parameter estimation methods to estimate the registration parameters between the point cloud pairs. ${\overline{E}}_R$, ${\overline{E}}_t$, and RR are used to evaluate the experimental results, and the error threshold of RR is set to (5°, 0.6 m). LGR, RANSAC, GROR, and RANSAIC are used as comparison algorithms.

The experimental results are shown in

Table 4. Registration results on KITTI with learning-based correspondences.

Method	${\overline{\mathit{E}}}_{\mathit{R}}$(°)	${\overline{\mathit{E}}}_{\mathit{t}} \left(\mathbf{m}\right)$	RR (%)
LGR	0.378	0.0693	99.10
RANSAC	0.803	0.1861	98.38
GROR	0.505	0.1287	97.84
RANSIC	0.385	0.0872	99.10
Ours	0.341	0.0804	99.10

, and some visualized results are shown in Figure 10. From the experimental results, it can be seen that LGR, RANSAIC, and the proposed algorithm obtain the highest registration recall with high parameter estimation accuracy, and the proposed algorithm reaches the optimum in terms of rotation error. RANSAC achieves high registration recall, although the estimated parameters are usually sub-optimal but mostly within acceptable range. GROR performs slightly worse on the KITTI dataset compared to the other algorithms. It is experimentally verified that the proposed algorithm has excellent performance in estimating registration parameters and is common across different scenarios.

5. Discussion

In this paper, we propose a method for solving the problem of estimating transformation parameters in feature-based point cloud registration algorithms. For feature-based point cloud registration, high outlier ratios in correspondences established by feature descriptors are a common problem. The outlier ratio in correspondences established by classical handcrafted descriptors such as FPFH is usually higher than 90%. In this case, the proposed algorithm still obtains a high registration accuracy and maintains the optimal accuracy compared to algorithms such as RANSAC, GORE, and One-Point RANSAC. Meanwhile, the proposed algorithm has high registration efficiency, which is tens times faster than RANSIC and several times faster than GROR and VODRAC under the condition of a very high outlier ratio. In conclusion, our algorithm has superior robustness, accuracy, and computational efficiency compared with other state-of-the-art methods.

In terms of algorithm generality, the proposed algorithm takes correspondences as input and outputs the final registration parameters. Point cloud registration can be accomplished by combining any feature matching and correspondence establishment methods, such as handcrafted descriptors and learning-based descriptors. Due to the advanced feature description performance of the learning-based descriptors, combining them with the proposed method can be used for point cloud registration in low-overlap and complex scenarios, and a remarkable registration performance can be obtained. Combining the proposed algorithm with GeoTrans achieves a 3.41% improvement in registration recall on low-overlap point cloud datasets compared to LGR. The algorithm can also be applied to the registration of large-scale scenarios, and the proposed algorithm combined with GeoTrans for large-scale point cloud data registration also obtains the optimal performance.

Although the proposed algorithm is able to achieve fast and robust point cloud registration, it still has some limitations. Firstly, the proposed algorithm still relies on the initial correspondences. If the number of inliers in the correspondences is too small, the proposed algorithm may not be able to find enough correct inliers for parameter estimation, leading to the failure of the algorithm. Secondly, the algorithm relies on the Euclidean distance to determine the compatibility between the correspondences. However, the Euclidean distance has an inherent ambiguity in 3D space; i.e., the Euclidean distances from the surface of the sphere to the center of the sphere are all equal. This property may lead to a lack of stability in the compatibility calculation, thus affecting the performance of the algorithm.

6. Conclusions

In this paper, we present an efficient and robust point cloud registration method that directly outputs the final alignment registration based on correspondences and excels in terms of accuracy, efficiency, and robustness. Compared to many existing techniques, the algorithm in this paper operates efficiently under very high outlier conditions and strikes an excellent balance between efficiency and accuracy. In order to minimize the influence of the outliers, this paper introduces the concept of the compatibility graph, and proposes a minimum subset sampling method for the combination of compatible edges and compatible vertices, which effectively avoids the participation of a large number of outliers in the computation. A preference-guided accelerated sampling strategy is further proposed to effectively utilize the estimated transformation parameters at the initial stage, calculate the preference score of each vertex based on the transformation parameters, and then guide the execution of the sampling in the direction of more likely to be an inlier to improve the efficiency of registration. Finally, the transformation parameters are estimated based on the maximum set of compatible vertices to complete the accurate registration. Based on a synthetic and real dataset, the proposed registration algorithm is compared and analyzed with classical and advanced algorithms. Simulation experiments demonstrate the robustness and efficiency of the algorithm, which can still accomplish registration quickly when the outlier ratio is as high as 99%. Real data show that the algorithm can successfully perform point cloud registration even if the correspondence established by the feature description contains a large number of outliers. Compared with the state-of-the-art algorithms, the proposed algorithm is able to realize a point cloud registration several times faster while maintaining a comparable or higher registration accuracy. By combining the proposed algorithm with a learning-based feature description method, the registration accuracy can be further improved and can be applied to low overlap and large-scale point cloud registration tasks.

In follow-up work, as the proposed algorithm is still closely related to the quality of the initial correspondences, and more inliers can give more accurate results, designing more reliable correspondence establishment methods will be a priority. In addition, the proposed method relies on the Euclidean distance of the correspondence to compute the compatibility, and the compatibility results obtained are not stable enough, so exploring the compatibility of the correspondence with higher orders to further improve the parameter estimation performance and registration accuracy is another future research work.