基于均值漂移的自适应跟踪算法

韦 迅，卢志茂，孙 海

(哈尔滨工程大学信息与通信工程学院，哈尔滨150001)

目标跟踪广泛应用于区域监控、交通控制、视频压缩和人机交互等领域.如何对视频中感兴趣的目标进行实时有效地跟踪是目标跟踪的重点和难点.目标在运动过程中存在着遮挡、放大、缩小、旋转等情况，同时目标运动的环境中也会存在多种干扰，这就对跟踪算法提出了很高的要求，不仅要求计算量小来满足实时跟踪，还要求适应目标和环境的变化.

由Fukunaga等人于1975年在文献[1]中提出的均值漂移是一种高效的目标跟踪算法，Yizong Cheng对该算法进行了改进，Comaniciu等人把它应用于目标跟踪中.均值漂移算法具有特征稳定，能部分抗干扰，受目标形状变化影响小，能实现实时跟踪等优点，因此在目标跟踪中得到广泛应用.窗口宽度的选择影响到算法的计算量，从而影响到跟踪的实时性及有效性，因此，跟踪算法中的核函数的窗口宽度对目标跟踪起着关键作用.均值漂移跟踪算法是个半自动跟踪算法，其核函数的窗口宽度是人为决定的，即在初始帧中选定跟踪窗口宽度，且在目标跟踪过程中宽度不变.当目标变小时，跟踪窗口相对较大，导致跟踪窗口内背景区域过多使跟踪效果变差;当目标变大时，跟踪窗口相对较小，跟踪窗口内的信息就减少，从而不能有效地进行跟踪甚至导致目标消失.文献[2]提出了对跟踪框加减百分之十增量的方法，即在当前帧中分别选择相对于前一帧跟踪窗口的90%、100%、110%来独立计算Bhattacharyya系数，选择最大的Bhattacharyya系数所对应的窗口作为本帧中的跟踪窗口.当目标变小时该算法对于跟踪效果较好，但是目标变大时，跟踪窗口不仅不会变大，反而经常变小，这是由Bhattacharyya系数的性质决定的，它往往在跟踪窗口较小时较大.文献[3]基于Lindeberg理论，结合联合DOG算子和Epanicinikov核，在跟踪过程中不断用DOG算子和搜索窗作卷积，运算量非常大，影响了算法的实时性.文献[4]利用角点匹配来选取核窗宽，不适合跟踪目标变小及目标运动过快的情况.文献[5]采用均值漂移和连续两帧中匹配窗口的最大相关系数来得到变换参数，同样计算量大，很难满足实时性要求.文献[6]使用不变矩的带宽估计方法，但矩阵特征的计算量大，影响跟踪的实时性.文献[7]提出一种基于运动矢量分析的均值漂移算法，但是需要特定的硬件来支持.文献[8]提出基于SIFT匹配的跟踪算法，但是非常依赖目标图像的内容和质量.

本文针对现有算法的缺陷，提出了一种基于均值漂移自适应跟踪算法，根据候选目标边缘加权直方图与模板中心加权直方图计算出Bhattacharyya系数，通过Bhattacharyya系数来判断目标变化情况.若目标变小或不变，则根据Bhattacharyya系数来确定目标缩小的比例;若目标变大，则采用形心定位和特征点仿射模型对跟踪窗口进行更新.实验表明，该算法能有效、实时地跟踪大小变化的目标.

1 均值漂移算法

1.1 均值漂移向量

均值漂移算法是一种非参数概率估计算法，通过迭代的方式使每一个点朝着概率密度较大的方向移动.在d维的空间中，设x是其中的一个点，则其概率密度为:

均值漂移向量为:

其中:g(x)=－k'(x)为轮廓函数，当g(x)=1时，式(2)为:

图1中的黑点为核函数的中心点，用x表示，周围的白点为xi，图中的箭头表示核函数的中心点与样本点之间的偏移向量，样本点越密的区域箭头越多，平均偏移量就会指向该区域，也就是梯度方向表示每个采样点的权值.

图1 均值漂移向量示意图

1.2 均值漂移跟踪算法

均值漂移算法是一种半自动跟踪算法，它以人工的方式画出所要跟踪的窗口.

1)目标模型

