Vocabulary-based hashing for image search

ABSTRACT

This paper proposes a hash function family based on feature vocabularies and investigates the application in building indexes for image search. Each hash function is associated with a set of feature points, i.e. a vocabulary, and maps an input point to the ID of the nearest one in the vocabulary. The function family can be employed to build a high-dimensional index for approximate nearest neighbor search. Then we concentrate on its application in image search. Guiding rules for the construction of the vocabularies are derived, which improve the effectiveness of the approach in this context by taking advantage of the data distribution. The rules are applied to design an algorithm for vocabulary construction in practice. Experiments show promising performance of the approach and the effectiveness of the guiding rules. Comparison with the popular Euclidean locality-sensitive hashing also shows the advantage of our approach in image search.

REFERENCES

• 1: S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM, 1998.
• 2: M. Casey and M. Slaney. Song intersection by approximate nearest neighbour search. In ISMIR, 2006.
• 3: M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In SCG, 2004.
• 4: H. Jegou, M. Douze, and C. Schmid. Hamming embedding and weak geometric consistency for large scale image search. In ECCV, 2008.
• 5: A. Joly and O. Buisson. A posteriori multi-probe locality sensitive hashing. In MM, 2008.
• 6: Y. Ke, R. Sukthankar, and L. Huston. Efficient near-duplicate detection and sub-image retrieval. In MM, 2004.
• 7: D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 2004.
• 8: D. Nister and H. Stewenius. Scalable recognition with a vocabulary tree. In CVPR, 2006.
• 9: S. Poullot, O. Buisson, and M. Crucianu. Z-grid-based probabilistic retrieval for scaling up content-based copy detection. In CIVR, 2007.
• 10: J. Sivic and A. Zisserman. Video Google: A text retrieval approach to object matching in videos. In ICCV, 2003.
• 11: H. Yang, Q. Wang, and Z. He. Randomized sub-vectors hashing for high-dimensional image feature matching. In MM, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.9 Applications

General Terms:
Algorithms, Design

Keywords:
hashing index, image search, visual vocabulary