薛長虎，聶桂根，汪　晶

(武漢大學衛(wèi)星導航定位技術(shù)研究中心，湖北 武漢 430079)

?

擴展卡爾曼濾波與粒子濾波性能對比

薛長虎，聶桂根，汪晶

(武漢大學衛(wèi)星導航定位技術(shù)研究中心，湖北 武漢 430079)

Comparison of Performance between Extended Kalman Filter and Particle Filter

XUE Changhu,NIE Guigen,WANG Jing

摘要：在非線性濾波方法中，粒子濾波以其精度均勻且不受模型復雜程度的影響而受到廣泛關(guān)注。與傳統(tǒng)的非線性濾波方法——擴展卡爾曼濾波相比，粒子濾波有著無可替代的優(yōu)勢，但也存在著一些缺陷。本文對這兩種非線性濾波算法分別用MATLAB和VC++編程進行模擬仿真，并進行了一系列的比較，從算法原理、計算精度和穩(wěn)定性、計算速度等方面說明了各自的優(yōu)缺點和具體的差別。試驗結(jié)果表明，粒子濾波計算消耗的時間遠遠大于擴展卡爾曼濾波消耗的時間，并且粒子濾波計算時間隨粒子數(shù)的增加呈近似級數(shù)增長。

關(guān)鍵詞：非線性系統(tǒng)；擴展卡爾曼濾波；粒子濾波

近年來，對濾波方法的研究是科學界的一個熱門課題。在系統(tǒng)的數(shù)學模型比較簡單且預測值服從高斯分布的情況下，卡爾曼濾波提供了一種幾乎完美的求解最優(yōu)估計的算法，并且在航空航天、導航與制導、目標識別與跟蹤、測繪、金融等領(lǐng)域得到了非常廣泛的應用。但在實際情況中，我們所遇到的系統(tǒng)通常會復雜得多，這些系統(tǒng)的數(shù)學模型往往具有非線性和模型不確定性等特點[1]。非線性濾波的研究已經(jīng)成為一個熱點話題，先后出現(xiàn)了擴展卡爾曼濾波、無味卡爾曼濾波、粒子濾波(又稱自舉濾波)等方法。其中，擴展卡爾曼濾波(extended Kalman filter, EKF)和粒子濾波(particle filter, PF)是目前研究最多、應用最廣的非線性濾波算法。本文將從算法(包括系統(tǒng)模型、原理)和性能(包括計算精度、運算速度)等方面對這兩種濾波算法進行對比。

一、擴展卡爾曼濾波和粒子濾波算法對

1. 系統(tǒng)模型

一個非線性離散系統(tǒng)的數(shù)學模型的一般形式可以表示為

(1)其中，上面為系統(tǒng)的狀態(tài)更新方程，xk為第k時刻系統(tǒng)的狀態(tài)向量；wk-1為第k-1時刻系統(tǒng)的過程的平穩(wěn)噪聲序列；fk為系統(tǒng)狀態(tài)轉(zhuǎn)移函數(shù)，是狀態(tài)xk-1的非線性(或線性)函數(shù)。下面為系統(tǒng)的觀測方程，zk為系統(tǒng)的觀測向量；vk為觀測的平穩(wěn)噪聲序列；hk為系統(tǒng)觀測函數(shù)，是狀態(tài)xk的非線性(或線性)函數(shù)。

從式(1)可以看出，狀態(tài)轉(zhuǎn)移函數(shù)和觀測函數(shù)沒有做出線性或非線性的假設條件，過程噪聲和觀測噪聲也沒有假設為高斯白噪聲序列。本文將在以下章節(jié)分別對擴展卡爾曼濾波和粒子濾波對模型的處理過程進行總結(jié)。

2. 擴展卡爾曼濾波模型與算法

(2)

式中

(3)

再根據(jù)傳統(tǒng)的卡爾曼濾波理論，可得到擴展卡爾曼濾波算法遞推公式

(4)

擴展卡爾曼濾波實際上是利用上一時刻的狀態(tài)估計值來預測當前時刻的狀態(tài)，利用觀測值進行修正。其算法簡單，計算量小，易于在計算機上進行模擬試驗。但由于擴展卡爾曼濾波使用了泰勒級數(shù)展開，只保留了一次項，因此該算法得到的結(jié)果并不是最優(yōu)估計，總會存在著一些系統(tǒng)誤差，并且更新方程和觀測方程的非線性越強，圖像彎曲程度越大，預測結(jié)果的誤差就會越大。另外，隨機模型的構(gòu)建也非常關(guān)鍵，如果構(gòu)建的隨機模型與準確性較差會直接影響濾波結(jié)果的質(zhì)量。

3. 粒子濾波的模型與算法

粒子濾波算法是一種基于貝葉斯采樣估計的序貫重要性采樣濾波方法，其核心是用一組帶有權(quán)值的隨機樣本來近似表征后驗概率密度函數(shù)，從而求得狀態(tài)的最小方差估計[5-7]。

狀態(tài)預測方程

(5)

狀態(tài)更新方程

(6)

式中

(7)

然而該過程計算非常復雜，特別是式中存在的積分運算，使得該過程難以實現(xiàn)。1993年，Gordon和Salmond提出基于序貫重要性采樣(SIS)思想的自舉濾波算法，借助蒙特卡洛方法，將積分運算離散化，轉(zhuǎn)變?yōu)閷?quán)樣本求和的運算過程[2,9]。

那么狀態(tài)的后驗期望為

(8)

但隨著時間的增加，大多數(shù)粒子的權(quán)值逐漸減小并趨于零，這就會出現(xiàn)粒子退化問題，即重要性權(quán)值會集中在極少數(shù)的粒子上，僅靠這些粒子難以有效表達出后驗概率密度函數(shù)，而權(quán)值小的粒子經(jīng)過同樣復雜的計算過程，其對計算結(jié)果的影響微乎其微，甚至可以忽略不計。為了解決這個問題，Gordon等提出了重采樣方法。目前常用的處理方式是計算有效粒子數(shù)Neff，定義為

(9)

如果Neff

粒子濾波實質(zhì)上是將連續(xù)的概率密度函數(shù)離散化，通過計算離散樣本的加權(quán)和來近似計算狀態(tài)后驗估計值的過程。粒子濾波的優(yōu)點在于它可以適用于任何系統(tǒng)，并沒有線性或高斯分布的前提條件，精度與模型和分布也無關(guān)。因此與擴展卡爾曼濾波相比，粒子濾波的適應性、可靠性更強，精度更均勻。但是粒子濾波的數(shù)學過程比較復雜，計算困難，并且算法的精度與所選取的重要性函數(shù)和粒子數(shù)量有關(guān)。故粒子濾波在近年來計算機技術(shù)迅速發(fā)展的時代才得到一些實際應用。

二、擴展卡爾曼濾波和粒子濾波仿真試驗與性能對比

設有如下非線性模型

(10)

式中，wk和vk為零均值高斯白噪聲，方差分別為10.0和1.0。該狀態(tài)更新方程和觀測方程都是高度非線性的，下面分別使用擴展卡爾曼濾波和粒子濾波算法對該模型進行50步估計，并從計算精度和速度方面對兩種方法的性能進行比較。

1. 計算精度的比較

試驗選用最新版Matlab軟件(Matlab 2014a)進行模擬，取初值x0=0.1，粒子數(shù)N=500。圖1為擴展卡爾曼濾波和粒子濾波估計結(jié)果，狀態(tài)真實值大概介于-20～+20之間。從圖中可以看出，粒子濾波的估計結(jié)果與真實值更為接近，除了少數(shù)幾個偏差較大的點，絕大多數(shù)估計值都很接近真實值，而擴展卡爾曼濾波在很多時刻都會出現(xiàn)偏離真實值較大的情況，并且偏離的幅度也比粒子濾波大得多。為了更直觀地顯示出二者的差異繪制了擴展卡爾曼濾波和粒子濾波的估計結(jié)果與真實值的誤差折線圖，如圖2所示?？梢钥闯?，粒子濾波計算結(jié)果的誤差大小和方差明顯優(yōu)于擴展卡爾曼濾波。在系統(tǒng)非線性較強的時刻，擴展卡爾曼濾波算法得到的結(jié)果誤差大小能達到粒子濾波誤差的幾倍甚至十幾倍。

