基于Meanshift与Kalman的视频目标跟踪算法

杨红霞，杭亦文，刘 旭

(1.武汉理工大学自动化学院，湖北 武汉 430070;2.武汉大学电气工程学院，湖北 武汉 430072)

对运动目标进行跟踪不仅可以提供目标的运动状态和轨迹，也为运动分析、场景理解等提供可靠的数据来源，在智能监控、突发事件检测等方面有着重要的应用。而图像噪声、天气突变、光照变化、目标运动随机性等复杂的场景，都会给运动目标的跟踪带来困难。近年来，所提出的跟踪方法通常有基于模型的跟踪、基于区域的跟踪、基于活动轮廓的跟踪和基于特征的跟踪等[1]。基于模型的跟踪方法通过对运动目标进行建模，利用视频图像序列确定模型的参数，从而精确分析出目标的运动轨迹[2]。该方法在遮挡或干扰下，性能较好，但几何模型的建立非常困难，计算量大、运行时间长，难以实现实时跟踪;基于区域的跟踪是基于对连续帧中分割出的目标区域建立联系而提出的[3]，对多目标跟踪效果较好，但由于只能获得区域级的跟踪，当目标发生形变或存在遮挡时，就会导致目标跟踪丢失，且费时，无法做到实时跟踪;基于活动轮廓的跟踪则利用目标边界信息来实现跟踪[4]，该方法能有效克服干扰或部分遮挡问题，但其对跟踪的初始化特别敏感;基于特征的跟踪是利用目标的某个或局部特征进行匹配[5]，在目标部分遮挡时，利用部分特征仍能跟踪，常用的特征有目标质心、颜色特征、角点等局部特征。最典型的基于特征的方法是利用颜色特征的Meanshift算法，该方法是一种基于迭代收敛到概率密度的局部极大的非参数估计算法，具有实时性好，易于与其他算法集成，对目标的旋转、变形，以及边缘遮挡不敏感等优点。DORIN[6－7]将其应用于图像滤波、分割和目标跟踪领域，通过对目标模型和后续帧候选区的颜色直方图进行相似性度量而进行跟踪。通过 BRADSKI改进的 CAMSHIFT(continuously apative meanShift)[8]能较好地处理颜色概率分布不断变化的视频序列，但是当场景中运动速度过快或目标间出现遮挡时，物体的特征会因为遮挡无法识别而产生错误的跟踪。这就要求跟踪器必须具有预测功能。针对以上问题，笔者提出了基于Kalman滤波器和Meanshift的视频目标跟踪算法。利用Kalman滤波器的预测估计能力对Meanshift的跟踪结果进行处理，解决了目标跟踪丢失的问题。其改进的算法框图如图1所示。

1 Meanshift跟踪

Meanshift算法利用目标的颜色特征概率密度描述运动目标区域中心位于x的目标模型，在目标中心邻域搜索窗口内以相似性度量最大为原则，寻找最优的位于y的目标模型，使得两次移动距离小于某一阈值，以达到目标的真实位置。笔者采用Bhattacharyya系数度量目标模型u和候选模型u(y)的相似程度。模型根据目标区域颜

图1 改进的算法框图

色特征的概率密度函数来描述:

其中:u为目标的特征值，取值为［1，m］;y为最优候选区域中心。(y)越大，表示两模型越相似。为定位下一帧目标，应使(y)最大化。

将当前帧的候选目标的中心初始为前一帧目标中心y0，然后在其领域内搜索匹配目标，不断地从目标的当前位置y0移动到新目标位置y1，若Meanshift向量y1－y0，‖y1－y0‖ ＜ ε 则停止迭代，使得(y)最大，直到候选区域与目标区域足够相似，此时目标区域中心位置会由y0移动到新的位置y1。

2 Kalman滤波器

Meanshift在目标中心邻域内搜索匹配目标，若目标运动速度过快，或是目标间存在遮挡，会导致跟踪效果不好。笔者引入Kalman滤波器根据以往帧的观测向量预测当前帧的状态向量，由此知道目标可能的位置。Kalman滤波器是一种对动态系统的状态序列进行最小均方误差估计的最优滤波器[9]，它能够预测下一帧区域的中心，并且更正当前帧的目标区域。令状态向量X=(xc，yc)T为目标在x轴和y轴的位置，测量矢量Z=[xc，yc]T为观测目标的位置。首先初始化状态Xi，再以该目标位置作为Kalman滤波器的观测值来进行下一帧的运算。

Kalman滤波器的状态方程和测量方程为:

其中，A为状态转移矩阵;H为测量矩阵;Wi，Vi分别为状态和测量的噪声向量，它们是互不相关的正态白噪声，其方差分别为Q、R。

状态向量预测方程为:

状态向量协方差矩阵预测为:

状态向量更新方程为:

状态向量协方差更新方程为:

Kalman加权矩阵或增益矩阵为:

3 改进的Meanshift与Kalman滤波器跟踪

