基于改进帧间差分与局部Camshift相结合的目标跟踪算法

周文静　陈玮

摘要：

为了能够准确、快速地跟踪运动目标，提出了改进帧间差分与局部Camshift相结合的目标跟踪算法。针对传统帧间差分法在运动目标提取过程中容易产生“空洞”的现象，并且对噪声敏感的问题，提出了三帧差分的运动目标检测算法。首先，利用三帧差分法，将相邻的三帧图像作为一组进行再差分，从而检测出中间帧运动目标的形状轮廓，然后将该区域作为运动目标的模板区域，并将该区域进行适当扩充，最后采用局部Camshift算法进行目标跟踪。实验结果表明，改进的帧间差分可以有效地弥补“空洞”现象，对噪声也起到了一定的抑制作用。同时，该方法克服了传统Camshift算法需要人为选择跟踪区域和容易发散的缺点，达到了预期的目标检测和跟踪效果。

关键词：

局部Camshift算法；三帧差分法；目标检测；目标跟踪

DOIDOI：10.11907/rjdk.172531

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）003006704

英文摘要Abstract：The target tracking algorithm based on improved interframe difference and local Camshift were put forward to quickly and exactly track moving object. The three frame difference target detection algorithm is proposed for the traditional interframe difference method， which is prone to “empty” phenomenon in the process of moving object extraction and is sensitive to noise. Firstly， the three frame difference method is used to discriminate the adjacent threeframe image as a group to detect the shape contour of the moving target of the intermediate frame， and the region is used as the template area of the moving object， and the area is appropriately expanded， with local Camshift algorithm for target tracking. Experimental results show that the improved interframe difference can effectively compensate for the “hole” phenomenon， the noise also played a certain degree of inhibition. At the same time， this method overcomes the shortcomings of the traditional Camshift algorithm that requires artificial selection of tracking areas and easy divergence to achieve the desired target detection and tracking.

英文关键词Key Words：local Camshift algorithm； three frame difference； target detection； target tracking

0引言

隨着计算机与通信技术及图像处理技术的发展，计算机视觉已成为目前的研究热点，而运动目标检测与跟踪是计算机视觉研究的核心课题之一[1]。Camshift是一种基于颜色直方图的跟踪算法，利用颜色的相关信息跟踪运动目标。该算法继承了MeanShift算法在实时性和鲁棒性方面的优点[2]，同时可根据上一帧的结果自适应调整搜索窗口位置和大小，从而得到目标在当前帧的位置[3]。

Camshift算法在背景单一，且跟踪目标与背景颜色差别较大时，具有很好的跟踪效果。然而，传统的Camshift算法在目标检测阶段需手动选取跟踪目标，而不能实现目标的全自动检测和跟踪。同时，传统的Camshift算法在反向投影时，需对后续整幅视频图像进行全局计算，增加了额外的计算负担，并且全局计算也会大大降低跟踪质量。比如在亮度不强的区域，反向投影会产生噪声点。

文献[3]提出了帧间差分与Camshift相结合的目标跟踪算法，但帧间差分所提取的目标区域有“空洞”现象，区域信息获取不完整，可能导致跟踪区域发散[3]。针对以上问题，本文提出改进帧间差分与局部Camshift相结合的跟踪算法。

1Camshift目标跟踪算法

Camshift （Continuously Adaptive MeanShift），即连续自适应的MeanShift算法。MeanShift是一种基于梯度计算的均值漂移跟踪算法。在D维空间中，均值移动矢量沿着概率密度增大的方向逐步搜寻，从而得到该空间概率密度的局部最大值。Meanshift算法是在一张指定的图片上计算最优迭代结果，而Camshift是面向连续的视频序列，逐一对每一帧图像进行Meanshift运算，求出最优搜索结果[45]。Camshift算法具体操作步骤如下：

（1）读取视频帧图像，并将该图像由RGB颜色空间转至HSV空间。为了实现色彩空间的降维，需将H（hue）分量分离出来，即由原来的（R，G，B，X，Y）5维降为（H，X，Y）3维，从而减少计算复杂度。

（2）初始化搜索窗，并计算出搜索窗区域的颜色直方图，进行反向投影操作，将原始图像转为色彩概率分布图。

