王永翔　陈国初

摘 要： 粒子滤波算法是一种基于贝叶斯估计和非参数化蒙特卡罗模拟的新型算法。详细介绍了粒子滤波算法的基本原理，阐述了递推贝叶斯估计方法、序贯重要性采样以及序贯重要性重采样算法；分析了粒子滤波主要存在的问题及关键改进之处，然后介绍粒子滤波算法的应用，并对算法未来发展进行了展望。

关键词： 贝叶斯估计； 序贯重要性采样； 重采样； 粒子滤波

中图分类号：TP301.6 文献标志码：A 文章编号：1006-8228（2015）08-01-04

Research on development of particle filtering algorithm

Wang Yongxiang， Chen Guochu

（College of Electrical Engineering， Shanghai Dianji University， Shanghai 200240， China）

Abstract： Particle filtering is a new algorithm based on Bayesian estimation and non-parametric Monte Carlo simulation. This paper introduces in detail the basic principle of particle filtering algorithm， describes the recursive Bayesian estimation method， sequential importance sampling and sequential importance resample algorithm， analyzes the main problems and the key improvements on the particle filter. Then， the application and the future development of particle filtering algorithm is discussed.

Key words： Bayesian estimation； sequential importance sampling； resample； particle filter

0 引言

许多复杂的系统都存在着滤波处理、参数估计等问题，尤其在通信、自动控制、金融、弹道武器等领域滤波处理显得更加重要。1960年，卡尔曼滤波器（KF）[1]被提出，其作为一种线性、无偏的最小方差状态估计器得到很广泛应用。然而，由于卡尔曼滤波对系统要求比较苛刻，其只能处理一些线性并且噪声服从高斯分布的线性系统，对于非线性、非高斯噪声的复杂系统，其往往达不到滤波要求。尽管后来有些学者提出了扩展Kalman滤波器（EKF）[2]、无迹Kalman滤波器（UKF）[3]等，处理的系统也往往是高斯噪声分布的弱非线性的，对于强非线性的系统，其滤波精度及稳定性等仍然达不到要求。

20世纪50年代，Hammersley等人提出了一种序贯重要性采样（SIS）蒙特卡罗方法[4]，通过离散的随机样本来逼近概率分布。该算法主要是从一个重要性分布中抽取一个带有权值的样本集合来代表所研究的系统状态的后验概率密度函数，并利用这些样本及其权值对系统状态进行估计。然而，由于算法本身存在样本退化和计算复杂度高等问题，该算法很长一段时间没有得到较大发展。直到1993年，Gordon等人提出了重采样概念[5]，将其引入到SIS中产生了基本粒子滤波算法—序贯重要性重采样算法（SIR）。新算法克服了原算法中的样本退化问题，同时计算机技术的快速发展也为SIR算法的计算提供了有力保证。

本文首先通过状态空间模型详细介绍递推贝叶斯估计，粒子滤波算法的基本原理，阐述序贯重要性采样以及重要性重采样算法，然后介绍粒子滤波常见问题及关键改进之处，最后介绍粒子滤波算法的应用并对算法未来发展进行了展望。

1 基本粒子滤波算法

1.1 递推贝叶斯估计方法

粒子滤波（Particle Filter，PF）的思想是基于贝叶斯估计原理利用粒子集来表示概率的蒙特卡洛（Monte Carlo）模拟方法，它可以用在任何形式的状态空间模型上。假设状态空间模型如下：

状态模型：

xk=f（xk-1，uk-1） ⑴

观测模型：

yk=h（xk，vk） ⑵

其中，f和h为已知的状态函数和观测函数，xk是系统在k时刻的状态量，uk和vk分别为零均值的系统噪声和观测噪声，yk是k时刻状态的观测值，uk和vk相互独立并独立于过去和当前状态。

