一种KD树的快速SURF图像匹配算法

广州南方学院电气与计算机工程学院 彭 石 张 晴 曾海杰 张焱玮

现有的图像匹配算法存在运行慢、时间复杂度高等缺点，本文在研究了图像特征和匹配算法的基础上，提出了一种改进的快速匹配算法。该算法能有效地解决图像尺寸过大带来的匹配慢的问题，首先对于要匹配的的图像，经过线性缩小后变为易于处理的灰度图，再使用SURF算法计算初始特征点集，经过逆变换后映射到原图像求得过滤后的点集，并且生成SURF特征描述子，针对SURF匹配慢的缺陷，本文采用KD树来实现点集的匹配和查询，测试结果表明，本文算法在保证了匹配精度的条件下，有效的降低了匹配的时间复杂度。

图像匹配算法在遥感、航空航天、生物信息识别等方面应用广泛，特别是随着智能设备的普及，指纹识别、人脸识别等图像处理技术越来越受到重视和关注。快速准确地处理与识别图像，满足用户个性化多样化的需求，是国内外理论研究的重要参考原则。

图像匹配可以采用不同的方法进行，有采用全局统计特性的匹配，还有基于局部特征的方法。前者一般采用统计的手段，后者先计算特征点，利用特征点的特征描述子来进行图像的匹配。由于特征点数一般比较少，所以后者的匹配速度一般比前者快，精度也高很多。为了有效进行图像匹配，Lowe DG提出了一种SIFT算法，该算法匹配和识别的效率较高，但实时性较差，Bay H,Tuyte T,Gool L Van针对SIFT的不足提出了改进的算法SURF，该算法具有匹配的速度比较快、在图像尺度和仿射变换下保持不变性等优点；阮芹,彭刚,李瑞利用改进后的SURF算法，针对两幅图像的重叠部分提取局部特征点，实现了重叠部分的平滑过渡。

本文提出了一种基于KD树的快速匹配算法，该算法能有效地解决图像尺寸过大带来的匹配慢的问题，首先该算法把要匹配的的图像缩小后变为易于处理的灰度图，再使用SURF算法计算初始特征点集，经过逆变换后映射到原图像求得过滤后的点集，并且生成SURF特征描述子，最后采用KD树来实现点集的匹配和查询。该方法可以在匹配精度不变的条件下，显著减少匹配的计算次数。

1 改进的SURF算法流程

1.1 图像缩放

图像缩放，本质上就是将每个像素点的矢量进行缩放，也就是将矢量x方向和y方向的坐标值缩放，假设缩小系数为k，缩放表示成矩阵的形式：

通过上述矩阵乘法的形式，把原图像上的每一个像素点映射到新图像上相应的像素点了，其逆变换为：

1.2 SURF特征点检测

为了有效地提取图像f(x,y)的特征，Surf通过计算其Hessian矩阵来实现图像的预处理操作。Hessian矩阵通过计算图像的偏导数得到包含图像特征信息的初始矩阵，经过过滤可以得到SURF的关键特征点。由于f(x,y)图像包含有噪声信号，生成Hessian矩阵前一般先进行滤波操作，高斯滤波后的该矩阵数学表达式为：

得到Hessian矩阵之后，SURF通过计算其判别式是否为局部最大来寻找关键点的位置。局部最大值对应的点一般比周围点更亮或更暗，这些点包含更多的图像信息，为了准确找出这些点SURF使用盒式滤波器计算Hessian矩阵行列式：

上式中det表示在点(x,y)周围区域的方框滤波响应值，如果行列式的值为负，并且特征值异号，该点不是局部极值；如果行列式为正并且特征值同号，则该点为局部极值。使用其它大小的模板，Hessian矩阵行列式就包含了多尺度响应信息，经过局部搜索周围点的Hessian值，如果最大，则为标记为特征点。

图1 线性变换

从缩放后的图像得到特征点之后，本文通过运算得到原图像的特征点。如图1所示，已知P点为经过步骤1逆变换后的像素点，它的四周有四个待识别的点，利用上述步骤重新计算四个点的Hessian矩阵及其行列式，如果最大则标记为原图像的特征点。

1.3 SURF特征描述子

1.3.1 特征点方向分配

经过上一步得到特征点后，接下来就需要计算每个点对应的主要方向。SURF算法在特征点的周围区域通过小波变换计算领域特征，每计算一次，按照一定的角度旋转继续进行下一次特征计算，所有方向统计完成，小波响应值最大的方向即为特征点的主要参考方向。

1.3.2 特征向量生成

Surf算法的每个特征点都包含一个64维的特征向量，其计算方法是沿着每个点的主要参考方向，取16个排列成4X4正方形的方块，每个方块都包含25个像素，通过计算这些像素不同的小波特征，每个方块生成4维的向量，故每个特征点需要统计的特征向量有64个值。

1.4 特征匹配

经过上述步骤得到特征点和特征向量之后，本文使用kd树完成特征点的查询和匹配的过程。

1.4.1 kd树的生成过程

（1）对于需要统计的点集，假设每个点有m维数据，分别计算各个维度的方差，选择方差最大的维度n，假设该维度下对应的中值为d，以其对应的节点为根节点对原始点集进行划分，维度n下比d小的和比d大的生成两个子集A、B。

（2）对A、B子集按照1的方法继续进行划分，不断地生成新的子集和节点，直到所有集合划分结束，kd树生成完毕。

1.4.2 查询匹配过程

（1）kd树的查询过程是从根节点开始的，将查询节点Q特征向量相应维度上的值与kd树的相应的值作比较，若前者小遍历左边的分支及其节点，否则去另一边的分支，重复上述过程不断记录节点Q与叶结点向量之间的距离，最小距离dmin对应的数据点称为最近邻点。

（2）进行遍历回滚，在找到的节点附近的节点进行上述过程，防止存在离Q更近的节点。

对于找到的最近邻与次近邻点值，本文通过以下步骤进行判断是否为正确匹配，对于目标图片的中每个特征点，使用上述的方法计算它的最近邻和次近邻，

如果二者之差的绝对值大于某个阈值，则认为该匹配是成功的，否则就进行下一次匹配。对于待匹配的两张图像，将各图像所有特征点都进行上述的SURF特征匹配过程。

2 实验结果与分析

为了验证本文算法的有效性，实验中选择了1000张图片进行了性能测试，这些图片分成5组，每组200张图片，各组前100张是不同主题的原始图像，后100张是从不同方向拍摄或者旋转后的图像。将后100张图片分别用SIFT、SURF以及本文算法与前100张进行匹配识别，然后从识别的精度和时间复杂度两个方面比较测试的结果。每进行一次匹配，将所有匹配后的特征点距离按照从小到大排序，然后计算前50个最近距离之和作为两张图的相似度，经过100次计算后，如果正确匹配就将正确的次数加1，否则将错误次数加1。

图2 特征匹配结果

表1 各算法的识别精度比较

表2 各算法的平均匹配时间比较

图2所示为旋转后的图片和原图的匹配过程，左右图上的连线表示匹配成功。全部图片进行上述过程得到的结果如下所示，表1、2为用三种算法实验得到的精度和时间复杂度表。从表1可以看出，本文算法的匹配精度不低于SURF算法，远远高于SIFT算法。从表2可知，本文算法的匹配时间远远低于SIFT，和SURF算法相比，足足缩短了2倍多。由此可知，本文算法在匹配上具有时间复杂度低的优势。

结束语：本文提出了一种基于KD树的快速匹配算法，该算法能有效地解决图像匹配速度慢的问题，首先该算法把要匹配的的图像缩放后变为易于处理的灰度图，再使用SURF算法计算初始特征点集，经过逆变换后映射到原图像求得最终的特征点集，并且生成SURF特征描述子，最后采用KD树来实现点集的匹配和查询。实验结果表明，本文方法能够在保证匹配精度不降低的条件下，明显降低匹配的时间复杂度。