李善姬，禹愛蘭

（延邊大學(xué)工學(xué)院，吉林延吉133002）

一種改進(jìn)重采樣的粒子濾波算法?

李善姬，禹愛蘭

（延邊大學(xué)工學(xué)院，吉林延吉133002）

粒子濾波算法中重采樣是解決粒子退化的一種重要方法，但重采樣會導(dǎo)致粒子多樣性的損失。針對這一問題，對基本重采樣算法進(jìn)行了改進(jìn)。改進(jìn)算法首先按基本重采樣思想找到權(quán)值大的粒子進(jìn)行復(fù)制，然后借鑒遺傳算法進(jìn)行交叉和變異操作，其中變異由變異尺度因子和粒子集的均值來實現(xiàn)。利用改進(jìn)重采樣的粒子濾波算法對經(jīng)典純方位目標(biāo)跟蹤問題進(jìn)行了仿真，仿真結(jié)果表明，改進(jìn)算法具有更好的跟蹤精度。

目標(biāo)跟蹤；粒子濾波；重采樣；遺傳算法

1 引言

粒子濾波器（Particle Filter）利用一些隨機(jī)樣本（粒子）來表示系統(tǒng)隨機(jī)變量的后驗概率分布，它不依賴于系統(tǒng)模型或觀測方程的線性程度和狀態(tài)的分布，克服了以往基于線性高斯濾波方法的缺點，適用于難以進(jìn)行線性化、難以高斯近似處理以及處理后性能較差的情況。粒子濾波以其突出的優(yōu)點成為當(dāng)前非線性估計領(lǐng)域的一個熱門研究方向，并得到了廣泛的應(yīng)用［1-3］。在粒子濾波器中，普遍存在的一個問題是粒子退化問題，即經(jīng)過幾次迭代之后，很多粒子的權(quán)值變得很小甚至接近于零，這些小權(quán)值粒子在重要度更新的時候雖然還要參與計算，但是對整個系統(tǒng)的貢獻(xiàn)很小，基本上屬于無用的粒子，這樣不僅要浪費大量的計算資源，同時也容易造成跟蹤精度降低甚至可能會丟失目標(biāo)。粒子重采樣是解決粒子退化的一種重要方法，常用的重采樣算法有多項式重采樣、殘差重采樣、分層重采樣、系統(tǒng)重采樣等。這些算法通過增加粒子的有效性解決了粒子退化問題。重采樣后，重要度高的粒子通過重采樣被多次選取，這在一定程度上損失了粒子的多樣性，即所謂的粒子枯竭，會導(dǎo)致濾波性能下降。針對這一問題，有不少關(guān)于將遺傳機(jī)制引入到重采樣過程中的研究［4，5］。本文在改進(jìn)重采樣算法時，在基本重采樣的基礎(chǔ)上借鑒遺傳算法中的交叉和變異操作，通過對粒子進(jìn)行重組和變異，保證了粒子的多樣性。利用改進(jìn)算法對純方位跟蹤問題進(jìn)行了仿真，結(jié)果表明了算法的有效性。

2 改進(jìn)重采樣的粒子濾波算法

2.1 粒子濾波及其存在的主要問題

粒子濾波是一種基于蒙特卡羅方法的貝葉斯?fàn)顟B(tài)估計算法，其中狀態(tài)的后驗概率密度p（xk｜z1：k）由一組具有權(quán)值的粒子

來近似。每一時刻從提議分布q（xik｜xik-1，z1：k）中采樣新的粒子xik，并根據(jù)觀測密度和貝葉斯規(guī)則計算新的權(quán)值wik，將權(quán)值歸一化之后，k時刻的后驗概率密度可以由一組新的粒子｛(xik，wik)，i=1，2，…，N｝來表達(dá)。

基本粒子濾波算法如下。

步驟1：初始化

k=0時刻，從初始的先驗分布p（x0）采樣N個初始粒子xi0（i=1，…，N）。

步驟2：狀態(tài)更新

（1）k時刻采樣粒子集xik～q（xik｜xi

k-1，z1：k）

（2）計算權(quán)值

