《数字视频处理及应用》课件第4章

第4章视频运动目标检测和跟踪4.1运动目标检测4.2运动目标跟踪4.3本章小结

4.1运动目标检测

4.1.1帧差法

帧差法(Framedifferencemethod)是使用最多的一类算法。其基本原理是将前后相邻两帧或三帧图像对应的像素值相减，在环境亮度变化不大的情况下，如果对应像素值相差很小，可以认为此处无运动目标，如果图像区域某处的像素值变化很大，则认为这是由于图像中运动物体引起的，将这些区域标记下来，利用这些标记的像素区域，就可以得到运动目标在图像中的位置。由于目标大小、背景亮度的差别，对差分图像的分割方法也不尽相同；另外，当目标有阴影干扰时也要进行特殊处理。帧差法对于动态环境具有较强的自适应性，鲁棒性较好，能够适应各种动态环境，但一般不能完全提取出所有相关的特征像素点，这样在运动目标内部容易产生空洞现象。

此方法主要利用运动目标在视频图像中相邻图像帧中会产生较明显的差值图像而将前景目标与背景图像区分的，但对于抖动噪声等情况下的检测效果不理想。

设差分图像为Dt(x，y)，第t+1帧和第t帧图像在(x，y)的像素值

分别为It+1(x，y)和It(x，y)，二值化结果为Bt(x，y)，则帧差法的运算公式为

Dt(x，y)=|It+1(x，y)－It(x，y)|

(4-1)(4-2)

帧差法检测的运动目标如图4-1所示。帧差法是最简单最直接的方法，它能较快的检测出视频图像中发生变化的部分，能较好的适应环境变化较大的情况，对于目标运动时引起图像中发生明显变化的像素容易检测，但对于像素变化不明显的点很难检测。例如一个表面灰度比较一致的目标用帧差法检测时会产生目标表面的空洞，这里需要增加增补空洞的算法来提取完整的目标，而且前后两帧相减的结果得到的运动区域往往与目标的真实大小有很大的差别，会给目标识别或行为分析带来困难(如图4-1(c)所示)。帧差法计算量小，实现简单，具有良好的实时性，但无法很好的克服背景中噪声对目标的干扰。因此该方法大多用于背景比较简单，环境干扰比较小的情况。图4-1帧差法检测的运动目标4.1.2光流法

光流的方法是目前研究比较多的方法，光流反映了在一定时间间隔内由于运动所造成的图像变化，对图像的运动场进行估计，将相似的运动矢量合并成运动目标。

考虑一个视频序列，它的亮度变化用I(x，y，t)表示。如果在时刻t的一个成像点(x，y)在时刻t+d移动到点(x+dx，y+dy)，假定同一个物体点在不

同时刻的图像具有相同的亮度值，因此

I(x+dx，y+dy，t+dt)=I(x，y，t)

(4-3)

应用泰勒展开式，当dx，dy，dt很小时，

(4-4)联合公式(4-3)和(4-4)得到(4-5)公式(4-5)是用运动矢量(dx,dy)表示的，给两边同时除以dt得到(4-6)

1)基于匹配的光流计算方法

基于匹配的光流计算方法包括基于特征和基于区域的两种。基于特征的方法是不断地对目标主要特征进行定位和跟踪，对大目标的运动和亮度变化具有鲁棒性，存在的问题是光流通常很稀疏，而且特征提取和精确匹配十分困难；基于区域的方法先对类似的区域进行定位，然后通过相似区域的位移计算光流，这种方法在视频编码中得到了广泛的应用，但它计算的光流仍不稠密。

2)基于频域的光流计算方法

基于频域的方法利用速度可调整的滤波组输出频率或相位信息，虽然能获得很高精度的初始光流估计，但往往涉及复杂的计算，而且可靠性评价也十分困难。

3)基于梯度的光流计算方法