（3）利用MeanShift算法在概率分布图上进行迭代漂移。假设I（x，y）是概率投影图上（x，y）处的像素值，则搜索窗口的零阶距为：

M00=∑x∑yI（x，y）（1）

计算一阶距为：

M10=∑x∑yxI（x，y），M01=∑x∑yyI（x，y）（2）

搜索窗的质心位置为：

Xc=M10M00，Yc=M01M00 （3）

（4）调整搜索窗大小，宽度为：

s=M00256（4）

长度为宽度的1.2s。

（5）将搜索窗的中心移至质心（Xc，Yc）处，如果移动距离大于预设的固定阈值，则重复步骤（3）～（5），直到搜索窗中心与质心间的移动距离小于预设的固定阈值，待其收敛或达到最大迭代次数，得到最终搜索窗口的位置和大小。

（6）读入下一帧图像，根据新得到的搜索窗口参数信息，跳转至步骤（2）继续执行，直至视频播放结束。

2局部Camshift目标跟踪算法

为了克服传统Camshift算法在反向投影时带来的额外计算和噪声点，将算法全局计算改为局部计算[6]，让反向投影限制在搜索窗口内部进行，提出了局部Camshift目标跟踪算法。，该算法有效地改善了Camshift算法的计算量和无关的计算容易让更多无关的物体干扰跟踪算法。局部Camshift算法具体操作步骤如下：①对给定的图像作直方图运算，初始化窗口，设定初始窗口的位置，准备跟踪；②对当前窗口作适当扩充，并计算扩充后窗口的反向投影；③使用Meanshift算法进行迭代，待收敛后，返回跟踪目标的零阶距M00和收敛位置；④以收敛位置为中心建立窗口，由式（4）进行窗口的尺寸计算，并根据计算结果更新窗口大小；⑤将更新的窗口作为下一帧视频图像的初始窗口，并将Meanshift算法的迭代窗口中心重新作为目标初始位置，跳转至步骤（2）继续执行，直至视频播放结束，返回。

3三帧差分算法

3.1三帧差分法原理与框架

三帧差分算法是两帧差分算法的改进算法[7]。该算法的基本原理是对两次帧间差的差分图像再进行相关操作，即将当前帧与前一帧作差分运算，下一帧与当前帧作差分运算，然后对两次差分结果通过选择适当的阈值进行二值化处理，最后将经过二值化处理的两次差分结果再进行逻辑“与”操作[8]。其算法框架如图1所示。

3.2三帧差分法流程

（1）灰度化。输入的视频文件是彩色的，一般采用的是RGB颜色模型。由于三帧差分法是基于像素点的运动目标检测算法，它通过对视频图像序列中的连续三帧图像分别进行相邻的差分运算，判断背景中像素点的灰度值是否发生了变化，然后根据灰度值的变化得到运动目标，所以对输入的彩色视频进行灰度化处理，将彩色图像转化为灰度图像。灰度处理采用YUV与RGB颜色空间变化的方法，如式（5）所示：

Y=0.3R+0.59G+0.11B（5）

（2）分帧处理。从视频序列中t时刻选取连续三帧视频图像，记为Ik-1（x，y）、Ik（x，y）、Ik+1（x，y），分别表示前一帧、当前帧和后一帧图像。其中，x、y是像素位置。

（3）差分处理。分别计算相邻两帧图像的差值：

diff1（k，k-1）（x，y）=|Ik（x，y）-Ik-1（x，y）|（6）

diff2（k+1，k）（x，y）=|Ik+1（x，y）-Ik（x，y）|（7）

因為视频帧与帧之间时间间隔较短，而运动目标的运动速度不快，所以可以对运动目标进行准确定位[9]。因此，采用此算法进行目标定位。实验中，选取视频序列Car中连续的3帧图像，分别为第7帧、8帧和9帧。差分实验如图2所示。

（4）二值化。通过选择合理的阈值T，对得到的差值图像进行二值化处理，如式（8）、式（9）所示：

g1（k，k-1）（x，y）=255，diff1（k，k-1）（x，y）≥T0， diff1（k，k-1）（x，y）

g2（k+1，k）（x，y）=255，diff2（k+1，k）（x，y）≥T0， diff2（k+1，k）（x，y）

