Pyramid match hashing: Sub-linear time indexing over partial correspondences

Matching local features across images is often useful when comparing or recognizing objects or scenes, and ef-ficient techniques for obtaining image-to-image correspon-dences have been developed [6, 4, 11]. 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 re-sult is a bounded approximate similarity search algorithm that finds (1 + )-approximate nearest neighbor images in O(N1/(1+)) time for a database containing N images rep-resented by (varying numbers of) local features. By design the indexing is robust to outlier features, as it favors strong one-to-one matchings but does not penalize for additional distant features. We demonstrate our approach applied to image retrieval for images represented by sets of local ap-pearance features, and show that searching over correspon-dences is now scalable to large image databases. 1