（3）歸一化權(quán)值

步驟3：重采樣

從粒子集{xik}中根據(jù)權(quán)值{?wik}重新采樣得到新的N個粒子集{?xik}，并重新分配粒子權(quán)值wik= ?wik=1／N。

步驟5：k=k+1，返回步驟2。

在基本粒子濾波算法中，普遍存在的一個問題是粒子退化問題，即經(jīng)過幾次迭代之后，差不多所有粒子的權(quán)值都趨于零。已經(jīng)證明，重要性權(quán)值的方差隨著時間遞增而增大，所以要完全消除退化現(xiàn)象是不可能的。粒子退化意味著大量的計算都用來更新粒子，而這些粒子對逼近后驗概率密度p（xk｜z1：k）的貢獻(xiàn)幾乎為零。通過重采樣后得到新的粒子和權(quán)值，可以有效地防止退化問題，但同時帶來的另一個問題是會引起粒子的枯竭，也就是權(quán)值較小的粒子被去除，而權(quán)值較高的粒子被多次采樣，這將導(dǎo)致采樣結(jié)果中包含許多重復(fù)的粒子，會損失掉粒子的多樣性，使得濾波性能下降。特別是在樣本受限的條件下，粒子枯竭現(xiàn)象對于濾波精度的影響更為明顯，甚至可能會導(dǎo)致濾波發(fā)散現(xiàn)象。

2.2 改進(jìn)的重采樣算法

為了改善重采樣帶來的粒子多樣性損失，有不少研究是將遺傳算法引入到粒子濾波的重采樣過程中。文獻(xiàn)［4］的遺傳重采樣粒子濾波器是首先對狀態(tài)進(jìn)行二進(jìn)制編碼，然后再按照設(shè)定的選擇、交叉、變異概率對于粒子集依次進(jìn)行相應(yīng)的算子計算，最后對粒子集進(jìn)行二進(jìn)制解碼后得到最終的重采樣粒子集。文獻(xiàn)［5］的遺傳重采樣是采用十進(jìn)制對粒子進(jìn)行編碼，遺傳過程首先進(jìn)行選擇操作，然后對被選擇保留下來的個體點進(jìn)行兩兩配對，按照一定概率進(jìn)行交叉操作，最后根據(jù)某個概率，對個體進(jìn)行十進(jìn)制變異操作。本文在改進(jìn)重采樣算法時，借鑒遺傳算法中交叉和變異的概念，在基本重采樣的基礎(chǔ)上對算法進(jìn)行了改進(jìn)。首先按基本重采樣思想找到權(quán)值較大的粒子進(jìn)行復(fù)制，然后按照某一交叉概率pc隨機(jī)選擇兩個粒子按照下面的公式進(jìn)行交叉：

上述交叉算法只是形式上解決了粒子枯竭問題，因為盡管所有粒子是不同的，但經(jīng)過多次迭代后，它們將會非常接近，這對粒子的多樣性是不利的。借鑒遺傳算法中變異的概念在某一變異概率pm下再進(jìn)行如下變異操作：

式中，a為變異尺度因子，b取粒子集x{}ik的均值。

上述借鑒遺傳操作的改進(jìn)重采樣算法描述如下：（1）按基本重采樣方法根據(jù)權(quán)值?wik利用輪盤賭的方法選擇N個粒子x{} ik；

（2）按交叉概率pc，根據(jù)式（4）進(jìn)行交叉操作，得到交叉后的粒子集{xik}c；

（3）按變異概率pm，根據(jù)式（5）進(jìn)行變異操作，得到變異后的粒子集{xik}m。

完成上述步驟的重采樣后，重新計算權(quán)值并歸一化。

3 仿真結(jié)果及分析

純方位目標(biāo)跟蹤在許多領(lǐng)域尤其是軍事領(lǐng)域（航空、航海、水下）具有非常廣泛的應(yīng)用，其基本問題是根據(jù)受到噪聲污染的傳感器方位數(shù)據(jù)來估計目標(biāo)的軌跡（即位置和速度）。純方位跟蹤是一類典型的目標(biāo)運動分析問題，可以使用非線性狀態(tài)空間模型來描述，由于它具有可觀測性較弱的特點，通常是一個非線性估計問題。有關(guān)基于粒子濾波的純方位目標(biāo)跟蹤研究［6，7］也有不少。

