基于粒子滤波架构的实时目标跟踪算法研究

孟军英，刘教民，韩 明，王 娟

（1.燕山大学 信息科学与工程学院，河北 秦皇岛 066004；2.石家庄学院 计算机系，河北 石家庄 050035）

在视频序列图像中，对感兴趣的目标进行跟踪，获取其各种运动参数及运动轨迹的问题，称为目标跟踪.目标跟踪可以分为基于参数估计的跟踪和基于状态估计的跟踪两种[1].基于参数估计的典型跟踪算法是Camshift算法，该算法具有跟踪速度快及可以收敛至局部极值的优点，但在跟踪过程中发生相似颜色干扰、背景复杂等情况时，容易收敛于非目标，导致跟踪失败.基于状态估计的滤波可以分为针对线性随机系统估计问题的线性滤波和针对非线性随机系统的非线性滤波.在线性滤波问题上，最著名的就是Kalman滤波器.对于线性和高斯的系统状态空间模型Kalman滤波器是一个线性无偏的最小方差估计器，可以提供可靠的解析解[2].但是，现实世界中多数系统是非线性、非高斯或包含有非线性、非高斯的因素.因此，目前大量的研究工作都集中在非线性滤波中，并发展出了多种有效算法，其中最具代表性的有扩展卡尔曼滤波（Extended Kalman Filter，EKF）、Unscented卡尔曼滤波（UKF）、粒子滤波器（Particle Filter）等.其中，EKF算法是将非线性状态函数和观测函数进行局部线性化（一阶泰勒级数展开），然后再进行Kalman滤波.EKF要求随机系统的状态分布是高斯的，对于许多实际的系统其仍是一种近似精度只有一阶的非线性高斯滤波器，对强非线性系统滤波精度低.1993年N.Gordon等人提出一种自举粒子滤波（Bootstrap）算法，采用蒙特卡洛(Monte Carlo)模拟方法中的序贯重要性采样（SIS）方法依据大数定理来求解贝叶斯估计中的积分运算，适用于任何能用状态空间模型描述的非线性系统，精度可以逼近最优估计[3].它为分析非线性动态系统提供了一种有效的解决方法，从而得到了广泛的关注.

但是，为了逼近最优估计，提高跟踪的准确性，通常需要大量的粒子，而粒子数的增加会使计算量成级数增加，算法实时性变差.目前在这一领域的优化算法主要有自适应粒子滤波（adaptiveparticle filter，APF）.APF主要思想是让粒子数目随信号环境的变化而适应改变，从而减少冗余粒子，降低算法的复杂度和计算量，但其粒子数受权值方差影响比较大，粒子间的相关性强，难以并行实现.RTPF多采用减少粒子集中的粒子数、丢弃数据或组合数据的方法来提高算法的实时性，在实现上可能会由于粒子数不足而导致滤波发散.因此，找到一种在保证滤波精度前提下的实时性粒子滤波算法，成为目前对粒子滤波算法优化的主要方向.

本文在粒子滤波的基本架构上，选取EKF产生的高斯分布作为重要性概率密度函数，使粒子分布更接近实际的后验分布，然后，应用Camshift算法，使粒子向真实后验分布进一步聚集，使有效粒子增多，排除权值过小的无效粒子，从而提高算法效率.

1 粒子滤波基本架构

动态状态空间模型分为状态转移模型 |1和观测模型 | ，其中 为系统在 时刻的状态变量， 为系统在 时刻的测量值.对于非线性、非高斯过程，其模型可表示为

其中： 与 分别为过程噪声和观测噪声，并且相对独立、协方差分别为 和 的零均值加性噪声序列； : , : 为有界非线性映射.假设系统的状态转移是一个Markov过程，那么

在时刻 的后验概率密度可近似表示为

大多数情况下，直接从0:|1:抽样十分困难，所以一般从与其同分布的重要性函数0:|1:抽取样本[3]，此时权值定义为

分解后，权值更新公式如下

后验概率密度的加权近似为

