QGORE: Quadratic-Time Guaranteed Outlier Removal for Point Cloud Registration

Area of Science:

• Computer Vision
• Geometric Algorithms
• 3D Data Processing

Background:

• Correspondence-based point cloud registration is crucial for 3D matching.
• Existing 3D keypoint methods generate high outlier rates (>95%).
• Guaranteed Outlier Removal (GORE) offers robustness but suffers from high computational cost.

Purpose of the Study:

• To develop a computationally efficient Guaranteed Outlier Removal (GORE) method.
• To preserve the globally optimal solution of GORE while improving efficiency.
• To enable practical application of GORE in 3D point cloud registration.

Main Methods:

• Proposed Quadratic-time GORE (QGORE) with O(N^2) time complexity.
• Utilized a voting strategy with geometric consistency for tight upper bound estimation.
• Introduced a one-point RANSAC with 'rotation correspondence' for efficient lower bound estimation.
• Developed an l_p-like adaptive estimator for the optimization process.

Main Results:

• QGORE achieves the same robustness and optimality as the original GORE.
• QGORE is 1-2 orders of magnitude faster than GORE.
• The proposed methods significantly reduce computational complexity for outlier removal.
• Experimental results validate the effectiveness and efficiency of QGORE.

Conclusions:

• QGORE presents a significant advancement in efficient and robust 3D point cloud registration.
• The method overcomes the practical limitations of previous GORE algorithms.
• QGORE offers a viable solution for handling extreme outliers in large-scale 3D datasets.
• Source code will be publicly available to facilitate research and application.