假设选中的目标区域中心为x0，其中有n个像素，分别是{xi}i=1，…，nu=1，…，n，特征值的个数为m，分别为u=1，…，m，则目标特征值的概率密度函数估计为:

2)候选目标模型

候选目标区域的中心坐标为y，和目标模型同样的道理，计算候选目标特征值的概率密度函数估计为:

3)Bhattacharyya函数计算相似度

均值漂移跟踪算法是基于颜色直方图特征来进行跟踪的，使用相似性函数描述目标模型和候选目标之间的相似度.相似性函数有很多种，如Fisher linear discrimant，直方图交集，Bhattacharyya 函数等，通常我们选用Bhattacharyya函数来判断相似性，其定义为:

4)目标定位

这样目标中心就从上一帧的y0移动到下一帧的y1，即移动到和原来目标模板最相似的区域.

2 带宽自适应均值漂移算法

2.1 Bhattacharyya系数计算

均值漂移中的核函数是凸函数，表示靠近中心点所占的权重较大，边缘的权重较小，这样对边缘具有较好的抑制，有利于目标跟踪的稳定性，函数的定义如下式所示:

边缘对判断目标的缩放起着重要的作用.边缘所占的权重越大，则中心点占的权重越小，核函数变为下式:

目标模板特征值中心加权概率密度估计qd可由式(6)和(9)得出，目标模板特征值边缘加权概率密度估计qe可由式(6)和(10)得出，根据qd和qe可以得出模板自身的Bhattacharyya系数为ρde=跟踪窗内特征值边缘加权概率密度估计pe由式(6)和(10)得出，由此可以计算出候选目标与模板Bhattacharyya系数为

1)当 ρde＞ ρ'de时，目标变小.

2)当 ρde= ρ'de时，目标大小不变.

3)当 ρde＜ ρ'de时，目标变大.

2.2 目标变小时跟踪窗口的调整

设当前帧的两个窗宽分别为h1=hprev、h2=hprev+Δh，其中:Δh=0.1hprev，hprev为前一帧窗宽，通过均值漂移算法来计算当前帧两个窗宽所对应的Bhattacharyya系数，最大的Bhattacharyya系数所对应的窗宽为hopt，为了避免跟踪窗口的改变过于敏感，改变后的跟踪窗宽如下式所示:

其中:式(11)中 β 的值为0.3.

以 hnew为跟踪窗口再次计算 ρ'de，当 ρde＞ ρ'de，则跟踪窗口小于目标，按照以上步骤重新计算窗宽，直到 ρde＜ ρ'de.

2.3 目标变大或不变时跟踪窗口的调整

目标变大时的跟踪，首先对跟踪目标形心进行定位，然后通过相邻两帧中特征点和匹配计算出变大的后的窗口大小.

设Oi为第i帧目标形心，ci为i跟踪窗口的中心，当目标增大时i+1帧目标形心和跟踪窗口中心分别为Oi+1和Ci+1，则目标形心和跟踪窗口中心偏移量d=ci+1－oi+1，因此要通过d来补偿空间定位的偏移.第i帧到第i+1帧视频中，目标是逐渐变大的，根据后向跟踪方法，从第i+1帧到第i帧，目标是逐渐变小的，均值漂移跟踪算法对缩小的目标能够很好的跟踪其形心，且目标形心与跟踪窗口中心重合，即采用后向跟踪方法得到的跟踪窗口中心c'i+1就是在第i帧用均值漂移跟踪算法找到的目标形心，这样就存在另外一个偏移量d'=c'i+1－ci，由于视频中目标运动速度不是很快，所以d'近似等于d.这样目标的形心位置就是:

目标尺度的变化是通过仿射模型和特征点匹配的方法算出的.首先在候选目标窗口内检测目标测角点，然后通过归一化交叉相关法得到相邻两帧的匹配特征点对，根据仿射变换原理，特征点对满足下式:

其中:ex和ey分别是x轴和y轴上的平移分量，sx和sy分别为x轴和轴y上的伸缩幅值.跟踪窗口的宽度可由下式进行更新:

角点能够很好的刻画出跟踪目标的空间结构，且比较容易检测，因此，选用匹配角点作为样本来对仿射模型参数进行估算.

3 实验结果及分析

