漂移系数优化颜色直方图的Mean Shift算法

宋康康，陈恳，郭运艳

宁波大学信息科学与工程学院，浙江宁波315211

1 引言

近年来，M ean-Shift算法以其无参数、快速模式匹配的特性被广泛应用到目标跟踪领域[1-3]。经典M ean Shift算法利用空间核加权颜色直方图作为模板，通过搜索局部巴氏系数最大值，实现目标跟踪定位。颜色直方图是对图像在颜色空间中分布的一种简单的非参数估计，描述了图像的全局统计特征，具有旋转和平移不变性，而且特征提取方便，因此常常作为特征模型广泛应用于图像检索和目标跟踪之中。另一方面颜色特征容易受光照条件变化的影响，因此利用颜色特征的M ean Shift算法的一个挑战是如何提高跟踪的鲁棒性。

为克服上述颜色直方图的弱点，许多学者提出了许多改进方法。例如，用背景像素与目标像素定义加权系数，以此计算空间直方图，实施目标跟踪定位，主要存在的问题是如何鲁棒的区分背景与目标[4]。文献[5-6]利用目标颜色空间和纹理特征，构建边缘直方图，用以区分目标与背景信息，提升颜色直方图的鲁棒性。

利用加权求取颜色特征和边缘特征的巴氏系数，进行目标特征匹配和跟踪，弥补了单一颜色特征不稳定的弱点，但未涉及模板更新问题[7]。利用可见光和红外双通道做目标多特征信息融合，克服了可见光条件下，颜色直方图对光照条件敏感的问题，但是也进行模板更新[8]。采用目标先验知识创建了多个颜色直方图模板，增强了颜色直方图模板描述目标特征的能力，并能实时选取最优模型，但是计算稍微复杂[9-10]。

上述研究者主要利用多特征或多模型来增强颜色特征刻画目标的强度，取得了不错的效果，但也产生了计算比较复杂，设备多等问题。本文试图直接从均值漂移的漂移系数出发，提升颜色直方图中目标的信息特征，同时分析论证了属于目标颜色的特征对漂移贡献较多，依据这个特点，对漂移系数较大的特征点进行目标特征的强化，进而减少了收敛迭代次数。经多次强化后，颜色直方图中的目标特征会凸显，若不能够及时引入因目标特征改变而产生的新特征，会使算法失效，对此又提出了模板更新机制，将新的目标特征信息加入到直方图中，从而增强了颜色特征的鲁棒性，最终实现了算法快速稳定的跟踪效果。

2 基于漂移系数的加权颜色直方图

2.1 目标信息表示

在M ean Shift算法中，跟踪目标通常定义为一个椭圆或者矩形的跟踪窗口内，用颜色直方图描述目标的颜色特征信息，则目标参考模型可以表示为其中

Ch是归一化系数，h是核带宽，x0是中心像素坐标，u是颜色特征值，xi是跟踪窗口中第i个像素，共有n个像素，k(x)是非增、连续的核函数，b(xi)将颜色特征映射到对应的直方图空间。当以y为中心时，候选目标模型则按如下的式子建立，={u}u=1,2,…,m，其中

同样Cc为归一化系数。

2.2 Mean Shift跟踪算法

采用Bhattacharyya系数度量候选模型与参考模型之间的相似性。通过Mean Shift算法迭代，迭代过程如下：

其中y1为新的目标中心坐标，

y0是当前候选目标区域的中心位置，则基于Mean Shift算法的目标跟踪通过反复的迭代式（4），使目标从当前y0不断的移到新位置y1，直至Bhattacharyya系数最大或者达到规定的迭代次数为止，得到的y1即M ean Shift

偏移得到的跟踪窗口的新的中心坐标。

2.3 基于背景的加权颜色直方图

为削弱目标周围背景信息对核窗口内目标信息的干扰，Comaniciu[11]等人提出了基于背景直方图加权的M ean Shift算法，即：

2.4 基于漂移系数优化的加权颜色直方图

M ean Shift算法在求取漂移系数时，将每个当前的点对应到参考的特征空间中，与参考模板相比较而获得。对于那些属于目标颜色特征空间中的点，其权值要较大，这样算法就能快速收敛到目标中心。权值的大小与对应颜色特征出现在颜色直方图中的概率大小成正相关，因此如果目标参考模板中混入较多背景信息，反过来冲淡了目标本身特征信息，从直方图上看，对应目标特征的bin的高度会降低，即其概率变小，导致属于目标的漂移系数下降，从而导致算法收敛产生偏差，出现跟踪效果差甚至丢失目标等情形。

