薛长虎，聂桂根，汪　晶

(武汉大学卫星导航定位技术研究中心，湖北 武汉 430079)



扩展卡尔曼滤波与粒子滤波性能对比

薛长虎，聂桂根，汪晶

(武汉大学卫星导航定位技术研究中心，湖北 武汉 430079)

Comparison of Performance between Extended Kalman Filter and Particle Filter

XUE Changhu,NIE Guigen,WANG Jing

摘要：在非线性滤波方法中，粒子滤波以其精度均匀且不受模型复杂程度的影响而受到广泛关注。与传统的非线性滤波方法——扩展卡尔曼滤波相比，粒子滤波有着无可替代的优势，但也存在着一些缺陷。本文对这两种非线性滤波算法分别用MATLAB和VC++编程进行模拟仿真，并进行了一系列的比较，从算法原理、计算精度和稳定性、计算速度等方面说明了各自的优缺点和具体的差别。试验结果表明，粒子滤波计算消耗的时间远远大于扩展卡尔曼滤波消耗的时间，并且粒子滤波计算时间随粒子数的增加呈近似级数增长。

关键词：非线性系统；扩展卡尔曼滤波；粒子滤波

近年来，对滤波方法的研究是科学界的一个热门课题。在系统的数学模型比较简单且预测值服从高斯分布的情况下，卡尔曼滤波提供了一种几乎完美的求解最优估计的算法，并且在航空航天、导航与制导、目标识别与跟踪、测绘、金融等领域得到了非常广泛的应用。但在实际情况中，我们所遇到的系统通常会复杂得多，这些系统的数学模型往往具有非线性和模型不确定性等特点[1]。非线性滤波的研究已经成为一个热点话题，先后出现了扩展卡尔曼滤波、无味卡尔曼滤波、粒子滤波(又称自举滤波)等方法。其中，扩展卡尔曼滤波(extended Kalman filter, EKF)和粒子滤波(particle filter, PF)是目前研究最多、应用最广的非线性滤波算法。本文将从算法(包括系统模型、原理)和性能(包括计算精度、运算速度)等方面对这两种滤波算法进行对比。

一、扩展卡尔曼滤波和粒子滤波算法对

1. 系统模型

一个非线性离散系统的数学模型的一般形式可以表示为

(1)其中，上面为系统的状态更新方程，xk为第k时刻系统的状态向量；wk-1为第k-1时刻系统的过程的平稳噪声序列；fk为系统状态转移函数，是状态xk-1的非线性(或线性)函数。下面为系统的观测方程，zk为系统的观测向量；vk为观测的平稳噪声序列；hk为系统观测函数，是状态xk的非线性(或线性)函数。

从式(1)可以看出，状态转移函数和观测函数没有做出线性或非线性的假设条件，过程噪声和观测噪声也没有假设为高斯白噪声序列。本文将在以下章节分别对扩展卡尔曼滤波和粒子滤波对模型的处理过程进行总结。

2. 扩展卡尔曼滤波模型与算法

(2)

式中

(3)

再根据传统的卡尔曼滤波理论，可得到扩展卡尔曼滤波算法递推公式

(4)

扩展卡尔曼滤波实际上是利用上一时刻的状态估计值来预测当前时刻的状态，利用观测值进行修正。其算法简单，计算量小，易于在计算机上进行模拟试验。但由于扩展卡尔曼滤波使用了泰勒级数展开，只保留了一次项，因此该算法得到的结果并不是最优估计，总会存在着一些系统误差，并且更新方程和观测方程的非线性越强，图像弯曲程度越大，预测结果的误差就会越大。另外，随机模型的构建也非常关键，如果构建的随机模型与准确性较差会直接影响滤波结果的质量。

3. 粒子滤波的模型与算法

粒子滤波算法是一种基于贝叶斯采样估计的序贯重要性采样滤波方法，其核心是用一组带有权值的随机样本来近似表征后验概率密度函数，从而求得状态的最小方差估计[5-7]。

