Grid graph-based large-scale point clouds registration

ABSTRACT

Automatic registration of unordered point clouds is the prerequisite for urban reconstruction. However, most of the existing technologies still suffer from some limitations. On one hand, most of them are sensitive to noise and repetitive structures, which makes them infeasible for the registration of large-scale point clouds. On the other hand, most of them dealing with point clouds with limited overlaps and unpredictable location. All these problems make it difficult for registration technology to obtain qualified results in outdoor point cloud. To overcome these limitations, this paper presents a grid graph-based point cloud registration (GGR) algorithm to align pairwise scans. First, point cloud is divided into a set of 3D grids. We propose a voting strategy to measure the similarity between two grids based on feature descriptor, transforming the superficial correspondence into 3D grid expression. Next, a graph matching is proposed to capture the spatial consistency from putative correspondences, and graph matching hierarchically refines the corresponding grids until obtaining point-to-point correspondences. Comprehensive experiments demonstrated that the proposed algorithm obtains good performance in terms of successful registration rate, rotation error, translation error, and outperformed the state-of-the-art approaches.

KEYWORDS:

• Point cloud alignment
• scan matching
• graph algorithms
• reconstruction

1. Introduction

Point clouds are widely unitized for various applications such as 3D modeling (Montuori et al. 2014), 3D model reconstruction (Dong et al. 2018). Scanner’s field of vision is constrained, therefore several scans from various angles are required. The different view measured cloud data that lack georeferencing information must be aligned in order to provide a large-scale urban scene. Therefore, the registration is an indispensable operation before the scan are used further. However, several challenges exist in solving point cloud registration: (1) Large data size: millions or billions of points per scan calls for computationally efficient techniques. (2) Noise: noise will affect the reliability of geometric features extraction. (3) Occlusions and low overlapping: the search for correspondences is hampered by inadequate data and nonoverlapping region, which might be detrimental to registration. (4) Repetitive elements: homogeneous architectural structures may also cause the mismatching of corresponding feature pairs. Numerous researches (Cai et al. 2019; Dong et al. 2020; Zhou, Park, and Koltun 2016) have been conducted to increase the registration method's accuracy, effectiveness, and robustness in order to overcome these issues.

Point cloud registration involves the dual task of extracting correspondences and transformation parameters solving. The transformation parameters are derived by minimizing geometric errors on putative correspondences. As a result, outliers among these correspondences can undermine point cloud registration. The challenge of point cloud registration, therefore, is to ensure the reliability of correspondences extraction. However, approaches that extract correspondences from closest points, such as ICP (Iterative Closest Point) (Besl and McKay 1992), may converge to an incorrect local minimum if the initial orientation is not correct. Recently, feature-based registration methods (e.g. Li, Hu, and Ai 2021; Rusu, Blodow, and Beetz 2009), which provide accurate correspondences through feature descriptors, have gained more attention.

The core idea behind feature-based methods is to extract correspondences by comparing the feature representations of two scans. However, a high outlier rate is typical with these methods. To overcome this issue, researchers have focused on improving the stability of descriptions (e.g. Rusu, Blodow, and Beetz 2009; Salti, Tombari, and Stefano 2014). Robust descriptions ensure high similarity among corresponding points and discrimination against non-corresponding points. However, feature descriptors remain sensitive to noise and repetitive structures, leading to erroneous matching results when comparing the similarity between two points independently, especially for feature-based approaches (e.g. Enqvist, Josephson, and Kahl 2009; Fredriksson et al. 2016) that presume all-to-all correspondences. Note that in registration tasks, the accuracy of correspondences is more important than their number. Point cloud registration method requires only three corresponding pairs to accurately estimate the transformation, but correct correspondences can be drowned out by many mismatches. Consequently, outlier filters (e.g. Bai et al. 2021; Martin and Robert 1981; Yang, Jingnan, and Carlone 2021) advocate for identifying inliers from contaminated correspondences and building correspondences based only on these inliers. However, a high outlier rate can ultimately lead to the failure of outlier filters.

As previously discussed, one of the main challenges faced by feature-based registration methods is establishing accurate correspondences in scenarios with a high outlier rate. This paper proposes a method that aims to improve the ability to discern correct correspondences during the matching stage without the need to optimize the performance of the feature descriptor. Our approach may ultimately reduce the reliance on exact outlier filters and lead to more robust and precise registration results. Figure 1 demonstrates that this method leads to an increase in the number of inliers while also reducing the outlier rate. Notably, there was no significant difference between the proposed method and the outlier filtering method, suggesting that the removal of outliers is a contributing factor to the high inlier rate observed.

Figure 1. We address point cloud registration in an outdoor terrestrial laser scanner case where many point-to-point correspondences. (a) A classical method to align two scans by comparing feature representations of two scans. The data with 92.3% outliers (shown as red lines) and 7.7% inliers (shown as green lines). The number of inliers is 875 and the number of outliers is 10,534. (b) GGR computes the correspondence by using same feature descriptor. The data with 22.4% outliers (shown as red lines) and 77.6% inliers (shown as green lines), and our method increases the inliers.

We introduce a pairwise registration method for aligning two large-scale point clouds. Our approach utilizes a grid-graph matching technique to obtain spatially-consistent correspondences between the two point clouds. Initially, graph matching is used to obtain corresponding grids as the initial correspondences, which are then refined and updated alternately until obtaining point-to-point correspondences. The first step involves discretizing the point cloud into sparse 3D grids, where each point in a 3D grid represents its geometry information, instead of creating a global feature representation. We employ a voting strategy inspired by current Hough voting techniques (Lee et al. 2021) to determine the similarities between two grids. Next, we refine the votes hierarchically based on spatial geometry consistency and propose an improvement based on reweight random walk. Finally, we calculate the transformation parameter between the two scans by finding the largest number of consistent consensuses. Despite dividing point clouds into a series of 3D grids, our method retains the geometric information of the scans. The grid graph significantly reduces the complexity of searching for spatial consistency and is robust to unevenly distributed point densities without pre-processing. The main contributions of this work can be summarized as follows:

1. A voting mechanism that uses feature descriptors is proposed to calculate the similarity between two grids. The number of votes is counted to construct putative correspondences.

