图像处理算法5_目标跟踪及遮挡处理算法资料

1、基于粒子滤波算法的目标跟踪及遮挡处理算法1.1引言对运动目标物的跟踪也是视觉监控系统中的基础算法之一。目标跟踪的任务是通过对图像序列的处理，准确估计出感兴趣目标物在每个时刻的运动参数，包括位置、大小、速度、加速度以及运动轨迹等，为行为理解等更高层的任务打下基础。本章首先概述目标跟踪算法的基本步骤和难点，并对现有算法作分类简介；然后对实现鲁棒跟踪所必需的工具在线贝叶斯估计算法作详细介绍；在此基础上详细论述本文使用的跟踪方法，该方法将已有的多种先进算法有机结合，使计算量显著降低，鲁棒性增强；最后对提出的算法进行总结和分析。1.2 目标跟踪算法概述目标跟踪算法主要由两个部分组成：（1）目标物表示；（

2、2）运动状态估计。下面对它们分别介绍。1.2.1目标物表示目标物表示的核心在于特征的选择和提取，即用什么特征来描述和表示感兴趣目标物。一个好的目标物表示方法应该能够将被跟踪的目标物和背景中的物体以及其它物体区别开来，这正是目标物表示的难点所在。运动目标物所在的环境通常是很杂乱的，其中存在许多与目标物有相似特征的物体。例如：房间内的窗帘、家具等往往与人的皮肤颜色相近；当监控视野中存在多个行人的时候，跟踪器容易将目标行人与其他行人相混淆。下面介绍几种常用的特征。1.2.1.1颜色特征颜色是人类辨识物体的重要特征，也是视觉跟踪中最常用的特征之一。颜色特征通常是在一块区域中提取出来的，因此它具有对目标

3、平面旋转、非刚性形变、远离或靠近镜头的尺度变化以及部分遮挡等情形较为鲁棒的优点。另外，由于图像直接由一个个像素的颜色值所表示，因此颜色特征还具有容易提取、计算简单的优点。最常用的颜色特征是颜色直方图。Comaniciu等人提出了基于颜色直方图的跟踪算法12。在他们的方法中，颜色直方图受到了核函数的空间加权。这样区域内中心附近的像素对颜色直方图有更大的贡献，使跟踪更加精确，因为区域边缘的像素可能来自背景或其它物体，其可信度较低。具体的操作流程主要包括：（1）将目标物初始时刻的颜色直方图保存起来作为模型，并在后面的跟踪过程中作增量平均式更新。（2）以上一帧中估计出的目标物所在位置为初始候选区域，计

4、算颜色直方图，并计算它与模型直方图的Bhattacharrya系数，Bhattacharrya系数越大，说明二者的相似度越高。（3）使用均值位移（Mean Shift）算法迭代式地移动候选区域的位置，最终在Bhattacharrya系数关于位置坐标的一个局部最大值处收敛，该位置即当前帧的估计值。该方法计算简单，跟踪效果较好，最大的优点是可以跟踪非刚性目标物。但是该方法求得的是一个局部最优解，在一些场景中不够精确。尤其是当目标物的运动速率较快以至它在前后两帧中的位置之差大于目标物本身的尺寸时，以及目标物被严重遮挡时，该方法将会失效。为了克服Comaniciu方法的缺点，K.Nummiaro等人将

5、颜色直方图融入粒子滤波器（Particel Filter）的框架中3，P. Prez等人也提出了类似的方法4。上面提到的均值位移和粒子滤波器两种算法将分别在本文的后续章节中中介绍。颜色特征除了用直方图来表达之外，还可以用连续密度函数来表达。McKenna等人提出用混合高斯模型来描述目标物的颜色分布5。该模型可由期望最大化（Expectation-Maximization）算法进行初始化，在跟踪过程中用在线期望最大化方法进行更新。由于混合高斯模型的组件数目有限且固定，有时不能精确地描述目标物的颜色分布。为此，Bohyung6提出序列核密度近似（Sequential Kernel Density

6、Approximation， SKDA）算法。该方法充分利用了高斯函数的平滑性以及良好的导数性质，用数目可灵活变动的高斯函数的加权和来近似颜色的密度函数。其中每个高斯函数的均值对应密度函数的一个局部峰值，该峰值由均值位移算法求得。每个高斯函数的协方差矩阵则通过对峰值处的曲率拟合来估计。当不同高斯函数的均值可由均值位移算法收敛到同一个峰值处时，这些高斯函数可以由一个高斯函数来近似，因此当观测样本越来越多时，高斯函数的数目不会无限地增多。序列核密度近似算法对颜色分布的描述非常精确，但计算量大是它的一个缺点。1.2.1.2 轮廓特征轮廓特征是对物体形状的描述，和颜色特征一样，也是人眼辨识物体的重要依

7、据。轮廓特征具有不受光照变化影响、可表示外形复杂的物体等优点。Isard将轮廓特征与概率方法结合起来，实现了对任意形状的目标物的跟踪，也由此奠定了用概率方法进行视觉跟踪的基础框架7-9。他们描述物体轮廓的工具是B样条曲线。B样条曲线可以表示成一系列控制点坐标对相应B样条基函数的加权和，因此可由这些控制点的坐标值构成的向量控制点向量来表示。控制点向量构成的空间称为样条空间。对于具有复杂几何形状的目标，样条空间的维数很高，如果对其变化不加任何限制，则难以表达跟踪目标。为此，首先建立好目标物的控制点向量模板，再将目标物的运动限定为平移、尺度变化、平面旋转等几种有限的形式，就可获得样条空间的一个子空间

8、，称为形状空间。形状空间的维数比样条空间低得多，因此可将其中的每一个向量线性映射为一个低维的形状向量来表示，这样可使轮廓跟踪的性能更稳定，计算量也大大减小。1.2.1.3其它特征颜色和轮廓可以说是两种最常用的特征。除此之外，还存在其它的一些特征，例如光流10和局部二元图11。光流是一种有效的特征，其缺点是计算量大，难以满足实时性要求。局部二元图是对图像纹理的一种有效表示，相比于颜色特征，具有光照不变性的优点。1.2.2 运动状态估计目标跟踪过程中需要处理一些复杂的情形，例如：目标物经历较大的外形变化，目标物被其他物体暂时遮挡，跟踪丢失后需要重新恢复等，因此要求运动状态估计方法有较好的鲁棒性。此

9、外，由于监控系统的实时性要求，对计算量有严格的限制，这也对运动状态估计算法提出了挑战。确定性跟踪方法本质上是一个优化问题。这种方法的思想是：首先通过手动或目标检测获得目标模板，建立代价函数（Cost Function）来表达目标候选位置和目标模板的相似程度，然后利用最优化方法找到代价函数的最大值，认为最大值对应的位置就是目标在图像序列中的位置。基于均值位移（Mean Shift）算法的跟踪方法是确定性跟踪方法的典型代表12。均值位移跟踪方法简单有效，在一些跟踪场景取得了较满意的跟踪效果。但其缺点在于没有利用图像数据以外的先验信息，不能跟踪快速运动的物体，不能很好地处理遮挡问题。概率跟踪方法将目

10、标跟踪转换为在贝叶斯滤波框架下推理目标状态（如位置、速度）后验概率密度的过程。首先选择状态变量，通过状态转移方程进行预测，然后利用最新观测值对预测作出修正。当过程噪声和观测噪声都是高斯分布且状态转移方程和观测方程是线性的，常规的卡尔曼滤波（Kalman Filter）能给出最优解12；当状态方程和观测方程是非线性函数时，扩展卡尔曼滤波（Extended Kalman Filter）或者无迹卡尔曼滤波（Unscented Kalman Filter）13,14能近似求解后验概率。如果状态空间是由有限的离散值组成，隐马尔科夫模型（HMM）15可以实现跟踪。但是在实际场景中，状态方程和观测方程往往都

11、是非线性的，同时噪声也是非高斯的，而且状态分布是多模态的，在这种情况下，常常利用近似方法求解后验概率密度，一个很好的方法就是粒子滤波器。粒子滤波器不需要线性、高斯、单模态假设，特别适用于图像跟踪领域，已经成为图像跟踪的研究热点。本文所提出的视觉跟踪方法的主体框架也是粒子滤波器，本文将对包括粒子滤波器在内的贝叶斯估计理论在下节中作详细的介绍。1.2.2.1 贝叶斯递归状态估计在视频跟踪方法中，跟踪问题可以看成是在线的贝叶斯估计问题，其基础为运动模型和观测模型，可用以下两个方程来描述： （4-1） （4-2）式中，和可分别为非线性函数，和分别为过程噪声和观测噪声，且相互独立。和分别为状态向量和过程

12、噪声向量的维数，和分别为观测向量和观测噪声向量的维数。从贝叶斯估计角度来看，跟踪问题就是从所有的历史观测数据中推理出时刻状态的值，即：估计。状态变量可以包含目标物在图像中的位置、大小及运动速度等分量。假设状态变量初始概率密度函数作为先验知识已知，那么可以通过下面两式递推得到： （4-3） （4-4）式中，由目标的运动状态方程，即式（4-4）定义，由目标的观测方程，即式（4-2）定义，为归一化常数，具有如下形式： （4-5）以上过程可以用图4-1中的概率图模型来描述，图中和分别为第时刻的目标状态和观测。图01 贝叶斯跟踪图模型 在得到之后，可以计算出最小均方意义下的最优估计和估计方差： （4-6