粒子滤波算法一个不可避免的问题就是权值退化.经过多次迭代，大多数粒子的权值变得很小，状态空间中的有效粒子越来越少，大量的计算浪费在对估计后验滤波概率分布几乎不起作用的粒子更新上，使得跟踪性能下降.针对此问题，Gordon等人提出了重采样方法[4].其基本思想是通过对概率密度函数重新采样，过滤掉权值较小的粒子，复制权值大的粒子.但是，如果不断复制权值大的粒子，不可避免的出现样本枯竭问题，损失信息，因此可以在重采样前根据一定准则判断是否需要进行重采样.考虑到实时性，目前常用的准则是通过有效粒子数 与阀值 的关系来进行判定.

2 实时粒子滤波算法设计

粒子滤波的跟踪精度与采样的粒子数目成正比，粒子数目增加会使计算复杂度大大增加，实时性变差.因此，本文将EKF和Camshift算法嵌入到粒子滤波架构，从重要性概率密度函数选取以及粒子聚类两方面优化粒子滤波算法，提高其实时性.

2.1 重要性概率密度函数的选取

无论是从提高实时性或是避免样本枯竭角度考虑，重要性密度函数的选择都是一个十分关键的问题．选择可以满足重要性权值的方差最小原则，但在实际应用中，由于目标概率密度并不能写成一般的解析式，所以直接从中抽取样本几乎是不可能实现的．目前，多数应用选取先验分布作为重要性函数，即．但由于先验分布并未包含 时刻的最新测量值，因而产生的粒子常常位于后验分布的尾部，使得权值变化较大，容易导致滤波发散，而且当似然函数的高似然区域出现在先验概率分布的尾部时，还会出现退化现象，并且在随后的离散分布重采样过程中极易导致严重的粒子衰退现象．

通过分析发现，大多数系统的过程噪声都是高斯的，或者属于类高斯分布，也就意味着其先验建议分布是类高斯的，那么，利用高斯分布作为重要性密度函数是可行的[5]．而且由于高斯建议分布叠加了真实建议分布与最新测量值 ，使先验分布朝着高似然区域移动，与测量值有关粒子的权值相应增大，经过重采样过程，这些粒子在总的粒子中的比例增加，而与观测信息无关的粒子将被舍弃，使运算代价不会无谓浪费，因而能够有效提高粒子滤波的效率和精度．

因此，本算法在生成粒子时，利用EKF滤波算法中产生最优的高斯分布作为重要性分布，结合最新的测量值，通过高斯近似不断更新后验概率分布，实现递推估计．也就是说，EKF在任意时刻按照如下方式对后验概率密度进行近似

然后，让新粒子从各自的重要性密度函数中产生出来，然后执行权值更新过程，并根据判定准则对粒子执行重采样步骤.

2.2 基于均值漂移的粒子聚类

均值偏移算法本质上是一种基于核概率密度估计的无参数方法[7]．对于一个服从概率密度函数 的数据集{,=1,2,... ,n}，对数据集中的每一点分别执行均值偏移迭代，使它们朝着相似度高的区域移动，直到算法最终收敛．

而均值偏移向量可以表示为

均值偏移向量总是指向概率密度梯度的方向.从图1可以看出，状态转移完成后，采用Camshift算法，对粒子进行均值偏移迭代，那么粒子就会沿着概率密度梯度的方向移动，最后粒子在后验概率密度函数值大的区域聚集，完成粒子聚类.

图1 基于Camshif算法的粒子聚类示意图Fig.1 Particle clusterbased on Camshift

3 算法具体实现

融合了Kalman和Camshift的完整粒子滤波算法流程如下：

2）应用Kalman滤波递推公式更新采样粒子，进行状态预测；

4）采用Camshift算法对每个粒子进行漂移，得到聚类后的粒子集；

5）权值更新与归一化权重；

6）均值与方差估计；

4 算法的实验结果及分析

将所提出的改进的粒子滤波算法在交通目标跟踪和违章检测中进行了应用测试.系统中采用的交通监控视频分辨率为480×640，实现了对单目标以及多目标的跟踪.

