改进的Meanshift运动目标跟踪算法

张　英，车　进，牟晓凯，白雪冰

(宁夏大学 物理电气信息学院，宁夏 银川 750021)



改进的Meanshift运动目标跟踪算法

张英，车进，牟晓凯，白雪冰

(宁夏大学 物理电气信息学院，宁夏 银川 750021)

Meanshift算法在对快速运动的目标进行跟踪时容易丢失目标，并且在目标被遮挡时，也容易造成跟踪失败，跟踪的过程中跟踪框不能随着运动目标的大小变化而变化。提出一种基于Meanshift运动目标跟踪算法的改进算法。该算法基本思想是采用改进的三帧差分法对运动目标区域进行提取，求得跟踪框轮廓，同时用Meanshift算法对运动目标进行跟踪，获得目标最大概率区域，将该区域中心作为跟踪框的中心。跟踪过程中通过巴氏系数判断是否目标被遮挡，若被遮挡则调用Kalman滤波进行预测跟踪。实验结果表明，该算法能够快速、准确地跟踪目标。

三帧差分；Meanshift；运动目标跟踪；Kalman滤波

智能视频监控系统如今被广泛应用，它是计算机视觉领域中近些年来新兴起的一个研究方向。它主要是利用计算机视觉技术对采集到的视频图像信号进行处理、分析和理解，得到关键信息从而对视频监控系统进行控制，提高视频监控系统数字化水平。跟踪运动目标可以获得运动目标的运动状态和轨迹，同时为更高级别的处理提供可靠的数据。由于噪声的存在、天气的变化、目标的无规则运动等都会给准确跟踪带来很多问题。对运动目标跟踪的完整性和准确性主要取决于对跟踪算法的选取。2002年Dorin Comaniciu采用Meanshift算法跟踪运动目标，缩短了跟踪时间，计算难度也降低了。Meanshift算法主要是基于无参数密度估计对运动目标进行跟踪，该算法通过计算目标模型和候选模型的核密度直方图来比较它们的相似程度，运动目标形状的改变对颜色直方图影响不大[1]。因此，Meanshift算法对运动目标尺度变化有较好的适应性[2]。但是当运动目标运动速度过快或目标被遮挡的情况，Meanshift算法就没有办法准确地跟踪运动目标，往往容易跟丢，这就需要跟踪算法必须具有预测能力。本文提出了一种基于Meanshift算法的目标跟踪改进算法，该算法结合了三帧差分检测运动目标和Kalman滤波器对Meanshift算法进行改进，改进算法的优点在于可以使跟踪框自适应变化，并且当目标被遮挡之后也能很准确地跟踪运动目标。

1　三帧差分算法原理

传统帧间差分或者三帧差分得到的运动目标都存在一定的缺点，获得的运动目标不完整，特别是对于缓慢运动的目标会存在大量的空洞。本文采用一种改进的三帧差分算法确定运动区域[3]。该算法首先用Surendra背景提取算法提取有效背景，采用背景选择性更新方法对背景进行实时更新；用连续的三帧图像分别与背景进行差分，采用HSV颜色空间阴影去除方法对三个差分结果进行阴影去除，然后进行三帧差分，将差分结果进行“与”运算；最后用“与”运算得到的结果与中间帧背景减除的结果进行“或”运算，则可以得到运动区域。如图1所示。

图1　三帧差分运动目标检测结果

2　Meanshift算法

2.1Meanshift算法原理

从d维空间Rd中取出n个采样点xi，其中i=1,…,n，在这里能够给出在参考点x处的Meanshift向量的基本形式为

(1)

从式(1)中能够看出(xi-x)是样本点xi相对于确定的参考点x的偏移量大小，Meanshift算法的基本向量Mh(x)的含义是在多维空间中，首先选择一个参考点x，在事先确定区域内对样本点xi与参考点的偏移量先进行求和然后再求平均值[4]。可以看出，所有区域内的样本点xi是从概率密度函数f(x)中采样得到的，根据概率统计学可知如果概率密度梯度值不等于零，则函数梯度指向概率密度增加最大的那个方向，sh区域中的采样样本几乎都落在沿着概率密度梯度的方向。显然，相应的Meanshift向量Mh(x)就是指向概率密度梯度最大的方向。

如图2所示，大圆的范围表示为sh，图中箭头方向表示参考点x的偏移向量，空心圆为落入区域sh中的n个采样点xi∈sh，而实心圆就是Meanshift基本向量的参考点x。很显然，基本向量Mh(x)的结果就是使参考点向采样点概率密度最大的方向进行偏移。

图2　均值偏移示意图

从式(1)中能够看出，在区域sh(x)中所得到的采样点xi，无论确定的参考点x离采样点有多远，对Meanshift基本向量Mh(x)的计算结果的影响是一致的。通过仿真可以看出这样的形式会使得参考点的收敛速度变得很慢。通常情况下，参考点x附近的采样点对基本向量的估计结果起到的作用就越大，因此对距离参考点不同远近的采样点赋予了不同的权值，常用的Meanshift扩展形式可以写为

