iccv iccv2013 iccv2013-214 iccv2013-214-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chao Wang, Lei Wang, Lingqiao Liu
Abstract: Graph matching has been widely used in various applications in computer vision due to its powerful performance. However, it poses three challenges to image sparse feature matching: (1) The combinatorial nature limits the size of the possible matches; (2) It is sensitive to outliers because the objective function prefers more matches; (3) It works poorly when handling many-to-many object correspondences, due to its assumption of one single cluster for each graph. In this paper, we address these problems with a unified framework—Density Maximization. We propose a graph density local estimator (퐷퐿퐸) to measure the quality of matches. Density Maximization aims to maximize the 퐷퐿퐸 values both locally and globally. The local maximization of 퐷퐿퐸 finds the clusters of nodes as well as eliminates the outliers. The global maximization of 퐷퐿퐸 efficiently refines the matches by exploring a much larger matching space. Our Density Maximization is orthogonal to specific graph matching algorithms. Experimental evaluation demonstrates that it significantly boosts the true matches and enables graph matching to handle both outliers and many-to-many object correspondences.
[1] M. Cho, J. Lee, and K. M. Lee. Feature correspondence and deformable object matching via agglomerative correspondence clustering. ICCV, 2009.
[2] M. Cho, J. Lee, and K. M. Lee. Reweighted random walks for graph matching. ECCV, 2010.
[3] M. Cho and K. M. Lee. Authority-shift clustering: Hierarchical clustering by authority seeking on graphs. CVPR, 2010.
[4] M. Cho and K. M. Lee. Mode-seeking on graphs via randomwalks. CVPR, 2012.
[5] M. Cho and K. M. Lee. Progressive graph matching: Making
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17] a move of graphs via probabilistic voting. CVPR, 2012. M. Cho, Y. M. Shin, and K. M. Lee. Co-recognition of image pairs by data-driven monte carlo image exploration. ECCV, 2008. D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. IJPRAI, pages 265–298, 2004. T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. NIPS, 2007. O. Duchenne, F. Bach, I. Kweon, and J. Ponce. A tensorbased algorithm for high-order graph matching. CVPR, 2009. V. Ferrari, T. Tuytelaars, and L. V. Gool. Simultaneous object recognition and segmentation from single or multiple model views. IJCV, 67(2):159–188, 2006. M. Gori, M. Maggini, and L. Sarti. Exact and approximate graph matching using random walks. TPAMI, 27(7): 1100– 1111, 2005. S. Jouili, S. Tabbone, and V. Lacroix. Median graph shift: A new clustering algorithm for graph domain. ICPR, 2010. J. Lee, M. Cho, and K. M. Lee. Hyper-graph matching via reweighted random walks. CVPR, 2011. M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. ICCV, 2005. M. Leordeanu and M. Herbert. An integer projected fixed point method for graph matching and map inference. NIPS, 2009. W. Lin, S. Liu, Y. Matsushita, and T. Ng. Smoothly varying affine stitching. CVPR, 2011. H. Liu, L. J. Latecki, and S. Yan. Fast detection of dense
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25] subgraph with iterative shrinking and expansion. TPAMI, 2013. D. G. Lowe. Object recognition from local scale-invariant features. ICCV, 1999. J. Maciel and J. Costeira. A global solution to sparse correspondence problems. TPAMI, 25(2): 187–199, 2003. J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust wide baseline stereo from maximally stable extremal regions. BMVC, 2002. K. Mikolajczyk and C. Schmid. Scale and affine invariant interest point detectors. IJCV, 2004. Y. A. Sheikh, E. A. Khan, and T. Kanade. Mode-seeking by medoid shifts. ICCV, 2007. L. Torresani, V. Kolmogorov, and C. Rother. Feature correspondence via graph matching: Models and global optimization. ECCV, 2008. R. Zass and A. Shashua. Probabilistic graph and hypergraph matching. CVPR, 2008. W. Zhang, X. Wang, D. Zhao, and X. Tang. Graph degree linkage: agglomerative clustering on a directed graph. ECCV, 2012. 334432 14