基于梯度的方法利用图像序列的时空微分计算2D速度场(光流)。由于计算简单和较好的实验结果，基于梯度的方法得到了广泛应用。虽然很多基于梯度的光流估计方法取得了较好的估值，但由于在计算光流时涉及到可调参数的人工选取，可靠性评价因子的选择困难，以及预处理对光流计算结果的影响，在应用光流对目标进行实时检测与自动跟踪时仍存在很多问题。总的来说，光流法的优点是能够检测独立运动的目标，不需要预先知道场景的任何信息，并且可用于摄像机运动的情况。光流计算是随后的一些高层处理所需要的先决条件，主要利用运动目标的矢量流特征来检测运动区域。当相机运动时，该方法仍然可以用来检测独立运动的目标。但大部分光流法计算复杂并且对噪声十分敏感，如果没有特殊的硬件支持，很难将光流法应用到实时的视频图像处理系统中。因此，如何将光流的方法应用于实时视频图像处理是一个值得研究的方向。影响光流场估计结果的主要参数有：平滑模板的大小和迭代次数。下面针对不同参数对最终估计的影响进行了实验，如图4-2所示，随着模板大小的增大，图像的边缘信息更加平滑；如图4-3所示，随着迭代次数的增加，图像的方向信息更加清晰。图4-2模板大小对光流估计的影响图4-3迭代次数对光流估计的影响4.1.3背景差法

背景差法将当前帧和不断更新的参考模型进行比较，与模型不一致的区域被标识为运动区域。背景差法是目前运动目标检测比较常用的方法，特别是在背景相对静止的场合。背景差法复杂度不高，但对动态场景中由光照等自然条件引起的变化比较敏感，因此如何将这些变化标记为背景是学者们一直研究的课题。该方法的基本思想是将图像分为背景和前景，对背景进行建模，然后把当前帧与背景模型进行逐像素的比较，那些与背景模型符合的像素被标记为背景像素，不符合的像素被标记为前景像素，同时更新背景模型。最简单的背景模型是时间平均图像，大多数研究人员目前都致力于开发不同的背景模型，以减少动态场景变化对运动分割的影响。

在视频监控系统中，静止的摄像头用来监视室内(外)场景中的运动。在摄像机拍摄到的图像中包括运动的目标及背景，消除图像中的背景只保留运动的目标是背景差法的目的，而它的关键是对背景进行建模，这是背景差法分割前景目标的基础。总结已有的自适应背景提取与更新方法，大致可分为两类：第一类是非模型法，即从过去的一组观测图像中按照一定的假设选择像素灰度构成当前的背景图像；第二类是模型法，即对图像的每一个像素点都分别建立对应的背景模型，以提取背景图像，并采用自适应方法对模型参数进行调整以实时更新背景图像。

1.非模型法

在非模型法中，最重要的是灰度选取的假设规则。最早提出的自适应平滑算法，认为在一段图像序列中，像素点稳定状态最长的灰度值是背景像素灰度值。但如果前景目标运动较慢或者在一段时间内暂时处于静止状态，稳定状态最长的灰度值往往是前景目标，此时就会产生错误结果。有学者对此作了改进，在算法中引入了光流场计算，就可以把由运动目标产生的稳定状态最长的灰度值去掉，但光流场的计算增加了算法的复杂性和运算量。另外，可以假设在训练阶段背景至少在50%的时间内可以被观测到，由此提出了中值法，即将图像序列中处于某个像素点中间的灰度值认为是该点的背景像素灰度值。但如果背景像素在少于50%的时间内被观测到，中值法就会得到错误结果。非模型法得到的是灰度图像形式的参考背景。系统每读入一帧新图像，就将该帧图像每个像素点的灰度值与参考背景图像对应像素点的灰度值相减。若差值大于某个背景灰度阈值T，则该像素点属于运动目标，反之则为背景像素。

由于是有选择的选取部分灰度值构成参考背景，因此非模型法可以在很大程度上避免混合现象。但非模型法的灰度选取规则都是基于一定的前提假设，如果实际情况和假设不符，就会得到错误的结果。而且背景判断的灰度阈值T是固定的，这导致算法适应气候环境和光照条件变化的能力下降。

2.模型法

在模型法中，通过对图像的每个像素点建立对应的像素模型，来完成背景的自适应提取与更新。模型法获得的参考背景不是简单的灰度图像，而是图像中各像素的参数模型。系统每读入一帧新的图像时，就将该图像每个像素的灰度值与该点像素模型的各个分布进行匹配，以判定该点是属于前景运动目标还是背景像素，并进行模型参数更新。与非模型方法相比，模型法能更准确的提取背景，其模型自适应更新机制能更好的适应背景环境的变化。

