LI Lai1,2, LIU Guang-can1,2, SUN Yu-bao1,2, LIU Qing-shan1,2
1. Jiangsu Key Laboratory of Big Data Analysis Technology, Nanjing, Jiangsu 210044, China;
2. School of Information and Control, Nanjing University of Information Science & Technology, Nanjing, Jiangsu 210044, China
Hashing is a key technique to achieve fast nearest neighbor search in high-dimensional,massive datasets.Among various methods,Iterative Quantization (ITQ) and Isotropic Hash (IsoHash) are probably the most popular ones due to their high retrieval accuracy.However,as the constraints imposed on the rotation matrix are too weak,the optimization problem in ITQ is severely under-deterministic and therefore easy to cause over-fitting.In IsoHash,the isotropic projection matrix is updated in a manner that is completely independent of the binary hash codes,and thereby the quality of the produced hash codes may be depressed.To address these issues,this paper proposes an isotropic iterative quantization hashing method,which extends the formulation of ITQ by incorporating properly the isotropic prior adopted in IsoHash.In our method,the hash code matrix and rotation matrix are updated alternately in an iterative fashion.Experiments are conducted on three benchmark datasets,CIFAR-10,22K LabelMel and ANN_GIST_1M.The results show that the proposed method performs better than the competing methods in terms of precision,recall and mAP.
[1] Arya S,Mount D M.Approximate nearest neighbor queries in fixed dimensions[A].Acm-Siam Symposium on Discrete Algorithms[C].Society for Industrial and Applied Mathematics,1996.271-280.
[2] Gionis A,Indyk P,Motwani R.Similarity search in high dimensions via Hashing[A].International Conference on Very Large Data Bases[C].Morgan Kaufmann Publishers Inc,2000.518-529.
[3] Weiss Y,Torralba A,Fergus R.Spectral Hashing[A].Advances in Neural Information Processing Systems[C].MIT,2009.1753-1760.
[4] Kulis B,Darrell T.Learning to Hash with binary reconstructive embeddings[A].Advances in Neural Information Processing Systems[C].MIT,2009.1042-1050.
[5] Kulis B,Jain P,Grauman K.Fast similarity search for learned metrics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(12):2143-2157.
[6] Weiss Y,Fergus R,Torralba A.Multidimensional spectral Hashing[A].Computer Vision-ECCV 2012[C].Berlin,Heidelberg:Springer,2012.340-353.
[7] Andoni A,Indyk P.Near-optimal Hashing algorithms for approximate nearest neighbor in high dimensions[A].47th Annual IEEE Symposium on Foundations of Computer Science[C].IEEE,2006.459-468.
[8] Norouzi M,Blei D M.Minimal loss Hashing for compact binary codes[A].Proceedings of the 28th International Conference on Machine Learning[C].ACM,2011.353-360.
[9] Xu H,Wang J,Li Z,et al.Complementary Hashing for approximate nearest neighbor search[A].2011 International Conference on Computer Vision[C].IEEE,2011.1631-1638.
[10] Chang S F.Supervised Hashing with kernels[A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE,2012.2074-2081.
[11] Liu W,Wang J,Kumar S,et al.Hashing with Graphs[A].Proceedings of the 28th International Conference on Machine Learning[C].ACM,2011.1-8.
[12] Gong Y,Lazebnik S.Iterative quantization:A procrustean approach to learning binary codes[A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE,2011.817-824.
[13] Gong Y,Lazebnik S,Gordo A,et al.Iterative quantization:A procrustean approach to learning binary codes for large-scale image retrieval[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(12):2916-2929.
[14] Heo J P,Lee Y,He J,et al.Spherical Hashing[A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE,2012.2957-2964.
[15] He K,Wen F,Sun J.K-means Hashing:An affinity-preserving quantization method for learning binary compact codes[A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE,2013.2938-2945.
[16] Broder A Z,Charikar M,Frieze A M,et al.Min-wise independent permutations[J].Journal of Computer and System Sciences,2000,60(3):630-659.
[17] Raginsky M,Lazebnik S.Locality-sensitive binary codes from shift-invariant kernels[C].Advances in Neural Information Processing Systems[C].MIT,2009.1509-1517.
[18] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive Hashing scheme based on P-stable distributions[A].Proceedings of the Twentieth Annual Symposium on Computational Geometry[C].ACM,2004.253-262.
[19] Kulis B,Grauman K.Kernelized locality-sensitive Hashing for scalable image search[A].IEEE 12th International Conference on Computer Vision[C].IEEE,2009.2130-2137.
[20] Shen F,Shen C,Liu W,et al.Supervised discrete Hashing[A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE,2015.37-45.
[21] Kong W,Li W J.Isotropic Hashing[A].Advances in Neural Information Processing Systems[C].MIT,2012.1646-1654.
[22] Xia Y,He K,Kohli P,et al.Sparse projections for high-dimensional binary codes[A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE,2015.3332-3339.
[23] Attouch H,Bolte J.On the convergence of the proximal algorithm for non-smooth functions involving analytic features[J].Mathematical Programming,2009,116(1-2):5-16.
[24] Hochba D S.Approximation algorithms for NP-Hard problems[J].ACM SIGACT News,1997,28(2):40-52.
[25] Chu M T.Constructing a Hermitian matrix from its diagonal entries and eigenvalues[J].Siam Journal on Matrix Analysis & Applications,1995,16(1):207-217.
[26] Gower J C,Dijksterhuis G B.Procrustes problems[J].Oxford Statistical Science,2004,168(2):233.
[27] Wang J,Kumar S,Chang S F.Sequential projection learning for Hashing with compact codes[A].Proceedings of 27th International Conference on Machine Learning[C].ACM,2010.1127-1134.
[28] Krizhevsky A,Hinton G.Learning Multiple Layers of Features from Tiny Images[R].University of Toronto,2009.
[29] Torralba A,Fergus R,Weiss Y.Small codes and large image databases for recognition[A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE,2008.1-8.
[30] Yuan Y,Lu X,Li X.Learning Hash functions using sparse reconstruction[A].Proceedings of International Conference on Internet Multimedia Computing and Service[C].ACM,2014.14.
2017, Vol. 45 
