Carnegie Mellon University
Deformable Graph Matching

Feng Zhou and Fernando De la Torre Frade
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June, 2013.

  • Adobe portable document format (pdf) (6MB)
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.

Graph matching (GM) is a fundamental problem in computer science, and it has been successfully applied to many problems in computer vision. Although widely used, existing GM algorithms cannot incorporate global consistence among nodes, which is a natural constraint in computer vision problems. This paper proposes deformable graph matching (DGM), an extension of GM for matching graphs subject to global rigid and non-rigid geometric constraints. The key idea of this work is a new factorization of the pair-wise affinity matrix. This factorization decouples the affinity matrix into the local structure of each graph and the pair-wise affinity edges. Besides the ability to incorporate global geometric transformations, this factorization offers three more benefits. First, there is no need to compute the costly (in space and time) pair-wise affinity matrix. Second, it provides a unified view of many GM methods and extends the standard iterative closest point algorithm. Third, it allows to use the path-following optimization algorithm that leads to improved optimization strategies and matching performance. Experimental results on synthetic and real databases illustrate how DGM outperforms state-of-the-art algorithms for GM.


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

BibTeX Reference
   author = "Feng Zhou and Fernando {De la Torre Frade}",
   title = "Deformable Graph Matching",
   booktitle = "IEEE Conference on Computer Vision and Pattern Recognition (CVPR)",
   month = "June",
   year = "2013",