第三章 Mean Shift算法的理论基础以及在目标跟踪中的应用 视频中运动目标跟踪算法的研究
小不同的目标计算时的影响。?(x)为Delta函数，??b(xi)?u?是判断目标区域中像素的颜色值是否隶属于第u个bin，若是，值为1；不是，值为0。C为标准化系数，使
?qu?1mu?1，因此有：
C?1?x0?xik???hi?1?n2?
???（二）候选目标模型的描述
初始帧以后目标的可能区域就是候选区域，令其中心位置为y，也即为核函数的作用中心。区域像素用?xi?i?12...m的概率密度为：
?y?xipu(y)?Ch?k??hi?1??nh2...nh表示，类比目标模型，候选目标模型的特征值u=1、
????b(xi)?u? (3.16) ??其中Ch是标准化系数：
Ch?1?y?xik???hi?1?nh2?
???（三）相似度函数
为了表示目标模型与候选模型的相似程度，我们引入了相似度函数。Comaniciu等在文献[35]中论述Mean Shift算法时使用Bhattacharyya系数作为相似度函数，Bhattacharyya系数是一种散度性测量，其几何意义是两个向量夹角的cos值。
这里我们也选择Bhattacharyya系数做为相似度函数，定义为：
?(y)??(p(y),q)??pu(y)qu (3.17)
u?1????m??其范围是[0,1]。Mean Shift跟踪算法中?(y)的值越大，表明候选模型与目标模型越相似，当前帧中?(y)最大的候选区域即可认为是此时目标的位置。
（四）目标定位
?18
视频中运动目标跟踪算法的研究 第三章 Mean Shift算法的理论基础以及在目标跟踪中的应用
?在当前帧中寻找目标的位置，实际上是寻找?(y)最大的区域。首先在当前帧找到前一帧中目标中心的位置y0，作为当前帧的目标中心，从这一点开始寻求最优的匹配区域，令其中心为y。对式（3.17）在y0处进行泰勒展开，可把Bhattacharyya系数近似为：
?C1m??(p(y),q)??pu(y0)qu?h2u?12???y?xi?wk?i?hi?1?nh2?? (3.18) ??其中：
wi??u?1mqupu(y0)????b(xi)?u? (3.19)
很容易发现式（3.18）中只有第二项含有y。接下来我们来分析第二项，令
fh,K?y?xiCh??wik??hi?12?nh2?? (3.20) ??要使式（3.18）最大，就等同于要求式（3.20）最大。可以利用均值偏移过程搜索其最大位置，即通过计算式（3.20）的Mean Shift向量获取候选区域中心帧目标区域中心y的向量：
?y?xi2??xiwig????hi?1???ymh,G(y)?0 (3.21)nh?y?xi2??wig????i?1?h?nh到当前
其中：g(x)??k'(x)，mh,G(y)就是从y0到y的向量。
Mean Shift算法的定位过程是从前一帧的目标位置y0起，在其邻域内搜索目标位置y的过程，搜索方向是向?(y)变化最大的方向移动，这要比一般的盲搜算法节约时间，Mean Shift算法通过若干次迭代后找到目标的位置。由于函数?(y)是光滑的，所以利用?(y)的梯度信息可以完成目标的搜索定位。虽然这里使用的是目标的颜色信息，但是对于纹理、边缘或任何特征的组合，使用函数?(y)的最大化都是适用的。 3.2.4 算法实现及结果分析
以vc6.0为编程平台，在Inter Core(TM)2 Duo 3.00GH CPU的PC机验证经典Mean
19
????第三章 Mean Shift算法的理论基础以及在目标跟踪中的应用 视频中运动目标跟踪算法的研究
Shift跟踪算法的效果，程序中采用的是16?16?16的颜色直方图，使用的是RGB颜色空间，初始化是在目标存在的帧中通过手动完成。本文选择CAVLAR项目组[23]提供的标准视频“EnterExitCrossingPaths2front.mpg”进行测试，部分实验结果如图3-4所示。该视频采集于某商店前的走廊，视频图像的像素大小为320240，帧速率为25帧/秒，行人在运动过程中频繁出现光照变化、背景相似等情况。采用基于颜色直方图特征的Mean Shift跟踪算法进行跟踪，前70帧算法跟踪稳定，在72帧左右跟踪出现了明显的偏差，到了83帧时，跟踪目标完全丢失。这是因为目标在70帧以后受到光线明显变化和背景相似的影响时，颜色特征过于敏感，使得基于单一颜色特征的跟踪方法跟踪失败。
（a）第6帧 （b）第43帧
（c）第70帧 （d）第83帧
（e）第95帧 （f）第104帧
图3-4 经典Mean Shift跟踪算法的跟踪结果
20
视频中运动目标跟踪算法的研究 第三章 Mean Shift算法的理论基础以及在目标跟踪中的应用
从图3-4的跟踪实验结果我们可以发现，前70帧红色跟踪窗能一直很好的跟踪着运动的行人目标。特别是在（b）和（c）所示的跟踪结果中还可发现，当光照变化不明显时，Mean Shift算法仍可实现对目标的准确跟踪。另外，由于Mean Shift算法使用的是RGB颜色来构成特征空间，跟踪过程中不受目标形变的影响，从而实现了对类似行人的非刚体目标的较好跟踪，但是，现有的Mean Shift算法及其改进算法通常采用颜色特征，在实际应用环境中，由于场景复杂，很难保证跟踪算法的鲁棒性。当光照变化过于剧烈或跟踪目标和背景颜色相似时，容易丢失目标，导致跟踪失败。通过本实验可以说明Mean Shift跟踪算法在一般场景具有很好的鲁棒性、准确性等优点。总之，Mean Shift算法作为一种高效的模式匹配算法，已成功地应用在实时性较高的目标跟踪场合中。
3.3 基于梯度方向直方图特征的Mean Shift目标跟踪算法
上一节介绍的Mean Shift运动目标跟踪算法一般根据运动目标的颜色直方图特征来实现运动目标的跟踪。通常，除了可以利用运动目标的颜色直方图特征实现运动目标的跟踪外，还可以在跟踪过程中借助于运动目标的纹理、梯度方向直方图等特征。基于颜色或纹理特征的Mean Shift跟踪算法受光线变化的影响比较大，而梯度方向直方图特征对光线变化和局部区域的微小形变比较不敏感。梯度方向直方图特征在目标的匹配[24]和检测[25]中被成功的运用：Lowe[24]提出的尺度不变特征变换描述子（简称SIFT）利用梯度方向直方图来描述特征点，达到了非常好的匹配效果；Dalal[25]等人采用梯度方向直方图特征来描述行人目标并结合支持向量机（简称SVM）分类器，在人体检测方面达到了极好的性能。本节即将介绍的Mean Shift跟踪算法就是一种基于运动目标自身的梯度方向直方图特征来进行跟踪的方法。 3.3.1 梯度方向直方图特征
本文中不需要计算每个像素点的梯度方向直方图[26]，而是对整个目标区域计算一个梯度方向直方图并用来描述该目标区域的特征。梯度方向直方图的建立过程为：首先计算目标所在区域各个像素点的梯度幅值和方向，然后对目标区域每个点的梯度幅值进行加权，即离中心点越远则赋予越小的加权值，然后统计各个方向上的梯度幅值，
21
第三章 Mean Shift算法的理论基础以及在目标跟踪中的应用 视频中运动目标跟踪算法的研究
最终形成梯度方向直方图。如图3-5所示，其中最左边图中黑色箭头表示梯度幅值和方向，蓝色圆圈表示按离中心点的距离进行幅值加权，中间图表示经统计后在8个方向上梯度幅值，最右边图表示梯度方向直方图。此特征因为只保留方向特征，不保留强度特征，因此对于亮度、光照等变化具有一定的适应性。
图3-5 梯度方向直方图特征提取过程示意图
下面是梯度方向直方图特征提取的详细过程：假设目标区域的初始中心位置为0，首先利用Sobel算子得到目标区域任意像素点yi的梯度幅值m(yi)和梯度方向?(yi)，对于彩色图像仅保留梯度幅值最大的颜色通道。梯度幅值和方向计算公式为：
G(x,y)??I(x?1,y)?I(x?1,y）?2??I(x,y?1)?I(x,y?1）?2 (3.22)
?/?I(x?1,y)?I(x-1,y）?? (3.23) ??arctan??I(x,y?1)?I(x,y?1）在基于梯度方向直方图特征的Mean Shift跟踪算法中，首先将原始像素灰度值转换到特征空间，目标模型q和候选目标模型p在特征空间中用梯度方向直方图表示。为保留目标的局部形状信息，将目标区域进行有限分块，针对每块区域提取同一核函数加权的梯度方向直方图。每一块的大小可以不同，以获得不同尺寸的信息；块与块之间可以重叠，以获得不同位置的信息。
假设目标用W个矩形表示，第w个矩形块的中心位置为lw,尺度为hw，其梯度
ww?,qU]，参见式（3.15）计算出 方向直方图为qw?[q1w,?,quw?www?yi?lqu?Cq?k?hwi?1?nww?nw?ww?yi?l?Cq??k?i?1?hw??22???m(y)??b???y???u? (3.24)
ii???1???m?y?? (3.25)
i????22