吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (1): 218-226.doi: 10.13229/j.cnki.jdxbgxb201701032

• 论文 • 上一篇    下一篇

熵 选 择 多 重 二 进 制 编 码

赵宏伟1, 2, 王振1, 杨文迪3, 刘萍萍1, 2   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.吉林大学 符号计算与知识工程教育部重点实验室,长春 130012;
    3.华东师范大学 计算机科学与软件工程学院,上海 200062
  • 收稿日期:2015-11-16 出版日期:2017-01-20 发布日期:2017-01-20
  • 通讯作者: 刘萍萍(1979-),女,副教授,博士.研究方向:计算机视觉.E-mail:liupp@jlu.edu.cn
  • 作者简介:赵宏伟(1962-),男,教授,博士生导师.研究方向:计算机视觉.E-mail:zhaohw@jlu.edu.cn
  • 基金资助:
    国家自然科学基金项目(61101155); 吉林省自然科学基金项目(20140101184JC,20150520063JH); 吉林大学研究生创新基金项目(2015051).

Multiple binary codes based on entropy selection

ZHAO Hong-wei1, 2, WANG Zhen1, YANG Wen-di3, LIU Ping-ping1, 2   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University,Changchun 130012, China;
    3.School of Computer Science and Software Engineering, East China Normal University,Shanghai 200062,China
  • Received:2015-11-16 Online:2017-01-20 Published:2017-01-20

RICH HTML

0   

PDF (PC)

322

摘要： 为了解决查询高维浮点型数据的近邻点需要计算代价昂贵的欧式距离,内存占用率较高的问题,将高维浮点型数据通过哈希映射函数映射为低维二进制编码,并保证同一样本点在两种空间内的归一化距离满足相似性。从而在实现近邻检索任务时,可使用代价较低的汉明距离替换欧式距离,达到降低检索复杂度的目的。为保证由哈希函数生成的二进制编码具有较优的近邻检索性能,本文首先基于查找机制得到数据集适应空间分布特性的二进制标签,然后利用SVM算法得到二进制标签的分类平面,并选择其中具有最大熵值的平面函数作为最终的哈希映射函数。为了进一步提高近邻检索性能,在训练阶段,初始化多种不同的编码中心点用以生成多重二进制标签,并得到与此相应的多重哈希函数和多重二进制编码。在检索过程中,建立了基于多重二进制编码的近邻检索体系,返回具有较小平均汉明距离的样本点作为最终检索结果。实验结果表明:与其他现存优秀算法相比,本文算法可以快速、有效地将浮点型数据转化为二进制编码,而且基于这些二进制编码的近邻检索性能较优。

关键词: 计算机应用, 近邻检索, 二进制特征, 哈希编码, 熵

Abstract: Searching for Approximate Nearest Neighbors (ANN) of high dimensional floating point data has to compute their expensive Euclidean distances, and the memory occupancy rate is high. In order to fix such problem, an algorithm is proposed to effectively and efficiently map high dimensional floating point data into low dimensional binary codes, while preserving the normalized distance similarity. As a result, Hamming distances can be used to instead the Euclidean distances during ANN search process. To guarantee the ANN search performance of obtained binary codes, the distribution adaptive binary labels of the training data are firstly acquired based on the look-up mechanism. Then, the classifaction planes are obtained on the basis of SVM algorithm, and the one with the highest entropy value is chosen as the final hashing function. In order to further improve the retrieval performance, the retrieval system based on multiple binary codes is proposed. During the training process, different kinds of original encoding centers are chosen to obtain multiple hashing functions and multiple binary codes. During the search stage, the points with the minimal average Hamming distances are returned as query results. Experiments show that the proposed algorithm can efficiently and effectively map the floating point data into superior binary codes, and has excellent ANN search performance when compared with other state-of-art methods.

Key words: computer application, approximate nearest neighbor search, binary codes, Hashing algorithm, entropy

中图分类号: 

  • TP391.41
