Accelerating Globally Optimal Consensus Maximization in Geometric Vision.

Area of Science:

• Computer Vision
• Computational Geometry
• Optimization

Background:

• Branch-and-bound methods find globally optimal solutions for geometric problems but are computationally expensive.
• High dimensionality drastically increases the complexity of these methods, limiting practical applications.

Purpose of the Study:

• To develop a novel technique for branch-and-bound consensus maximization that reduces computational complexity.
• To enable the application of globally optimal solutions in real-time computer vision scenarios.

Main Methods:

• A new technique branches over an n-1 dimensional space for n-dimensional problems.
• The remaining degree of freedom is solved using the interval stabbing technique within bound calculations.
• This approach reduces the number of intervals and tightens bounds, decreasing overall iterations.

Main Results:

• The method achieves significant speed-up factors, often exceeding two orders of magnitude.
• Demonstrated effectiveness across fundamental computer vision tasks like camera resectioning and point set registration.
• The technique enhances the viability of globally optimal consensus maximization for online applications.

Conclusions:

• The proposed method offers a substantial reduction in computational complexity for branch-and-bound consensus maximization.
• This advancement makes globally optimal solutions practical for real-time computer vision problems.
• The technique significantly improves the efficiency of solving outlier-affected geometric problems.