基于SURF和Camshift的目标跟踪算法研究

李建建，王春阳

（长春理工大学 电子信息工程学院，长春 130022）

近年来，对于运动目标的跟踪一直是机器视觉领域一个关键的研究方向［1］。尽管出现了非常多的方法，但是如何快速有效的跟踪目标，仍然是一个非常值得研究的课题，随着图像处理技术的发展和开源代码的发布使得许多目标跟踪算法得以实现并改进，Camshift［2］算法就是其中一个。

Camshift算法是一种基于颜色直方图信息的半自动跟踪算法，需要人工选取第一帧的搜索窗口，而且只采用HSV颜色模型H通道的颜色信息，当目标发生遮挡或者背景有相似颜色干扰时，该算法容易丢失跟踪目标［3］。David G Lowe等提出的SIFT［4］算法在目标发生旋转、尺度缩放、亮度变化的情况下仍具有良好的鲁棒性，但SIFT算法缺点是计算量大，耗时时间长［5］。Herbert Bay等人对SIFT算法作出改进得到SURF［6］算法，SURF算法鲁棒性好且时间复杂度低，适合实时性要求较高的场合。

针对上述问题，本文给出在Camshift算法基础上结合SURF算法的目标跟踪技术方法。利用SURF特征的位置信息弥补了Camshift只依靠颜色信息的缺陷，提高了目标在发生遮挡或者背景有相似颜色干扰时的跟踪准确性，并具有较强的鲁棒性和有效性。

1 Camshift算法

Camshift算法是一种基于颜色直方图的连续自适应均值漂移算法。设(x,y)为搜索窗口中的像素位置，I(x,y)是概率分布图中(x,y)的像素值，Camshift算法过程如下：

（1）人工确定第一帧搜索窗口；

（2）提取H分量计算出搜索窗口的颜色概率直方图，根据颜色概率直方图，得到新搜索窗口的大小和质心位置，分别计算：

零阶矩：

x、y的一阶矩：

搜索窗口的质心位置：

搜索窗口的宽度s=2M00256；长度l=1.2s；

（3）重复（2），直到质心位置变化小于设定的阈值，或者当循环运算的次数达到设定的最大次数时，就停止运算；

（4）在后一帧视频图像中用（3）中的结果初始化搜索窗口的大小和质心位置，跳转到步骤（2）继续进行目标跟踪。

2 SURF算法

2.1 特征点检测和描述子生成

（1）特征点检测

SURF算法通过计算相关Hessian矩阵并找到尺度空间的极值点来检测特征点。对于图像中某个像素点=(x,y)。箱式滤波同图像卷积后的结果分别设为Dxx、Dxy、Dyy，引入误差参数β，则Hessian矩阵的行列式表示为：

其中，β近似取0.9，当det(H)值为负数时，该点为非极值点；当其值为正数时，该点可能是局部极值点，当局部极值点大于或者小于立体领域其他相邻的26个点时，认为该局部极值点作为立体领域的特征点。

（2）特征点主方向确定

在尺度空间σ下，以特征点为中心，以6σ为半径，分别计算出该区域的每个点在x，y方向的哈尔小波响应（波长为4σ），并给每个响应值赋予相应的高斯权重系数，然后以特征点为中心，用π 3扇形区域范围遍历整个圆形区域，选择其中最长的向量作为该特征点的主方向，对图像中每个特征点进行相同运算，得到每个特征点的主方向。

（3）特征点描述子生成

以特征点为中心，选取一边垂直于主方向边长为20σ的正方形窗口，将该窗口分为4×4的子窗口，计算每个子窗口主方向和垂直方向的哈尔小波响应，分别记为dx、dy，然后对每个子窗口的响应值和响应值的绝对值分别求和表示为∑dx、∑dy、∑|dx|、∑ |dy|，这样每个子窗口形成一个四维分量的矢量V=(∑||dx,∑|dy|,∑|dy|)，每个特征点的描述子则由64维特征向量构成。

2.2 SURF特征匹配定位目标

对于两幅图像中的每个特征点，本文采用快速近似最近邻搜索算法进行匹配［7］。为了验证SURF算法的快速有效性，运用SURF算法和SIFT算法分别对同一组目标模板和视频帧进行特征点、检测描述子生成和特征点匹配，如图1所示。图1（a）为SURF算法的匹配结果，图1（b）为SIFT算法的匹配结果，表1为SURF和SIFT算法的性能比较。

图1 SURF和SIFT算法的匹配结果

表1 SURF和SIFT算法性能比较

从表1可以看出，SURF算法总耗时大约是SIFT算法的1/3，时间复杂度更低，虽然SIFT算法检测出的特征点更多，但是耗时过长，难以满足本文快速定位的要求，所以SURF算法相比SIFT算法更适合用于实时目标跟踪。

