基于Mean Shift算法视频跟踪研究

杨 辉，刘 军，阮 松

（1.武汉工程大学 智能机器人湖北省重点实验室，湖北 武汉430074；2.武汉工程大学 计算机科学与工程学院，湖北 武汉430074）

0 引 言

目标跟踪融合了计算机视觉，模式识别，人工智能，自动控制，数学等领域的先进技术［1］，在航天、医疗、交通、安全、生产等领域有着广泛的应用前景。在众多的跟踪算法中，Mean Shift算法因原理简单，鲁棒性好以及无参的特性，近几年来在视频跟踪领域受到了广泛的关注。然而，由于Mean Shift算法是一种基于概率密度梯度无参估计的匹配算法，采用跟踪区域颜色反向投影图的策略来建立目标模型和候选目标模型，大大限制了Mean Shift算法在跟踪领域的广泛应用。通过实验可知，在背景简单的情况下能够达到良好的跟踪目的；同时，理论上分析候选目标模型的建立依赖于前一帧的跟踪结果，所以相邻两帧中必须要有重叠区域，这是Mean Shift算法实现良好跟踪的前提，一旦视频速度变快，相邻两帧失去重叠的区域就会导致跟踪失败。随着视频技术的快速发展，各种视频类型层出不穷，其中高速，背景复杂的视频占据了较大的比例，为了实现视频的实时跟踪，对这类视频的研究是不可回避的。基于Mean Shift算法在跟踪方面的良好性能，为了能进一步提高Mean Shift的跟踪性能，不少学者对Mean Shift算法进行了探索和研究。文献 ［2］提出的改进型Mean Shift方法提高了对目标的辨识能力和鲁棒性，但分块基于的标准和过程增加了算法的复杂性；文献 ［3］提出基于特征匹配的运动目标检测和 Mean Shift算法相结合的方法改善了一定速度目标跟踪性能；文献 ［4］采用多特征融合来实现跟踪，这种方法加大了背景和目标的可分性，但是各种特征在各种情况下所占的比例需要时时跟新，过程比较繁琐。

本文从跟踪目标背景的复杂性以及帧速的角度出发，提出基于Mean Shift算法融合Harris角点特征和Surf算法的视频跟踪，旨在改善Mean Shift算法在目标背景复杂以及帧速过快情况下的视频跟踪性能。

1 Mean Shift算法的跟踪原理及其局限性

1.1 Mean Shift算法原理简介

Mean Shift算法是一种迭代算法。具体流程为：先算出待测点的偏移量的平均值 （也称偏移均值或 Mean Shift向量），移动该点到其偏移均值点，然后以偏移均值点作为新的待测点，再次计算新待测点的偏移均值，如此迭代循环，直到满足相应的条件就结束。取M维空间RM中的n个样本点并标记为Xi（i＝1，2……n），Sh是一个以h为半径高维球区域，其中有K个样本点落在Sh范围内，在X点处Sh范围内的偏移均值定义为

在数学上概率密度梯度的值非零则表示为概率密度增加的最大方向，若样本点采样于概率密度函数，则概率密度梯度的方向即为偏移均值。由于样本点离X的远近的不同以及每个样本点重要性的差异，偏移均值的最终效果也不同。为此在偏移均值中引入核函数GH （x）和权值函数W （x），得到扩展的偏移均值为

把式 （2）最右边第一项记为m （x），则 Mean Shift算法可以理解为以下3个步骤：

（1）计算 m （x）；

（2）计算 m （x）－x 的值，与阈值ε进行比较，若大于转 （3），否则算法结束；

（3）令x＝m （x），继续 （1）；

2002年Mean Shift算法在非刚体跟踪方面的应用被提出，并近似为一个 Mean Shift向量的最优化问题。Mean Shift算法在跟踪过程中，对目标模型的描述利用的是跟踪目标的灰度或色彩分布，类比扩展的偏移均值式 （2）可知，搜索框的作用即为核函数的作用，目标的灰度或色彩分布即为样本的权值。具体跟踪过程描述如下：

（1）在初始帧，用搜索框框定目标，记搜索框的中心为X0；

（2）计算搜索框内的颜色概率分布，根据概率分布求得搜索框的质心为Xc；

