层次结构K-d树的立体图像快速匹配方法  

Fast and Hierarchical K-d Tree Based Stereo Image Matching Method

作　　者：张贵安[1] 袁志勇[1] 童倩倩[1] 廖祥云[1] ZHANG Gui-An YUAN Zhi-Yong TONG Qian-Qian LIAO Xiang-Yun(School of Computer, Wuhan University, Wuhan 430072, Chin)

机构地区：[1]武汉大学计算机学院,湖北武汉430072

出　　处：《软件学报》2016年第10期2462-2472,共11页Journal of Software

基　　金：国家自然科学基金(61373107)~~

摘　　要：特征匹配是计算机视觉和图形图像处理领域中很多研究方向的基础,也是当前的研究热点.SIFT(scaleinvariant feature transformation)特征因其具有尺度、旋转不变性,对一定范围的仿射及视角变换具有鲁棒性等优点,自Lowe提出后,10多年来一直受到众多研究人员的关注.匹配的快速性和准确性是很多应用对特征匹配的要求,如三维重建中立体图像对(stereo pairwise image,简称SPI)的匹配.针对这一问题,以SIFT特征为基础,提出用于SPI匹配的方向大约一致(approximately consistent in orientation,简称ACIO)约束关系,其描述了SPI的匹配特征向量间的空间位置关系,有效地避免了误匹配的发生,提高了匹配的精度;通过对标准K-d树(standard K-d tree,简称SKD-tree)结构的分析,提出了层次结构K-d树(hierarchical K-d tree,简称HKD-tree),将SPI特征集根据ACIO约束关系划分成层次结构并建立映射,该方法缩小了搜索空间,从而达到加速匹配的目的.在ACIO和HKD-tree的基础上,提出了高效、快速的匹配算法.实验结果表明,所提方法比SKD-tree方法和最新的级联哈希方法(cascade hash,简称Cas Hash)在精度上略占优势,但在匹配速度上比SKD-tree快一个数量级以上,同时也数倍于Cas Hash.Feature Matching has long been the basis and a central topic in the field of computer vision and image processing. SIFT（scale-invariant feature transformation, by David G. Lowe）, due to its advantages of invariance to image scale and rotation, and robustness to a substantial range of affine distortion and change in viewpoint, has been attracting the attention of many domestic and foreign researchers over a decade. Rapidity and accuracy are very crucial for stereo pairwise image matching in applications such as 3D reconstruction. First, in order to accelerate the speed and promote the accuracy of matching, this paper proposes a novel method based on SIFT called approximately consistent in orientation（ACIO）, which depicts the spatial location relationship of two matched vectors between stereo pairwise images（SPI）, and therefore improves the accuracy of matching efficiently by avoiding the wrong correspondences. Secondly, this paper analyzes the structure of standard K-d tree（SKD-tree） and proposes a new one with hierarchical structure, named HKD-tree, which partitions the feature sets of SPI into stripes in terms of ACIO constraint and builds map between them. By reducing the search space, the matching speed increases greatly. Thirdly this work presents an efficient and fast matching algorithm based on ACIO and HKD-tree. Extensive trials based on a benchmark data set show that the proposed approach outperforms the state-of-the-art methods in matching speed with slight promotion in accuracy. Particulary, it is one order of magnitude faster than SKD-tree and also several times against the recent Cas Hash method.

关 键 词：尺度不变特征变换 方向大约一致 层次结构K-d树 立体图像对 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]