 |
    |
Graduated Consistency-Regularized Optimization for Multi-graph Matching
Junchi Yan1, 2, Yin Li3, Wei Liu4, Hongyuan Zha3, 5, Xiaokang Yang1, and Stephen Mingyu Chu2
1Shanghai Jiao Tong University, 200240, Shanghai, China
yanjunchi@sjtu.edu.cn
2IBM Research - China, 201203, Shanghai, China
3Georgia Institute of Technology, 30032, Atlanta, USA
4IBM T.J. Watson Research Center, 10598, New York, USA
5East China Normal University, 200062, Shanghai, China
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.
LNCS 8689, p. 407 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014