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

特征匹配是计算机视觉和图形图像处理领域中很多研究方向的基础，也是当前的研究热点.SIFT （scale-invariant feature transformation）特征因其具有尺度、旋转不变性，对一定范围的仿射及视角变换具有鲁棒性等优点，自David G.Lowe提出后，10多年来一直受到众多研究人员的关注.匹配的快速性和准确性是很多应用对特征匹配的要求，如三维重建中立体图像对（stereo pairwise images,简称SPI）的匹配.针对这一问题，本文以SIFT特征为基础，提出用于SPI匹配的方向大约一致（approximately consistent in orientation,简称ACIO）约束关系，其描述了SPI的匹配特征向量间的空间位置关系，有效地避免了误匹配的发生，提高了匹配的精度；通过对标准K-d树（standard K-dtree,简称SKD-Tree）结构的分析，提出了层次结构K-d树（hierarchical K-d tree,简称HKD-Tree），将SPI特征集根据ACIO约束关系划分成层次结构并建立映射，该方法缩小了搜索空间，从而达到加速匹配的目的；在ACIO和HKD-Tree基础上，提出了高效快速的匹配算法.实验结果表明，本文所提方法比SKD-Tree方法和最新的级联哈希方法（cascade hash,简称CasHash）在精度上略占优势，但是在匹配速度上比SKD-Tree快一个数量级以上，同时也数倍于CasHash.

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

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), because of 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 although over a decade has past, since proposed by David G. Lowe. Rapidity and accuracy are very crucial for stereo pairwise images matching in applications like 3D reconstruction, structure from motion and so on. In order to accelerate the speed and promote the accuracy of matching, firstly we propose 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 so improves the accuracy of matching efficiently by avoiding the wrong correspondences. Secondly we analyze the structure of standard K-d tree (SKD-Tree) and propose 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. Because of search space shrinking, the matching speed increases greatly. Thirdly we present an efficient and fast matching algorithm based on ACIO and HKD-Tree. Extensive trials based on a benchmark data set show that our approach outperforms the state-of-the-art ones in matching speed with slight promotion at accuracy, in which about at one order of magnitude faster than SKD-Tree and also several times against the recent one named CasHash.