黃莉靜，于乃文，王敬濤

（1.河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018；2.河北科技大學(xué)理工學(xué)院，河北石家莊 050018；3.石家莊學(xué)院計(jì)算機(jī)系，河北石家莊 050035）

基于均值遷移的粒子濾波算法研究

黃莉靜1，于乃文2，王敬濤3

（1.河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018；2.河北科技大學(xué)理工學(xué)院，河北石家莊 050018；3.石家莊學(xué)院計(jì)算機(jī)系，河北石家莊 050035）

針對(duì)弱觀測(cè)噪聲環(huán)境下的粒子退化現(xiàn)象，特別是觀測(cè)噪聲較小時(shí)非線性非高斯的粒子濾波問題，提出了一種基于均值遷移的粒子濾波算法。首先，將核密度估計(jì)的無(wú)參快速模式匹配算法引入到粒子濾波中，并迭代計(jì)算概率密度估計(jì)。然后，利用均值遷移估計(jì)粒子梯度的方向，計(jì)算每個(gè)粒子移向其樣本的均值。當(dāng)粒子位置發(fā)生改變時(shí)，對(duì)重采樣粒子進(jìn)行加權(quán)處理。最后，根據(jù)本算法采樣更新粒子集，有效地克服了粒子退化現(xiàn)象并提高了狀態(tài)估計(jì)精度。

后驗(yàn)分布；密度估計(jì)；均值遷移；加權(quán)值；粒子濾波

黃莉靜，于乃文，王敬濤.基于均值遷移的粒子濾波算法研究［J］.河北科技大學(xué)學(xué)報(bào)，2014，35（2）：184-188.

HUANG Lijing，YU Naiwen，WANG Jingtao.Particle filter algorithm based on mean-shift［J］.Journal of Hebei University of Science and Technology，2014，35（2）：184-188.

粒子濾波是一種基于蒙特卡洛方法和遞推貝葉斯估計(jì)的統(tǒng)計(jì)濾波方法［1－3］，根據(jù)大數(shù)定理采用蒙特卡洛的方法來(lái)求解貝葉斯估計(jì)中的積分運(yùn)算，國(guó)內(nèi)外已經(jīng)取得了一定的進(jìn)展。文獻(xiàn)［4］提出了似然粒子濾波（LPF），它使用似然函數(shù)作為建議分布，考慮了最新觀測(cè)信息，而且保證大部分的粒子位于高似然區(qū)，從而提高了粒子的利用效率，使得狀態(tài)估計(jì)更加準(zhǔn)確。文獻(xiàn)［5］利用卡爾曼粒子濾波來(lái)產(chǎn)生建議分布。文獻(xiàn)［6］提出自適應(yīng)粒子群優(yōu)化的新型粒子濾波算法，該方法實(shí)現(xiàn)簡(jiǎn)單，但是對(duì)于最新粒子的觀測(cè)值卻容易偏離真實(shí)的后驗(yàn)概率。上述文獻(xiàn)中的粒子濾波均存在一個(gè)主要問題是粒子的退化現(xiàn)象，尤其是當(dāng)觀測(cè)噪聲較小并且似然粒子濾波形狀尖銳時(shí)，粒子的退化現(xiàn)象比較嚴(yán)重。

針對(duì)粒子退化現(xiàn)象的常用解決方法是對(duì)粒子進(jìn)行重采樣，但是經(jīng)過重采樣之后，權(quán)值大的粒子會(huì)被多次復(fù)制，導(dǎo)致粒子集失去多樣性，出現(xiàn)樣本枯竭現(xiàn)象。針對(duì)這一問題文獻(xiàn)［7］提出高斯粒子濾波算法，利用高斯分布近似于狀態(tài)后驗(yàn)概率密度這一特點(diǎn)進(jìn)行高斯化的粒子濾波，當(dāng)高斯假設(shè)成立時(shí)該算法是漸進(jìn)的最優(yōu)。文獻(xiàn)［8］提出了粒子濾波與均值漂移相結(jié)合的算法，該算法從后驗(yàn)分布的連續(xù)近似中重采樣來(lái)更新粒子集，從而增加粒子的多樣性。文獻(xiàn)［9］在似然粒子濾波的基礎(chǔ)上提出了正則似然粒子濾波（R-LPF）算法，通過構(gòu)建狀態(tài)的連續(xù)后驗(yàn)概率密度來(lái)獲得新的樣本粒子。