Cheng[13]定义了一族核函数，使得随着样本与被偏移点的距离不同，其偏移量对均值偏移向量的贡献也不同，其次还设定了一个漂移系数，使得不同的样本点重要性不一样，这大大扩大了M ean Shift的适用范围。这里漂移系数是指式（5），若将系数全部设为1，核函数取Epanechnikov[13]，其影子函数为常数，式（4）就退化为M(x)=，即为一般的均值函数，此时核窗口中心的每个点对均值偏移的贡献都是相同的，而M ean Shift算法赋予每个点不同的系数，最终收敛于加权中心处。

针对背景加权算法中存在的缺陷，根据漂移系数在均值漂移算法中的特点，本文提出了基于漂移系数优化的颜色直方图的M ean Shift算法。某像素点的漂移系数反应了该点对漂移的贡献，漂移系数越大贡献也就越大，收敛速度越快，同时表明属于目标的像素点拥有较大的贡献。

如图1显示的是将核窗口内较大的漂移系数点映射到一幅与核窗口等大的二值图中，白色点表示该点具有较大的漂移系数，黑色点的漂移系数则较小。可以清楚看到，属于目标颜色特征确实拥有较大漂移系数，因此跟踪效果也十分理想。

图1 漂移系数分布图

2.5 漂移系数优化的颜色直方图

由于目标的颜色直方图容易受到外界的影响，使得颜色直方图会混入早上，而通过漂移系数可以有效去除其中的噪声。对于跟踪中的每一帧，逐个检测核窗口内像素点的贡献值，按贡献大小，调整参考颜色直方图，使目标模板能够刻画目标特征，增强目标与背景的区分度。对每个核窗口内的像素点，做如下的运算：

u′是核窗口内的某一像素点对应到颜色特征空间的特征值，U是目标的颜色特征空间中拥有较大漂移系数的特征值的集合，M是核窗口内所有像素点的漂移系数的平均值，为避免漂移系数等于0，算法会设定一个最小下限ε（一般取0.01），p是核窗口内的某个像素点，b(p)将像素点映射到颜色特征空间，w(b(p))为颜色特征空间的某个特征值对应的漂移系数，颜色特征空间一般设为16×16×16 bin，即将R、G、B量化到一个三维数组中。这样经式（7）处理后，系数较大的颜色特征被保留了下来，小系数的颜色噪声去除了。归一化后得到新的参考目标模型newq′={newq′u′}，即更新后的参考目标模型，其不仅具备了目标的应有的特征信息，而且大大抑制了背景的信息。

图2是第1、291帧的跟踪结果。图3中的左图是第一帧的目标参考模型，右图是第291帧时目标的参考模型。从实验结果看，在第一帧中，虽然使用了背景颜色直方图加权，抑制了部分信息，但是颜色直方图信息比较杂乱，零星分布着一些噪声信息，这些信息削弱了目标特征的表达。本文算法通过对目标模型中漂移系数较小加以抑制，从而突出了目标的特征信息，从右边参考模型上可以看到，颜色直方图中的有效信息被放大了，噪声也被充分抑制了，并且整个跟踪效果十分好。图4是算法迭代次数图，圆圈标记的曲线是本文算法的迭代次数，十字标记的是对比算法的。从图4迭代次数上看，本文算法的迭代次数更少，图5显示了各个特征值对应的漂移系数值。从图5上看，本文算法的系数大而集中，因而迭代次数就少，收敛更快。

本文算法能够按照当前帧中目标的特征，优化目标参考模型的建立，使得每次漂移权值都能够取得较大，克服了过时的目标参考模型引起的目标特征描述落后的缺点。虽然在每帧中能够逐步降低背景成分信息，但是存在一个不能够引入新的目标特征信息的缺点，对目标变化中引入的有效目标信息要在颜色直方图中及时体现，因此要进行模板更新。

图2 跟踪结果图

第1帧的目标参考模型

图3 目标参考模型

图4 迭代次数

图5 漂移系数

2.6 基于漂移系数的模板更新算法

