基于均值漂移的改进目标跟踪算法

刘天键，邱立达，张 宁

（闽江学院物理学与电子信息工程系，福州350108）

基于均值漂移的改进目标跟踪算法

刘天键，邱立达，张 宁

（闽江学院物理学与电子信息工程系，福州350108）

在可视化跟踪过程中目标窗经常会由于遮挡、光照、姿势等变化而发生跟踪漂移，影响目标跟踪的准确性和稳定性。为解决该问题，提出一种基于图层的离散域均值漂移算法，在离散域提取基于核的直方图作为目标模型，并对离散分区中的目标函数进行平滑以避免寻优搜索陷入局部极小值，从而提高目标跟踪性能。实验结果表明，与多示例学习算法相比，该算法的跟踪精度提高了16%，具有更好的实时性和鲁棒性。

目标跟踪；目标表示；离散域模型；均值漂移；迭代寻优

1 概述

目前，目标跟踪已经成为机器视觉领域的一个重要研究方向，现已提出许多针对目标跟踪的解决方案，主要有一般法和判别法2类可视跟踪算法。一般法采用寻优的方式解决目标跟踪问题，比如模板匹配、均值漂移和粒子滤波［1-3］；判别法通过区分目标和背景的方法解决跟踪问题，从而把跟踪问题转化为二值分类器设计问题，比如OAB（Online AdaBoost）［4］、多示例学习（M ultip le Instance Learning，M IL）［5-6］、跟踪学习检测（Tracking Learning and Detectiong，TLD）［7-8］。判别法需要通过多个目标和背景样本在线训练分类器。上述2种方法各有优缺点，跟踪效果依赖目标表示模型。在目标表示模型中，有基于模板的表示和基于特征的表示以及基于全局的表示和基于局部的表示。基于模板表示的模型简单，但对目标空间结构过于敏感，如文献［9］指出基于模板表示的模型存在的主要问题是目标函数不够平滑使得搜索易陷入局部最小值。通常采用高斯金字塔的方法模糊图像以达到平滑目标函数的目的。但近年来的研究结果表明，高斯金字塔并非是平滑目标函数的最佳选择。利用特征模型提取目标的边缘、颜色、纹理特征作为目标特征，使用直方图来描述目标，对姿势变化不敏感但对目标空间结构变化敏感。在特征模型表示目标的算法中，均值漂移算法以其高效、实时性能引起学者们的广泛关注。该算法是一种基于核密度估计的模式匹配算法，利用视觉特征，比如灰度、颜色等信息描述跟踪目标，通过迭代计算最新的样本分布来估计非参概率密度，从而实现目标的定位和跟踪。均值漂移算法在引入到机器视觉领域后，用于解决图像滤波、图像校准、目标跟踪等问题。但在跟踪过程中，目标表观和背景变化会影响特征模型的表示，目前仍是跟踪算法面临的主要问题。文献［10］提出一种基于背景加权的直方图算法以消除目标模型中的背景干扰，但该方法在减少背景信息的同时模糊了前景信息，导致跟踪器性能下降。学者们对于改善直方图的空间信息进行了大量研究，包括多核、多片区方法［11］。文献［12］提出一种方向梯度直方图（Histogram of Gradient，HOG）方法，当目标表观发生遮挡时，仍能稳定跟踪目标，但该方法对噪声敏感，跟踪准确性易受尺度、分辨率的影响。其他改进方法，如增加高阶统计矩、时域信息和特征选择［1-2］，这些方法提高了传统直方图法的性能，但需要确定核函数的数量和形状，增加了算法复杂度。文献［13］提出一种新型的目标表示模型，即分布域（D istribution Field，DF）目标描述子模型，能够平滑目标函数的同时保留目标的像素信息，在复杂环境下跟踪目标可获得满意的效果。文献［14］提出一种基于分布域表示的多示例学习跟踪器，在分布域选择判别能力强的特征替换Harr特征，获得了鲁棒的跟踪效果。基于此，本文提出一种离散域均值漂移（D iscrete Field M ean Shift，DFMS）算法，在均值漂移框架中引入离散域目标表示模型，通过改进均值漂移算法，实现对目标由粗到细的跟踪。

2 离散域目标表示

在文献［3］中，离散域（DF）目标模型定义像素为某一特征值的概率分布数组。例如，在灰度特征空间，每个像素在0～255之间存在一个概率分布。离散域模型用（2+N）维的矩阵d表示，前2维分别表示目标图像的高度和宽度，其余N维对应不同的特征空间。对于灰度特征空间分辨率为h×w的图像，输出的三维离散域模型为h×w×m，m为灰度特征值的分区数。将一个图像I按照分区数扩展成矩阵d：