(2)

2.2Meanshift跟踪算法

(3)

式中：δ为克罗内克函数[6]。k(x)是核函数的轮廓函数，采用该函数给不同的像素点赋权值。对中心点附近的像素点赋予的权值比较大，离中心点远的像素点所得权值就会比较小。通过该函数可以使得密度估计更加稳定可靠。C的计算表达式为

(4)

(5)

通过式(5)可以看到Ch与y值之间并没有什么联系，根本原因是由于像素位置xi的形式是规则化网格，因此确定核密度和尺度h后，Ch的大小也就被确定了[7]。

(6)

y0为当前视频帧图像的初始位置，式(6)在y0处进行泰勒展开可以得到

(7)

通过上式可以看出经过泰勒展开后，y值只受等式右边第二项的影响。这样看来可以利用Meanshift算法对其进行迭代，在区域中得到概率密度估计最大值，通过该值确定目标的最新位置y1[8]。完成迭代以后，y1的值就是最后匹配的最佳位置。

3　Kalman滤波器

Meanshift算法主要是在目标中心领域附近搜索出相似度最大的运动目标，如果目标运动太快，或是目标被障碍物遮挡，都会使得跟踪的结果有很大的误差。因此本文结合Kalman 滤波算法，该算法主要具有预测当前帧状态向量的功能，它是根据以往帧观测向量进行预测的，这样就可以得到运动目标的预测位置目标。Kalman滤波器主要是运用最小均方误差估计方法对动态系统的状态序列进行计算，由此可以得到下一帧中运动目标区域的中心位置信息，与此同时替换当前帧运动目标区域的位置[9]。假设目标位置在x轴以及y轴的状态向量表示为X=(xc,yc)T，预测目标的位置在x轴以及y轴的测量矢量表示为Z=[xc,yc]T。首先初始化状态向量Xi，接着用该状态向量作为Kalman滤波器的观测值来预测相邻帧的值。

Kalman滤波器的状态方程和测量方程分别表示为

Xi+1=AXi+Wi，

Zi=HXi+Vi

(8)

式中：A为状态转移矩阵；H为测量矩阵；Wi,Vi分别表示状态噪声向量和测量噪声向量，假定该噪声都是独立的白噪声，对应的方差分别为Q,R。

状态向量预测方程的表达式为

(9)

状态向量协方差矩阵预测方程的表达式为

(10)

状态向量更新方程表达式为

(11)

状态向量协方差更新方程表达式为

(12)

Kalman加权矩阵或增益矩阵表达式为

(13)

4　基于Meanshift的改进跟踪算法

通常情况下，Meanshift算法是一种有效的跟踪算法，很大程度上能够保证很好的跟踪效果[10]。Meanshift算法没有过多的考虑目标的实际运动情况，而仅仅是用偏移量也就是最大概率梯度的方向来确定目标位置，这样就忽略了实际运动目标的运动速度和运动方向信息。Meanshift算法的缺点在于跟踪框对于运动速度过快的目标跟踪效果不好，甚至会脱离实际目标。跟不上目标的主要原因是因为选取的初始值不正确，使得之后的迭代就出现更多的错误。在Meanshift算法中，对泰勒式展开的目的是使得巴氏系数最大化，其中只有当y1值与y0值相差不大的时候泰勒展开有作用。这个时候，如果将当前帧的初始值定为前一帧目标的中心坐标，当目标运动过快时就不能准备跟踪目标。并且在目标被遮挡时，也容易造成跟踪失败，跟踪过程中窗口大小无法自适应变化。

针对以上问题，本文提出一种基于Meanshift算法的改进算法。采用改进的三帧差分法对运动目标区域进行提取，求得跟踪框轮廓，同时用Meanshift算法对运动目标进行跟踪，获得目标最大概率区域，将该区域中心作为跟踪框的中心。跟踪过程中通过巴氏系数判断是否目标被遮挡，若被遮挡则调用Kalman滤波进行预测跟踪。改进算法的优点在于可以使跟踪框自适应变化，并且当目标被遮挡之后也能很准确地跟踪运动目标。算法流程图如图3所示。

图3　本文算法流程图

1)首先要获得前景区域即运动目标区域。采用三帧差分对运动区域进行提取，然后将运动区域用跟踪框进行标注。

2)其次利用Meanshift算法进行迭代，由于它是重心移动，即向反向投影图中概率大的地方移动，所以会得到运动目标的中心点位置。

3)将获得的运动目标中心点也就是最大概率点作为跟踪框的中心，这样就实现了准确的跟踪，同时实现了跟踪框的实时变化。

4)在每一帧图像中，都利用巴氏系数(式(1))判断运动目标是否被遮挡，如果巴氏系数大于阈值T(经过多次实验，取T=0.4效果最佳)，则不调用Kalman预测算法；否则调用Kalman预测算法对运动目标进行预测跟踪。

