基于分块背景更新的均值飘移跟踪算法

杨 莉，李茂林

（南昌大学 信息工程学院，江西 南昌330031）

0 引 言

研究者们对目标跟踪做了大量研究并取得了许多成果［1－3］。其中，均值飘移跟踪算法因其高效性、简便性等优点被广泛应用。经典均值飘移跟踪算法多只对兴趣目标建立颜色直方图，没有考虑背景信息对其定位的影响，而直方图只能反映目标区域整体的统计特性，不能反映跟踪目标的空间特征状态信息。Ning等［4］验证了背景加权跟踪算法没有起到实际效果，并采用改正后的权重背景直方图有效地降低了背景对目标定位的干扰，但是当背景信息有较大改变时，该算法基于全部背景信息更新的策略，忽略了更新前的背景信息对目标定位的作用；罗富贵等［5］采用赋予目标区域内像数点大权重的算法，但需要目标模型包含非常少的背景信息；王建华等［6］提出了赋予背景信息内像数点小权重的算法，但背景中出现与目标区域相似度高的颜色信息时，缺乏有效处理。这两种算法有相似之处，较好地排除了目标窗口内背景信息对目标定位的干扰，但忽略了目标窗口外围的背景信息对目标定位的问题。

为了利用目标物体的空间信息并排除背景区域信息对目标定位的干扰，本文提出了基于分块背景更新的改进算法。首先把背景区域分成4小块，然后建立融合背景信息的颜色直方图的目标模型，再引入距离权重并在跟踪过程中动态地更新背景信息。实验结果表明，与整块背景信息更新策略和加权更新背景信息的策略相比，改进算法具有更高的迭代收敛效率和更强的抗背景干扰能力。

1 经典均值飘移跟踪算法

在经典均值飘移目标跟踪中，常用颜色直方图描述兴趣目标。目标模型可以表示为在目标区域上的颜色特征值的概率值。令｛｝i＝1，…n为归一化的目标模型中心像素点的位置。相应目标模型特征（u＝1，2，…，m）的概率密度为

式中：k（x）——核函数，用于对像素进行加权，n是目标窗口中像数点的个数；m 是特征空间的元素个数；b（x＊i）将目标区域中的每个像素点映射到对应的特征空间；δ［b（x＊i）－u］是用于判断目标区中的任意像素x＊i的值是否等于第u个特征值，C 为归一化常数。类似式 （1），令｛xi｝i＝1，…nh为当前帧候选目标区域中的像素点，同理可计算该跟踪窗口中候选目标的概率密度

式中：y——候选目标的中心坐标；h——跟踪窗口带宽；nh——目标候选窗口中全部像素的数量；Ch——归一化常数。

为了确定待跟踪目标在新的帧中的位置，目标直方图与候选目标直方图之间的相似性常用巴氏系数来度量，巴氏系数计算方法如下

均值漂移算法就是在新的帧中确定一个候选位置，使得巴氏系数最大。均值飘移向量表示为

在新的帧中，以目标在前一帧的最佳位置yo作为当前时刻目标的初始位置。利用式 （4）计算得到目标在该位置的均值飘移向量m（yo），再用此向量来移动初始位置得到新的位置y′，如此反复直到满足一定的收敛条件 （最大迭代次数或者相邻两帧位置偏移足够小）。最终的收敛位置就是目标在当前帧中的最终位置。

2 基于分块背景更新的加权目标跟踪算法

2.1 基于分块背景的目标模型

为了体现各个方向上的背景信息对目标定位的作用，进一步提高改进算法的效率，采用分块背景模型。首先在目标窗口周围定义一个面积是目标窗口3倍的背景区域［1］，如图1所示，中部深色区域是目标窗口，周围是背景区域，把背景区域划分成4个子块 （每个子块各为一种颜色），依次计算每个子块的直方图模型4）。赋予每个子块一个加权系数，构成整体背景信息模型

图1 背景区域的划分

为了使建立的颜色直方图能更好地辨别背景区域和目标区域，降低背景信息对目标定位的干扰，采用融合背景信息的颜色直方图。在目标区域，计算目标模型，然后与用式 （7）计算出来的背景模型的权重系数融合［4］，形成本文提出的基于分块背景信息的目标模型。而候选目标模型则不融合背息信息，类似目标颜色模型，候选目标模型表示为（y）。

