The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Graph matching plays a central role in solving correspondence problems in computer vision. Graph matching problems that incorporate pair-wise constraints can be cast as a quadratic assignment problem (QAP). Unfortunately, QAP is NP-hard and many algorithms have been proposed to solve different relaxations. This paper presents factorized graph matching (FGM), a novel framework for interpreting and optimizing graph matching problems. In this work we show that the affinity matrix can be factorized as a Kronecker product of smaller matrices. There are three main benefits of using this factorization in graph matching: (1) There is no need to compute the costly (in space and time) pair-wise affinity matrix; (2) The factorization provides a taxonomy for graph matching and reveals the connection among several methods; (3) Using the factorization we derive a new approximation of the original problem that improves state-of-the-art algorithms in graph matching. Experimental results in synthetic and real databases illustrate the benefits of FGM.

Notes

Text Reference

Feng Zhou and Fernando De la Torre Frade, "Factorized Graph Matching," IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June, 2012.

BibTeX Reference

@inproceedings{Zhou_2012_7022,
   author = "Feng Zhou and Fernando {De la Torre Frade}",
   title = "Factorized Graph Matching",
   booktitle = "IEEE Conference on Computer Vision and Pattern Recognition (CVPR)",
   month = "June",
   year = "2012",
}

The Robotics Institute

Menu