模板更新算法是目标匹配算法的关键所在，若不及时更新模板，会导致匹配失败，从而导致跟踪失败。更重要的是，采用颜色特征的M ean Shift算法更容易受到外界信息的干扰，主要原因是颜色信息受光照条件影响比较大，光照变化引起的目标颜色的轻微变化也会导致颜色直方图的剧烈变化。因此模板更新是关系算法稳定性的关键问题。许多学者也提出了很多模板更新方法[14-15]。

模板更新主要涉及三个问题，一是背景信息的抑制问题，二是新目标信息的引入问题，三是更新时机的问题，当然还有许多其他问题[16-17]。第一个问题已经在前面一节中解决，此节主要论述后两个问题。时机的选择很重要，选的太早，就浪费宝贵的处理时间；若过晚，则更新后的模板可靠性很低。因此必须时时检测目标颜色特征的变化情况，在变化还不是太明显的时候，便逐步更新。对于更新条件，本文按如下的公式计算：

则更新条件为sumq＜0.8。sumq是对所有较大系数所占颜色直方图中的比率，如果比率小于0.8，认为当前参考模型对漂移贡献开始减少，需引进新的颜色特征，因而进行信息引入式的模板更正。首先建立目标周围2倍区域背景的颜色直方图={u}u=1,2,…，k，其共有k个特征值，参考模板更新公式为：

3 实验结果

为验证本文算法的有效性，根据不同的要求，取了标准测试视频中的三个典型序列，每个序列中跟踪目标的速度和背景复杂度各不相同，与背景加权直方图的M ean Shift算法比较，主要比较内容为跟踪算法的迭代次数和跟踪定位效果，以及模板更新。

3.1 实验1

场景是由运动相机拍摄的，而且背景随着相机的移动而变化，背景信息嘈杂，跟踪目标的速度不是很快，但具有一定的旋转变化，目标颜色特征与背景有一些相似之处。

图6为跟踪定位结果，分别取第1、77、89帧的结果，上两行为背景加权算法的跟踪结果，后两行为本文算法的结果。首先从取出的几张典型的跟踪定位图中看，背景加权算法受到了背景信息的干扰，产生了一些偏差，本文算法要优于背景加权算法，特别是第77帧时，本文算法较精确定位了目标，而背景加权算法偏离目标中心较大。主要原因是由于背景加权的颜色直方图在背景信息中含有与目标颜色特征信息类似的特征时，反过来会抑制目标信息，而本文算法能够对权值的分析，恢复被抑制的有效信息，避免了这一弱点。

图6 本文算法与背景加权算法跟踪结果比较

图7显示了迭代结果，十字标记的曲线是本文算法结果，方块标记的是背景加权算法的结果。从迭代次数上看，本文算法的结果要明显优于背景加权算法。原因是目标特性信息的提升，给予漂移时更大的权值，从而减少了迭代次数，平均迭代次数在4.1左右，效率要高出很多，背景加权算法要多与5次。

图7 迭代次数比较

3.2 实验2

高速运动的橄榄球运动员，其背景要简单些，但有部分遮挡情况发生，伴随有明显的旋转等目标外型变化，且是在摄像机运动情况下拍摄的，并且目标运动快速，但其颜色特征与背景区别较明显。

图8为跟踪定位结果，分别取第1、45、66帧的结果，上两行为背景加权算法的跟踪结果，后两行为本文算法的结果。从跟踪定位效果看，两者都能够成功跟踪定位目标，而且效果好，本文算法要略胜一筹。特别在第66帧时，背景加权算法定位的中心在运动员的腿部区域，而本文算法则在胸部区域，这是由于在初始化的目标的大部分成分集中在胸部区域，而此区域对漂移贡献较大，因而这些信息会被提升，最后的跟踪定位中心为胸部区域。

图8 跟踪结果比较

图9显示了迭代结果，十字标记的曲线是本文算法结果，方块标记的是背景加权算法的结果。再从迭代次数上看，本文算法的平均迭代次数为5.09，而背景加权算法为6.20，要优于后者，同样是由于目标特征信息的提升，从而使属于目标的特征提供了较大的漂移系数，迭代收敛速度也就更加快。综合上述实验结果，在上述复杂程度的场景下，与背景加权算法相比，本文算法不仅跟踪定位精度高，而且效率高。