用统计描述法描述上式方程，系统模型对应为状态转移概率密度p（xk|xk-1），观测模型对应为观测似然概率密度p（yk|xk），并假定状态的初始概率密度函数p（x0|y0）=p（x0）已知。设已知k-1时刻的概率密度p（xk-1|y1：k-1），且状态xk服从一阶马尔可夫过程，则由第一步预测可得k时刻的先验概率密度函数：

⑶

其中，系统的转移概率密度：

⑷

假定p（uk-1|xk-1）=p（uk-1），则：

⑸

其中，δ（·）是狄拉克函数，若δ（·）函数存在，xk-1和uk-1已知，那么状态值xk可以通过⑴式得到。然后，若yk测量可知，则可由贝叶斯准则实现第二步的更新，得后验滤波概率密度：

⑹

其中，似然概率密度：

⑺

⑻

通常是一个归一化常数。

由式⑶～⑹构成了贝叶斯递推估计过程，整个过程实现了由k-1时刻的p（xk-1|y1：k-1）到k时刻的p（xk|y1：k）预测更新，理论上解决了求解后验概率密度的问题。但是由于式⑶的积分在实际中很难求解，并且整个过程中运用了许多假设，在实际应用中受到了很大的限制，所以对于非线性非高斯分布的系统贝叶斯估计法还不能给出很好的解决方法。

1.2 序贯重要性采样（SIS）

针对贝叶斯估计无法解决的积分问题，1954年Hammersley等人提出了SIS算法。根据Monte Carlo方法从后验概率密度中抽取N个独立同分布样本，用经验分布逼近状态的概率密度函数，使

⑼

然而，在实际中p（x0：k|y1：k）往往是非标准的多变量形式，并且它很难写成组合形式的解析分布函数，从样本p（x0：k|y1：k）中抽样通常是非常困难的甚至没法实现。所以，常常从被引入的一个容易实现采样的重要分布函数q（x0：k|y1：k）中抽样。为了便于采样，首先对q（x0：k|y1：k）进行分解：

⑽

当观测值到来时，将新的数据值加入到旧样本中得到新的样本。这样，从q（x0：k|y1：k）抽取N个独立同分布样本并加权求和来近似表示p（x0：k|y1：k），得：

⑾

其中，为归一化后的权值。

⑿

假设：

得：

⒀

结合式⑽可得权值的递推公式为：

⒁

为算法简便，设q（xk|x0：k-1，y1：k）=q（xk|xk-1，y1：k），这样重要性密度函数就只由xk-1和yk决定，每一步只需估计出p（xk|y1：k），权值递推式变为：

⒂

相应的近似后验概率密度函数：

⒃

1.3 序贯重要性重采样算法

SIS算法解决了Bayesian估计无法解决的积分问题，以样本均值代替了积分运算实现了递推贝叶斯估计。但是，SIS算法却存在着严重的样本退化问题。当空间维数或时间增加时，经过很多次迭代之后，较少量的粒子权重会变得很大，而绝大多数的粒子权重会变得很小，权值的更新大部分时间都浪费在这些权重小甚至不起作用的粒子上。

1993年，Gordon等人提出的重采样算法有效的解决了样本退化问题。重采样的根本目的是去除那些权值小的粒子，保留并复制那些权值较大的粒子[6]，从式⒃中抽取相互独立的权值相等的粒子，可以设。如图1，形象地说明了重要性采样与重采样过程。

图1 重要性采样与重采样过程

粒子退化程度一般采用有效粒子数Neff来衡量

⒄

有效的粒子个数Neff越小，意味着粒子退化越厉害，当Neff小于一定的阈值NT时，然后才进行重采样。

基本粒子滤波算法就是在序贯重要性采样（SIS）基础上加入了重采样步骤，具体步骤如下。

第一步：初始化（k=0）

从初始分布p（x0）中采样N个样本：{，i=1，2，…，N}，权值：=1/N，令k=1。

第二步：重要性采样

⑴ 采样得N个k时刻样本：{，i=1，2，…，N}

⑵ 观测值到来时，计算每个粒子权值，并由下式更新权值