13、）（4-7）式（4-3）和式（4-4）构成了最优贝叶斯估计的基础，分别称之为预测和更新方程。由于在计算此二式时，存在高维积分运算，因此实际中很难解出状态最佳估计的解析形式，利用（4-3）和式（4-4）得到的状态解仅仅是概念上的，在实际中，必须利用一些数学工具来近似求解。1.2.2.2 重要性采样重要性采样是一种普适的蒙特卡洛积分方法。但是，上述最简单的表示形式还不能在迭代估计中使用，因为在估计后验密度函数之前，必需保存好所有的历史数据；又因为在每个新的时刻，获得一个新的观测数据后，必须对状态的历史轨迹重新仿真以计算新的重要性权值，这样计算量将随时间的推移而无限增长。从前一小节可知，后验概率密度

14、可以由来自该密度的独立同分布粒子近似，粒子数越多，近似的后验密度就越逼近真实后验密度。然而遗憾的是，往往不可能直接从后验密度采样粒子，需要引入一个已知的、易于采样的概率密度并从中采样粒子，这个概率密度称为重要性采样分布，或建议分布。关于后验密度的条件期望可表示为： （4-8）其中被称为重要性权重： （4-9）接下来，如果能够根据采样产生个独立同分布的粒子，那么。关于后验密度的条件期望的蒙特卡洛近似为：（4-10）其中为归一化重要性权重： （4-11）为方便起见，以后直接用表示归一化重要性权重。对于个有限数目的粒子，式（4-10）是有偏估计（两个估计值之比），但仍然是渐进收敛的16，即 （4-1

15、2）显然，式（4-10）可看作是直接由蒙特卡洛方法得到的，即后验概率密度可近似为： （4-13）重要性采样是一种普适的蒙特卡洛积分方法。但是，上述最简单的表示形式还不能在迭代估计中使用，因为在估计后验密度函数之前，必需保存好所有的历史数据；又因为在每个新的时刻，获得一个新的观测数据后，必须对状态的历史轨迹重新仿真以计算新的重要性权值，这样计算量将随时间的推移而无限增长。1.2.2.3 序贯重要性采样 如果修改采样方法，使得无需改变上一时刻已经仿真好的状态轨迹样本，就能计算后验密度函数的估计，那么就意味着时刻的重要性函数的边缘分布即是时刻的重要性函数，即 （4-14）进一步可得 （4-15）容易

16、看出这样的重要性函数可以迭代计算重要性权重： （4-16）进一步，如果，那么重要性函数只依赖于和。这个假设非常有用，因为通常情况下，只需估计后验分布的边缘分布。今后，本文将这种情况视为默认情况。那么，只需保存样本而将轨迹样本和历史观测数据舍弃，则重要性权重递推公式变为 （4-17）且后验密度可估计为 （4-18）因此只要选择合适的建议分布，就可以根据式（4-17）迭代计算粒子重要性权重，这就是序贯重要性采样算法。序贯重要性采样算法中有一个重要的特殊情况是直接用转移概率密度函数作为重要性函数： （4-19）将式（4-19）代入式（4-17），得到 （4-20）这是最常用的一种重要性函数，因为这种

17、情况下的计算最容易。1.2.2.4 重采样序贯重要性算法有一个致命的缺陷，经过若干次递推后，除了少数粒子外，其余粒子的权值可忽略不计，从而使得大量计算浪费在几乎不起任何作用的粒子更新上，甚至最后只剩下一个权值很大（几乎接近1）的有效粒子，而其他粒子的权值几乎为零。这就是粒子退化问题，当退化现象发生时，粒子集不能有效地表达后验概率密度。为了避免这个问题，可以采用重采样（Re-Sampling）策略。重采样的核心思想是繁殖加权大的粒子，淘汰加权小的粒子。重采样算法从已有的粒子集中采样次，产生一个新的粒子集，每次采样服从离散分布 （4-21）因此重采样的输出实际上是多项分布的一个样本，当然新粒子集中

18、极可能存在相同的粒子。经过重采样后，每个粒子的权重相等，即。重采样的一种常用的具体实现算法如表4-1所示。表4-1 粒子重采样算法1）初始化累积概率：（2）依次计算从2到的累积概率： FOR 计算累积概率： END FOR（3）初始化待选粒子在旧粒子集中的序号（4）由均匀分布生成一个随机样本：（5）重采样： FOR 按累积概率递增： WHILE END WHILE 分配粒子： 分配权重： END FOR1.2.2.5粒子滤波算法前面各部分讨论了序贯重要性采样算法以及粒子重采样算法，本节给出粒子滤波的完整算法，如表4-2所示。表4-2 粒子滤波算法（1）初始化： ，根据先验分布，采样初始粒子集。