2. We propose a spatial consistency module for refine the ambiguous putative correspondences. To retrieve explicit result from superfluous putative correspondence, GGR leverages a new improved graph matching to guide the correspondences extraction. The similarity of spatial geometry is identified as a characteristic of inliers.

3. A hierarchical matching module is proposed to refine the corresponding grids. Experiment shows the GGR is robust to point clouds in lager scenes.

2. Related works

In this section, we will provide a brief overview of some techniques used in point cloud registration. A typical registration method must address two main challenges: identifying correspondences and estimating transformation parameters. Corresponding to the techniques used for identifying correspondence, point cloud registration methods can be broadly classified into two groups: point-based methods and feature-based methods.

2.1. Feature-based methods

The feature-based methods perform point cloud registration by matching 3D points between scans through comparing feature representations, and then using the resulting correspondences to estimate transformation parameters. To address the challenge of real-world datasets, Choy, Park, and Koltun (2019) and Deng, Birdal, and Ilic (2018) have emphasized the development of robust feature descriptors. These descriptors ensure discrimination against non-corresponding points, while also ensuring substantial similarity among feature descriptions of corresponding points. Prominent examples of hand-crafted methods include Spin Images (Johnson and Hebert 1999), Fast Point Feature Histogram (FPFH) (Rusu, Blodow, and Beetz 2009), and Signature of Histogram of Orientations (SHOT) (Salti, Tombari, and Stefano 2014). However, these methods are limited to local geometry and susceptible to noise. Learning-based methods, such as 3DMatch (Zeng et al. 2017), PPFNet (Deng, Birdal, and Ilic 2018), and FCGF (Choy, Park, and Koltun 2019), apply deep neural networks to encode 3D descriptors. Compared with hand-crafted methods, deep learning-based methods can automatically code more robust and distinct feature representations. Traditional matching strategies can be classified into two categories: unary-based and higher-order. Unary-based approaches, such as ratio test (Lowe 2004), similarity metric (Zeng et al. 2017), and reciprocal check (Bradski 2000), treat 3D features as independent units. However, this approach causes a much higher outlier rate, which is problematic for point cloud registration technology.

To remove outlier of correspondences, Outlier filtering methods are employed to detect mismatches. Outlier filtering algorithms eliminate incorrect correspondences and calculate rigid transformation between point clouds based on the remaining correspondences. Point cloud registration methods based on RANSAC (Martin and Robert 1981) are the most extensively used robust methods. Recently, learning-based 3D outlier rejection methods, such as PointDSC (Bai et al. 2021), 3DRegNet (Pais et al. 2020), and DGR (Choy, Dong, and Koltun 2020), have been proposed. These methods use operators such as sparse convolution and pointwise MLP to classify putative correspondences and predict the inlier probability of each correspondence. While these approaches achieve good performance at small-scale indoor point cloud registration, limitations on data amount and complexity make it difficult to apply them to large-scale outdoor point clouds (Dong et al. 2020).

In general, point-based methods are more popular for registration due to their applicability to various scenes. However, point cloud registration methods based on feature lines, plane, and surfaces have also emerged. Representative methods, such as voxel-based four-planes congruent sets (Xu et al. 2019), use planes instead of points as basic elements to form congruent sets. Geometric constraints constructed by building facades and ground surfaces were utilized by Xu et al. (2017) for the coarse registration of urban point clouds. Khoshelham et al. (2010) estimated the positions and orientations of two scans using the corresponding planes. Although line/plane-based methods (Xiao et al. 2013; Yang, Dong et al. 2016) work effectively for man-made objects, they suffer significant performance degradation in natural scenes with fewer line/plane features. Although feature-based methods can generally provide satisfactory results for point cloud registration, they still face common limitations such as low descriptiveness and weak robustness of existing 3D feature descriptors, as well as the high outlier rate of many outlier rejecting algorithms.

2.2. Points-based methods

Points-based registration uses mathematical rules instead of feature descriptor to identify corresponding pairs. There are some point-based methods in the literature which do not follow the paradigm of feature descriptors calculation and feature matching. For example, iterative closest point (ICP) (Besl and McKay 1992) is the most extensively used point cloud registration approach. ICP heuristically chooses the closest point in Euclidean space as a correspondence; then, a rigid transformation is fitted by using these correspondences. Thus, ICP searches for local optimum of initial transformation by alternating between finding the correspondences and computing the best transformation given these correspondences. Many variants, such as point-to-plane, plane-to-plane and normal, are proposed to improve one or more constraints of ICP. ICP is still sensitive to partial overlaps, and ICP will almost always fail in 3D scan sequences with partial overlaps. Many methods introduce robust transformation estimation technique to improve the robustness of ICP, such as Trimmed ICP (Chetverikov, Stepanov, and Krsek 2005), and Go-ICP (Yang, Li et al. 2016). ICP and its variant high relies on the initial transformation parameter.

The 4-points Congruent Set (4PCS) (Aiger, Mitra, and Cohen-Or 2008) is another representative work for point cloud registration. 4PCS determine the corresponding four-point base sets by exploiting the rule of intersection ratios instead of feature descriptor calculation and matching. 4PCS increases the correspondences set requirement to four points, resulting in increased robustness to noise. 4PCS’s variants have been proposed to improve performance of the algorithm. For example, Super 4PCS (Mellado, Aiger, and Mitra 2014) improved efficient of original 4PCS by applying a splitting and indexing strategy using a 3D grid. However, both the 4PCS and Super4PCS can result in wrong alignments for outdoor dataset. Keypoint 4PCS (K-4PCS) (Theiler, Wegner, and Schindler 2014) extracts keypoints as input candidates for creating and finding corresponding congruent sets. When Super4PCS is used for scenes with repeated structures or symmetrical structures such as buildings, it is easy to encounter registration misalignment, leading to low registration success rates.

3. The proposed methody

In this section, we present a registration algorithm that utilizes a successive scheme consisting of three components: correspondences generation, graph matching, and hierarchical refinement. This approach can help to improve the accuracy and robustness of the registration process, and has been shown to be effective in experiment of point cloud registration.

3.1. Registration framework

