  Correspondence-based point cloud registration is a cornerstone in geometric
computer vision, robotics perception, photogrammetry and remote sensing, which
seeks to estimate the best rigid transformation between two point clouds from
the correspondences established over 3D keypoints. However, due to limited
robustness and accuracy, current 3D keypoint matching techniques are very prone
to yield outliers, probably even in very large numbers, making robust
estimation for point cloud registration of great importance. Unfortunately,
existing robust methods may suffer from high computational 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 RANSAC-type consensus maximization solver, named DANIEL
(Double-layered sAmpliNg with consensus maximization based on stratIfied
Element-wise compatibiLity), for robust registration. DANIEL is designed with
two layers of random sampling, in order to find inlier subsets 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) probabilistic termination conditions are employed to ensure the timely
return of the final inlier set. Based on a variety of experiments over multiple
real datasets, we show that DANIEL is robust against over 99% outliers and also
significantly faster than existing state-of-the-art robust solvers (e.g.
RANSAC, FGR, GORE).