19、（2）FOR a) 重要性采样：从建议分布采样粒子集。 b) 重要性加权：根据式（4-17）计算重要性权重，且对它们归一化。 c) 最小均方误差估计： d) 重采样：按照表4-1所示重采样算法得到新粒子集 图4-2展示了粒子滤波的一个实例。首先，在时刻，滤波器已经由重要性采样获得了粒子集，它是先验分布的近似表示。接着计算粒子集的重要性加权，获得，它是后验分布的近似表示。然后通过重采样获得，它也是后验分布的近似表示。此时，时刻的流程已全部走完。来到时刻，再通过重要性采样获得，接下来的流程就和图中时刻开始时一样了。图4-2 粒子滤波示意图粒子滤波器是一种强大的目标跟踪方法，它最大的优点就在于不受具

20、体分布的限制，适用于任何非线性、非高斯条件下的目标跟踪。在很多情况下视觉跟踪的观测模型都是非线性的，有时甚至无法显式地写出观测方程，在这种情况下运动状态估计的问题更像是一个搜索问题，但即使在这种情况下粒子滤波器也能派上用场。Isard等人提出的条件概率密度传递9（Conditional Density Propagation， CONDENSATION）就是标准粒子滤波器的一个变体，随后该方法在视觉跟踪领域得到了广泛的应用和研究。尽管如此，粒子滤波器也存在不少缺点，除了前面提到的粒子退化问题，另一个比较明显的缺点是维度问题。由于粒子滤波器的核心思想在于利用一个随机样本及其相应的重要性权重来近似

21、密度函数，因此如果粒子的数量不够多，就不能精确地近似密度函数。随着状态变量维度的增加，所需的粒子数量呈指数增长趋势。粒子数越大，计算量也越大，这就给实时跟踪增加了难度。事实上，序贯蒙特卡洛方法正是随着计算和存储设备性能的提高才得到了足够的重视，进而得到长足的发展和越来越广泛的应用。1.3使用多特征融合的粒子滤波器的视觉跟踪通过前几节的分析，可知视觉跟踪方法主要由目标物表示和运动状态估计方法两部分组成。本文分别对这两部分提出改进的算法。目标物表示的关键在于特征的选择和提取，各种特征都存在固有的优缺点，为了实现鲁棒的目标跟踪，本文将颜色和形状特征结合起来共同表示运动目标物。在运动状态估计方面，粒子

22、滤波器凭借其优良的性能和通用性已成为视觉跟踪领域的研究热点，然而其计算量大的缺点对实时跟踪提出了很大的挑战。为了克服这一困难，本文将粒子滤波器与均值位移算法相结合，并根据多特征融合的方法对标准均值位移算法作了修改。在每次求取重要性权重之前，均值位移操作被独立地施加在每个粒子上面，使得粒子更加靠近后验密度函数的局部最大值处，因而能够更加有效地近似后验密度函数，相比于传统方法，所需粒子数显著下降，大大减轻了计算负担。另外，由于所用的均值位移操作依赖于颜色特征，而颜色特征在跟踪过程中由于目标物外形的变化很可能失效，因此本文根据颜色特征的可靠度来限制均值位移算法的迭代次数，防止粒子受到误导，而且进一步

23、减少了计算量，还有助于保持粒子多样性。下面对本文所使用的视觉跟踪方法作详细论述。1.3.1运动模型本文使用的跟踪方法主要用于跟踪人的头部，因此将目标物建模为一个直立的椭圆。状态变量表示为 （4-22）其中表示目标物的中心位置，和分别表示当前时刻椭圆的横半轴和纵半轴相对于固定半轴长和的比值，和分别为初始跟踪时刻的半轴长度。用随机游走（Random Walk）模型对目标物的运动状态建模： （4-23）其中是一个多维零均值高斯噪声，假设其各分量相互独立，协方差矩阵为 （4-24）本文使用的运动模型是零阶模型，没有引入目标物的速度以及横竖半轴的变化速度。这主要是基于两个方面的考虑：一是为了使计算量尽量

24、小，避免粒子滤波器使用大量粒子在高维空间近似密度函数；二是为了使粒子滤波器能够捕捉到不规则的运动，因而使用了随机游走模型。1.3.2观测模型本节阐述本文所使用的具体观测模型颜色特征和边缘特征的融合模型。其中颜色特征和边缘特征分别在4.3.2.1节和4.3.2.2节中介绍，然后在4.3.3中介绍二者的融合算法。1.3.2.1颜色观测模型最常用的颜色特征是颜色直方图，因为它具有计算简单、不受物体尺度变化影响、可用于描述非刚性物体以及对部分遮挡情形具有鲁棒性等优点。本文使用的颜色特征是受到核函数空间加权的颜色直方图1,3，首先为目标物建立一个颜色直方图模型，并用归一化直方图来表示它，其中是直方图的格

