Fast and Robust Registration of Partially Overlapping Point Clouds

I INTRODUCTION

Point cloud registration is the problem of estimating the rigid relative pose transformation that aligns a pair of point clouds into the same coordinate system. This is a key problem in many downstream applications including 3D scene reconstruction , localisation and SLAM . Recent applications such as Augmented Reality (AR) , cooperative (multi-agent) perception for autonomous vehicles and multi-agent SLAM introduce new challenges to this problem. Specifically, these applications require registration methods that are robust to point clouds with low overlap, e.g. when sensors are far apart, and capable of operating in real-time.

Existing registration methods are often designed and evaluated assuming a significant overlap between the input point clouds. This assumption is valid for applications such as SLAM and lidar odometry , where pairs of point clouds are obtained sequentially in adjacent time steps by a single vehicle navigating in a driving environment. On the other hand, applications such as cooperative perception and multi-agent SLAM require registering point clouds obtained simultaneously from a pair of sensors on two different vehicles that are potentially far apart, and thus, may have low field-of-view overlap, e.g. Figure 1. As the relative translation between the sensors increases, the number of identifiable correspondences decreases, which poses challenges in registering the point clouds accurately.

The majority of existing point cloud registration methods cannot guarantee real-time execution. Traditional local registration methods such as Iterative Closest Point (ICP) solve the problem iteratively assuming an initial relative pose. However, the iterative nature of such methods renders them unfeasible for real-time applications, particularly considering large scale point clouds. These methods are also prone to non-optimal solutions when the initial pose estimate is poor, which may be addressed with global-optimisation variants at the cost of higher computational complexity. Another category of methods identify correspondences between point clouds using a distance metric between hand-engineered features or learned point-wise features . These correspondences are often contaminated by a large number outliers and must be filtered using RANSAC or learned models , which further increases the registration execution time. Furthermore, state-of-the-art learning-based models require computationally demanding 3D convolutions and generate numerous putative correspondences, introducing a bottleneck on the RANSAC loop and rendering real-time execution unfeasible.

To mitigate the aforementioned limitations, we propose a novel point cloud registration method capable of operating in real-time and robust to low-overlapping point clouds. The proposed method identifies correspondences between the source and target point clouds by learning point-wise features. A novel encoder hierarchically subsamples the point clouds to reduce the number of key points and improve the run-time performance. The resulting features are refined using self- and cross-attention based on a graph neural network. The attention network leverages geometrical relationships between key points and their features across to improve the correspondence accuracy, particularly in regions of low overlap. The relative pose parameters are obtained by fitting the learned correspondences using Random Sample Consensus (RANSAC) to robustly reject outliers. During inference, the RANSAC fitting is done efficiently considering a small number of correspondences, which allows end-to-end inference times below 410ms. The model is trained and evaluated separately on the KITTI odometry dataset and a novel Cooperative Driving Dataset (CODD). The relative translation between sensors in CODD ranges up to 30m, introducing challenging pairs of point clouds with low overlap, which we hope will create a new research benchmark. Our contributions are summarised as:

A computationally efficient point-wise feature encoder that allows identifying correspondences between point clouds;

A graph neural network that provides self- and cross-attention between point clouds and improves the quality of correspondences;

A novel registration method for point clouds that is robust to partially-overlapping point clouds and capable of operating in real-time;

A new synthetic lidar dataset containing low overlapping point clouds in a wide range of driving scenarios;

II RELATED WORKS

This section reviews existing point cloud registration methods in the literature and highlights how the method proposed in this paper differs from these existing works. We divide existing methods in the literature into two categories: traditional registration methods and learning-based methods.

Iterative Closest Point (ICP) is a local registration method that assumes an initial relative pose and iteratively computes the transformation parameters that minimise the distance between each point in the source point cloud and its closest neighbour in the target point cloud. This method is highly sensitive to the initial pose estimate, and converges to non-optimal local-minima results when the initial pose estimate is poor. To mitigate this, estimate global optimum solutions for ICP considering branch-and-bound search over the transformation space. However, such global methods have significantly higher execution times, which prevents their usage in real-time applications.

