Graph Matching Based A Probabilistic Spectral Method
A large number of tasks in computer vision involve finding consistent correspondences between two sets of features. A common solution is graph matching which is widely used in various research areas. In this paper, we consider the graph matching problem as an Integer Quadratic Programming (IQP) formulation. Solution of this problem is NP-hard as it is known to all. Therefore, we focus on an efficient approximation algorithm using a spectral technique. Firstly, we introduce a probabilistic interpretation of the spectral graph matching problem. It is easier to solve than previous spectral methods. Secondly, spectral matching can be interpreted as a maximum likelihood estimate of the assignment probabilities and that the graduated assignment algorithm boils down to an estimate maximize formulation. Finally, we propose a new graph matching algorithm that achieves robust matching results. We experimentally demonstrate the effectiveness of our approach for synthetic graph and real images.
graph matching IQP spectral methods NP-hard graduated assignment
Zhenhua Ren Jieyu Zhao
Research Institute of Computer Science and Technology,Ningbo University, Ningbo, China, 315211
国际会议
2011 Seventh International Conference on Natural Computation(第七届自然计算国际会议 ICNC 2011)
上海
英文
1538-1543
2011-07-26（万方平台首次上网日期，不代表论文的发表时间）