背景模型一般有两种：单模型和多模型。前者是用单个概率分布模型来描述背景像素点的颜色分布，后者则用多个概率分布模型来共同描述同一个背景像素点的颜色分布。常用的描述背景像素点颜色分布的概率模型是高斯正态分布。单个高斯分布的背景概率模型适用于单模型背景差法。单模型法可以在彩色空间用一个高斯模型对背景建模，对室内进行背景的变化检测。单模型的背景差法主要解决背景比较单一的情况，直方图会显示出单峰的特点。但当场景中有树叶晃动或者噪声等原因造成全程固定位置上的像素不断改变时，整个背景的直方图会显示出非单峰的特点，单个模型是无法准确模拟这些情况的。

当背景像素亮度的直方图在一段时间内是多峰分布时，可以利用多个分布来模拟一个像素的变化情况。于是出现了多模型方法，高斯混合背景模型就是为了解决这个问题提出的。该模型对视频图像中的每一点用多个高斯模型去近似，用新得到的观察值更新模型参数，使旧观察值的影响力逐渐变小。这些模型中包含有前景和背景，可以从多个高斯模型中根据一定的准则选择一个子集作为背景模型。将每个像素新的观察值与这个背景模型相比较，如果匹配则标记该像素为背景像素，否则标记为前景像素。模型中的每个参数的选择及更新方法是值得进一步研究的。对视频帧中的某个像素(x0，y0)定义其分布模型，设到t时刻，该像素取值的集合为{X1，…，Xt}={I(x0，y0，i)：1≤i≤t}，其中，I为视频帧。如果将该像素的所有历史值用K个高斯模型来近似，那么观察到的当前像素值的概率为

(4-7)其中，ωk,t为t时刻第k个高斯模型的权值，满足∑Kk=1ωk,t=1，它的大小体现了当前用该高斯模型表示像素值时的可靠程度；μk，t和Σk，t分别为t时刻第k个高斯模型的均值和协方差；K是高斯模型的个数，K的取值取决于系统的计算能力，通常取值在3到5之间；η是高斯概率密度函数，定义为(4-8)考虑到减少计算复杂度的原因，协方差矩阵定义为：Σk，t=σ2kI。通常权值ωk，t比较大，方差σk，t比较小的高斯模型被认为是匹配背景的模型。这是因为当一个新的物体出现在场景中时，它遮挡住了背景物体，此时在当前的所有高斯模型中不存在与它匹配的模型，那么这将导致产生一个新的模型或增加已知模型的方差，并且运动物体停止之前，它的方差总是大于背景像素的方差。为了在混合模型中找到代表背景的模型,首先将高斯模型按ω/σ值的降序进行排列。当一个高斯模型收集到更多与背景有关的信息，且其方差减小时，这个值会增大。在重新估计混合模型的各种参数之后，从匹配的模型到候选的背景分布得到了充分的排序，这样最有可能是背景的模型排在了最前面，最没有可能是背景的模型排在了最后面。然后选择前B个模型作为背景模型

其中，T是最小模型个数的度量。如果T选得比较小，背景模型会被认为是单峰的；如果T选得比较大，背景模型会被认为是多峰的。

算法运行时，每读入一帧样本，若存在分布Ci与样本xj相匹配，即满足xj∈[μi－3σi，μi+3σi]，则认为当前像素为背景点，否则就判为前景点。

在进行长时间的视频应用时，由于背景静止标准定义的广泛性，背景物体会发生一定的变化，因此，高斯混合模型需要对各分布模型进行更新。对于每个像素值，首先应该检查它是否匹配混合模型的某个模型，检测方法如下：

(4-9)

其中，τ的取值取决于场景的噪声，通常取2.5，即新像素值与现有模型均值之差小于该模型方差的2.5倍时，新像素与这个模型匹配，否则不匹配。检查了是否匹配现有模型后，会出现两种可能的情况：匹配和不匹配。如果新像素值与现有模型中的某个模型匹配，那么增加该模型的权值ωk,t,减小该模型的方差σk，t，并重新计算均值μk，t；如果新像素值与现有任何一个模型都不匹配，则产生一个新的模型，并将该新增的模型放在模型队列的最后。对混合模型的更新，可以使用下面的方法：

