iccv iccv2013 iccv2013-238 iccv2013-238-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Minsu Cho, Karteek Alahari, Jean Ponce
Abstract: Many tasks in computer vision are formulated as graph matching problems. Despite the NP-hard nature of the problem, fast and accurate approximations have led to significant progress in a wide range of applications. Learning graph models from observed data, however, still remains a challenging issue. This paper presents an effective scheme to parameterize a graph model, and learn its structural attributes for visual object matching. For this, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. Experimental evaluations on synthetic and real image datasets demonstrate the effectiveness of our approach, and show significant improvement in matching accuracy over graphs with pre-defined structures.
[1] http://www.di.ens.fr/willow/research/graphlearning/.
[2] S. Belongie, J. Malik, and J. Puzicha. Shape matching and object recognition using shape contexts. TPAMI, 2002.
[3] A. C. Berg, T. L. Berg, and J. Malik. Shape matching and object recognition using low distortion correspondences. In CVPR, 2005.
[4] W. Brendel and S. Todorovic. Learning spatiotemporal graphs of human activities. In ICCV, pages 778–785, 2011. 31 Table 3: Matching performance on 5 object classes from Caltech-256 and PASCAL VOC2007 datasets. For each class, the average performance on 20 random splits of the data is reported. Our method (HARG-SSVM) shows the best matching results on all the 5 classes. For more details, see text and our project website [1]. FaceMotorbikeCarDuckWine bottle MethodAcc. (%)errorAcc. (%)errorAcc. (%)errorAcc. (%)errorAcc. (%)error wSD W/ oWl- eS aS PrVEn iM nCg786 45. 7630 . 1 2034524 5748. 1260 . 21 281692354024. 3810 . 23 504 91354 294. 120 0. 218216817 5302. 5340 . 1 2 9204 HARG-SSVM93.90.07071.40.13471.90.15872.20.12686.10.090 node attributes, and matching results are shown. In the graph model, bigger circles represent stronger nodes, and darker lines denote stronger edges. In the second and the fifth columns, to better visualize node attributes, we show the edge responses based on the learned SIFT attributes. For each model, some matching examples with high scores are shown. The results show that the learned graph model enables robust matching in spite of deformation and appearance changes. (Best viewed in pdf.)
[5] T. S. Caetano, J. J. McAuley, L. Cheng, Q. V. Le, and A. J. Smola. Learning graph matching. TPAMI, 2009.
[6] M. Cho, J. Lee, and K. M. Lee. Reweighted random walks for graph matching. In ECCV, 2010.
[7] M. Cho and K. M. Lee. Progressive graph matching: Making a move of graphs via probabilistic voting. In CVPR, 2012.
[8] D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. IJPRAI, 2004.
[9] T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. In NIPS, 2007.
[10] N. Dalal and B. Triggs. Histograms of oriented gradients for human detection. In CVPR, 2005.
[11] J. Davis and P. Domingos. Bottom-up learning of Markov network structure. In ICML, 2010.
[12] O. Duchenne, F. Bach, I. Kweon, and J. Ponce. A tensor-based algorithm for high-order graph matching. In CVPR, 2009.
[13] O. Duchenne, A. Joulin, and J. Ponce. A graph-matching kernel for object categorization. In ICCV, 2011.
[14] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. Trans. PAMI, 1996.
[15] S. Hare, A. Saffari, and P. H. S. Torr. Efficient Online Structured Output Learning for Keypoint-Based Object Tracking. In CVPR, 2012.
[16] T. Joachims, T. Finley, and C.-N. Yu. Cutting-plane training of structural svms. Machine Learning, 2009.
[17] S.-I. Lee, V. Ganapahthi, and D. Koller. Efficient Structure Learning of Markov Networks using L1-Regularization. In NIPS, 2006.
[18] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV, 2005.
[19] M. Leordeanu, M. Hebert, and R. Sukthankar. Beyond local appearance: Category recognition from pairwise interactions of simple features. In CVPR, 2007.
[20] M. Leordeanu, M. Hebert, and R. Sukthankar. An integer projected fixed point method for graph matching and map inference. In NIPS, 2009.
[21] M. Leordeanu, R. Sukthankar, and M. Hebert. Unsupervised learning for graph matching. IJCV, 2012.
[22] D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 2004.
[23] J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust wide baseline stereo from maximally stable extremal regions. In BMVC, 2002.
[24] K. Mikolajczyk and C. Schmid. Scale and affine invariant interest point detectors. IJCV, 2004.
[25] S. Nowozin, P. Gehler, and C. Lampert. On parameter learning in CRF-based approaches to object class image segmentation. ECCV, 2010.
[26] D. Pachauri, M. Collins, V. SIngh, R. Kondor, and V. S. Deepti Pachauri, Maxwell Collins, Risi Kondor. Incorporating domain knowledge in matching problems via harmonic analysis. In ICML, 2012.
[27] A. Sharma, R. Horaud, J. Cech, , and E. Boyer. Topologically-robust 3d shape matching based on diffusion geometry and seed growing. In CVPR, 2011.
[28] M. Szummer, P. Kohli, and D. Hoiem. Learning CRFs using graph cuts. In ECCV, 2008.
[29] B. Taskar, C. Guestrin, and D. Koller. Max-margin markov networks. In NIPS, 2003.
[30] L. Torresani, V. Kolmogorov, and C. Rother. Feature correspondence via graph matching: Models and global optimization. In ECCV, 2008.
[31] I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. JMLR, 2005.
[32] S. Umeyama. An eigen decomposition approach to weighted graph matching problems. Trans. PAMI, 1988.
[33] B. Yao and L. Fei-Fei. Action recognition with exemplar based 2.5d graph matching. In ECCV, 2012. 32