基于Mean Shift多特征融合跟踪的改进算法

雷 川，黄 山，，张洪斌

（1.四川大学 电气信息学院，四川 成都610065；2.四川大学 计算机学院，四川 成都610065）

0 引 言

由于Mean Shift目标跟踪算法在目标跟踪过程中能够很快的找到最佳的匹配，故其非常适合用于对要求跟踪响应快的实时跟踪系统中［1，2］。Mean Shift目标跟踪算法基于颜色模型，应用每一帧图像颜色投影通过颜色直方图来自动调节搜索窗口的位置和尺寸，且通过算法迭代收敛时得到最佳的中心位置作为目标的中心。该算法也存在缺陷，当目标运动过快时，在两个相邻帧图像中的目标区域不能重叠，否则会导致跟踪目标的丢失。为解决这种缺陷，文献［3］将卡尔曼滤波与Mean Shift跟踪算法相结合，先通过卡尔曼滤波器预测目标在下一帧图像中的位置，然后调节使Mean Shift算法收敛的搜索窗口中心，使算法收敛的目标中心更准确，同时Mean Shift跟踪算法仅仅以颜色特征描述目标，当跟踪窗口中出现相似颜色干扰或者跟踪目标变暗时，其跟踪效果同样不理想；文献 ［4］通过融合颜色特征和边缘特征，解决了在相似颜色干扰或者光照条件变化情况下，原始的Mean Shift 跟踪算法效果不理想的缺陷。

传统的Mean Shift算法存在当跟踪快速运动目标和亮度环境改变过快或跟踪目标长时间变暗时，跟踪性能变差的缺陷的问题。上述两种改进算法增加了算法的复杂程度、迭代次数，影响跟踪的实时性。本文在分析算法跟踪缺陷的基础上，结合运动矢量，融合颜色特征和边缘特征，提出了一种改进的Mean Shift跟踪算法。实验验证了该算法的良好效果。

1 传统算法描述

本文采用Mean Shift与特征融合算法来跟踪运动目标，由于Mean Shift跟踪算法是通过找到当前帧中颜色直方图和目标模板中颜色直方图之间的相似度最大值来跟踪目标，故该跟踪算法天然的融入了颜色特征。在视频目标跟踪中，颜色特征对遮挡有较强的鲁棒性，但当环境亮度变化，运动目标变暗或相似颜色干扰时，基于颜色特征的目标跟踪算法无法达到跟踪要求，而边缘特征可以很好的弥补颜色特征在环境变化的情况下跟踪效果差的缺陷。

1.1 Mean Shift跟踪算法

通常用跟踪目标的灰度或色彩分布来描述该物体，假设物体中心位于x0，xi表示目标窗口中的第i 个像素点，则该物体模板概率密度可以表示为

候选的位于y 的物体模型的概率密度可以描述为

为使ρc（y）最大，对式 （3）泰勒展开

其中

计算y1－y0，如果 y1－y0＜ε则停止迭代，目标的中心由y1代替y0，每次迭代都可以从y0中得到一个新的位置y1

如此，运动目标从原始的位置逐渐调整到当前位置，实现对目标的跟踪。

1.2 边缘特征

多特征融合算法，是目标跟踪领域中比较常用的算法。利用多特征描述目标是一种非常有效的实现稳健跟踪的方法［5］。常见的描述跟踪目标的特征有，彩色、轮廓、梯度、角点、纹理、边缘等。常见的多特征融合有，彩色和轮廓，彩色和梯度，彩色和边缘，角点、彩色和轮廓等。边缘特征在图像中表示为跟踪目标的轮廓边缘，在像素分布上则表示为图像中亮度的变化最明显部分，即其周围像素有灰度的阶跃变化。边缘特征很好的弥补了原始Mean Shift算法中用单一的用颜色特征来描述跟踪目标的缺陷。

1.1节表明Mean Shift跟踪算法根据颜色直方图对目标建模，使相似性度量Bhattaharry系数最大来确定运动目标在下一帧中的位置，从而实现目标的跟踪。类似的，可以提取目标边缘的直方图来描述运动目标。

目标模型的边缘直方图由下式表示

候选的位于y 的物体可以描述为

Bhattacharrya系数

对式 （9）泰勒展开，并使上式最大，与1.1 中类似，可以得到目标在下一帧中的位置y1e。

2 运动矢量

由于Mean Shift跟踪算法在搜索跟踪目标过程中，只能在局部的某个搜索范围内有效，当跟踪目标运动过快时，特别是在前一帧和后一帧跟踪目标在空间上没有重叠时，算法的跟踪效果不理想，容易导致跟踪目标的丢失。其主要原因在于，在对Mean Shift跟踪算法的推导过程中，上述公式对相似度量函数在跟踪目标的初始中心位置的某个邻域内即核函数的带宽尺寸内进行泰勒展开；此时，若跟踪目标的运动速度过快，致使在连续的两帧图像中，目标的运动距离超过了该邻域，原始的Mean Shift已经不能在局部区域内搜索到使相似性度量函数的一阶导数取得极值的最优点，从而导致跟踪目标的丢失。

