Team for Research in
Ubiquitous Secure Technology

Citation
Kristen Grauman, trevor darrell. "Pyramid Match Hashing: Sub-Linear Time Indexing Over Partial Correspondences". Proc. CVPR 2007, IEEE CS Press, June, 2007.

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 sublinear 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 +
)-approximate nearest neighbor images in O(N1/(1+
)) 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.

Electronic downloads

• grauman_darrell_cvpr2007.pdf · application/pdf · 299 kbytes

• HTML

  Kristen Grauman, trevor darrell. <a
  href="http://www.truststc.org/pubs/275.html"
  >Pyramid Match Hashing: Sub-Linear Time Indexing Over
  Partial Correspondences</a>, Proc. CVPR 2007, IEEE CS
  Press, June, 2007.

• Plain text

  Kristen Grauman, trevor darrell. "Pyramid Match
  Hashing: Sub-Linear Time Indexing Over Partial
  Correspondences". Proc. CVPR 2007, IEEE CS Press, June,
  2007.

• BibTeX

  @inproceedings{Graumandarrell07_PyramidMatchHashingSubLinearTimeIndexingOverPartial,
      author = {Kristen Grauman and trevor darrell},
      title = {Pyramid Match Hashing: Sub-Linear Time Indexing
                Over Partial Correspondences},
      booktitle = {Proc. CVPR 2007},
      organization = {IEEE CS Press},
      month = {June},
      year = {2007},
      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
                sublinear 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 +
                
  )-approximate nearest neighbor images in
                O(N1/(1+
  )) 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.},
      URL = {http://www.truststc.org/pubs/275.html}
  }
  

Posted by trevor darrell on 30 Jul 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.