一种基于颜色和边缘特征的Mean Shift目标跟踪算法

石祥滨，乔利英，刘 芳，吴杰宏

(沈阳航空航天大学 a.计算机学院;b.工程训练中心，沈阳 110136)

在动态环境下进行目标跟踪是当今机器视觉中的一个研究热点和难点，并被广泛应用于军用和民用领域。目前，国内外学者提出了许多不同的跟踪算法［1－3］，但是这些算法大都是面向特定应用环境的。为了提高跟踪的鲁棒性，许多人研究认为利用多个特征进行目标跟踪是解决这一问题的有效途径。但是，多特征跟踪存在的两个问题即如何合理选择目标特征以及如何构造有效的融合机制。文献［4］使用串行结构处理多个视觉线索，最大的特点就是跟踪系统对环境和场景变化的自组织和自适应力强。Collins等［5］将一种在线多特征自适应选择机制嵌入在均值漂移跟踪方法中，但该方法本质上还是只利用了目标的颜色特征，当目标和背景相似时其跟踪效果较差。对此，文献［6］提出的算法从颜色和形状－纹理等7个特征分量中选择前两个较可靠的特征集合来描述目标，并且跟踪过程中对模板进行了更新。但该方法在模板跟踪过程中是对一定间隔的帧数进行模板更新，无法适应跟踪过程中的环境突变，所以不具有完全的自适应性。王欢等［7］在Auxiliary粒子滤波框架内将所有特征观测进行概率融合，并使用融合权系数计算法进行择优过滤，跟踪结果更可靠，但是该方法复杂度高，跟踪实时性难以保证。

Mean Shift算法［8］是一种基于非参数概率密度估计的核跟踪方法。该方法实时性好、易于实现，且对边缘遮挡、目标旋转以及轻微的变形都不敏感，因而在人体目标跟踪中得到了广泛应用。但是，该算法鲁棒性不高，原因是单一信息缺乏对光照变化及相似背景等的足够强的区分性，而且缺乏有效的模板更新机制。

针对上面算法存在的缺陷，同时考虑Mean Shift方法的不足之处，本文提出了一种基于颜色和边缘特征相融合的方法，并且对跟踪过程中目标的模板变化进行及时更新。该方法首先在初始帧通过构造目标两个特征的核密度模型来描述目标;然后在待检测帧中使用相似度函数的加权融合来度量每个特征与模板的相似性;通过寻找候选目标与模板的总体最大相似度来完成对目标的定位;最后通过对目标特征权值和模板的更新来避免跟踪中模板漂移现象的发生。提出的方法在精确性和鲁棒性方面对单一特征的Mean Shift跟踪算法进行了改进，实验结果证明了本文提出的算法的有效性。

1 目标特征提取

1.1 颜色特征描述

传统Mean Shift方法通常采用RGB颜色空间，但是这种彩色空间具有分量间高度相关性且与人的视觉感知不一致的缺点。为了获得对光照变化的鲁棒性，减弱通道间的耦合关系，本文将输入的彩色图像从RGB颜色空间转变到HSV空间。其中H(Hue)表示色调，S(Saturation)表示饱和度，V(Value)表示颜色的亮度。HSV颜色空间的两个重要特点是:首先亮度分量与色调分量是分开的，V分量与图像的彩色信息无关。其次，H与S分量与人感受色彩的方式紧密相连。这些特点使得HSV颜色空间非常适合人的的视觉系统对彩色感知特性进行处理分析。计算公式［9］如下:

其中(R，G，B)分别代表红、绿、蓝像素值，取值范围为［0，255］。H 的取值范围为［0，360］。从公式(1)中观察到，当亮度值变得很高或者很低时，会导致H值发生较大波动。这样会使反投影图像表示不精确，同时也增加了噪声。为了消除这种影响，本文对亮度设定阈值，剔除掉小于或者大于一定亮度值的像素。本文只考虑那些与亮度值大于10或者小于240对应的H值。

为了简便，本文仅提取H分量信息建立目标颜色直方图。首先将H值均匀划分成m个小区间，每个小区间称为直方图的一个bin。然后，统计目标区域内落入每个直方图区间的像素数。同时，使用核函数给靠近中心位置的像素赋予较高的权值，靠近边缘的赋予较低权值，以降低背景噪声的影响，提高颜色特征对目标和背景的区分能力。这样得到的色度特征向量为:Qc=(qc1，qc2，…qcm)，则第i个子区间对应的bin的概率密度函数可以通过式(2)［8］计算得到:

基于HSV颜色直方图的提取过程如图1所示。

1.2 边缘特征描述

图1 HSV特征提取