状态预测方程

(5)

状态更新方程

(6)

式中

(7)

然而该过程计算非常复杂，特别是式中存在的积分运算，使得该过程难以实现。1993年，Gordon和Salmond提出基于序贯重要性采样(SIS)思想的自举滤波算法，借助蒙特卡洛方法，将积分运算离散化，转变为对带权样本求和的运算过程[2,9]。

那么状态的后验期望为

(8)

但随着时间的增加，大多数粒子的权值逐渐减小并趋于零，这就会出现粒子退化问题，即重要性权值会集中在极少数的粒子上，仅靠这些粒子难以有效表达出后验概率密度函数，而权值小的粒子经过同样复杂的计算过程，其对计算结果的影响微乎其微，甚至可以忽略不计。为了解决这个问题，Gordon等提出了重采样方法。目前常用的处理方式是计算有效粒子数Neff，定义为

(9)

如果Neff

粒子滤波实质上是将连续的概率密度函数离散化，通过计算离散样本的加权和来近似计算状态后验估计值的过程。粒子滤波的优点在于它可以适用于任何系统，并没有线性或高斯分布的前提条件，精度与模型和分布也无关。因此与扩展卡尔曼滤波相比，粒子滤波的适应性、可靠性更强，精度更均匀。但是粒子滤波的数学过程比较复杂，计算困难，并且算法的精度与所选取的重要性函数和粒子数量有关。故粒子滤波在近年来计算机技术迅速发展的时代才得到一些实际应用。

二、扩展卡尔曼滤波和粒子滤波仿真试验与性能对比

设有如下非线性模型

(10)

式中，wk和vk为零均值高斯白噪声，方差分别为10.0和1.0。该状态更新方程和观测方程都是高度非线性的，下面分别使用扩展卡尔曼滤波和粒子滤波算法对该模型进行50步估计，并从计算精度和速度方面对两种方法的性能进行比较。

1. 计算精度的比较

试验选用最新版Matlab软件(Matlab 2014a)进行模拟，取初值x0=0.1，粒子数N=500。图1为扩展卡尔曼滤波和粒子滤波估计结果，状态真实值大概介于-20～+20之间。从图中可以看出，粒子滤波的估计结果与真实值更为接近，除了少数几个偏差较大的点，绝大多数估计值都很接近真实值，而扩展卡尔曼滤波在很多时刻都会出现偏离真实值较大的情况，并且偏离的幅度也比粒子滤波大得多。为了更直观地显示出二者的差异绘制了扩展卡尔曼滤波和粒子滤波的估计结果与真实值的误差折线图，如图2所示。可以看出，粒子滤波计算结果的误差大小和方差明显优于扩展卡尔曼滤波。在系统非线性较强的时刻，扩展卡尔曼滤波算法得到的结果误差大小能达到粒子滤波误差的几倍甚至十几倍。

图1　扩展卡尔曼滤波与粒子滤波估计结果

图2　扩展卡尔曼滤波与粒子滤波估计值与真实值的差

为了使试验结果更有说服性，笔者用Visual C++语言进行了同样的仿真过程，使用的编译器为微软发布的Visual Studio 2010，设置同样的初始条件，将计算结果导入到数据文件中，再借助Matlab绘图功能绘出状态估计折线图(如图3所示)和误差折线图(如图4所示)，可以得到与Matlab仿真类似的结果。可以看出，在高度非线性的系统中，粒子滤波算法的精度和稳定性明显优于扩展卡尔曼滤波。

2. 计算速度对比

将扩展卡尔曼滤波与粒子滤波的仿真代码用两个脚本分别实现，运行并计时，比较二者的计算时间。笔者使用的计算机CPU型号为Intel Core i5双核处理器，主频2.60 GHz，内存大小为8 GB，Windows 8操作系统。将扩展卡尔曼滤波和粒子滤波仿真代码分别运行10次，并记下每次运行的时间。粒子数不是很多时，VC++运行两种算法时间差别不大，而Matlab运行时间差异比较明显，见表1。

