A branch-and-bound approach to correspondence and grouping problems

Area of Science:

• Computer Vision
• Machine Learning
• Computational Geometry

Background:

• Data correspondence is crucial for computer vision tasks like 3D reconstruction.
• Existing methods struggle with repetitive textures and mismatches.
• A robust solution combining appearance and geometric information is needed.

Purpose of the Study:

• To develop a novel algorithm for feature correspondence in computer vision.
• To guarantee global optimization for improved accuracy.
• To address limitations of existing appearance-based and geometry-based methods.

Main Methods:

• Formulating feature correspondence as a mixed integer program.
• Solving the program efficiently using a series of linear programs.
• Employing a branch-and-bound procedure for optimization.
• Generalizing the framework for data correspondence under unknown parametric models.

Main Results:

• The algorithm successfully identifies feature correspondences with maximal inliers.
• It verifies both appearance similarity and geometric constraints.
• Validated on synthesized and real-world challenging image data.

Conclusions:

• The proposed algorithm offers a mathematically guaranteed global optimization for feature correspondence.
• It effectively combines appearance and geometric constraints.
• Demonstrates broad applicability in computer vision problems requiring data grouping.