Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching
This work addresses point matching challenges in applications like computer vision and robotics, offering an incremental improvement in optimization efficiency and robustness.
The paper tackles the problem of aligning partially overlapping point sets under geometric transformations by introducing a global optimization method that transforms the Robust Point Matching objective into a quadratic form and uses a specialized Branch-and-Bound algorithm. Experiments show superior robustness to non-rigid deformations, noise, and outliers compared to state-of-the-art methods.
Numerous applications require algorithms that can align partially overlapping point sets while maintaining invariance to geometric transformations (e.g., similarity, affine, rigid). This paper introduces a novel global optimization method for this task by minimizing the objective function of the Robust Point Matching (RPM) algorithm. We first reveal that the original RPM objective is a cubic polynomial. Through a concise variable substitution, we transform this objective into a quadratic function. By leveraging the convex envelope of bilinear monomials, we derive a tight lower bound for this quadratic function. This lower bound problem conveniently and efficiently decomposes into two parts: a standard linear assignment problem (solvable in polynomial time) and a low-dimensional convex quadratic program. Furthermore, we devise a specialized Branch-and-Bound (BnB) algorithm that branches exclusively on the transformation parameters, which significantly accelerates convergence by confining the search space. Experiments on 2D and 3D synthetic and real-world data demonstrate that our method, compared to state-of-the-art approaches, exhibits superior robustness to non-rigid deformations, positional noise, and outliers, particularly in scenarios where outliers are distinct from inliers.