⑶ 权值的归一化

第三步：判断是否重采样

计算有效粒子数Neff=1/，若Neff?NT则执行第四步；否则执行第五步。

第四步：重采样

依据权值大小采样新粒子，使其满足pr（=）=，设定=，=1/N。

第五步：估计输出

后验概率密度估计输出：

状态估计输出：

第六步：令k=k+1，返回第二步。

2 关键问题及改进之处

2.1 粒子滤波存在的关键问题

⑴ 重要性密度函数选择问题

重要性密度函数实现了粒子滤波算法中的抽样问题，其选择往往是以最小化重要性权值为标准。实验证明，为了有效地限制粒子退化，一般情况下是选择重要性密度函数作为先验概率密度函数，即q（xk|，y1：k）=p（xk|，y1：k）。然而由于这种方法没有考虑当前时刻的观测值，使现有的模型处理当前状态时会产生很大的误差，不能将概率密度函数真实分布准确的表示出来。

⑵ 样本退化问题

样本退化（或粒子退化）现象是粒子滤波技术中最严重的一个问题，选择好的重要性密度函数和重采样是解决这个问题的关键。重采样算法的提出对样本退化问题有了一定的抑制作用，但同时也产生了另外一个问题—粒子耗尽问题。由于在重采样过程中，随着采样次数的增加，较少的权值大的粒子被复制保留，大多数权值小的粒子被遗弃，这样导致粒子多样性被逐渐削减。

⑶ 样本贫乏问题

样本贫乏问题往往是由重采样过程导致的，重采样后的少数粒子不能真正的反映出后验概率密度的特征。尤其是在模型参数不变或过程噪声较小时，样本贫乏问题显得尤为突出，因为若重采样后的粒子数仅剩几个或变成一个点时，就会导致样本枯竭而严重影响滤波性能。

⑷ 滤波实时性问题

实时性也是粒子滤波中的一个重要问题。粒子滤波虽然解决了卡尔曼算法不能解决的非线性、非高斯等问题，但由于粒子滤波是源于Monte Carlo的思想随着粒子数的不断增加，算法的计算复杂度也逐渐变高，这就会严重影响算法的实时性。

2.2 粒子滤波的改进之处

⑴ 基于重要性密度函数选择的改进

重要性密度函数的选择，其根本目的是限制粒子的退化，提高算法的准确度。SIR粒子滤波器选择先验概率密度函数p（xk|）作为重要性密度函数使得算法简洁易求，但由于其选择没有考虑最新来的观测值，使得算法精度不是很高。文献[7]将EKF方法结合到PF算法中构造重要性密度函数，提出了扩展Kalman粒子滤波器（EKF-PF），不仅考虑了先验概率分布，也结合了当前的观测值，使得重要性密度函数越来越接近真实的后验密度函数分布。Merwe等人[8]将估计精度优于EKF的UKF应用于粒子滤波算法中，提出了无味粒子滤波器（UPF），获得更好的采样，使滤波算法性能得到进一步的改善。此外，对重要性密度函数的改进，还提出了高斯-厄米特粒子滤波、高斯和粒子滤波等等。

⑵ 基于重采样技术的改进

基于重采样改进PF算法中最典型的是1999年Pitt等人提出的辅助粒子滤波算法，通过引入一个辅助变量来获得一个考虑当前状态观测值的重要性概率密度函数。正则化粒子滤波器[9]也是在重采样阶段通过核密度函数进行抽样的改进算法。此外，除了对重采样本身改进之外，也有在重采样之前、重采样之后和免去重采样等地方改进。文献[10]提出的进化粒子滤波器，将进化规则融合到PF算法中，即在重采样前先对未更新粒子进行变异处理，通过竞争选择出似然密度函数大的粒子。文献[11]通过在重采样之后对粒子进行转移，然后提出了改进的马尔可夫蒙特卡罗粒子滤波算法，其通过Markov转换核函数使p（x0：k|y1：k）产生新的粒子序列来逼近目标的真实后验概率分布。文献[12]直接免去重采样步骤，将高斯分布近似概率密度p（xk|y1：k）和p（xk|y1：k-1），提出了高斯粒子滤波器消除了重采样带来的样本匮乏问题。

