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.
- J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509--517, 1975. Google ScholarDigital Library
- 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 ScholarDigital Library
- O. Chum, M. Perdoch, and J. Matas. Geometric min-hashing: Finding a (thick) needle in a haystack. In CVPR, 2009.Google ScholarCross Ref
- 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 ScholarDigital Library
- R. A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7:179--188, 1936.Google ScholarCross Ref
- J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov. Neighbourhood components analysis. In NIPS. 2004.Google Scholar
- G. Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14(8):1771--1800, 2002. Google ScholarDigital Library
- G. Hinton and R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(5786):504--507, 2006.Google ScholarCross Ref
- E. Horster and R. Lienhart. Deep networks for image retrieval on large-scale databases. In ACM Multimedia, 2008. Google ScholarDigital Library
- 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 ScholarCross Ref
- P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Symposium on Theory of Computing, 1998. Google ScholarDigital Library
- H. Jegou, M. Douze, and C. Schmid. Packing bag-of-features. In CVPR, 2009.Google ScholarCross Ref
- H. Jegou, M. Douze, and C. Schmid. Improving bag-of-features for large scale image search. IJCV, 87:191--212, 2010. Google ScholarDigital Library
- 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 ScholarDigital Library
- B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. In NIPS, 2009.Google ScholarDigital Library
- B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In ICCV, 2009.Google ScholarCross Ref
- N. Kumar, L. Zhang, and S. Nayar. What is a good nearest neighbors algorithm for finding similar patches in images? In ECCV, 2008. Google ScholarDigital Library
- D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91--110, 2004. Google ScholarDigital Library
- M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP, 2009.Google Scholar
- D. Nister and H. Stewenius. Scalable recognition with a vocabulary tree. In CVPR, 2006. Google ScholarDigital Library
- A. Oliva and A. Torralba. Modeling the shape of the scene: a holistic representation of the spatial envelope. IJCV, 42:145--175, 2001. Google ScholarDigital Library
- 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 ScholarDigital Library
- R. Salakhutdinov and G. Hinton. Semantic hashing. SIGIR Workshop, 2007.Google Scholar
- G. Shakhnarovich, P. Viola, and T. Darrell. Fast pose estimation with parameter-sensitive hashing. In ICCV, 2003. Google ScholarDigital Library
- J. Sivic and A. Zisserman. Video google: A text retrieval approach to object matching in videos. In ICCV, 2003. Google ScholarDigital Library
- 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 ScholarDigital Library
- J. R. Smith and S.-F. Chang. VisualSEEk: a fully automated content-based image query system. In ACM Multimedia, 1996. Google ScholarDigital Library
- 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 ScholarDigital Library
- A. Torralba, R. Fergus, and Y. Weiss. Small codes and large image databases for recognition. In CVPR, 2008.Google ScholarCross Ref
- J. Wang, S. Kumar, and S.-F. Chang. Semi-supervised hashing for scalable image retrieval. In CVPR, 2010.Google ScholarCross Ref
- J. Wang, S. Kumar, and S.-F. Chang. Sequential projection learning for hashing with compact codes. In ICML, 2010.Google ScholarDigital Library
- X.-J. Wang, L. Zhang, F. Jing, and W.-Y. Ma. Annosearch: image auto-annotation by search. In CVPR, 2006. Google ScholarDigital Library
- K. Weinberger and L. Saul. Fast solvers and efficient implementations for distance metric learning. In ICML, 2008. Google ScholarDigital Library
- Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NIPS, 2008.Google ScholarDigital Library
- 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 ScholarDigital Library
- J. Yang and A. G. Hauptmann. (Un)reliability of video concept detection. In CIVR, 2008. Google ScholarDigital Library
- J. Zobel and A. Moffat. Inverted files for text search engines. ACM Computing Surveys, 38(2), 2006. Google ScholarDigital Library
Index Terms
Lost in binarization: query-adaptive ranking for similar image search with compact codes
Recommendations
Binary Code Ranking with Weighted Hamming Distance
CVPR '13: Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern RecognitionBinary hashing has been widely used for efficient similarity search due to its query and storage efficiency. In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points ...
Query-Adaptive Hash Code Ranking for Fast Nearest Neighbor Search
MM '14: Proceedings of the 22nd ACM international conference on MultimediaRecently hash-based nearest neighbor search has become attractive in many applications due to its compressed storage and fast query speed. However, the quantization in the hashing process usually degenerates its discriminative power when using Hamming ...
On non-antipodal binary completely regular codes
Binary non-antipodal completely regular codes are characterized. Using a result on nonexistence of nontrivial binary perfect codes, it is concluded that there are no unknown nontrivial non-antipodal completely regular binary codes with minimum distance ...
Comments