cvpr cvpr2013 cvpr2013-109 cvpr2013-109-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Raffay Hamid, Dennis Decoste, Chih-Jen Lin
Abstract: We present a robust and efficient technique for matching dense sets of points undergoing non-rigid spatial transformations. Our main intuition is that the subset of points that can be matched with high confidence should be used to guide the matching procedure for the rest. We propose a novel algorithm that incorporates these high-confidence matches as a spatial prior to learn a discriminative subspace that simultaneously encodes both the feature similarity as well as their spatial arrangement. Conventional subspace learning usually requires spectral decomposition of the pair-wise distance matrix across the point-sets, which can become inefficient even for moderately sized problems. To this end, we propose the use of random projections for approximate subspace learning, which can provide significant time improvements at the cost of minimal precision loss. This efficiency gain allows us to iteratively find and remove high-confidence matches from the point sets, resulting in high recall. To show the effectiveness of our approach, we present a systematic set of experiments and results for the problem of dense non-rigid image-feature matching.
[1] M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 2003. 2, 3
[2] T. Caetano, J. McAuley, L. Cheng, Q. Le, and A. Smola. Learning graph matching. PAMI, 31(6): 1048–1058, 2009. 1, 3, 7
[3] E. Candes and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? Information Theory, IEEE Transactions on, 52(12):5406–5425, 2006. 8
[4] T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. NIPS, 19:313, 2007. 1, 3
[5] E. Delponte, F. Isgr o`, F. Odone, and A. Verri. Svd-matching using sift features. Graphical models, 68(5):415–431, 2006. 7
[6] D. DeMers, G. Cottrell, et al. Non-linear dimensionality reduction. NIPS, pages 580–580, 1993. 7
[7] O. Duchenne, F. Bach, I. Kweon, and J. Ponce. A tensor-based algorithm for high-order graph matching. PAMI, 2011. 7
[8] O. Duchenne, A. Joulin, and J. Ponce. A graph-matching kernel for object categorization. In ICCV, pages 1792–1799. IEEE, 2011. 7
[9] L. Fei-Fei, R. Fergus, and P. Perona. One-shot learning of object categories. PAMI, pages 594–61 1, 2006. 6
[10] F. Glover. Maximum matching in a convex bipartite graph. Naval Research Logistics Quarterly, 14(3):313–316, 1967. 2
[11] N. Goel, G. Bebis, and A. Nefian. Face recognition experiments with random projection. In Proc. SPIE, pages 426–437, 2005. 8
[12] G. Golub and C. Reinsch. Singular value decomposition and least squares solutions. Numerische Mathematik, 14(5):403–420, 1970. 7
[13] G. Golub and C. Van Loan. Matrix computations. Johns Hopkins University Press, 1996. 5, 7
[14] N. Halko, P. Martinsson, and J. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217–288, 2011. 5
[15] R. Hartley and A. Zisserman. Multiple view geometry in computer vision, volume 2. Cambridge Univ Press, 2000. 6
[16] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV, 2005. 1, 3
[17] C. Liu, J. Yuen, A. Torralba, J. Sivic, and W. Freeman. Sift flow: Dense correspondence across different scenes. Computer Vision– ECCV 2008, pages 28–42, 2008. 6
[18] D. Lowe. Object recognition from local scale-invariant features. In Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, volume 2, pages 1150–1 157. Ieee, 1999. 6
[19] D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–1 10, 2004. 6
[20] K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. PAMI, pages 1615–1630, 2005. 6
[21] C. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. 1998. 7
[22] D. Rueckert, L. Sonoda, C. Hayes, D. Hill, M. Leach, and D. Hawkes. Nonrigid registration using free-form deformations: application to breast mr images. TMI, pages 712–721, 1999. 6
[23] G. Scott and H. Longuet-Higgins. An algorithm for associating the features of two images. Proceedings of the Royal Society of London. Series B: Biological Sciences, 244(1309):21–26, 1991. 1, 2, 3, 7
[24] L. Shapiro and J. Michael Brady. Feature-based correspondence: an eigenvector approach. ICV, pages 283–288, 1992. 7
[25] X. Shen and F. Meyer. Analysis of event-related fmri data using diffusion maps. In IPMI, pages 103–137. Springer, 2005. 8
[26] M. Torki and A. Elgammal. One-shot multi-set non-rigid featurespatial matching. In CVPR. IEEE, 2010. 1, 2, 6, 7
[27] M. Torki and A. Elgammal. Putting local features on a manifold. In CVPR, pages 1743–1750. IEEE, 2010. 1, 7
[28] L. Torresani, V. Kolmogorov, and C. Rother. Feature correspondence via graph matching: Models and global optimization. ECCV, pages 596–609, 2008. 1, 3
[29] S. Ullman. Aligning pictorial descriptions: an approach to object recognition. Cognition, 32(3): 193–254, 1989. 6
[30] S. Umeyama. An eigen decomposition approach to weighted graph matching problems. PAMI, 10(5):695–703, 1988. 1, 7 [3 1] S. Vempala. The random projection method, volume 65. Amer Mathematical Society, 2005. 2, 4, 8 222999112199