RSKDD-Net: Random Sample-based Keypoint Detector and Descriptor

Introduction

Point cloud registration is an important problem in 3D computer vision, which aims to estimate the optimal rigid transformation between two point clouds. 3D keypoint detection and description are two fundamental components of point cloud registration. Inspired by numerous handcrafted 2D keypoint detectors and descriptors , researchers proposed several handcrafted 3D keypoint detectors and descriptors for point cloud. However, additional RGB channels in images contain richer information than Euclidean coordinates of point cloud without RGB information, which makes handcrafted 3D keypoint detectors and descriptors less reliable than that in 2D images.

With the rapid development of deep learning, many works have explored learning-based methods for 3D descriptors in point cloud . However, only a few works explore deep learning-based methods in 3D keypoint detection due to the lack of ground truth dataset for keypoint detector . 3DFeatNet and USIP are two pioneering works of learning-based keypoint detectors, however, they have less efficiency consideration. 3DFeatNet predicts saliency for each input point and select keypoints based on the predicted saliency. The per-point saliency estimation requires a considerable time thus is not applicable in practice. USIP relies on FPS to generate keypoint candidates. However, FPS has a time complexity of $\mathcal{O}(N^{2})$, therefore is inefficient and time-consuming. Hence, both two methods above can not efficiently process large scale point clouds, which restricts their applications in scenes that require real-time performance, such as autonomous driving.

Based on the above observation, we propose our network named as Random Sample-based Keypoint Detector and Descriptor Network (RSKDD-Net), which jointly generates keypoints and the corresponding descriptors for large scale point cloud efficiently. In this paper, we introduce the random sample concept in RSKDD-Net to improve the efficiency of our network, which is ill-considered in 3DFeatNet and USIP. Random sampling is highly efficient and has been utilized in point cloud semantic segmentation to improve the efficiency , however, can lead to a considerable information loss. Inspired by the success of dilation strategy in deep learning of 2D image , we propose a novel random dilation strategy to cluster neighbor points, which significantly enlarges the receptive field. We exploit attention mechanism to aggregate the positions and features of neighbor points to generate keypoints and also an attentive feature map to estimate saliency uncertainty of each keypoint. The generative framework avoids inefficient per-point saliency estimation in 3DFeatNet . To jointly learn keypoint detector and descriptor, the clusters and attentive feature maps are further fed into the descriptor network to generate descriptors. To train the descriptor in a weakly supervised manner, we introduce the matching loss, which utilizes a soft assignment strategy to estimate correspondences of keypoints. The network architecture can be seen in Fig. 1.

Extensive experiments are performed to evaluate our RSKDD-Net. The results show that our approach achieves state-of-the-art performance with much lower computation time.

To summarize, our main contributions are as follows:

We propose a deep learning-based method to jointly detect keypoints and generate descriptors for large scale point cloud registration. The proposed method achieves state-of-the-art performance with a more than $15\times$ higher speed.

We propose a novel random dilation strategy to enlarge the receptive field, which significantly improves the performance of keypoint detector and descriptor. Besides, an attention mechanism is introduced to aggregate the positions and features of neighbor points.

We propose an effective matching loss based on soft assignment strategy so that the descriptor can be trained in a weakly supervised manner.

Related work

Existing approaches of keypoint detector and descriptor for point cloud can be categorized into handcrafted and learning-based approaches.

The current handcrafted 3D keypoint detectors and descriptors are mainly inspired by numerous handcrafted methods in 2D images. SIFT-3D and Harris-3D are 3D extensions of widely used 2D detectors SIFT and Harris . Intrinsic Shape Signatures (ISS) selects points where the neighbor points in a ball region have large variations along each principal axis. For the description of keypoints, researchers have also developed several 3D descriptors based on the geometric features of points, like Point Feature Histograms (PFH) , Fast Point Feature Histograms (FPFH) and Signature of Histograms of Orientations (SHOT) . A comprehensive introduction of handcrafted 3D detectors and descriptors can be found in .

Learning-based approaches