其中，

α是学习率，且0<α<1，它反映了背景更新的快慢，当学习率α较高时，背景变化会很快的融入到背景模型中去，当α较低时，背景的变化将比较缓慢的融入背景模型。Mk，t是模型匹配算子，它只取0和1两个值，当新像素值与模型匹配时它取1，否则取0，即(4-14)一般α的取值是固定的，对于场景没有明显变化、检测时间短的应用是可取的，选取合适的值可以提高检测效率。但对于长时间的检测及背景的变化难以预测时，固定的α会大大的影响检测的效率与结果。另外，Mk，t是匹配检测算子，它属于像素级的运算，对于复杂的背景在像素级上进行匹配检测是远远不够的，还应该考虑区域级甚至帧级的匹配。

图4-4给出了高斯混合模型检测运动目标的结果，图(b)中白色区域表示运动区域，可以看出，高斯混合模型能较好的检测到运动区域(人)。在检测结果中还包含了背景的运动部分，这些实际上是一种干扰，会影响后续的处理，因此出现了一些改进的高斯混合模型，在检测前景运动区域的同时，消除了背景的运动干扰。图4-4高斯混合模型检测运动目标

4.2运动目标跟踪

所谓目标跟踪，就是指对视频图像中的运动目标进行检测、提取、识别和跟踪，获取运动目标的运动参数(如目标质心、速度、加速度等)以及运动轨迹，从而进行进一步处理与分析，实现对运动目标的行为理解，以完成更高一级的任务。

运动目标跟踪融合了许多领域的先进技术，其中包括图像处理、模式识别、人工智能、自动控制等，它在军事视觉制导、机器人视觉导航、安全监测、公共场景监控、智能交通等许多方面都有广泛的应用。这也使得目标跟踪技术有着非常广泛的应用前景。国内外许多研究人员一直致力于该项技术的研究。在智能交通领域，通过对车辆目标的跟踪，智能交通信息分析系统可以使用架设在城市道路和高速公路上的固定摄像设备获取道路上的车辆信息，从而为终端交通管理部门提供必要的信息，自动记录并获取交通事件，分析交通事故并自动报警，记录违章车辆信息等。

在军事和工业领域，随着视频传感设备的不断普及，基于视觉的目标跟踪技术的应用变得越来越广泛。视频设备具有非接触性、直观性的特点，在军事上，一些人类无法到达或者存在极大危险的地方可以由携带视频传感器的机器人去探索，一些更加智能的机器人不但可以发现目标，还可以跟踪目标，认知周围环境，自主行进。目前自主制导、精确打击的智能武器是军事研究中的一个热点，而这类武器必须具有目标跟踪模块，目前这一模块越来越多地由视频传感器来提供必要的信息，并使用视频目标跟踪技术来实现精确打击。在日常生活中，运动目标跟踪技术的应用更为广泛。在银行、机场、广场等重要场所，智能的视频监控技术为安检部门、保安部门和军警部门提供了有效的防护手段，新技术的应用确保了国家和人民的安全。在医学界，医学影像处理中视频目标检测、跟踪技术使得非接触式地获得人类某些器官的运动特征成为一种可能，通过这种观测，可以通过不同时刻图像之间的运动估算来获取人体器官的运动变化信息，进而做出反映器官运动功能的定量描述，以便对病情进行检测，为治疗方案的确定提供重要的参考依据。在气象分析方面，通过对气象卫星传送的序列图像进行运动估计，可以较准确地估算出风速及风向，对未来的天气情况进行预报，并用于云层跟踪、台风轨迹跟踪和估计等。在运动目标检测之后，视频中的运动目标会被一帧一帧地跟踪。在处理过程中，运动跟踪算法与运动检测算法会进行大量的信息交互。跟踪通常是利用点、线或区域等特征在后续帧中进行运动目标的匹配，常用的数学工具有卡尔曼滤波器(KalmanFilter)、水平集方法(LevelSetMethod)、粒子滤波或CONDENSATION方法、动态贝叶斯网络、测地学(Geodesic)的方法等。运动跟踪的方法主要分为四类：基于区域的跟踪、基于主动轮廓的跟踪、基于特征的跟踪和基于模型的跟踪。