Other traditional approaches use handcrafted features to find correspondences between the point clouds. Fast Point Feature Histogram (FPFH) encodes the local geometry of 3D points using multi-dimensional feature vectors. But the correspondences obtained by comparing FPFH features are often contaminated by a large number of outliers, which prevents accurate registration. For this reason, RANSAC methods are used to filter out the outlier correspondences. More recently, TEASER reformulates the registration problem using a truncated least-squares cost, which results in improved registration accuracy compared to RANSAC when considering a high number of outliers.

II-B Learning-based Methods

One group of learning-based registration methods focus on learning accurate correspondences between the point clouds. Generally, these methods learn a mapping from the original Euclidean space to a latent feature space and optimise the mapping such that corresponding points have a small distance in the latent space. Deng et al. uses a PointNet model to learn point-wise features and trains the model using an $N$-tuple loss. VCR-Net learns point-wise feature vectors using multi-layer-perceptrons (MLPs) to extract local features, which are refined using global attention and used to identify correspondences between point clouds. In contrast, uses sparse fully convolutional networks to obtain voxel-wise features and trains the model using variations of triplet loss with hard negative mining. The resulting correspondences are often contaminated with outliers and need to be pruned using RANSAC or further learning-based filtering methods before estimating the pose transformation parameters.

Another group of methods solve the problem end-to-end by learning the relative pose transformation directly. For example, PCRNet uses a PointNet model to encode a global feature vector for both source and target point clouds and directly regress the transformation parameters. DeepVCP uses PointNet++ to create point-wise features, then selects top K salient points using a learned weighting network to generate a deep feature embedding. The embeddings are fed to a 3D CNN to obtain soft-correspondences which are finally used to compute the transformation parameters in closed form.

The proposed method differs from previous works in the following ways. First, our method considers a novel and computationally efficient point-wise feature encoder based on Set Abstraction (SA) and Feature Propagation (FP) layers . While previous works have used PointNet++ feature encoders, we distinguish our encoder by adopting an architecture that hierarchically subsamples points at each layer, resulting in improved computational performance. Secondly, we improve the quality of the correspondences using a novel graph-based attention network that allows to efficiently combine self- and cross- information across point clouds. Differently from the feature-based attention in , the proposed graph attention leverages both spatial and feature dimensions of local neighbourhoods to refine point-wise features. Finally, we extend our analysis beyond existing datasets and evaluate our model performance in challenging low overlapping point clouds using a novel dataset where the translation between sensor poses vary uniformly up to 30 meters.

III PROBLEM FORMULATION

This error is a form of the Orthogonal Procrustes problem and admits the closed-form solution described below. First, the centroids are computed as

and the covariance matrix, denoted by $H$, is obtained using

Finally, the rotation matrix and translation vector $R,t$ that minimise Eq. 1 are computed in closed-form as

considering the Singular Value Decomposition (SVD) $H=USV^{T}$. The next section proposes a novel method to efficiently obtain correspondences between pairs of point clouds.

IV PROPOSED METHOD

This section presents a novel method for robust point cloud registration using learned correspondences targetting efficient, real-time inference. Figure 2 describes the components and data flow of the proposed method. The proposed method can be summarised as follows:

Both point clouds are fed to an encoder to obtain a subset of key points and associated point-wise features.

A graph neural network refines the point-wise features considering self- and cross-attention.

The resulting features are used to identify correspondences between the source and target key points.

The relative transformation parameters $R,t$ are robustly estimated using a RANSAC formulation of the problem defined in Section III.

The aforementioned components and the training process are described in the following subsections.