其中，T为设定阈值，g1（k，k-1）（x，y）、g2（k+1，k）（x，y）为二值化处理结果。

阈值的选择采用最佳阈值法，即迭代法[10]。它是一种不断用变量的旧值递推新值的过程，即无限趋近于“真值”的过程[11]。迭代阈值的获取步骤归纳如下：

步骤1：选择适当的初始阈值T（j），一般情况下可以选取整幅图像的平均灰度值作为迭代的初始阈值，j为总迭代次数，初始化时j=0。

步骤2：用T（j）分割图像，将图像分为2个区域C（j）1和C（j）2。

步骤3：计算两区域的平均灰度值，其中N（j）1、N（j）2为第j次迭代时区域C1和C2的像素点个数，f（x，y）表示图像中（x，y）点的灰度值。

u（j）1=1N（j）1∑f（x，y）∈C（j）1f（x，y）（10）

u（j）2=1N（j）2∑f（x，y）∈C（j）2f（x，y）（11）

步骤4： 计算新的门限值，即：

T（j+1）=u（j）1+u（j）22（12）

步骤5：令j=j+1，重复步骤2-4，直到T（j+1）与T（j）的差小于规定值或j达到最大的迭代次数。

（5）与运算。通过与运算提取二值化图像的交集，从而得到运动目标前景图像[12]：

X=g1（k，k-1）（x，y）g2（k+1，k）（x，y）（13）

其中，*为与运算。

（6）腐蚀与膨胀。对获得的二值图像进行形态学的腐蚀与膨胀操作。腐蚀的作用是为了消除干扰点或噪声点，使跟踪目标变小，从而消除小于结构元素的点[13]。而膨胀的作用是将与目标接触的所有背景点合并到目标上，使目标增大，可弥补目标的“空洞”现象[14]。实验如图3所示。

4三帧差分与局部Camshift算法相结合

利用三帧差分可以检测出运动目标区域，然后利用局部Camshift算法进行目标跟踪[15]，具体操作步骤如下：

（1）读取视频帧序列，将第一帧图像拷贝给pre_frame，再将第二帧图像拷贝给frame，并分别进行灰度化处理，记为pre_gray，fra_gray。

（2）将第三帧图像拷贝给next_frame，并进行灰度化处理，记为next_gray。

（3）将第一帧灰度图像pre_gray与第二帧灰度图像fra_gray进行差分运算，得到差分图像，记为gray_image1；第二帧灰度图像fra_gray与第三帧灰度图像next_gray进行差分运算，得到差分图像，记为gray_image2[16]；最后，对gray_image1和gray_image2进行二值化处理，通过迭代法选择适当的阈值T，得到大于阈值T的像素点个数，进而判断是否已检测到目标。

（4）若得到的像素点个数大于预先设置好的个数，则表示此时已检测到跟踪目标，然后求取这些像素点的最小外接矩形，并在此基础上对得到的矩形进行适当的外扩处理。此时，即完成了运动目标检测。

（5）再对gray_image1和gray_image2进行与运算，得到大于阈值T的中间帧二值图像，记为gray_image。为了消除边缘和噪声对目标的干扰，本文采用图像形态学中对二值图像腐蚀和膨胀的方法解决这个问题[17]。

（6）对检测出的运动目标区域采用局部Camshift算法进行跟踪，同时，将第二帧拷贝给第一帧，第三帧拷贝给第二帧，读取下一帧，跳至步骤（2）执行，直至视频播放结束，返回。

5实验与仿真

本次仿真实验是在处理器型号为 Intel Corei5-2430M，主频2.40GHz，内存4GB，操作系统为Windows 7专业版的PC机上使用Visual Studio2015以及OpenCV 3.2.0版本实现的。

如图4、图5所示是一组汽车行驶视频序列，选取汽车作为跟踪目标，跟踪结果显示在蓝色矩形框内。画面中，周围小草的颜色与汽车颜色相似，因而对跟踪目标有一定干扰。视频序列是从第1帧开始框选跟踪目标。图4采用传统的帧间差分与Camshift相结合的跟踪算法，图5采用改进的帧间差分与局部Camshift相结合的跟踪算法。从图5可以看出，改进的跟踪算法在跟踪过程中可以保证跟踪目标整体上的完整性（彩图见封二）。

