運(yùn)動目標(biāo)追蹤的人工魚群優(yōu)化粒子濾波算法

張婷婷，于 明，閻 剛

（河北工業(yè)大學(xué) 天津市電子材料與器件重點(diǎn)實(shí)驗(yàn)室，天津 300130）

運(yùn)動目標(biāo)追蹤的人工魚群優(yōu)化粒子濾波算法

張婷婷，于 明，閻 剛

（河北工業(yè)大學(xué) 天津市電子材料與器件重點(diǎn)實(shí)驗(yàn)室，天津 300130）

為了進(jìn)一步提高視頻圖像序列中的運(yùn)動目標(biāo)追蹤精度，在擴(kuò)展卡爾曼粒子濾波中引入人工魚群算法，利用人工魚群算法優(yōu)化采樣過程，使粒子不斷朝高似然區(qū)域移動來尋找最優(yōu)位置；然后對重采樣過程優(yōu)化，提高樣本多樣性，克服粒子樣本貧化問題，提高對系統(tǒng)狀態(tài)的預(yù)估精度；最后以顏色直方圖特征描述運(yùn)動目標(biāo)，結(jié)合目標(biāo)的運(yùn)動特征建立游走模式的二階自回歸模型，以提高運(yùn)動估計(jì)精度．對比標(biāo)準(zhǔn)粒子濾波（PF）、擴(kuò)展卡爾曼粒子濾波（EKPF），人工魚群優(yōu)化擴(kuò)展卡爾曼粒子濾波算法（AFSA-EKPF）能夠?qū)V波結(jié)果均方誤差的均值和方差分別降低至0.113 86和0.003 09，同時(shí)在追蹤運(yùn)動目標(biāo)實(shí)驗(yàn)中，能夠有效地消除目標(biāo)遮擋所帶來的影響．

運(yùn)動目標(biāo)跟蹤；擴(kuò)展卡爾曼粒子濾波；人工魚群；顏色直方圖

0 引言

有效的目標(biāo)跟蹤系統(tǒng)要求較高的實(shí)時(shí)性、魯棒性，但在實(shí)際環(huán)境中，運(yùn)動目標(biāo)姿態(tài)、遮擋、形變、背景及光照等因素對跟蹤過程的魯棒性會產(chǎn)生一定的影響，有效解決復(fù)雜環(huán)境條件下的運(yùn)動目標(biāo)狀態(tài)估計(jì)問題是目標(biāo)跟蹤領(lǐng)域的一個(gè)難點(diǎn)[1]．近些年來，基于MonteCarlo方法和遞推Bayesian估計(jì)的粒子濾波算法成為解決非線性、非高斯條件下系統(tǒng)估計(jì)問題的有效方法，不同于傳統(tǒng)的卡爾曼濾波方法，粒子濾波直接將非線性的系統(tǒng)模型進(jìn)行非線性變換，采用的隨機(jī)樣本方法對系統(tǒng)狀態(tài)的概率分布描述，使得非線性狀態(tài)估計(jì)更接近隨機(jī)系統(tǒng)的非線性本質(zhì)[2]．

有研究者將粒子濾波應(yīng)用于目標(biāo)跟蹤，以解決其中的非線性、非高斯問題[3]．廣泛使用的序列重要性采樣（SIS）會帶來粒子退化問題，N.J.Gordon等人提出了在SIS粒子濾波算法后進(jìn)行重采樣，來減緩粒子退化的問題，但是又帶來了粒子貧化問題——重采樣后喪失粒子多樣性，具有較大權(quán)值的粒子被多次選取，經(jīng)過若干次迭代后，所有的粒子都集中在一個(gè)點(diǎn)上[4]．

