粒子濾波算法改進及其應用研究

王永翔　陳國初

摘 要： 粒子濾波算法是一種基于貝葉斯估計和非參數化蒙特卡羅模擬的新型算法。詳細介紹了粒子濾波算法的基本原理，闡述了遞推貝葉斯估計方法、序貫重要性采樣以及序貫重要性重采樣算法；分析了粒子濾波主要存在的問題及關鍵改進之處，然后介紹粒子濾波算法的應用，并對算法未來發展進行了展望。

關鍵詞： 貝葉斯估計； 序貫重要性采樣； 重采樣； 粒子濾波

中圖分類號：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