The encoder is a core component of the pipeline, as it computes point-wise features that will be used to identify correspondences. We propose a novel and computationally efficient encoder network based on Set Abstraction (SA) and Feature Propagation (FP) layers . The proposed encoder architecture, including the hyper-parameters of each layer, is depicted in Figure 3. The encoder outputs subset of sampled coordinates (key points) from the source and target point clouds, denoted by $X$ and $Y$, and their respective feature vectors, $f_{X}$ and $f_{Y}$. The input to the encoder consists of 3D point coordinates and corresponding features, e.g. lidar return intensity. Note that the input features are optional, but in this work they consist of a single scalar per point representing the lidar intensity. The source and target point clouds are fed to the encoder independently.

The first four encoder layers are SA layers. A SA layer consists of four operations:

$n$ coordinates are sampled from the previous layer using Farthest Point Sampling (FPS) .

A local neighbourhood of each sampled coordinate is established by selecting all points within radius $r$ of the respective coordinate.

The features of the points in each neighbourhood are fed to a shared Multi Layer Perceptron (MLP), denoted as a list $L$ containing the number of intermediate nodes per layer.

The resulting feature vectors of the $n$ sampled coordinates is computed using an aggregation function (max-pooling) over the MLP output of the points in the respective neighbourhoods.

Each SA layer hierarchically subsamples and aggregates information from the previous layer with progressively larger receptive volumes, which is a fundamental step in reducing the computational cost of our pipeline. At the same time, it is also important not to discard valuable information, i.e. prioritising that points from one layer are within the neighbourhood of sampled points in the next layer. This trade-off is achieved by tuning the layers’ hyper-parameters, namely $n,r,L$, such that the sampled points’ neighbourhood include most points from the previous layer. These hyper-parameters were optimised for large outdoor driving environments and would require fine-tuning for indoor scenarios.

The last encoder layer is an FP layer. It propagates high level information from SA4 to the points in the previous layer (SA3) as illustrated in Figure 3. This is achieved by interpolating the feature vectors in SA3 layer using the features from the three nearest-neighbour coordinates in SA4. The final features are obtained fusing the original SA3 features with the interpolated SA4 features using a shared MLP, represented by a list $L$ of intermediate nodes. More details about the interpolation can be found in .

IV-B Graph-based Attention

The feature vectors obtained with the encoder network represent local point cloud information. However, these features are agnostic to the global context of the point cloud. For example, if a point cloud contains multiple objects, e.g. trees, it would be difficult to distinguish between individual trees. Another problem, most critical for low overlapping point clouds, is that regions of overlap generally have different point densities in each point cloud, challenging the correct identification of correspondences since a point’s features change with the density of points in its neighbourhood. To mitigate both problems, we propose a graph-based attention module which transforms points’ feature vectors considering the wider point cloud context (self-attention) and the context of both source and target point-clouds (cross-attention). Self-attention increases the distinctiveness of key points by attending to their surrounding context. The cross-attention layer learns to refine point-wise features by attending to the most similar features across point clouds. Both layers, illustrated in Figure 4, increase the likelihood of finding accurate correspondences, even in cases of low overlap.

The self-attention layer introduces attention between points within the same point cloud. A graph connecting the points (nodes) is created for each point cloud using the $k$-Nearest-Neighbours of the points’ spatial coordinates. Let $f_{i}$ be a feature vector from either $f_{X}$ or $f_{Y}$. The self-attention layer computes a residual term for $f_{i}$ using the Crystal Graph Convolution Operation :

where $\mathcal{N}(i)$ indicates the $k$ neighbour nodes of $i$, $z_{i,j}=[f_{i},f_{j}]$ is the aggregated features of nodes $i,j$. $\sigma(\cdot)$ indicates the sigmoid function, and the Softplus function is defined as $\text{Softplus}(z)=\log(1+e^{z})$. The attention matrices $W_{f},W_{s}$ are parameters to be learned and the operation $\odot$ represents element-wise multiplication. We adopt the number of nearest neighbours $k=32$, which provides a good trade-off between accuracy and computational efficiency. This process is performed independently with shared parameters for both source and target point clouds.

