核函数自适应的Mean Shift目标跟踪算法

赵 瑜，黄 山，2，王 凯

（1.四川大学 电气信息学院，四川 成都610065；2.四川大学 计算机学院，四川 成都610065）

0 引 言

运动目标跟踪［1］如今在各个领域都有广泛的应用。Mean Shift算法中带宽是由初始目标模板的尺寸决定并且整个跟踪过程中带宽不变，目标尺寸在逐渐增大或减小的过程中很容易导致在跟踪过程中的目标丢失。针对此问题，目前一般方法为先运用卡尔曼滤波［2］对下一帧进行预测，然后结合Mean Shift算法［3］进行迭代。文献 ［4］提出一种运动矢量与Mean Shift算法结合的方法。针对传统Mean Shift算法中核函数无法自适应跟新的问题，本文提出一种目标质心的分布散度与多级正方形匹配结合的核函数带宽的更新策略。实验结果表明了本文策略的有效性。

1 Mean Shift算法

1.1 初始目标模型的建立

本文采用目标感兴趣的最小外接矩形标识目标区域，该矩形窗口含有n个像素点，区域的尺寸就是核函数的带宽大小。假设初始目标区域，且用 ｛xi｝来表示，其中i＝1，2，...，n，其中心为x0。那么初始目标模型的特征值u概率密度如下所示

1.2 候选目标模型描述

同理，如果在当前帧中得到的运动目标的质心点的坐标为y0，那么在下一帧及以后的图像序列中，可能包含有运动目标的区域称之为候选模型区域，而且候选区域的质心点的坐标为y1，该候选区域中的像素用 ｛xi｝来表示，其中i＝1，2，…，nh

参照式 （1）

它也是归一化常数。

1.3 相似性度量函数

本文相似性度量函数采用Bhattacharyya系数，其定义为

1.4 目标定位

为使收敛到最大值，先以第N－1帧的质心坐标为第N帧中目标区域的质心点坐标，再以该点作为起始位置的领域内搜索运动目标。将式 （3）在模板的起始位置质心点处做泰勒展开如下所示

其中权值为

式 （4）中第一项泰勒项为常量与要搜索的新的质心y无关，因此要求得最大，只需第二项泰勒项最大即可，第二项泰勒项其实也是一个核函数密度估计。为了获得最大的，我们可以计算第二项泰勒项的Mean Shift向量，即候选区域质心向真实的目标区域的质心移动的向量

其中g（x）＝－k′（x），算法还得经过一系列迭代运算，最终找到最优的质心。

2 核函数带宽的改进

2.1 传统自适应带宽选择策略

第一种方法为增量试探法：先假设一个变换量α（0 ＜α＜1），然后对原带宽H 进行增加和减小α得H1和H2，分别计算带宽H、H1和H2对应的Bhattacharyya系数，选择其中使Bhattacharyya系数取得最大值的带宽值作为新的带宽值作为最佳跟踪窗口尺寸。但此方法在目标尺寸逐渐增大时效果不明显。原因是采用Bhattacharyya系数对两个模板进行相似性测量，Bhattacharyya系数经常会在小的跟踪窗口中达到局部的最大值。

另一种尺度变换方法：仿射变换法自适应带宽选择策略，其原理是如果运动目标运动过程投影近似一个平面运动过程或运动目标本身为刚性物体，那么相邻俩帧之间目标的尺度变化采用仿射变化来表示，之后采用一些特征匹配手段获得到运动目标运动过程中的仿射变换的参数，进而计算出带宽。但此方法需要分别针对尺度、角度等做多点相关的计算，计算过程繁琐，运算量太大，难以满足实时性的实际要求。

2.2 本文带宽跟新方法

分析了传统带宽跟新的方法，本文提出一种可以预先分析出运动目标尺度变化趋势的方法。

（1）根据与初始模型的相似度来确定点的权值，按权值来统计中心点位置和分布广度

式中：H、W 为初始目标模上标示运动目标区域的高和宽，h、w 为预估计当前帧图像中标示运动目标区域的高和宽；devorig为初始目标模板质心点的分布广度，dev为候选目标模型的质心点的分布广度。

（2）本文提出四级同心正方形法对目标尺寸变化趋势预测机制。

四级正放形区域划分与变长如图1所示。

图1 四级正放形区域划分与变长

四级同心正方形组以初始目标模型的质点为中心，建立4级同心的正方形组，本文约定从外向内，分别为第一层、第二层、第三层、第四层。四层正方形的边长比例设定为1∶2∶3∶4。

本文中最外层正方形的边长为初始模板的中标示运动目标区域的矩形框的宽W 和高H 间的最小值。即

