Robust Point Cloud Registration Framework Based on Deep Graph Matching

A large proportion of traditional methods need an initial transformation and find a locally optimal solution near the initialization, in which ICP [8, 9] is an early and representative method. ICP starts with an initial transformation and iteratively alternates between solving two trivial subproblems: finding the closest points as correspondences under current transformation and computing optimal transformation by SVD from found correspondences. Many variants have been proposed to improve ICP [32, 33, 34]. Nevertheless, ICP and its variants can only converge to a local optimum, and their success heavily relies on a good initialization. To improve the robustness to noise and outliers and enlarge the convergence basin, some methods transform point clouds into probability distributions and reformulate point cloud registration as matching two probability distributions, such as GMM [35] and HGMR [36]. These methods do not need to alternately solve correspondences and transformation, but their objective functions are nonconvex, so they still need a good initialization to avoid converging to a bad local optimum. Recently, a series of globally optimal methods based on BnB have been proposed, such as Go-ICP [10], GOGMA [11], GOSMA [12], and GoTS [37], but they are very slow and only practical in some limited scenarios. Another line of work avoids transformation initialization by establishing correspondences. They usually first extract keypoints from the original point clouds and construct feature descriptors for them and then establish potential correspondences through feature matching [13, 14]. After that, RANSAC-like algorithms can be used to find the correct correspondences for registration. Different from RANSAC-like methods, FGR [38] optimizes a correspondence-based objective function by a graduated nonconvex strategy and achieves state-of-the-art performance in correspondence-based point cloud registration. However, correspondence-based methods are sensitive to duplicate structures and partial-to-partial point clouds because a large proportion of the potential correspondences will be incorrect in these scenarios. Specifically, the lack of good initialization, a large proportion of outliers and time constraints are still big challenges for traditional point cloud registration methods.

The developments of deep learning on point clouds processing allow researchers to make good use of existing techniques, such as PointNet [39], and DGCNN [40], to extract point cloud features for downstream tasks. These studies have stimulated the interest of using deep learning in point cloud registration. One of the earliest works is PointNetLK [41], which calculates global feature descriptors of the two point clouds through PointNet and iteratively uses the IC-LK algorithm [42, 43] to minimize the distance between the two global feature descriptors to achieve registration. PCRNet [15] replaces the IC-LK algorithm in PointNetLK with a deep neural network. DCP [18] utilizes transformer [44, 45] to compute soft correspondences between two point clouds and utilizes a differentiable SVD algorithm to calculate the transformation. Although these methods have the advantages of being fast and some of them do not need transformation initialization, they cannot effectively handle partial-to-partial point cloud registration. PRNet [46] proposes a keypoint detector and uses the keypoint-to-keypoint correspondences in a self-supervised way to solve the partial-to-partial point cloud registration. DeepGMR [47] extracts pose-invariant correspondences between raw point clouds and Gaussian mixture model (GMM) parameters, and then recovers the transformation from the matched Gaussian mixture models. IDAM [20] integrates the iterative distance-aware similarity convolution module into the matching process, which can overcome the shortcomings of using inner products to obtain pointwise similarity. RPM-Net [19] proposes a network to predict optimal annealing parameters and uses annealing and Sinkhorn [48] to obtain soft correspondences from local features. Soft correspondences can increase robustness, but they lead to the decrease of registration accuracy, which is shown in our experiments on clean point clouds. Although these methods can handle partial-to-partial point cloud registration to some extent, there is still room for improvement in their accuracy and robustness. The difference between our method and the existing learning-based methods is that we construct graphs from the original point clouds and merge structural information of the graphs into node features so that the nodes can be better matched.

Most of the direct point cloud registration methods used in object-level registration do not work well in scene-level registration. For scene-level registration, it has become popular to build correspondences based on the learned local feature descriptors of point clouds first, and then compute the transformation using the robust estimator RANSAC [26]. These methods focus on how to obtain more efficient and robust local features. For example, 3DMatch [24] converts point cloud patches into volumetric voxel grids and uses a 3D convolution network to extract local features. The benchmark dataset presented in 3DMatch [24] is popular in evaluating scene-level registration algorithms. PPFNet [49] presented a 3D local patch descriptor with an augmented set of simple geometric relationships: points, normals and point pair features (PPF). These two methods [24, 49] rely on the supervision of correspondences between patches. Later methods utilize self-supervised or unsupervised learning for feature extraction. For example, PPF-FoldNet [50] and CapsuleNet [51] train an autoencoder to reconstruct the original input point clouds without supervision and use the trained encoder for feature extraction. However, features are extracted only for predefined patches, so the perception field of these methods [24, 49, 50, 51] is greatly limited. Therefore, computing the feature descriptors for each point is a better option. The key issue is how to efficiently extract point features for large scene-level point clouds. FCGF [22] uses 3D sparse convolution to process the complete point cloud to generate dense feature predictions, which are more efficient than patch-based methods. Similar to FCGF, D3Feat [23] uses a fully convolution neural network KPConv [52] to compute dense features, and it jointly predicts dense features and point saliency score. Predator [21] utilizes cross attention mechanism to obtain more robust feature descriptors. StickyPillars [53] use a graph neural network and the Sinkhorn algorithm to solve outdoor scene registration. Different from PREDATOR and StickyPillars, we designed an edge generator to update the features of points in overlapping areas using the features of overlapping areas, while features of points in non-overlapping areas are updated only by themselves. This prevents the features of overlapping areas from being disturbed by features of non-overlapping areas.

