一种基于最小哈希的二值特征匹配方法

doi:10.3969/j.issn.1006-2475.2016.06.016

摘要/Abstract

摘要： 特征匹配是图像识别中一个基本研究问题。常用的匹配方式一般是基于贪婪算法的线性扫描方式，但只适用于低维数据。当数据维数超过一定程度时，这些匹配方法的时间效率将会急剧下降，甚至不强于强力线性扫描方法。本文提出一种基于最小哈希的二值特征匹配方法。通过最小哈希函数映射变换操作，将原始特征集合分成多个子集合，并将一个在超大集合下内查找相邻元素的问题转化为在一个很小的集合内查找相邻元素的问题,计算量有所下降。使用Jaccard距离度量的最小哈希函数能最大限度地保证原始数据中相似的向量对在哈希变换后依然相似。实验表明这种匹配方法应用在二值特征上时，可以获得比KD-Tree更好的匹配效果。


关键词: 最小哈希, 二值特征, 特征匹配

Abstract: Feature matching is one of basic problems in image recognition. Common matching methods are the linear scanning methods based on greedy algorithm, and they are applied to low dimensional data. When data dimension exceeds a certain degree, the time efficiency of matching will decrease sharply, even not stronger than the strong linear scanning method. This paper proposes a binary feature matching method based on minimum hashing. By the mapping transformation in minimum hashing function, the original feature set will be divided into several subsets. It can be transformed into a problem of searching the adjacent elements within a tiny set instead of a huge set, which decreases the computational cost. Using Jaccard distance, minimum hashing function can maximally ensure the similarity of similar vectors in original data after hash transformation. Experiments show that this method can obtain better matching performance than KD-Tree when it is applied to binary feature.


Key words: minimum hashing, binary feature, feature matching

中图分类号:

TP391

郭倩,孙涵. 一种基于最小哈希的二值特征匹配方法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2016.06.016.

GUO Qian， SUN Han. A Binary Feature Matching Method Based on Minimum Hashing[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.06.016.

参考文献

［1］ Yang Xin, Cheng Kwang-ting. Local difference binary for ultrafast and distinctive feature description［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(1):188-194.
［2］ Calonder M, Lepetit V, Ozuysal M, et al. BRIEF: Computing a local binary descriptor very fast［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7):1281-1298.
［3］ Rublee E, Rabaud V, Konolige K, et al. ORB:An efficient alternative to SIFT or SURF［C］// Proceedings of the 2011 International Conference on Computer Vision. 2011:2564-2571.
［4］ Alahi A, Ortiz R, Vandergheynst P. Freak: Fast retina keypoint［C］// 2012 IEEE Conference on Computer Vision and Pattern Recognition. 2012:510-517.
［5］ Zhang Shi-liang, Tian Qi, Huang Qing-ming, et al. USB: Ultrashort binary descriptor for fast visual matching and retrieval［J］. IEEE Transactions on Image Processing, 2014,23(8):3671-3683.
［6］ Shakhnarovich G, Viola P, Darrell T. Fast pose estimation with parameter-sensitive hashing［C］// Proceedings of the 9th IEEE International Conference on Computer Vision. 2003,2:750-757.
［7］ Jiang Qing-yuan, Li Wu-jun. Scalable graph Hashing with feature transformation［C］// Proceedings of the 24th International Conference on Artificial. 2015:2248-2254.
［8］ Li Hai-quan, Dai Xin-bin, Zhao Xue-chun. A nearest neighbor approach for automated transporter prediction and categorization from protein sequences［J］. Bioinformatics, 2008,24(9):1129-1136.
［9］ Buhler J, Tompa M. Finding motifs using random projections［J］. Journal of Computational Biology, 2002,9(2):225-242.
［10］Haveliwala T H, Gionis A, Indyk P. Scalable techniques for clustering the Web［C］// 3rd International Workshop on the Web and Databases. 2000:129-134.
［11］Goodman J E, O’Rourke J. Handbook of Discrete and Computational Geometry［M］. 2ed. CRC Press LLC, 2004.
［12］Ravichandran D, Pantel P, Hovy E. Randomized algorithms and NLP: Using locality sensitive hash function for high speed noun clustering［C］// Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics. Association for Computational Linguistics. 2005:622-629.
［13］Chiu Chih-yi, Wang Hsin-min, Chen Chu-song. Fast min-hashing indexing and robust spatio-temporal matching for detecting video copies［J］. ACM Transactions on Multimedia Computing, Communications, and Applications, 2010,6(2):Article No. 10.
［14］Schlkopf B, Smola A, Müller K R. Kernel principal component analysis［C］// Proceedings of the 7th International Conference on Artificial Neural Networks. 1997:583-588.
［15］Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via Hashing［C］// Proceedings of the 25th International Conference on Very Large Data Bases. 1999:518-529.
［16］Rosenblatt M. A central limit theorem and a strong mixing condition［J］. Proceedings of the National Academy of Sciences of the United States of America, 1956,42(1):43-47.
［17］Fan Bin, Wu Fu-chao, Hu Zhan-yi. Aggregating gradient distributions into intensity orders: A novel local image descriptor［C］// 2011 IEEE Conference on Computer Vision and Pattern Recognition. 2011:2377-2384.
［18］Fan Bin, Wu Fu-chao, Hu Zhan-yi. Robust line matching through line-point invariants［J］. Pattern Recognition, 2012,45(2):794-805.

[1]	杨旭朝, 雷志勇, 王娇娇. 基于局部重叠区域的无显著特征图像配准算法[J]. 计算机与现代化, 2023, 0(01): 24-29.
[2]	徐惠, 铁治欣, 舒莹. 基于特征匹配的快速降维排序搜索方法[J]. 计算机与现代化, 2022, 0(02): 85-91.
[3]	冯钧，黄多辉. 基于改进BRISK算法的单目视觉里程计[J]. 计算机与现代化, 2018, 0(09): 62-.
[4]	胡晨1，江泽涛2. 一种SIFT像素点筛选预处理降维双向匹配方法[J]. 计算机与现代化, 2016, 0(9): 54-59+72.
[5]	周敏1，刘宁钟2，王立春2. 基于无人机航拍的公路图像拼接方法研究[J]. 计算机与现代化, 2016, 0(10): 49-53.
[6]	吕俊1，王福田1,2，汤进1,2，罗斌1,2. 基于全景温度场的电力设备在线自动识别与诊断[J]. 计算机与现代化, 2015, 0(8): 19-23.
[7]	张志强 . 基于云计算的大规模人脸特征检索[J]. 计算机与现代化, 2014, 0(7): 71-74+79.
[8]	隋建凯1，刘惠义1，严烁2. 一种基于随机森林的特征匹配方法[J]. 计算机与现代化, 2014, 0(4): 81-85.
[9]	范路桥;段班祥;周文琼;姚锡凡. 基于计算机双目立体视觉的排爆机器人 自动抓取的研究和实现[J]. 计算机与现代化, 2013, 1(8): 192-194.
[10]	赵毅力;徐丹. 基于全景图像的虚拟漫游系统研究[J]. 计算机与现代化, 2011, 1(6): 11-4.
[11]	姜文卿. 一种基于组合特征的商标图像检索算法研究[J]. 计算机与现代化, 2009, 1(10): 82-4.