K-Closest Points and Maximum Clique Pruning for Efficient and Effective 3-D Laser Scan Matching (RA-L 2022)



License Build

The official implementation of KCP: K-Closest Points and Maximum Clique Pruning for Efficient and Effective 3D Laser Scan Matching, accepted for publication in the IEEE Robotics and Automation Letters (RA-L).

KCP is an efficient and effective local point cloud registration approach targeting for real-world 3D LiDAR scan matching problem. A simple (and naive) understanding is: ICP iteratively considers the closest point of each source point, but KCP considers the k closest points of each source point in the beginning, and outlier correspondences are mainly rejected by the maximum clique pruning method. KCP is written in C++ and we also support Python binding of KCP (pykcp).

For more, please refer to our paper:

  • Yu-Kai Lin, Wen-Chieh Lin, Chieh-Chih Wang, K-Closest Points and Maximum Clique Pruning for Efficient and Effective 3-D Laser Scan Matching. IEEE Robotics and Automation Letters (RA-L), vol.7, no. 2, pp. 1471 -- 1477, Apr. 2022. (paper) (preprint) (code) (video)

If you use this project in your research, please cite:

  title={K-Closest Points and Maximum Clique Pruning for Efficient and Effective 3-D Laser Scan Matching},
  author={Lin, Yu-Kai and Lin, Wen-Chieh and Wang, Chieh-Chih},
  journal={IEEE Robotics and Automation Letters},

and if you find this project helpful or interesting, please Star the repository. Thank you!

Table of Contents

📦 Resources

⚙️ Installation

The project is originally developed in Ubuntu 18.04, and the following instruction supposes that you are using Ubuntu 18.04 as well. I am not sure if it also works with other Ubuntu versions or other Linux distributions, but maybe you can give it a try 👍

Also, please feel free to open an issue if you encounter any problems of the following instruction.

Step 1. Preparing the Dependencies

You have to prepare the following packages or libraries used in KCP:

  1. A C++ compiler supporting C++14 and OpenMP (e.g. GCC 7.5).
  2. CMake3.11
  3. Git
  4. Eigen3 ≥ 3.3
  5. nanoflann
  6. TEASER++d79d0c67

GCC, CMake, Git, and Eigen3

sudo apt update
sudo apt install -y g++ build-essential libeigen3-dev git

sudo apt install -y software-properties-common lsb-release
wget -O - https://apt.kitware.com/keys/kitware-archive-latest.asc 2>/dev/null | gpg --dearmor - | sudo tee /etc/apt/trusted.gpg.d/kitware.gpg >/dev/null
sudo apt update
sudo apt install cmake


cd ~
git clone https://github.com/jlblancoc/nanoflann
cd nanoflann
mkdir build && cd build
sudo make install


cd ~
git clone https://github.com/MIT-SPARK/TEASER-plusplus
cd TEASER-plusplus
git checkout d79d0c67
mkdir build && cd build
sudo make install

Step 2. Preparing Dependencies of Python Binding (Optional)

The Python binding of KCP (pykcp) uses pybind11 to achieve operability between C++ and Python. KCP will automatically download and compile pybind11 during the compilation stage. However, you need to prepare a runable Python environment with header files for the Python C API (python3-dev):

sudo apt install -y python3 python3-dev

Step 3. Building KCP

Execute the following commands to build KCP:

Without Python Binding

git clone https://github.com/StephLin/KCP
cd KCP
mkdir build && cd build
cmake ..

With Python Binding

git clone https://github.com/StephLin/KCP
cd KCP
mkdir build && cd build

Step 4. Installing KCP to the System (Optional)

This will make the KCP library available in the system, and any C++ (CMake) project can find the package by find_package(KCP). Think twice before you enter the following command!

# Under /path/to/KCP/build
sudo make install

🌱 Examples

We provide two examples (one for C++ and the other for Python 3) These examples take nuScenes' LiDAR data to perform registration. Please check

for more information.

📝 Some Remarks

Tuning Parameters

The major parameters are

  • kcp::KCP::Params::k and
  • kcp::KCP::Params::teaser::noise_bound,

where k is the number of nearest points of each source point selected to be part of initial correspondences, and noise_bound is the criterion to determine if a correspondence is correct. In our paper, we suggest k=2 and noise_bound the 3-sigma (we use noise_bound=0.06 meters for nuScenes data), and those are default values in the library.

To use different parameters to the KCP solver, please refer to the following snippets:


#include <kcp/solver.hpp>

auto params = kcp::KCP::Params();

params.k                  = 2;
params.teaser.noise_bound = 0.06;

auto solver = kcp::KCP(params);


import pykcp

params = pykcp.KCPParams()
params.k = 2
params.teaser.noise_bound = 0.06

solver = pykcp.KCP(params)

Controlling Computational Cost

