 |
    |
On the Convergence of Graph Matching: Graduated Assignment Revisited
Yu Tian1, Junchi Yan1, Hequan Zhang3, Ya Zhang1, Xiaokang Yang1, and Hongyuan Zha2
1Shanghai Jiao Tong University, 200240, Shanghai, China
tianyu0124@gmail.com
ethanyan1985@gmail.com
ya_zhang@sjtu.edu.cn
xkyang@sjtu.edu.cn
2Georgia Institute of Technology, 30032, Atlanta, USA
zhanghequan1987@126.com
3Beijing Institute of Technology, 100081, Beijing, China
zha@cc.gatech.edu
Abstract. We focus on the problem of graph matching that is fundamental in computer vision and machine learning. Many state-of-the-arts frequently formulate it as integer quadratic programming, which incorporates both unary and second-order terms. This formulation is in general NP-hard thus obtaining an exact solution is computationally intractable. Therefore most algorithms seek the approximate optimum by relaxing techniques. This paper commences with the finding of the “circular” character of solution chain obtained by the iterative Gradient Assignment (via Hungarian method) in the discrete domain, and proposes a method for guiding the solver converging to a fixed point, resulting a convergent algorithm for graph matching in discrete domain. Furthermore, we extend the algorithms to their counterparts in continuous domain, proving the classical graduated assignment algorithm will converge to a double-circular solution chain, and the proposed Soft Constrained Graduated Assignment (SCGA) method will converge to a fixed (discrete) point, both under wild conditions. Competitive performances are reported in both synthetic and real experiments.
LNCS 7574, p. 821 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012