（3）移动搜索框使得搜索框的中心与X重合，移动前判断若｜X0－Xc｜＞ε且在当前帧中移动次数小于常数C，则移动后继续2；否则移动后输入下一帧继续 （2），此帧搜索框的初始位置为上一帧搜索框的最终位置。

3.3 调节黏液合成与分泌 在 CRS 病理机制中，细菌脂多糖和炎性介质共同刺激黏膜杯状细胞，使之分泌大量黏稠的黏液，导致炎症迁延不止。黏蛋白 4、黏蛋白 5AC 和黏蛋白 5B 是气道黏液中主要的 3 种成分，影响着黏液的弹性和黏性。黏液分泌受 IL-8 的调控，研究证实，红霉素、阿奇霉素、麦迪霉素等可以抑制 IL-8、TNF-α、黏蛋白 5AC等的表达，从而减少黏液的分泌[21-22]。此外，MA可以改善黏液的清除、减少糖精传输时间，改变黏液的流变性能[23]。黏液中氯化物含量较高可能导致流变性能差，而 MA 通过减少氯化物含量使更多稀薄的黏液产生[24]。

1.2 Mean Shift算法在跟踪方面的局限性

Mean Shift算法在跟踪方面的局限性通过两段视频予以说明。

视频1：被跟踪目标为灰色，整个场景中由于灯光的原因整体呈现灰黑色，背景闪烁变化，过于复杂，跟踪目标从954帧开始跟踪，到第1938帧时跟踪失败共跟踪984帧，如图1和图2所示。

视频2：跟踪目标为黑色，且始终在运动场上移动，与白色的运动场背景对比鲜明，跟踪目标从第263帧开始进行跟踪，跟踪目标从左下角移动到右上角，到第540帧时出现跟踪失败，总共跟踪277帧，运动视频速度过快，导致前后帧没有重叠的区域，跟踪失败，如图3和图4所示。

综上所述，Mean Shift算法不适于跟踪目标背景复杂，速度过快的视频。

2 Harris角点检测

在图像中角点一般定义为亮度变化剧烈的点或边缘曲线曲率的极大值点［5］。角点数目少，一般只占整幅图像0.05%左右的像素，但角点却含有图像重要局部特征信息，由于不同图像之间角点差异性很大，因此将角点作为特征提取的对象，在减少数据量的同时，又能够提取丰富的特征信息。Harris角点检测是一种基于灰度图像亮度变化的角点检测算法。基本思想是：在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化值超过设定的阈值时，就将窗口的中心像素点提取为角点［6］。优点是在操作时只用到了一阶差分及滤波，因此计算简单，对图像光照、旋转、部分仿射变化以及噪声干扰具有很好的鲁棒性，比较适合于目标的定位。由于Harris角点检测算法对尺度变化敏感，同一物体在不同尺度下提取的角点可能完全不同，在跟踪过程中，摄像机和目标之间距离的变化会导致跟踪目标的尺度发生变化，因此不能单纯地用Harris角点检测算法提取的特征来进行跟踪。

Mean Shift算法利用目标颜色信息这一特征进行跟踪，当背景过于复杂或者与跟踪目标相似时很容易导致跟踪失败，这是因为单一的特征不足以描述跟踪目标，为了提高Mean Shift算法在这方面的跟踪性能，有必要引入更多更好的特征进行融合实现实时跟踪。而Harris算法的优点决定了它所提取目标的特征与周围环境具有明显的可分性。因此选择Harris算法提取的特征与颜色特征进行融合在理论上是个不错的选择。融合的方法为将Mean Shift的跟踪过程的第二步修改为，计算搜索框内的角点以及角点的颜色概率分布，根据概率分布求得搜索框的质心为Xc。

3 Surf算法

3.1 特征点检测

Surf对于特征点的检测是基于Hessian矩阵行列式的正负，而Hessian矩阵的行列式在计算的过程中采用了积分图像法，这是Surf算法实现快速检测的关键原因之一。

Hessian矩阵定义如下