近年來學(xué)者們提出了很多改進(jìn)方法[4-6]，與傳統(tǒng)的解決方法不同，一些學(xué)者通過智能優(yōu)化算法來避免粒子貧化問題[7-8]，Kotecha和Djuric提出高斯和粒子濾波（GSPF）算法，考慮到系統(tǒng)模型比較復(fù)雜時(shí)，單一高斯分布近似后驗(yàn)分布遠(yuǎn)遠(yuǎn)不夠，結(jié)合高斯濾波和粒子濾波的優(yōu)點(diǎn)，不需要重采樣步驟，算法避免了貧化問題且精度有所提高．Cai[9]等人提出了人工魚群優(yōu)化粒子濾波算法，利用人工魚群算法優(yōu)化粒子運(yùn)動，使其朝高似然區(qū)域移動，從而提高狀態(tài)估計(jì)精度．但這種算法沒有考慮最新的觀測數(shù)據(jù)，采樣得到的粒子集不能有效地表示后驗(yàn)概率．

為了進(jìn)一步解決粒子退化和貧化帶來的濾波精度降低問題，本文研究提出一種新的算法 AFSA-EKPF （ArtificialFish-Extended Kalman Particle Filtering），將人工魚群算法引入到擴(kuò)展卡爾曼粒子濾波中，分別優(yōu)化采樣過程和重采樣過程，調(diào)節(jié)似然函數(shù)使粒子集不斷向真實(shí)狀態(tài)值移動，解決粒子退化和貧化問題，提高濾波精度，并且以顏色特征描述運(yùn)動目標(biāo)，對比標(biāo)準(zhǔn)粒子濾波（PF）、擴(kuò)展卡爾曼粒子濾波（EKPF），分析實(shí)驗(yàn)結(jié)果．

1 擴(kuò)展卡爾曼粒子濾波

擴(kuò)展卡爾曼粒子濾波算法的基本思想是利用擴(kuò)展卡爾曼濾波（EKF）來構(gòu)造粒子濾波的建議分布函數(shù)，從重要性密度函數(shù)的角度對粒子濾波算法進(jìn)行改進(jìn)[10]．

EKF通過高斯近似更新后驗(yàn)分布來實(shí)現(xiàn)遞推估計(jì)，融合最新的觀測值，在每時(shí)刻按照公式(1)對后驗(yàn)密度進(jìn)行近似

EKPF應(yīng)用EKF方法可以得到一個(gè)相對較好的重要性密度函數(shù)，但粒子權(quán)重的方差隨時(shí)間而遞增，使得只有少量的粒子具有較大權(quán)值，粒子的權(quán)重集中到少量粒子上，因此大量的工作都被浪費(fèi)在小權(quán)值粒子上．同時(shí)重采樣過程中出現(xiàn)了粒子樣本貧化問題，經(jīng)過幾次迭代以后大權(quán)值的粒子被選擇多次，導(dǎo)致粒子集的多樣性降低，不能有效的表示后驗(yàn)概率密度，存在一定的退化現(xiàn)象．尤其是當(dāng)似然函數(shù)非常窄或似然函數(shù)位于先驗(yàn)概率分布尾部時(shí)，粒子樣本貧化問題更加嚴(yán)重，如圖1、圖2所示，在這些情況下會出現(xiàn)很大的模型誤差，從而導(dǎo)致濾波精度下降．

圖1 窄的似然函數(shù)Fig.1 Situation of narrow likelihood function

圖2 似然函數(shù)位于先驗(yàn)概率分布尾部Fig.2 Likelihood function located in the tailof prioriprobability

2 人工魚群算法

人工魚群算法是一種基于魚群自治體的尋優(yōu)策略．在水中魚類數(shù)量最大的地方往往是該水域營養(yǎng)最豐富的地方，所以通過模擬魚群的行為來尋找全局最優(yōu)．魚群一般具有3種自由行為：覓食、追尾和聚群．覓食行為是指每條魚在自由游動情況下，發(fā)現(xiàn)食物時(shí)，都會朝著食物多的方向游去．追尾行為是指在魚群中某些個(gè)體發(fā)現(xiàn)前方有食物時(shí)，相鄰個(gè)體會追隨其朝食物所在地點(diǎn)游去．聚群行為是為了保證自身種群生存而養(yǎng)成的一種生活習(xí)性，魚在水中自由移動時(shí)都會聚集成群．其中魚群中個(gè)體的覓食行為可以達(dá)到局部最優(yōu)，而追尾和聚群行為可以跳出局部最優(yōu)使魚群達(dá)到全局最優(yōu)．

