图像特征匹配中一种快速关键维过滤搜索算法

doi:10.3969/j.issn.1001-2400.2010.03.027

Abstract

Abstract:

In dealing with the issues of low efficiency and low accuracy in multiple wide-based-line image matching,this paper adopts the classical SIFT descriptor, and proposes a novel high dimensional feature search algorithm. This paper follows the distance-based similarity standard, and firstly partitions the image feature set into different classes, then establishes a B+Tree for each class, and finally gives out a key dimension filtering strategy(KDF) in the KNN search step to speed up the high dimensional feature matching. Experimental results show that the proposed algorithm, which can obtain a higher accuracy with a lower time cost than the classical KNN search algorithm such as BBF, LSH and so on, would be a help to improve the capability of multiple wide-based-line image matching.

Key words: feature matching, SIFT, KNN, B+Tree, key dimension filtering, image retrieval

HE Zhou-can;WANG Qing;YANG Heng. Key dimension filtering based search algorithm of B+Tree for image feature matching[J].J4, 2010, 37(3): 534-540.

References

[1]Brown M, Lowe D G. Automatic Panoramic Image Stitching Using Invariant Features[J]. International Journal of Computer Vision, 2007, 1(74): 59-73.
[2]Beis J S, Lowe D G. Shape Indexing Using Approximate Nearest-neighbor Search in High-Dimensional Spaces[C]//Proc Conf Computer Vision and Pattern Recognition. Puerto Rico: IEEE Computer Society, 1997: 1000-1006.
[3]Yao J, Cham W K. Robust Multi-view Feature Matching from Multiple Unordered Views[J]. Pattern Recognition, 2007, 40(11): 3081-3099.
[4]Lowe D G. Distinctive Image Features from Scale-Invariant Key Points[J]. Int Journal of Computer Vision, 2004, 60(2): 91-110.
[5]Mikolajczyk K, Schmid C. A Performance Evaluation of Local Descriptors[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630.
[6]Mikolajczyk K, Matas J. Improving Descriptors for Fast Tree Matching by Optimal Linear Projection[C]//Proc ICCV. Rio de Janeiro: IEEE, 2007: 1-8.
[7]Nene S A, Nayar S K. A Simple Algorithm for Nearest Neighbor Search in High Dimensions[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 1997 (19) 9:989-1003.
[8]Jagadish H V, Ooi B C, Tan K L, et al. iDistance: an Adaptive B+2tree Based Indexing Method for Nearest Neighbor Search [J]. ACM Trans on Data Base Systems, 2005, 30(1): 364-397.
[9]Gionis A, Indyky P, Motwaniz R. Similarity Search in High Dimensions via Hashing[C]//Proc VLDB. Edinburgh: Morgan Kaufmann Publishers, 1999: 518-529.
[10]Yang Heng, Wang Qing, He Zhoucan. Randomized Sub-vectors Hashing for High-dimensional Image Feature Matching[C]//ACM MM. Vancouver: ACM, 2008: 705-708.
[11]Image Database[EB/OL]. [2010-04-20]. http://lear.inrialpes.fr/people/Mikolajczyk.
[12]Ke Y, Sukthankar R. PCA-SIFT: a More Distinctive Representation for Local Image Descriptors[C]//Proc Conf Computer Vision and Pattern Recognition. Washington: IEEE Computer Society, 2004: 511-517.
[13]Object Recognition Benchmark[EB/OL]. [2010-04-20]. http://vis.uky.edu/～?stewe/ukbench/.

[1]	YAN Jia,CAO Yudong,REN Jiaxing,CHEN Donghao,LI Xiaohui. Deep asymmetric compression Hashing algorithm [J]. Journal of Xidian University, 2021, 48(5): 212-221.
[2]	LIU Daohua,CUI Yushuang,ZHAO Yansong,SONG Yuting,WANG Jinghui. Method for retrieving the teaching image based on the improved convolutional neural network [J]. Journal of Xidian University, 2019, 46(3): 52-58.
[3]	ZHANG Yuhe;GENG Guohua;WEI Xiaoran;SHI Chenchen;ZHANG Shunli. Feature extraction of point clouds using the DBSCAN clustering [J]. Journal of Xidian University, 2017, 44(2): 114-120.
[4]	YANG Yuan;ZHA Yufei;QIN Bing;LIANG Bingbing;YANG Liwei;LI Yunqiang. Image retrieval based on kernel trick and iterative quantization [J]. Journal of Xidian University, 2017, 44(1): 165-170.
[5]	YU Wangsheng;TIAN Xiaohua;HOU Zhiqiang;LIU Bin. Improved quadratic-form metric for histogram distance measurement [J]. J4, 2015, 42(3): 161-167+172.
[6]	YAN Yunyi;JIANG Shuai;GUO Baolong. Image retrieval using stable interest points and Gabor wavelet [J]. J4, 2014, 41(5): 118-123.
[7]	ZHU Xudong;LI Hui;GUO Zhen. Privacy-preserving query over the encrypted image in cloud computing [J]. J4, 2014, 41(2): 151-158.
[8]	CHEN Bing;ZHAO Yigong;LI Xin. Wide baseline image matching based on a new local descriptor [J]. J4, 2011, 38(2): 116-123.
[9]	MENG Fanjie;GUO Baolong. Image retrieval by using local distribution features of interest points and multiple-instance learning [J]. J4, 2011, 38(2): 47-53.
[10]	ZHANG Zhi-an;LUO Bin. New approach for image retrieval based on olor and spatial features [J]. J4, 2008, 35(3): 577-580.
[11]	CHEN Feng;DU Lan;BAO Zheng. Modified KNN rule with its application in radar HRRP target recognition [J]. J4, 2007, 34(5): 681-686.
[12]	ZHAO Shan;ZHOU Li-hua. Image retrieval based on the texture and shape in the DCT compressed domain [J]. J4, 2007, 34(3): 402-408.
[13]	CUI Jiang-tao(1);SUN Jun-ding(1;2);ZHOU Li-hua(1). An efficient high-dimensional image indexing method for relevance feedback [J]. J4, 2006, 33(1): 62-65.
[14]	MENG Fan-jie; GUO Bao-long. A novel image retrieval algorithm based on the color and distribution of interest points [J]. J4, 2005, 32(2): 256-259.
[15]	SUN Jun-ding1;WU Xiao-sheng2;ZHOU Li-hua1. Engropy-based image retrieval [J]. J4, 2004, 31(2): 223-228.

Key dimension filtering based search algorithm of B+Tree for image feature matching

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0