Globally consistent correspondence of multiple feature sets using proximal Gauss-Seidel relaxation

Jin Gang Yu, Gui Song Xia, Ashok Samal, Jinwen Tian

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Feature correspondence between two or more images is a fundamental problem towards many computer vision applications. The case of correspondence between two images has been intensively studied, however, few works so far have been concerned with multi-image correspondence. In this paper, we address the problem of establishing a globally consistent correspondence among multiple (more than two) feature sets given the pairwise feature affinity information. Our main contribution is to propose a novel optimization framework for solving this problem based on the so-called Proximal Gauss-Seidel Relaxation (PGSR). The proposed method is distinguished from previous works mainly in three aspects: (1) it is more robust to noise and outliers; (2) its solution is based on convex relaxation and the principled PGSR method, which in general has convergence guarantee; (3) the scale of the problem in our method is linear with respect to the number of feature sets, making it computationally practical to be used in real-world applications. Experimental results both synthetic and real image datasets have demonstrated the effectiveness and superiority of the proposed method.

Original languageEnglish (US)
Pages (from-to)255-267
Number of pages13
JournalPattern Recognition
StatePublished - Mar 1 2016


  • Convex relaxation
  • Feature correspondence
  • Graph matching
  • Multiple feature set correspondence
  • Permutation matrix
  • Proximal Gauss-Seidel method

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Globally consistent correspondence of multiple feature sets using proximal Gauss-Seidel relaxation'. Together they form a unique fingerprint.

Cite this