下面利用本文提出的改進(jìn)重采樣的粒子濾波算法對經(jīng)典的純方位跟蹤問題進(jìn)行仿真，并將仿真結(jié)果與基本粒子濾波算法進(jìn)行比較。

假設(shè)目標(biāo)在x-y平面的運動方程為

Xk=[x，x˙，y，y˙]Tk表示目標(biāo)k時刻的狀態(tài)向量，uk=[ux，uy]Tk是系統(tǒng)噪聲。x和y代表目標(biāo)的位置，x˙和y˙代表目標(biāo)的速度。系統(tǒng)噪聲uk是零均值的高斯白噪聲，協(xié)方差為

觀測噪聲vk也是零均值的高斯白噪聲，方差為r= 0.0052。目標(biāo)初始狀態(tài)為

初始方差為

式中，σ1=0.001，σ2=0.002，σ3=0.002，σ4=0.001。仿真的時間步長為25，粒子數(shù)為100。為了定量比較算法性能，定義一次獨立實驗的均方根誤差為

式中，T表示一次實驗的時間步長，x＾k表示k時刻的估計值，xk表示k時刻的真實值。

圖1為單次實驗?zāi)繕?biāo)真實軌跡與基本重采樣粒子濾波器跟蹤結(jié)果，圖2為單次實驗?zāi)繕?biāo)真實軌跡與改進(jìn)粒子濾波器（本文算法）跟蹤結(jié)果。

圖1 目標(biāo)真實軌跡與PF跟蹤軌跡Fig.1 Real target trajectory and PF tracking trajectory

圖2 目標(biāo)真實軌跡與改進(jìn)PF跟蹤軌跡Fig.2 Real target trajectory and improved PF tracking trajectory

表1表示20次獨立實驗后，兩種（基本重采樣和改進(jìn)重采樣）PF算法的x坐標(biāo)和y坐標(biāo)的均方根誤差平均值。

表1 x、y坐標(biāo)的MSETable 1 The MSE of x and y axis

從仿真結(jié)果可看出，采用改進(jìn)重采樣算法的PF跟蹤結(jié)果在x坐標(biāo)和y坐標(biāo)上都具有更小的誤差和更好的跟蹤精度，說明了改進(jìn)算法的有效性。雖然遺傳代數(shù)不需要取較大的值，但是當(dāng)粒子數(shù)增加時，改進(jìn)算法的運算量和運算時間會有所增加。

4 結(jié)束語

本文對粒子濾波重采樣算法進(jìn)行了改進(jìn)，在基本重采樣算法的基礎(chǔ)上，借鑒遺傳算法中交叉和變異的概念對粒子進(jìn)行重組和變異，改善了重采樣帶來的粒子多樣性的損失。利用改進(jìn)算法在MATLAB環(huán)境下對經(jīng)典的純方位跟蹤問題進(jìn)行了仿真，仿真結(jié)果說明利用改進(jìn)算法的粒子濾波器具有較好的跟蹤性能，但同時運算量也有所增加。

［1］Hue C，Cadre L.Sequential Monte Carlomethods formultiple target tracking and data fusion［J］.IEEE Transactions on Signal Processing，2002，50（2）：309-325.

［2］Arulampalam S，Maskell S，Gordon N，eta1.A tutorialon particle filters for on-line non-linear／non-Gaussian Bayesian tracking［J］.IEEE Transactions on Signal Processing，2002，50（2）：174-188.

［3］李勇，汪立新，鄭海偉.一種改進(jìn)的粒子濾波算法［J］.電訊技術(shù)，2009，49（1）：50-53. LIYong，WANG Li-xin，ZHENG Hai-wei.An Improved Particle Filter Algorithm［J］.Telecommunication Engineering，2009，49（1）：50-53.（in Chinese）

