A Practical O(N²) Outlier Removal Method for Correspondence-Based Point Cloud Registration.

Area of Science:

• 3D Computer Vision
• Computational Geometry
• Robotics

Background:

• Point Cloud Registration (PCR) is crucial for 3D data alignment.
• Correspondence-based PCR methods are preferred for their lack of initial guess requirements.
• Existing 3D keypoint techniques suffer from high outlier rates, and robust methods are computationally expensive.

Purpose of the Study:

• To develop a computationally efficient and highly robust outlier removal method for PCR.
• To address the limitations of current techniques in handling high outlier rates and computational costs.

Main Methods:

• Introduced a polynomial time (O(N^2)) outlier removal method based on the bound principle.
• Defined novel concepts: Correspondence Matrix (CM) and Augmented Correspondence Matrix (ACM).
• Proposed a cost function minimizing the determinant of CM/ACM for tight bounds and a scale-adaptive Cauchy estimator (SA-Cauchy) for optimization.

Main Results:

• Demonstrated robustness at outlier rates exceeding 99% on simulated and real datasets.
• Achieved 1-2 orders of magnitude speed improvement compared to existing methods.
• The proposed method effectively reduces the input set size while maintaining a low outlier rate.

Conclusions:

• The proposed method offers a significant advancement in robust and efficient PCR.
• It provides a practical solution for scenarios with extremely high outlier rates.
• The publicly available source code facilitates further research and application.