Recent years, deep learning-based methods have been widely used for point cloud analysis . The most relevant approaches to our work are 3DFeatNet and USIP . Unlike previous learning-based descriptors which rely on ground truth matched pairs to train the network, 3DFeatNet proposed a weakly supervised 3D descriptor. The network samples positive and negative pairs according to the distance of point cloud and utilizes a triplet network to train the descriptor. For keypoints detection, they simply predict attentive weight for each point in point cloud and select salient points without more precise optimization. Unlike 3DFeatNet, the focus point of USIP is keypoint detector and how to train the detector fully unsupervised. They sample keypoint candidates using FPS and use SOM to organize the point cloud. An offset to the original candidate points and saliency uncertainty are predicted to select keypoints. USIP proposes probabilistic chamfer loss and point-to-point loss to train the network fully unsupervised. However, saliency estimation for each point of 3DFeatNet and FPS in USIP are both inefficient.

Approach

Attentive points aggregation

2 Descriptor

3 Loss

Denoting source and target point clouds as $\mathcal{S}$ and $\mathcal{T}$, keypoints from source and target point clouds as $\mathbf{X}^{\mathcal{S}}$ and $\mathbf{X}^{\mathcal{T}}$, the corresponding saliency uncertainties as $\mathbf{\Sigma}^{\mathcal{S}}$ and $\mathbf{\Sigma}^{\mathcal{T}}$, and descriptors as $\mathbf{Q}^{\mathcal{S}}$ and $\mathbf{Q}^{\mathcal{T}}$. The ground truth relative rotation $\mathbf{R}$ and translation $\mathbf{t}$ is also provided. For the training of detector, we follow USIP to use the probabilistic chamfer loss and point-to-point loss. Probabilistic chamfer loss is utilized to minimize the distance of keypoints in source and target point cloud and point-to-point loss is defined to penalize the keypoints for being too far from the original point clouds. Please refer to for the details of probabilistic chamfer loss and point-to-point loss.

Soft assignment can be considered as an approximate derivable version of nearest neighbor search on descriptors. Intuitively, the target keypoints with more similar descriptors to the source keypoint will be given a larger score. When $t\rightarrow 0$, the soft assignment will degenerate to a deterministic nearest neighbor search. Similarly, we can also calculate the corresponding source keypoint for each target keypoint using soft assignment strategy. Furthermore, according to the saliency uncertainty $\sigma_{i}\in\mathbf{\Sigma}$ of each keypoint, we introduce weight for each keypoint,

where $\sigma_{\max}$ is the pre-defined upper bound of saliency uncertainty. The final matching loss aims at minimizing the distance between estimated corresponding keypoints, which can be represented as

Intuitively, the reduction of the matching loss will motivate the soft assignment strategy to select keypoints that are closer in space as matching points, which pull the matched descriptors closer and unmatched descriptors away. Besides, the introduction of weights of keypoints makes keypoints with lower saliency uncertainties have higher weights in the matching loss.

Experiments

We evaluate our proposed RSKDD-Net on two large scale outdoor LiDAR datasets, namely KITTI Odometry Dataset (KITTI dataset) and Ford Campus Vision and Lidar Dataset (Ford dataset). KITTI dataset provides 11 sequences (00-10) with ground truth vehicle poses and we use Sequence 00 to train, Sequence 01 for validation and the others for testingWe simply drop Sequence 08 because of the large errors of ground truth vehicle poses in this sequence. Ford dataset contains two sequences and we only use this dataset for testing. For training, the current point cloud with the 10th point cloud after it is considered as a training pair. For testing, we use the current point cloud with the five consecutive frames before and after it as test data. Consequently, we obtain over 100,000 testing pairs in KITTI dataset and Ford dataset.

Evaluation metric

We follow the same evaluation metrics as in 3DFeatNet and USIP for keypoint detector and descriptor, namely Repeatability, Precision and Registration performance.

Repeatability is introduced in USIP to evaluate the stability of detected keypoints. Given source and target point clouds with the ground truth transformation, a keypoint in source point cloud is repeatable if its distance to the nearest keypoint in target point cloud is less than a distance threshold $\epsilon_{r}$. Repeatability is defined as the ratio of repeatable keypoints to all detected keypoints.