25、子数目。令表示目标物每个像素相对于它的中心的位置向量，且该向量的横坐标和纵坐标分别受到当前时刻的横半轴和纵半轴的归一化。模型直方图按下式进行计算： （4-25）其中表示处的颜色向量在直方图里的格子序号，是核函数的轮廓函数，是归一化常数： （4-26） 在跟踪过程中，需要将候选区域的颜色直方图与模型直方图进行比较。候选区域的颜色直方图的计算方法与模型直方图相似。用表示中心位于处的候选区域内的颜色直方图，注意此处的横纵坐标也分别受到和的归一化，则的计算方法为 （4-27）目标物的模型直方图与候选区域的直方图之间的相似度由二者的Bhattacharyya系数给出： （4-28）再定义二者的距离为 （

26、4-29）用Bhattacharyya系数定义的距离有诸多好处。首先它满足三角不等式，且具有非常直观的几何意义：它是两个维单位向量与的夹角的余弦值，这里和为概率分布的本质也由单位向量体现出来了。另一方面，式(4-28)可以解释为向量与之间的相关函数。假设候选区域的直方图与模型直方图之间的Bhattacharyya距离呈零均值高斯分布（当候选区域即是目标物时距离为0），则可定义颜色似然函数为： （4-30）其中为高斯分布的方差。1.3.2.2形状观测模型 在跟踪的过程中，目标物的颜色特征可能发生突然的变化，比如人突然转身的情形，此时候选区域的颜色直方图将与模型直方图极不匹配，但目标物的形状却通常

27、不会发生这么剧烈的变化。而且形状特征不受光照变化的影响。因此形状观测模型可以弥补颜色模型的一些不足。下面介绍本文使用的形状观测模型。假设被跟踪的物体呈椭圆形，那么其形状信息可由边缘处的亮度梯度来表示，定义形状特征为椭圆边缘的梯度平均值17： （4-31）其中是候选区域的中心坐标向量，是椭圆边缘上处的梯度，是椭圆边缘上的像素总个数。通常情况下椭圆不能精确地描述目标物的轮廓。Xu等人提出了一种改进的基于梯度的建模方法18。在椭圆边缘处，沿着一条过该点且垂直于椭圆切线的线段搜索梯度最大的点，并用该点处的梯度替换式(4-31)中椭圆边缘上的梯度，如下式所示： （4-32）其中表示垂直于椭圆切线，且中心

28、在处的线段。与颜色观测模型相似，定义形状似然函数为 （4-33）其中为方差。1.3.3 特征融合算法将来自多个模态、特征或传感器的信息融合在一起是视觉系统中的经常会遇到的问题，融合策略用自适应和自组织的方式将这些不同的信息融合到同一个结果中，而且根据单个信息与最终结果的一致程度对不同信息赋以不同的权重，因此那些与最近的结果不相符的信息将被抑制，反之，与结果非常一致的信息将得到较大的权重。Shen19等人将融合策略应用于基于粒子滤波器的多特征融合，在一些场景中起到了很好的效果。前面的章节中已经分析了颜色特征和形状特征各自的优缺点，如果将二者结合，可以实现优势互补，使目标跟踪更具鲁棒性。颜色特征和

29、形状特征的融合体现为最终的似然函数是二者各自似然函数的加权乘积： (4-34)其中，和被分别定义为颜色特征和形状特征的可靠度，它们满足和两个条件。式(4-34)的意义非常明显，当其中一个特征的可靠度为0时，该特征对融合后的似然函数没有任何贡献。下面介绍观测模型如何融入到粒子滤波的框架中。假设在设在时刻，已经得到重采样后的粒子集，那么接下来在时刻进行重要性采样。本文采用最方便也是最常用的方法进行采样，即令重要性函数为一步转移概率密度函数： (4-35)其中很容易由式(4-23)得到，它是以为均值，以为协方差矩阵的高斯函数： (4-36)在具体操作时，首先生成个零均值高斯噪声样本：，再将噪声样本与

30、时刻的粒子相加： (4-37)这样就获得了新的粒子集，然后按式(4-20)计算重要性加权，由于粒子集中每个粒子的权重相等，因此式(4-20)进一步化为 (4-38)注意上式中，对不同的粒子，其观测值是不同的。这就是视觉跟踪里使用的CONDENSATION算法与标准粒子滤波器的不同点所在。因为显式的观测方程根本无法写出，所以只能根据不同的假设计算与之对应的似然值。 计算出粒子重要性权重后，就可以估计时刻的运动状态： (4-39)再定义由单个特征估计出的运动状态为： (4-40) (4-41)然后用欧氏距离来度量单个特征的估计值与多特征融合的估计值之间的差别： (4-42)再为每个特征计算系数，它

