基于小生境遺傳算法的粒子濾波算法

張 航，李夢麗，楊清波

1.中南大學 信息科學與工程學院，長沙 410083

2.中南大學 信息科學與工程學院 控制工程系，長沙 410083

基于小生境遺傳算法的粒子濾波算法

張 航1，李夢麗2，楊清波2

1.中南大學 信息科學與工程學院，長沙 410083

2.中南大學 信息科學與工程學院 控制工程系，長沙 410083

1 引言

粒子濾波（Particle Filter，PF）[1]是一種基于Monte Carlo仿真的遞推貝葉斯估計方法。因具有適用于非線性及非高斯噪聲環境等優點，被廣泛應用于目標跟蹤、圖像處理和故障檢測[2-3]等諸多領域，其基本原理是根據系統狀態的一組帶有權值的隨機樣本來表示實際問題所需要的后驗概率密度函數，這些樣本被形象地稱為“粒子”。粒子濾波最常見的問題是粒子的退化現象，對粒子進行重采樣是解決粒子退化問題的一種重要方法，重采樣的目的就是將權值小的粒子用權值大的粒子分解代替。當前存在多種重采樣算法，如系統重采樣（System Resampling，SR）[4]，殘差重采樣（Residual Resampling，RR）[5]，多項式重采樣（Multinomial Resampling，MR）[6]等。所用的重采樣過程雖然解決了粒子的退化問題，但也帶來了粒子貧乏的問題。將遺傳算法引入粒子重采樣中，能有效增加粒子多樣性，但基本遺傳算法常在各個個體未達到最優解之前就收斂于一個局部最優點，從而導致樣本趨于一致，即產生“早熟”現象，不能保證在粒子濾波重采樣上計算效率和可靠性的要求。

為了克服這些不足，本文引入了小生境遺傳機理來解決粒子濾波跟蹤算法中的粒子多樣性退化的問題，這種算法提高了粒子的多樣性，相對于普通粒子濾波，基于小生境遺傳重采樣的粒子濾波僅需要較少的粒子就可以實現狀態的精確估計。

2 基本原理

2.1 粒子濾波原理

若已知狀態的初始概率密度函數為p(x0|z0)=p(x0)，則預測方程和更新方程為：

其中離散狀態序列x1:k={x1，x2，…，xk}具有馬爾可夫特性，離散測量序列zk={z1，z2，…，zk}為獨立測量序列，且與各狀態獨立。式（1）（2）構成了狀態xk的最優貝葉斯估計，但其解析解只在特定高斯條件或狀態空間有限時成立。

為了計算式（1）（2），引入序貫重要性采樣算法（SIS）。其核心思想是用一組帶權值的隨機粒子來表示并計算所需的后驗概率密度，人們從建議分布q(xk|xk-1，z1:k)中采樣得到一組粒子，并通過加權和的形式逼近狀態后驗概率密度。粒子權值計算公式為：

則后驗概率密度可以近似為：

其中是歸一化權值，，N表示采樣粒子數目。根據大數定理，當N足夠大時，可以證明式（4）就是真實的后驗概率密度，則得到狀態的輸出為：

粒子濾波重采樣的思想是通過對樣本重新采樣，繁殖重要性權值高的粒子，淘汰權值低的粒子，從而抑制退化，如圖1所示。

圖1 粒子濾波重采樣示意圖

2.2 Mean Shift算法原理

Mean Shift算法是一種利用數據驅動的無參估計算法，又稱為核密度估計算法，主要通過均值偏移向量尋找到后驗概率局部最優[7]。算法如下：

（1）確定初始幀的目標模型：

其中，xi表示目標模型的像素位置向量；x0表示目標模型中心像素位置向量，u是經過核函數加權量化以后的特征向量；h是跟蹤窗口帶寬；δ是沖擊響應函數；C是歸一化常量。

（2）確定當前幀的候選目標模型：

其中，y0是當前幀搜索窗口的中心像素位置坐標。（3）利用Mean Shift計算Bhattacharyya距離：

進而求得Mean Shift向量m(y)：

當‖m(y)‖＜ε時結束，y1就是目標的準確位置；否則，令y0←y1，轉步驟（2）。

3 改進的粒子濾波算法

