Paper Info
Title
Graduated Consistency-Regularized Optimization For Multi-Graph Matching
Abstract
Graph matching has a wide spectrum of computer vision applications such as finding feature point correspondences across images. The problem of graph matching is generally NP-hard, so most existing work pursues suboptimal solutions between two graphs. This paper investigates a more general problem of matching N attributed graphs to each other, i.e. labeling their common node correspondences such that a certain compatibility/affinity objective is optimized. This multi-graph matching problem involves two key ingredients affecting the overall accuracy: a) the pairwise affinity matching score between two local graphs, and b) global matching consistency that measures the uniqueness and consistency of the pairwise matching results by different sequential matching orders. Previous work typically either enforces the matching consistency constraints in the beginning of iterative optimization, which may propagate matching error both over iterations and across different graph pairs; or separates score optimizing and consistency synchronization in two steps. This paper is motivated by the observation that affinity score and consistency are mutually affected and shall be tackled jointly to capture their correlation behavior. As such, we propose a novel multi-graph matching algorithm to incorporate the two aspects by iteratively approximating the global-optimal affinity score, meanwhile gradually infusing the consistency as a regularizer, which improves the performance of the initial solutions obtained by existing pairwise graph matching solvers. The proposed algorithm with a theoretically proven convergence shows notable efficacy on both synthetic and public image datasets.
Year
DOI
Venue
2014
10.1007/978-3-319-10590-1_27
COMPUTER VISION - ECCV 2014, PT I
Keywords
Field
DocType
Permutation Matrix,Graph Match,Quadratic Assignment Problem,Consistency Constraint,Assignment Matrix
Convergence (routing),Pairwise comparison,Local consistency,Optimal matching,Quadratic assignment problem,Computer science,Matching (graph theory),Artificial intelligence,3-dimensional matching,Blossom algorithm,Machine learning
Conference
Volume
ISSN
Citations 
8689
0302-9743
26
PageRank 
References 
Authors
0.75
33
6
Name
Order
Citations
PageRank
Junchi Yan189183.36
Yin Li279735.85
Wei Liu34041204.19
Hongyuan Zha46703422.09
Xiaokang Yang53581238.09
Stephen Mingyu Chu6260.75