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

黃莉靜，于乃文，王敬濤

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

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

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

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

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

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

黃莉靜，于乃文，王敬濤.基于均值遷移的粒子濾波算法研究［J］.河北科技大學(xué)學(xué)報，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.

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

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

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

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

1.1 重要密度函數(shù)

1.2 粒子濾波算法

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

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

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

則后驗概率密度可表示為

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

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

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

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

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

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

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

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

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

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

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

3 均值遷移粒子濾波算法

3.1 核K－ 密度估計

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

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

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

其中H是任意的核K值。

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

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

4 實驗仿真

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

［1］ 劉曙光，劉明遠(yuǎn)，何 鉞.機(jī)器視覺及其應(yīng)用［J］.河北科技大學(xué)學(xué)報，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ī)應(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é)報，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é)報，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）；河北省科技支撐計劃項目（12210807）

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

E-mail：rnhlj＠hebust.edu.cn