图9 迭代次数比较

3.3 实验3

图10为模板更新结果，分别取第1、88、199帧的结果，上两行为背景加权算法的跟踪结果，后两行为本文算法的结果。选取目标的头部，头部选择后，脸部特征无法捕捉，此时大权值所占直方图比率下降，达到模板更新条件，进行模板更新。第一行为背景加权算法，没有及时采取模板更新，在第88帧开始，跟踪定位产生偏差，随后就丢失跟踪目标。而第二行为本文跟踪结果，当目标旋转后，采取了模板更新策略，改变了目标参考的特征信息分布，使得在整个跟踪过程中依然具有良好的跟踪定位效果。

图10 模板更新结果

4 总结

本文主要分析了均值漂移算法中漂移系数的特性，即属于目标特征的漂移系数相对较大，依据此特性将漂移系数引入到颜色直方图的计算中去，有利于目标特征的提升，并且能够区分出核窗口内的背景等其他信息，通过抑制核窗口内的噪声，从而增强了目标特征信息的刻画，使得迭代速度加快。再通过模板更新反映目标当前特征，使得颜色直方图得到更新，鲁棒性得到增强。最后从两个不同复杂度的标准测试序列，以及不同的目标速度，验证了本文算法执行效率高，稳定性好。

[1]Shah K A，Kapadia H K，Shah V A，et al.Application of Mean-Shift algorithm for license plate localization[C]//Proceedings of 2011 Nirma University International Conference on Engineering（NUiCONE），2011：8-10.

[2]Zhou Huiyu，Yuan Yuan，Shi Chunmei.Object tracking using SIFT features and mean shift[J].Computer Vision and Image Understanding，2009，113（3）：345-352.

[3]王相海，方玲玲，丛志环.基于MSPF的实时监控多目标跟踪算法研究[J].自动化学报，2012，38（1）：139-144.

[4]李小和，张太镒，沈晓东，等.基于加权空间直方图的均值漂移目标跟踪[J].光电子·激光，2010，21（5）：767-771.

[5]王新红，王晶田，敏杨，等.基于空间边缘方向直方图的Mean Shift跟踪算法[J].中国图象图形学报，2008，13（3）：586-592.

[6]戴渊明，韦巍，林亦宁.基于颜色纹理特征的均值漂移目标跟踪算法[J].浙江大学学报，2012，46（2）：212-217.

[7]郑玉凤，马秀荣，赵晓琳，等.基于颜色和边缘特征的均值迁移目标跟踪算法[J].光电子·激光，2011，22（8）：1231-1235.

[8]程咏梅，王进行，魏坤，等.基于加权Mean—Shift可见光/红外双通道目标跟踪[J].光子学报，2010，39（2）：357-363.

[9]左军毅，梁彦，潘泉，等.基于多个颜色分布模型的Camshift跟踪算法[J].自动化学报，2008，34（7）：736-742.

[10]袁广林，薛模根，谢恺，等.多颜色直方图自适应组合Mean Shift跟踪[J].中国图象图形学报，2011，16（10）：1832-1839.

[11]Comaniciu D，Ramesh V，Meer P.Kernel based objecttracking[J].IEEE Transactions on Pattern Analysis and--M achine Intelligence，2003，25（5）：564-577.

[12]Ning J，Zhang L，Zhang D，et al.Robust mean-shift trackingwith corrected background-weighted histogram[J].Com-puter Vision，IET，2012，6（1）：62-69.

[13]Cheng Y.Mean shift，mode seeking and clustering[J].IEEETrans on Pattern Analysis and M achine Intelligence，1995，17（8）：790-799.

[14]彭宁嵩，杨杰，周大可，等.Mean-Shift跟踪算法中目标模型的自适应更新[J].数据采集与处理，2005，20（2）：125-129.

[15]朱胜利，朱善安.基于卡尔曼滤波器组的Mean Shift模板更新算法[J].中国图象图形学报，2007（3）：460-465.

[16]潘吉彦，胡波，张建秋.抑制模板漂移的目标跟踪算法[J].电子学报，2009，37（3）：622-627.

[17]Jia Z，Balasuriya A，Challa S.Target tracking with Bayesianfusion based template matching[C]//Proc of IEEE IntConf on Image Processing.[S.l.]：IEEE，2005：2826-2829.