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

doi:10.13229/j.cnki.jdxbgxb20170299

摘要/Abstract

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

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

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

杨东升, 张展, 廉梦佳, 王丽娜. 位图局部敏感哈希的匹配二进制特征搜索算法[J]. 吉林大学学报(工学版), 2018, 48(3): 893-902.

YANG Dong-sheng, ZHANG Zhan, LIAN Meng-jia, WANG Li-na. Matching binary feature search algorithm of bitmap locality sensitive hashing[J]. 吉林大学学报(工学版), 2018, 48(3): 893-902.

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed