一种基于历史特征的SURF改进算法研究

黄进勇　李哲　张天凡

摘 要： 图像配准是数字图像处理深度应用的基础之一，其中基于SURF的图像配准算法因识别率高而得到广泛的研究与应用，但其数据量大且对计算要求较高，因此提出一种基于对象关联的配准方法，在SURF前端提取对象ROI以检测是否有新的对象进入检测区域从而将新旧对象分为两类分别处理，对于已经存在的对象可根据运动特征关联进行进一步过滤，较大幅度地减少重复特征点的检测和计算，也可避免依赖局部区域像素的梯度方向造成过大的误差。实验结果表明，改进的算法提高了配准率，减少了约20%的计算量，帧率下降至0.8左右时趋于稳定，保证了较好的实时性。

关键词： SURF算法； Hessian矩阵； 运动对象识别； 匹配率

中图分类号： TN911.73?34 文献标识码： A 文章编号： 1004?373X（2017）03?0038?05

Research on a SURF improved algorithm based on historical characteristics

HUANG Jinyong1， LI Zhe1， 2， ZHANG Tianfan1， 2

（1. College of Technology， Hubei Engineering University， Xiaogan 432000， China；

2. School of Automation， Northwestern Polytechnical University， Xian 710072， China）

Abstract： The image registration is one of the fundaments for further application of the digital image processing. The SURF?based image registration algorithm is widely researched and applied due to its high recognition rate， but it has large data quantity and high calculation requirement， so a registration method based on object association is proposed. The object ROI is extracted in the front end of SURF to detect whether a new object has entered into the detection area， so as to divide the old and new objects into two classes for processing. The existing objects can be further filtered according to the motion feature association to significantly reduce the detection and calculation of the repeated feature points， and avoid the excessive error caused by relying on the gradient direction of the local region pixel. The experimental results show that the improved algorithm has improved the registration rate， its calculation quantity is reduced by 20%， its frame rate trends to be stable when it is dropped to about 0.8， and the algorithm insures good real?time performance.

Keywords： SURF algorithm； Hessian matrix； moving object recognition； matching rate

0 引 言

运动目标识别一直是机器视觉领域的研究热点。它已被广泛应用于视频监控、测绘、机器人导航等领域中。SURF（Speeded Up Robust Features）[1] 是近年应用广泛的一种匹配算法，采用了Harr特征以及积分图像概念，使得同等条件下标准的SURF算子快于典型的SIFT[2] 算子数倍，大幅度地减少了计算时间，同时在连续的图像下也具有很好的鲁棒性[3] 。在SURF的基础上，文献[4] 从材料的光照反射率角度提出一种能量函数进行目标匹配，对三维环境下多角度拍摄的视频匹配有较大的改进；文献[5]根据相邻像素在平滑和边缘地区可能各不相同，提出光滑能量函数，能量函数的扩散速度由梯度、线点等信息确定，从而降低深度不连续区域的失配率。文献[6]提出一种改进的PatchMatch算法，通过积累强度差异或者颜色相异度之间连接的像素，沿路径计算以获得相邻图像之间的关联性，从而改善匹配准确度。

由于SURF算法中主要使用相邻帧数据进行计算，早期运动特征数据被当前较短时间的信息所取代，使得SURF只能反映当前 “瞬间”状态，易被噪声干扰，从而导致该算法匹配率较低。此外，基于局部区间像素的梯度方向易受主方向影响，即使是一个小角度的偏差也会导致特征匹配失误，从而显示错误的匹配结果。

针对该问题，提出一种实时更新特征点的优化方案，存储对象ROI及该区域内特征点构建一段时间内的历史特征，改善匹配率；通过实时更新特征点，去除重复特征，维持较低的运算率。在实验部分，利用OpenCV3轻量及高效的特性[7]，并结合VS2015实现了该改进算法，样本匹配率提升约15%，同期处理帧率稳定在0.8，基本能够达到实时性处理的要求。

1 SURF特征点检测模型

典型的SURF算法主要包括获取对象ROI、特征点监测、特征向量的提取和匹配标记[8] ，如图1所示。

在构建SURF算法前需要得到相应的Hessian矩阵，进而构建高斯金字塔尺度空间，然后再构建SURF特征点进行特征匹配。

1.1 构建Hessian矩阵及高斯金字塔尺度空间

1.1.1 构建Hessian矩阵

从数学的角度来讲，海森矩阵（Hessian Matrix）是一个由多元函数的二阶偏导数组成的方块矩阵。对比SIFT算法，Hessian矩阵的行列式近似值图像远远优于DOG图像，SURF算法加快了检测的速度，从而较优于SIFT。设函数[fx，y，]Hessian矩阵[H，]图像中任意一个像素点的Hessian矩阵如下[9] ：

[Hfx，y=?2f?x2?2f?x?y?2f?x?y?2f?y2] （1）

设判别式DET对[H]矩阵的特征值进行分类，通过判别式得到的值对所有的点进行分类，并根据判别式的正负决定该点是否为极值。判别式DET如下：

[DETH=?2f?2f?x2?y2-?2f?x?y2] （2）

将图像像素[Lx，y]代入函数[fx，y，]设置标准高斯滤波器，经过特定内核卷积计算二阶偏导数，得到[H]矩阵的三个矩阵元素[Lxx，][Lxy，][Lyy]。计算[H]矩阵：

[H（x，σ）=Lxx（x，σ）Lxy（x，σ）Lxy（x，σ）Lyy（x，σ）] （3）

1.1.2 高斯平滑处理

构造Hessian矩阵前必须确定特征点在尺度上无噪声，通过高斯滤波处理可以有效地降低特征点噪声。经过滤波后的Hessian计算公式如下：

[L（x，t）=G（t）?I（x，t）] （4）

式中[L（x，t）]为一幅图像对应不同程度解析下的图像，可用于高斯核[G（t）]和图像函数[I（x）]在点[x]的卷积来实现，其中高斯核[G（t）]的计算公式如下：

[G（t）=?2g（t）?x2] （5）

式中：[g（x）]为高斯函数；[t]为高斯方差。根据该方法可以计算出图像任意像素的决定值，并用该方法确定特征点。

由于求Hessian时需要先高斯平滑再求二阶导数，所以在这里离散的像素点用模板卷積形成，这两种操作步骤用一个模板代替即可。

1.1.3 建立相关金字塔结构

经过变换后得到一张类似于SIFT中DOG图的近似Hessian的行列式图。在金字塔结构中，图像被分为多个层，每层被称为octave，每个octave有几个不同尺度的图片。在SURF中，图片的大小始终不变，而不同octave层中用到的高斯模板尺度也不相同。该算法可以同时处理多幅图像的尺度空间，而不需要进行图像的双采样，从而提高计算性能。

与SIFT算法类似，SURF算法将Hessian矩阵处理的像素点与其三维领域的点逐一比较，如某一像素点是该矩阵像素中的极值，则保留下来作为初始特征点。最后，使用相应大小的滤波器进行检测。

如图2所示为[3×3]的滤波器，对模糊图像九个像素点的特征点进行检测，并将剩下的八个模糊层与上下两模糊层九个像素对应比较。图中标记“◆”的特征值大于周围像素，可以确定为该区域的特征点。

1.2 筛选关键点集合

通过三维线性插值法对关键点的位置和尺度进行采集，得到图像中SURF候选特征点集合[X0，]从中选择具有稳定性的点作为该图像的SURF特征点，设其组成的集合为[X，]由于[X0]中有部分点容易受到对比度的影响而成为噪声点，同时位于图像中边缘的点难以定位，所以出于SURF算法的稳定性考虑，这两种点需要去除。

1.2.1 剔除对比度低的点

将候选特征点[x]的偏移量定义为[Δx，]其对比度为[H（x）]的绝对值，对[x]的Hessian表达式进行泰勒级数展开：

[H（x）=H+?HT?xΔx+12ΔxT?2HT?x2Δx] （6）

由于[x]为Hessian计算公式的极值点，所以[?H（x）?x=0，]解方程得：

[Δx=-?2H-1?x2??H（x）?x] （7）

通过迭代多次后得到稳定的特征点的位置及尺度[x，]将其代入公式求得[Hx，]求其绝对值可得[Hx]。设对比度阈值为[T，]则对比度点的剔除公式为：

[x∈XH（x）≥Tc，x∈X0x∈XH（x）

1.2.2 剔除边缘点

由于边缘梯度方向上的主曲率值较大，而边缘方向上曲率较小，在边缘上得到的Hessian的极值点与非边缘区域的点相比，其主曲率比较大，因此可以将主曲率比较值大于一定阈值的点视为边缘上的点，将其剔除。由于候选点Hessian的[H（x）]的主曲率与[2×2]的Hessian矩阵[H]的特征值成正比：

[H=LxxLxyLxyLyy] （9）

式中：[Lxx，][Lxy，][Lyy]为候选点领域对应位置的像素差分；令[α]为[H]的最大特征值，[β]为[H]的最新特征值，令[γ=αβ，]则[H（x）]的主曲率比值与[γ]成正比。由[H]的几何行列式的值可得：

[Tr（H）=Lxx+Lyy=α+β] （10）

[DET（H）=LxxLyy-（Lxy）2=αβ] （11）

[Tr（H）2DET（H）=（α+β）2αβ=（γβ+β）2γβ2=（γ+1）2γ] （12）

式中：[（γ+1）2γ]只与两特征值之比有关，与特征值自身大小无关，随着[γ]的增大而增大；设主曲率比值阈值为[T，]则边缘点的剔除公式为：

[x∈XTr（H）2DET（H）≤（Tγ+1）2Tγ，x∈X0x?XTr（H）2DET（H）>（Tγ+1）2Tγ，x∈X0] （13）

剔除低对比度和边缘点后所剩特征点如图3所示。

1.3 SURF特征描述算子

1.3.1 选取特征点的主方向

SURF在生成特征矢量时，为保证特征矢量具有选择不变性，需要对每个特征点分配一个主方向。因此，SURF算法以特征点为中心，对6 s（s为特征尺度单位）的半径圆形区图像的Harr小波响应进行运算。与SIFT在求取特征点主方向不同，SIFT是以特征点为中心，在以[1.6?]为半径的领域内计算梯度方向直方图[10] 。如图4所示，在求取特征点主方向时，两种算法都以带宽模板的Harr小波为考虑要素，而图像区域的梯度实际是一样的。

针对Harr小波的响应值，以[σ=2 s]为参数进行高斯加权，并设计了一个以特征点为中心，滑动[π3]的扇形窗口，得到特征点的主方向，如图5所示。

如图5所示，与约0.2的[Harr]旋转的滑动窗口的步长和图像的小波响应值[dx，][dy]进行图像的滑窗积累，得到矢量[（mω，θω）]：

[mω=ωdx+ωdyθω=arctanωdxωdy] （14）

[Harr]响应累计值对应最高的方向为主方向，这是最长的向量对应的方向，即：

[θ=θωmaxmω] （15）

1.3.2 构造SURF特征点描述子

生成特征点描述算子与确定特征点的方向类似，需要对图像的Harr小波响应进行计算。但与圆形计算区域不同，需要在一个矩形区域内计算Harr小波响应。以特征点为中心，将20×20图像特征点的主方向分成4×4的子块，利用[Harr]小波响应计算各块模板尺寸，然后对响应值进行统计，[dx，][dx，][dy，][dy]形成特征矢量，如图6所示。

图6中以特征点为中心，以20 s为边长的矩形窗口为特征描述算子计算使用的窗口，特征点到矩形边框的线段表示特征点的主方向。将20 s的窗口划分为4×4的子窗口，每个子窗口中有5×5个像元，使用尺度为2 s的[Harr]小波对子窗口图像进行响应值计算，共进行25次采样，得到与主方向一致的矢量[dy]和对应初值方向的矢量[dx。]然后以特征点为中心，对[dx，][dy]进行高斯加权计算，其中[σ=3.3 s]。最后，得到每个子块的响应值，并得到每个子块的矢量：

[V子块=dx，dx，dy，dy] （16）

2 针对视频问题的优化

在SURF算法应用中，对于图像与图像间的匹配有着不错的匹配率，但在视频中单以SURF算法進行暴力匹配的话，会有匹配率低的问题，而其主要的问题是，其匹配模板中包含的人物特征点具有一定的局限性：不是全方位的特征，与其他特征点有重复等问题。针对上述问题，对人物特征点处理进行优化，其流程图如图7所示。

图7中，实线部分为原有的SURF对视频的处理过程，而虚线部分则是对视频问题的优化。将每一帧的特征点进行收集，增加特征点集的特征点数解决人物特征点的局限性，提升匹配成功率。

3 测试结果分析

在算法测试结果中，通过静态图像对比测试和视频图像对比测试两方面对SURF算法进行测试分析。其中，测试部分所用的图像与视频皆来自于作者实验室实际拍摄的视频源，测试结果图中显示的为其中所有测试结果的一部分。测试硬件环境为Windows 7，Intel i5?4440 3.1 GHz，内存16 GB，软件环境为Visual Studio 2015，OpenCV 3。

3.1 静态图像测试

如图8所示，取视频片段进行测试。以图8（a），图8（b）中的人物作为匹配模板，并以该模板对自身进行匹配测试，测试匹配结果显示为吻合。在图8（c），图8（d）中，以图8（a），图8（b）的模板进行配，图8（c）匹配结果吻合，但图8（d）中有个别错误匹配连接。

以上述人物模型为匹配模板，对视频片段中连续的100幅静态图像进行匹配测试，将匹配率按10%分割为10个匹配端统计，其测试结果如图9所示。结果显示，只用SURF对不同图像进行人物匹配，稳定匹配率在40%～49%之间。

3.2 视频图像测试

采用之前对连续不同帧匹配率偏低问题的优化方案对视频进行测试，其结果如图10所示。

图10（a）～图10（c）中对缓慢行走的人物进行匹配，可以稳定地显示其人物编号0。图10（d）～图10（f）中对快速奔跑的人物进行匹配，可以稳定地显示其人物编号1。图10（g）～图10（i）中分别出现了人物0和人物1，可以看到能准确地进行识别。

上述测试结果表明，本文进一步优化了SURF对连续帧匹配率低的问题。但是在实验中，连续处理了一段时间的视频数据后，有计算速度明显下降的趋势。所以又对连续帧匹配时的帧率进行统计测试，其结果如图11所示。

结果显示，在连续帧处理时，随着时间的增加，帧率呈现一种下降趋势，直到指数为0.8时才稳定下来。当指数在1以上时视频能稳定地显示结果，而当指数低于1时，则会显得卡顿。

4 结 论

本文对连续不同帧匹配率偏低的问题提出了优化方案，并结合视频进行测试，虽然帧率仍然会出现下降，但随着计算时间的推移逐步趋于稳定，而且由于使用了对象历史特征信息从而能够较好地避免依赖局部区域像素的梯度方向造成过大的误差。同期算法对数据存储空间的要求维持在较高水平，因此可以进一步从同一对象相关特征点的检测、匹配和重复性检测方面进行改进，进一步提高算法效率。

参考文献

[1] BAY H， ESS A， TUYTELAARS T， et al. Speeded?up robust features （SURF） [J]. Computer vision and image understanding， 2008， 110（3）： 346?359.

[2] LOWE D G. Object recognition from local scale?invariant features [C]// Proceedings of 1999 International Conference on Computer Vision. Washington， D. C.： IEEE， 1999： 1150?1157.

[3] 张锐娟，张建奇，杨翠.基于SURF的图像配准方法研究[J].红外与激光工程，2009，38（1）：160?165.

[4] YANG Menglong， LIU Yiguang， CAI Ying， et al. Stereo mat?ching based on classification of materials [J]. Neurocomputing， 2016， 194（C）： 308?316.

[5] ZHOU Zhiyu， WU Dichong， ZHU Zefei. Stereo matching using dynamic programming based on differential smoothing [J]. Optik?international journal for light and electron optics， 2016， 127（4）： 2287?2293.

[6] JIANG Yutong， SUN Changming， TAN Xiao， et al. Orientation?guided geodesic weighting for PatchMatch?based stereo mat?ching [J]. Information sciences， 2016， 334/335： 293?306.

[7] 李建，孔令寅.基于OpenCV的立体匹配算法的研究与实现[J].计算机工程与设计，2013，34（2）：566?569.

[8] 时磊，谢晓方，乔勇军.基于SURF算法的人脸跟踪技术研究[J].计算机仿真，2010，27（12）：227?231.

[9] 包加桐，宋爱国，郭晏，等.基于SURF特征跟踪的动态手势识别算法[J].机器人，2011，33（4）：482?489.

[10] 赵璐璐，耿国华，李康，等.基于SURF和快速近似最近邻搜索的图像匹配算法[J].计算机应用研究，2013，30（3）：921?923.