孙亭+黄凤兰+袁梦琪+卜凡亮

摘要：本文采用SIFT算法进行特征点检测，运用Kd-tree构造数据索引空间，采用最近邻检测算法在其中进行数据的查询，实现待匹配图像特征点和参考图像特征点的匹配。由于SIFT算法描述的特征点具有旋转不变性、尺度不变性等优良特性，借助这些特征点对，能够实现测量系统中的立体匹配。本文对获取的同一场景的两幅图像进行处理，用上述方法进行立体匹配，实现了较好的匹配效果，达到了接近实时性的匹配速度。

关键词：SIFT算法；Kd-tree；最近邻检测；立体匹配

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）15-0199-03

图像匹配是双目视觉测量系统中的关键技术。基于图像特征的匹配方法是最常用的匹配方法，该方法首先提取图像的局部特征（区域、线、点），然后计算两幅图像特征的相关性来确定它们之间的最佳匹配，再通过反映两幅图像关系的变换矩阵，将待匹配图像投影到参考图像中，实现两幅图像之间的匹配。基于图像特征的匹配方法研究要从Moravec[1]利用角点检测实现立体匹配开始。Harris角点检测在有效地运动跟踪方面具有重要的研究价值。Schmid[2]和Mohr研究表明不变尺度特征匹配能够扩展应用到一般的图像识别问题。由于Harris角点描述符对图像的尺度比较敏感，用于不同尺度的图像之间匹配，效果不是很理想。1999年David G.Lowe总结了已有的基于不变量技术的特征检测方法，提出了一种基于图像局部特征的描述算子，SIFT特征描述算子[3]。该算子具有多种良好的不变特性，对图像的旋转、缩放、尺度空间变换和仿射变换等均保持不变性，此外，该算法将特征检测、特征矢量生成、特征匹配搜索等步骤完整的结合，并进行进一步优化处理，达到了接近实时的运算速度，实现了良好的匹配效果。

本文利用SIFT算法对图像中的特征点进行检测，并利用基于Kd-tree的最近邻算法进行特征点的匹配，最后依赖于已有的特征点匹配对，实现双目视觉立体匹配。

1.2 SIFT特征描述子及特征矢量

SIFT描述子是一种用于特征检测的特征描述子，通过量化描述图像局部特征，客观地反映特征点附近局部区域内图像的分布情况。为了实现图像的旋转不变性，我们通过图像的梯度参数，求取特征点附近局部结构的稳定方向。对于已经检测到的特征点，特征点尺度值是确定的，我们可以得到最接近该值的高斯图像：

1.3 图像特征点匹配

对捕获的同一场景两幅图像，如果两个特征点描述矢量之间相距较近，就认为这两个特征点对应于三维场景中的同一位置；反之，则处于不同的位置。特征点匹配技术就是从对应同一场景的两幅图像特征点集合中，找到两两距离最近的特征点，实现特征点一对一匹配。

特征匹配常采用线性扫描法，就是将特征点和查询点逐一进行距离比较，选择距离最小的点，但是该检索方法搜索效率比较低。本文采用Kd-tree[5]的数据结构，将整个数据空间划分成小空间，逐级展开搜索，搜寻最近邻点。Kd-tree本质上就是二叉树，每个节点表述一个空间范围。构建流程如下：

（1）分析数据点数据，展开kd-tree；

（2）找到分割超面，确定其垂直方向轴序号，计算对应维度上的数据方差；

（4）分割数据。维数小于阈值的，其对应的特征点放在右子树空间；否则放在左子树空间；

（5）分别展开左子树、右子树，重复上述步骤（2）、（3）、（4），将空间和数据集进一步细化，直至空间中只包含一个特征数据点。

在kd-tree中进行数据的查询是为了检索kd-tree数据集中与查询点距离最近的数据点。按照二叉树结构展开搜索，沿着搜索路径，找到最近邻的近似点，也就是包含查询点的叶子节点。但是这样找到的叶子节点不一定就是最近邻点，最近邻点肯定距离查询点更近，也就是说，最近邻点一定在以查询点为圆心，通过叶子节点为半径的圆域内。这就需要我们沿搜索路径回溯操作，看是否存在某一数据点，距离查询点更近。若存在，就用新查到的数据点代替叶子节点，反之若不存在，则认为已经找到的叶子节点就是最近邻点，从而完成特征点的匹配。

2 立体匹配

立体匹配[6]是指对参考图像中的任意像素，在待匹配图像中找到与之相对应的像素点的过程，即找到空间中任一场景点在两幅图像中对应的像素点。这些像素点有可能是已经检测出的特征点，也有可能只是普通的像素点。由于使用SIFT算法检测到的特征点具有多种不变特性，在图像中处于相对稳定的区域，我们可以建立待匹配像素点和周围特征点的关系，来实现像素点之间的匹配。

本文在特征匹配的基础上，研究了普通像素点和特征点之间的关系，实现了图像的立体匹配。算法具体流程如下：

（1）在参考图像中，从上往下，从左至右对图像特征点依次排序，并求取各特征点到参考像素点之间的欧氏距离；

（2）比较求得的欧氏距离，选择其中距离最小的特征点为最近特征点，如存在距离相同的特征点，选择序号最小的特征点为最近特征点；同理，选择距离次小的特征点为次近特征点；

（3）从匹配好的特征点对中，找到最近特征点和次近特征点，并从已经存在的匹配对集合中，找到待匹配图像中与之对应的最近特征点和次近特征点。

（4）在参考图像中，建立两个特征点与参考像素点之间的函数关系。运用该函数关系求出待匹配图像中对应的像素点。

对于立体匹配，除了借助特征点匹配对，立体匹配本身还具有一些约束条件：1）唯一性约束。每个参考像素点存在且只存在唯一的待匹配像素点与之相匹配；2）顺序一致性约束。同一扫描线上的两个像素点在参考图像和待匹配图像上具有相同位置次序；3）一致性约束。两幅图像中，对于未遮挡的相同场景，对应的像素点具有相同的视差。运用立体匹配条件，可以进一步优化我们已经得到的立体匹配点对，实现更好的匹配效果。

3 实验结果及分析

本文使用的实验设备：一个带有旋转云台的自动三脚架（三脚架和云台的运动情况可以进行参数设置），一台85mm微距的尼康摄像机，一台戴尔的台式电脑。

将摄像机安装在三脚架上，设置三脚架运动参数，使得三脚架只进行垂直运动。用该设备获取三脚架运动前后，对着的同一场景的两幅图像。

应用SIFT算法，对获取的两幅图像进行特征点检测。图中黑色的点表示检测到的特征点，从图1可以看出，利用SIFT算法进行特征点检测，得到的检测结果大多是比较明显的边缘点、角点、像素灰度变化比较大的点，这为后续的特征匹配打下了良好的基础。

从特征点匹配的实验结果来看，检测到的特征点都能在目标图像中找到对应的特征点，完成特征点的相互匹配。但是仔细观察不难发现，本实验中存在错误的匹配对。本实验中一共实现了151对特征点的匹配，其中存在3对错误的匹配，即误匹配率为1.98%，实现了较好的匹配效果。而且匹配运算时间只用了6.763 S，达到了很好的实时性效果。图中误匹配点对主要集中在图像中部，分析是书柜排布相似、书本上存在个别效果不明显的特征点等原因导致的。

在立体匹配上，本文进行了多次实验，选取其中几组实验，实验结果如图所示。其中蓝线表示最近特征点对和次近特征点对，红线表示对应的求得的匹配像素点对。实验像素坐标如表1所示。

从上述实验数据中可以看出，大部分数据横、纵轴差值相当，对比实验图像，实验数据是真实可靠的。进行实验时，理论上智能三脚架只进行垂直升降运动，由此参考像素点和待匹配像素点的横坐标是相同的，但是在实际的操作中，由于地面不完全平整、仪器本身条件限制等原因，摄像机运动过程中存在一定程度的晃动，会产生一定程度的横向偏移，使得参考像素点和待匹配像素点的横轴坐标不一致。其次，由于像素点的匹配是依赖于特征点匹配对的，如果特征点匹配对是误匹配，会直接导致后面的像素点匹配对发生错误，如图4所示。还有即使特征点匹配对是正确的，后面建立的几何函数的不精准或是计算的精确度等原因，也会影响像素点的匹配。

4 结语

在刑事案件现场中，一般人造物品比较多，特征都比较明显。本文利用SIFT算法对拍摄的现场图像进行特征点检测 ，能够快速、有效的实现特征点的检测。在特征匹配的过程中，通过SIFT特征描述子建立特征矢量，对检测到的特征点进行详细的描述。 构造Kd-tree数据结构，利用该结构进行近邻检测，实现特征点的匹配，再在此基础上，完成立体匹配。本文实现了快速的立体匹配，实现了较好的匹配效果。但仍然存在不足，有误匹配的出现，正确的匹配在精度上也有待加强，有待于进一步优化。

参考文献：

[1] Moravec H. Rover visual obstacle avoidance[C]. In International Joint Conference on Artificial Intelligence， Vancouver， Canada， 1981， 785-790.

[2] Schmid C. and Mohr R. Local gray-value invariants for image retrieval[J]. IEEE Trans. On Pattern Analysis and Machine Intelligence， 1997， 19（5）：530-534.

[3] Lowe D. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision， 2004， 60（2）：91-110.

[4] 王永明，王贵锦.图像局部不变性特征与描述[M].北京：国防工业出版社，2010.4：79-88

[5] 杜振鹏，李德华.基于KD-Tree搜索和SURF特征的图像匹配算法研究[J].计算机与数字工程，2012（2）：96-100.

[6] 姜宏志，赵慧洁.基于极线校正的快速相位立体匹配[J].光学精密工程，2011（10）：2520-2527.