1.基于区域的跟踪

基于区域的跟踪(Region-basedTracking)算法的基本思想是：首先得到包含目标的模板(Template)，该模板通过分割获得或是预先人为设定，模板通常为略大于目标的矩形，也可为不规则形状；然后在序列图像中，运用相关算法跟踪目标，对灰度图像可以采用基于纹理和特征的相关准则，对彩色图像还可利用基于颜色的相关准则。最常用的相关准则是平方和准则(theSumofSquaredDifferences，SSD)，如下式：

C=∑(i－j)2

(4-15)

其中，i和j分别是图像和图像的像素。该算法还可以和多种预测算法结合使用，如线性预测、二次曲线预测等，以估计每幅图像中目标的位置。这种算法的优点在于当目标未被遮挡时，跟踪精度非常高，跟踪非常稳定。但其缺点首先是费时，当搜索区域较大时情况尤其严重；其次，算法要求目标变形不大，且不能有太大遮挡，否则相关精度下降会造成目标的丢失。对基于区域的跟踪方法关注较多的是如何处理模板变化时的情况，这种变化是由运动目标姿态变化引起的，如果能正确预测目标的姿态变化，则可实现稳定跟踪。

2.基于主动轮廓的跟踪

基于主动轮廓的跟踪(ActiveContour-basedTracking)方法是将目标描述为边缘轮廓来跟踪，在后续的帧中边缘轮廓会进行动态的更新，这是因为运动目标的边缘特征能提供与运动方式、物体形状无关的目标信息。Snake方法是基于边缘信息跟踪的一种常用的主动轮廓算法。Snake模型是一种有效的分割和跟踪工具，该模型可以用来检测和跟踪目标。用参数表示轮廓线：

v(s)=[x(s)，y(s)]

(4-16)

轮廓线的能量定义为

Esnake[v(s)]=Eint[v(s)]+Eimage[v(s)]+Econ[v(s)]

(4-17)其中，Eint表示主动轮廓线的内部能量，Eimage表示图像约束力的能量，Econ表示外部限制作用力产生的能量。曲线在内部力、外部力和约束力的作用下，主动地向感兴趣的目标轮廓附近移动，当曲线能量最小时，该曲线就是感兴趣目标轮廓。

由于该方法利用了目标轮廓的全局信息，获得的轮廓是一条封闭的曲线，不需要目标的任何先验知识，因此在边缘检测、图像分割、目标跟踪和三维重构等方面得到了广泛应用。传统的Snake模型存在着两个严重的缺点：首先，初始轮廓必须靠近目标的真实边缘，否则很可能会得到错误的结果；其次，传统的模型不能进入目标的深凹部分。针对这些缺点，出现了很多改进的方法，这些方法总体上是通过设计一个外力来实现的，如主动轮廓线的气球模型、距离势能模型、GVF-Snake(GradientVectorFlowtoSnake)模型等。这些模型都扩大了初始轮廓的捕获区域，使初始轮廓不必靠近目标的真实边缘，降低了对轮廓线初始化的敏感性。B-Snake方法将目标轮廓用B样条来表达，轮廓的表达更加有效、更加结构化。主动轮廓方法分为两类：参数化主动轮廓和测地线主动轮廓。参数化主动轮廓使用参数表示运动曲线；测地线主动轮廓的运动方程不包含与曲线几何结构无关的参数，并且在高维空间使用LevelSet方法表示曲线。同参数化主动轮廓模型相比，测地线主动轮廓模型能够在不附加任何外界控制条件的情况下自动处理曲线在运动过程中的拓扑结构变化，而参数化模型需要附加外界控制条件或先验知识。测地线主动轮廓模型更适合于同时跟踪多个非刚体运动目标。

3.基于特征的跟踪

基于特征的跟踪(Feature-basedTrakcing)方法先从视频帧中提取特征基元，然后将基元分类到高层特征，最后通过在视频帧中匹配高层特征来跟踪和识别目标。用于目标跟踪的个体特征有很多，在视频图像相邻的两帧中，由于采样时间间隔很小，可以认为这些个体特征在运动形式上具有平滑性。因此可以用直线、曲线、参照点等个体特征来跟踪运动目标。

基于特征的跟踪方法有显著的优点：①由于使用的符号模型运动方式简单，运动具有平滑性，因此跟踪目标的算法比较简单；②该方法已经假设符号运动是相互独立的运动，因此在运动分析时可以不区分运动目标是刚体还是非刚体，也不需要考虑它的几何形状；③跳跃过程中符号特征容易获得，能够匹配到每一个特征符号。基于特征的跟踪方法也存在缺点：①伴随着复杂运动的简单运动，使得刚体运动目标的特征提取变得困难，如圆柱旋转运动时，运动目标不可能是匀加速运动，更不可能是匀速运动；②运动初始化时的难点，刚体的一些特征会因为遮挡而无法识别，解决初始化的困难又会使跟踪算法变得非常复杂；③在改变符号参数和3D目标运动参数时，这些参数是非线性的，因此特征跟踪中恢复的3D运动参数对噪声很敏感；④该方法可以利用目标的运动信息等各种特征跟踪存在部分遮挡的目标，但不能有效处理全部遮挡、重叠及干扰等情况。

基于特征的跟踪方法又可细分为：基于全局特征(global-feature-based)的方法、基于局部特征(local-feature-based)的方法和基于独立图形(dependence-graph-based)的方法。

4.基于模型的跟踪

基于模型的跟踪(Model-basedTracking)方法需要利用先验知识，跟踪的过程就是将运动区域与目标模型匹配的过程。基于模型的非刚体跟踪方法与基于模型的刚体跟踪方法差别很大，而具有非刚体特征的代表性目标就是人体，具有刚体特性的代表性目标就是车辆。因此，基于模型的跟踪又分为基于模型的人体跟踪和基于模型的车辆跟踪。

基于模型的人体跟踪采用预测—匹配—更新的工作模式。首先，下一帧的人体模型状态由先验知识和历史跟踪记录进行预测；然后，将被预测的模型投影到二维图像平面上与图像数据进行匹配，这时候需要一个特殊的状态估计函数来度量投影模型和图像数据的相似性；最后，根据不同的搜索策略，找到匹配的人体状态，并更新模型。基于模型的车辆跟踪中车辆模型的建立要易于人体模型的建立。由于刚体形态不变的特性，车辆模型不用时刻进行更新，可以在数帧后更新，或匹配时相似性超过一定门限时进行更新。但基于模型的车辆跟踪需要考虑目标旋转时的匹配问题。

基于模型的跟踪与其他跟踪方法相比具有以下优点：①由于有先验知识的支持，该方法具有较好的稳健性，能够在有干扰和遮挡的情况下得到较好的结果；②用于人体跟踪时，可以将人体结构、人的运动约束及其他先验知识融合使用；③用于三维跟踪时，只要校正好相机，设置好二维图像坐标与三维真实世界坐标的对应关系，就可以获得目标的三维状态。当然基于模型的跟踪方法也有不足之处，如在跟踪前必须有相应目标的模型结构，不能进行未知目标或无目标模型的跟踪，并且该方法的计算量比较大。4.2.1均值漂移跟踪

均值漂移(MeanShift)算法作为一种基于梯度分析的非参数优化算法，最早由FukunagaHostetler于1975年提出，1995年Cheng将其引入到计算机视觉领域，引起了国内外学者的广泛关注。均值漂移目标跟踪算法作为匹配类跟踪算法的典型代表之一，以其无需参数、快速模式匹配的特性在目标跟踪领域迅速发展起来。基于均值漂移的目标跟踪算法最大的优点就是计算量很小，特别适合于对跟踪系统有实时性要求的场合；其次，作为一个无参数密度估计算法，很容易做成一个模块，从而与其他的算法集成。尽管该算法速度快，对某些目标跟踪问题效果较好，但是它也存在一定的缺陷：使用经典的均值漂移算法时，当背景和目标的灰度分布较相似时，算法效果欠佳；另外均值漂移算法要求相邻两幅图像间的目标区域具备部分的重合，以此来向目标中心位置漂移，当目标发生严重遮挡或目标运动速度较快时因无法满足上述要求，往往导致跟踪收敛于背景中，而不是目标本身。

