基于多哈希算法的大规模图像快速检索方法

J4 ›› 2016, Vol. 38 ›› Issue (07): 1316-1321.

基于多哈希算法的大规模图像快速检索方法

唐小蔓1，王云飞1，邹复好1，周可2

(1.华中科技大学计算机科学与技术学院，湖北武汉 430074;
2.华中科技大学武汉光电国家实验室，湖北武汉 430074）

收稿日期:2015-12-05 修回日期:2016-03-06 出版日期:2016-07-25 发布日期:2016-07-25
基金资助:
国家自然科学基金重点资助项目（61232004）；国家973计划（2011CB302305）

A fast retrieval method for large scale images
based on multiple Hash algorithms

TANG Xiaoman1,WANG Yunfei1,ZOU Fuhao1,ZHOU Ke2

(1.School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074;
2.Wuhan National Laboratory for Optoelectronics,Huazhong University of Science and Technology,Wuhan 430074,China)

Received:2015-12-05 Revised:2016-03-06 Online:2016-07-25 Published:2016-07-25

摘要/Abstract

摘要：

哈希技术被视为最有潜力的相似性搜索方法，其可以用于大规模多媒体数据搜索场合。为了解决在大规模图像情况下，数据检索效率低下的问题，提出了一种基于分段哈希码的倒排索引树结构，该索引结构将哈希码进行分段处理，对每段哈希码维护一个倒排索引树结构，并结合高效的布隆过滤器构建哈希索引结构。为了进一步提高检索准确性，设计了一种准确的排序融合算法，对多个哈希算法的排序结果分别构建加权无向图，采用PageRank的思想对基于多个哈希算法的排序列表的融合技术进行了详细的说明。实验结果表明，基于分段哈希码的倒排索引树结构能极大地提升数据的检索速度。此外，相比于传统的单个哈希算法排序技术，基于多个哈希算法的排序列表融合技术的检索准确率优势显著。

关键词: 相似性搜索；哈希算法；倒排索引树；排序融合算法

Abstract:

Hash technique is regarded as the most promising method of similarity search, which can be used in large scale multimedia data search. In order to solve the problem of low efficiency of data retrieval over large scale images, we propose a reverse index tree structure based on segmental Hash codes, and elaborate its implementation principles. In this structure, Hash codes are segmented. We design an inverted tree index structure for each section of Hash codes, and build the Hash index structure with the combination of the bloom filters. To further improve the accuracy of the retrieval results, we design a fusing algorithm which constructs the weighted undirected graph separately for the ranking results of multiple Hash algorithms. The fusion algorithm of the sorting list based on multiple Hash algorithms is described in detail by PageRank. Experimental results show that the structure of the inverted index tree based on segmental Hash codes can greatly improve data retrieval speed. Compared with the conventional single Hash algorithm sorting technique, the rank fusion technique for ordered lists of multiple Hash algorithms has obvious superiority in retrieval accuracy.

唐小蔓1，王云飞1，邹复好1，周可2. 基于多哈希算法的大规模图像快速检索方法[J]. J4, 2016, 38(07): 1316-1321.

TANG Xiaoman1,WANG Yunfei1,ZOU Fuhao1,ZHOU Ke2. A fast retrieval method for large scale images
based on multiple Hash algorithms [J]. J4, 2016, 38(07): 1316-1321.

参考文献［12］

［1］	Kulis B,Grauman K.Kernelized localitysensitive hashing for scalable image search［C］∥Proc of the 12th IEEE International Conference on Computer Vision,2009:21302137.
［2］	Datar M,Immorlica N,Indyk P,et al.Localitysensitive hashing scheme based on pstable distributions［C］∥Proc of the 20th Annual Symposium on Computational Geometry,2004:253262.
［3］	Indyk P, Motwani R. Approximate nearest neighbors:Towards removing the curse of dimensionality［C］∥Proc of the 30th Annual ACM Symposium on Theory of Computing,1998:604613.
［4］	Andoni A,Indyk P.Nearoptimal hashing algorithms for approximate nearest neighbor in high dimensions［C］∥Proc of the 47th Annual IEEE Symposium on Foundations of Computer Science,2006:459468.
［5］	Mihcak M K,Venkatesan R.New iterative geometric methods for robust perceptual image hashing［C］∥Proc of the Security and Privacy in Digital Rights Management,2002:1321.
［6］	Weiss Y,Torralba A,Fergus R.Spectral hashing［C］∥Proc of the Advances in Neural Information Processing Systems,2009:17531760.
［7］	Panigrahy R.Entropy based nearest neighbor search in high dimensions［C］∥Proc of the 17th Annual ACMSIAM Symposium on Discrete Algorithm, Society for Industrial and Applied Mathematics,2006:11861195.
［8］	Zhang D,Wang Jun,Cai Deng,et al.Selftaught hashing for fast similarity search［C］∥Proc of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval,2010:1825.
［9］	Andoni A, Indyk P. E2lsh 0.1 user manual［Z］.Cambridge,Massachusetts: Massachusetts Institute of Technology,2005:123.
［10］	Liu Wei, Wang Jun, Kumar S, et al. Hashing with graphs［C］∥Proc of the 28th International Conference on Machine Learning,2011:18.
［11］	Shakhnarovich G,Viola P,Darrell T.Fast pose estimation with parametersensitive hashing［C］∥Proc of the 9th IEEE International Conference on Computer Vision,2003:750757.
［12］	Wang Yunfei. Research on similarity search based on hidden semantic hashing algorithm［D］.Wuhan:Huazhong University of Science and Technology, 2005.(in Chineses)
［13］	Lv Qin,Josephson W,Wang Zhe,et al.Multiprobe lsh:Efficient indexing for highdimensional similarity search［C］∥Proc of the 33rd International Conference on Very Large Data Bases,2007:950961.
［14］	Brin S, Page L. The anatomy of a largescale hypertextual Web search engine［J］.Computer Networks and ISDN Systems,1998,30(1):107117.
［15］	Zobel J,Moffat A.Inverted files for text search engines［J］.ACM Computing Surveys (CSUR),2006,38(2):6.
［16］	Bayer R.Symmetric binary Btrees:Data structure and maintenance algorithms［J］.Acta Informatica,1972,1(4):290306.
［17］	Bloom B H. Space/time tradeoffs in hash coding with allowable errors［J］.Communications of the ACM,1970,13(7):422426.
［18］	Jing Y,Baluja S.Visualrank:Applying pagerank to largescale image search［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(11):18771890.
［19］	Page L, Brin S, Motwani R, et al. The pagerank citation ranking:Bringing order to the web［C］∥Proc of the 7th International World Wide Web Conference, 1998:161172.
	附中文参考文献：
［12］	王云飞.基于隐含语义哈希算法的相似性搜索研究［D］.武汉：华中科技大学,2015.
	作者简介:唐小蔓(1992),男，湖北安陆人，硕士生，研究方向为计算机视觉与机器学习。