［4］葉龍，王京玲，張勤.遺傳重采樣粒子濾波器［J］.自動化學(xué)報，2007，33（8）：885-887. YE Long，WANG Jing-ling，ZHANG Qin.Genetic Resampling Particle Filter［J］.Acta Automatica Sinica，2007，33（8）：885-887.（in Chinese）

［5］劉剛，梁曉庚.遺傳重采樣粒子濾波的目標(biāo)跟蹤研究［J］.計算機(jī)工程與應(yīng)用，2010，46（19）：196-199. LIU Gang，LIANG Xiao-geng.Research on target tracking based on Gene Algorithm′s Resampling Particle Filter［J］. Computer Engineering and Applications，2010，46（19）：196-199.（in Chinese）

［6］匡興紅，邵惠鶴.改進(jìn)的SRCDKF-PF算法及在BOT系統(tǒng)中的應(yīng)用［J］.系統(tǒng)仿真學(xué)報，2008，20（6）：1508-1510，1514. KUANG Xing-hong，SHAO Hui-he.Application of Improved SRCDKF-PF for BOT System［J］.Journal of System Simulation，2008，20（6）：1508-1510，1514.（in Chinese）

［7］馮馳，呂曉鳳，汲清波.粒子濾波理論及其在目標(biāo)跟蹤中的應(yīng)用［J］.計算機(jī)工程與應(yīng)用，2008，44（6）：246-248. FENGChi，LV Xiao-feng，JIQing-bo.Particle filtering theory and its application in target tracking［J］.Computer Engineering and Applications，2008，44（6）：246-248.（in Chinese）

LIShan-jiwas born in Yanji，Jilin Province，in 1959.She received the M.S.degree in 1997.She is now a professor and also the instructor of graduate students.Her research direction is signal and information processing.

Email：lishanji＠ybu.edu.cn

禹愛蘭（1988—），女（朝鮮族），吉林松原人，2010年獲學(xué)士學(xué)位，現(xiàn)為碩士研究生，主要研究方向為數(shù)字信號處理。

YU Ai-lan was born in Songyuan，Jilin Province，in 1988.She received the B.S.degree in 2010.She is now a graduate student. Her research direction is digital signal proc essing.

關(guān)于本刊編輯部授權(quán)中國知網(wǎng)優(yōu)先數(shù)字出版的通知

根據(jù)期刊出版業(yè)態(tài)創(chuàng)新的需要，為了尋找新的發(fā)展空間和經(jīng)營模式，爭取成果首發(fā)權(quán)，提高期刊的國際競爭力，本刊編輯部已授權(quán)中國知網(wǎng)（www.cnki.net）對本刊所錄用稿件優(yōu)先數(shù)字出版。作者投稿時需按本刊網(wǎng)站“相關(guān)下載”欄目中“《電訊技術(shù)》數(shù)字優(yōu)先出版論文模板.doc”格式進(jìn)行排版。

謝謝支持與合作！讓我們?yōu)椤峨娪嵓夹g(shù)》的發(fā)展而共同努力、攜手共進(jìn)！

《電訊技術(shù)》編輯部

An Im proved Resam pling Particle Filtering Algorithm

LIShan-ji，YU Ai-lan
（College of Engineering，Yanbian University，Yanji133002，China）

Resampling is an importantmethod to solve particle degradation in particle filtering（PF）algorithm. But resamplingwill lead to the loss of particle diversity.To solve this problem，the basic resampling algorithm is improved.The improved algorithm first findsweights to copy large particles according to the basic thinking of resampling，and then uses the genetic algorithm（GA）to cross and variate.The variation is realized by scale variation factor and themean of particle sets.The problem of classical Bearing-only target tracking is simulated with the improved resampling particle filter algorithm.Simulation results show that the improved algorithm has better tracking precision.

target tracking；particle filtering；resampling；genetic algorithm

TP391

A

10.3969／j.issn.1001-893x.2011.09.007

李善姬（1959—），女（朝鮮族），吉林延吉人，1997年獲碩士學(xué)位，現(xiàn)為教授、碩士生導(dǎo)師，主要研究方向為信號與信息處理；

1001-893X（2011）09-0035-04

2011-04-11；

2011-06-02