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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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-of-the-art root-mean-square transformation error (0.006, m, 0.014) with average computational time 49 ms. In the real-world data experiment, KCP-TEASER achieves an average error of (0.018 m, 0.101) with average computational time 77 ms. 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.

Original languageEnglish
Pages (from-to)1471-1477
Number of pages7
JournalIEEE Robotics and Automation Letters
Issue number2
StatePublished - 1 Apr 2022


  • Computer vision for transportation
  • Mapping
  • Range sensing


Dive into the research topics of 'K-Closest Points and Maximum Clique Pruning for Efficient and Effective 3-D Laser Scan Matching'. Together they form a unique fingerprint.

Cite this