本研究針對(duì)弱觀測(cè)噪聲條件下的非線性非高斯的動(dòng)態(tài)系統(tǒng)的濾波問題，提出了基于加權(quán)均值遷移的粒子濾波算法。該算法首先將核K－密度估計(jì)的無(wú)參快速模式匹配算法引入到粒子濾波中，并迭代計(jì)算概率密度估計(jì)。然后利用均值遷移估計(jì)粒子梯度的方向，計(jì)算每個(gè)粒子移向其樣本的均值，當(dāng)粒子位置發(fā)生改變時(shí)，對(duì)粒子采樣進(jìn)行加權(quán)處理。實(shí)驗(yàn)證明了本算法的可行性和有效性。

1 傳統(tǒng)粒子濾波算法

1.1 重要密度函數(shù)

1.2 粒子濾波算法

粒子濾波算法選擇最易于實(shí)現(xiàn)的先驗(yàn)概率密度作為重要密度函數(shù)，即

將式（7）代入到式（6），則可將重要性權(quán)值可簡(jiǎn)化為

將權(quán)值做歸一化處理可得

則后驗(yàn)概率密度可表示為

當(dāng)Ns→＋∞，有大數(shù)定理可以保證式（10）的后驗(yàn)概率密度逼近與真實(shí)的后驗(yàn)概率密度p（xk｜z1：k）。

綜上所述，粒子濾波算法表述如下。

1）粒子初始化：有先驗(yàn)概率p（x0）產(chǎn)生粒子群集，所有粒子權(quán)值為

2）權(quán)值更新：在時(shí)刻k，對(duì)粒子權(quán)值進(jìn)行更新，更新結(jié)果為

3）重采樣：重新得到新的粒子集合｛xi＊0：k，i＝0，1，2，…，Ns｝；

4）結(jié)果輸出：在時(shí)刻k，未知參數(shù)x的最小均方估計(jì)為

5）狀態(tài)預(yù)測(cè)：利用方程預(yù)測(cè)未知參數(shù)xik＋1；

6）在下一個(gè)時(shí)刻k＝k＋1時(shí)，轉(zhuǎn)到第2）步循環(huán)執(zhí)行，直到結(jié)束為止。

2 對(duì)傳統(tǒng)粒子濾波算法分析

當(dāng)重要性函數(shù)近似接近于后驗(yàn)概率分布時(shí)，則可以用重要性函數(shù)代替后驗(yàn)概率分布作為采樣函數(shù)，但是此時(shí)要求重要性函數(shù)的方差基本為0，即

由于傳統(tǒng)的粒子濾波算法選擇先驗(yàn)概率作為重要性密度函數(shù)，如果是在量測(cè)精度要求低的場(chǎng)合，這種選取方法能夠獲得較好的結(jié)果。但是對(duì)于量測(cè)精度要求高的場(chǎng)合，由于在進(jìn)行更新時(shí)沒有考慮當(dāng)前觀測(cè)值，使得從重要性概率密度中取樣得到的樣本與從真實(shí)后驗(yàn)概率密度采樣得到的樣本有較大偏差，尤其是當(dāng)似然函數(shù)位于系統(tǒng)狀態(tài)轉(zhuǎn)移概率密度的尾部或似然函數(shù)程尖峰狀態(tài)時(shí)，這種偏差更加明顯。

3 均值遷移粒子濾波算法

3.1 核K－ 密度估計(jì)

3.2 加權(quán)粒子均值遷移

本研究的均值遷移是將核K－密度估計(jì)的無(wú)參快速模式匹配算法，引入到粒子濾波中的一種迭代計(jì)算概率密度估計(jì)的方法。