根據(jù)上述情況，使每條人工魚根據(jù)自身以及四周的情況自由選擇一種行為．最后人工魚將停留在局部極值周圍，在實(shí)際應(yīng)用中求極大問題時(shí)，目標(biāo)函數(shù)值最大的人工魚一般停留在值最大的極值域周圍，因此可根據(jù)該內(nèi)容找出全局極值域．同時(shí)一般情況下值最大的極值域周圍會停留著最多的人工魚，可根據(jù)這一特性找到全局極值．魚群的覓食行為可以獲取到局部極值，追尾和聚群行為都是幫助跳出局部極值從而獲取到全局極值點(diǎn)．人工魚群算法對追尾和聚群行為進(jìn)行評價(jià)，然后選擇一種合適的行為，最終快速高效地達(dá)到全局最優(yōu)[]．

3 基于人工魚群優(yōu)化的擴(kuò)展卡爾曼粒子濾波算法

將人工魚群算法引入到擴(kuò)展卡爾曼粒子濾波算法中，把粒子當(dāng)作人工魚，魚群通過不斷更新自己的位置來隨機(jī)尋找高食物濃度的區(qū)域，把似然度當(dāng)作食物濃度，當(dāng)人工魚沒有發(fā)現(xiàn)相對自身較高的濃度區(qū)域時(shí)，他們會不斷地隨機(jī)游動直到搜索到高濃度區(qū)域．再優(yōu)化采樣過程和重采樣過程，使粒子集通過似然函數(shù)調(diào)節(jié)不斷向真實(shí)狀態(tài)值移動．

通過人工魚群算法優(yōu)化覓食和聚群行為，粒子集不斷向系統(tǒng)中最優(yōu)粒子靠近，智能粒子集群則向高似然區(qū)域移動，如圖3所示，從而解決粒子退化和貧化問題，可以提高濾波精度．對動態(tài)系統(tǒng)進(jìn)行一階線性化近似，縮小與真實(shí)后驗(yàn)分布產(chǎn)生樣本的偏差．當(dāng)?shù)螖?shù)達(dá)到設(shè)定上限或人工魚群的最優(yōu)值符合某閾值時(shí)，表明人工魚群已經(jīng)分布在真實(shí)狀態(tài)附近，則停止優(yōu)化．此時(shí)再利用最新觀測值對粒子集進(jìn)行權(quán)重更新并做歸一化處理．

圖3 人工魚群優(yōu)化過程Fig.3 Processof artificial fish schoolalgorithm optimization

基于人工魚群優(yōu)化的擴(kuò)展卡爾曼粒子濾波算法（AFSA-EKPF）：

Step2：用EKF方法更新每時(shí)刻的采樣粒子，更新公式為公式 (3)

Step3：從重要性密度函數(shù)中采樣并計(jì)算權(quán)值，更新公式為公式 (4)、公式 (5)

Step4：利用人工魚群算法優(yōu)化，只考慮魚群的覓食和聚群2種行為時(shí)，所采用的目標(biāo)函數(shù)為公式 (6)．

對覓食行為和聚群行為進(jìn)行建模尋找局部最優(yōu)，設(shè)定閾值和迭代上限，當(dāng)目標(biāo)函數(shù)的偏差小于某閥值，或者迭代次數(shù)達(dá)到設(shè)定上限時(shí)終止算法．

Step5：歸一化并更新粒子權(quán)值，更新公式為公式 (7)

Step8：當(dāng)k=k+1時(shí)，跳轉(zhuǎn)至Step2．

通過人工魚群算法優(yōu)化粒子集，使粒子集不斷向高似然區(qū)域移動，增加粒子樣本集的多樣性，緩解粒子的退化現(xiàn)象并解決粒子貧化問題，最終得到的粒子集可以充分表示粒子的真實(shí)分布狀態(tài)，保證權(quán)值最大的粒子用于估計(jì)，從而有效改善因粒子退化和貧化而造成的濾波精度下降問題．

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

