A Binary Feature Matching Method Based on Minimum Hashing

doi:10.3969/j.issn.1006-2475.2016.06.016

Abstract

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

CLC Number:

TP391

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.

References

［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]	Non-saliency Feature Image Registration Algorithm Based on Local Overlapping Region. YANG Xu-zhao， LEI Zhi-yong， WANG Jiao-jiao [J]. Computer and Modernization, 2023, 0(01): 24-29.
[2]	XU Hui, TIE Zhi-xin, SHU Ying. Fast Dimensionality Reduction Sorting Search Method Based on Feature Matching [J]. Computer and Modernization, 2022, 0(02): 85-91.
[3]	FENG Jun, HUANG Duo-hui. Monocular Visual Odometry Based on Improved BRISK Algorithm [J]. Computer and Modernization, 2018, 0(09): 62-.
[4]	HU Chen1, JIANG Ze-tao2. A SIFT Pixel Filter Pretreatment Dimensionality Reduction Bidirectional Matching Method [J]. Computer and Modernization, 2016, 0(9): 54-59+72.
[5]	ZHOU Min1, LIU Ningzhong2, WANG Lichun2. Research on Stitching Method Based on UAV Aerial Image of Road [J]. Computer and Modernization, 2016, 0(10): 49-53.
[6]	LYU Jun1, WANG Fu-tian1,2, TANG Jin1,2, LUO Bin1,2. Online Automatic Recognition and Diagnosis of Electrical Devices via Thermal Panorama [J]. Computer and Modernization, 2015, 0(8): 19-23.
[7]	SUI Jiankai1, LIU Huiyi1,YAN Shuo2. Feature Matching Method Based on Random Forests Classifier [J]. Computer and Modernization, 2014, 0(4): 81-85.
[8]	FAN Lu-qiao;DUAN Ban-xiang;ZHOU Wen-qiong;YAO Xi-fan. Research and Implementation of Automatic Grasping of a EOD Robot  Based on Computer Binocular Stereo Vision [J]. Computer and Modernization, 2013, 1(8): 192-194.
[9]	ZHAO Yi-li;XU Dan. Research on Virtual Navigation System Based on Panoramic Images [J]. Computer and Modernization, 2011, 1(6): 11-4.
[10]	JIANG Wen-qing. Trademark Image Retrieval Research Based on Combined Shape Features [J]. Computer and Modernization, 2009, 1(10): 82-4.