其中L（x，y，Ф）是图像I（x，y）在尺度Ф下的图像，由高斯函数G （Ф）与图像I（x，y）卷积得到，Lxx（x，y，Ф），Lxy（x，y，Ф），Lyy（x，y，Ф）是L （x，y，Ф）的二阶偏导数。实际计算时用盒形滤波器与模板的卷积近似得到二阶偏导数的值Dxx，Dxy，Dyy。盒形滤波器由若干块构成，在每一块的连续区域具有相同的权值，因此做卷积运算实际上计算的就是这块区域的积分图。盒形滤波器和积分图的引入大大加快了卷积的计算速度。Hessian矩阵的行列式为 （w为近似计算的误差因子）

若det（H）＞0则该点即为极值点。依次计算各尺度下的极值点，并将各极值点与其同一尺度的领域8个点以及相邻尺度的9个点共26个点比较大小。若该点是这些点中最大的或是最小的，则该点即为特征点。

3.2 特征点描述

Surf特征点的描述分为两部分：确定主方向和构造特征描述向量。

为保证旋转不变形，需要确定主方向。以每个特征点为中心，以6倍特征点所在尺度为半径画圆，计算圆内各点在X和Y方向上小波响应，其中Haar小波边长为4倍特征点所在尺度，为了使靠近特征点的响应贡献大，分别给这些响应赋高斯权重系数，然后将圆内每60度范围内的响应相加形成矢量，选择最长的矢量即为该特征点的主方向。

在描述每个特征点时，将坐标轴旋转为该特征点的主方向。以特征点为中心，取20Ф＊20Ф的区域，其中Ф为特征点所在的尺度，将其分成5＊5个4Ф＊4Ф的子区域，将20Ф＊20Ф的区域看成是5＊5的采样点，在每个采样点上分别计算主方向和垂直方向的Haar小波响应dx和dy。对dx和dy进行高斯加权后，对各子区域的dx，dy，｜dx｜，｜dy｜分别累加求和，并归一化为单位向量，这样得到4＊4＊4共64个值，即Surf提取的特征的描述向量是64维的，相比128维的sift特征描述向量而言，数据量减少了一半，这也是Surf算法快于sift算的原因之一。这种采用区域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性［10］。

Mean Shift算法在实施跟踪的过程中，后一帧的初始搜索框的位置，取决于前一帧的搜索结果。若帧速过快，相邻两帧失去重叠区域，则会导致跟踪失败。本文引入Surf算法解决帧速过快导致的跟踪失败，具体过程为，标定目标时，用Surf算法提取目标的Surf特征点集P，设Hi和Hi＋1为前后两帧的搜索框内的颜色直方图，利用Bhattacharyya距离判断他们的相似程度，Bhattacharyya距离越大则越相似，若dBhattacharyya（Hi，Hi＋1）＜＝0.8则跟踪失败。一旦跟踪失败，用Surf算法在整帧画面中提取与P相匹配的点集Q，选择一个将不部分Q点集包含在内的矩形框，更新搜索框为该矩形框，继续采用Mean shift实行跟踪。

4 改进的Mean Shift算法流程及实验结果与分析

融合Harris角点检测算法和Surf算法后的Mean Shift视频跟踪完整流程如图5所示。

从图5可知，改进后的Mean Shift算法，在流程上与原Mean Shift相比，特征提取即第2步增加了Harris角点提取，新增加了第5步和第9步用于跟踪失败后的搜索框的重定位。按照此流程分别测试了二段视频，用来检验改进后的跟踪效果。本实验采用C＋＋ （visual studio 2010）和 Opencv（2.3.1）库实现。

图5 改进后的Mean Shift算法

视频一：对于背景过于复杂的视频采用改进后的Mean Shift算法跟踪效果如图6所示。

图6 改进后的Mean Shift算法跟踪效果

分析：采用Harris角点提取目标所得的颜色概率分布图作为特征对背景过于复杂的视频进行连续跟踪，效果图如图6所示，跟踪效果良好，与图1－2相比，效果得到明显改善。

视频二：帧速过快跟踪失败情况下采用改进Mean Shift跟踪效果如图7所示。

分析：当后一帧以前一帧搜索框最后的位置作为初始搜索框的位置时，有可能帧速过快，目标已经不在后一帧初始搜索框内如图7（b）所示，此时根据前后两帧颜色概率直方图的Bhattacharyya距离判断出跟踪失败，启动Surf算法，在整幅帧中查找目标。图7（c）中目标再次出现，查找到目标，之后继续用Mean Shift算法进行跟踪。与图3－4相比，跟踪失败的情况得到改善。