Instead of correspondence-free registration in TEASER++, KCP considers k closest point correspondences to reduce the major computational cost of the maximum clique algorithm, and we have expressed the ability for real-world scenarios without any complicate or learning-based feature descriptor in the paper. However, it is still possible to encounter computational time or memory issue if there are too many correspondences fed to the solver.

We suggest controlling your keypoints around 500 for k=2 (in this way the computational time will be much closer to the one presented in the paper).

Torwarding Global Registration Approaches

It is promising that KCP can be extended to a global registration approach if a fast and reliable sparse feature point representation method is employed.

In this way, the role of RANSAC, a fast registration approach usually used in learning based approaches, is similar to KCP's, but the computation results of KCP are deterministic, and also, KCP has better theoretical supports.

🎁 Acknowledgement

This project refers to the computation of the smoothness term defined in LOAM (implemented in Tixiao Shan's excellent project LIO-SAM, which is licensed under BSD-3). We modified the definition of the smoothness term (and it is called the multi-scale curvature in this project).

You might also like...
Functional programming style pattern-matching library for C++
Functional programming style pattern-matching library for C++

Mach7: Pattern Matching for C++ by Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup Abstract Pattern matching is an abstraction mechanism that can

Simple header only pattern matching for c++14

Simple, Extensible C++ Pattern Matching Library I have recently been looking at Haskell and Rust. One of the things I wanted in C++ from those languag

Pan-Genomic Matching Statistics
Pan-Genomic Matching Statistics

SPUMONI Pan-genomic Matching Statistics for Targeted Nanopore Sequencing Based on MONI: A MEM-finder with Multi-Genome References. MONI index uses the

fuzzy matching selection gui

fm === fm provides a gui to select an item from a list using a fuzzy matching algorithm. When an item is selected, it is sent to the plumber `send` po

Distance matching plugin

Distance Matching This plug-in is custom implementation of the Distance Matching technique which was shown by Laurent Delayen at Nucl.ai 2016. In two

An in-progress matching decompilation of Final Fantasy VII For the PSX.

FFVII An in-progress decompilation of the original US release of Final Fantasy VII on the PSX. Building (Linux) Install build dependencies The build p

A portable fork of the high-performance regular expression matching library

Vectorscan? A fork of Intel's Hyperscan, modified to run on more platforms. Currently ARM NEON/ASIMD is 100% functional, and Power VSX are in developm

CVE-2022-0185 POC and Docker and Analysis write up
CVE-2022-0185 POC and Docker and Analysis write up

CVE-2022-0185 linux 内核提权(逃逸) [toc] 漏洞简介 漏洞编号: CVE-2022-0185 漏洞评分: 漏洞产品: linux kernel - fsconfig syscall 影响范围: linux kernel 5.1-rc1 ~ 5.16.2 利用条件: linu

  • Could it apply to 2d point cloud registration

    Could it apply to 2d point cloud registration

    Hello author, Thanks for your sharing excellent work to community!

    • Could we apply KCP to a 2d point cloud registration problem ?
    • If we can, does KCP need user to provide point cloud correspondences? Teaser++ does not support pure 2D transformation, and it also needs user to generate the correspondences, here

    Thanks for your help.

    opened by narutojxl 2
  • Could I close the pmc notice?

    Could I close the pmc notice?

    HI Lin, the program always print the debug info "*** [pmc: thread 3] current max clique = 154, time = 0.0690331 sec DEBUG current mc: 154 DEBUG current mc: 154 DEBUG current mc: 154 DEBUG current mc: 154" Could I close it and what should I do?

    opened by AdamPengG 2
  • Add CodeQL workflow for GitHub code scanning

    Add CodeQL workflow for GitHub code scanning

    Hi StephLin/KCP!

    This is a one-off automatically generated pull request from LGTM.com :robot:. You might have heard that we’ve integrated LGTM’s underlying CodeQL analysis engine natively into GitHub. The result is GitHub code scanning!

    With LGTM fully integrated into code scanning, we are focused on improving CodeQL within the native GitHub code scanning experience. In order to take advantage of current and future improvements to our analysis capabilities, we suggest you enable code scanning on your repository. Please take a look at our blog post for more information.

    This pull request enables code scanning by adding an auto-generated codeql.yml workflow file for GitHub Actions to your repository — take a look! We tested it before opening this pull request, so all should be working :heavy_check_mark:. In fact, you might already have seen some alerts appear on this pull request!

    Where needed and if possible, we’ve adjusted the configuration to the needs of your particular repository. But of course, you should feel free to tweak it further! Check this page for detailed documentation.

    Questions? Check out the FAQ below!


    Click here to expand the FAQ section

    How often will the code scanning analysis run?

    By default, code scanning will trigger a scan with the CodeQL engine on the following events:

    • On every pull request — to flag up potential security problems for you to investigate before merging a PR.
    • On every push to your default branch and other protected branches — this keeps the analysis results on your repository’s Security tab up to date.
    • Once a week at a fixed time — to make sure you benefit from the latest updated security analysis even when no code was committed or PRs were opened.

    What will this cost?

    Nothing! The CodeQL engine will run inside GitHub Actions, making use of your unlimited free compute minutes for public repositories.

    What types of problems does CodeQL find?

    The CodeQL engine that powers GitHub code scanning is the exact same engine that powers LGTM.com. The exact set of rules has been tweaked slightly, but you should see almost exactly the same types of alerts as you were used to on LGTM.com: we’ve enabled the security-and-quality query suite for you.

    How do I upgrade my CodeQL engine?

    No need! New versions of the CodeQL analysis are constantly deployed on GitHub.com; your repository will automatically benefit from the most recently released version.

    The analysis doesn’t seem to be working

    If you get an error in GitHub Actions that indicates that CodeQL wasn’t able to analyze your code, please follow the instructions here to debug the analysis.

    How do I disable LGTM.com?

    If you have LGTM’s automatic pull request analysis enabled, then you can follow these steps to disable the LGTM pull request analysis. You don’t actually need to remove your repository from LGTM.com; it will automatically be removed in the next few months as part of the deprecation of LGTM.com (more info here).

    Which source code hosting platforms does code scanning support?

    GitHub code scanning is deeply integrated within GitHub itself. If you’d like to scan source code that is hosted elsewhere, we suggest that you create a mirror of that code on GitHub.

    How do I know this PR is legitimate?

    This PR is filed by the official LGTM.com GitHub App, in line with the deprecation timeline that was announced on the official GitHub Blog. The proposed GitHub Action workflow uses the official open source GitHub CodeQL Action. If you have any other questions or concerns, please join the discussion here in the official GitHub community!

    I have another question / how do I get in touch?

    Please join the discussion here to ask further questions and send us suggestions!

    opened by lgtm-com[bot] 0
Yu-Kai Lin
M.S. student in Computer Science @ NCTU
Yu-Kai Lin
TAFuzzer: Effective and Efficient Targeted Fuzzing framework for Smart Contract Vulnerability Detection (CCS2022a Under Review).

TAFuzzer An effective and efficient targeted fuzzing framework for smart contract vulnerability detection. Requirements TAFuzzer is supported on Linux

null 2 Feb 7, 2022
An implementation of ICP(Iterative Closest Point).

An implementation of ICP(Iterative Closest Point). Users can specify which dimensions of transformation to optimize.

Ming Cao 5 Aug 18, 2022
Kernel source for j7y17lte - the goal is to make it as closest to linux-stable sources as possible without breaking OneUI compatibility.

Linux kernel release 3.x <http://kernel.org/> These are the release notes for Linux version 3. Read them carefully, as they tell you what this is al

Exynos7870 1 Oct 28, 2021
A laser cut Dreamcast Pop'n Music controller and integrated memory card using the Raspberry Pi Pico's Programmable IO

Dreamcast Pop'n Music Controller Using Raspbery Pi Pico (RP2040) Intro This is a homebrew controller for playing the Pop'n Music games on the Sega Dre

null 42 Dec 29, 2022
OpenScan is an open-source document scanner app that enables users to scan hard copies of documents or notes and convert it into a PDF file. No ads. No data collection. We respect your privacy.

OpenScan An open source app that enables users to scan hardcopies of documents or notes and convert it to a PDF file. No ads. No data collection. We r

Ethereal Developers Inc 1.2k Jan 4, 2023
StochFuzz - Sound and Cost-effective Fuzzing of Stripped Binaries by Incremental and Stochastic Rewriting

StochFuzz: A New Solution for Binary-only Fuzzing StochFuzz is a (probabilistically) sound and cost-effective fuzzing technique for stripped binaries.

Zhuo Zhang 164 Dec 5, 2022
A C++11 large integer library with effective high performance, simplistic in nature and also clean in the eyes.

BigIntegerCPP BigIntegerCPP is a C++11 port of large integer library used in CryptoLib4Pascal. It allows mostly parsing of numbers as strings in diffe

Telepati 26 Dec 22, 2022
A web application which finds the shortest or quickest path from two points in the city of Rio de Janeiro.

A web application which finds the shortest or quickest path from two points in the city of Rio de Janeiro. Obviously not Waze. (final project for EDA @ EMAp, 2021)

null 2 Nov 17, 2021
Lib 2d - A c++ library for paths defined by points within the 2d space

#lib_2d A c++ library for anything related to points within the 2d space (using floating point data types) using Catch as testing framework https://gi

Martin Buck 46 Dec 16, 2021
Open source Splatoon 2 save editor for the Nintendo Switch (NX) built on top of the effective-spoon project

Open source Splatoon 2 save editor for the Nintendo Switch (NX) built on top of the effective-spoon project

Crusty ★ 6 Sep 16, 2022