nips nips2006 nips2006-39 nips2006-39-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Timothee Cour, Praveen Srinivasan, Jianbo Shi
Abstract: Graph matching is a fundamental problem in Computer Vision and Machine Learning. We present two contributions. First, we give a new spectral relaxation technique for approximate solutions to matching problems, that naturally incorporates one-to-one or one-to-many constraints within the relaxation scheme. The second is a normalization procedure for existing graph matching scoring functions that can dramatically improve the matching accuracy. It is based on a reinterpretation of the graph matching compatibility matrix as a bipartite graph on edges for which we seek a bistochastic normalization. We evaluate our two contributions on a comprehensive test set of random graph matching problems, as well as on image correspondence problem. Our normalization procedure can be used to improve the performance of many existing graph matching algorithms, including spectral matching, graduated assignment and semidefinite programming. 1
[1] Marcello Pelillo. A unifying framework for relational structure matching. icpr, 02:1316, 1998.
[2] Christian Schellewald and Christoph Schn¨ rr. Probabilistic subgraph matching based on convex relaxation. o In Energy Minimization Methods in Computer Vision and Pattern Recognition, 2005.
[3] P.H.S. Torr. Solving markov random fields using semi definite programming. In Artificial Intelligence and Statistics, 2003.
[4] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 18, 1996.
[5] Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. In International Conference on Computer Vision, October 2005.
[6] Stella X. Yu and Jianbo Shi. Grouping with bias. In Advances in Neural Information Processing Systems, 2001.
[7] G.L.Scott and H.C.Longuett-Higgins. An algorithm for associating the features of two images. In Proceedings of the Royal Society of London B, 1991.
[8] Paul Knopp and Richard Sinkhorn. Concerning nonnegative matrices and doubly stochastic matrices. Pacific J. Math, 2:343–348, 1967.
[9] J.F. Sturm. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11–12:625–653, 1999. Special issue on Interior Point Methods.