利用均值遷移估計(jì)粒子梯度的方向，通過式（18）計(jì)算每個(gè)粒子移向其樣本的均值：

其中H是任意的核K值。

在均值遷移算法中，需要對(duì)每個(gè)粒子重復(fù)使用，但是當(dāng)粒子位置發(fā)生改變時(shí)，新采樣粒子并不流向后驗(yàn)分布，因此本研究對(duì)粒子采用加權(quán)處理的方法。

設(shè)在k時(shí)刻粒子第i次均值遷移后的粒子集合為｛S（n）k，i｝，利用式（19）中的粒子概率密度平衡系數(shù)估算新粒子位置：

4 實(shí)驗(yàn)仿真

其中：vk為系統(tǒng)過程噪聲，服從Gamma分布；nk為弱觀測(cè)噪聲。

為了驗(yàn)證算法的有效性和準(zhǔn)確性，實(shí)驗(yàn)選取具有代表性的標(biāo)準(zhǔn)測(cè)試視頻序列進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)平臺(tái)為Pentium 4，2.53 GHz的CPU，2GB內(nèi)存的PC機(jī)，編程環(huán)境是采用Matlab R2009a實(shí)現(xiàn)，粒子數(shù)為60。

本研究實(shí)驗(yàn)分別使用傳統(tǒng)粒子濾波（PF）、似然粒子濾波（LPF）、正則似然粒子濾波（R-LPF）以及本研究提到的加權(quán)均值遷移粒子濾波4種粒子濾波算法進(jìn)行比較實(shí)驗(yàn)中迭代步長(zhǎng)為T＝60。重采樣閾值為Nth＝N／5。

由圖1可以看出，本研究算法的估計(jì)效果優(yōu)于標(biāo)準(zhǔn)粒子濾波，更接近于實(shí)際狀態(tài)值。

為了更進(jìn)一步的驗(yàn)證本研究算法的有效性，進(jìn)行100次蒙特卡羅仿真實(shí)驗(yàn)，對(duì)各種算法計(jì)算粒子狀態(tài)的

本研究以弱觀測(cè)動(dòng)態(tài)模型作為實(shí)驗(yàn)對(duì)象，系統(tǒng)狀態(tài)轉(zhuǎn)移方程和觀測(cè)方程為均方根誤差（RMSE），圖2中所示為各個(gè)算法的均方根誤差的曲線圖。

圖1 不同算法狀態(tài)估計(jì)值Fig.1 State estimation of different algorithm

圖2 不同算法的RMSEFig.2 RMSE of different algorithm

不同算法估計(jì)結(jié)果的RMSE均值、方差及各算法平均運(yùn)行時(shí)間如表1所示。

由表1可以看出，本研究算法的均方根誤差和方差較其他3種算法更小，經(jīng)過圖2的100次仿真得到的很小的RMSE均值也驗(yàn)證了本文算法的收斂性，運(yùn)行時(shí)間與R-LPF算法相比時(shí)間復(fù)雜度更低。

表1 不同算法的狀態(tài)估計(jì)比較結(jié)果Tab.1 State estimation comparison results

5 結(jié) 語(yǔ)

本研究針對(duì)弱觀測(cè)噪聲條件下的非線性非高斯的動(dòng)態(tài)系統(tǒng)的濾波問題，提出了基于加權(quán)均值遷移的粒子濾波算法。本研究算法相對(duì)于其他算法優(yōu)越之處在于算法中涉及的所有粒子均參與了任意時(shí)刻的粒子更新，每一個(gè)粒子都進(jìn)行均值遷移和加權(quán)后的粒子概率密度平衡系數(shù)估算新粒子位置，使得粒子集中包含了更多相異的粒子路徑，從而改善了粒子集的多樣性。

［1］ 劉曙光，劉明遠(yuǎn)，何 鉞.機(jī)器視覺及其應(yīng)用［J］.河北科技大學(xué)學(xué)報(bào)，2000，21（4）：11-15.

LIU Shuguang，LIU Mingyuan，HE Yue.The machine vision and its application［J］.Journal of Hebei University of Science and Technology，2000，21（4）：11-15.

