DANIEL: A fast and robust consensus maximization method for point cloud registration with high outlier ratios

Correspondence-based point cloud registration is a cornerstone in computer vision, robotics, autonomous navigation and remote sensing, which seeks to estimate the best rigid transformation between two point clouds from the point correspondences established over 3D keypoints. Owing to limited robustness and accuracy, current 3D keypoint matching techniques are rather prone to yield outliers, probably in large numbers, thus making robust estimation (outlier rejection) for the registration problem very important. Unfortunately, previously proposed robust registration methods often suffer from high computation cost or insufficient robustness when encountering high (or even extreme) outlier ratios, hardly ideal enough for practical use. In this paper, we present a novel, time-efficient consensus maximization solver, named Double-layered sAmpliNg with consensus maximization based on stratIfied Element-wise compatibiLity (DANIEL), for robust point cloud registration. DANIEL is smartly designed with two layers of random sampling operation, in order to find the inlier subset with the lowest computational cost possible. Specifically, we (i) apply the rigidity constraint to prune raw outliers in the first layer of one-point sampling, (ii) introduce a series of stratified element-wise compatibility tests to conduct rapid compatibility checking between minimal models so as to realize more efficient consensus maximization in the second layer of two-point sampling, and (iii) employ probabilistic termination conditions to ensure the timely return of the final inlier set. By conducting a series of experiments on multiple real datasets, we demonstrate that the proposed solver DANIEL (i) is robust against over 99% of outliers, (ii) is also significantly faster than previous state-of-the-art robust algorithms, and (iii) is fairly practical for use in real-world applications such as object localization and scan matching problems.