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

Overview

KCP

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:

@article{lin2022kcp,
  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},
  volume={7},
  number={2},
  pages={1471--1477},
  year={2022},
  doi={10.1109/LRA.2021.3140130},
}

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. CMake โ‰ฅ 3.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

nanoflann

cd ~
git clone https://github.com/jlblancoc/nanoflann
cd nanoflann
mkdir build && cd build
cmake .. -DNANOFLANN_BUILD_EXAMPLES=OFF -DNANOFLANN_BUILD_TESTS=OFF
make
sudo make install

TEASER++

cd ~
git clone https://github.com/MIT-SPARK/TEASER-plusplus
cd TEASER-plusplus
git checkout d79d0c67
mkdir build && cd build
cmake .. -DBUILD_TESTS=OFF -DBUILD_PYTHON_BINDINGS=OFF -DBUILD_DOC=OFF
make
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 ..
make

With Python Binding

git clone https://github.com/StephLin/KCP
cd KCP
mkdir build && cd build
cmake .. -DKCP_BUILD_PYTHON_BINDING=ON -DPYTHON_EXECUTABLE=$(which python3)
make

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:

C++

#include <kcp/solver.hpp>

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

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

auto solver = kcp::KCP(params);

Python

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).

Owner
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 4 Dec 21, 2021
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 31 Jun 6, 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.1k Jun 25, 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
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 161 Apr 7, 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 25 Apr 22, 2022
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 โ˜… 5 Mar 25, 2022
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

Yuriy Solodkyy 1.2k Jun 24, 2022
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

John Bandela 204 Jun 15, 2022
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

Omar Ahmed 22 May 31, 2022
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

phil9 8 Nov 24, 2021
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

Roman Merkushin 46 Jun 25, 2022
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

null 15 Jun 5, 2022
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

VectorCamp 191 Jun 17, 2022
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

breeze 17 May 25, 2022