圖1　擴展卡爾曼濾波與粒子濾波估計結(jié)果

圖2　擴展卡爾曼濾波與粒子濾波估計值與真實值的差

為了使試驗結(jié)果更有說服性，筆者用Visual C++語言進行了同樣的仿真過程，使用的編譯器為微軟發(fā)布的Visual Studio 2010，設置同樣的初始條件，將計算結(jié)果導入到數(shù)據(jù)文件中，再借助Matlab繪圖功能繪出狀態(tài)估計折線圖(如圖3所示)和誤差折線圖(如圖4所示)，可以得到與Matlab仿真類似的結(jié)果?？梢钥闯?，在高度非線性的系統(tǒng)中，粒子濾波算法的精度和穩(wěn)定性明顯優(yōu)于擴展卡爾曼濾波。

2. 計算速度對比

將擴展卡爾曼濾波與粒子濾波的仿真代碼用兩個腳本分別實現(xiàn)，運行并計時，比較二者的計算時間。筆者使用的計算機CPU型號為Intel Core i5雙核處理器，主頻2.60 GHz，內(nèi)存大小為8 GB，Windows 8操作系統(tǒng)。將擴展卡爾曼濾波和粒子濾波仿真代碼分別運行10次，并記下每次運行的時間。粒子數(shù)不是很多時，VC++運行兩種算法時間差別不大，而Matlab運行時間差異比較明顯，見表1。

圖3　用VC++實現(xiàn)的狀態(tài)估計結(jié)果

圖4　用VC++實現(xiàn)的計算結(jié)果誤差

s

進行同樣的50步估計過程，卡爾曼濾波只需將每一步的結(jié)果進行迭代計算來得到下一步的先驗預測，再用觀測值進行修正即可；而粒子濾波需要將每一步的每個粒子進行迭代計算，并進行重采樣，最后將所有的粒子取加權(quán)和得到最終結(jié)果，實際上每一個粒子的計算過程相當于一個小的卡爾曼濾波過程，粒子濾波的計算量遠遠大于擴展卡爾曼濾波。因此，粒子濾波計算用的時間與擴展卡爾曼濾波有著比較明顯的差距。

從粒子濾波的運算過程中可以看出，粒子濾波的計算量與所采樣的粒子數(shù)量密切相關(guān)。筆者統(tǒng)計了仿真試驗過程中粒子數(shù)量對粒子濾波程序運行時間的影響，見表2。

表2　粒子濾波不同粒子數(shù)運算時間統(tǒng)計　s

可見，采樣的粒子數(shù)量對粒子濾波運算速度的影響是十分顯著的。當粒子數(shù)較少時(如100或200)可以較快地得到計算結(jié)果，Matlab仿真模擬可以在1 s內(nèi)完成計算和繪圖工作，VC++計算時間幾乎看不出有差異；隨著粒子數(shù)的逐漸增長，Matlab程序和VC++程序的運行時間都會有比較明顯的增加；當粒子數(shù)達到5000時，Matlab程序的計算時間能達到近3 min，VC++程序運算時間也達到了幾秒。圖5和圖6分別顯示了Matlab程序和VC++程序計算時間隨粒子數(shù)的變化趨勢，可見程序計算時間與粒子數(shù)量并不是呈線性變化的，而是呈近似拋物線的變化趨勢。

圖5　Matlab程序計算時間隨粒子數(shù)的變化

圖6　VC++程序計算時間隨粒子數(shù)的變化

針對以上試驗結(jié)論，筆者另外選取了一組非線性模型進行了驗證。系統(tǒng)模型[17]為