Graph matching has been widely studied in computer vision and pattern recognition [54, 55, 56, 57, 58]. Recently, learning-based graph matching has attracted considerable research interest [59, 60, 27], but, to the best of our knowledge, there is no research on using learning-based graph matching to solve the point cloud registration problem.

To establish the correspondence matrix between two point clouds, it is necessary to embed the source point cloud $\mathbf{X}$ and the target point cloud $\mathbf{Y}$ into a common feature space. We choose different backbones to extract high-dimensional features to better fit different kinds of datasets. For object-level datasets, we first define the local feature descriptor $\mathcal{P}_{x_{i}}$ of $x_{i}$ as: $\mathcal{P}_{x_{i}}=\left\{\left(x_{i},x_{n}\right)\mid\forall x_{n}\in\mathcal{K}_{i}\right\},$where $\mathcal{K}_{i}$ represents the $K$-nearest neighboring points of $x_{i}$. Then low-dimensional local feature descriptors are mapped to high-dimensional local feature spaces through nonlinear functions $f_{\theta}$: $\mathbb{R}^{K\times 6}\rightarrow\mathbb{R}^{V}$, where $V$ is the dimensionality of the final high-dimensional local feature. The implementation of $f_{\theta}$ can be found in Section 1 of the supplementary materials, where $\theta$ represents the parameter of the nonlinear function, which consists of shared multilayer perceptron (MLP), maxpooling and concatenation. We use the high-dimensional local features as the node features $\mathcal{F}$ of the initial graph. The node feature $\mathcal{F}_{x_{i}}$ of $x_{i}$ can be expressed as follows: $\mathcal{F}_{x_{i}}=f_{\theta}\left(\mathcal{P}_{x_{i}}\right),\mathcal{F}_{x_{i}}\in\mathbb{R}^{V}.$

Unlike object-level point clouds, scene-level point clouds contain a great number of points and have more complex geometric structure. To improve computational efficiency and feature representation capabilities on scene-level point clouds, we build the local feature extractor $f_{\theta}$ based on KPFCN [52] to extract high-dimensional local features. The local feature extractor takes the source point cloud $\mathbf{X}$ and the target point cloud $\mathbf{Y}$ as inputs, and outputs the coordinates and local features of the new source $\mathbf{X}$ and the new target point cloud $\mathbf{Y}$, which are obtained by layer-by-layer grid-based subsampling. KPFCN uses kernel point convolution to extract the local features of each points, which can better learn the geometric information of neighbor points. In addition, it uses multi-layer grid-based subsampling to reduce the number of points and expand the feature receptive field. For more details about the implementation of KPFCN, we recommend reading the original paper [52]. The above process can be formulated as $(\mathbf{X},\mathcal{F}_{x_{i}})=f_{\theta}(\mathbf{X})$. In order to balance computation cost and registration accuracy, we constructed the local feature extractor by removing the decoder units from the 2nd to the last un-pooling layer from the default UNet-like KPFCN structure.

Inspired by the idea of the Siamese network [61], the two point clouds share the same local feature extractor. When the two point clouds become closer, the local features also become similar, so this structure is suitable for iterative registration.

If only the local features are used to predict the correspondences between point clouds, it is easy to obtain incorrect correspondences, especially when there are outliers. The reason is that the local features do not contain the structural information of the point cloud on a larger scale (self-correlation) and the association between the two point clouds (cross-correlation). Inspired by Wang’s research on deep graph matching [27], we construct graphs from point clouds and use deep graph matching to establish better correspondences. Section 4.2 describes how to build graphs from point clouds, and Section 4.3 introduces how to predict the correspondences by using deep graph matching and the AIS module.