⑶ 其他改进方法

基于重要性密度函数和重采样的改进是粒子滤波算法中最常见的两种改进方法，这两种方法也是针对粒子滤波的有效性进行改进。除此之外，也有对粒子的实时性进行改进的算法，如改变粒子滤波的样本数量或改变系统状态的维数等。文献[13]提出的边缘化粒子滤波和文献[14]通过KLD采样样本分布来自适应改变粒子的数量方法，都使算法的实时性得到了很大提高。

3 粒子滤波的应用

随着科学技术的快速发展以及各领域各系统的复杂度的提高，滤波处理技术也不断得到发展。粒子滤波以其可以处理非线性非高斯等复杂系统的优势广泛的被应用于各个领域，如目标跟踪、系统识别与参数估计、金融数据分析、故障诊断等等。

3.1 目标跟踪

卫星导航系统、车辆、雷达跟踪等领域都涉及到目标定位与跟踪问题，粒子滤波技术在这些复杂的非线性系统的处理中得到广泛的应用。传统的粒子滤波在目标跟踪中，其模型的样本数控制往往是比较困难的，文献[15]将状态估计和系统估计分解开来计算滤波的粒子，使结果精度得到很大提高。文献[16]将粒子滤波技术结合径向神经网络最佳逼近特性应用于直升机运动跟踪中，在跟踪精度与实时性中都显示出了较好地效果，很好解决了卡尔曼等传统滤波器无法解决的非线性难题。

3.2 参数估计与系统识别

现代大多数复杂的非线性系统都存在着参数估计问题，由于系统的数据是随机的或未知的，通过粒子滤波器对系统离散变量进行模型建立来估计系统的参数是一个有效地处理方法。由于粒子滤波技术可以处理线性的和非线性系统，所以可将系统分为线性和非线性两部分来处理，不但扩展了粒子滤波在单一的非线性系统中的应用，而且也省去采用其他滤波器处理线性部分的麻烦。

3.3 金融数据分析

模糊随机系统的估值问题是金融领域数据分析中常见的问题，金融数据是随机波动不确定的，粒子滤波在处理这些数据估计时起到了一定的作用。文献[17]就将粒子滤波技术应用在股票交易数据预测中，根据交互式的粒子滤波原理分别从跟踪和滤波角度对数据进行预测，达到很好的预测效果。

3.4 故障诊断

故障诊断是各类复杂系统中的一个重要研究分支，对于线性系统的故障诊断研究目前已经取得了较好的成果，而对于非线性和强非线性系统的故障诊断仍然很不成熟。粒子滤波技术的较快发展对这方面的研究提供了解决方法。如一些模型尚不完备的复杂动态系统的故障诊断处理等，文献[18]提出了一种有效的PF算法，通过把粒子集的规格化因子和最大后验概率估计状态的信度两个值提取出来，并在此基础上设出检测未知故障模式阈值逻辑，达到了很好地预报故障效果。

除了以上介绍的领域外，粒子滤波在图像处理、计算机视觉、生物学、海洋学等领域都有相关性的应用。

4 总结与展望

粒子滤波技术在处理非线性系统时具有独特的优势，近些年其被研究的趋势也在逐渐上升。在详细阐述粒子滤波基本原理后，对算法中常见的问题以及一些改进的方法作了分析介绍，并举例说明了其在各种领域中的广泛应用。但作为一种新的滤波处理方法，粒子滤波技术仍处于不断的发展中，理论方法和实际应用还有待进一步深入研究。

⑴ 首先，粒子滤波算法本身还有待改进，如算法的收敛性、重要性密度函数选择、重采样部分，以及基于系统观测模型和状态模型准确建模等。此外，怎样减少计算量、削减粒子退化，以及进一步提高算法的准确性和实时性也仍然是未来的研究方向。

