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

張 航，李夢(mèng)麗，楊清波

1.中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410083

2.中南大學(xué) 信息科學(xué)與工程學(xué)院 控制工程系，長(zhǎng)沙 410083

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

張 航1，李夢(mèng)麗2，楊清波2

1.中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410083

2.中南大學(xué) 信息科學(xué)與工程學(xué)院 控制工程系，長(zhǎng)沙 410083

1 引言

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

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

2 基本原理

2.1 粒子濾波原理

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

其中離散狀態(tài)序列x1:k={x1，x2，…，xk}具有馬爾可夫特性，離散測(cè)量序列zk={z1，z2，…，zk}為獨(dú)立測(cè)量序列，且與各狀態(tài)獨(dú)立。式（1）（2）構(gòu)成了狀態(tài)xk的最優(yōu)貝葉斯估計(jì)，但其解析解只在特定高斯條件或狀態(tài)空間有限時(shí)成立。

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

則后驗(yàn)概率密度可以近似為：

其中是歸一化權(quán)值，，N表示采樣粒子數(shù)目。根據(jù)大數(shù)定理，當(dāng)N足夠大時(shí)，可以證明式（4）就是真實(shí)的后驗(yàn)概率密度，則得到狀態(tài)的輸出為：

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

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

2.2 Mean Shift算法原理

Mean Shift算法是一種利用數(shù)據(jù)驅(qū)動(dòng)的無(wú)參估計(jì)算法，又稱為核密度估計(jì)算法，主要通過(guò)均值偏移向量尋找到后驗(yàn)概率局部最優(yōu)[7]。算法如下：

（1）確定初始幀的目標(biāo)模型：

其中，xi表示目標(biāo)模型的像素位置向量；x0表示目標(biāo)模型中心像素位置向量，u是經(jīng)過(guò)核函數(shù)加權(quán)量化以后的特征向量；h是跟蹤窗口帶寬；δ是沖擊響應(yīng)函數(shù)；C是歸一化常量。

（2）確定當(dāng)前幀的候選目標(biāo)模型：

其中，y0是當(dāng)前幀搜索窗口的中心像素位置坐標(biāo)。（3）利用Mean Shift計(jì)算Bhattacharyya距離：

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

當(dāng)‖m(y)‖＜ε時(shí)結(jié)束，y1就是目標(biāo)的準(zhǔn)確位置；否則，令y0←y1，轉(zhuǎn)步驟（2）。

3 改進(jìn)的粒子濾波算法

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

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

圖2 兩種算法在頭部快速移動(dòng)下的對(duì)比圖

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

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

（3）均值偏移。利用Mean Shift算法預(yù)測(cè)得到目標(biāo)位置，并在該位置附近隨機(jī)產(chǎn)生Μ個(gè)粒子，并計(jì)算各個(gè)粒子的權(quán)值。

（4）狀態(tài)輸出。由采樣得到的N個(gè)粒子根據(jù)式（5）得到K時(shí)刻的目標(biāo)狀態(tài)的后驗(yàn)概率估計(jì)。

①將粒子濾波采樣的N個(gè)粒子和Mean Shift產(chǎn)生的Μ個(gè)粒子組成粒子集，并設(shè)為初始群體，適應(yīng)度為個(gè)體相對(duì)應(yīng)的權(quán)值

②根據(jù)各個(gè)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排列，記憶前N個(gè)個(gè)體。

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

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

⑤通過(guò)以上操作后，依據(jù)這2N+Μ個(gè)個(gè)體的新適應(yīng)度對(duì)個(gè)體進(jìn)行降序排序，記憶前N個(gè)個(gè)體，這就是重采樣的結(jié)果。

⑥若種群適應(yīng)度達(dá)到設(shè)定門(mén)限，則輸出計(jì)算結(jié)果，否則轉(zhuǎn)到步驟②。

4 實(shí)驗(yàn)結(jié)果分析

為了證明本文改進(jìn)算法在目標(biāo)跟蹤方面的有效性，在一臺(tái)P4 2.4 GHz，2 GB內(nèi)存的計(jì)算機(jī)上進(jìn)行仿真，在VC++6.0平臺(tái)上，對(duì)下面兩段視頻作對(duì)比實(shí)驗(yàn)，把標(biāo)準(zhǔn)的粒子濾波算法和本文改進(jìn)的算法進(jìn)行比較。跟蹤的結(jié)果選用矩形框進(jìn)行表示。

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

圖3 水平方向位置估計(jì)誤差

第二個(gè)視頻序列是關(guān)于遮擋情況下的跟蹤實(shí)驗(yàn)，視頻尺寸為128×96，兩種算法的粒子數(shù)均為80，臉受到了手的遮擋，而且手的顏色與臉顏色相近，這些都給跟蹤帶來(lái)了干擾，但可以看出，本文改進(jìn)的算法依舊具有良好的跟蹤性能，優(yōu)于標(biāo)準(zhǔn)的粒子濾波算法，如圖4所示。

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

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

圖5 時(shí)間統(tǒng)計(jì)

從表1中可以看出，本文的改進(jìn)算法（NPF）相對(duì)于標(biāo)準(zhǔn)粒子濾波算法（PF）計(jì)算時(shí)間有所增加，因?yàn)楸疚牡母倪M(jìn)算法增加了算法復(fù)雜度，但由此增加的時(shí)間開(kāi)銷在接受范圍之內(nèi)，兼顧了跟蹤的實(shí)時(shí)性，且跟蹤更準(zhǔn)確，可以得出結(jié)論：改進(jìn)算法從總體上明顯提高了系統(tǒng)的性能。

表1 兩種跟蹤方法時(shí)間對(duì)比 ms

5 總結(jié)

粒子濾波能較好地處理非線性、非高斯系統(tǒng)的狀態(tài)估計(jì)問(wèn)題，但是，標(biāo)準(zhǔn)粒子濾波算法重采樣過(guò)程中的粒子多樣性減弱造成了濾波精度下降。本文針對(duì)此問(wèn)題，利用小生境遺傳算法思想，給出了一種有效的重采樣粒子濾波跟蹤算法。實(shí)驗(yàn)證明，相對(duì)標(biāo)準(zhǔn)的粒子濾波算法，本文所給出的算法有一定的改善。

[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

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

粒子濾波；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.

國(guó)家自然科學(xué)基金（No.50808025）；2010年中南大學(xué)碩士研究生學(xué)位論文創(chuàng)新資助項(xiàng)目（No.2010ssxt209）。

張航（1967—），男，博士，副教授；李夢(mèng)麗（1987—），女，碩士研究生，主要研究方向?yàn)閳D像處理、模式識(shí)別；楊清波（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