其中，i和j分别表示图像的行和列；K表示可能的像素值，称为分区中的一层。由于模型沿着特征维的向量和为1，因此可以看成是一个概率分布。DF首先在χ和y维分别用2D高斯滤波器进行平滑，即对于每一图层K进行滤波，在传播信息的同时不会损失信息。

其中，h是标准差为σs的高斯核；“*”表示卷积。卷积前，d（i，j，K）中为1的值可以解释为在原始图像中这个位置有一个灰度级为L的像素。卷积后，中为1值的语义为在原始图像中靠近这个位置有一个灰度级为L的像素，这样就在模型中引入了位置不确定性。由于在卷积过程中没有引入其他图层的像素值，因此不会造成目标像素值信息的损失。如果式（2）中的卷积核本身符合概率分布，那么仍然可以保持沿特征维的和为1，满足DF模型要求。在特征域进行与空间域类似的操作，使得模型能够适应目标表观、姿势和阴影的变化，如式（3）所示对进行特征维平滑后输出。

其中，hσf是标准差为σf的高斯核。为便于推导，将h×w×m维的d～重构为n×m维的矩阵ν，n= h×w。

扩展和平滑后的DF可以看成在目标表观模型中引入不确定性。DF模型反映了原始图像在表观和位置的小范围变化结果，是相邻图像集合中的一种紧凑表示模型。模型中的权值满足简单假设，即相邻图像中像素值保持不变的概率较大、发生变化的概率较小。采用DF模型衡量目标相似度时，可以用不同的距离度量函数比较目标模型和候选模型，本文采用巴氏距离度量。在跟踪过程中，DF模型的更新采用FIR滤波实现。

为评价DF模型的性能，基于引力盆特性对DF与其他描述子进行比较。引力盆定义为围绕点P的一个区域，在这个区域中的任何位置都能通过目标函数梯度下降最后达到点P。采用广泛性和专注性评估引力盆的性能［3］。广泛性是指描述子适用的对象广度，广泛性越广表现为引力盆的引力半径越大；专注性是描述子适用单一对象的程度，专注性高的描述子表现为引力盆斜坡陡、半径小。图1显示了不同描述子的引力盆作用范围，可以看出，DFMS描述子具有比基于核的均值漂移（M ean Shift，M S）描述子更宽的收敛半径，同时比基于直方图的Bhatta描述子更平滑的特性。对于Bhatta描述子而言，由于模糊化的DF模型使得亮度加权范围更大，因此DF模型广泛度更广；同时由于没有混入不同亮度级的像素，对于MS描述子，DF模型专注度更高。

图1 各目标描述子的目标函数比较

3 基于均值漂移算法的目标跟踪

假设t时刻跟踪目标选择为像素位置为｛χi｝i=1，2，…，n的矩形区域，用K：R2→R+表示核函数，不同位置对应不同权值。基于核的目标DF模型可以表示为：

其中，c为核函数的中心位置；ν（i，j）表示第j层DF模型；C为归一化因子，使得∑mj=1qj=1。对于每一个图层ν有νj=νj（t）=DF（χi，t）=ν（：，j）。将这些νj组合成n×m的矩阵。定义核函数向量为Ki（c）= K（χi，c），得到目标模型。

假设时刻t′，目标候选模型的中心为c，候选DF模型表示为：

目标函数采用离散域的巴氏距离度量，寻优过程求距离最小值等同于求相似度最大值。因此，可以通过估计目标位置求得相似度函数最大值。

其中，寻优过程通过计算梯度，并使梯度等于0得到相似度函数最大值。式（11）围绕P（c）进行泰勒级数展开，忽略高次项后，得到距离最小化的条件为：

最优解可以表示为加权平均的形式：

其中，g（χ）=-K′（χ）。寻优过程可以看成是在目标函数上的梯度降过程。为进一步提高算法性能，采用多个DF模型描述目标，这些模型按照对应的σs值递减排列，即调整空间模糊度，使得DF模型包含不同频率的信息。在跟踪过程中，采用从粗到细的DF模型进行搜索，最平滑的DF模型最先用于搜索，达到局部最小值后，启用第2个DF继续搜索，从而提高算法实时性。本文在均值漂移算法框架中，引入离散域目标表示，用模糊数组代替目标模型中的函数，使得目标函数伸展平滑，从而提高系统性能。设置空间平滑参数，亮度平滑参数σf=0.625，ɷf=5，分区数m=16，学习因子λ= 0.95，目标跟踪过程具体如下：