The graphs built from $\mathbf{X}$ and $\mathbf{Y}$ are denoted as source graph $\mathcal{G}_{s}=\left\{\mathbf{X},\mathbf{E}_{\mathbf{X}}\right\}$ and target graph $\mathcal{G}_{t}=\left\{\mathbf{Y},\mathbf{E}_{\mathbf{Y}}\right\}$, respectively. The graph nodes are the original points, and the graph edges are represented by the adjacency matrix $\mathbf{E}$. The node features of $\mathcal{G}_{s}$ and $\mathcal{G}_{t}$ are denoted by $\mathcal{F}_{x_{i}}$ and $\mathcal{F}_{y_{j}}$, respectively. There are trivial methods to generate the edges, such as full connection, nearest neighbor connection and Delaunay triangulation, but the features of graphs cannot be effectively aggregated, resulting in poor correspondences, as shown in Figure 6 (d). Inspired by the success of BERT [44] in NLP, we introduce a transformer [45] module to dynamically learn the soft edges of any two nodes within a point cloud. The transformer-based edge generator is illustrated in Figure 2 (b). Detail structure of the edge generator can be found in Section 1.3 of the supplementary materials. The transformer consists of several stacked encoder-decoder layers. The encoder uses a self-attention layer and shared MLP to encode node features, and the decoder associates and encodes features based on the co-attention mechanism. The transformer takes node features $\mathcal{F}_{\mathbf{X}},\mathcal{F}_{\mathbf{Y}}$ as input and encodes them into embedding features $\mathcal{T}_{\mathbf{X}},\mathcal{T}_{\mathbf{Y}}$. Soft edge adjacency matrices are obtained by applying a softmax function on the inner product of the embedding features as follows:

This part is shown in Figure 2 (c), which consists of three consecutive steps as follows: First, we use intra-graph conv to explore the self-correlation of node features, where features are aggregated from nodes along edges within each graph. The message passing scheme between nodes is the same as PCA-GM [27]. A node self-correlation feature $\mathcal{F}_{x_{i}}^{corr}$ of $\mathcal{G}_{s}$ is computed by intra-graph convolution as follows:

and likewise for $\mathcal{G}_{t}$. Here, $\breve{\mathbf{E}}$ is the L1 column-normalized adjacency matrix calculated from $\mathbf{E}$, and $f_{adj}$ and $f_{self}$ are message passing functions, which are implemented by fully connected layers and ReLU.

Second, the AIS module is used to calculate a soft correspondence matrix. The AIS module consists of an affinity layer, instance normalization and Sinkhorn. An affinity matrix $\mathbf{A}$ between the two graphs is computed as follows:

where $\mathbf{W}$ is the learnable parameter in the affinity layer. If $\mathcal{F}_{x_{i}}^{corr}$,$\mathcal{F}_{y_{j}}^{corr}\in\mathbb{R}^{Q}$, then $\mathbf{W}\in\mathbb{R}^{Q\times Q}$.

Before using Sinkhorn to compute the soft correspondence matrix $\widetilde{\mathbf{C}}$, we need to transform $\mathbf{A}$ into a normalized matrix while keeping the same distribution. There are two approaches to do so, and the naïve approach is to use softmax for rows or columns. The problem with this approach is that it processes each row or column and does not consider the matrix as a whole, which may result in the problem that a smaller value in $\mathbf{A}$ is transformed into a larger value in the transformed matrix [30]. To avoid this situation, we do not use softmax but use instance normalization [62] to transform $\mathbf{A}$. Instance normalization not only considers all the elements globally, but also avoids the above problem caused by softmax. For handling outliers, we add an additional row and an additional column of ones to the transformed matrix and then input it into Sinkhorn [48] to calculate the soft correspondence matrix $\widetilde{\mathbf{C}}$ by the iterative process of alternating row and column normalization.

Finally, we enhance the node features by exploring cross-correlation through cross-graph conv. Cross-graph conv is similar to intra-graph conv, except that features are aggregated from the node features of the other graph with edges replaced by $\widetilde{\mathbf{C}}$. The more similar the node pairs between the two graphs are, the higher the corresponding weight of $\widetilde{\mathbf{C}}$ will be. We obtain a new node feature $\mathcal{F}_{x_{i}}^{\prime}$ of node $x_{i}$ with a self-correlation feature and cross-correlation feature as follows:

and likewise for $\mathcal{G}_{t}$. Here, $f_{cross}$ consists of a feature concatenate and a fully connected layer, and it is shared for $\mathcal{G}_{s}$ and $\mathcal{G}_{t}$.