31、反映了单个特征的估计值与多特征融合后的估计值的一致程度： (4-43)其中为常数。每个特征的可靠度由一个一阶差分方程更新： (4-44)其中为常数，它控制着可靠度变化的快慢，表示相邻两帧之间的时间间隔。1.3.4 改进的粒子滤波由前面章节的分析可知，粒子滤波器不受非线性、非高斯模型的限制，非常适合在视觉跟踪算法中使用。然而，粒子滤波器的核心思想是用随机样本来近似概率密度函数，因此为了达到良好的性能，粒子数目必需足够大。在视觉跟踪里面，为每个粒子计算重要性权重时需要进行一次观测来获得似然值，如计算颜色直方图及其与模型直方图的相似度。因此当粒子数目增多时，观测的次数也随之增多，这就给跟踪器带来了巨

32、大的计算负担。如果粒子滤波器中的粒子在密度函数的各个峰值附近比较密集，在其它地方比较稀疏，那么只需要较少的粒子数就能够很好地近似概率密度函数。因此，如果能找到一种优良的重要性采样函数，使得粒子具有上述分布特点，那么就可以很好地解决粒子滤波器计算量大的问题。然而通常采用的以一步状态转移函数作为重要性采样函数进行采样的方法只是根据先验概率作了预测，并没有将最新的实际观测数据作为采样的依据之一。这种方法往往会导致较差的性能，尤其是当似然函数在先验密度的尾端或相对先验密度较窄时，只有少量的粒子拥有较大的权重，这种情况下大量的计算都浪费在那些权重很小的粒子上面，为了解决这个问题，本文使用了一种经过改进的

33、粒子滤波器。该方法将基于颜色直方图的均值位移跟踪方法引入到粒子重要性采样之后、重要性加权之前。这一改进使粒子能更加有效地近似后验密度函数，因此只需要比传统粒子滤波器少得多的粒子数，就能够获得良好的效果。这一方法由E. Maggio等人提出20，他们称之为混合跟踪器。然而这种改进的粒子滤波器也有缺陷。因为均值位移算法依赖于颜色直方图，所以当颜色特征在跟踪过程中变得不可靠时（例如人突然转身的情形），均值位移算法就不起作用甚至会将粒子移动到更差的位置，即对粒子产生了“误导”，且均值位移算法在改善粒子分布情况的同时，本身也付出了较多的计算量，均值位移算法很可能使大量的粒子集中在同一处，降低了粒子的多样

34、性。本文提出根据融合算法所求得的颜色特征可靠度来限制该均值位移的迭代次数。这一修改不仅防止了粒子被“误导”现象的发生，还减小了计算量，保持了粒子的多样性。1.3.4.1 均值位移由式（4-27）和（4-28）可见，模型直方图与候选区域直方图之间的相似度是关于候选区域中心位置的平滑函数，因此可用初始位置处的泰勒展开式将它近似为： （4-45）将式（4-27）代入式（4-45）可得： （4-46）其中 （4-47）因此对目标物所在位置的估计问题就转化为使式（4-46）的第二项最大化的问题。可用均值位移算法迭代地寻找到它的一个局部最大值的位置，即递归计算以下二式： （4-48） （4-49）其中。本

35、文使用的核函数是Epanechnikov核，其轮廓函数的导数是常数，因此式（4-48）可化为： （4-50）以上递归过程在时终止，其中是一个预设的小值常数。1.3.4.2 概率方法和确定性方法的融合如果粒子滤波器中的粒子在密度函数的各个峰值附近比较密集，在其它地方比较稀疏，那么只需要较少的粒子数就能够很好地近似概率密度函数。因此，如果能找到一种优良的重要性采样函数，使得粒子具有上述分布特点，那么就可以很好地解决粒子滤波器计算量大的问题。然而通常采用的以一步状态转移函数作为重要性采样函数进行采样的方法只是根据先验概率作了预测，并没有将最新的实际观测数据作为采样的依据之一。这种方法往往会导致较差的

36、性能，尤其是当似然函数在先验密度的尾端或相对先验密度较窄时，只有少量的粒子拥有较大的权重，这种情况下大量的计算都浪费在那些权重很小的粒子上面。如果能将粒子移动到似然值较大的位置，那么就可以达到改善粒子有效性的目的。而均值位移算法正是实现这一目标的一个很好的方法。由于均值位移算法是一种非参数化（Non-Parametric）方法，它可以不借助除图像数据之外的信息实现目标跟踪。当通过粒子重要性采样获得一个新的粒子集后，再对每个粒子实施独立的均值位移操作，可将粒子移动到一个关于位置的颜色相似度函数的局部最大值处。因此，与均值位移操作实施之前相比，每个粒子具有更大的颜色似然值，对最终估计出的后验密度函