图2（a）中，运用SURF算法将目标模板与含有目标的视频帧进行匹配时，可以定位目标，并获得目标质心及大小，图2（b）中，运用SURF算法将目标模板与不含目标的视频帧进行匹配时，未定位出目标位置。由此，在获得目标先验知识的情况下，可利用SURF算法定位目标，继续进行动态目标跟踪。

图2 SURF算法定位目标效果

3 基于SURF和Camshift的目标跟踪算法

首先运用SURF算法将帧图像与目标模板进行特征匹配，计算出目标在帧图像中的位置和大小，并将结果作为Camshift算法第一帧的搜索窗口，然后利用当前帧搜索窗口与目标模板两者之间的颜色概率直方图的Hellinger距离判定跟踪结果是否准确。采用k个bin的颜色概率直方图，目标模板的颜色概率直方图P=(p1,...pk)，当前帧搜索窗口的颜色直方图为Q=(q1,...qk)，则Hellinger距离计算公式为：

两个直方图越相似，则H(P,Q)值越小；两个直方图相差越大，则H(P,Q)值越大［8］。经过多次实验，当H(P,Q)大于0.5时，本文认为跟踪失败，再次运用SURF算法重定位运动目标，将跟踪继续进行下去，如果H(P,Q)小于0.5，则认为跟踪成功，将当前帧的跟踪结果作为目标模板。

基于SURF和Camshift的目标跟踪算法流程图如图3所示。

图3 基于SURF和Camshift的目标跟踪算法流程图

4 实验结果及分析

本算法的实验硬件环境为Intel（R）Core（TM）i7-4710HQ，主频是2.5GHz，8G内存，软件开发环境是Windows7操作系统，Microsoft Visual Studio 2010配置OpenCV库。标准测试视频名为David3，总帧数为252帧。

下面分别使用传统的Camshift算法和本文提出的算法对测试视频进行测试，对比两种算法的跟踪效果，试验中选取黄色上衣男子为跟踪目标并存储为目标模板，如图4所示，选取第176帧，181帧，187帧，195帧作跟踪效果对比。

图4 传统的Camshift算法和本文算法跟踪效果对比

如图4（a）所示，在第176帧中，人工确定的搜索窗口难以收敛到跟踪物体的边缘［9］，而使用本文算法，如图（b）所示，目标的特征点一般位于边缘处，利用目标模板和图像帧进行SURF特征匹配定位目标，并自动快速确定首帧的搜索窗口，减少了其他非目标像素点的干扰；在第181帧中，跟踪目标过程中背景出现相似颜色像素干扰，传统的Camshift算法跟踪窗口发生扩大，本文算法具有较好的跟踪精确性；如图4（a）所示，在187帧中，目标发生遮挡，跟踪窗口误跟踪到与目标有相似颜色的树木，本文算法中检测到目标模板与搜索窗口的颜色概率直方图Hellinger距离大于给定阈值，利用SURF算法将目标模板与图像帧进行特征匹配，将得到的包含目标的最小立式矩形作为Camshift算法的搜索窗口，如图4（b）所示，在第195帧中，本文算法继续对原目标进行有效跟踪。通过图4传统的Camshift算法和本文算法的跟踪效果对比，本文算法具有较好的鲁棒性和有效性。

5 结论

本文提出一种基于SURF和Camshift的目标跟踪算法，验证了SURF算法在实时性要求较高的场合有更好的应用，使用Hellinger距离作为跟踪效果的判定标准，利用SURF算法匹配结果得到特征点的位置、方向信息对Camshift算法进行约束和更新，经过实验证明本文算法具有较强的鲁棒性，可对单目标进行有效实时跟踪。

［1］翟卫欣，程承旗.基于Kalman滤波的Camshift运动跟踪算法［J］.北京大学学报：自然科学版，2015，51（05）：799-804.

［2］HSIEH C J，LUM K Y.Automated image tracking based on the Camshift algorithm with adaboost and target trajectory and size estimation［C］.11th IEEE International Conference on Control& Automation（ICCA），2014：918-923.

［3］修春波，魏世安.显著性直方图模型的Camshift跟踪方法［J］.光学精密工程，2015，23（06）：1749-1757.

［4］Amerini I，Barni M，Caldeli R，et al.Removal and injection of keypoints for SIFT-based copy-move counter-forensics［J］.Eurasip Journal on Information Secutity，2013（1）：1-12.

［5］彭欣，刘富强，宋华军.基于SURF目标跟踪算法研究［J］.长春理工大学学报：自然科学版，2011，34（02）：138-141.

［6］张锐娟，张建奇，杨翠.基于SURF的图像配准方法研究［J］.红外与激光工程，2009，38（01）：160-165.

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

［8］李伟湋，贾修一.基于Hellinger距离的特征选择算法［J］.计算机应用，2010，30（06）：1530-1532.

［9］张宏志，张金换，岳卉，等.基于CamShift的目标跟踪算法［J］.计算机工程与设计，2006，27（11）：2012-2014.