To compute the hard correspondence matrix ${\overline{\mathbf{C}}}^{pre}$, which is binary, we sum the elements of each row and each column of $\widetilde{\mathbf{C}}$ and take out the rows and columns with a sum greater than confidence threshold $\tau$, and apply a LAP solver based on Hungarian algorithm[29] on the resulting matrix to obtain a binary matrix. Then, the elements of the binary matrix are assigned to a zero matrix with the shape of $\widetilde{\mathbf{C}}$ according to their position in $\widetilde{\mathbf{C}}$, and the result is the hard correspondence matrix ${\overline{\mathbf{C}}}^{pre}$ we need. Finally, for object-level registration, we take ${\overline{\mathbf{C}}}^{pre}$ as input to predict the transformation $\{\hat{\mathbf{R}},\hat{\mathbf{t}}\}$ by weighted SVD or RANSAC, and set $\tau=0.5$. Since scene-level registration is more difficult, we only use RANSAC as correspondence-based estimator to estimate the transformation parameters and set $\tau=0.7$. In addition, we also provided the influence of $\tau$ on scene-level registration in Section 6.3 of the supplementary materials.

Our loss function takes the ground truth correspondences directly as supervision, which is different from previous studies [18, 19, 47] that define loss on transformation parameters. Focal loss [31] between soft correspondence matrix $\widetilde{\mathbf{C}}$ and ground-truth correspondence matrix $\overline{\mathbf{C}}^{gt}$ is adopted to train our model. The formula is as follows:

where $\alpha$ is a balance factor to address class imbalance, $\alpha\in[0,1]$ for correct correspondences and $1-\alpha$ for incorrect correspondences. $\gamma$ is a modulating factor to down-weight easy correspondences and thus focus training on hard ones to distinguish correspondences [31]. We empirically set $\alpha=0.5$ and $\gamma=0$ in object-level registration, which is equivalent to CE loss used in the conference paper [30]. Finding enough good correspondences for scene-level registration is more difficult, so we focus more on those hard correspondences and empirically set $\alpha=0.25$ and $\gamma=2$ as in [31]. Since our loss function is only related to the soft correspondence matrix $\widetilde{\mathbf{C}}$, the calculations in Section 4.4 do not need to be differentiable.

This network is implemented using PyTorch and trained on a single Nvidia Tesla V100. We train the network using the SGD optimizer and set $L=2$ in this study. For object-level datasets, we consider a neighborhood of $K$ = 20 for local feature extractor and set $V=1024$ for high-dimensional local features. For scene-level datasets, we set $V=528$ for high-dimensional local features. The number of heads in multi-head attention for the Transformer in Edge Generator is 4. For all experiments, we only run one iteration during training. To achieve more precise registration, we iteratively update the transformation twice during test time. For more training details and network architecture implementation, please refer to the supplementary materials.

In this section, we visualize the graph edges generated by different methods to demonstrate the superiority of building graph via our edge generator. The edges for an object model is shown in Figure 5. For the KNN graph, we choose the five nearest neighbors of each point and draw an edge between it and the neighbors. For the proposed method, edges with a weight greater than 0.1 in the edge weight matrix are chosen for visualization. As illustrated in Figure 5, our edge generator creates edges mostly in the overlapping parts, avoiding information interference in non-overlapping parts. Points in non-overlapping areas are not connected to any other points, making it easier to identify them.

In this section, we present the results of the ablation study to analyze the effectiveness of two key components. All ablation studies are performed on the partial-to-partial dataset with the same settings as section 5.1.7. We analyze the two key components as follows:

To demonstrate the effectiveness of the AIS module, we design a variant to replace the AIS module, and the resulting method is denoted as RGMVar1. The variant computes the distance matrix $\mathbf{D}$ between the nodes of the two graphs by computing the L2 norm of node features, transforms $\mathbf{D}$ into a positive matrix within the finite values by the formula $e^{-\left(\mathbf{D}_{i,j}\ -\ 0.5\right)}$, and uses Sinkhorn to calculate the soft correspondences. The results are listed in the first row of Table VIII. We find that the registration accuracy becomes very poor by using the AIS variant, and this result shows that the proposed AIS module can effectively improve the registration performance. This is because the AIS module generates more correct matching than its variant, and an illustrative example of the correspondences generated by AIS and its variant is shown in Figure 6 (e) and (b).

To understand the importance of our edge generator, we design two variants that use full connection edges and sparse connection edges instead of building edges by a transformer, and the resulting methods are denoted as RGMVar2 and RGMVar3, respectively. For the full connection edges, we connect each point and all other points in the point cloud. For the sparse connection edges, we only connect each point and those points in a sphere centered at this point with a radius of 0.2. The results are shown in the second and third rows of Table VIII, and they are also inferior to the performance by using a transformer to generate edges. Examples of the hard correspondences generated by each of these two variants is shown in Figure 6 (c) and (d).