Following the self-attention layer, the cross-attention layer allows interaction between the source and target point cloud features. This layer creates a bi-partite graph between source and target points. Each source point is connected to the $k$-Nearest-Neighbours nodes in the target point cloud, where the distance metric is the dot product between the feature vectors of the respective points. This layer uses the same residual update rule from Eq. 5, considering the different underlying graph and independent attention matrices $W_{f}^{\prime},W_{s}^{\prime}$. The graph-attention network output is given by the updated feature vectors from source and target point clouds, denoted by $\hat{f}_{X}$ and $\hat{f}_{Y}$, respectively.

IV-C Identifying Correspondences

where $T$ is a temperature hyper-parameter and the Softmax function is applied row-wise. Each element $\phi_{ij}$ represents the probability that the $i$-th key point in $X$ matches the $j$-th key point in $Y$. The Softmax function scales the coefficients of each row $\phi_{i}$, ensuring a probability distribution over the points in $Y$. The temperature parameter, denoted by $T$, controls the entropy of distribution across points in $Y$. In the limit, when $T\to 0^{+}$, the coefficients become the one-hot encoding of the point in $Y$ with the highest similarity (i.e. dot product). Finally, each key point $x_{i}\in X$ is matched to the key point in $Y$ with highest correspondence probability, resulting in the set of correspondence pairs $\{(x_{i},y_{\operatorname*{arg\,max}_{j}\phi_{ij}}),i=1,\dots,N\}$. The ordered set of correspondences in $Y$ is denoted as $\hat{Y}=\{y_{\operatorname*{arg\,max}_{j}\phi_{1j}},\dots,y_{\operatorname*{arg\,max}_{j}\phi_{Nj}}\}$.

IV-D Estimating Transformation Parameters

The previous step computes a correspondence for every point in $X$. In practice, only a fraction of points in $X$ will have correspondences in $Y$, particularly in the case of partially overlapping point clouds. Sensor noise and varying point densities can also lead to encoding errors and erroneous correspondences. To mitigate the effect of correspondence outliers, a common practice is to use sample consensus algorithms such as RANSAC . A general version of this algorithm applied to this problem consists of three steps:

Create a hypothesis: Sample a minimal set of three correspondences from the set of correspondences and compute the transformation parameters using Eq. 4.

Score the hypothesis based on consensus: Compute the number of inlier correspondences, where a correspondence $(x_{i},\hat{y}_{i}),x_{i}\in X,\hat{y}_{i}\in\hat{Y}$ is an inlier if $\left\|Rx_{i}+t-\hat{y}_{i}\right\|\leq\kappa$, where $\kappa$ is the inlier threshold, $R,t$ are the hypothesis parameters computed in the first step.

Repeat the previous steps for $L$ times and select the hypothesis with the highest number of inliers.

The number of tested hypotheses, denoted by $H$, offers a trade-off between computational performance and robustness to outliers. $H$ can also be derived to achieve a desired confidence of the selected hypothesis , i.e. sampling an outlier-free set of correspondences. While previous works used RANSAC with a large set of putative correspondences , this may be unfeasible for real-time systems. In this work, we achieve negligible RANSAC computational cost by learning a small set of correspondences ($N=512$), which allows to reduce the number of hypotheses being tested.

IV-E Training Process

The training process consists of optimising the encoder and attention networks to find accurate correspondences where they exist. We maximise the matching probabilities of ground-truth correspondences and minimise the matching probability of non-corresponding points. This is achieved by directly minimising the following loss function:

where the binary variable $\delta_{i}$ indicates whether the source point $x_{i}$ has a correspondence in $Y$ and $\hat{j}$ represents the index of the corresponding point in $Y$. Additionally, $N_{c}=\sum_{i=1}^{N}\delta_{i}$ is the number of ground-truth correspondences and $\lambda$ is a hyper-parameter scaling the contributions of incorrect matches into the loss function. A point in $X$ is considered to have a correspondence in $Y$ if, under the ground-truth transformation, it is within a distance smaller or equal to $1.6$ meters from a point in $Y$. This inlier distance is arbitrary and was chosen based on the smallest encoder radius. Data augmentation is employed by applying random rotation transformations to both input point clouds and adjusting the ground-truth rotation matrix accordingly. The optimisation details are described in Section V-C.

