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

• Orginal Article • Previous Articles     Next Articles

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

RICH HTML

4   

PDF (PC)

324

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

CLC Number: 

  • 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] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] HE Lei,ZONG Chang-fu,TIAN Cheng-wei,WU Ren-jun,Zhang Tai-wu. DC motor fault diagnosis and fault tolerance control method for steer-by-wire car[J]. 吉林大学学报(工学版), 2011, 41(03): 608 -612 .
[2] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[3] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[4] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[5] ZHU Jian-feng, LIN Yi, CHEN Xiao-kai, SHI Guo-biao. Structural topology optimization based design of automotive transmission housing structure[J]. 吉林大学学报(工学版), 2013, 43(03): 584 -589 .
[6] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[7] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[8] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[9] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[10] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd