nips nips2006 nips2006-34 nips2006-34-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Kristen Grauman, Trevor Darrell
Abstract: Pyramid intersection is an efficient method for computing an approximate partial matching between two sets of feature vectors. We introduce a novel pyramid embedding based on a hierarchy of non-uniformly shaped bins that takes advantage of the underlying structure of the feature space and remains accurate even for sets with high-dimensional feature vectors. The matching similarity is computed in linear time and forms a Mercer kernel. Whereas previous matching approximation algorithms suffer from distortion factors that increase linearly with the feature dimension, we demonstrate that our approach can maintain constant accuracy even as the feature dimension increases. When used as a kernel in a discriminative classifier, our approach achieves improved object recognition results over a state-of-the-art set kernel. 1
[1] P. Agarwal and K. R. Varadarajan. A Near-Linear Algorithm for Euclidean Bipartite Matching. In Symposium on Computational Geometry, 2004.
[2] S. Belongie, J. Malik, and J. Puzicha. Shape Matching and Object Recognition Using Shape Contexts. IEEE Trans. on Pattern Analysis and Machine Intelligence, 24(24):509–522, April 2002.
[3] A. Berg, T. Berg, and J. Malik. Shape Matching and Object Recognition using Low Distortion Correspondences. In Proc. IEEE Conf. on Comp. Vision and Pattern Recognition, San Diego, CA, June 2005.
[4] M. Charikar. Similarity Estimation Techniques from Rounding Algorithms. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002.
[5] A. Gersho and R. Gray. Vector Quantization and Signal Compression. Springer, 1992.
[6] K. Grauman. Matching Sets of Features for Efficient Retrieval and Recognition. PhD thesis, MIT, 2006.
[7] K. Grauman and T. Darrell. The Pyramid Match Kernel: Discriminative Classification with Sets of Image Features. In Proc. IEEE Int. Conf. on Computer Vision, Beijing, China, Oct 2005.
[8] P. Indyk and N. Thaper. Fast Image Retrieval via Embeddings. In 3rd International Workshop on Statistical and Computational Theories of Vision, Nice, France, Oct 2003.
[9] T. K. Landauer, P. W. Foltz, and D. Laham. Introduction to LSA. Discourse Processes, 25:259–84, 1998.
[10] S. Lazebnik, C. Schmid, and J. Ponce. Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Scene Categories. In Proc. IEEE Conf. on Comp. Vision and Pattern Recognition, June 2006.
[11] D. Lowe. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 60(2):91–110, Jan 2004.
[12] J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust Wide Baseline Stereo from Maximally Stable Extremal Regions. In British Machine Vision Conference, Cardiff, UK, Sept. 2002.
[13] D. Nister and H. Stewenius. Scalable Recognition with a Vocabulary Tree. In Proc. IEEE Conf. on Comp. Vision and Pattern Recognition, New York City, NY, June 2006.
[14] F. Odone, A. Barla, and A. Verri. Building Kernels from Binary Strings for Image Matching. IEEE Trans. on Image Processing, 14(2):169–180, Feb 2005.
[15] J. Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge Univ. Press, 2004.
[16] J. Sivic and A. Zisserman. Video Google: A Text Retrieval Approach to Object Matching in Videos. In Proc. IEEE Int. Conf. on Computer Vision, Nice, Oct 2003.