skip to main content
10.1145/1991996.1992012acmconferencesArticle/Chapter ViewAbstractPublication PagesicmrConference Proceedingsconference-collections
research-article

Lost in binarization: query-adaptive ranking for similar image search with compact codes

Published:18 April 2011Publication History

ABSTRACT

With the proliferation of images on the Web, fast search of visually similar images has attracted significant attention. State-of-the-art techniques often embed high-dimensional visual features into low-dimensional Hamming space, where search can be performed in real-time based on Hamming distance of compact binary codes. Unlike traditional metrics (e.g., Euclidean) of raw image features that produce continuous distance, the Hamming distances are discrete integer values. In practice, there are often a large number of images sharing equal Hamming distances to a query, resulting in a critical issue for image search where ranking is very important. In this paper, we propose a novel approach that facilitates query-adaptive ranking for the images with equal Hamming distance. We achieve this goal by firstly offline learning bit weights of the binary codes for a diverse set of predefined semantic concept classes. The weight learning process is formulated as a quadratic programming problem that minimizes intra-class distance while preserving interclass relationship in the original raw image feature space. Query-adaptive weights are then rapidly computed by evaluating the proximity between a query and the concept categories. With the adaptive bit weights, the returned images can be ordered by weighted Hamming distance at a finer-grained binary code level rather than at the original integer Hamming distance level. Experimental results on a Flickr image dataset show clear improvements from our query-adaptive ranking approach.

References

  1. J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509--517, 1975. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. T.-S. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y.-T. Zheng. NUSWIDE: A real-world web image database from national university of singapore. In CIVR, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. O. Chum, M. Perdoch, and J. Matas. Geometric min-hashing: Finding a (thick) needle in a haystack. In CVPR, 2009.Google ScholarGoogle ScholarCross RefCross Ref
  4. R. Datta, D. Joshi, J. Li, and J. Z. Wang. Image retrieval: ideas, influences, and trends of the new age. ACM Computing Surveys, 40(2), 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. R. A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7:179--188, 1936.Google ScholarGoogle ScholarCross RefCross Ref
  6. J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov. Neighbourhood components analysis. In NIPS. 2004.Google ScholarGoogle Scholar
  7. G. Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14(8):1771--1800, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. G. Hinton and R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(5786):504--507, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  9. E. Horster and R. Lienhart. Deep networks for image retrieval on large-scale databases. In ACM Multimedia, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. P. Indyk. Nearest neighbors in high-dimensional spaces. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 39. CRC press, 2004.Google ScholarGoogle ScholarCross RefCross Ref
  11. P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Symposium on Theory of Computing, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. H. Jegou, M. Douze, and C. Schmid. Packing bag-of-features. In CVPR, 2009.Google ScholarGoogle ScholarCross RefCross Ref
  13. H. Jegou, M. Douze, and C. Schmid. Improving bag-of-features for large scale image search. IJCV, 87:191--212, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Y. G. Jiang, C. W. Ngo, and J. Yang. Towards optimal bag-of-features for object categorization and semantic video retrieval. In CIVR, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. In NIPS, 2009.Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In ICCV, 2009.Google ScholarGoogle ScholarCross RefCross Ref
  17. N. Kumar, L. Zhang, and S. Nayar. What is a good nearest neighbors algorithm for finding similar patches in images? In ECCV, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91--110, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP, 2009.Google ScholarGoogle Scholar
  20. D. Nister and H. Stewenius. Scalable recognition with a vocabulary tree. In CVPR, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. A. Oliva and A. Torralba. Modeling the shape of the scene: a holistic representation of the spatial envelope. IJCV, 42:145--175, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. T. Quack, U. Monich, L. Thiele, and B. Manjunath. Cortina: A system for large-scale, content-based web image retrieval. In ACM Multimedia, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. R. Salakhutdinov and G. Hinton. Semantic hashing. SIGIR Workshop, 2007.Google ScholarGoogle Scholar
  24. G. Shakhnarovich, P. Viola, and T. Darrell. Fast pose estimation with parameter-sensitive hashing. In ICCV, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. J. Sivic and A. Zisserman. Video google: A text retrieval approach to object matching in videos. In ICCV, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. A. W. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain. Content-based image retrieval at the end of the early years. PAMI, 22(12):1349--1380, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. J. R. Smith and S.-F. Chang. VisualSEEk: a fully automated content-based image query system. In ACM Multimedia, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. A. Torralba, R. Fergus, and W. Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. PAMI, 30(11):1958--1970, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. A. Torralba, R. Fergus, and Y. Weiss. Small codes and large image databases for recognition. In CVPR, 2008.Google ScholarGoogle ScholarCross RefCross Ref
  30. J. Wang, S. Kumar, and S.-F. Chang. Semi-supervised hashing for scalable image retrieval. In CVPR, 2010.Google ScholarGoogle ScholarCross RefCross Ref
  31. J. Wang, S. Kumar, and S.-F. Chang. Sequential projection learning for hashing with compact codes. In ICML, 2010.Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. X.-J. Wang, L. Zhang, F. Jing, and W.-Y. Ma. Annosearch: image auto-annotation by search. In CVPR, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. K. Weinberger and L. Saul. Fast solvers and efficient implementations for distance metric learning. In ICML, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NIPS, 2008.Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning with application to clustering with side-information. NIPS, pages 521--528, 2003.Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. J. Yang and A. G. Hauptmann. (Un)reliability of video concept detection. In CIVR, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. J. Zobel and A. Moffat. Inverted files for text search engines. ACM Computing Surveys, 38(2), 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Lost in binarization: query-adaptive ranking for similar image search with compact codes

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      ICMR '11: Proceedings of the 1st ACM International Conference on Multimedia Retrieval
      April 2011
      512 pages
      ISBN:9781450303361
      DOI:10.1145/1991996

      Copyright © 2011 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 18 April 2011

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate254of830submissions,31%

      Upcoming Conference

      ICMR '24
      International Conference on Multimedia Retrieval
      June 10 - 14, 2024
      Phuket , Thailand

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader