K-Closest Points and Maximum Clique Pruning for Efficient and Effective 3-D Laser Scan Matching

Yu-Kai Lin, Wen-Chieh Lin, Chieh-Chih Wang

IEEE Robotics and Automation Letters (RA-L). Vol.7, No. 2, pp. 1471-1477, Apr. 2022


We propose K-Closest Points (KCP), an efficient and effective laser scan matching approach inspired by LOAM and TEASER++. The efficiency of KCP comes from a feature point extraction approach utilizing the multi-scale curvature and a heuristic matching method based on the k-closest points. The effectiveness of KCP comes from the integration of the feature point matching approach and the maximum clique pruning. We compare KCP against well-known scan matching approaches on synthetic and real-world LiDAR data (nuScenes dataset). In the synthetic data experiment, KCP-TEASER reaches a state-ofthe-art root-mean-square transformation error (0.006m, 0.014◦ ) with average computational time 49ms. In the real-world data experiment, KCP-TEASER achieves an average error of (0.018m, 0.101◦ ) with average computational time 77ms. This shows its efficiency and effectiveness in real-world scenarios. Through theoretic derivation and empirical experiments, we also reveal the outlier correspondence penetration issue of the maximum clique pruning that it may still contain outlier correspondences.

Paper | Code | Video | Presentation