An Efficient Globally Optimal Algorithm for Asymmetric Point Matching

Wei Lian, Lei Zhang, and Ming-Hsuan Yang

Abstract:

Although the robust point matching algorithm has been demonstrated to be effective for non-rigid registration, there are several issues with the adopted deterministic annealing optimization technique. First, it is not globally optimal and regularization on the spatial transformation is needed for good matching results. Second, it tends to align the mass centers of two point sets. To address these issues, we propose a globally optimal algorithm for the robust point matching problem where each model point has a counterpart in scene set. By eliminating the transformation variables, we show that the original matching problem is reduced to a concave quadratic assignment problem where the objective function has a low rank Hessian matrix. This facilitates the use of large scale global optimization techniques. We propose a branch-and-bound algorithm based on rectangular subdivision where in each iteration, multiple rectangles are used to increase the chances of subdividing the one containing the global optimal solution. In addition, we present an efficient lower bounding scheme which has a linear assignment formulation and can be efficiently solved. Extensive experiments on synthetic and real datasets demonstrate the proposed algorithm performs favorably against the state-of-the-art methods in terms of robustness to outliers, matching accuracy, and run-time.

Paper:

[Download]

Matlab source code:

[Download]

Data used in this paper:

Dataset used in section 6.1.1 [download]

Dataset used in section 6.1.3 [download]

Dataset used in section 6.2.1 [download]

Dataset used in section 6.2.2 [download]

Figures:

The following figures show the matching results by (from left to right column) our method using similarity transformation, our method using affine transformation, MSTT, UG, RRWM, IPFP, MPM and TM on images of motobike, car, eiffel and revolver, respectively. Here blue lines indicate correct matches and red lines indicate wrong matches. Please refer to Section 6.1.3 of our paper for the detailed experiment setup.

Motobike

Car

Eiffel Tower

Revolver