為了驗(yàn)證本文算法的有效性，首先對比了標(biāo)準(zhǔn)粒子濾波（PF）、擴(kuò)展卡爾曼粒子濾波（EKPF）、人工魚群優(yōu)化擴(kuò)展卡爾曼粒子濾波算法（AFSA-EKPF）的濾波實(shí)驗(yàn)，然后將粒子濾波應(yīng)用于目標(biāo)跟蹤，對比分析了運(yùn)動目標(biāo)遮擋下的目標(biāo)追蹤實(shí)驗(yàn)．

4.1 粒子濾波實(shí)驗(yàn)及分析

進(jìn)行人工魚群優(yōu)化擴(kuò)展卡爾曼粒子濾波算法（AFSA-EKPF）仿真實(shí)驗(yàn)，并與標(biāo)準(zhǔn)粒子濾波（PF）、擴(kuò)展卡爾曼粒子濾波（EKPF）進(jìn)行對比分析，系統(tǒng)模型如公式 (8)、公式 (9)

式中：Vt1～Gamma 3,2為過程噪聲，Nt～0,0.00001，粒子數(shù)N=100，觀測時(shí)間T=60；感知距離visual= 0.3，人工魚群算法中的步長step=0.15，實(shí)驗(yàn)中采用均值估計(jì)系統(tǒng)的狀態(tài)，即進(jìn)行了100次獨(dú)立實(shí)驗(yàn)．

圖4 PF的狀態(tài)估計(jì)曲線Fig.4 Stateestimation curveof PF

圖5 EKPF的狀態(tài)估計(jì)曲線Fig.5 Stateestimation curveof EKPF

圖4，圖5，圖6分別是PF、EKPF和AFSA-EKPF的狀態(tài)估計(jì)曲線，圖7為一次獨(dú)立實(shí)驗(yàn)條件下的3種算法的狀態(tài)估計(jì)曲線，圖8為3種算法進(jìn)行100次獨(dú)立實(shí)驗(yàn)的均方誤差曲線，表1為3種算法進(jìn)行100次獨(dú)立實(shí)驗(yàn)的均方誤差均值和方差．

圖6 AFSA-EKPF的狀態(tài)估計(jì)曲線Fig.6 Stateestimation curveof AFSA-EKPF

圖7 PF、EKPF和AFSA-EKPF的狀態(tài)估計(jì)曲線Fig.7 Stateestimation curveof PF,EKPFand AFSA-EKPF

圖7是3種算法的狀態(tài)估計(jì)曲線，由實(shí)驗(yàn)結(jié)果可以看出本文提出的AFSA-EKPF的曲線相似程度更高，其估計(jì)值更接近于真實(shí)值，從而可以提高濾波效果．由圖8中3種算法的均方誤差（MSE）曲線的比較可以看出，AFSA-EKPF算法的均方誤差值最低．表1中數(shù)據(jù)為100次獨(dú)立實(shí)驗(yàn)中3種算法的均方誤差的均值和方差，通過對比AFSA-EKPF的值明顯小于PF和EKPF算法，說明本文算法提高了對系統(tǒng)狀態(tài)的預(yù)估精度．綜上所述本文算法優(yōu)于PF和EKPF算法，濾波精度更高，解決了由于粒子退化和貧化導(dǎo)致的濾波精度降低問題．

圖8 PF、EKPF和AFSA-EKPF的均方誤差曲線Fig.8 Mean Squared Error curveof PF,EKPFand AFSA-EKP

表1 PF、EKPF和AFSA-EKPF均方誤差的均值和方差Tab.1 Mean and variance ofMSE aboutPF，EKPFand AFSA-EKPF

4.2 目標(biāo)跟蹤實(shí)驗(yàn)

顏色特征是每個(gè)物體最本質(zhì)的物理特征，同時(shí)也是人類認(rèn)識世界，感知世界和區(qū)分物體的一種主要辨認(rèn)特征．用顏色特征描述目標(biāo)，當(dāng)目標(biāo)進(jìn)行平移、部分被遮擋以及旋轉(zhuǎn)時(shí)都能保持穩(wěn)定，具有較強(qiáng)的魯棒性．顏色直方圖將顏色空間分為若干個(gè)小的顏色區(qū)間，整個(gè)過程叫做顏色量化（color quantization），每個(gè)小的區(qū)間稱為顏色直方圖的一個(gè)柄，最終統(tǒng)計(jì)各個(gè)區(qū)間內(nèi)的像素?cái)?shù)量，顏色直方圖統(tǒng)計(jì)了一副圖像中顏色的數(shù)量特征，計(jì)算了不同色彩在整幅圖像中所占的比例．該方法不用考慮像素所在的空間位置，簡單、快速、易于實(shí)現(xiàn)，這里選取顏色直方圖提取目標(biāo)的顏色特征．區(qū)域y上的顏色直方圖的構(gòu)建方法可表示為公式 (10)

