吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (3): 893-902.doi: 10.13229/j.cnki.jdxbgxb20170299

• 论文 • 上一篇    下一篇

位图局部敏感哈希的匹配二进制特征搜索算法

杨东升1, 张展1,2, 廉梦佳1,2, 王丽娜1,2   

  1. 1.中国科学院 沈阳计算技术研究所,沈阳 110168;
    2.中国科学院大学,北京 100049;
  • 收稿日期:2017-03-30 出版日期:2018-05-20 发布日期:2018-05-20
  • 作者简介:杨东升(1965-),男,研究员,博士生导师.研究方向:数控技术,机器人视觉.E-mail:dsyang@sict.ac.cn
  • 基金资助:
    “核高基”国家科技重大专项项目(2017ZX01030-201).

Matching binary feature search algorithm of bitmap locality sensitive hashing

YANG Dong-sheng1, ZHANG Zhan1,2, LIAN Meng-jia1,2, WANG Li-na1,2   

  1. 1.Shenyang Institute of Computing Technology, Chinese Academy of Science, Shenyang 110168,China;
    2.University of Chinese Academy of Science, Beijing 100049,China
  • Received:2017-03-30 Online:2018-05-20 Published:2018-05-20

摘要: 针对现有匹配二进制特征搜索算法效率低和入围点少的问题,提出了快速计算位图算法和位图局部敏感哈希算法。首先,计算左图提取的二进制特征的位向量;然后,使用快速计算位图算法计算位向量的位图,将位图作为关键字,并与二进制特征的标识作为映射,构建局部敏感哈希表;接着,将哈希表中的关键字存入位集;最后,判断右图提取的二进制特征对应的位图是否存在于哈希表中,优化查询哈希表中的匹配二进制特征,提高匹配二进制特征的搜索效率和质量。实验证明:位图局部敏感哈希算法提高了二进制特征近邻搜索的效率、增加了入围点数。

关键词: 计算机应用, 位图, 局部敏感哈希, 二进制特征, 图像匹配, 汉明距离

Abstract: To solve the issues of low efficiency and less inliers of existing matching binary feature search algorithms, a Fast Calculating Bit Map algorithm (FCBM) and a Bit Map Locality Sensitive Hashing algorithm (BMLSH) are proposed. First, the bit vectors of the binary features extracted from left image is calculated and the FCBM is used to calculate bitmap of each bit vector. Second, the bitmaps of the bit vectors are taken as the key words, and each keyword and its corresponding binary feature identifier are used to construct local sensitive hash table, then the maps are stored in the hash table. Furthermore, the keywords in the hash table are stored in the bit set. Finally, the bit set is used to judge whether the bitmaps of right image binary feature exists or not in the hash table, and the query of matching binary features are optimized to improve the search efficiency and quality. Experiments show that the proposed BMLSH can improve the search efficiency and increase the number of inlier points.

Key words: computer application, bitmap, locality sensitive hashing, binary feature, image matching, hamming distance

中图分类号: 

  • TP391