Our method aims to align two unordered point clouds in a global coordinate reference, without requiring an initial position. Figure 2 provides an overview of our registration framework. The input consists of a pair of point clouds, which are first divided into a set of 3D grids. A voting method generates putative correspondences by measuring the similarity between two 3D grids. Next, a graph matching process hierarchically refines the corresponding grids until two fragments are expressed as point-to-point correspondences. Finally, the transformation parameters is calculated using a random sample strategy for correspondence selection.

Figure 2. Workflow of the GGR.

3.2. Grid-based correspondences

To achieve robust correspondences in point clouds, we introduce a grid-based correspondence detection method that involves two primary steps: 3D grid generation and voting strategy. The aim of these methods is to establish a similarity measure capable of identifying corresponding grids when supplied with point cloud as input. By segmenting the point clouds into a series of 3D grids and utilizing a voting mechanism to create potential correspondences.

3D grid generation. In order to represent the point cloud, we generate a set of 3D grids, each containing several 3D points as illustrated in Figure 3. The point cloud serves as input for this grid generation process.

Figure 3. Point cloud voxelization. (a) Initial point cloud. (b) Point cloud voxels.

Given point clouds $\mathbf{X}=\{x_i\}\in {\mathbb{R}}^{3\times N_X}$, and $\mathbf{Y}=\{y_i\}\in {\mathbb{R}}^{3\times N_Y}$, where $x_i\in {\mathbb{R}}^3$, $y_i\in {\mathbb{R}}^3$, $N_X$ and $N_Y$ are the numbers of points in $\mathbf{X}$ and $\mathbf{Y}$ respectively. Given the voxel grid size $l_{\mathrm{int}}$, we adopt the same interval $l_{\mathrm{int}}$ to generate square 3D grids. The grids of $\mathbf{X}$ and $\mathbf{Y}$ are denoted as ${\mathbf{V}}_X=\{v_i^X{\}}_{i=1}^N$ and ${\mathbf{V}}_Y=\{v_j^Y{\}}_{J=1}^M$. Meanwhile, each point with high dimensional feature vector is assigned to a unique label. Any corresponding points in two grids can be mapped into the two grids.

It should be noted that the size of the grid, $l_{\mathrm{int}}$, has a direct impact on the number of points contained within a grid. When a grid contains only one point, it is no longer subdivided, making that point the smallest 3D grid. As such, point cloud voxelization process begins with the initial point cloud and proceeds until the number of 3D points in each grid falls below a predetermined threshold.

Voting strategy. Due to the spatial homogeneity of 3D data, corresponding points are highly likely to belong to the inliers of a grid pair. To take advantage of this fact and find the most reliable consensus between two scans, we utilize a voting method. This approach can help to identify putative correspondences that are robust to noise and other sources of error.

We propose a voting method where the votes are determined by retrieving closest points in a feature space. The grid $v_i^X\in {\mathbf{V}}_X$ is represented as a community, each point $\{x_i\}\in v_i^X$ is represented as voter, and the grid ${\mathbf{V}}_Y$ is represented as a ballot box. We use the Fast Point Feature Histogram (FPFH) algorithm to obtain the feature descriptors of the point cloud. We have chosen this feature because it can be computed in a fraction of a millisecond and provides good matching accuracy across a broad range of datasets. For example, if the FPFH features of $y_j\in v_j^Y$ and $x_i\in v_i^X$ are the nearest neighbors in feature space, then $x_i$ contributes a vote to $v_j^Y$, increasing its vote count by one, as the shown in Figure 4. $\mathrm{F}(y_j)$represents the feature descriptor of point $y_j$, $\mathrm{F}(x_i)$ represents the feature descriptor of point $x_i$. This voting strategy is better because multiple candidate correspondences can be considered. Therefore, in addition to the nearest point in the feature space, secondary neighboring points whose distance is less than the threshold are also selected for voting. The vote count is as follows: (1) $\begin{array}{c}V(v_j^Y)=\sum _{y_j\in v_j^Y}^{|v_j^Y|}\sum _{x_i\in v_i^X}^{|v_i^X|}\mathrm{F}(y_j)-\mathrm{F}(x_i)<{\tau }_1\end{array}$(1) Where, $\lfloor .\rfloor$ represents the Iverson bracket and ${\tau }_1$ denotes a distance threshold, and $V(v_j^Y)$ represents the number of votes obtained by grid $v_j^Y$. After all the votes have been cast, the maximum number of votes received, represented by $\max \{V(v_j^Y)|v_j^Y\in {\mathbf{V}}_Y\}$, corresponds to the grid $v_i^X$.

Figure 4. A diagram of matching strategy. The green point represents a 3D point within grid $v_i^X$, whereas the red point denotes a 3D point within grid $v_j^Y$.

In real-world scenarios, feature descriptions may not be robust enough, leading to the selection of promising correspondences that are actually mismatches. To address this issue, GGR focuses on selecting promising correspondences to improve the accuracy of the point cloud registration process. To ensure the correct corresponding grid is extracted, we track candidate correspondences in addition to the list of candidates. While retrieving the grid with the most similar object is a common method for correspondence extraction, we explore some potentially correct correspondences in this paper. When the number of votes exceeds the threshold, we consider correspondence of $v_i^X$ to be valid if $V(v_j^Y)<{\tau }_2$. We additionally track two candidate correspondences in this paper, resulting in one-to-many putative correspondences, as shown in Figure 5. Matching result is tackled by solving a binary matching matrix $\mathbf{C}=\{0,1{\}}^{N_X\times N_Y}$, where $c_{ij}\in \mathbf{C}$, i.e. (2) $\begin{array}{c}{c}_{ij}=\{\begin{array}{c}\begin{array}{cc}1& \mathrm{if}{v}_j^Y\mathrm{and}{v}_i^X\mathrm{are}\mathrm{matched}\end{array}\\ \begin{array}{cc}0& \mathrm{other}\end{array}\end{array}\end{array}$(2)

Figure 5. Two point cloud pairs matching process by increasing putative correspondence. (a) The grids with the maximal vote are taken to as a candidate correspondence. (b) We additionally track 2 candidate correspondences.

Although correspondence extraction is still based on 3D points, correspondences are represented as corresponding grids. By generating each point from a 3D grid and representing it as a grid in its own right, it becomes easier to combine cues from the grid during the point cloud registration process. The use of corresponding grids also helps to reduce computational complexity when searching for consistent correspondences, as the number of possible correspondences is effectively reduced.

It is worth noting that enlarging the putative correspondences can increase the indeterminacy of matching, which runs counter to the assumption that maximum similarity is the most promising correspondence. In order to reject mismatch from uncertain correspondences, we construct a graph to implicitly verify the spatial geometry between corresponding points. With the abuse of notation, we use $\mathbf{C}(v_i^{\mathbf{X}})\to v_i^{\mathbf{Y}}$ to denote the $v_i^{\mathbf{X}}$ corresponds to $v_i^{\mathbf{Y}}$ and we also use $v_i^{\mathbf{Y}}=\mathbf{C}(v_i^{\mathbf{X}})$ to denote the map. As shown in Figure 5(b), $\{v_1^{\mathbf{Y}},v_2^{\mathbf{Y}}\}=\mathbf{C}(v_1^{\mathbf{X}})$ but $v_1^{\mathbf{Y}}\ne \mathbf{C}(v_3^{\mathbf{X}})$, $v_1^{\mathbf{Y}}$, $v_2^{\mathbf{Y}}$ are the candidate of $v_1^{\mathbf{X}}$.

3.3. Spatial consistency-based grid matching

To enhance the reliability of selected grid correspondences, we have developed a graph matching method that adaptively refines voting. The aim of this approach is to refine correspondences and identify reliable corresponding grids based on input corresponding grid $\mathbf{C}$.

Problem formulation. The high-order similarity of grids is established through graph matching. The spatial structure similarity is an intuitive feature of promising correspondences. The grid generates canonical ‘meeting points’ from the center of the grids to verify the spatial consistency of corresponding grids. Two sets of centers, $\mathbf{Q}=\{q_i{\}}_{i=1}^N$, $\mathbf{P}=\{p_k{\}}_{k=1}^M$, where $q_i\in {\mathbb{R}}^3$ and $p_k\in {\mathbb{R}}^3$, are used to obtain correspondences $\mathbf{C}$ via a vote method. Correspondences with spatial consistency are returned when the Euclidean distance between $(q_i,p_i)$ equals that of $(q_j,p_j)$. In ideal circumstances, if the lengths are not equal, there must be at least one false match in $\mathbf{C}$, as shown in Figure 6.

Figure 6. An example for computing the 3D grid reliability metric. Yellow dashed lines represent correspondence. (a) Three 3D grid and their candidates. (b) When they are mismatched, the topologies around them will make a difference. (c) Spatial consistent corresponding grids. This brief explanation is an example to interpret the method can be applied to many discrete point.

$\mathbf{Q}$ and $\mathbf{P}$ can be represented as two undirected graphs, $G^1=(V^1,E^1,A^1)$ and $G^2=(V^2,E^2,A^2)$, where $V$ represents a set of discrete points, $E$ represents undirected edges, and $A$ represents attributes. Node $q_i$ is associated with an attribute $a_i^1\in A^1$, while the associated attribute of edge $a_{ij}^1\in A^1$ is the spatial distance between $q_i$ and $p_j$. Therefore, we propose an algorithm to help find correspondences with similar spatial geometry from putative correspondences. The mutual similarity of correspondences is measured by $f(\mathbf{C})$, which is defined as the mutual similarity score. In the case of grid, the mutual similarity $f(\mathbf{C})$ can be defined as follows: (3) $\begin{array}{c}f(\mathbf{C})=\sum _{\begin{array}{c}{\mathbf{C}}_{i,k}=1\\ {\mathbf{C}}_{j,l}=1\end{array}}{s}_{\mathrm{e}}(a_{i,j},a_{k,l})+\sum _{{\mathbf{C}}_{i,k}=1}{s}_{\mathrm{p}}(q_i,p_k)\end{array}$(3)

Subject to $\sum _k^M{\mathbf{C}}_{i,k}=1,\mathrm{\forall }i$, $\sum _i^N{\mathbf{C}}_{i,k}=1,\mathrm{\forall }k$, $\mathbf{C}=\{0,1{\}}^{N\times M}$. Here, $s_{\mathrm{p}}(q_i,p_k)$ represents the similarity of $(q_i,p_k)$, while $s_{\mathrm{e}}(a_{i,j},a_{k,l})$ represents the similarity of Euclidean distance $a_{i,j}$ and $a_{k,l}$. In this paper, we utilize a continuous relaxation optimization strategy to predict $\mathbf{C}$. We consider any spatially consistent grid as a promising correspondence which will be inputted into the refinement process.

Affinity graph with candidate matches. The graph matching process between $G^1$ and $G^2$ can be represented as a ranking within the association graph $G^{\mathrm{s}}=(V^{\mathrm{s}},E^{\mathrm{s}},A^{\mathrm{s}})$. The attribute $A^{\mathrm{s}}$ is encoded into the affinity matrix $\mathbf{W}$, which is utilized for calculating the graph matching. The affinity matrix element ${\mathbf{W}}_{ik:jl}$, denoting the affinity of $G^{\mathrm{s}}$, measures the mutual consistency of $\{(q_i,p_k),(q_j,p_l)\}$. ${\mathbf{W}}_{ik:jl}$ is as defined as follows: (4) $\begin{array}{c}{\mathbf{W}}_{ik:jl}=\{\begin{array}{c}{s}_p(a_i^1,a_k^2),k=l,i=j\\ s_e(a_{i,j}^1,a_{k,l}^2),else\end{array}\end{array}$(4) Where $s_e(a_{ij}^1,a_{kl}^2)=\max (D-|a_{ij}^1,a_{kl}^2|,0)$, $a_{ij}^1=\Vert x_i-x_j{\Vert }_2$, $a_{kl}^2=\Vert y_k-y_l{\Vert }_2$. Non-diagonal element $s_e(a_{ij}^1,a_{kl}^2)$ is pairwise similarity between $a_{ij}^1$ and $a_{kl}^2$. The diagonal term $s_{\mathrm{p}}(a_i^1,a_k^2)$ denotes the unary similarity of a correspondence. The column-wise vectorized replica of $\mathbf{C}$, represented as $\mathbf{c}\in \{0,1{\}}^{NM}$, is used in graph matching to seek the optimal solution ${\mathbf{c}}^{\ast }$ that maximizes the similarity function, which can be expressed as follows: (5) $\begin{array}{c}\begin{array}{c}{\mathbf{c}}^{\mathbf{\ast }}=\mathrm{argmax}({\mathbf{c}}^{\mathrm{T}}\mathbf{W}\mathbf{c})\\ s.t.\mathbf{c}\in {\{0,1\}}^{NM},\mathrm{\forall }i,\sum _{a=1}^M{\mathbf{c}}_{ia}\le 1,\mathrm{\forall }a,\sum _{I=1}^N{\mathbf{c}}_{ia}\le 1\end{array}\end{array}$(5)

Whereas the constraints pertain to the one-to-one correspondence linking $\mathbf{Q}$ and $\mathbf{P}$, the graph matching approach relaxes $\mathbf{C}$ to $[0,1]$. The score between $q_i$ and $p_k$ is represented by $c_{ik}\in \mathbf{C}$, which is known as the soft matching matrix $\mathbf{C}$.

We propose a method called additional conflicting walk prevention (ACWP) to construct the edges of the affinity graph. The aim of ACWP is to create a more concise version of $G^{\mathrm{s}}$ by retaining important connections and removing connections from incompatible nodes. This same approach is also presented in Li et al. (2020). Specifically, when a random walker is on node $v_{ik}$, it is not allowed to move to nodes $\mathrm{\forall }k\ne l,v_{il}$ and $\mathrm{\forall }j\ne i,v_{jk}$ in order to prevent conflicting walks. However, this self-loop rejection approach does not sufficiently address situations where a node is explicitly matched with candidates. For example, if $q_1$ and $q_2$ are matched with $p_a$ and $p_b$, respectively, self-loop rejection would still preserve the outgoing edges of distorted nodes like $v_{1b}$ and $v_{2a}$. In reality, the outgoing edges of $v_{1b}$ should be eliminated because $q_1$ and $p_b$ are incompatible. ACWP works by removing conflicting elements from the affinity matrix $\mathbf{W}$. If $p_k$ does not correspond to $q_i$, or if $p_l$ and $q_j$ do not represent a 3D point correspondence, then ${\mathbf{W}}_{ik:jl}$ is set to 0.

In order to select reliable nodes in $G^{\mathrm{s}}$, we use Random Walk to determine the ranking of nodes. We obtain an approximate solution through a continuous relaxation optimization strategy similar to the one used by Cho, Lee, and Lee (2010).

Random walk. A typical approach to solving Eq. (5) is through a random walk on an association graph. The process involves starting from any node and selecting one of the outgoing edges based on the translation kernel of the affinity graph. The maximum degree, denoted as $d_{\max }={\mathbf{W}}_{\mathrm{\infty }}$ where $\Vert .{\Vert }_{\mathrm{\infty }}$ represents the infinite norm of the matrix, is defined. We then formulate the transition matrix $\mathbf{P}$ as follows. (6) $\begin{array}{c}P=\left(\begin{array}{cc}\mathbf{W}/d_{\max }& 1-\mathbf{d}/d_{\max }\\ 0^{\mathrm{T}}& 1\end{array}\right)\end{array}$(6) Where $\mathbf{W}/d_{\max }$ is the $MN\times MN$ sub-stochastic matrix, $1$ is an $MN\times 1$ all-one vector. The random walk includes a set of transient nodes ${\mathrm{c}}_{\mathrm{abs}}$. For ranking on the absorbing Markov chain, define the conditional distribution $\mathbf{c}$ as: (7) $\begin{array}{c}{\overline{\mathbf{c}}}_{ia}^{(n)}={\displaystyle \frac{{\mathbf{c}}_{ia}^{(n)}}{1-{\mathrm{c}}_{\mathrm{abs}}^{(n)}}}\end{array}$(7)

If ${\mathbf{c}}^{(n+1)}={\mathbf{c}}^{(n)}=\mathbf{c}$, $\mathbf{c}$ is a quasi-stationary distribution of the Markov chain. Random walker traverses an edge with probability $\alpha$ or jumps to some constrained nodes with probability $1-\alpha$. (8) $\begin{array}{c}\left(\begin{array}{cc}{\mathbf{c}}^{(n+1)\mathrm{T}}& {\mathrm{c}}_{\mathrm{abs}}^{(n+1)}\end{array}\right)=\alpha \left(\begin{array}{cc}{\mathbf{c}}^{(n)\mathrm{T}}& {\mathrm{c}}_{\mathrm{abs}}^{(n)}\end{array}\right)P+\\ (1-\alpha )\left(\begin{array}{cc}{f}_c{({\mathbf{c}}^{(n)\mathrm{T}}\mathbf{W})}^{\mathrm{T}}& 0\end{array}\right)\end{array}$(8)

Eq. (8) represents a dynamic Markov chain with a jump distribution that varies dynamically. The reweighting function, denoted by $f_c(.)$, incorporates inflation and bistochastic normalization techniques (Cho, Lee, and Lee 2010). The quasi-stationary distribution of Eq. (5) is computed using the power iteration method. The discretization algorithm (Munkres 1957) is then employed to obtain one-to-one correspondences. The experiments demonstrate that graph matching is a stable and effective approach for selecting reliable correspondences.

Table

Algorithm 1: Spatial Consistency-based Grid Matching

Input: Point clouds $(\mathbf{X},\mathbf{Y})$ and descriptor $\mathbf{F}(\mathbf{X})$ and $\mathbf{F}(\mathbf{Y})$; voxel grid size $l_{\mathrm{int}}$ Output: Correspondences $\mathbf{C}$; Generate 3D grids ${\mathbf{V}}_{\mathrm{X}}$ and ${\mathbf{V}}_{\mathrm{Y}}$ by grid interval $l_{\mathrm{int}}$ build $\mathbf{C}$ by voting method between ${\mathbf{V}}_{\mathrm{X}}$ and ${\mathbf{V}}_{\mathrm{Y}}$ given the weight matrix $\mathbf{W}$ follow Eq. 3. setting ${\mathbf{W}}_{ik:jl}\to 0$ for all conflicting match pairs initialize the transition matrix $\mathbf{P}=\mathbf{W}/d_{\max }$ repeat ${\overline{\mathbf{c}}}^{\mathrm{T}}={\mathbf{c}}^{\mathrm{T}}\mathbf{P}$ ${\mathbf{c}}_{\mathrm{cons}}\leftarrow$reweighting with two-way constraints ${\mathbf{c}}^{\mathrm{T}}=\alpha {\overline{\mathbf{c}}}^{\mathrm{T}}+(1-\alpha ){\mathbf{c}}_{\mathrm{cons}}$ $\mathbf{c}=\mathbf{c}/\sum {\mathit{c}}_{\mathit{i}a}$ until $\mathbf{c}$ converges Discretize $\mathbf{c}$ by Hungarian algorithm

3.4. Hierarchical matching

Any spatially consistent grid is considered a promising correspondence, but the corresponding grids may be too coarse to estimate precise transformation parameters. Therefore, we propose a hierarchical matching module to refine the rough correspondences. We input the grid graph matching result into the hierarchical matching module to generate corresponding points, as shown in Figure 7. A simple way to alleviate the coarseness of the consensus is to aggregate nearby grids and refine them hierarchically, as shown in Figure 8. The initial grid is subdivided into sub-grids, and these sub-grids will undergo an alternating process of corresponding grid extraction and subdivision until the number of points in the grid is below a certain threshold.

Figure 7. An example to show that the matching result of GGR. Green lines represent correct correspondence and red lines represent mismatches. (a) Grid correspondence. (b) Refinement result.

Figure 8. Nearby grids aggregation and sub-grid generation. (a) Red grid represents $v_i^{\mathrm{Y}}$, green grids represent neighborhoods of $v_i^{\mathrm{Y}}$. (b) Red grid represents point cloud${\tilde{v}}_i^{\mathrm{Y}}$, green grids represent sub-grids.

The corresponding grids may not completely overlap. To eliminate outliers caused by low overlap, the input $v_i^{\mathrm{Y}}$ of refinement aggregates nearby grids. The neighborhoods of $v_i^{\mathrm{Y}}$ and $v_i^{\mathrm{Y}}$ are grouped to form ${\tilde{v}}_i^{\mathrm{Y}}$. The points in ${\tilde{v}}_i^{\mathrm{Y}}$ and $\mathbf{C}(v_i^{\mathrm{Y}})$ follow the process outlined in Algorithm 1. This approach produces point-to-point correspondences if the voxel has fewer points than the threshold, as the corresponding points are generated using each point as a grid in the final step. The hierarchical matching process is illustrated in Algorithm 2.

Table

Algorithm 2: Hierarchical matching

Input: Two point clouds $(\mathbf{X},\mathbf{Y})$ and descriptor $\mathbf{F}(\mathbf{X})$ and $\mathbf{F}(\mathbf{Y})$; Output: Point-to-point correspondences $\mathbf{C}$; Set grid interval ${\tilde{l}}^{(n)}={\tilde{l}}^{(n)}\times 0.5$ If $N(\mathbf{X})$ > threshold Generate ${\tilde{v}}_i^{\mathrm{Y}}$ by combining neighborhoods of $v_i^{\mathrm{Y}}$ Refine $(v_i^{\mathrm{X}},{\tilde{v}}_i^{\mathrm{Y}})$ recursively by Algorithm 1 Else Each point of $(v_i^{\mathrm{X}},{\tilde{v}}_i^{\mathrm{Y}})$ act as a grid and matched by Algorithm 1

3.5. Registration module

The extraction of correspondences has been constrained by geometric structure. To do so, a 3-point sample is generated through random sampling, and we retrieve the optimal rotation and translation parameters that minimize the 3-point geometric error outlined in Eq. (9(9) $\begin{array}{c}\tilde{\mathbf{R}},\tilde{\mathbf{t}}=\underset{\mathbf{R},\mathbf{t}}{\mathrm{argmin}}\sum _i^{\mathbf{C}}\mathbf{R}{x}_i+\mathbf{t}-y_i^2\end{array}$(9) ). (9) $\begin{array}{c}\tilde{\mathbf{R}},\tilde{\mathbf{t}}=\underset{\mathbf{R},\mathbf{t}}{\mathrm{argmin}}\sum _i^{\mathbf{C}}\mathbf{R}{x}_i+\mathbf{t}-y_i^2\end{array}$(9) Where, $x_i$ and $y_i$ represent the coordinates of the 3-point sample. We calculate $\tilde{\mathbf{R}}$ and $\tilde{\mathbf{t}}$ using the Procrustes method (Gower 1975), a closed-form solution for rigid transformation in SE(3). The method processes all samples and clusters those correspondences that satisfy Eq. (3). (10) $\begin{array}{c}\hat{\mathbf{R}},\hat{\mathbf{t}}=\underset{\mathbf{R},\mathbf{t}}{\mathrm{argmax}}\sum _i^{\mathbf{C}}\mathbf{R}{x}_i+\mathbf{t}-y_i<\tau \end{array}$(10)

Where, $\lfloor .\rfloor$ represents the Iverson bracket and $\tau$ denotes an inlier threshold. The group with a greater number of inliers is assumed to be the correct correspondences. Therefore, correspondences with a higher number of inliers are chosen for the final correspondences $\tilde{\mathbf{C}}$.

We recompute the transformation matrix using all the surviving inliers $\tilde{\mathbf{C}}$. The correspondences are used to calculate the transformation $\hat{\mathbf{R}}$, $\hat{\mathbf{t}}$ between by minimizing. (11) $\begin{array}{c}\hat{\mathbf{R}},\hat{\mathbf{t}}=\underset{\mathbf{R},\mathbf{t}}{\mathrm{argmin}}\sum _i^{\tilde{\mathbf{C}}}\mathbf{R}{x}_i+\mathbf{t}-y_i^2\end{array}$(11)

4. Experiments

The goal of this section is to: (1) define the evaluation metrics used in all experiments; (2) quantitatively evaluate the robustness of our method; and (3) analyze GGR in pairwise registration tasks on the WHU-TLS dataset, ETH dataset (Pomerleau et al. 2012) and iQmulus dataset (Vallet et al. 2015). In pairwise registration, we adhere to the same evaluation protocols as outlined in (Choy, Park, and Koltun 2019).

4.1. Evaluation metrics

To ensure a fair comparison, we adhere to the evaluation metrics of FCGF and report the following: (1) Feature Matching Recall (FMR), (2) Rotation Error (RE) and Translate Error (TE), and (3) Registration Recall (RR). Mathematically, FMR is defined as: (12) $\begin{array}{c}R={\displaystyle \frac{1}{|{\mathrm{\Omega }}_s|}\sum _{(i,j)\in {\mathrm{\Omega }}_s}{\mathbf{T}}^{\mathbf{\ast }}{x}_i-y_i<\tau }\end{array}$(12) ${\mathrm{\Omega }}_s$ represents a set of correspondences between a pair of point clouds, $x$ and $y$ are 3D coordinates from the fragments, and ${\mathbf{T}}^{\ast }$ is the ground-truth pose. ${\tau }_1$ and ${\tau }_2$ are the inlier distance thresholds; and $\lfloor .\rfloor$ is an operator that returns 1 if the input predicate is satisfied and 0 otherwise. The Rotation Error (RE) and Translation Error (TE) are used: (13) $\begin{array}{c}RE(\hat{\mathbf{R}})=arccos{\displaystyle \frac{\mathrm{Tr}({\hat{\mathbf{R}}}^{\mathrm{T}}{\mathbf{R}}^{\mathbf{\ast }})-1}{2},TE(\hat{\mathbf{t}})=\hat{\mathbf{t}}-{\mathbf{t}}_2^{\mathbf{\ast }}}\end{array}$(13) Where ${\mathbf{R}}^{\ast }$ and ${\mathbf{t}}^{\ast }$ represent the true rotation and translation values, respectively. Additionally, we report the intermediate registration recall obtained with the pose estimation $\hat{\mathbf{T}}$. For fragment pairs $\{i,j\}$ with at least a 30% overlap, registration is deemed correct if $\mathrm{TE}<{\mu }_{\mathrm{t}}$ and $\mathrm{RE}<{\mu }_{\mathrm{r}}$. RR is a metric that assesses the percentage of pairs that correctly match the pose. As several studies have indicated, RR holds greater significance than precision because enhanced pruning can enhance precision.

4.2. Sensitivity of grid configuration

The 3D grid takes two parameters: grid size and orientation. We quantitatively evaluate the robustness of our method by testing it with different sizes and orientations. For accuracy consideration, we utilized varying voxel grid sizes for WUH-TLS dataset in subsequent calculation and analysis. In this experiment, all settings remained consistent except for the voxel size, which varied from 15 to 30 in intervals of 5. We set ${\mu }_{\mathrm{t}}=5$, ${\mu }_{\mathrm{r}}=0.01$, and $\tau =10$. The experimental results are illustrated in Figure 9.

Figure 9. Rotation error and translation error of different grid size.

Figure 9 displays the evaluation of GGR's rotation error, translation error, and registration recall at each $l_{\mathrm{int}}$. All rotation and translation errors fall below 0.06 rad and 5 m, respectively. The lowest rotation and translation errors occur at $l_{\mathrm{int}}=15$, while the registration recall is the highest. This effect is more pronounced when more correspondences require verification. In other words, building a graph model with a smaller grid yields better results. However, smaller $l_{\mathrm{int}}$ values may cause memory usage to exceed area limits. Accordingly, in the subsequent experiments, we set the value of $l_{\mathrm{int}}$ to 15. This value is approximately equal to 1/30th of the length of the longer side of the bounding box of the point cloud.

In practice, GGR does not require any assumptions about the initial position of the point cloud. Therefore, we analyze GGR's sensitivity to grid orientation. We adjust the grid's orientation by transforming the raw point cloud using various transformations that consider the characteristics of the TLS point cloud (following Cai et al. 2019). The second point cloud is displaced relative to the first one by a 4DOF transformation (3D translation and rotation around the vertical axis). Three types of transformation noise are generated, and we compare GGR's performance with RANSAC, RANSACo (a variant of RANSAC provided by the Open3D library), and TEASER. The results are illustrated in Figure 10.

M1: The second point cloud is displaced relative to the first one by randomly generating a 4DOF transformation.

M2: The second point cloud is translated by adding random small constants to the x and y axes, respectively, and a random small constant rotation around the vertical axis.

M3: The second point cloud is transformed according to a ground-truth transformation.

Figure 10. Performance of orientation experiment of algorithms. (a) Rotation performance; (b) Translation performance.

As shown in Figure 10, the performance of RANSAC and RANSACo was erratic compared to that of TEASER and GGR at all three noise levels. In contrast, the performance of TEASER and GGR was more stable. Our method achieved greater accuracy, with a rotation error of about 0.01 rad under all three types of noise, and a translation error of less than 3 m.

Figure 10 shows the registration recall of the different methods. RANSACo, RANSAC, and TEASER showed slight fluctuations in performance at the three noise levels due to the invariance of their descriptors, which makes them insensitive to the orientation of the point cloud. However, in M1, the registration recall in RANSACo, RANSAC, and TEASER was lower (at 19%, 6%, and 44%, respectively) than in GGR, which achieved a recall of 60%. As shown in Figure 11, there is an increasing trend in GGR's recall, with higher recall in M2 and M3. A better initial location makes the corresponding grids more comparable, improving GGR's registration recall. However, despite being sensitive to grid orientation, GGR does not require an accurate initial location estimation to operate effectively. Overall, GGR outperforms other techniques in terms of registration recall, while our technique performs well in both registration recall and registration accuracy on a real-world dataset.

Figure 11. Registration recall comparison.

4.3. Evaluation on real outdoor data: WHU-TLS

The WHU-TLS dataset, which comprises LIDAR scans, is utilized to assess the effectiveness of our GGR in typical outdoor scenes. The obtained results from registering the WHU-TLS dataset are presented in this section. Real-world scenarios are used to showcase the benefits of GGR, with registration accuracy being measured by the deviation between estimated and ground-truth values. To demonstrate the superiority of our approach, we compared GGR against various state-of-the-art methods. We employed a voxel-based subsampling operation with a voxel size of 0.8 for the dataset. In order to ensure fairness in comparison, all methods used the same FPFH descriptor provided by MATLAB to extract correspondences. Table 1 shows the registration outcomes for all analyzed methods.

Table 1. Against the state-of-the-art registration methods on WUH-TLS.

Method	Recall	ER(rad)	TR(m)
RANSAC	6.4%	0.034	4.488
RANSAC o/w	12.8%	0.040	2.090
ANN	21.3%	0.029	2.752
FGR	27.7%	0.032	3.382
TEASER	46.8%	0.010	1.168
GGR	59.6%	0.009	1.144

Pairwise registration: we selected feature-based registration methods such as RANSAC (Martin and Robert 1981), RANSACo (Zhou, Park, and Koltun 2018), FGR (Zhou, Park, and Koltun 2016), TEASER (Yang, Jingnan, and Carlone 2021), and ANN (Marius and Lowe 2009) for comparison. RANSAC was used to estimate 6DOF pose by employing 3-point samples, with a probability of finding a valid sample set set to 0.99. Table 1 presents the registration evaluation metrics of all six algorithms.

Based on the quantitative evaluation results, RANSAC exhibited poorer registration performance with a registration recall of only 6.4%, rotation error exceeding 0.03 rad, and translation error surpassing 4 m. However, the variant provided by the OPNE3D Library (Zhou, Park, and Koltun 2018) achieved better results compared to the original RANSAC method. FGR also displayed a tendency to fail in the dataset, especially with data having rotation errors greater than 0.03 rad and translations errors over 3 m. Among the evaluated methods, TEASER demonstrated overall higher alignment accuracy than RANSAC, FGR, and ANN. Nevertheless, through experimentation, we discovered that TEASER collapses when handling high correspondence numbers, resulting in a success rate up to 19.2% worse than GGR. Other methods performed poorly due to the absence of optimality guarantees. GGR achieved the highest recall rate and possessed remarkable translation and rotation registration accuracy. It is worth noting that ICP and 4PCS were unable to align the WHU-TLS dataset; hence they were omitted from the experiments. The result of GGR as shown in Figure 12.

Figure 12. Example visualization of our registration result. (a), (b) and (c) are original datas; (d), (e) and (f) are the registration results.

Correspondence extraction: As mentioned previously, a high outlier rate can cause feature-based methods to fail. We evaluated the performance of our method and other methods using the WHU-TLS dataset. RANSAC, FGR, and TEASER generate initial correspondences by retrieving the closest point in feature space, with an inlier threshold set to 10 m based on experimental results. Table 2 presents the feature matching outcomes.

Table 2. Comparisons of the FMR (%) of our method against the state-of-the-art methods.

Method	Recall	FMR
		Mean	Max	Min
RANSAC	6.4%	2.0%	6.5%	0.2%
ANN	21.3%	7.2%	6.6%	0.2%
FGR	27.7%	2.0%	6.6%	0.2%
TEASER	46.8%	2.5%	10.7%	0.0%
GGR	59.6%	12.6%	68.8%	0.0%

We numerically demonstrated the registration versus high outlier dilemma in prior works. Our grid-graph matching strategy achieved the highest FMR. When the outlier rate exceeded 98%, RANSAC struggled to complete the registration task within the allotted iterations. Despite having a greater FMR than TEASER, ANN's registration accuracy is still inferior to that of TEASER. As shown in Table 2, the mean FMR of our method reached 12.6%, while that of TEASER was only 2.5%. RANSAC and FGR performed poorly under extreme outlier rates. Our grid-graph matching strategy achieved high registration recall by increasing the FMR.

As demonstrated in Table 2, registration methods that rely on outlier rejection can fail under high outlier rates. In contrast, the grid-graph matching technique can reliably extract corresponding points to achieve accurate registration. As mentioned before, there is no clear difference between the matching method and the outlier filter. The removal of outliers is a factor in the robustness of the matching method.

Performance on ETH dataset and iQmulus dataset: To evaluate the generalizability of GGR to datasets with varying scales, we conducted evaluations on both the ETH dataset and iQmulus dataset. The ETH dataset was captured using a ground-based LiDAR scanner, while the iQmulus dataset was obtained from the IQmulus & TerraMobilita Contest using a monofiber Riegl LMS-Q120i LiDAR. The pairwise point cloud for the iQmulus dataset was obtained through simulation. For the ETH dataset, we used a voxel grid size of 3.5 m, whereas for the iQmulus dataset, the voxel grid size was set to 10 m. The translation and rotation errors are presented in Table 3.

Table 3. Against the state-of-the-art registration methods on WUH-TLS.

Dataset	Method	ER(rad)	TR(m)
ETH dataset	FGR	0.050	0.848
	TEASER	0.065	0.326
	GGR	0.025	0.255
iQmulus dataset	FGR	0.115	19.252
	TEASER	0.001	0.340
	GGR	0.001	0.341

Table 3 presents the performance comparison of GGR, FGR, and TEASER on both the ETH dataset and iQmulus dataset. Experiments indicate that GGR outperforms FGR and TEASER on the ETH dataset, with significant improvements in both rotation and translation errors. On the other hand, TEASER slightly outperforms GGR on the iQmulus dataset, demonstrating better registration performance with a modest increase of 0.001 m in translation error, while rotations errors are equally matched between the two methods. Nevertheless, despite the slight advantage of TEASER over GGR on the iQmulus dataset, the latter method's effectiveness is still demonstrated by its exceptional performance on the ETH dataset.

5. Conclusion

In this article, we present a certifiable feature-based point cloud registration algorithm that can handle extreme outlier rates. Our experiments demonstrate that the grid-graph matching technique reliably extracts corresponding points, achieving accurate registration. Additionally, we propose a more adaptable method that directly enhances matching to increase the number of inliers and reduce failures caused by high outlier rates. We also evaluate GGR's performance on benchmarks and show that it outperforms state-of-the-art methods, such as RANSAC and TEASER, while remaining robust against underperforming descriptors. Our experiments suggest that optimizing the matching strategy can improve registration results when dealing with outdoor TLS point clouds with outlier rates below 2.0%. However, since GGR's voting strategy module is sensitive to the spatial transformation of the point cloud, future work should focus on exploring grid similarity calculation methods that are insensitive to spatial transformations. This will further enhance the method's practicality.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are openly available at http://doi.org/10.1016/j.isprsjprs.2020.03.013.