如图2所示，有4辆车同时被系统检测出并进行了有效的实时跟踪.在右侧车道中，车辆行驶路线上有阴影干扰，但是系统还是比较好的识别了目标，并未发生目标丢失，说明了本算法在存在干扰因素的复杂环境中仍然可以正常工作，鲁棒性较强.

图2 干扰情况下的车辆跟踪（从左到右分别是第11、15、20帧）Fig.2 Target tracking under distribution(Frame11,15,20)

通过实验，将本算法与Camshift滤波算法和基本粒子滤波算法进行了性能比较，图3为算法性能比较图，通过对x方向图3a），y方向图3b）和欧式距离图3c）3个参数进行对比，可以看到本算法的在跟踪误差上优于其他两个算法，跟踪精度更高.

表1 算法时间性能和跟踪精度比较Tab.1 Comparison of time performance and tracking accuracy

为了测试算法的实时性，将所开发的实时跟踪算法与Camshift及基本粒子滤波算法进行了时间性能及误差的联合比较.从表1中看出，Camshift算法虽然跟踪速度最快，但是其误差是本文算法的8倍左右.而基本粒子滤波算法在采用相同粒子数目的情况下，跟踪的实时性及误差明显低于本文所提出的算法，随着粒子数目增加，这种现象更加明显.另外，从表中可以清楚的看出，基本粒子滤波算法在粒子数减少时，跟踪精度下降十分明显，而本文算法在粒子数为100时，其跟踪精度与基本粒子滤波算法粒子数为500时基本相当.实验结果说明，基于粒子滤波架构嵌入Camshift的跟踪算法在跟踪效率上具有明显的优势.其中，误差采用均方根误差来衡量.

5 结论

粒子滤波算法因其较强的非线性处理能力而成为目前的研究热点.但由于算法的局限，实时性较差，限制了其在工程上的应用.通过分析发现，许多非线性系统都可以看作是一个包含线性子结构的状态空间模型，因此，可以利用Kalman滤波器处理线性的状态预测过程，选取优化的重要性概率密度函数，使先验分布向高似然区域移动，增加与量测值有关的粒子权值.进一步利用Camshift算法，使粒子向后验概率密度高的区域聚类，进一步降低计算复杂度，使粒子滤波算法效率大大改善.实验结果表明，改进的粒子滤波算法可以有效减少计算量，在复杂环境下也可以实现对目标的有效、实时跟踪.

[1]Gordon N J，Salmond D J，Smith A FM.A novelapproach tononlinearand non-Gaussian Bayesian stateestimation[J].IEEEproceeding，1993，140：107-113.

[2]Julier SJ，Uhlmann JK.A new extension of the Kalman filter to nonlinear systems[C]//The11th IntSymposium on Aerospace/Defense Sensing，Simulation and Controls，Orlando:IEEE，1997:54-65.

[3]Arnaud Doucet，Nando De Freitas.SequentialMonte Carlo Methods in Practice[M].Berlin:The Springer press，2001:97-118.

[4]Doucet A，Gordon N J，Krishnamurthy V.Particle filters for state estimation of jump Markov linear systems[J].IEEE Transactions on Signal Processing，2001，49：613-624.

[5]Schoh T，Gustafsson F，Nordlund P J.Marginalized particle filters for m ixed linear/nonlinear state-space models[J].IEEE Trans On Signal Processing，2005，53（7）：2279-2289.

[6]刘军.科学计算中的蒙特卡罗策略 [M].北京：高等教育出版社，2009：110-116.

[7]王鑫，唐振民.一种改进的基于Camshift的粒子滤波实时目标跟踪算法 [J].中国图象图形学报，2010，15（10）：1507-1514.

[8]Collins R T.Mean shift Blob Tracking through Scale Space[C]//Proc of the IEEECSConference on Computer Vision and Pattern Recognition，San Francisco:IEEE，2003:234-240.

[9]魏武，张亚楠，裴海龙，等.融合多模型的粒子滤波运动目标实时跟踪算法 [J].公路交通科技，2010，27（1）：95-100.

[10]Taek Lyul Song，Dong Gwan Lee，Jonha Ryu.A probabilistic nearestneighbor filter algorithm for tracking in a clutter environment[J].Signal Processing，2005，85（10）：2044-2053.