［2］ 李 科，徐克虎，黃大山.改進(jìn)的均值漂移和粒子濾波混合跟蹤方法［J］.計(jì)算機(jī)應(yīng)用，2012，32（2）：504-506.

LI Ke，XU Kehu，HUANG Dashan.Improved object tracking method based on mean shift and particle filter［J］.Journal of Computer Applications，2012，32（2）：504-506.

［3］ HU X L，SCHON T B，LJUNG L.A basic convergence result for particle filtering［J］.Signal Processing，2008，56（4）：1337-1348.

［4］ ARULAMPALAM M S，MASKELL S，GORDON N，et al.A tutorial on particle filters for online nonlinear／non-Gaussian Bayesian tracking［J］.Signal Processing，2002，50（2）：174-188.

［5］ 夏 楠，邱天爽，李景春，等.一種卡爾曼濾波與粒子濾波相結(jié)合的非線性濾波算法［J］.電子學(xué)報(bào)，2013，41（1）：148-152.

XIA Nan，QIU Tianshuang，LI Jingchun，et al.A nonlinear fitering algorithm combining the Kalman filter and the particle filter［J］.Acta Electronica Sinica，2013，41（1）：148-152.

［6］ 陳志敏，薄煜明，吳盤龍，等.基于自適應(yīng)粒子群優(yōu)化的新型粒子濾波在目標(biāo)跟蹤中的應(yīng)用［J］.控制與決策，2013，28（2）：193-200.

CHEN Zhimin，BO Yuming，WU Panlong，et al.Novel particle filter algorithm based on adaptive particle swarm optimization and its application to radar target tracking［J］.Control and Decision，2013，28（2）：193-200.

［7］ SHAN Caifeng，WEI Yucheng，TAN Tieniu，et al.Real time hand tracking by combining particle filtering and mean-shift［A］.Sixth IEEE International Conference on Automatic Face and Gesture Recognition［C］.Seoul：IEEE Computer Society，2004.669-674.

［8］ 韓 明，劉教民，王震洲，等.適用于多目標(biāo)跟蹤的 MSPF算法研究［J］.河北工業(yè)大學(xué)學(xué)報(bào)，2012，41（5）：15-19.

HAN Ming，LIU Jiaomin，WANG Zhenzhou，et al.Research on MSPF algorithm for multi-target tracking［J］.Journal of Hebei University of Technology，2012，41（5）：15-19.

［9］ JULIER S J，UHLMANN J K，DURRAN W H F.A new method for nonlinear transformation of means and covariances in filters and estimators［J］.IEEE Trans Automatic Control，2000，45：477-482.

Particle filter algorithm based on mean-shift

HUANG Lijing1，YU Naiwen2，WANG Jingtao3
（1.School of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.Polytechnic College，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；3.Department of Computer Science，Shijiazhuang University，Shijiazhuang Hebei 050035，China）

To cope with particle degeneracy with weak measurement noise，especially the particle filter problems of nonlinear／non-Gaussian when the measurement noise is smaller，a particle filter algorithm is proposed based on mean-shift.Firstly，non-parametric fast pattern matching algorithm of Kernel density estimation is introduced for particle filter，and the probability density estimation is iteratively calculated.Then，particle gradient direction and the mean value for each particle that moves to the sample are estimated by mean shift.When the position of particles is changed，the re-sampled particles are weightily processed.Finally，using the method to update particle sets overcomes the particle degradation effectively and improves the accuracy of state estimation.

posterior distribution；density estimation；mean-shift；weighted value；particle filter

TP391

A

1008-1542（2014）02-0184-05

10.7535／hbkd.2014yx02013

2013-09-12；

2013-11-03；責(zé)任編輯：張 軍

河北省自然科學(xué)基金（F2012208004）；河北省科技支撐計(jì)劃項(xiàng)目（12210807）

黃莉靜（1977-），女，河北張家口人，碩士，主要從事網(wǎng)絡(luò)與數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘方面的研究。

E-mail：rnhlj＠hebust.edu.cn