[1] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.
[2] Oliva A, Torralba A. Modeling the shape of the scene: a holistic representation of the spatial envelope[J]. International Journal of Computer Vision, 2001, 42(3): 145-175.
[3] Wang Jun, Kumar S, Chang S F. Semi-supervised hashing for scalable image retrieval[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition(CVPR),San Francisco,Ca,USA,2010:3424-3431.
[4] Weiss Y, Fergus R, Torralba A. Multidimensional Spectral Hashing[M]. Berlin Heidelberg, Springer, 2012: 340-353.
[5] Weiss Y, Torralba A, Fergus R. Spectral hashing[C]∥Proceedings of the Advances in Neural Information Processing Systems, Vancouver,British Columbia,Canada,2008:1753-1760.
[6] Liu Wei, Wang Jun, Ji Rong-rong, et al. Supervised Hashing with kernels[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Rhode Island, 2012: 2074-2081.
[7] Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality[C]∥Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, Texas, 1998: 604-613.
[8] Gong Y C, 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.
[9] MacQueen J. Some methods for classification and analysis of multivariate observations[C]∥Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, California, 1967: 281-297.
[10] He Kai-ming, Wen Fang, Sun Jian. K -means hashing: an affinity-preserving quantization method for learning binary compact codes[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Portland, Oregon, 2013: 2938-2945.
[11] Jegou H, Douze M, Schmid C, et al. Aggregating local descriptors into a compact image representation[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, 2010: 3304-3311.
[12] Jegou H, Douze M, Schmid C. Product quantization for nearest neighbor search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(1): 117-128.
[13] Ge Tie-zheng, He Kai-ming, Ke Qi-fa, et al. Optimized product quantization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(4): 744-755.
[14] Gong Yun-chao, Lazebnik S. Iterative quantization: a procrustean approach to learning binary codes[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Colorado Springs, 2011: 817-824.
[15] Wang Jian-feng, Wang Jing-dong, Yu Neng-hai, et al. Order preserving hashing for approximate nearest neighbor search[C]∥Proceedings of the 21st ACM International Conference on Multimedia, Barcelona, Spain, 2013: 133-142.
[16] Salakhutdinov R, Hinton G. Semantic hashing[J]. International Journal of Approximate Reasoning, 2009, 50(7): 969-978.
[17] Norouzi M, Blei D M. Minimal loss hashing for compact binary codes[C]∥Proceedings of the 28th International Conference on Machine Learning (ICML), Bellevue, Washington, 2011: 353-360.
[18] Norouzi M, Blei D M, Salakhutdinov R. Hamming distance metric learning[C]∥Proceedings of the Advances in Neural Information Processing Systems, South Lake Tahoe, Nevada, 2012: 1061-1069.
[19] Wang Jun, Liu Wei, Sun A X, et al. Learning hash codes with listwise supervision[C]∥Proceedings of the Computer Vision (ICCV), Sydney, Australia, 2013: 3032-3039.
[20] Zhang Dell, Wang Jun, Cal Deng, et al. Self-taught hashing for fast similarity search[C]∥Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval, Geneva, Switzerland, 2010: 18-25.
[21] Zhu Xiao-feng, Huang Zi, Cheng Hong, et al. Sparse hashing for fast multimedia search[J]. ACM Transactions on Information Systems (TOIS), 2013, 31(2):9.1-9.24.
[22] Lin Guo-sheng, Shen Chun-hua, Suter D, et al. A general two-step approach to learning-based hashing[C]∥Proceedings of the IEEE International Conference on Computer Vision (ICCV), Sydney, Australia, 2013: 2552-2559.
[23] Russell B C, Torralba A, Murphy K P, et al. LabelMe: a database and web-based tool for image annotation[J]. International Journal of Computer Vision, 2008, 77(1-3): 157-173.
[24] Krizhevsky A, Hinton G. Learning multiple layers of features from tiny images[R]. Toronto,2009.
[25] Vedaldi A, Fulkerson B. VLFeat: an open and portable library of computer vision algorithms[C]∥Proceedings of the International Conference on Multimedia, Firenze, Italy, 2010: 1469-1472.
[26] Philbin J, Chum O, Isard M, et al. Object retrieval with large vocabularies and fast spatial matching[C]∥Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR), Minneapolis, Minnesota, 2007: 1-8.
[27] Liu Wei, Wang Jun, Kumar S, et al. Hashing with graphs[C]∥Proceedings of the International Conference on Machine Learning (ICML-11), Bellevue, Washington, 2011: 1-8.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 念腾飞, 李萍, 林梅. 冻融循环下沥青特征官能团含量与流变参数灰熵分析及微观形貌[J]. 吉林大学学报(工学版), 2018, 48(4): 1045-1054.
[12] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[13] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[14] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[15] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发