一种改进的Camshift视频目标跟踪算法

王玲玲，裴 东，王全州

(西北师范大学，甘肃兰州730070)

1 引言

运动目标跟踪技术被广泛用于智能视频监控、智能交通控制系统、企业监控等领域［1－2］。然而，用什么样的特征来描述运动目标是实现目标跟踪精度的一个关键问题。

Meanshift算法是一种采用无参估计的方法，操作简单，由Comaniciu等学者引入到了目标跟踪领域［3］中，但和具有模板自适应调整能力的Camshift算法相比，后者应用较为广泛，其在复杂场景中仍存在不足。文献［4］和文献［5］是一种基于边界的边缘匹配方法，该方法的计算量大而繁杂;文献［6］是联合颜色和纹理信息的目标跟踪算法，受光照影响较小，但不能处理目标被遮挡的问题;文献［7］提出了结合LBP纹理特征的运动车辆检测方法，有效克服了外界因素的影响，但存在算法复杂度高的缺点。

传统Camshift算法是一种基于颜色核的目标特征模型，易受周围环境的影响，在目标和背景颜色相近、光照强度变化较大、目标部分或全部瞬间遮挡的情况下，传统Camshift算法不能有效地抵抗各种外界干扰，导致运动目标跟踪效果不理想［8］。然而，不同目标和背景之间的空间结构信息和纹理信息具有较大的差异，且对光线变化不太敏感，因此，充分发挥不同特征之间的互补性，利用梯度方向特征［9］和纹理特征的不同来区分目标和背景。本文在传统Camshift算法的基础上，先将色度直方图、梯度方向直方图和LBP纹理特征进行融合，利用特征联合直方图的方法构建目标的外观特征模型，再结合最大类间方差法［10］进一步改进算法，确定目标和背景的最佳分割阈值，加强目标和背景的区分度。实验表明，改进的Camshift算法具有更高的跟踪准确度和鲁棒性。

2 经典Meanshift目标跟踪模型

Meanshift作为Camshift算法的核心，是一种基于颜色信息的跟踪方法，在目标所在的跟踪区域中，计算所有像素点 {xi}i=1，2，…，n的颜色概率分布作为目标特征模型:

假设上一帧目标的中心用yj表示，将上一帧的中心位置yj作为当前帧的中心，核函数k(x)的带宽不变，计算候选目标内像素点 {xi}i=1，2，…，n'的颜色概率分布:

在跟踪过程中，核函数中心从当前位置yj移动到下一个可能的中心位置yj+1的迭代公式为:

其中，wi为加权系数，g(x)=－k'(x)。

3 基于联合直方图的目标外观特征模型

3.1 色度直方图

鉴于RGB颜色空间对光线变化较敏感，先通过颜色空间转化后，再提取色度直方图，具体步骤如下:

1)将颜色空间转化到HSV格式，提取H分量;

2)计算H通道直方图。假设n个像素点

{xi}i=1，2，…，n的m级直方图为{}u=1，2，…，m，定义b(xi)为像素点 xi的直方图索引，则直方图为

3)直方图尺度转换。像素从［0，max(q)］转换为［0，255］的函数表达式为:

原图像通过转换后，像素值由u变化成pu。

3.2 梯度方向直方图

梯度方向反映了目标邻域内的灰度增加趋势，而梯度差异［11］通常在物体重叠的边缘处较大，计算如下:

其中，f(h，w)为像素点的位置;d(h，w)表示梯度;θ( h，w)表示方向;dx为水平方向的梯度;dy为垂直方向的梯度。

以α度为单位将梯度方向划分为［360/α］级，为了减小目标区域图像边界噪声的影响，用带宽为h1的剖面函数k()·:[0，+!]→R进行平滑处理，得到梯度直方图的公式为:

3.3 简化的LBP纹理算子

局部二元模式(LBP)算法计算简单，是描述目标局部纹理特征的较好方法。以 c为中心点，( P ，R)为邻域的LBP算子定义如下:

其中，gc为中心像素点(xc，yc)的灰度值;gi表示等间隔落在以点(xc，yc)为圆心、半径为R的圆周上的P个点对应的像素值，把P位二进制编码进行首尾相连，统计P位二进制编码从1到0和0到1的次数为:

当P=8，R=1时，LBP算子共产生256种二进制编码，其中，U＞2的为198种，U=0或2的为58种。

为了提高后续的处理速度，利用Ojala提出的“统一模式”来降低LBP纹理特征的维数，把U＞2的二进制编码划分为一类，将U=0或2的LBP编码中1的数量相同的编码划分为一类。因此，256种LBP纹理被压缩为(P+2)种，文献［12］给出了LBP统一模式的定义:

3.4 联合直方图的目标外观特征模型

