J4 ›› 2010, Vol. 37 ›› Issue (3): 534-540.doi: 10.3969/j.issn.1001-2400.2010.03.027

• 研究论文 • 上一篇    下一篇



  1. (西北工业大学 计算机学院,陕西 西安  710072)
  • 收稿日期:2008-12-18 出版日期:2010-06-20 发布日期:2010-07-23
  • 通讯作者: 何周灿
  • 作者简介:何周灿(1984-),男,西北工业大学硕士研究生,E-mail: hezhoucan@163.com. 通讯作者:王庆,教授,博士生导师,E-mail: qwang@nwpu.edu.cn.
  • 基金资助:


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

HE Zhou-can;WANG Qing;YANG Heng   

  1. (School of Computer Sci. and Eng., Northwestern Polytechnical Univ., Xi’an  710072, China)
  • Received:2008-12-18 Online:2010-06-20 Published:2010-07-23
  • Contact: HE Zhou-can


为了解决宽基线多图匹配中匹配效率低和匹配精度不高的问题,使用经典的SIFT特征作为描述子,提出一种新的高维特征搜索算法.采用基于距离尺度的相似性度量准则,首先将图像高维特征集合分类,然后为每一个类建立B+Tree索引,最后在KNN(K Nearest Neighbor)搜索阶段应用基于关键维过滤的查找策略,实现高维特征的快速匹配.实验结果表明,与经典的BBF和LSH等KNN搜索算法相比较,关键维过滤搜索算法具有更高的搜索效率和搜索精度,有助于提升宽基线多图匹配性能.

关键词: 特征匹配, 尺度不变特征变换, K近邻, B+Tree, 关键维过滤, 图像检索


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