边缘是图像最基本的特征之一。本文使用Sobel算子来检测图像的边缘［10］。假设用G表示跟踪窗口内原图像，Gx和Gy分别表示使用水平和垂直的Sobel算子对图像进行卷积运算后得到的梯度图像，则梯度大小为:G=，梯度方向为θ=arg tan。梯度方向的取值范围为［0，π］。与颜色直方图构建方法一样，将边缘方向均匀划分为n等分，形成的边缘特征向量为Qe=(qe1，qe2，…，qen)，则第 i个特征值对应的目标边缘概率密度函数用式(4)［8］计算得到:

其中Cc=1/k(‖q0－pj/h‖2)为归一化常数使得=1。p0表示搜索窗口中心像素位置，{pj}j=1，…，n表示该区域内像素位置，k(x)表示核函数，这里同样使用Epanechikov核，h为核函数带宽。dir(pj)函数用来计算像素pj所属的子区间。边缘方向直方图的提取过程如图2所示。

图2 边缘方向直方图

2 相似性测量

Mean Shift跟踪算法是基于最大化目标模板与候选的中心加权直方图计算得到的Bhattacharyya系数为准则的。相似性度量函数可作为目标模板和候选之间距离的相似性判据。这里我们定义目标模板和候选这两个离散分布之间的距离为［8］:

其中，pci和qci为颜色特征的候选目标和模板，pei和qei为目标的边缘特征的候选和模板的表示。

3 目标定位

ωcj和ωej分别表示颜色特征和边缘特征所对应的像素xj的权值。二者的计算公式相似，其中基于颜色的ωcj的计算公式如下:

注意到式(10)中第一项与第三项与y无关，第二项和第四项表示轮廓函数为k、权值为wω的核概率密度估计。则与总的相似性度量函数(7)对应的Meanshift向量为:

其中g(x)=－k'(x)。获得Mean Shift偏移向量之后，可以求得相应的Mean Shift迭代公式(13)，使候选目标从当前位置y^迭代移动到新的位置，若‖y1－y0‖ ＜ε或迭代次数 ＞N则停止迭代。

算法中通常取ε=0.5pixels和N=20。从式(9)和式(11)可以看出，本文算法中每个像素的权值由两部分组成:一部分来自核函数g(x)，使得离候选目标中心越远的点权值越小;另一部分来自wω，是根据每个特征的区分能力获得的像素权值ω的加权和。特征的权值w越高，则跟踪结果越依赖于该特征;反之则对跟踪结果的影响越小。如果能够根据不同的场景对每个特征设定不同的权值，就可以实现更加准确可靠的跟踪。

4 自适应权值更新

在长时间的跟踪过程中，场景可能会发生变化，比如光照变化或目标姿态变化等。考虑到不同的特征对场景中目标与背景的区分能力是不同的，因此在目标与候选目标总的相似性度量值中应该更相信那些区分能力强的特征，而区分能力弱的特征容易受到背景的干扰，影响跟踪的稳定性和鲁棒性。故本文利用下式来评价每个特征对当前场景的可分性:其中，ρtk表示特征k的模板在t时刻与当前帧目标之间的相似性测度。

考虑到当场景(指背景和目标)遭遇到比较频繁的突变时，仅依靠目标在当前帧的信息来确定特征权值，可能会使跟踪变得不太稳定。为了避免权值的更新对目标变化过于敏感，更新公式如下:

5 模板更新

Mean Shift算法的缺陷之一就是缺乏必要的模板更新机制。若场景中突然发生了光照变化或者目标自身发生了平移旋转等变化，某些特征的模板和目标相比已经发生了很大的变化，导致二者的匹配度很低甚至无法匹配，这时需要及时更新该特征模板，保证跟踪能持续稳定的进行下去。模板更新存在的一个主要问题是模板漂移，这是因为在跟踪过程中，图像中的背景像素被误分类为目标像素，导致模型逐渐偏离真实值。而本文利用两个特征在跟踪场景中的互补性，仅选择那些权值较低即可分性差的特征进行模板更新，而那些权值较高即对当前场景适应力强的则保持不变。这样做，一方面可以避免错误的更新造成整个目标模型的漂移，另一方面又可以使模板对目标及环境变化有足够的适应性。具体方法是对本文的两个特征的权值求最小值，若该值小于模板的可靠性阈值，则更新该模板，具体公式如下:

其中Td为特征的可靠性阈值，取值范围为Td∈［0，0.5］。为了避免模板更新对目标的变化过于敏感，根据下式更新目标的模板:

6 实验及结果分析

本实验使用的硬件平台为2.00 HZ的CPU，在Windows XP操作系统下的计算机，软件平台为 Microsoft VC++6.0编程环境，用 Open CV1.0为基础进行实现。采集环境为超市，测试视频的图像大小为720*576，共150帧图像。基于颜色及边缘特征融合的核跟踪算法流程如下:

(1)初始化:采用手工标定的方法定位t=0时刻的目标位置为，目标的颜色及边缘特征特征被均匀划分为16份，形成的模板分别为qc和qe，权值分别为wc和we，算法的最大迭代次数为N=20，初始权值均为0.5，目标跟踪过程中使用的模板更新阈值为0.15，更新系数为0.8。

(2)以y0为候选目标起始搜索位置，根据公式(2)和公式(4)计算候选目标的颜色及边缘特征模型;

(3)根据公式(9)计算候选目标区域内的每个特征的像素的权值;

(6)根据公式(12)计算每个特征在当前场景下的可分性;

(7)利用公式(13)更新目标的各个特征在下一帧中的权值;

(8)根据公式(14)选择需要更新的特征模板，根据公式(15)更新该特征模板。

图3 跟踪结果对比

图3给出了基于颜色特征(CMS)的跟踪、文献［6］提出的基于颜色、形状和纹理(CSTMS)的自适应跟踪算法以及本文算法的实验结果。对比实验使用跟踪结果的x坐标误差、y坐标误差来度量跟踪结果的准确程度，使用平均跟踪时间(fps)来评价目标的实时效果，如表1所示。各算法的跟踪结果对比图3从上到下依次为CMS、CMTMS以及本文算法，从左至右依次为图像序列的第22、69、118和149帧。由于摄像机的运动，主要测量在背景运动情况下，目标的平移、旋转以及环境光照变化等对跟踪的影响。由图(3)可以看出，初始时刻在室内光照未变化时，虽然目标颜色和环境较为相似，但是CMS、CMTMS以及本文算法都能稳定地跟踪目标，其中基于颜色的Mean Shift跟踪效果最佳，其次是本文算法，CMTMS需要对所选择的多个特征进行优先级排序，然后选择可分性较好的两个特征进行跟踪，故处理时间稍慢一些。从117帧开始场景中发生光照变化时，导致目标外观的亮度发生了急剧变化，颜色线索的可分性逐渐恶化，CMS方法出现跟踪偏差，甚至有漂移的倾向。CMTMS提出的模型更新方法由于不能及时更新模型，所以也出现了跟踪偏差。而本文方法利用了两个特征在跟踪过程中的互补作用。当颜色特征的权值急剧减小时，形状特征权值逐渐变大，这时主要依靠边缘信息保证跟踪的准确性和稳定性，从而克服了光照变化对跟踪的影响。随着对目标颜色模型的及时更新，颜色特征的可分性逐渐增加，其权值也相应地提高，图4显示了特征权值在跟踪过程中的自适应变化。

图4 权值的自适应变化

表1 跟踪误差(均值标准差)和平均每帧跟踪时间对比

从表1可以看出，本文算法的X坐标和Y坐标的平均跟踪误差比CMS方法和CMTMS的跟踪算法都较小。算法在未经优化的情况下，同时受实验环境的影响，实时性如表1所示，在理想化情况下完全可以达到实时跟踪。

7 结论

本文使用多特征融合思想，利用特征之间的互补性，提出融合颜色和边缘特征在Mean Shift跟踪算法中，同时根据环境变化自适应调整特征之间的权值，并通过一种选择性模板更新策略，克服了跟踪过程中产生的模板漂移问题。实验证明，在运算时间增幅不明显的情况下，改进算法有效地提高了目标跟踪的鲁棒性和精确性，并在动态相似背景、光照变化、目标旋转平移等变化等情况都具有良好的适应性。作者认为，如果在多特征融合框架下引入背景运动补偿机制，可有效的解决背景的大幅度运动，我们对此将做进一步研究。

［1］李培华.一种新颖的基于颜色信息的粒子滤波器跟踪算法［J］.计算机学报，2009，32(12):2454－2463.

［2］ Nummiaro K，Koller-Meier E，Van-Gool L.An adaptive color-based particle filter［J］.Image and Vision Computing，2003，21(1):99 －110.

［3］ Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking［J］.IEEE Transactions on Patten Analysis and Machine Intelligence，2003，25(5):564 －575.

［4］张海青，李厚强.基于多线索的目标跟踪［J］.中国图象图形学报，2008，13(11):2187 －2196.

［5］ Collins R T，Liu Y X，Leordeanu M.Online selection of discriminative tracking features［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1631 －1643.

［6］ Junqiu Wang，Yasushi Yagi.Integrating color and shape-texture features for adaptive real-time object tracking［J］.IEEE Transactions on Image Processing，2008，17(2):235 －241.

［7］王欢，王江涛，任明武，等.一种鲁棒的多特征融合目标跟踪新算法［J］.中国图象图形学报，2009，14(33):489－498.

［8］ Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking［J］.IEEE Transactions Pattern Analysis and Machine Intelligence，2003，25(5):564 －575.

［9］朱虹.数字图像技术与应用［M］.北京:机械工业出版社，2011.

［10］冈萨雷斯.数字图像处理(第二版)［M］.北京:北京电子工业出版社，2007.