本文采用运动矢量来解决运动目标过快而使跟踪目标丢失的问题。设mvx，mvy分别是运动矢量在x 轴和y 轴上的权值，运动矢量在水平和垂直分量间的夹角θ，其取值范围的区间为（0，2π），将该取值范围平均分成8份，即每份占，并且由θ的定义可得tanθ＝mvy／mvx，由此得到每个运动矢量对应的方向编码，该编码函数为

由于本文实验都是在摄像头静止的情况下采集的视频，而对于静止的摄像头，背景区域宏块各个方向的运动矢量都为0，仅有存在目标运动的区域的各个方向上运动矢量不为0。在此情况下对目标运动方向和速度进行估计：设运动目标区域中所有运动矢量的方向编码概率密度分布为，i∈（0，7），由该8个方向上的编码概率密度分布，可以建立运动矢量方向上的编码直方图。根据上述的概率密度分布可以得到运动矢量方向编码的最大概率密度，即＝max（），如果超过一定的阈值，说明跟踪目标在同一运动方向上有整体的位移移动特性，此时可以根据该最大值估计跟踪目标的运动方向和运动速度。否则可认为跟踪目标没有位移特性。取使＝Pmax的所有矢量。

3 本文算法

该算法首先应用运动矢量对候选模板中心y0进行修正得到修正后的中心y′0，以避免目标运动过快而使Mean Shift跟踪算法丢失目标，然后在Mean Shift跟踪算法中动态地融合颜色特征和边缘特征来减少环境的改变给跟踪性能带来的影响。算法具体步骤如下：

步骤1 运动矢量预测：在第一帧中初始化目标中心y0，在下一帧中通过运动矢量预测在当前帧中的候选区域中心y′0，计算y′0的公式如下）

式中：α∈（0，1），与目标的运动速度成反比。

步骤2 Mean Shift算法搜索：根据第一步中计算出的当前帧候选中心y′0，通过Mean Shift算法搜索得到当前帧中目标的中心y1：根据基于颜色特征的Mean Shift算法搜索在当前帧中目标的中心y1c；根据基于边缘特征的Mean Shift算法搜索在当前帧中目标的中心y1e；动态融合颜色特征和边缘特征得到目标在当前帧中目标的中心y1，其计算公式如下

其中

式中：ρc（y）、ρe（y）——颜色特征和边缘特征的Bhattacharrya系数；

步骤3 判断 y1－y0＜ξ，如果该式成立则换下一帧，否则重复第二步，直到该式成立。

4 实验结果及分析

为验证本文算法的有效性，作者对快速运动的行人和复杂环境中运动的行人进行了实验。本文中的实验使用的计算机硬件配置为Intel Core2 2.4GHz CPU，2G RAM），软件环境为Windows XP操作系统，VS2010，Opencv2.4.8软件编程环境。

4.1 针对快速运动的行人的实验

该实验将摄像机固定在三脚架上采集视频，视频大小为450×320，帧率为30fps，长度为128。对两个慢跑的行人中的某个人进行跟踪。图1是采用基于Mean Shift融合颜色和边缘特征 （MMS算法）跟踪算法的结果，图1 （a）第26帧图为原始状态图。

图1 MMS算法跟踪结果

由上述实验结果可知，由于物体运动速度较快MMS跟踪算法无法预测到下一帧运动目标的位置，图1中第55帧图，逐渐开始丢失目标，第88帧图，该算法已经完全丢失对运动目标的跟踪。

本文算法跟踪结果如图2所示。

图2 本文算法跟踪结果

上述实验采用本文跟踪算法的实验结果，初始状态图依然选取第26帧，依然是选取第55帧图和第88帧图的跟踪结果图与MSS跟踪算法的跟踪效果作对比，由于本文算法引入了运动矢量为运动目标下一帧的位置做预测，故在目标运动速度较快时也能有较好的跟踪性能，第55帧图和第88帧图的跟踪结果说明了这一点。同时，运动矢量的引入也减少了Mean Shift的迭代次数。

从20帧到120帧中随机抽取5帧，以15帧为间隔，统计两种算法在相应帧下的Mean Shift迭代次数，见表1。从表1可以看出，本文算法可以减少跟踪过程中Mean Shift的迭代次数，从而减少跟踪的过程中的运算。

表1 两种算法Mean Shift迭代次数比较

4.2 在复杂情况下的行人跟踪实验

实验采集某银行的监控视频，对在光照变化和颜色干扰的情况下，分别通过原始的Mean Shift算法和本文算法对行人进行跟踪。