如图6、图7所示，类似于摄像头监控下的视频序列，选取人作为跟踪目标。第26帧为相对静止的场景，无运动目标。从图6可以看出，传统跟踪算法在第85帧和117帧出现跟踪目标大部分缺失的情况，而改进的跟踪算法表现出较好的跟踪性能（彩图见封二）。

仿真实验结果表明，改进的跟踪算法具有更好的跟踪效果，跟踪准确度得到明显提高。同时，局部Camshift大大降低了算法的计算复杂度，使跟踪速度得到明显提高。

6结语

本文在传统Camshift跟踪算法的基础上，提出了基于改进帧间差分与局部Camshift相结合的目标跟踪算法[17]。通过三帧差分对运动目标进行了很好的定位，有效避免了帧间差分带来的“空洞”現象，克服了传统Camshift算法需人为框选跟踪区域和易发散的缺点，实现了一种全自动的目标跟踪。局部Camshift算法使目标跟踪速度得到很大提高，降低了计算复杂度。但在特定场景下，本文算法也存在一定局限，比如跟踪目标运动速度过快时，易于出现跟踪丢失的情况等[18]。随着深度学习的迅速发展，利用深度学习进行目标跟踪，是目前该领域的一个研究热点，如何使用该方法提高跟踪效果是接下来的研究方向。

参考文献参考文献：

[1]尹红娟，栾帅.三帧差分运动目标检测算法分析与验证[J].计算机与数字工程，2017，328（1）：6971，87.

[2]张春林，李小坚.基于帧间差分和背景差分结合的Camshift目标跟踪算法[J].工业控制计算机，2014，27（6）：118120.

[3]张宏志，张金换，岳卉，等.基于Camshift的目标跟踪算法[J].计算机工程与设计，2006，27（11）：20122014.

[4]汤泉.基于AdaBoost和Camshift的人脸检测与跟踪[J].电子科技，2016，29（12）：166169.

[5]储珺，杜立辉，汪凌峰，等.基于局部背景感知的目标跟踪[J].自动化学报，2012，38（6）：19851995.

[6]刘毅，楚杨杰.局部Camshift跟踪算法[C].武汉：武汉理工大学，2007：2829.

[7]XIAOWEI HAN，YUAN GAO，ZHENG LU，et al. Research on moving object detection algorithm based on improved three frame difference method and optical flow[C].Fifth International Conference on Instrumentation and Measurement， Computer， Communication and Control，2015.

[8]HONGKUN LIU，JIALUN DAI，RUCHEN WANG，et al. Combining background subtraction and threeframe difference to detect moving object from underwater video[C]. Oceans， 2016：15.

[9]HONGXIA CHU，SHUJIANG YE，QINGCHANG GUO，et al. Object tracking algorithm based on Camshift algorithm combinating with difference in frame[C]. International Conference on Automation and Logistics，2007.

[10]周帅，秦明伟，侯宝临.结合局部差分的CamShift动目标跟踪算法[J].自动化仪表，2017，38（2）：14.

[11]司艳丽.胶体推进剂燃烧特性的图像分析技术[D].南京：南京理工大学，2011：3435.

[12]刘红，周晓美，张震.一种改进的三帧差分运动目标检测[J].安徽大学学报：自然科学版，2014，38（6）：5559.

[13]丁亚军，谢可夫.改进型中值滤波和形态学组合降噪方法[J].计算机与现代化，2007，138（2）：4142，45.

[14]杜厚鹏，卢官明.基于监控视频的运动车辆检测与违章分析[D].南京：南京邮电大学，2014：1315.

[15]杨杰，穆平安，戴曙光.一种改进Camshift算法的研究[J].计算机应用与软件，2014，31（2）：167170.

[16]李萌，郑娟毅，门瑜.基于帧差法的运动车辆阴影去除算法[J].电视技术，2016，40（10）：1114.

[17]初紅霞，宋起超，王希凤，等.基于帧间差分与Camshift相结合的目标跟踪算法[J].弹箭与制导学报，2008，28（3）：8588.

[18]赵春晖，包玉刚，姚冰.基于Kim与Camshift结合的运动目标跟踪算法[J].黑龙江大学自然科学学报，2010，27（1）：126130.

责任编辑（责任编辑：黄健）