對該系統(tǒng)進行同樣過程的模擬試驗，濾波結(jié)果對比、誤差對比及粒子濾波時間變化等得到與上述仿真試驗相似的結(jié)果(如圖7—圖9所示)，由此可以驗證上述結(jié)論。

圖7　兩種濾波算法估計結(jié)果對比

圖8　兩種濾波算法結(jié)果誤差對比

然而在實際工程應用中，系統(tǒng)模型是極其復雜的，并且絕大多數(shù)系統(tǒng)是多維的，狀態(tài)量和觀測量都是多維向量，為了使最后計算結(jié)果達到精度和穩(wěn)定性等方面的要求，通常需要采集幾萬個粒子來計算，其計算量是非常龐大的，特別是在需要實時計算數(shù)據(jù)的領(lǐng)域，如組合導航、目標跟蹤等，普通計算機的計算速度是遠遠達不到要求的，因此粒子濾波的實用性就降低了很多。有學者提出了很多相關(guān)的改進算法來改進粒子濾波的計算精度和速度，如Freitas等提出擴展卡爾曼粒子濾波算法的思想[9,12]，Merwe等提出無味粒子濾波算法[13]，Pitt等提出輔助粒子濾波算法[14]，蔣蔚博士等提出了支持向量機概率密度估計粒子濾波和支持向量回歸機粒子濾波等方法[15-16]。這些方法都在一定程度上改善了粒子濾波的性能和精度，但仍然沒有使粒子濾波廣泛地應用于實時計算的領(lǐng)域。

圖9　Matlab程序計算時間隨粒子數(shù)的變化

三、結(jié)束語

粒子濾波具有不受系統(tǒng)模型的限制、對被估計狀態(tài)的后驗分布不做任何假設及在非線性系統(tǒng)濾波中精度均勻、穩(wěn)定性好等特性，因此具有其他估計方法不具備的優(yōu)勢，但因其計算過程中重要性采樣、粒子退化和計算量等問題導致其實現(xiàn)起來比較困難、實時性差，因此粒子濾波的適用領(lǐng)域非常有限。試驗表明，同樣的非線性動態(tài)系統(tǒng)，粒子濾波的精度和穩(wěn)定性優(yōu)于擴展卡爾曼濾波，但其運行消耗的時間要遠遠大于擴展卡爾曼濾波；并且，粒子濾波的運行時間隨粒子數(shù)量的增加呈近似拋物線增長，粒子數(shù)越多，消耗的時間增加越快。

目前大部分領(lǐng)域在非線性濾波中都還使用算法簡單、計算方便的擴展卡爾曼濾波方法，然而隨著各領(lǐng)域?qū)V波計算精度和穩(wěn)定性等方面的要求越來越高，粒子濾波算法將會逐漸改進和完善，并將應用于各種科研和工程領(lǐng)域中。

參考文獻：

[1]趙琳, 王小旭, 丁繼成，等. 組合導航系統(tǒng)非線性濾波算法綜述[J]. 中國慣性技術(shù)學報, 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].哈爾濱：哈爾濱工業(yè)大學, 2010.

[17]杜航原, 郝燕玲, 趙玉新. 基于集合卡爾曼濾波的改進粒子濾波算法[J]. 系統(tǒng)工程與電子技術(shù), 2011, 33(7): 1653-1657.

中圖分類號：P228

文獻標識碼：B

文章編號：0494-0911(2016)04-0010-05

通信作者：聶桂根

作者簡介：薛長虎(1992—)，男，碩士生，主要研究方向為多源觀測數(shù)據(jù)與滑坡機理模型同化理論與方法。E-mail：xch073423@163.com

基金項目：國家重點基礎研究發(fā)展計劃(2013CB733205)

收稿日期：2015-05-29

引文格式： 薛長虎，聶桂根，汪晶. 擴展卡爾曼濾波與粒子濾波性能對比[J].測繪通報，2016(4)：10-14.DOI:10.13474/j.cnki.11-2246.2016.0111.