（1）初始化目标离散域模型，并对二维空间X，Y及特征空间进行平滑：

（2）初始化目标位置（χ1；y1）。

（3）计算候选目标离散域模型：

（4）对目标函数寻优，得到目标位置估计（χ′；y′）。

（5）更新如下模型并返回步骤（3）循环操作直到最后一帧：

4 实验结果与分析

为验证本文算法性能，在公开测试集上［15］与OAB（Online AdaBoost）［4］，SBT（Sem i-supervised Tracking）［5］，BSBT（Beyond Semi-supervised Tracking）［6］，多示例学习（Multiple Instance Learning，M IT）［7］，跟踪学习检测（Tracking Learning andDetecting，TLD）［8］算法进行性能比较。在6个不同视频序列中进行对比测试，包含遮挡、姿势变化、光照变化和目标形变等场景。测试平台在一台硬件为Intel i7 3770 CPU 3.4 GHz、6 GB RAM，软件为Matlab7.8的PC上进行。为定量比较跟踪器性能，采用预测边界框与基准边界框的中心位置误差（Center Location Error，CLE）和重叠率（Overlap Rate，OVR）2个评价指标。OVR比CLE更具参考价值，因为当跟踪失败时，CLE可以是某个任意值，而OVR值总为0。DFMS参数设置如第3节所示。图2给出了定性比较的结果。

图2 算法定性比较结果

可以看出，在适当遮挡、光照变化和姿势变化的序列中，DFMS获得了鲁棒的跟踪结果和较高的跟踪精度。在coke序列中包含剧烈的光照变化和适当遮挡，第189帧，当跟踪的可乐罐从台灯移动到叶子中时，由于发生了光照变化和部分遮挡，其他跟踪算法跟踪失败，而本文算法仍可以正确地跟踪目标。在其他序列中，本文算法也具有较好的跟踪性能。在这些序列中，DFMS能在一个很宽的引力盆范围中按照梯度降的方法回到基准位置。表1给出了定量比较结果。

表1 算法跟踪性能比较

图3是6种算法在coke序列上的中心位置误差（CLE）和重叠率（OVR）指标，其中，CLE的门限值为20个像素；OVR的门限值为25%，可以看出，DFMS明显优于其他算法。采用正确率、成功率进行性能比较［15］，并进一步利用曲线下面积（AUC）排名［15］综合评价跟踪器的性能。

图3 算法在coke序列上的定量评价结果

从图4可以看出，DFMS的目标中心平均距离的正确率比M IL算法提高了16%，DFMS在保持成功率（s）的基础上，显著提高了正确率（P）。可见，DFMS算法可以适应复杂环境的变化，如适当遮挡、表观变化、姿势和光照变化等。例如，当发生遮挡时，DF模型随着遮挡物变化而更新，由于遮挡物与目标处于不同图层，因此模型被遮挡像素在目标图层附近呈现较小的概率。如果在接下来的数帧中，遮挡物消失，DF模型将不会被遮挡物污染，并能成功地避免漂移。这正是本文算法能够能在多个视频序列中获得满意效果的原因。而且参数σs和σf的选择也很重要，如果σs选得太大，模糊范围增大，目标函数平滑，对目标空间结构不敏感，DF模型趋同，将导致目标细节信息的丢失。如果选得太小，模糊程度不够，目标函数不够平滑，跟踪器易陷入局部最小值。因此，需要根据按照目标尺寸选择σs，通常是大目标选择大σs，小目标选择小σs。另外，σf的选择也受到其他因素的影响，例如，表观模型中灰度的方差，如果σf减小，则跟踪小目标的性能趋向变好；如果σf增大，则跟踪大目标的性能趋向变好。核函数的选择对结果影响不大，为使g（χ）=-K′（χ）= 1，选择Epanechnikov核函数。参数λ控制模型的更新速度，如果λ值较大，则更新慢，容易克服遮挡，但不容易适应表观变化；如果λ值较小，则更新快、适应变化快。综上所述，应根据应用场景的需要在克服遮挡和适应表观变化之间进行折中选择。

图4 算法在6个视频序列上的定量评价结果

5 结束语

本文提出一种基于图层的改进型均值漂移（DFMS）算法。该算法在跟踪过程中采用DF模型，该模型对姿势变化不敏感，对目标几何结构敏感，并且在实现目标模型模糊的同时，能避免目标模型被污染。因此，DFMS应用于表观、姿势、光照等适当变化的场景时，能取得较好的跟踪性能。下一步将结合梯度方向、尺度变化的跟踪场景对本文提出的均值漂移算法进行改进，从而实现目标的鲁棒跟踪。