则式(3)中候选目标区域内像素点{xi}i=1，2，…，n'的联合特征概率分布为:

4 Camshift算法的进一步改进

最大类间方差法可用来确定目标和背景的分割阈值，若目标或背景的部分被错分时，都会导致目标和背景的区分度下降，因此，在Camshift算法中嵌入最大类间方差法确定跟踪目标和背景的最佳阈值，达到增强目标和背景区分度的效果。

针对图像f(x，y)，假设图像的大小为M ×N，T为前景(即目标)和背景的阈值，w0是目标区域像素点数占图像的比例，u0是灰度平均值，w1是背景像素点数占图像的比例，u1是灰度平均值，则目标和背景占整幅图像的比例为:

假设N0和N1分别表示灰度值小于和大于阈值T的像素个数，则有:

计算总平均灰度u和类间方差g的公式为:

根据式(18)和式(19)对式(20)进行简化后的等价公式为:

根据遍历法，当方差g最大时，可以认为目标和背景之间的区分度最大，此时，T为最佳阈值。

运动目标跟踪的步骤如下:

1)初始化目标模型:计算选定目标区域的联合直方图，用式(13)计算目标的候选概率模型{}u=1，2，…，m'，为目标的初始位置。

2)读入下一帧图像，计算特征的联合直方图，根据式(14)得到目标候选模型()。

3)计算零阶矩、一阶矩和搜索窗的质心(xc，yc):

4)重新调整搜索窗的大小S:

5)将窗口中心移到质心位置，若移动距离小于某一阈值，停止当前帧的迭代，转到2);否则，重新调整目标位置，转到3)，继续当前帧迭代。

5 实验仿真结果与分析

本文算法的硬件测试平台为2.8GHz CPU，4G RAM，Windows 32位操作系统的PC机，软件实现平台为 Visual Studio 2010 和 Opencv2.3.1。

图1是对文献［13］中的DATASET2标准视频利用传统Camshift算法、文献［14］算法、本文算法进行目标跟踪处理的结果。其中，图1(a)、1(b)、1(c)和1(d)中的三帧图像依次为第324、366和417帧，跟踪目标为运动小车，图1(a)是未进行目标跟踪时的图像。

在图1所示的跟踪过程中，当运动目标未遮挡时，三种算法都能完成运动小车的跟踪，其中本文算法的跟踪精度最高;当运动小车靠近相近颜色的树木时，图1(b)中的传统Camshift算法跟踪偏移量较大，目标定位不准确，图1(c)中的文献［14］算法虽然能够继续进行目标跟踪，但跟踪框变大，跟踪精度明显降低;当运动目标被树全部遮挡后，传统Camshift算法和文献［14］算法都出现了目标跟踪丢失现象，和前两种算法相比，图1(d)中的本文算法，不仅能够准确地跟踪目标，而且克服了相似颜色的干扰和目标的遮挡，未出现目标跟踪丢失，仍准确跟踪。

图1 三种算法在PEST2001视频上的比较Fig.1 Comparison of three algorithms in PEST2001 video

在视频跟踪过程中，第314、318、324、372 和412帧的目标轨迹如图2所示。

图2 目标轨迹图Fig.2 The tracks of targets

曲线1是目标的实际运动轨迹，曲线2、3、4分别为本文算法、文献［14］算法、传统Camshift算法对应的目标跟踪轨迹，从图2中的曲线3和曲线4可看出，目标未遮挡时，两种算法的跟踪误差较小，目标被遮挡后，曲线4出现明显的目标跟踪丢失现象，曲线3虽然跟踪目标未丢失，但跟踪偏差较大，从图2中的曲线2可看出，本文算法的跟踪轨迹和目标的实际运行轨迹基本一致，可以准确地进行目标跟踪。

在上述跟踪过程中，三种算法的性能比较如表1所示，其中准确率是指跟踪目标的准确度，用公式描述如下:

其中，DM为跟踪到的运动目标的像素点数;NM为未跟踪到的运动目标像素点数。

表1 三种算法的性能比较Tab.1 Performance comparison of three algorithms

为了进一步体现本文算法的优势，现分别采集具有颜色干扰、光照变化和瞬间遮挡时的连续1200帧视频图像为样本，分别用三种算法测试目标跟踪的准确率，其中准确率是指跟踪目标的准确度，结果见表2。

表2 三种算法在外界干扰情况下的性能比较Tab.2 Performance comparison of three algorithms under environmental disturbanct