5　实验结果分析

图4是传统Meanshift算法的跟踪结果。该视频的运动目标的大小由大变小， 传统的Meanshift算法跟踪框不能实现自适应变化，所以整个过程中跟踪框不能随目标的大小而变化；并且当运动目标被遮挡时，第131帧图像中运动轨迹发生了错误的变化。图5是本文算法的跟踪结果。结合了三帧差分和Kalman预测跟踪，实现了跟踪框的自适应变化，并且遮挡之后还能准确跟踪。

图4　传统的Meanshift算法跟踪结果

图5　本文算法的跟踪结果

6　结论

本文提出一种基于Meanshift算法的改进算法。采用改进的三帧差分法对运动目标区域进行提取，该方法不仅保证了系统的检测效率而且还可以完整地提取出待跟踪的运动目标区域，从而求得跟踪框轮廓。同时用Meanshift算法对运动目标进行跟踪，获得运动目标信息即最大概率区域，将该区域中心作为跟踪框的中心，这样实现了跟踪框的自适应变化。跟踪过程中通过对巴氏系数的计算，判断目标是否被遮挡，若被遮挡则启用Kalman对下一帧目标位置进行预测。实验结果证明，本文将Meanshift算法结合三帧差分和Kalman滤波算法可以对运动目标进行实时准确跟踪。

[1]杨红霞，杭亦文，刘旭. 基于Meanshift与Kalman的视频目标跟踪算法[J]. 武汉理工大学学报(信息与管理工程版)，2012，34(2)：147-150.

[2]姚放吾，许辰铭. 基于目标质心的Meanshift跟踪算法[J]. 计算机技术与发展，2012，22(6)：104-110.[3]张英，车进，周鹏. 一种改进的三帧差分运动目标实时检测算法[J].计算机测量与技术，2015，23(6)：2073-2075.

[4]许辰铭. 视频图像中的运动目标检测与跟踪[D].南京：南京邮电大学，2012.

[5]陈柱，李子印，朱明凌. 基于块的Mean-shift 跟踪算法[J].电视技术，2015，39(20)：6-10.

[6]HE J W， YANG Y Y. Multi-iterative tracking method using meanshift based on kalman filter[C]//Proc. 2014 IEEE International Conference on Signal Processing， Communications and Computing (ICSPCC).[S.l.]：IEEE，2014：22-27.

[7]YIN H P， CHAI Y， YANG S X， et al. Fast-moving target tracking based on mean-shift and frame-difference methods[J]. Systems engineering and electronics， 2011，22(4)：587-592.

[8]许慧芳，许亚军. 智能视频监控系统中多摄像头协同跟踪算法[J].电视技术，2015，39(18)：86-90.

[9]CHU C， HWANG J. Fully unsupervised learning of camera link models for tracking humans across non-overlapping cameras[J].IEEE transaction on circuits and systems for video technology，2014，24(6)：979-994.

[10]AVED A J， HUA K A， GURAPPA V. An informatics-based approach to object tracking for distributed live video computing[J]. Multimedia tools and applications，2014，68(1)：111-133.

张英(1989— )，硕士，主研信号、图像处理与模式识别；

车进(1973— )，博士，教授，硕士生导师，主要研究方向为图像处理及智能视频技术方向的研究，为本文通信作者；

牟晓凯(1990— )，硕士生，主研模式识别与图像处理；

白雪冰(1991— )，硕士生，主研信号、图像处理与模式识别。

责任编辑：闫雯雯

Improved meanshift moving tracking algorithm

ZHANG Ying， CHE Jin， MU Xiaokai， BAI Xuebing

(SchoolofPhysics&ElectricalInformationEngineering，NingxiaUniversity，Yinchuan750021，China)

When Meanshift algorithm tracks the fast-moving targets， it is easy to lose the target. And when the targets are blocked， it is likely to cause tracking failure. The tracking window size can not be adapted to change. An improved Meanshift target tracking algorithm is presented. The algorithm uses improved three-frame difference method to extract moving target area， and seek tracking frame outline. At the same time， Meanshift algorithm tracks the moving targets and obtains the target maximum probability region. Then the regional center can be a center of the tracking frame. During tracking process， Pap coefficient can determines whether the target is blocked. If target is blocked， then kalman filter can be called to forecast and track. Experimental results show that the algorithm is quick and accurate to track the target.

three-frame difference； Meanshift； moving target tracking； Kalman filter

TP391

ADOI： 10.16280/j.videoe.2016.10.020

国家自然科学基金项目(61162020)

2015-12-22

文献引用格式：张英，车进，牟晓凯，等. 改进的Meanshift运动目标跟踪算法[J].电视技术，2016，40(10)：97-100.

ZHANG Y， CHE J， MU X K，et al. Improved meanshift moving tracking algorithm[J]. Video engineering，2016，40(10):97-100.