［1］ Cannons K J，Gryn J M，Wildes R P.Visual Tracking Using a Pixelwise Spatiotemporal Oriented Energy Representation［C］//Proceedings of the 11th European Conference on Computer Vision.New York，USA：ACM Press，2010：511-524.

［2］ Liu Tianjian，Zhang Zutao.Adaptive Double Kalm an Filter and Mean Shift for Robust Fast Object Tracking［J］.International Journal of Advancements in Computing Technology，2013，5（6）：349-356.

［3］ 詹建平，黄席樾，沈志熙，等.基于均值漂移和卡尔曼滤波的目标跟踪方法［J］.重庆理工大学学报：自然科学版，2010，24（3）：76-80.

［4］ Stalder S，Grabner H，van Gool L.Beyond Semisupervised Tracking：Tracking Should Be as Simple as Detection，but Not Simpler than Recognition［C］// Proceedings of IEEE International Conference on Computer Vision Workshops.Washington D.C.，USA：IEEE Press，2009：1409-1416.

［5］ Ning Jifeng，Shi Wuzhen，Yang Shuqin，et al.Visual Tracking with Online Multiple Instance Learning［J］. Image and Vision Computing，2009，31（11）：983-990.

［6］ 黄叶珏，郑河荣.基于在线多示例提升随机蕨丛的目标跟踪［J］.计算机应用，2012，32（11）：3178-3181.

［7］ Kalal Z，Matas J，Mikolajczyk K.P-N Learning：Bootstrapping Binary Classifiers by Structural Constraints［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2010：49-56.

［8］ 王守超，李小霞.基于在线学习和结构约束的目标跟踪算法［J］.计算机工程，2012，38（18）：140-143.

［9］ Szeliski R.Image Alignment and Stitching：A Tutorial［J］.Foundations and Trends in Computer Graphics and Vision，2006，2（1）：101-104.

［10］ Ning Jifeng，Zhang Lei.Robust Mean-shift Tracking with Corrected Background-weighted Histogram［J］.IET Computer Vision，2012，6（1）：62-69.

［11］ Mobahi H，Zitnick C L，Ma Y.Seeing Through the Blur［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2012：1736-1743.

［12］ Dalal N，Triggs B.Histogram s of Oriented Gradients for Human Detection［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D.C.，USA：IEEE Press，2005：886-893.

［13］ Sevilla-lara L，Learned-miller E.Distribution Fields for Tracking［J］.IEEE Conference on Computer Vision& Pattern Recognition，2012，157（10）：1910-1917.

［14］ Ning Jifeng，Shi Wuzhen，Yang Shuqi，et al.Visual Tracking Based on Distribution Fields and Online Weighted Multiple Instance Learning［J］.Image and Vision Computing，2013，31（11）：853-863.

［15］ Wu Yi，Lim Jong-Woo，Yang Ming-Hsuan.Online Object Tracking：A Benchmark［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D.C.，USA：IEEE Press，2013：2411-2418.

编辑 陆燕菲

ImProved Object Tracking Algorithm Based on Mean Shift

LIU Tianjian，QIU Lida，ZHANG Ning
（Department of Physics and Electronic Inform ation Engineering，Minjiang University，Fuzhou 350108，China）

In the process of visual tracking，target window is always drifted for the illumination light change，deformation and poses change which affect the accuracy and robust tracking performance.To solve this problem，this paper proposes a novel M ean Shift（MS）algorithm based on picture layer which represents target model by the kernel histogram in the discrete fields.In order to improve the tracking performance，the objective function is smoothed to avoid falling into the localminimum in the search procedure.Experimental results show that the tracking precision of proposed algorithm increases by 16%com pared with Multiple Instance Learning（M IL）algorithm，and it has better real-time and robustness.

object tracking；object representation；discrete domain model；M ean Shift（MS）；iterative optimization

刘天键，邱立达，张 宁.基于均值漂移的改进目标跟踪算法［J］.计算机工程，2015，41（9）：281-285，291.

英文引用格式：Liu Tianjian，Qiu Lida，Zhang Ning.Im proved Object Tracking Algorithm Based on M ean Shift［J］. Computer Engineering，2015，41（9）：281-285，291.

1000-3428（2015）09-0281-05

A

TP242.6

10.3969/j.issn.1000-3428.2015.09.052

福建省教育厅基金资助项目（JA12263，JB11127）；福州市科技合作基金资助项目（2013-G-86）。

刘天键（1975-），男，副教授、博士，主研方向：目标检测与跟踪；邱立达、张 宁，讲师、硕士。

2015-03-03

2015-05-14 E-m ail：skybright@aliyun.com