An Efficient Globally Optimal Algorithm for Asymmetric Point Matching.

Area of Science:

• Computer Vision
• Computational Geometry
• Geometric Algorithms

Background:

• Robust point matching is crucial for non-rigid registration.
• Deterministic annealing optimization has limitations, including lack of global optimality and mass center alignment bias.
• Existing methods require regularization for accurate spatial transformation.

Purpose of the Study:

• To develop a globally optimal algorithm for robust point matching.
• To address limitations of deterministic annealing in non-rigid registration.
• To provide a more accurate and robust solution for point set registration.

Main Methods:

• Formulated the robust point matching problem as a concave quadratic assignment problem by eliminating transformation variables.
• Developed a modified normal rectangular branch-and-bound algorithm for global optimization.
• Introduced an efficient lower bounding scheme with a linear assignment formulation.

Main Results:

• The proposed algorithm achieves global optimality, unlike previous methods.
• Demonstrated superior performance in robustness to outliers compared to state-of-the-art techniques.
• Achieved higher matching accuracy and improved run-time efficiency on synthetic and real datasets.

Conclusions:

• The novel globally optimal algorithm effectively solves the robust point matching problem.
• The method offers significant advantages in accuracy, robustness, and computational efficiency for non-rigid registration.
• This approach provides a powerful new tool for point set registration tasks.