1.均值漂移算法概述

在计算机视觉领域，目标跟踪过程必须用一定的手段对跟踪的方法进行优化，对目标进行建模。常用方法是将目标的表象信息映射到一个特征空间，其中的特征值就是特征空间的随机变量。假定特征值服从已知函数类型的概率密度函数，由目标区域内的数据估计密度函数的参数，通过估计的参数得到整个特征空间的概率密度分布。参数密度估计通过这个方法得到视觉处理中的某些参数，但要求特征空间服从一个已知的概率密度函数，而对于实际应用来说，一般当前帧图像的概率密度分布信息是无法根据先验知识得到的，这就要借助无参密度估计(Non-parametricDensityEstimation)来获得概率密度的梯度，从而为快速模式匹配创造条件。均值漂移迭代就是一种高效的无参密度估计方法。

设{x*i}，i=1，…，n是观测值。概率密度函数的核密度估计定义为

(4-18)其中，δ(·)是Delta函数；δ(b(x*i)－u)的作用是判断目标区域中像素点x*i在特征空间量化的对应值b(x*i)是否为u，若是则为1，否则为0；C为标准化常量系数，使得，因此(4-19)候选目标区域中观测值用{xi}，i=1，…，nh表示，则特征值u=1，…，m在候选目标模型中出现的概率可以表示为(4-20)其中，Ch为归一化因子，使得。则

(4-21)于是，可以得到一些常用的多变量核函数如下：

Gauss核函数：(4-22)Epanikov核函数：(4-23)

Uniform核函数：

(4-24)物体跟踪可以简化为寻找最优的γ，使得与最相似。与的相似性用Bhattacharrya系数来度量分布，即(4-25)式(4-25)在点泰勒展开，并把式(4-22)代入，整理可得(4-26)其中，

(4-27)要使最大化，即要使式(4-27)右边的第二项最大化。而该项表示当前帧中γ位置处使用k(x)计算的密度估计，只不过数据多加了加权值ωi。这样就可以使用均值漂移过程寻找领域内该密度估计的极大值。在这个过程中，核从当前位置移向新位置。(4-28)式中，g(x)=－k(x)。均值漂移跟踪算法以γ0为起点，向两个模型相比颜色变化最大的方向移动，因此优于一般的全局搜索算法。

只要核函数满足一定条件，均值漂移算法就总是收敛的。它可以从任意一点出发，沿着核密度的梯度上升方向，以自适应的步长进行搜索，最终收敛于核密度估计函数的局部极大值处。

2.基于概率分布图的均值漂移目标跟踪算法

基于概率分布图的均值漂移算法，其核心思想是对视频图像中的每一帧对应的概率分布图作均值漂移迭代运算，并将前一帧的结果(搜索窗口的中心和大小)作为下一帧均值漂移算法搜索窗口的初始值，重复这个过程，就可以实现对目标的跟踪。

1)概率分布图

概率分布图(ProbabilityDistributionMap，PDM)是利用直方图反向投影(HistogramBackProject)获取的。所谓直方图反向投影，是指将原始视频图像通过目标直方图转换到概率分布图的过程。直方图反向投影产生的概率分布图，即为直方图的反向投影图，该概率分布图中的每个像素值表示输入图像中对应像素属于目标直方图的概率。概率分布图生成的具体过程如下：

(1)首先计算目标图像的直方图：假定目标区域由n个像素点{x*i}i=1，…，n组成，将该区域灰度分布离散成m级，

b：R2→{1，…，m}表示像素点xi*的直方图索引为b(x*i)，则目标区域的直方图为

(4-29)其中，C为归一化常数，使得。

(2)给定一幅新的待处理图像f，{xi}i=1，…，s表示图中的s个像素点，则f基于分布q的概率分布图I可以表示为(4-30)概率分布图I实际反映了图像f中各种颜色成分的分布信息：I上某一点的值大，说明f上对应点的颜色在目标图像上的分布多，反之，I上某一点值小，说明f上对应点的颜色值在目标图像上的分布少。因此，图像f颜色的信息在这个投影图I上得到了充分的描述。