其中：K為歸一化常數(shù)； 為Kroneckerdelta函數(shù)．

實(shí)驗(yàn)在奔騰4處理器，2.93 GHz主頻、512M內(nèi)存的臺式PC機(jī)上進(jìn)行，采用MATLAB 7.1軟件平臺實(shí)現(xiàn)的．視頻來自視頻數(shù)據(jù)庫[12]，視頻實(shí)驗(yàn)中所采用的圖像序列總長80幀，圖像分辨率128×96，幀率24 fps．實(shí)驗(yàn)中手動選取第一幀圖像中的目標(biāo)初始化為模板，粒子數(shù)設(shè)為100，重采樣預(yù)支閥值設(shè)為0.9．視頻1是一個(gè)人在行走過程中人臉被另外一個(gè)人遮擋的情況．人在走動時(shí)由于遮擋使得人臉部的外觀模型發(fā)生了較大變化，并且兩個(gè)目標(biāo)顏色相似，因此使得穩(wěn)定的跟蹤目標(biāo)比較困難．從圖9a）可看出在目標(biāo)未被遮擋前標(biāo)準(zhǔn)的粒子濾波算法可以穩(wěn)定的跟蹤目標(biāo)，但是由于重采樣，而造成粒子多樣性降低，在26幀到30幀中被顏色相似的另外一個(gè)目標(biāo)遮擋時(shí)跟蹤效果失?。畯膱D9b）中可以看出本文提出的算法在整個(gè)目標(biāo)運(yùn)動中都能較為準(zhǔn)確的跟蹤目標(biāo)，由于增加了粒子樣本的多樣性，每一個(gè)粒子就代表一種狀態(tài)信息，即增加了目標(biāo)狀態(tài)的多樣性，粒子越豐富，算法估計(jì)能力越強(qiáng)，從而在目標(biāo)的運(yùn)動狀態(tài)發(fā)生變化（被遮擋）的情況下也具有較好的效果．

圖9 視頻1跟蹤結(jié)果Fig.9 Tracking resultsof the Video 1

圖10 視頻2跟蹤結(jié)果Fig.10 Tracking resultsof the Video 2

視頻2是人在走動時(shí)被另外一個(gè)目標(biāo)遮擋的情況．從圖10a）可看出在行人在未被遮擋前標(biāo)準(zhǔn)的粒子濾波算法可以穩(wěn)定的跟蹤目標(biāo)，但是在17到19幀中被遮擋時(shí)跟蹤效果失?。畯膱D10b）中可以看出本文提出的算法在整個(gè)目標(biāo)運(yùn)動中都能準(zhǔn)確的跟蹤目標(biāo)，由于改善了粒子分布情況，增加了目標(biāo)狀態(tài)的多樣性，從而在目標(biāo)的運(yùn)動狀態(tài)發(fā)生變化（被遮擋）的情況下也具有較好的效果．

5 結(jié)論

本文提出一種運(yùn)動目標(biāo)追蹤的人工魚群優(yōu)化擴(kuò)展卡爾曼粒子濾波算法，將人工魚群算法引入到擴(kuò)展卡爾曼粒子濾波中，有效地防止粒子退化和貧化問題，提高對系統(tǒng)狀態(tài)的預(yù)估精度，更適合在對精度要求高的系統(tǒng)中進(jìn)行濾波計(jì)算．以顏色特征描述運(yùn)動目標(biāo)，結(jié)合目標(biāo)的運(yùn)動特征建立了游走模型的二階自回歸模型，提高了運(yùn)動估計(jì)精度．大量的實(shí)驗(yàn)證明，本文的算法可以提高跟蹤的準(zhǔn)確性，尤其是當(dāng)目標(biāo)被遮擋時(shí)跟蹤效果良好．

