cvpr cvpr2013 cvpr2013-106 cvpr2013-106-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Feng Zhou, Fernando De_la_Torre
Abstract: 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. The code is available at http : / / human s en s ing . c s . cmu .edu / fgm.
[1] H. A. Almohamad and S. O. Duffuaa. A linear programming approach for the weighted graph matching problem. IEEE Trans. Pattern Anal. Mach. Intell., 15(5):522–525, 1993. 4
[2] P. J. Besl and N. D. McKay. A method for registration of 3-d shapes. IEEE Trans. Pattern Anal. Mach. Intell., 14(2):239– 256, 1992. 3
[3] W. Brendel and S. Todorovic. Learning spatiotemporal graphs of human activities. In ICCV, 2011. 1
[4] R. Burkard, M. DellAmico, and S. Martello. Assignment Problems. SIAM, 2009. 1
[5] M. Chertok and Y. Keller. Efficient high order matching. IEEE Trans. Pattern Anal. Mach. Intell., 32(12):2205–2215, 2010. 3
[6] M. Cho, J. Lee, and K. M. Lee. Reweighted random walks for graph matching. In ECCV, 2010. 1, 3, 4, 6, 7
[7] H. Chui and A. Rangarajan. A new point matching algo-
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18] rithm for non-rigid registration. Comput. Vis. Image Underst., 89(2-3): 114–141, 2003. 6, 7 T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. In NIPS, 2006. 1, 2, 4, 6 O. Duchenne, F. Bach, I.-S. Kweon, and J. Ponce. A tensorbased algorithm for high-order graph matching. IEEE Trans. Pattern Anal. Mach. Intell., 33(12):2383–2395, 2011. 3 O. Duchenne, A. Joulin, and J. Ponce. A graph-matching kernel for object categorization. In ICCV, 2011. 1 S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Trans. Pattern Anal. Mach. Intell., 18(4):377–388, 1996. 1, 3, 4, 6 J. Hays, M. Leordeanu, A. A. Efros, and Y. Liu. Discovering texture regularity as a higher-order correspondence problem. In ECCV, 2006. 1 H. Jiang, S. X. Yu, and D. R. Martin. Linear scale and rotation invariant matching. IEEE Trans. Pattern Anal. Mach. Intell., 33(7): 1339–1355, 2011. 1 M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV, 2005. 1, 2, 4, 6, 7 M. Leordeanu, M. Hebert, and R. Sukthankar. An integer projected fixed point method for graph matching and MAP inference. In NIPS, 2009. 1, 3, 4, 6 M. Leordeanu, R. Sukthankar, and M. Hebert. Unsupervised learning for graph matching. Int. J. Comput. Vis. , 95(1): 1 18, 2011. 6 H. Li, J. Huang, S. Zhang, and X. Huang. Optimal object matching via convexification and composition. In ICCV, 2011. 1 E. M. Loiola, N. M. De Abreu, P. O. Boaventura, P. Hahn,
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29] and T. M. Querido. A survey for the quadratic assignment problem. Eur. J. Oper. Res., 176(2):657–690, 2007. 1, 2 A. Myronenko and X. B. Song. Point set registration: Coherent point drift. IEEE Trans. Pattern Anal. Mach. Intell., 32(12):2262–2275, 2010. 7 N. Quadrianto, A. J. Smola, L. Song, and T. Tuytelaars. Kernelized sorting. IEEE Trans. Pattern Anal. Mach. Intell., 32(10):1809–1821, 2010. 1 L. S. Shapiro and M. Brady. Feature-based correspondence: an eigenvector approach. Image Vision Comput., 10(5):283– 288, 1992. 2 J. R. Ullmann. An algorithm for subgraph isomorphism. J. ACM, 23:31–42, 1976. 1 S. Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Mach. Intell., 10(5):695–703, 1988. 2, 4 B. J. van Wyk and M. A. van Wyk. A POCS-based graph matching algorithm. IEEE Trans. PatternAnal. Mach. Intell., 26(1 1):1526–1530, 2004. 1, 4 M. Zaslavskiy, F. R. Bach, and J.-P. Vert. A path following algorithm for the graph matching problem. IEEE Trans. Pattern Anal. Mach. Intell., 31(12):2227–2242, 2009. 3, 4 R. Zass and A. Shashua. Probabilistic graph and hypergraph matching. In CVPR, 2008. 1, 3, 4, 6 Z. Zhang. Iterative point matching for registration of freeform curves and surfaces. Int. J. Comput. Vis., 13(2): 119– 152, 1994. 3 F. Zhou and F. De la Torre. Factorized graph matching. IEEE Trans. Pattern Anal. Mach. Intell. Under review, http : / / human s en s ing . c s . cmu . edu / fgm. 3, 4, 5 F. Zhou and F. De la Torre. Factorized graph matching. In CVPR, 2012. 2, 3, 4, 6 222999222977