2.2 背景模型的更新

为了提高跟踪的精度，需要动态地更新背景模型。Ning等［4］提出了基于巴氏系数的全部背景信息更新算法，忽略了更新前的背景信息对目标定位的作用。Wang等［7］提出基于巴氏系数的加权更新算法，需要设置较高的阈值，增加了计算时间。Vilaplana等［8］对每帧图像都加权更新背景，该算法更新的过于频繁。本文采用分块背景的更新方法。首先，在当前帧中，分别计算每个子块的背景模型和整体背景模型然后计算新旧整体背景模型的巴氏系数

通过巴氏系数选择性地更新背景模型，当ρ大于或等于事先给定的阈值，说明新旧整体背景信息不更新背景模型。否则更新背景模型，并计算各个子块的新旧模型的巴氏系数

其中l＝1，2，3，4。为了充分利用更新前的背景信息，只更新其中巴氏系数较小的3个子块模型，从而得到新的整体背景模型，并计算新背景的权重系数更新

2.3 距离权重

颜色直方图描述的是不同色彩在整幅图像中所占的比例，而并不关心每种色彩所处的空间位置，即无法描述图像中的目标空间信息。离目标中心位置越近的点，对迭代贡献越大，离中心位置越远的点，对迭代贡献越小，因此根据目标窗口中的像数点离中心位置的距离不同，可以定义一个距离权重。在目标窗口中计算离中心位置最大距离Dmax，然后计算其中每个像数点离中心位置的距离d（i）（i＝1，…nh），得到像素点离中心位置的离差率

结合距离权重，得到改进的权重

2.4 改进算法伪代码

改进算法用伪代码描述如下：

步骤2 初始化迭代次数k＝0。

步骤4 计算候选目标坐标y1。

图2 抗背景干扰能力测试1

步骤6 设定背景模型更新阈值α2（默认值：0.5）计算当前帧的背景模型｝u＝1，…m利用式 （8）计算新旧整体背景模型的巴氏系数ρ。如果ρ≥α2，转到步骤2进去下一帧迭代。否则，更新背景模型及其权重系数｛vu｝u＝1，…m，利用颜色模型和新的背景模型的权重系数｛v′u｝u＝1，…m更新目标模型。转到步骤2进去下一帧迭代。

3 实验结果及分析

实验在Intel（R）Core（TM）2 Duo CPU E7400 ＠2.80GHz处理器及1.98GB内存的电脑上，用matlab实现。为了验证改进算法的有效性，对标准型的视频进行对比实验，并分别用基于整块背景信息更新的均值飘移跟踪（whole background update，WBU）算法［5］、基于颜色特征的加权更新背景信息的均值漂移跟踪 （weighted update background，WUB）算法和改进算法进行了详细对比。其中深色矩形框为背景区域边界，白色矩形框内为目标区域。

为了测试改进算法抗背景干扰能力，本实验选择行人行走测试序列，如图2所示，起初行人站在墙柱前，依次经过冰箱、第二个墙柱、屏幕显示器、第三个墙柱、空调。WBU 算法，忽略了更新前背景信息对目标定位的作用又没考虑目标的空间信息，导致跟踪效果不佳；WUB算法虽然考虑了更新前背景信息对目标定位的作用，但需要设置比较大的阈值，增加了计算时间并且该算法没有考虑目标的空间信息因此造成跟踪效果不好，甚至跟丢目标；改进算法既考虑了更新前背景信息的重要性又在比较低的阈值下利用了目标空间信息很好地跟踪到了目标。

为了进一步测试改进算法的抗背景干扰能力，选取“CCTV 风云足球”栏目中足球比赛视频作为测试序列。如图3所示，有多个穿白色球服的运动员在跟踪目标周围，目标周围背景信息变化不大，但有较高相似目标的干扰。WBU 算法和WUB算法均没有考虑目标空间信息，容易受到目标周围相似的运动员干扰；改进算法利用了目标空间信息，有较好的跟踪效果。通过上面两个实验，说明改进算法与上述两种算法相比，有更强的抗背景干扰能力。