⑵ 其次，粒子滤波算法是基于Monte Carlo模拟的实现递推贝叶斯估计的数学算法，可以将其与其他智能算法相结合来对研究目标进行处理。虽然已经有不少学者根据其他智能算法对粒子滤波某个部分进行优化，但在组合算法的性能上还有待进一步提高。怎样增强粒子滤波等组合算法的稳定性和实用性也是值得更深一步研究。

⑶ 最后，尽管粒子滤波技术已应用于某些领域，但就其目前的发展还不是太成熟，仅仅部分的应用于某些领域。并且如今大多数学者对粒子滤波的实际研究往往是基于仿真模拟性的研究，怎样将粒子滤波技术扩展到更多的应用新领域还有待于进一步探索。

参考文献：

[1] Kalman R E. A new approach to linear filtering and prediction

problem. Transactions of the ASME-Journal of Basic Engineering，1960.82：35-45

[2] JAZW INSKIAH. Stochastic Processes and Filter ing Theory[M].

New York： Academic Press，1970.

[3] S. J. Julier， J. K. Uhimann， H. F. Durrant-Whyte. A new method

for nonlinear transformation of means a and estimators， IEEE T ans Automatic Control，2000.45（3）：477-482

[4] Hammersley J M， Morton K W. Poor man's Monte Carlo[J].Journal

of the Royal Statistical Society B，1954.16（1）：23-38

[5] Gordon N J， Salmond D J， Smith A F M. Novel approach to

nonlinear/non-Gaussian Bayesian state estimation[J]. IEE proceedings F： Radar and Signal Processing，1993.140（2）：107-113

[6] 赵梅，张三同等.辅助粒子滤波算法及仿真举例[J].北京交通大学学

报，2006.30（2）：24-28

[7] Ristic B， Arulampalam S， Gordon N. Beyond the Kalman filter：

Particle filters for tracking applications[M].Boston： Artech House， 2004.Boston： Artech House，2004.

[8] Merwe R V D， Doucet A， Freitas， et al. The unscented particle filter[J].

Advances in Neural Information Processing Systems，2001.96（390）：584-590

[9] Musso C， Oudjane N， Legland F. Improving regularized particle

filter[M].Doucet A， de Freitas J F G，Gordon N J.Sequential Monte Carlo Methods in Practical， New York：Springer-Verlag，2001：247-272

[10] 莫以为， 萧德云. 进化粒子滤波算法及其应用[J] .控制理论与应用，

2005.22（2）：269-272

[11] SPALL J C. Estimation via Markov Chain Monte Carlo[J].IEEE

Control Systems Magazine，2003.23（2）：34-45

[12] BOLIC M， DJURIC P M， HONG SANGJIN. Resampling

Algorithms and Architectures for Distributed Particle Filters[J]. IEEE Trans Signal Processing，2005.53（7）：2442-2450

[13] Schon T， Gustafsson F， Nordlund P J. Marginalized particle

filters for mixed linear/nonlinear state-space models[J]. IEEE Transactions on： Signal Processing，2005.53（7）：2279-2289

[14] Fox D. Adapting the sample size in particle filters through

KLD-sample[J]. The International Journal of Robotics Research，2003.22（12）：985-1003

[15] 鉴福升，徐跃民等.改进的多模型粒子滤波机动目标跟踪算法[J].控

制理论与应用，2010.27（8）：1012-1016

[16] 李春鑫，王孝通等.改进粒子滤波算法在目标跟踪中的应用[J].控制

工程，2009.16（5）：575-577

[17] Papavasiliou A. Adaptive particle filters with applications[R].

Princeton： University of Princeton，2002.

[18] 段琢华，蔡自兴，于金霞.不完备多模型混合系统故障诊断的粒子滤

波算法[J].自动化学报，2008.34（5）：581-587