在初始运动目标模板上的质心点和下一帧中确定质心的候选模板区域上的质心点也处，分别建立四级同心正方形，四级同心正方形的中的第四层各自包围了一个正方形区域Region＿A0 和Region＿B0。通过上述四级同心正方形组分割出4 个区域分别为Region＿A0、Region＿A1、Region＿A2、Region＿A3；同理Mean Shift算法收敛点（即候选模板）分割出4个区域分别为Region＿B0、Region＿B1、Region＿B2、Region＿B3。当运动目标尺寸变大，初始目标模板中的区域Region＿A1，对应的像素点应该大部分对应的扩散到候选目标区域Region＿B2；当运动目标尺寸变小，初始目标模板中的区域Region＿A1对应的像素点大部分收缩到候选目标区域的Region＿B0。用ρ10、ρ11、ρ12分别代表区域Region＿A1和区域Region＿B0、Region＿A1和区域Region＿B1、Region＿A1和区域Region＿B2建立的模型间的Bhattacharyya距离。类似我们可以取得到ρ21、ρ22、ρ23。

候选模板和初始模板间的正方形组匹配如图2所示。

图2 候选模板和初始模板间的正方形组匹配

根据上述目标尺度的变化和Region＿A1与 ｛Region＿Bi｝i＝0，1，2之间的变化关系，可以得出如下结论：当运动目标的尺度几乎无变化时，ρ10、ρ11、ρ12三者之中应该ρ11最大，同时对于ρ21、ρ22、ρ23三者之中ρ22最大；同理，运动目标的尺度缩小时，相应区域Region＿A1中表征运动目标的特征收缩到区域Region＿B0中，因此ρ10和ρ21取到最大值；运动目标尺度增大时，ρ12和ρ23应该取到最大值。因此通过回字形区域的直方图相似度间的关系可以用来确定运动目标的尺度变化的趋势。ρ10、ρ11、ρ12之间最大值和运动目标尺度变化关系如图3所示。

图3 之间最大值和运动目标尺度变化关系

2.3 带宽选择

（1）在当前帧中找到Mean Shift算法找到收敛点，即当前帧中的候选目标的质心点，以该质心点为中心，分别以初始目标模板的宽Wpre和高Hpre，采用增量试探法中建立矩形的方式分别建立3个矩形。高分别为H1，H，H2，宽分别为W1，W，W2

再建立以式 （9）和式 （10）中预测的当前帧中目标模板的宽w 和高h，采用增量试探法中建立矩形的方式分别建立3 个矩形。高分别为h1，h，h2，宽分别为w1，w，w2。本文中α取值为10%。

（2）距离决策机制：首先我们在选取初始模板的同时要记录其质心点的位置坐标 （xorigin，yorigin）。在当前帧中采用Mean Shift算法找到收敛点，即当前帧中的候选目标的质心点 （x1，y1）。在该点处，仿照式 （5）分别计算ρ10、ρ11、ρ12、ρ21、ρ22、ρ23。

1）若ρ12＞ρ10，ρ12＞ρ11且ρ23＞ρ21，ρ23＞ρ22；表明运动目标的尺度变大，对H、H2、h、h2进行对比，Bhattacharyya距离最大者就是尺度最优，即作为当前帧中运动目标的尺度也就是新的核函数的带宽。

2）若ρ11＞ρ10，ρ11＞ρ12且ρ22＞ρ21，ρ22＞ρ23；表明当前的目标尺度无较大变化，因此对H、H1、H2、h、h1、h2进行对比，Bhattacharyya距离最大者作为当前帧中运动目标的尺度也就是新的核函数的带宽。

3）若ρ10＞ρ11，ρ10＞ρ12且ρ21＞ρ22，ρ21＞ρ23；表明运动目标的尺度变小，对H、H1、h、h1这4个尺度对比，Bhattacharyya距离最大者作为当前帧中运动目标的尺度也就是新的核函数的带宽。

（3）减小计算量的改进方法：在采用Mean Shift算法进行目标跟踪时，需要在每一帧图像上进行迭代收敛计算，运算量太大导致跟踪系统时效性降低。本文在跟踪过程中由于权重涉及到开平方运算，在每帧Mean Shift算法迭代收敛时需要多次计算权重，因此希望找到一种有效的方法降低权重计算时的运算量。本文中采用＝代替，由式 （5）可得

3 实验与结果分析

本文以车辆和行人两类监控场景进行实验，来验证本文算法的效果。

实验一为对车辆采用Mean Shift算法进行跟踪的结果。本文分别对视频序列中的第851 帧、第1050 帧、第1075帧、第1750帧进行了展示，并且相对初始帧750帧时目标尺度呈逐渐增大的趋势。其中图4 （a）～ （d）的左边实验图为核函数的带宽固定时的Mean Shift算法的跟踪效果，居中实验图为核函数的带宽采用增量试探法时的Mean Shift算法的跟踪效果，右边实验图为核函数的带宽采用多级正方形法时Mean Shift算法的跟踪效果。

从上述结果中可以得出，本文算法所得效果最好。当目标靠近摄像头时，目标尺度变大，Mean Shift算法不能很好的标识运动目标。图4 （b）、（c）显示核函数带宽采用增量试探法时，Mean Shift算法可能在局部区域得到极大值，即局部收敛。而核函数带宽采用多级正方形法时，则不会出现突然收敛到局部极大值处，同时也避免了核函数带宽固定的弊端。