图3　用VC++实现的状态估计结果

图4　用VC++实现的计算结果误差

s

进行同样的50步估计过程，卡尔曼滤波只需将每一步的结果进行迭代计算来得到下一步的先验预测，再用观测值进行修正即可；而粒子滤波需要将每一步的每个粒子进行迭代计算，并进行重采样，最后将所有的粒子取加权和得到最终结果，实际上每一个粒子的计算过程相当于一个小的卡尔曼滤波过程，粒子滤波的计算量远远大于扩展卡尔曼滤波。因此，粒子滤波计算用的时间与扩展卡尔曼滤波有着比较明显的差距。

从粒子滤波的运算过程中可以看出，粒子滤波的计算量与所采样的粒子数量密切相关。笔者统计了仿真试验过程中粒子数量对粒子滤波程序运行时间的影响，见表2。

表2　粒子滤波不同粒子数运算时间统计　s

可见，采样的粒子数量对粒子滤波运算速度的影响是十分显著的。当粒子数较少时(如100或200)可以较快地得到计算结果，Matlab仿真模拟可以在1 s内完成计算和绘图工作，VC++计算时间几乎看不出有差异；随着粒子数的逐渐增长，Matlab程序和VC++程序的运行时间都会有比较明显的增加；当粒子数达到5000时，Matlab程序的计算时间能达到近3 min，VC++程序运算时间也达到了几秒。图5和图6分别显示了Matlab程序和VC++程序计算时间随粒子数的变化趋势，可见程序计算时间与粒子数量并不是呈线性变化的，而是呈近似抛物线的变化趋势。

图5　Matlab程序计算时间随粒子数的变化

图6　VC++程序计算时间随粒子数的变化

针对以上试验结论，笔者另外选取了一组非线性模型进行了验证。系统模型[17]为

对该系统进行同样过程的模拟试验，滤波结果对比、误差对比及粒子滤波时间变化等得到与上述仿真试验相似的结果(如图7—图9所示)，由此可以验证上述结论。

图7　两种滤波算法估计结果对比

图8　两种滤波算法结果误差对比

然而在实际工程应用中，系统模型是极其复杂的，并且绝大多数系统是多维的，状态量和观测量都是多维向量，为了使最后计算结果达到精度和稳定性等方面的要求，通常需要采集几万个粒子来计算，其计算量是非常庞大的，特别是在需要实时计算数据的领域，如组合导航、目标跟踪等，普通计算机的计算速度是远远达不到要求的，因此粒子滤波的实用性就降低了很多。有学者提出了很多相关的改进算法来改进粒子滤波的计算精度和速度，如Freitas等提出扩展卡尔曼粒子滤波算法的思想[9,12]，Merwe等提出无味粒子滤波算法[13]，Pitt等提出辅助粒子滤波算法[14]，蒋蔚博士等提出了支持向量机概率密度估计粒子滤波和支持向量回归机粒子滤波等方法[15-16]。这些方法都在一定程度上改善了粒子滤波的性能和精度，但仍然没有使粒子滤波广泛地应用于实时计算的领域。

图9　Matlab程序计算时间随粒子数的变化

三、结束语

粒子滤波具有不受系统模型的限制、对被估计状态的后验分布不做任何假设及在非线性系统滤波中精度均匀、稳定性好等特性，因此具有其他估计方法不具备的优势，但因其计算过程中重要性采样、粒子退化和计算量等问题导致其实现起来比较困难、实时性差，因此粒子滤波的适用领域非常有限。试验表明，同样的非线性动态系统，粒子滤波的精度和稳定性优于扩展卡尔曼滤波，但其运行消耗的时间要远远大于扩展卡尔曼滤波；并且，粒子滤波的运行时间随粒子数量的增加呈近似抛物线增长，粒子数越多，消耗的时间增加越快。