图3 抗背景干扰能力测试2

迭代次数是均值飘移跟踪算法计算效率的一个重要指标，为了测试改进算法的计算效率，选取测试各种算法的平均迭代次数。分别选取上述两个视频和文献 ［5］中提到的Table Tennis Player视频作为测试序列。计算这3 个测试序列的平均迭代次数。如表1 所示，在背景变化不大的前两个测试序列中，WBU 算法和WUB算法的迭代能力接近，但均没有考虑目标空间信息，因此平均迭代次数都比改进算法大，在第三个测试序列，背景信息变化大，改进算法基于分块背景更新且考虑目标空间信息，故平均迭代次数最小。通过分析比较，说明改进算法具有更高的计算效率。

表1 3种算法的平均迭代次数

4 结束语

本文在研究基于颜色特征的目标跟踪的基础上，引入一种融合分块背景模型更新的加权跟踪算法。为降低背景对目标定位的影响，并选择性地分块更新背景信息，并引入距离权重以适应背景变化较大的环境中的跟踪。同基于全部背景更新算法和加权更新算法相比，能够在一些背景干扰条件下对目标进行准确、有效的跟踪。在未来的工作中，将针对在目标变形、目标快速运动情况下的跟踪进行研究，以期得到一种适用面更广、鲁棒性更强的跟踪算法。

［1］Bousetouane Fouad，Dib Lynda，Snoussi Hichem.Improved mean shift integrating texture and color features for robust real time object tracking［J］.Visual Computer，2013，29 （3）：155－170.

［2］Yinghong M，Zhi－Hong M，Wenyan J，et al.Magnetic hand tracking for human－computer interface ［J］.IEEE Trans Magn，2011，47 （5）：970－973.

［3］Souza DFL，Machado LS，Moraes RM.Integration of tracking systems for the development of virtual reality applications［J］.IEEE Lat Am Trans，2010，8 （6）：714－721.

［4］Ning J，Zhang L，Zhang D，et al.Robust mean－shift tracking with corrected background－weighted histogram ［J］.Computer Vision，IET，2012，6 （1）：62－69.

［5］LUO Fugui，XUAN Shibin，XU Junge，et al.A valid Mean Shift target tracking algorithm under a complex background［J］.Journal of Guangxi University for Nationalities，2011，17（1）：58－63 （in Chinese）.［罗富贵，宣士斌，徐俊格，等.复杂背景下一种有效的Mean Shift目标跟踪算法 ［J］.广西民族大学学报 （自然科学版），2011，17 （1）：58－63.］

［6］WANG Jianhua，WANG Chunping，LIANG Wei，et al.Background optimization and dynamic analysis of mean shift tracking［J］.Electronics Optics ＆ Control，2012，19 （2）：17－20 （in Chinese）.［王建华，王春平，梁伟，等.Mean Shift跟踪的背景优化及动态分析［J］.电光与控制，2012，19 （2）：17－20.］

［7］Wang Lingfeng，Pan Chunhong，Xiang Shiming.Mean－shift tracking algorithm with weight fusion strategy ［C］//International Conference on Image Processing，2011：473－476

［8］Vilaplana V，Varas D.Face tracking using a region based mean－shift algorithm with adaptive object and background models［J］.International Workshop on Image Analysis for Multimedia Interactive Services，2009：9－12.

［9］CHEN Aibin，CAI Zixing，DONG Deyi.A tracking method based on weighted object and background ［J］.Control and Decision，2010，25 （8）：1246－1250 （in Chinese）.［陈爱斌，蔡自兴，董德毅.一种基于目标和背景加权的目标跟踪方法［J］.控制与决策，2010，25 （8）：1246－1250.］

［10］DONG Wenhui，CHANG Faliang，LI Tianping.Adaptive fragments－based target tracking fusing color histogram and SIFT features ［J］.Journal of Electronics ＆ Information Technology，2013，4 （1）：770－776 （in Chinese）. ［董文会，常发亮，李天平.融合颜色直方图及SIFT 特征的自适应分块目标跟踪方法 ［J］电子与信息学报，2013，4 （1）：770－776.］