从表2可以看出，在相似颜色干扰情况下，本文算法的准确率为98.7%，传统Camshift算法的准确率为57.0%，文献［14］算法的准确率为 92.3%;在光照发生变化的情况下，本文算法的准确率为98.9%，传统 Camshift算法的准确率为75.0%，文献［14］算法的准确率为87.2%;在目标存在瞬间遮挡的情况下，本文算法的准确率为96.5%，传统Camshift算法的准确率为55.9%，文献［14］算法的准确率为69.1%。

6 结论

本文提出的基于多特征联合直方图和最大类间方差法的目标跟踪算法，有效地解决了算法应对光照变化、同色干扰和目标遮挡的问题。虽然增加了算法的复杂度，但处理速度较快，跟踪准确度也有了明显提高。

［1］ S Saravanakumar，A Vadivel Saneem，C G Ahmed.Multiple human object tracking using background subtraction and shadow removal techniques［C］.The International Conference on Signal and Image Processing(ICSIP)，2010.

［2］ SUN Shaoyuan，GU Xiaojing，GE Man，et al.Pedestrian detection and tracking of vehicle infrared images［J］.Laser＆ Infrared，2012，42(8):949－953.(in Chinese)孙韶媛，谷小婧，戈曼，等.车载红外图像的行人检测与跟踪技术［J］.激光与红外，2012，42(8):949－953.

［3］ LIU Qing，TANG Linbo，ZHAO Baojun.Algorithm of target tracking based on Mean Shift with adaptive tracking window［J］.Journal of Systems Engineering and Electronics，2012，34(2):409－412.(in Chinese)刘晴，唐林波，赵保军.跟踪窗自适应的 Mean Shift目标跟踪算法［J］.系统工程与电子技术，2012，34(2):409－412.

［4］ Rucklidge W J.Efficiently locating objects using hausdorff distance［J］.International Journal of Computer Vision，1997，24(3):251－270.

［5］ HUANG Fuzhen，SU Jianbo.Abstracting and tracking of outline of face based on level set method［J］.Computer transaction，2003，26(4):491－496.

［6］ WANG Baoyun，FAN Baojie.Adoptive meanshift tracking algorithm based on the combined feature histogram of color and teature［J］.Journal of Nanjing University of Posts and Telecommunications，2013，33(3):18－25.(in Chinese)王保云，范保杰.基于颜色纹理联合直方图的自适应Meanshift跟踪算法［J］.南京邮电大学学报:自然科学版，2013，33(3):18－25.

［7］ SONG Xiaolin，WANG Wentao，ZHANG Weiwei.Vehicle detection and tracking based on the Local Binary Pattern texture and improved camshift operator［J］.Journal of Hunan University:Natural Sciences，2013，40(8):52－57.(in Chinese)宋晓林，王文涛，张伟伟.基于LBP纹理和改进Camshift算子的车辆检测与跟踪［J］.湖南大学学报:自然科学版，2013，40(8):52－57.

［8］ Exner D.Fast and robust camshift tracking［C］//2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington，DC:IEEE Computer Society，2010:9－16.

［9］ FENG Jun，LIANG Xiaoxia，MU Zhichun.Ear recognition with histogram of oriented gradient feature［J］.Journal of Nanjing University:Natural Sciences，2012，48(4):452－458.(in Chinese)封筠，梁晓霞，穆志纯.梯度方向直方图特征的人耳身份识别方法［J］.南京大学学报:自然科学版，2012，48(4):452－458.

［10］ WANG Yingying，HE Ping，LI Yongbin，et al.Fast IR target－detecting method using Otsu algorithm based on bound histogram［J］.Laser ＆ Infrared，2014，44(5):577－581.(in Chinese)王莹莹，何苹，李永宾，等.基于属性直方图的快速Otsu红外目标检测算法［J］.激光与红外，2014，44(5):577－581.

［11］ WANG Qin，JIANG Shuhong，ZHANG Jianqiu，et al.An approach to improve the performance of Mean－shift tracking algorithm［J］.Journal of Fudan University:Natural Science，2007，46(1):85－90.(in Chinese)汪沁，江淑红，张建球，等.提高Mean－shift跟踪算法性能的方法［J］.复旦学报:自然科学版，2007，46(1):85－90.

［12］ Ojala T，Valkealahti K，OJA E，et al.Texture discrimination with multi－dimensional distributions of signed gray level differences［J］.Pattern Recognition，2011，34(3):727－739.

［13］ Performance evaluation of tracking and surveillance 2001(PETS2001)［EB/OL］.http://ftp.pets.rdg.ac.uk/pub/PETS2001/.

［14］ LU Xuan，LEI Hang，HAO Zongbo.Automatic Camshift tracking algorithm based on multi－feature［J］.Computer Applications，2010，30(3):650－652.(in Chinese)卢璇，雷航，郝宗波.联合多特征的自动Camshift跟踪算法［J］.计算机应用，2010，30(3):650－652.