表1数据表明当目标尺度在逐渐增大时，该帧相对应的ρ12＞ρ10，ρ12＞ρ11，ρ23＞ρ21，ρ23＞ρ22是完全成立的。

实验二该实验是对行人目标进行跟踪的过程，实验过程目标远离摄像头。

3种带宽更改策略下的行人跟踪效果如图5所示。

表2数据表明当目标尺度在逐渐增大时，该帧相对应的ρ10＞ρ11，ρ10＞ρ12，ρ21＞ρ22，ρ21＞ρ23是完全成立的。

图4 3种带宽更改策略下的车辆跟踪效果

表1 车辆视频帧不同回字形区域相对应的ρ值

图5 3种带宽更改策略下的行人跟踪效果

表2 行人视频帧不同回字形区域相对应的ρ值

4 结束语

本文分析了传统Mean Shift算法中核函数带宽的固有缺陷，分析了现有方法的不足，提出了本文的算法。新算法首先采用目标质心点的分布散度和增量试探法计算出几个目标的可能变化尺度，然后采用多级正方形匹配的方法对目标的运动趋势进行预测，然后把Bhattacharyya距离最大者的尺度作为当前帧中核函数的带宽，减少了每帧中所需计算的像素的数量和背景噪声的影响，实现了对运动目标的有效跟踪。

［1］ZHANG Juan，MAO Xiaobo，CHEN Tiejun.Summary of moving target trac－king algorithm ［J］.Application Research of Computer，2009，26 （12）：4407－4410 （in Chinese）. ［张娟，毛晓波，陈铁军.运动目标跟踪算法研究综述 ［J］.计算机应用研究，2009，26 （12）：4407－4410.］

［2］YU Dan，WEI Wei，ZHANG Yuanhui.Dynamic target tracking with Kalman filter as predictor ［J］.Opto－Electronic Engineering，2009，36 （1）：52－56 （in Chinese）. ［虞旦，韦巍，张远辉.一种基于卡尔曼预测的动态目标跟踪算法研究［J］.光电工程，2009，36 （1）：52－56.］

［3］YUAN Shengzhi，XIE Xiaofang，LI Hongzhou.Bandwidthadaptive tracking algorithm based on Kalman－Mean Shift method ［J］.Laser and Infrared，2009，29 （5）：558－561 （in Chinese）. ［袁胜智，谢晓方，李洪周.一种基于Kalman－Mean Shift的自适应跟踪算法 ［J］.激光与红外，2009，29（5）：558－561.］

［4］TIAN Gang，HU Ruimin，WANG Zhongyuan.A Mean Shift target tracking algorithm based on motion vector analysis［J］.Journal of Image and Graphics，2010，15 （1）：85－90 （in Chinese）.［田纲，胡瑞敏，王中元.一种基于运动矢量分析的Mean Shift目标跟踪算法 ［J］.中国图象图形学报，2010，15（1）：85－90.］

［5］YAN Jia，WU Minyuan，CHEN Shuzhen，et al，Adaptive tracking window Mean Shift tracking algorithm ［J］.Optics and Precision Engineering，2009，17 （10）：2606－2611 （in Chinese）.［颜佳，吴敏渊，陈淑珍，等.跟踪窗口自适应的Mean Shift 跟踪 ［J］.光学精密工程，2009，17 （10）：2606－2611.］

［6］LIU Xin，LIU Hui，QIANG Zhenping，et al.Adaptive Background modeling based on mixture Gaussian model and frame subtraction ［J］.Journal of Ima－ge and Graphics，2008，13（4）：729－734 （in Chinese）. ［刘鑫，刘辉，强振平，等.混合高斯模型和帧间差分相融合的自适应背景模型 ［J］.中国图象图形学报，2008，13 （4）：729－734.］

［7］Chen Y T，Chen C S，Huang C R.Efficient hierarchical method for background subtraction ［J］.Pattern Recognition，2007，40（10）：2706－2715.

［8］LI Peihua，XIAO Lijuan.Mean Shift based object tracking with similarity and affine transformations ［J］.Journal of Image and Graphics，2011，16 （2）：258－266 （in Chinese）.［李培华，肖丽娟.基于Mean Shift的相似性变换和仿射变换目标跟踪算法 ［J］.中国图象图形学报，2011，16 （2）：258－266.］

［9］BAI Xiangfeng，LI Aihua，LI Xilai.Mean－Shift tracking algorithm based on adaptive bandwidth ［J］.Journal of Computer Applications，2011，31 （1）：254－257 （in Chinese）. ［白向峰，李艾华，李喜来.窗宽自适应Mean－Shift跟踪算法 ［J］.计算机应用，2011，31 （1）：254－257.］

［10］WANG Wenjiang，HUANG Shan，ZHANG Hongbin.Bandwidth－adaptive tracking algorithm based on Mean Shift and Kalman prediction ［J］.Computer Engineering＆Science，2013，35 （5）：87－92 （in Chinese）. ［王文江，黄山，张洪斌.一种基于Mean Shift和Kalman预测的带宽自适应跟踪算法 ［J］.计算机工程与科学，2013，35 （5）：87－92.］