基于粒子滤波算法的目标跟踪及遮挡处理算法1.1引言对运动目标物的跟踪也是视觉监控系统中的基础算法之一。
目标跟踪的任务是通过对图像序列的处理，准确估计出感兴趣目标物在每个时刻的运动参数，包括位置、大小、速度、加速度以及运动轨迹等，为行为理解等更高层的任务打下基础。
本章首先概述目标跟踪算法的基本步骤和难点，并对现有算法作分类简介；然后对实现鲁棒跟踪所必需的工具——在线贝叶斯估计算法作详细介绍；在此基础上详细论述本文使用的跟踪方法，该方法将已有的多种先进算法有机结合，使计算量显著降低，鲁棒性增强；最后对提出的算法进行总结和分析。
1.2 目标跟踪算法概述目标跟踪算法主要由两个部分组成：（1）目标物表示；（2）运动状态估计。
下面对它们分别介绍。
1.2.1目标物表示目标物表示的核心在于特征的选择和提取，即用什么特征来描述和表示感兴趣目标物。
一个好的目标物表示方法应该能够将被跟踪的目标物和背景中的物体以及其它物体区别开来，这正是目标物表示的难点所在。
运动目标物所在的环境通常是很杂乱的，其中存在许多与目标物有相似特征的物体。
例如：房间内的窗帘、家具等往往与人的皮肤颜色相近；当监控视野中存在多个行人的时候，跟踪器容易将目标行人与其他行人相混淆。
下面介绍几种常用的特征。
1.2.1.1颜色特征颜色是人类辨识物体的重要特征，也是视觉跟踪中最常用的特征之一。
颜色特征通常是在一块区域中提取出来的，因此它具有对目标平面旋转、非刚性形变、远离或靠近镜头的尺度变化以及部分遮挡等情形较为鲁棒的优点。
另外，由于图像直接由一个个像素的颜色值所表示，因此颜色特征还具有容易提取、计算简单的优点。
最常用的颜色特征是颜色直方图。
Comaniciu等人提出了基于颜色直方图的跟踪算法[1][2]。
在他们的方法中，颜色直方图受到了核函数的空间加权。
这样区域内中心附近的像素对颜色直方图有更大的贡献，使跟踪更加精确，因为区域边缘的像素可能来自背景或其它物体，其可信度较低。
具体的操作流程主要包括：（1）将目标物初始时刻的颜色直方图保存起来作为模型，并在后面的跟踪过程中作增量平均式更新。
（2）以上一帧中估计出的目标物所在位置为初始候选区域，计算颜色直方图，并计算它与模型直方图的Bhattacharrya系数，Bhattacharrya 系数越大，说明二者的相似度越高。
（3）使用均值位移（Mean Shift）算法迭代式地移动候选区域的位置，最终在Bhattacharrya系数关于位置坐标的一个局部最大值处收敛，该位置即当前帧的估计值。
该方法计算简单，跟踪效果较好，最大的优点是可以跟踪非刚性目标物。
但是该方法求得的是一个局部最优解，在一些场景中不够精确。
尤其是当目标物的运动速率较快以至它在前后两帧中的位置之差大于目标物本身的尺寸时，以及目标物被严重遮挡时，该方法将会失效。
为了克服Comaniciu方法的缺点，K.Nummiaro等人将颜色直方图融入粒子滤波器（Particel Filter）的框架中[3]，P. Pérez等人也提出了类似的方法[4]。
上面提到的均值位移和粒子滤波器两种算法将分别在本文的后续章节中中介绍。
颜色特征除了用直方图来表达之外，还可以用连续密度函数来表达。
McKenna等人提出用混合高斯模型来描述目标物的颜色分布[5]。
该模型可由期望最大化（Expectation-Maximization）算法进行初始化，在跟踪过程中用在线期望最大化方法进行更新。
由于混合高斯模型的组件数目有限且固定，有时不能精确地描述目标物的颜色分布。
为此，Bohyung[6]提出序列核密度近似（Sequential Kernel Density Approximation，SKDA）算法。
该方法充分利用了高斯函数的平滑性以及良好的导数性质，用数目可灵活变动的高斯函数的加权和来近似颜色的密度函数。
其中每个高斯函数的均值对应密度函数的一个局部峰值，该峰值由均值位移算法求得。
每个高斯函数的协方差矩阵则通过对峰值处的曲率拟合来估计。
当不同高斯函数的均值可由均值位移算法收敛到同一个峰值处时，这些高斯函数可以由一个高斯函数来近似，因此当观测样本越来越多时，高斯函数的数目不会无限地增多。
序列核密度近似算法对颜色分布的描述非常精确，但计算量大是它的一个缺点。
1.2.1.2 轮廓特征轮廓特征是对物体形状的描述，和颜色特征一样，也是人眼辨识物体的重要依据。
轮廓特征具有不受光照变化影响、可表示外形复杂的物体等优点。
Isard将轮廓特征与概率方法结合起来，实现了对任意形状的目标物的跟踪，也由此奠定了用概率方法进行视觉跟踪的基础框架[7-9]。
他们描述物体轮廓的工具是B样条曲线。
B样条曲线可以表示成一系列控制点坐标对相应B样条基函数的加权和，因此可由这些控制点的坐标值构成的向量—控制点向量来表示。
控制点向量构成的空间称为样条空间。
对于具有复杂几何形状的目标，样条空间的维数很高，如果对其变化不加任何限制，则难以表达跟踪目标。
为此，首先建立好目标物的控制点向量模板，再将目标物的运动限定为平移、尺度变化、平面旋转等几种有限的形式，就可获得样条空间的一个子空间，称为形状空间。
形状空间的维数比样条空间低得多，因此可将其中的每一个向量线性映射为一个低维的形状向量来表示，这样可使轮廓跟踪的性能更稳定，计算量也大大减小。
1.2.1.3其它特征颜色和轮廓可以说是两种最常用的特征。
除此之外，还存在其它的一些特征，例如光流[10]和局部二元图[11]。
光流是一种有效的特征，其缺点是计算量大，难以满足实时性要求。
局部二元图是对图像纹理的一种有效表示，相比于颜色特征，具有光照不变性的优点。
1.2.2 运动状态估计目标跟踪过程中需要处理一些复杂的情形，例如：目标物经历较大的外形变化，目标物被其他物体暂时遮挡，跟踪丢失后需要重新恢复等，因此要求运动状态估计方法有较好的鲁棒性。
此外，由于监控系统的实时性要求，对计算量有严格的限制，这也对运动状态估计算法提出了挑战。
确定性跟踪方法本质上是一个优化问题。
这种方法的思想是：首先通过手动或目标检测获得目标模板，建立代价函数（Cost Function）来表达目标候选位置和目标模板的相似程度，然后利用最优化方法找到代价函数的最大值，认为最大值对应的位置就是目标在图像序列中的位置。
基于均值位移（Mean Shift）算法的跟踪方法是确定性跟踪方法的典型代表[1][2]。
均值位移跟踪方法简单有效，在一些跟踪场景取得了较满意的跟踪效果。
但其缺点在于没有利用图像数据以外的先验信息，不能跟踪快速运动的物体，不能很好地处理遮挡问题。
概率跟踪方法将目标跟踪转换为在贝叶斯滤波框架下推理目标状态（如位置、速度）后验概率密度的过程。
首先选择状态变量，通过状态转移方程进行预测，然后利用最新观测值对预测作出修正。
当过程噪声和观测噪声都是高斯分布且状态转移方程和观测方程是线性的，常规的卡尔曼滤波（Kalman Filter）能给出最优解[12]；当状态方程和观测方程是非线性函数时，扩展卡尔曼滤波（Extended Kalman Filter）或者无迹卡尔曼滤波（Unscented Kalman Filter）[13,14]能近似求解后验概率。
如果状态空间是由有限的离散值组成，隐马尔科夫模型（HMM）[15]可以实现跟踪。
但是在实际场景中，状态方程和观测方程往往都是非线性的，同时噪声也是非高斯的，而且状态分布是多模态的，在这种情况下，常常利用近似方法求解后验概率密度，一个很好的方法就是粒子滤波器。
粒子滤波器不需要线性、高斯、单模态假设，特别适用于图像跟踪领域，已经成为图像跟踪的研究热点。
本文所提出的视觉跟踪方法的主体框架也是粒子滤波器，本文将对包括粒子滤波器在内的贝叶斯估计理论在下节中作详细的介绍。
1.2.2.1 贝叶斯递归状态估计在视频跟踪方法中，跟踪问题可以看成是在线的贝叶斯估计问题，其基础为运动模型和观测模型，可用以下两个方程来描述：()11,k k k k x f x v --= （4-1）(),k k k k z h x n = （4-2）式中，:x v x n n n k f R R R ⨯→和:x n z n n n k h R R R ⨯→可分别为非线性函数，k v 和k n 分别为过程噪声和观测噪声，且相互独立。
x n 和v n 分别为状态向量和过程噪声向量的维数，z n 和n n 分别为观测向量和观测噪声向量的维数。
从贝叶斯估计角度来看，跟踪问题就是从所有的历史观测数据{}1:1,,k k z z z =中推理出k 时刻状态k x 的值，即：估计()1:|k k p x z 。
状态变量可以包含目标物在图像中的位置、大小及运动速度等分量。
假设状态变量初始概率密度函数()0p x 作为先验知识已知，那么()1:|k k p x z 可以通过下面两式递推得到：()()()1:1111:11|||t k k k k k k p x z p x x p x z dx -----=⎰ （4-3）()()()()1:11:1:1||||k k k k k k k k p z x p x z p x z p z z --=（4-4）式中，()1|k k p x x -由目标的运动状态方程，即式（4-4）定义，()|t t p z x 由目标的观测方程，即式（4-2）定义，()1:1|k k p z z -为归一化常数，具有如下形式：()()()1:11:1|||k k k k k k k p z z p z x p x z dx --=⎰ （4-5）以上过程可以用图4-1中的概率图模型来描述，图中k x 和,1,2,k z k =分别为第k 时刻的目标状态和观测。
图0-1 贝叶斯跟踪图模型在得到()1:|t t p x z 之后，可以计算出最小均方意义下的最优估计和估计方差：()1:|t t t t t x x p x z dx =⎰ （4-6）()()()()()1:|TTttt tt tttt t t E x x x x x xx x p x z dx ⎛⎫--=-- ⎪⎝⎭⎰ （4-7）式（4-3）和式（4-4）构成了最优贝叶斯估计的基础，分别称之为预测和更新方程。
由于在计算此二式时，存在高维积分运算，因此实际中很难解出状态最佳估计的解析形式，利用（4-3）和式（4-4）得到的状态解仅仅是概念上的，在实际中，必须利用一些数学工具来近似求解。
1.2.2.2 重要性采样重要性采样是一种普适的蒙特卡洛积分方法。
但是，上述最简单的表示形式还不能在迭代估计中使用，因为在估计后验密度函数()0:1:|k k p x z 之前，必需保存好所有的历史数据1:k z ；又因为在每个新的时刻，获得一个新的观测数据1k z +后，必须对状态的历史轨迹0:k x 重新仿真以计算新的重要性权值，这样计算量将随时间的推移而无限增长。