为了验证算法的有效性以及实时性，采用传统固定核窗宽的均值漂移跟踪算法和本文提出的算法对目标逐渐增大和目标逐渐减小的车辆视频序列进行实验分析.视频帧数是40，周围环境为校园马路，测试环境为Windows XP系统，内存1 G，编程工具Matlab2010a.跟踪实验结果如图2、图4所示.

图2 本文算法与均值漂移跟踪算法结果对比

图2所示为跟踪目标变大时跟踪实验结果的对比图.其中，图2(A)中图像序列是使用固定核窗宽对目标增大时的跟踪效果.可以看出跟踪效果不理想，由于跟踪框不变，当跟踪目标增大时，跟踪框相对较小，跟踪的尺度就会产生偏差，且空间的定位也不准确.图2(B)中图像序列为本文提出的采用形心定位和特征点仿射模型对目标增大时的跟踪效果，从图2中可以看出，跟踪窗口随着目标的增大及时、有效地更新，跟踪窗口随之变大，且空间定位也很准确，解决了文献[2]方法对目标增大时跟踪窗口有时反而缩小的不足.跟踪的效果如图3所示.

图3 几种算法所得目标尺度与目标实际尺度对比

图4 本文算法与均值漂移跟踪算法结果对比

图4所示为目标缩小时跟踪实验结果的对比图.图4(A)中图像序列是使用固定核窗宽对目标缩小时的跟踪效果，从图4中可以看出空间定位准确，但是跟踪的视觉效果欠佳，跟踪框不能随着目标的缩小而响应缩小，导致计算量相对较大，影响跟踪的实时性.图4(B)中图像序列为使用本文跟踪算法对目标缩小时的跟踪效果，从图4中可以看出，随着跟踪目标尺寸逐渐缩小，跟踪窗口尺寸也能及时、有效地随之变小，且空间定位也很准确，能够很好的满足跟踪的有效性，而且在时间复杂度上本文算法也具有很大的优势.时间复杂度是通过算法中迭代循环次数算出，如表1所示.

表1 时间复杂度分析

4 结语

本文针对传统的均值漂移跟踪算法不能很好的缩放跟踪目标的缺陷，提出了自适应跟踪改进算法.通过边缘概率密度来判断目标的缩放，如果目标是缩小的，则通过Bhattacharyya系数来对跟踪窗口的更新，如果目标是增大的，则通过后向跟踪的方法对跟踪窗口的更新.通过跟踪实验表明，本文提出的算法对提高均值漂移跟踪算法的适应性有重要意义，有效地解决了尺度变化的目标定位困难和跟踪窗口更新的问题.但是本算法不适合对遮挡情况下的目标跟踪，遮挡情况下目标缩放的自适应跟踪是进一步需要研究的问题.

[1] FUKUNAGA K，HOSTETLER L D.The estimation of the gradient of a density function，with applications in pattern recognition[J].IEEE Trans.On Information Theory，1975，21(1):32 －40.

[2] COMANICIU D，RAMESH V，MEER P.Kernel－based object tracking[J].IEEE Trans.on Pattern Analysis and Machine Intelligence，2003，25(5):564 －577

[3] COLLINS R.Mean－shift blob tracking through scale space[C]//IEEE International Conference on Computer Vision and Pattern Recognition Baltimore，Victor Graphics:IEEE press，2003:234－240.

[4] 彭宁嵩，杨 杰，刘 志，等.Mean－Shift跟踪算法中核函数窗宽的自动选取[J].软件学报，2005，16(9):1542 －1550.

[5] 朱胜利，朱善安.核函数带宽自适应的Mean－shift目标跟踪算法[J].光电工程，2006，33(8):11 －16.

[6] BRADSKI G R.Computer vision face tracing for use in a perceptual user interface[J].Intel Technology Journal，1998，2:1 －15.

[7] 田 刚，胡瑞敏，王中元.一种基于运行矢量分析的 Mean shift目标跟踪算法[J].中国图像图形学报，2010，15(1):85－90

[8] HU X L，TANG Y C，ZHANG Z H.Video object matching based on SIFT algorithm[C]//International Conference on Neural Networks and Signal Processing(ICNNSP)，[S.l.]:[s.n.]，2008:412－415.