本文采用小生境概念的遺傳算法[8]，其基本思想是：通過兩兩比較種群中個體之間的海明距離，當這個距離在指定的距離L之內，再比較兩者之間的適應度大小，并對其中適應度較小的個體施加一個較強的罰函數，極大降低其適應度，這樣對于預先指定的某一距離L之內的兩個個體，其中較差的個體經處理后其適應度變得更差，它在后面的進化過程中被淘汰的概率就極大。也就是說，在距離L之內將只存在一個優良個體，從而既維護了群體的多樣性，又使得各個個體之間保持一定的距離，并使得個體能夠在整個約束空間分散開來，從而在克服早熟收斂方面都取得良好的效果。

本文提出基于小生境遺傳算法的粒子濾波重采樣算法。在跟蹤的過程中，粒子濾波與Mean Shift算法同步融合，首先利用粒子濾波的建議分布函數采樣N個粒子；其次利用Mean Shift搜索目標可能的位置，并在該位置附近采樣Μ個粒子。在重采樣部分引入小生境遺傳算法處理這N+Μ個粒子。改進算法的執行過程如下：

圖2 兩種算法在頭部快速移動下的對比圖

（1）初始化。設定粒子濾波建議分布函數采樣的粒子個數為N，Mean Shift采樣的粒子個數為Μ。從先驗分布p(x0)中采集粒子樣本，

（2）粒子序列重要性采樣。Fori=1，2，…，N，從建議分布中采樣得到新的粒子，計算粒子的權值，并歸一化粒子的權值。

（3）均值偏移。利用Mean Shift算法預測得到目標位置，并在該位置附近隨機產生Μ個粒子，并計算各個粒子的權值。

（4）狀態輸出。由采樣得到的N個粒子根據式（5）得到K時刻的目標狀態的后驗概率估計。

①將粒子濾波采樣的N個粒子和Mean Shift產生的Μ個粒子組成粒子集，并設為初始群體，適應度為個體相對應的權值

②根據各個個體的適應度對其進行降序排列，記憶前N個個體。

③對初始群體進行遺傳選擇、交叉、變異操作得到子代種群。

④小生境限制競爭選擇操作，將通過遺傳操作的子代種群與記憶的父代種群合并，得到2N+Μ個粒子，在合并后的種群里，對相鄰較近粒子中適應度低的處以罰函數加快其淘汰，使粒子更快地向高適應度方向移動。

⑤通過以上操作后，依據這2N+Μ個個體的新適應度對個體進行降序排序，記憶前N個個體，這就是重采樣的結果。

⑥若種群適應度達到設定門限，則輸出計算結果，否則轉到步驟②。

4 實驗結果分析

為了證明本文改進算法在目標跟蹤方面的有效性，在一臺P4 2.4 GHz，2 GB內存的計算機上進行仿真，在VC++6.0平臺上，對下面兩段視頻作對比實驗，把標準的粒子濾波算法和本文改進的算法進行比較。跟蹤的結果選用矩形框進行表示。

第一個視頻序列是基于頭部的快速左右移動的實驗。視頻尺寸為128×96，兩種算法的粒子數均為50，從圖2（a）的結果可以看出，標準粒子濾波跟蹤算法在第25幀和第43幀出現了目標丟失的現象，而從圖2（b）可知本文的算法能較好地跟蹤頭部。圖3顯示了第一個視頻序列水平方向位置估計誤差曲線，標準粒子濾波（PF）誤差較大，而本文的改進方法（NPF）誤差則相對較小。

圖3 水平方向位置估計誤差

第二個視頻序列是關于遮擋情況下的跟蹤實驗，視頻尺寸為128×96，兩種算法的粒子數均為80，臉受到了手的遮擋，而且手的顏色與臉顏色相近，這些都給跟蹤帶來了干擾，但可以看出，本文改進的算法依舊具有良好的跟蹤性能，優于標準的粒子濾波算法，如圖4所示。

兩種方法的時間復雜度，通過計算每幀圖像處理時間給出。圖5所示為視頻序列1和視頻序列2的跟蹤過程中本文改進算法在每一幀的耗時，可以看出視頻序列1的平均耗時為38 ms，視頻序列2的平均耗時為43 ms。

圖4 兩種算法在頭部遮擋情況下的對比圖

圖5 時間統計