37、数的贡献也更大，因而能更有效地近似后验概率密度函数。均值位移操作和重要性采样合并起来可以看作是一个改进的重要性采样方法，这种采样将最新的观测值引入到了采样的过程当中，从而改善了粒子的有效性。1.3.4.4 改进策略本文将均值位移算法的最大迭代次数限制为与颜色可靠度成正比的线性函数： （4-51）上式是作者在实验中得到的经验公式，其中为颜色特征的可靠度，由民主融合算法算出，为预设的正值常数。由式（4-51）可见，均值位移算法的最大次数在时达到最大值。加入这个限制之后，即使当均值位移算法迭代了次仍未到达收敛位置，也不再继续移动粒子。这个修改虽然很简单，但同时克服了如上所述的原算法的三个缺点。首先，

38、当颜色特征的可靠度很低时，也很小，防止了粒子被进一步引向远离真实值的位置；其次，迭代次数的降低直接使计算大为减少；最后，在粒子滤波的框架中，本来就不需要粒子一定要位于似然函数的局部最大值处，而事实上在均值位移算法中，最前面的几步迭代计算对粒子的移动步长是最大的12，因而对于改善粒子分布也是最有效的，因此本文提出的方法有效地利用了计算量，同时防止了粒子多样性的下降。由于目标的外观在跟踪中会发生变化，在此过程中需要更新目标的颜色模型。为了避免在发生遮挡时更新，我们预设一个门限值，当颜色的似然值高于此门限值时，才进行目标状态的预测和更新。颜色模型的更新过程可以表示如下： （4-52）其中01为更新速

39、率。1.4 实验结果为了验证本文所提出算法的性能，本文用C语言结合OpenCV开源视觉库将算法在计算机上编程实现，并将它应用在不同的图像序列上。在此，只展示其中两个序列的实验结果。为了更好地验证本文所提出算法的性能，还将它生成的实验结果与另外两种算法生成的实验结果作了对比。另两种算法分别是：K. Nummiaro等人提出的基于颜色特征的标准粒子滤波器和C. Shen等人提出的基于多特征融合的标准粒子滤波器。为方便起见，将Nummiaro算法缩写为PF-CC（Particle Filter with Color Cue），将Shen算法缩写为PF-MC（Particle Filter with

40、Multiple Cues），并将本文提出的算法缩写为PF-MC-MS（Particle Filter with Multiple cues and Mean Shift）。在所有的实验中，PF-CC算法和PF-MC使用的粒子数都是150，而PF-MC-MS算法仅使用40个的粒子。跟踪对象为一个人的头部，被建模为一个直立的椭圆。运动模型如本文4.3.1节所述，其中涉及的参数设为，。观测模型如本文4.3.2所述，参数设为。颜色直方图在RGB空间计算，其格子个数为。对于形状模型，边缘处某一点的梯度值由过该点的法向线段上的梯度最大值替代，线段长度为9。跟踪初始时刻目标物被手动选定。图像序列1和序列2

41、可在 21获取，它们的分辨率是，帧率为10Hz。这两个序列均是在办公室环境中拍得，背景中存在大量杂乱的物体，目标物都经历了旋转、尺度变化、遮挡和许多其它不规则的运动。序列1的跟踪结果如图4-3所示。在第36帧中，目标物突然转身，原先是人头面对着摄像头的状态变成了背对摄像头，导致颜色完全改变。此时，PF-CC算法明显受到了旁边纸盒的误导，因为纸盒的颜色和肤色相近。同时，PF-MC和PF-MC-MS均能正常跟踪。在第40、200和210帧中，PF-CC和PF-MC均丢失了目标，因为背景中存在大量杂乱无章的物体，且物体的颜色或形状与目标物有些许相似之处。特别是在第200帧中，PF-MC明显将人头旁边

42、的电脑显示屏误认为是目标物，因为显示屏也具有规则的闭合形状。 图4-3 序列1的实验结果。从上至下依次是由PF-CC、PF-MC和PF-MC-MS生成的结果，从左至右依次对应第36、40、200和210帧。对序列2中的目标物的跟踪比序列1更加具有挑战性，因为序列2中出现了多人的情形，跟踪器很容易将其它的人的头部误认为是目标物。在序列2中被跟踪的头部目标与序列1中的头部目标属于同一个人。跟踪结果如图4-4所示。在第5帧中，PF-CC已经完全丢失目标，PF-CC估计出的目标位置部分偏离了真实值，而PF-MC-MS跟踪良好。在第70、85和133帧中，PF-CC和PF-MC均把目标物旁边的人的头部误