图7 帧速过快跟踪失败情况下采用改进Mean Shift跟踪效果

5 结束语

用2段视频实验得出Mean Shift跟踪时在背景过于复杂，以及帧速过快方面的局限性，针对Mean Shift算法的局限性，分别予以改进。Harris角点检测算法提取的角点具有很好的定位性，将Harris角点检测算法与Mean Shift算法特征提取过程进行融合，得到融合的目标特征信息进行跟踪，通过实验得出效果图6与图1和图2对比可知，背景过于复杂情况的跟踪性能明显得到改善。帧速过快情况下的跟踪失败采用的是Surf算法与Mean Shift算法的融合，实验得出的效果图7可知，跟踪效果很好。虽然，本文涉及到3个算法的融合，但是Harris角点算法计算简单，Surf算法速度很快，算法的实现基于Opencv（2.3.1版本）库和VS2010，所以本文提出的算法可以很好进行实时跟踪。

：

［1］SUN Xin.Based on the level set target contour tracking algorithm ［D］.Harbin：Harbin Institute of Technology，2010：4－5（in Chinese）.［孙鑫.基于水平集的目标轮廓跟踪算法的研究 ［D］.哈尔滨：哈尔滨工业大学，2010：4－5.］

［2］HU Yin，YANG Jingyu.Based on block color histogram Mean shift tracking algorithm ［J］.Journal of System Simulation，2009，5 （10）：2936－2939 （in Chinese）.［胡铟，杨静宇.基于分块颜色直方图的 Mean shift跟踪算法 ［J］.系统仿真学报，2009，5 （10）：2936－2939.］

［3］YAO Fangwu，XU Chenming.Mean shift tracking algorithm based on the target centroid［J］.Computer Technology and Development，2012，6 （22）：104－106 （in Chinese）.［姚放吾，许辰铭.基于目标质心的Mean shift跟踪算法 ［J］.计算机技术与发展，2012，6 （22）：104－106.］

［4］YUN Xiao，XIAO Gang.Vessel tracking algorithm based on multi－feature adaptive fusion of the Camshift［J］.Optical Engineering，2011，5 （38）：52－58 （in Chinese）.［云霄，肖刚.基于Camshift的多特征自适应融合船舶跟踪算法 ［J］.光电工程，2011，5 （38）：52－58.］

［5］GONG Ping，LIU Xiangbin.An improved Harris corner detection algorithm ［J］.Computer Engineering and Aplications，2010，46 （11）：173－175 （in Chinese）.［龚 平，刘 相 滨，周鹏.一种改进的Harris角点检测算法 ［J］.计算机工程与应用，2010，46 （11）：173－175.］

［6］liuw ＿9.The idea of the Harris corner detection algorithm ［EB／OL］.［2007－11－28］.http：／／http：／／blog.csdn.net／liuw ＿9／article／details／1906245 （in Chinese）.［liuw＿9.Harris角点检测算法的 思 想 ［EB／OL］.［2007－11－28］.http：／／http：／／blog.csdn.net／liuw＿9／article／details／1906245.

［7］XIONG Yin，MA Huimin.Extraction and application of 3dimensional objects SIFT feature［J］.China Journal of Graphics，2010，15 （5）：814－819 （in Chinese）.［熊英，马惠敏.3维物体SIFT特征的提取与应用 ［J］.中国图像图形学报，2010，15 （5）：814－819.］

［8］FENG Jia.Study and improving of sift algorithm ［D］.Changchun：Jinlin Technology，2010：6－7 （in Chinese）.［冯嘉.Sift算法的研究和改进 ［D］.长春：吉林大学，2010：6－7.］

［9］BAY H，Tuytelaars T，GOOL L V.SURF：Speeded up robust features ［C］／／Proceedings of the European Conference on Computer Vision.Graz，Austria，2006：404－417.

［10］Yong.Learning experience of Surf algorithm ［EB／OL］.［2011－11－17］.http：／／http：／／www.yongblog.com／archives／123.html（in Chinese）.［Yong.Surf算法学习心得［EB／OL］. ［2011－11－17］.http：／／http：／／www.yongblog.com／archives／123.html.］