從表1中可以看出，本文的改進算法（NPF）相對于標準粒子濾波算法（PF）計算時間有所增加，因為本文的改進算法增加了算法復雜度，但由此增加的時間開銷在接受范圍之內，兼顧了跟蹤的實時性，且跟蹤更準確，可以得出結論：改進算法從總體上明顯提高了系統的性能。

表1 兩種跟蹤方法時間對比 ms

5 總結

粒子濾波能較好地處理非線性、非高斯系統的狀態估計問題，但是，標準粒子濾波算法重采樣過程中的粒子多樣性減弱造成了濾波精度下降。本文針對此問題，利用小生境遺傳算法思想，給出了一種有效的重采樣粒子濾波跟蹤算法。實驗證明，相對標準的粒子濾波算法，本文所給出的算法有一定的改善。

[1]Gordon N，Salmond D J，Smith A F M.Novel approach to nonlinear/non-Gaussian Bayesian state estimation[J].IEEE Proc of Radar and Signal Processing，1993，140（2）：107-113.

[2]Isaac A，Willett P，Bar-Shalom Y.Quickest detection and tracking of spawning targets using monopulse radar channel signals[J]. IEEE Trans on Signal Processing，2008，56（3）：1302-1308.

[3]Angelova D，Mihaylova L.Extended object tracking using Monte Carlo methods[J].IEEE Trans on Signal Processing，2008，56（2）.

[4]Bolic M，Djuric P，Hong S.Resampling algorithms for particle filters：a computational complexity perspective[J].EURASIP Journal on Applied Signal Processing，2004，2004：2267-2277.

[5]Bolic M，Djuric P M，Sangjin H.Resampling algorithms and architectures for distributed particle filters[C]//IEEE Transactions on Signal Processing，2005.

[6]Hol J D.Resampling in particle filters[R].Linkoping University，2004.

[7]Yimaz A.Object tracking by asymmetric kernel mean shift with automatic scale and orientation selection[C]//IEEE Conference on Computer Vision and Pattern Recognition，2007：1-6.

[8]Lee C G，Cho D H，Jung H K.Niching genetic algorithm with restricted competition selection for multimodal function optimization[J].IEEE Trans on Magn，1999，34（1）：1722-1755.

ZHANG Hang1,LI Mengli2,YANG Qingbo2

1.School of Information Science and Engineering,Central South University,Changsha 410083,China
2.Department of Control Engineering,School of Information Science and Engineering,Central South University,Changsha 410083,China

Resampling is a critical operation to solve degeneracy problem with particle filters generally.The basic idea of resampling is to discard particles which have small weights and concentrate on particles with large weights.But resampling often introduces sample impoverishment problem,especially the sample is limited under the condition,even causes the filter to disperse.This paper proposes improved particle filter algorithm.Mean Shift integrates with particle filter,and then the niching genetic algorithm is used in resampling in order to improve the variety of particles and remove the degeneracy phenomenon.The simulation results prove the proposed algorithm reduces the tracking error,and has better precision.

particle filter;Mean Shift;niching genetic algorithm;resampling

重采樣是解決粒子濾波退化問題的主要方法，重采樣的基本思想是采取復制保留權值較高的粒子，刪除權值較低的粒子，而這導致了粒子多樣性的減弱，特別是在樣本受限條件下，甚至導致濾波發散。針對上述問題，提出改進的粒子濾波算法，將Mean Shift與粒子濾波融合，在重采樣部分引入小生境遺傳算法，提高粒子的多樣性，避免粒子退化。實驗表明，改進后的算法狀態估計精度更高，效果更好。

粒子濾波；Mean Shift；小生境遺傳算法；重采樣

A

TP391

10.3778/j.issn.1002-8331.1112-0419

ZHANG Hang,LI Mengli,YANG Qingbo.Particle filter algorithm based on niching genetic algorithm.Computer Engineering and Applications,2013,49（18）：191-194.

國家自然科學基金（No.50808025）；2010年中南大學碩士研究生學位論文創新資助項目（No.2010ssxt209）。

張航（1967—），男，博士，副教授；李夢麗（1987—），女，碩士研究生，主要研究方向為圖像處理、模式識別；楊清波（1986—），男，碩士研究生。E-mail：chuichui77@126.com

2011-12-21

2012-02-10

1002-8331（2013）18-0191-04

CNKI出版日期：2012-05-28 http://www.cnki.net/kcms/detail/11.2127.TP.20120528.1612.001.html