[1] Lowe D G.Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision,2004,60(2):91-110.
[2] 聂海涛,龙科慧,马军,等. 基于快速SIFT算法和模糊控制的人脸识别[J]. 吉林大学学报:工学版,2016,46(2):549-555.
Nie Hai-tao,Long Ke-hui,Ma Jun,et al.Face recognition based on fast scale invariant feature algorithm and fuzzy control[J]. Journal of Jilin University (Engineering and Technology Edition),2016,46(2):549-555.
[3] Bay H,Ess A,Tuytelaars T,et al.Speeded-up robust features (surf)[J]. Computer Vision and Image Understanding,2008,110(3):346-359.
[4] 郭清达,全燕鸣,姜长城,等. 应用摄像机位姿估计的点云初始配准[J]. 光学精密工程,2017,25(6):1635-1651.
Guo Qing-da,Quan Yan-ming,Jiang Chang-cheng,et al.Initial registration of point clouds using camera pos estimation[J]. Optics and Precision Engineering,2017,25(6):1635-1651.
[5] Calonder M, Lepetit V, Strecha C,et al.BRIEF:binary robust independent elementary features[J/OL].[2017-03-22].http:∥icwww.epfl.ch/~lepetit/papers/calonder_eccv10.pdf.
[6] Rublee E, Rabaud V, Konolige K, et al.ORB:an efficient alternative to SIFT or SURF[J/OL].[2017-03-25].http:∥www.cs.zju.edu.cn/~gpan/course/materials/ORB.pdf.
[7] Leutenegger S, Chli M, Siegwart R Y.BRISK: binary robust invariant scalable keypoints[J/OL].[2017-03-23].http:∥www.robots.ox.ac.uk/~vgg/rg/papers/brisk.pdf.
[8] Alahi A, Ortiz R, Vandergheynst P.FREAK:fast retina keypoint[J/OL].[2017-03-24].https:∥infoscience.epfl.ch/record/175537/files/2069.pdf.
[9] 张展,杨东升. 圆周二进制描述符的图像点特征提取方法[J]. 计算机辅助设计与图形学学报,2017,29(8):1465-1476.
Zhang Zhan,Yang Dong-sheng.Image point feature extraction algorithm of circumferential binary descriptor[J]. Journal of Computer-Aided Design & Computer Grphics,2017,29(8):1465-1476.
[10] Richard Szeliski.计算机视觉-算法与应用[M]. 艾海舟,兴军亮译. 北京:清华大学出版社,2012:175-176.
[11] Indyk P, Motwani R.Approximate nearest neighbor: towards removing the curse of dimensionality[J/OL].[2017-03-23].http:∥www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/IndykM-curse.pdf.
[12] Lv Qin, Josephson William, Wang Zhe, et al. Multi-probe LSH: efficient indexing for high-dimensional similarity search[J/OL].[2017-03-24]. http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf.
[13] Kong Wei-hao,Li Wu-jun,Guo Min-yi.Manhattan hashing for large-scale image retrieval[C]∥Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, New York, NY, USA,2012:45-54.
[14] Shrivastave Anshumali, Li Ping.Densifying one permutation hashing via rotation for fast near neighbor search[J/OL].[2017-03-23].http:∥proceedings.mlr.press/v32/shrivastava14.pdf.
[15] Lin Guo-sheng,Shen Chun-hua,Shi Qin-fen,et al.Fast supervised hashing with decision trees for high-dimensional data[C]∥IEEE Conference on Computer Vision& Pattern Recognition, Columbus, OH, USA, 2014:1971-1978.
[16] Liong Venice Erin, Lu Ji-wen, Wang Gang, et al.Deep hashing for compact binary codes learning[J/OL]. [2017-03-23].https://www.cv-foundation.org/openaccess/content_cvpr_2015/papers/Liong_Deep_Hashing_for_2015_CVPR_paper.pdf.
[17] Lin Kevin, Yang Huei-fang, Hsiao Jen-hao, et al.Deep learning of binary hash codes for fast image retrieval[J/OL].[2017-03-22].http:∥www.iis.sinica.edu.tw/~kevinlin311.tw/cvprw15.pdf.
[18] Norouzi M, Fleet D J.Minimal loss hashing for compact binary codes[C]∥Proceedings of the 28th International Conference on Machine Learning, Bellevue, Washington, USA,2011:353-360.
[19] Norouzi M, Punjani A, Fleet D J.Fast search in hamming space with multi-index hashing[J/OL].[2017-03-25].https:∥www.cs.toronto.edu/~norouzi/research/papers/multi_index_hashing.pdf.
[20] Muja M, Lowe D G.Fast matching of binary features[C]∥2012 Ninth Conference on Computer and Robot Vision, Toronto, ON, Canada,2012:404-410.
[21] Muja M, Lowe D G.Scalable nearest neighbor algorithms for high dimensional data[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,36(11):2227-2240.
[22] Garcia-Molina H, Ullman J D, Widom J.数据库系统实现[M]. 杨冬青,吴愈青,包小源译. 2版. 北京:机械工业出版社,2010:688-693.
[23] Mikolajczyk K, Schmid C.A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis &Machine Intelligence,2005,27(10):1615-1630.
[24] 邹瑜,梁斌,王学谦,等. 基于旋转投影二进制描述符的空间目标位姿估计[J]. 光学精密工程,2017,25(11):2958-2967.
Zou Yu,Liang Bin,Wang Xue-qian,et al.Spacetarget pose estimation based on binary rotational projection histogram[J]. Optics and Precision Engineering,2017,25(11):2958-2967.
[25] 崔少辉,谢征,王刚,等. 二进制鲁棒不变尺度特征匹配电子稳像[J]. 光学精密工程,2015,23(9):2715-2723.
Cui Shao-hui,Xie Zheng,Wang Gang,et al.Feature matching electronic image stabilization based on binary robust in variant scalable keypionts[J]. Optics and Precision Engineering,2015,23(9):2715-2723.
[26] 罗家祥,林畅赫,王加朋,等.结合深度卷积网络与加速鲁棒特征配准的图像精准定位[J].光学精密工程,2017,25(2):469-476.
Luo Jia-xiang,Lin Chang-he,Wang Jia-peng,et al.Accurate image positioning combining deep convolution network with SURF registering[J]. Optics and Precision Engineering,2017,25(2):469-476.
[27] 熊昌镇,单艳梅,郭芬红.结合主体检测的图像检索方法[J].光学精密工程,2017,25(3):792-798.
Xiong Chang-zhen, Shan Yan-mei, Guo Fen-hong.Image retrieval method based on image principal part detection[J]. Optics and Precision Engineering,2017,25(3):792-798.
[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): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 何磊,宗长富,田承伟,吴仁军,张太武. 线控转向汽车直流电机的故障诊断与容错控制[J]. 吉林大学学报(工学版), 2011, 41(03): 608 -612 .
[2] 刘松山, 王庆年, 王伟华, 林鑫. 惯性质量对馈能悬架阻尼特性和幅频特性的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[3] 初亮, 王彦波, 祁富伟, 张永生. 用于制动压力精确控制的进液阀控制方法[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[4] 李静, 王子涵, 余春贤, 韩佐悦, 孙博华. 硬件在环试验台整车状态跟随控制系统设计[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[5] 朱剑峰, 林逸, 陈潇凯, 施国标. 汽车变速箱壳体结构拓扑优化设计[J]. 吉林大学学报(工学版), 2013, 43(03): 584 -589 .
[6] 胡兴军, 李腾飞, 王靖宇, 杨博, 郭鹏, 廖磊. 尾板对重型载货汽车尾部流场的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[7] 王同建, 陈晋市, 赵锋, 赵庆波, 刘昕晖, 袁华山. 全液压转向系统机液联合仿真及试验[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[8] 张春勤, 姜桂艳, 吴正言. 机动车出行者出发时间选择的影响因素[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[9] 马万经, 谢涵洲. 双停车线进口道主、预信号配时协调控制模型[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[10] 于德新, 仝倩, 杨兆升, 高鹏. 重大灾害条件下应急交通疏散时间预测模型[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .