cvpr cvpr2013 cvpr2013-192 cvpr2013-192-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nan Hu, Raif M. Rustamov, Leonidas Guibas
Abstract: In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
[1] M. Aubry, U. Schlickewei, and D. Cremers. The wave kernel signature: A quantum mechanical approach to shape analysis. In ICCV Workshop 4DMOD, 2011. 2, 3.1
[2] T. Biyikoglu, J. Leydold, and P. F. Stadler. Laplacian eigenvectors of graphs: Perron-Frobenius and Faber-Krahn Type Theorems. Springer, 2007. 3.1
[3] T. Caetano, J. McAuley, C. L., Q. Le, and A. Smola. Learning graph matching. IEEE Trans. PAMI, 3 1(6): 1048–1058, 2009. 1
[4] M. Cho, J. Lee, and K. M. Lee. Reweighted random walks for graph matching. In Proceedings of the 11th European conference on Computer vision: Part V, ECCV’ 10, pages 492–505, Berlin, Heidelberg, 2010. Springer-Verlag. 2, 4, 5. 1, 5. 1
[5] T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. In NIPS’06, pages 313–320, 2006. 2, 4
[6] D. Emms, R. C. Wilson, and E. R. Hancock. Graph matching using the interference of continuous-time quantum walks. Pattern Recogn., 42(5):985–1002, May 2009. 2
[7] M. Eshera and K. Fu. A graph distance measure for image analysis. IEEE Trans. Syst. Man Cybern., page 398Ð408, 1984. 2
[8] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Trans. Patt. Anal. Mach. Intell., 18, 1996. 2, 4
[9] M. Gori, M. Maggini, and L. Sarti. Exact and approximate graph matching using random walks. IEEE Trans. Pattern Anal. Mach. Intell., 27(7): 1100–1 111, July 2005. 2
[10] D. K. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2): 129–150, Mar. 2011. 3.1 222999111200 Average accuracy of an image to the rest of the sequence (b) RRWM (c) dap+ dkRRWM (a) Matching performance (d) dB+ dap+ dkRRWM Figure 4: Matching on pose house sequence. Yellow lines depict the correct matches, while red lines show the wrong matches.
[11] N. Hu and L. Guibas. Spectral Descriptors for Graph Matching. ArXiv e-prints, Apr. 2013. arXiv: 1304. 1572[cs.CV]. 1, 2, 3.1, 3.1, 3.1.1, 3.2, 4, 5.1
[12] S. Jouili and S. Tabbone. Graph matching based on node signatures. In Proceedings of GbRPR ’09, pages 154–163, Berlin, Heidelberg, 2009. Springer-Verlag. 2
[13] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV ’05, pages 1482–1489, Washington, DC, USA, 2005. IEEE Computer Society. 2, 4
[14] M. Leordeanu, M. Hebert, and R. Sukthankar. An integer projected fixed point method for graph matching and map inference. In NIPS. Springer, December 2009. 2, 4
[15] M. Leordeanu, R. Sukthankar, and M. Hebert. Unsupervised learning for graph matching. Int. J. Comput. Vision, 96(1):28–45, Jan. 2012. 1
[16] M. E. Lübbecke and J. Desrosiers. Selected topics in column generation. Oper. Res., 53(6): 1007–1023, Nov. 2005. 1, 3.1.1
[17] B. Luo and E. R. Hancock. Structural graph matching using the em algorithm and singular value decomposition. IEEE Trans. Pattern Anal. Mach. Intell., 23(10): 1120–1 136, Oct. 2001. 2
[18] J. J. McAuley, T. de Campos, and T. S. Caetano. Unified graph matching in euclidean spaces. IEEE Conf. CVPR, pages 1871–1878, 2010. 5, 5.3
[19] H. Qiu and E. R. Hancock. Graph matching and clustering using spectral partitions. Pattern Recogn., 39(1):22–34, Jan. 2006. 2
[20] A. Robles-Kelly and E. R. Hancock. String edit distance, random walks and graph matching. In Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, pages 104–1 12, London, UK, UK, 2002. Springer-Verlag. 2
[21] A. Robles-Kelly and E. R. Hancock. Graph edit distance from spectral seriation. IEEE Trans. Pattern Anal. Mach. Intell., 27(3):365–378, Mar. 2005. 2
[22] C. Schellewald and C. Schnörr. Probabilistic subgraph matching based on convex relaxation. In EMMCVPR’05, pages 171–186, Berlin, Heidelberg, 2005. Springer-Verlag. 2
[23] A. Shokoufandeh and S. J. Dickinson. A unified framework for indexing and matching hierarchical shape structures. In IWVF-4, pages 67–84, London, UK, UK, 2001. SpringerVerlag. 2
[24] J. Sun, M. Ovsjanikov, and L. Guibas. A concise and provably informative multi-scale signature based on heat diffu-
[25]
[26]
[27]
[28]
[29]
[30] [3 1] sion. In Eurographics Symposium on Geometry Processing (SGP), 2009. 2, 3. 1 S. Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Mach. Intell., 10(5):695–703, 1988. 2 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, Nov. 2004. 2, 4 P. C. Wong, H. Foote, G. Chin, P. Mackey, and K. Perrine. Graph signatures for visual analytics. IEEE trans. on visualization and computer graphics, 12(6): 1399–413, 2006. 2 E. P. Xing, A. Y. Ng, M. I. Jordan, and S. J. Russell. Distance metric learning with application to clustering with side-information. In NIPS, pages 505–512, 2002. 1 M. Zaslavskiy, F. Bach, and J.-P. Vert. A path following algorithm for the graph matching problem. IEEE Transactions on PAMI, 3 1(12):2227–2242, 2009. 2 R. Zass and A. Shashua. Probabilistic graph and hypergraph matching. CVPR, 2008. 4 G. Zhao, B. Luo, J. Tang, and J. Ma. Using eigen-decomposition method for weighted graph matching. ICIC’07, pages 1283–1294, 2007. 2 222999111311