Registration performance is evaluated using RANSAC algorithm. Followed 3DFeatNet, the number of RANSAC iterations is adjusted based on 99% confidence and capped at 10000 iterations. We evaluate the relative translation error (RTE), relative rotation error (RRE) as in 3DFeatNet. A registration is considered as successful if RTE $<2$ m and RRE $<5^{\circ}$. Besides, we also calculate the average inlier ratio and iteration times of the RANSAC algorithm.

Baseline algorithms

We compare our approach with three handcrafted 3D keypoint detectors ISS , Harris-3D and SIFT-3D with handcrafted keypoint descriptor FPFH and two deep learning-based 3D keypoint detectors and descriptors: 3DFeatNet and USIP . We use the implementation in PCL for handcrafted detectors and descriptor. For USIP, we use the provided source code and retrain the model on KITTI dataset due to the lack of pretrained model of descriptors. For 3DFeatNet, we simply use the provided pretrained model and test it on KITTI dataset and Ford dataset. Besides, we also evaluate the repeatability of random sampled points for reference. Experiments on other handcrafted descriptors are displayed in our supplementary.

Implementation details

In the pre-processing, we firstly downsample the input point cloud by a Voxelgrid filter of 0.1 m grid size and extract the surface normals and curvature of each point as additional features following USIP . Then 16384 points are randomly sampled from the downsampled point cloud as input point cloud. The dilation ratio $\alpha_{d}$ is set to 2 and the number of neighbor points is set to 128. The network is implemented using PyTorch . We use SGD as the optimizer with learning rate of $0.001$ and momentum of $0.9$. Temperature $t$ in matching loss is set to 0.1. We train the network in two-stage, firstly the detector is trained with probabilistic chamfer loss and point-to-point loss. Then we train the descriptor based on the pretrained detector using matching loss and the detector network will also be fine-tuned in this stage. The network is trained on NVIDIA GeForce 1080Ti and evaluated on a PC with Intel i7-9750H and NVIDIA GeForce RTX 2060.

2 Evaluation

We evaluate the efficiency of our RSKDD-Net and other two learning-based methods on KITTI dataset and the computation time is shown in Table 1. The top row of Table 1 represents the number of input points and the second row represents the number of keypoints. Thanks to the random sample strategy and no requirements for per-point saliency estimation, our method shows a much higher efficiency than the other two learning-based methods. Noting that the computation time of 3DFeatNet and USIP increases mainly with the number of input points and the number of keypoints, respectively. In comparison, the computation time of our method does not increase significantly with the number of input points and keypoints. Specifically, our method is more than $30\times$ faster than USIP and 3DFeatNet to detect 512 keypoints from 16384 input points.

Repeatability

We calculate the repeatability of 128, 256 and 512 keypoints with distance threshold of 0.5m. Besides, the repeatability with different distance thresholds for 512 keypoints are also evaluated for reference. The results are displayed in Fig. 3. According to the results, the repeatability of our method outperforms all other methods for 128 to 512 keypoints with a significant margin. Specifically, the repeatability of our method is about 20% higher than that of USIP for 512 keypoints at distance threshold of 0.5 m, which demonstrates the high stability of our selected keypoints.

Precision

We evaluate the precision for 512 keypoints with different distance thresholds and also the precision for different numbers of keypoints with distance threshold of 1.0 m. The results in Fig. 4 show that our RSKDD-Net provides a much higher precision than other methods for different numbers of keypoints and also different distance thresholds. Noting that our RSKDD-Net performs better on KITTI dataset than on Ford dataset, the reason may be that the point clouds in KITTI dataset are more structured so that our RSKDD-Net can detect keypoints with more geometric information.

Registration performance

The number of keypoints for evaluation of registration performance is fixed at 512. The experiment results are displayed in Table 2. According to the experiments, our method gives a better RTE than both handcrafted and learning-based methods. Although the RRE and success rate is slightly inferior to USIP, the inlier ratio of our method is more than twice than that of USIP and brings much less average iteration times due to the high precision and repeatability. Taken together, our method outperforms all of the other methods.

Qualitative Visualization