2)算法描述

建立被跟踪目标的直方图模型后，可将输入视频图像转化为概率分布图。通过在第一帧图像初始化一个矩形搜索窗，对以后的每一帧图像，基于概率分布图的均值漂移算法能够自动调节搜索窗的大小和位置，定位被跟踪目标的中心和大小，并且用当前帧定位的结果来预测下一帧图像中目标的中心和大小。算法的具体流程如下：

(1)初始化计算目标模型的直方图，同时将第一帧中目标区域作为初始化的搜索窗，设搜索窗的尺寸为s0，中心位置为P0；

(2)利用目标模型的直方图，反向投影到当前帧图像，得到当前帧的概率分布图I；

(3)均值漂移迭代过程：在概率分布图上，根据搜索窗的大小s0和P0中心位置，计算搜索窗的质心位置，具体步骤为：

①计算零阶矩:

(4-31)②分别计算x和y的一阶矩:(4-32)(4-33)其中，I(x，y)表示概率分布图I上点(x，y)处的像素值，x和y的变化范围为搜索窗的范围。

③计算搜索窗的质心位置:(4-34)④重新设置搜索窗的参数:(4-35)⑤重复①，②，③，④直到收敛(质心变化小于给定的阈值)或迭代次数小于某一阈值；

(4)此时的中心位置和区域大小就是感兴趣区域在当前帧中的位置和大小，返回(2)，重新获取新一帧图像，并利用当前所得的中心位置和区域大小在新的图像中进行搜索。

实际采用该算法对目标进行跟踪时，不必计算每帧图像所有像素点的概率分布，只需计算比当前搜索窗大一些的区域内的像素点的概率分布，这样可大大减少计算量。图4-5给出了基于概率分布图的均值漂移目标跟踪算法的流程图，其中，灰色方框内为迭代过程。图4-5基于概率分布图的均值漂移目标跟踪算法的流程图

3)跟踪效果

均值漂移在物体具有一定色彩和外形特征时跟踪效果非常好，图4-6是对该算法的效果进行测试。此例视频图像分辨率为320×240，帧率为25帧/秒。图4-6基于彩色直方图的均值漂移跟踪结果4.2.2粒子滤波跟踪

粒子滤波又称蒙特卡罗滤波，它是通过非参数化的蒙特卡罗模拟方法来实现递推贝叶斯滤波，一般用于复杂环境下的目标跟踪等。粒子滤波算法非常适用于非线性、非高斯动态系统的状态估计问题，算法容易编程实现。在视觉跟踪中，目标运动过程中往往会出现速度和方向的剧烈变化，同时，目标场景中的背景可能会发生频繁的变化，或者是目标运动过程中被障碍物遮挡，场景中出现多个目标等情形。在粒子滤波算法框架中，通过设计合理的分布，选择适当的目标特征信息，以上问题对跟踪的影响可以得到有效地解决。

1.蒙特卡罗方法

粒子滤波是以蒙特卡罗方法来实现递推贝叶斯滤波的，蒙特卡罗方法的基本原理及思路是：当所要求解的问题是某种事件出现的概率，或者是某个随机变量的期望值时，可以通过某种“试验”的方法，得到这种事件出现的概率，或者这个随机变量的平均值，并用它们作为问题的解。蒙特卡罗方法是以一个概率模型为基础，主要是正确描述和模拟这个概率过程，由于各种概率模型都可以看做是由各种各样的概率分布构成的，因此产生已知概率分布的随机变量(随机向量)，就成为实现蒙特卡罗方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因。按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解，这就是蒙特卡罗方法的基本思想。蒙特卡罗模拟的基本思想是用随机样本近似积分。假设从后验概率密度p(x0：k|z1：k)采样得到N个样本(粒子)，则后验密度可以通过正式近似表达：

(4-36)其中，xi0：k表示从后验分布采样得到的粒子；δ表示DiracDelta函数，基于这种近似表达，函数g(x0：k)的条件期望(4-37)可近似为(4-38)根据大树定律，当粒子数N趋于无穷时，近似期望收敛于真实期望，即(4-39)

2.粒子滤波算法

粒子滤波算法的基本思想是蒙特卡罗模拟，其中