图3为使用传统的Mean Shift算法对行人进行跟踪，图3 （a）第10帧图为初始状态图，手动圈定跟踪的目标和跟踪的范围，第18帧图和第42帧中有相似颜色和光照变化的干扰，原始的Mean Shift算法跟踪性能降低，导致跟踪目标丢失。

图3 Mean Shift算法结果

本文算法跟踪结果如图4所示。

图4 本文算法跟踪结果

表2是从10帧到60帧中选取5帧，每帧间隔为10帧，对中心误距离进行统计，得出两种算法在相应帧的中心距离误差，该结果与上面的实验图相对应。

表2 两种算法中心误差距离对比

本文算法由于动态融合颜色特征和边缘特征，当出现颜色相似干扰和光照条件变化时，由式 （12）、式 （13）可知，边缘特征的Bhattacharrya系数将增大，此时该算法以边缘特征为主来跟踪目标，受相似颜色干扰的影响就减小，能保持良好的跟踪性能。

5 结束语

本文针对Mean Sihft算法在跟踪方面的缺陷，在MMS跟踪算法的基础上引入运动矢量来预测运动目标在下一帧中的位置，解决运动过快导致跟踪目标丢失的缺陷，同时减少了算法的迭代次数；多特征融合解决了颜色干扰和光照变化对跟踪效果影响的问题。实验结果表明，该算法具有较强的鲁棒性。由于本文采用的是固定窗宽来跟踪目标，为了防止目标运动过快而使跟踪窗口内的颜色特征和边缘特征变化过大，即便采用运动矢量做预测也无法使Mean Shift跟踪算法收敛，故在目标运动过快时，需要限制窗宽的大小。下一步，可以考虑采用自适应变窗宽的方法，解决本文算法的不足。

［1］WANG Wenjang，HUANG Shan，ZHANG Hongbin.Band－Width－adaptivate tracking algorithm based on Mean Shift and Kalman prediction ［J］.Computer Engineering ＆ Science，2013，35 （5）：87－92 （in Chinese）. ［王文江，黄山，张红斌.一种基于Mean Shift和Kalman 预测的带宽自适应算法［J］.计算机科学与工程，2013，35 （5）：87－92.］

［2］LI Ning，ZHOU Jianjiang，ZHAO Xingxing.Moving object tracking in dynaminc image sequence based on estimation of motion vectors of feature points［J］.Transactions of Nanjing University of Aeronautics ＆Astronautics，2009，26 （4）：295－300.

［3］HU Bo.Research on video object tracking technology based on Mean－Shift algorithm and Kalman filter［D］.Ningbo：Ningbo University，2010（in Chinese）.［胡波.基于Mean－shift算法和卡尔曼滤波的视频目标跟踪技术研究［D］.宁波：宁波大学，2010.］

［4］ZHENG Yufeng，MA Xiurong，ZHAO Xiaolin，et.al.Mean shift target tracking algorithm based on color and edge features［J］.Journal of Optoelectronics Laser，2011，22 （8）：1231－1235 （in Chinese）. ［郑玉凤，马秀荣，赵晓琳，等.基于颜色和边缘特征的均值迁移目标跟踪算法 ［J］.光电子激光，2011，22 （8）：1231－1235.］

［5］TIAN Wei.The summary of object tracking ［D］.Shenyang：Northeast University，2011 （in Chinese）. ［田维.目标跟踪综述 ［D］.沈阳：东北大学，2011.］

［6］Tang Da，Zhang Yujin.Combing Mean－shift and particle filter for object tracking ［C］／／Proc of the 6th Int’l Conf on Image and Graphic，2011：771－776.

［7］SONG Yuqing，YUE Dongpeng.Multi－feature fusion for video object tracking ［C］／／Fifth International Conference on Intelligent Net－Works and Intelligent Systems.IEEE，2012：33－36.

［8］HAN Ping，XU Jianlong，WU Renbiao.New feature fusion method for target tracking ［J］.Journal of Civil Aviation University of China，2010，28 （4）：21－26 （in Chinese）.［韩萍，徐建龙，吴仁彪.一种新的目标跟踪特征融合方法 ［J］.中国名航大学学报，2010，28 （4）：21－26.］

［9］LIU Qing，TANG Linbo，ZHAO Baojun，et al.Improved mean shift target tracking algorithm ［J］.Systems Engineering and Electronics，2013，35 （6）：1318－1323 （in Chinese）.［刘晴，唐林波，赵宝军，等.改进的mean shift目标跟踪算法［J］.系统工程与电子技术，2013，35 （6）：1318－1323.］

［10］LI Ning，ZHOU Jianjiang，ZHAO Xingxing.Moving object tracking in dynaminc image sequence based on estimation of motion vectors of feature points［J］.Transactions of Nanjing University of Aeronautics ＆Astronautics，2009，26 （4）：295－300.

［11］WANG Honglin，YANG Bo，TIAN Guodong，et al.Object tracking by applying mean－shift algorithm into particle filtering ［C］／／Proceeding of ICBNMT，2009：550－554.