V PERFORMANCE EVALUATION

In this section, we first describe the datasets and the evaluation metrics, followed by the implementation details. We then compare the performance of the proposed method with traditional baselines, including ICP , FPFH RANSAC and TEASER ; and two state-of-the-art learning-based methods: FCGF and DGR . We also provide an ablation study identifying the impact of the proposed attention network into the registration performance.

The KITTI Odometry dataset is traditionally used to evaluate point cloud registration methods in outdoor environments. We follow the evaluation protocol of recent methods , which adopt sequences 0 to 5 for training, 6 to 8 for validation and 9 to 10 for testing. In each sequence, the samples are created by selecting pairs of points clouds obtained sequentially by a single vehicle such that the translation between the poses is less than 10m. The ground-truth pose is provided by GPS and refined using ICP to reduce misalignment.

The distribution of poses in the KITTI dataset is limited to the trajectory of a single vehicle as it navigates the environment. In practice, registration methods must be resilient to point clouds with arbitrary relative pose, where the overlap between point clouds may vary significantly across samples. To this end, we introduce Cooperative Driving Dataset (CODD) , an open-source synthetic dataset containing lidar point clouds collected simultaneously from multiple vehicles. This dataset is created using CARLA and features a diverse range of driving environments, including rural areas, suburbs, and dense urban centres. The dataset consists of 108 sequences, which are split into three independent subsets for training, validation and testing, as detailed in Table I. The samples are created by selecting all pair-wise combinations of point clouds obtained from vehicles driving simultaneously within a vicinity considering a maximum distance of 30m. Figure 5 presents the cumulative density plots of the relative distance (translation vector norm), rotation angle and overlap ratio of the pairs of point clouds in each dataset. The overlap ratio measures the overlap between point clouds as the percentage of points in the source point cloud that, when aligned, are within a distance smaller than $\gamma$ to any point in the target point cloud. Our CODD dataset has a significantly broader distribution of relative distance, rotation angles and overlap ratio between the point cloud pairs, which provides representative scenarios for cooperative perception and multi-agent SLAM.

V-B Evaluation Metrics

Following previous studies , the registration performance is evaluated in terms of the translation and rotation errors given by

where $R^{g},t^{g}$ denotes the ground-truth rotation matrix and translation vector, respectively. These metrics are reported considering their mean value over all dataset samples, denoted as Mean Translation Error (MTE) and Mean Rotation Error (MRE), respectively. We also consider the recall rate, measured as the ratio of successful registrations to the total number of samples, where the success criteria is $\text{TE}<0.6$m and $\text{RE}<5$deg following . The runtime performance is evaluated as the average inference time for the registration of a pair of point clouds disregarding the data loading time.

V-C Implementation Details

Our proposed method is implemented using PyTorch , PyTorch Geometric , the CUDA implementation of SA and FP layers from and the Open3D Procrustes RANSAC implementation. The model is trained independently for each dataset using the Adam optimiser with a learning rate of $0.1$, $\epsilon=10^{-4}$, $\beta_{1}=0.9,\beta_{2}=0.999$ and a batch size of 6 (pairs of point clouds). The model is trained for twenty epochs and the learning rate is reduced in half after every five epochs. For evaluation, the model with the lowest validation loss is selected. The temperature hyper-parameter, described in Section IV-C, is set to $T=10^{-2}$, and the loss scaling hyper-parameter is set to $\lambda=10$. During inference, the RANSAC inlier threshold, $\kappa$, is set to 0.5m, and the maximum number of RANSAC iterations, denoted by $H$, is computed to achieve $0.999$ confidence in the selected hypothesis within a limit of $10^{5}$ iterations. The point clouds from both datasets are downsampled using voxel sizes of 0.3m following previous methods . The overlap ratio distance threshold, $\gamma$, is set to 0.3m, following the down-sampling voxel size. The experiments are carried out on a Xeon ES-1630 CPU and Quadro M4000 GPU with 8 GB of memory. For fair comparison, all baselines are also evaluated on the same hardware. The official implementation and pre-trained models (30cm voxel) are used for the evaluation of in the KITTI dataset; likewise, the official TEASER implementation is adopted; and the Open3D implementation of FPFH, RANSAC and ICP is used for the evaluation of the respective methods.