We provide several qualitative visualization results of our proposed method. Two registration results are shown in left two columns of Fig. 5. The number of keypoints is fixed to 512 and the visualization results show a large inlier ratio of our proposed keypoint detector and descriptor. Besides, we give a sample of our keypoints detection results in the right column of Fig. 5. Although the method does not explicitly remove the points on ground plane, the detected keypoints automatically avoid the ground points and concentrate on points with geometric information like facades and corners. More qualitative results are provided in our supplementary.

3 Ablation study

We provide ablation study to illustrate the effectiveness of the random dilation cluster, attentive feature map, matching loss. All experiments of ablation study are performed on KITTI dataset. The repeatability and precision are calculated with 128, 256 and 512 keypoints. The distance thresholds of repeatability and precision are fixed at 0.5 m and 1.0 m, respectively.

Here we compare the performance of our proposed random dilation cluster with DPC and the corresponding repeatability and precision are displayed in Fig. 6(a) and Fig. 6(b). The results show that the random dilation cluster significantly improves the repeatability and precision of our network. And the random dilation cluster performs similar to and in some scenes even slightly better than DPC (e.g., the precision of 128 and 256 keypoints). In addition, our method is more simple and has no requirements for neighbor points sorting, which reduces the time complexity of neighbor points searching.

Attention feature map

In order to demonstrate the effectiveness of the attentive feature map for learning of descriptor, we remove the attentive feature map in the descriptor network and evaluate the precision. The results can be seen in Fig. 6(c). According to the results, the introduction of the attentive feature map results in an obvious increase in precision. The precision for different numbers of keypoints increases by about 0.1 with the attentive feature map.

Matching loss

We compare our matching loss with the triplet loss used in 3DFeatNet. Following 3DFeatNet, we sample positive and negative point cloud pairs based on the distance between two point cloud and the saliency uncertainty are also included in the triplet loss. Then we use the triplet loss to replace the proposed matching loss and retrain the network. The precision of the two loss functions can be seen in Fig. 6(d). According to the experiments, our matching loss significantly outperforms triplet loss in 3DFeatNet in our settings. Specifically, the precision of our method is about twice of that of the network training with triplet loss. Besides, we also perform experiments to study the effect of the temperature $t$ and also the weight in the proposed matching loss. As shown in Fig. 6(e), the precision with $t=0.5$ is obviously lower than the other two ones, which is due to the poor approximation of the soft assignment strategy with large $t$. And the performance will not change significantly when $t<0.1$. According to Fig. 6(f), the introduction of weight in the matching loss improves the performance of the descriptor.

Conclusion

This paper proposes a learning-based method to jointly detect keypoints and generate descriptors in large scale point cloud. The proposed RSKDD-Net achieves state-of-the-art performance with much faster inference speed. To overcome the drawback of random sampling, we propose a novel random dilation cluster strategy to enlarge the receptive field and an attention mechanism for positions and features aggregation. We propose a soft assignment-based matching loss so that the descriptor network can be trained in a weakly supervised manner. Extensive experiments are performed and demonstrate that our RSKDD-Net outperforms existing methods by a significant margin in repeatability, precision and registration performance.

Broader Impact

The proposed RSKDD-Net provides an efficient scheme to detect keypoints and generate descriptors for large scale point cloud registration. The method is most likely to be applied to localization and mapping system of autonomous vehicles to reduce the computation of point cloud registration, which may promote the development of autonomous driving. The development of autonomous driving can reduce the workload of human drivers and the incidence of traffic accidents, however, can have an impact on the determination of liability for traffic accidents and results in unemployment of human drivers. Besides, the proposed method has also applications on unmanned aerial vehicles. However, unmanned aerial vehicles can be utilized in military field, thereby threatening human safety. We should explore more beneficial applications of this method, such as promoting the development of autonomous driving to improve the quality of human life and improve its safety to reduce accidents.

Acknowledgments and Disclosure of Funding

This work is funded by National Natural Science Foundation of China (No. 61906138), the European Union’s Horizon 2020 Framework Programme for Research and Innovation under the Specific Grant Agreement No. 945539 (Human Brain Project SGA3), and the Shanghai AI Innovation Development Program 2018. We thank Guohao Li for helpful discussion.

References