Pyramid Match Hashing: Sub-Linear Time Indexing Over Partial Correspondences
- 1 June 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Matching local features across images is often useful when comparing or recognizing objects or scenes, and efficient techniques for obtaining image-to-image correspondences have been developed [4, 11, 16]. However, given a query image, searching a very large image database with such measures remains impractical. We introduce a sub-linear time randomized hashing algorithm for indexing sets of feature vectors under their partial correspondences. We develop an efficient embedding function for the normalized partial matching similarity between sets, and show how to exploit random hyperplane properties to construct hash functions that satisfy locality-sensitive constraints. The result is a bounded approximate similarity search algorithm that finds (1 + epsiv)-approximate nearest neighbor images in O(N1/1+epsiv) time for a database containing N images represented by (varying numbers of) local features. We demonstrate our approach applied to image retrieval for images represented by sets of local appearance features, and show that searching over correspondences is now scalable to large image databases.Keywords
This publication has 18 references indexed in Scilit:
- Scalable Recognition with a Vocabulary TreePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene CategoriesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Randomized Trees for Real-Time Keypoint RecognitionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- The pyramid match kernel: discriminative classification with sets of image featuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Sub-linear Indexing for Large Scale Object RecognitionPublished by British Machine Vision Association and Society for Pattern Recognition ,2005
- A spectral technique for correspondence problems using pairwise constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Fast pose estimation with parameter-sensitive hashingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Shape matching and object recognition using shape contextsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximate nearest neighborsPublished by Association for Computing Machinery (ACM) ,1998