43、以为是目标物，而PF-MC-MS均成功地实现了跟踪。 图4-4 序列2的实验结果。从上至下依次是由PF-CC、PF-MC和PF-MC-MS生成的结果，从左至右依次对应第5、70、85和133帧。 图05 序列3的实验结果。从上至下依次是由PF-CC、PF-MC和PF-MC-MS生成的结果，从左至右依次对应第39、91、158和196帧。序列3是在演播室里拍摄的，图像分辨率是320*240，帧率为25Hz。在这个序列中，光照一直处于忽明忽暗的变化之中，且窗帘的颜色和肤色近似，窗帘上的众多皱褶以及目标物经常离开和返回摄像机视野的情形也给跟踪带来了不小的难度。该序列的跟踪结果如图4-5所示。在第91

44、帧时，目标物移出了视野；在第158帧，目标物重新进入视野。在第196帧时，PF-CC和PF-MC均丢失了目标，而这个问题被PF-MC-MS解决得很好。这就证明了PF-MC-MS具有更强的从目标丢失中恢复的能力。图4-6 序列3的各帧图像中粒子所经历的均值位移迭代次数平均值在序列3的每帧图像中，粒子所经受的均值位移迭代次数的平均值如图4-6所示。序列1、序列2和序列3中粒子所经受的均值位移迭代次数平均值分别为2.08、2.23和2.34次每粒子每帧。上述实验结果显示：PF-MC-MS仅用40个粒子时的跟踪性能优于PF-CC和PF-MC使用150个粒子时的性能，且在每帧中每个粒子只需经历很少的均值

45、位移迭代次数（本实验中为小于2.5次）。由此可见：相比于其它两种传统算法，本文提出的算法极大地提高了跟踪的鲁棒性，同时极大地减少了计算量。1.5总结 本文论述了基于多特征融合的粒子滤波目标跟踪算法。本文把目标跟踪算法分解为目标物表示和运动状态估计两个部分，分别对已有的典型算法作了介绍。然后提出了一种使用多特征融合和改进的粒子滤波器的跟踪算法。该算法使用了颜色和形状两种特征来表示目标物，并用融合算法将二者融合到粒子滤波器的观测模型中。多特征融合提高了跟踪算法的鲁棒性。由于传统粒子滤波器计算量较大，本文在重要性采样之后将均值位移算法独立施加到每个粒子上面，改善了粒子的有效性，使所需粒子的数目大大减

46、少，计算量也随之减少。本文还将均值位移算法的最大迭代次数限制为与颜色可靠度成正比，设置相似度门限来更新粒子的传递过程，防止粒子在颜色不可靠时被均值位移算法移动到更差的位置，同时进一步减少了计算量，也防止了粒子多样性的下降。实验结果表明，与传统的基于粒子滤波器的跟踪方法相比，本文提出的算法计算量更小，鲁棒性更强。1.6 本章参考文献1 D. Comaniciu , Ramesh, V. and Meer, P., Real-time tracking of non-rigid objects using mean shift, Proc. IEEE Conf. on Computer Visio

47、n and Pattern Recognition, 2000, 2: 142-149.2 D. Comaniciu, V. Ramesh and P. Meer, “Kernel-Based Objict Tracking”, IEEE Trans. on PAMI, May 2003, 25(5), 564-577.3 Nummiaro, K., Koller-Meier, E. and Gool, L. V., An adaptive color-based particle filter, Image and Vision Computing, 2003, 21: 99-110.4 P

48、rez, P., Hue, C., Vermaak, J. and Gangnet, M., Color-based probabilistic tracking, Proc. 7th European Conference on Computer Vision, 2002, 661-675.5 S.J. McKenna, Y. Raja and S. Gong, “Tracking colour objects using adaptive mixture models,” Image and Vision Computing, 1999, 17 (3): 225231.6 B. Han,

49、D. Comaniciu, and Y. Zhu et al., “Sequential Kernel Density Approximation and Its Application to Real-Time Visual Tracking,” IEEE Trans. on PAMI, July 2008, 30(7): 1186-1197.7 A. Blake, R. Curwen and A. Zisserman, “A Framework for Spatio-Temporal Control in The Tracking of Visual Contours,” Internat

50、ional Journal International Journal of Computer Vision, October 1993, 11(2): 127-145.8 M. Isard and A. Blake, “Contour Tracking by Stochastic Propagation of Conditional Density,” Proc. European Conf. Computer Vision, 1996, 1: 343-3569 M. Isard, and A. Blake, CONDENSATION conditional density propagation for visual tracking, International Journal of Computer Vision, 1998, 29(1): 5-28.10 D. DeCarlo and D. Metaxas, “Optical Flow Constraints on Deformable Models with Applications to Face Tracking,” International Journal of Computer Vision, 2000, 38(2): 99-127.11 T. Oja