cvpr cvpr2013 cvpr2013-63 cvpr2013-63-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lei Zhang, Yongdong Zhang, Jinhu Tang, Ke Lu, Qi Tian
Abstract: Binary 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 are approximated by the Hamming distance between their binary codes. The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. Evaluations on two large-scale image data sets demonstrate the efficacy of our weighted Hamming distance for binary code ranking.
[1] A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In IEEE Symp. Found. Comput. Sci., pages 459–468, 2006.
[2] J. L. Bentley and B. Labo. K-d trees for semidynamic point sets. In Symp. Comput. Geom., pages 187–197, 1990.
[3] Y. Gong and S. Lazebnik. Iterative quantization: a procrustean approach to learning binary codes. In Computer Vision and Pattern Recognition, pages 817–824, 2011.
[4] H. J´ egou, M. Douze, and C. Schmid. Improving bag-offeatures for large scale image search. International Journal of Computer Vision, 87:316–336, 2010.
[5] H. J ´egou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33: 117–128, 2011.
[6] J. Ji, J. Li, S. Yan, B. Zhang, and Q. Tian. Super-bit localitysensitive hashing. In NIPS, pages 108–1 16, 2012.
[7] Y. Jiang, J. Wang, and S.-F. Chang. Lost in binarization: query-adaptive ranking for similar image search with compact codes. In ICMR, page 16, 2011.
[8] B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. In NIPS, pages 1042–1050, 2009.
[9] B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In International Conference on Computer Vision, pages 2130–2137, 2009.
[10] Y. Lecun, L. E. Bottou, Y. Bengio, and P. Haffner. Gradientbased learning applied to document recognition. Proceedings of The IEEE, 86:2278–2324, 1998.
[11] W. Liu, J. Wang, R. Ji, Y. Jiang, and S.-F. Chang. Supervised
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23] hashing with kernels. In CVPR, pages 2074–2081, 2012. W. Liu, J. Wang, S. Kumar, and S.-F. Chang. Hashing with graphs. In ICML, pages 1–8, 2011. D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60:91–1 10, 2004. K. Min, L. Yang, J. Wright, L. Wu, X.-S. Hua, and Y. Ma. Compact projection: simple and efficient near neighbor search with practical memory requirements. In Computer Vision and Pattern Recognition, pages 3477–3484, 2010. L. Qin, W. Josephson, Z. Wang, M. Charikar, and K. Li. MultiProbe LSH: Efficient Indexing for High-Dimensional Similarity Search. In VLDB, pages 950–961, 2007. M. Raginsky and S. Lazebnik. Locality-sensitive binary codes from shift-invariant kernels. In Neural Information Processing Systems, pages 1509–15 17, 2009. R. Salakhutdinov and G. E. Hinton. Semantic hashing. Int. J. Approx. Reason., 50:969–978, 2009. C. Silpa-anan and R. Hartley. Optimised KD-trees for fast image descriptor matching. In CVPR, pages 1–8, 2008. J. Wang, S. Kumar, and S.-F. Chang. Sequential Projection Learning for Hashing with Compact Codes. In International Conference on Machine Learning, pages 1127–1 134, 2010. X. Wang, L. Zhang, F. Jing, and W. Ma. AnnoSearch: Image auto-annotation by search. In CVPR, 2006. Y. Weiss, A. B. Torralba, and R. Fergus. Spectral hashing. In NIPS, pages 1753–1760, 2008. L. Zhang, X. Zhang, and H.-Y. Shum. QsRank: Querysensitive hash code ranking for efficient ?-neighbor search. In CVPR, pages 2058–2065, 2012. W. Zhou, Y. Lu, H. Li, Y. Song, and Q. Tian. Spatial coding for large scale partial-duplicate web image search. In ACM Multimedia, pages 5 11–520, 2010.
[24] W. Zhou, Y. Lu, H. Li, and Q. Tian. Scalar quantization for large scale image search. In ACM Multimedia, pages 169– 178, 2012. 111555999311