由于Meanshift跟踪关注的是目标模型和候选模型颜色分布的相似性，当目标重叠过多或背景与目标颜色相近时，Meanshift将不能保证跟踪准确无误。若目标运动速度过快，目标在相邻帧间没有重叠，运动目标可能会收敛于背景中与目标颜色相近的物体，而不是运动目标;或是目标间存在遮挡，利用颜色直方图对运动目标特征进行描述也会导致跟踪效果欠佳。导致跟踪效果不好的原因还可能在于在某些帧中目标的起始位置不理想，若能通过目标以前的运动信息预测到当前帧目标可能位置，然后将这一目标点作为目标的起始位置，就可以在这一邻域内寻找到目标的真实位置。笔者将Kalman滤波器融合进Meanshift跟踪的方法是:当Kalman滤波器作为辅助跟踪时，Meanshift的跟踪结果作为它的测量值，对Meanshift跟踪器产生的跟踪结果具有平滑作用;当Kalman滤波器作为预测器时，当前帧的预测状态中的xc，yc作为测量值，其结果就是保持运动目标的当前运动状态。在当前帧中，通过分析Meanshift跟踪器的跟踪输出得分Score，用以判断是否启动Kalman预测。Score的计算公式如下:

其中，I(x，y)为目标点(x，y)的像素值;R1、R2为前后两帧跟踪目标对应区域;A(R1)、A(R2)分别为R1和R2的面积。设一个门限值T，若Score＞T，表示当前目标和背景分布情况改变不大，Meanshift跟踪效果较好，其结果可输出到Kalman滤波器中，Kalman滤波器在状态更新和测量更新后，输出结果重新回到Meanshift跟踪器中。若Score≤T，Meanshift算法失效，则启动Kalman滤波器的预测功能，不再利用Meanshift跟踪器结果。若T取值过大，Meanshift产生的结果不可信，Kalman滤波器的预测功能容易失效，达不到预测跟踪的目的;若T取值过小，发挥不了Meanshift跟踪器图像匹配跟踪功能，因此，笔者采取了一种折衷方法，取T=0.5，跟踪效果基本满足要求。

4 实验结果及分析

实验硬件平台为Intel P 3.0 G，512 M内存计算机，软件采用Matlab编程环境。选用交通路口场景，大小为160×120，共300帧，帧率为15帧/s。图2是Meanshift算法的跟踪结果[10]。在第62帧以前，Meanshift可以较好地跟踪车和人等运动目标，在62帧以后由于新进来的人车连在一起相互遮挡，存在较多的颜色特征相似的目标，Meanshift无法准确跟踪。图3是利用笔者所提出的算法处理同一段视频序列，加入Kalman作为辅助跟踪器，在第62帧以后，当人车连在一起时，依据对各个Meanshift跟踪器的跟踪输出得分来开启Kalman预测，完成了对各个目标的跟踪。所示的方框为每一帧目标的跟踪结果。实验结果表明，融合Meanshift与Kalman滤波器预测的方法能对目标进行准确跟踪。

5 结论

针对复杂背景下，可能出现的跟踪效果差的问题，提出了一种融合Meanshift跟踪与Kalman滤波器预测的方法用于运动目标跟踪，判断Meanshift的跟踪效果，当跟踪效果良好时，Kalman滤波起到平滑作用;当跟踪效果差时，启动Kalman的预测功能。实验结果表明，所提出的算法能对目标进行准确跟踪，具有良好的抗干扰能力。

图2 Meanshift算法的跟踪结果

图3 改进后算法的跟踪结果

[1] HU W M，TAN T N，WANG L，et al.A survey on visual surveillance of object motion and behaviors[J].IEEE Transactions on Systems，Man and Cybernetics，Part C:Applications and Reviews，2004，34(3):334 －352.

[2] HAAG M，NAGEL H H.Combination of edge element and optical flow estimates for 3D －model－based vehicle tracking in traffic image sequences[J].Inter J Comp Vision，1999，35(3):295 －319.

[3] JORGE B，JOSE M S，FILIBERTO P.Motion based seg－mentation and region tracking in image sequences[J].Pattern Recognition，2001，34(3):661 －670.

[4] BOO H L，II C，GI J J.Motion － based moving object tracking using an active contour[C]//IEEE International Conference on Acoustics，Speech and Signal Processing.[S.l.]:[s.n.]，2006:649 －652.

[5] SAUNIER N，SAYED T.A feature － based tracking algorithm for vehicles in intersections[C]//The 3rd Canadian Conference on Computer and Robot Vision.[S.l.]:[s.n.]，2006:59 －69.

[6] DORIN C，PETER M.Meanshift:a robust approach toward feature space analysis[J].IEEE Transations on Pattern Analysis and Machine Intelligence，2002，24(5):603－618.

[7] DORIN C，VISVANATHAN R，PETER M.Kernel－based object tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(5):264 －577.

[8] BRADSKI G R.Compute vision face tracking for use as a component of a perceptual user interface[J].Worshop on Application of Computer Vision，1998(2):214 －219.

[9] WELCH G，BISHOP G.An introduction to the Kalman filter[EB/OL].[2011 － 09 － 08].http://www.cs.unc.edu/～welch/kalman/2001.

[10] MOTWANI M，TIRPANKAR N.Towards benchmarking of video motion tracking algorithms[J].Signal Acquisition and Processing，2010(2):215 －219.