V-D Performance on the KITTI dataset

The evaluation results, presented in Table II, show that our proposed method achieves competitive registration errors compared to other methods at a significantly lower inference time – more than five times faster than the fastest baseline. While the proposed method has a marginal increase in mean translation error compared to baseline methods, it achieves on-par recall rate relative to baseline methods. The mean translation and rotation errors of our method can be further reduced using ICP for refinement (Ours + ICP), at the cost of increased inference time.

V-E Performance on the CODD dataset

We aim to evaluate the performance of the proposed method and baselines on challenging low-overlapping pairs of point clouds. For a fair comparison, learning-based methods are also trained on the CODD dataset. Table III presents the results on the CODD test set, aggregated by the overlap ratio between point clouds in four progressively larger intervals – the last interval contains all samples. Traditional methods are not resilient to low overlapping points clouds, as the registration error increases significantly when considering lower overlap ratios, as shown in the first three rows of Table III. In contrast, the learning-based baselines are reasonably robust to low overlapping point clouds and achieve high recall rates on all intervals. However, the latter methods demand substantial running times due to their complex encoders and the filtering of a high number of putative correspondences. In contrast, our proposed method achieves similar or better recall rates to the learning-based baselines with more than 35 times faster inference times. This is achieved by our efficient encoder design which outputs a small number of correspondences, which in turn reduces the RANSAC inference time. Our efficient encoder strategy comes at the cost of a slight increase of the MTE and MRE metrics, as compared to DGR . To mitigate this, we apply ICP refinement to our model’s output (Ours + ICP), which allows achieving similar MTE and MRE for highly overlapping point clouds and outperforming all baselines on low-overlapping point clouds. Although the ICP refinement comes with an additional computational cost, we still achieve a nine-fold speed-up compared to learning-based baselines. Qualitative results are presented in Figure 1.

Figure 6 shows the Empirical Cumulative Density Function (ECDF) of the translation error, rotation errors, and inference time for different methods. The distributions indicate that the proposed method with ICP refinement has the best translation error across samples, closely matched by DGR , however with one order of magnitude smaller inference time. The inference time distributions show that the proposed method is the fastest among baselines, with an inference time of 320ms on average, with negligible standard deviation (17ms). The proposed method can operate in real-time considering data input frequencies up to 3Hz.

V-F Ablation Study

We assess the impact of the proposed attention network into the registration performance, measured in terms of translation and rotation errors. This is achieved by removing the graph attention module, retraining the model and evaluating its performance on the CODD test set. The results, indicated in Table III “Ours - Att”, show that the graph-attention network plays a key role in improving the accuracy of the correspondences, resulting in lower translation and rotation errors. The benefits of the graph attention network is most significant for low-overlapping point clouds, as indicated by the last range group in Table III, where the removal of the attention results in a 40% reduction of the registration recall and a significant increase in the mean translation and rotation errors.

VI CONCLUSION

We proposed a novel point cloud registration method focusing on fast inference of partially overlapping lidar point clouds. The performance evaluation on the KITTI and CODD datasets indicates that the proposed model can operate with a latency lower than 410ms and 320ms, respectively. The results show that the proposed model outperform baseline methods in terms of rotation and translation errors for pairs of point clouds with low overlap. Furthermore, we show that the proposed graph attention module plays a key role in improving the quality of the correspondences in low overlapping point clouds, which results in higher registration performance.

References