目前大部分领域在非线性滤波中都还使用算法简单、计算方便的扩展卡尔曼滤波方法，然而随着各领域对滤波计算精度和稳定性等方面的要求越来越高，粒子滤波算法将会逐渐改进和完善，并将应用于各种科研和工程领域中。

参考文献：

[1]赵琳, 王小旭, 丁继成，等. 组合导航系统非线性滤波算法综述[J]. 中国惯性技术学报, 2009(1):46-52.

[2]GORDON N J, SALMOND D J, SMITH A F M. Novel Approach to Nonlinear/Non-Gaussian Bayesian State Estimation[C]∥IEE Proceedings F (Radar and Signal Processing). [S.l.]: IET Digital Library, 1993.

[3]毛克诚, 孙付平. 扩展卡尔曼滤波与采样卡尔曼滤波性能比较[J]. 海洋测绘, 2006(5):4-6.

[4]HAYKIN S E. Kalman Filtering and Neural Networks [M]. New York: John Wiley & Sons, 2001.

[5]胡士强, 敬忠良. 粒子滤波原理及其应用[M]. 北京: 科学出版社, 2010: 21-25.

[6]于金霞,刘文静,汤永利. 粒子滤波重采样算法研究[J]. 微计算机信息, 2010(16)：44-45.

[7]胡士强, 敬忠良. 粒子滤波算法综述[J]. 控制与决策, 2005(4)：361-371.

[8]CHEN Z. Bayesian Filtering: From Kalman Filters to Particle Filters, and Beyond [J]. Statistics, 2003, 182(1): 1-6.

[9]DOUCET A, GODSILL S, ANDRIEU C. On Sequential Monte Carlo Sampling Methods for Bayesian Filtering [J]. Statistics and Computing, 2000, 10(3): 197-208.

[10]程水英, 张剑云. 粒子滤波评述[J]. 宇航学报, 2008(4)：1099-1111.

[11]ARULAMPALAM M S, MASKELL S, GORDON N, et al. A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking [J]. Signal Processing, IEEE Transactions on, 2002, 50(2): 174-188.

[12]FREITAS de GOMES,FERDINAN DO J. Bayesian Methods for Neural Networks[D]. [S.l.]: University of Cambridge, 2003.

[13]MERWE der R V,FREITAS de N,DOUCET A, et al. The Unscented Particle Filter[J].NIPS, 2001:13: 584-590.

[14]PITT M K, SHEPHARD N. Filtering via Simulation: Auxiliary Particle Filters [J]. Journal of the American Statistical Association, 1999, 94(446): 590-599.

[15]JIANG W, YI G, ZENG Q. Application of Proximal Support Vector Regression to Particle Filter[C]∥Intelligent Computing and Intelligent Systems, 2009. [S.l.]：IEEE, 2009.

[16]蒋蔚. 粒子滤波改进算法研究与应用[D].哈尔滨：哈尔滨工业大学, 2010.

[17]杜航原, 郝燕玲, 赵玉新. 基于集合卡尔曼滤波的改进粒子滤波算法[J]. 系统工程与电子技术, 2011, 33(7): 1653-1657.

中图分类号：P228

文献标识码：B

文章编号：0494-0911(2016)04-0010-05

通信作者：聂桂根

作者简介：薛长虎(1992—)，男，硕士生，主要研究方向为多源观测数据与滑坡机理模型同化理论与方法。E-mail：xch073423@163.com

基金项目：国家重点基础研究发展计划(2013CB733205)

收稿日期：2015-05-29

引文格式： 薛长虎，聂桂根，汪晶. 扩展卡尔曼滤波与粒子滤波性能对比[J].测绘通报，2016(4)：10-14.DOI:10.13474/j.cnki.11-2246.2016.0111.