[1]Zhang Sh J，Stentiford F．Motiondetectionusingamodelofvisualattention[C]//Proceedingsof IEEE InternationalConferenceon ImageProcessing，2007，1：513-516．

[2]CappeO，GodsillSJ，Moulines E．An overview ofexistingmethodsand recentadvances in sequentialMonte Carlo[J]．Proceedingsof the IEEE，2007，95（5）899-924．

[3]Boers Y，Driessen JN．Inter-actingmultiplemodelparticle filter[J]．IEEEProceedingsof Radar Sonar Navigation，2003，150（5）：344-349．

[4]韓磊，郭曉金，齊威，等．改進(jìn)的粒子濾波算法 [J]．電視技術(shù)，2012，36（7）：16-19．

[5]Cheng Yongming，JiangM ingyan，Yuan Dongfeng．Novelclusteringalgorithmsbasedon Improved artificial fish swarm algorithm[C]//Proceedings of Sixth InternationalConferenceon Fuzzy Systemsand Know ledge Discovery，2009，3：141-145

[6]Han H，Ding Y S，Hao K R．An evolutionary particle filterw ith the immunegenetic algorithm for intelligentvideo targettracking[J]．Computers &Mathematicsw ith Applications，2011，62（7）：2658-2695．

[7]Musso C，Oudjane N，Legland F，Improving regularized particle filters[D]．SequentialMonte Carlo Methods in Practice，New York：Springer-Verlag，2001．

[8]PARK S，HWANG JP，KIM E．A new evolutionary particle filter for thepreventionofsample improverishment[J]．IEEETransEvolutionary Computation，2009，13（4）：8010-809．

[9]CaiY．Artificial fish schoolalgorithm applied inacombinatorialoptimizationproblem[J]．International Journal of IntelligentSystemsand Applications，2010，2（1）：37-45．

[10]LiLiang-qun，JiHong-bing，Luo Jun-hui．The iterated extended Kalmanparticle filter[C]．Proceedingof IEEE InternationalSymposium on Communicationsand Information Technology，2005：1213-1216．

[11]Yongm ing Cheng，M ingyan Jiang，Dongfeng Yuan．Novelclusteringalgorithmsbased on improved artificial fish swarm algorithm[C]//Proceedings of Sixth InternationalConferenceon Fuzzy Systemsand Know ledge Discovery，2009，3：141-145．

[12]http：//www．ces．clemson．edu/tb/research/headtracker/seq/．Accessed 21Sept2012．

[責(zé)任編輯 代俊秋]

Moving object tracking based on artificial fish particle filtering

ZHANG Tingting，YUM ing，YAN Gang

(Tianjin Key Laboratory of Electronic Materialsand Devices,HebeiUniversity of Technology,Tianjin 300130,China)

In order to improve the precision ofmoving object tracking in video image sequence,artificial fish algorithm is induced into extended Kalman particle filtering.The sampling process isoptim ized by artificial fish algorithm to find theoptimalposition bymaking the particlemoving towards thehighly likelihood region.Then re-sampling process isoptim ized to improvevariety ofparticle,and overcome thedilution ofparticle to improveestimated accuracy ofsystem state. Finally,two-orderautoregressivemodel is constructed to improve the precision ofmoving object tracking by colorhistogram feature.Comparingw ith the standard particle filtering and extended Kalman particle filtering,experimental results based on artificial fish-extended Kalman particle filtering can produce highter precision,Mean and variance of MSE are reduced to 0.113 86 and 0.003 09 respectively.Influenceof Targetocclusion is reduced while tracking themoving object extremely.

moving object tracking;extended kalman particle filtering;artificial fish;colorhistogram

TP391.41

A

1007-2373(2016)04-0012-08

10.14081/j.cnki.hgdxb.2016.04.003

2015-11-17

河北省自然科學(xué)基金（F2015202239）；天津市科技計(jì)劃項(xiàng)目（15ZCZDNC00130）

張婷婷（1984-），女（漢族），講師，博士生．