An Efficient Globally Optimal Algorithm for Asymmetric Point Matching

Wei Lian, Lei Zhang, Ming Hsuan Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

32 Citations (Scopus)


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 in the case that 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 modified normal rectangular branch-and-bound algorithm to solve the resulting problem where multiple rectangles are simultaneously subdivided to increase the chance of shrinking the rectangle 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.

Original languageEnglish
Article number7555337
Pages (from-to)1281-1293
Number of pages13
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number7
Publication statusPublished - 1 Jul 2017


  • Branch and bound
  • concave optimization
  • linear assignment
  • point correspondence
  • robust point matching

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'An Efficient Globally Optimal Algorithm for Asymmetric Point Matching'. Together they form a unique fingerprint.

Cite this