運動目標追蹤的人工魚群優化粒子濾波算法

張婷婷，于 明，閻 剛

（河北工業大學 天津市電子材料與器件重點實驗室，天津 300130）

運動目標追蹤的人工魚群優化粒子濾波算法

張婷婷，于 明，閻 剛

（河北工業大學 天津市電子材料與器件重點實驗室，天津 300130）

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

運動目標跟蹤；擴展卡爾曼粒子濾波；人工魚群；顏色直方圖

0 引言

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

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

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

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

1 擴展卡爾曼粒子濾波

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

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

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

圖1 窄的似然函數Fig.1 Situation of narrow likelihood function

圖2 似然函數位于先驗概率分布尾部Fig.2 Likelihood function located in the tailof prioriprobability

2 人工魚群算法

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

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

3 基于人工魚群優化的擴展卡爾曼粒子濾波算法

將人工魚群算法引入到擴展卡爾曼粒子濾波算法中，把粒子當作人工魚，魚群通過不斷更新自己的位置來隨機尋找高食物濃度的區域，把似然度當作食物濃度，當人工魚沒有發現相對自身較高的濃度區域時，他們會不斷地隨機游動直到搜索到高濃度區域．再優化采樣過程和重采樣過程，使粒子集通過似然函數調節不斷向真實狀態值移動．

通過人工魚群算法優化覓食和聚群行為，粒子集不斷向系統中最優粒子靠近，智能粒子集群則向高似然區域移動，如圖3所示，從而解決粒子退化和貧化問題，可以提高濾波精度．對動態系統進行一階線性化近似，縮小與真實后驗分布產生樣本的偏差．當迭代次數達到設定上限或人工魚群的最優值符合某閾值時，表明人工魚群已經分布在真實狀態附近，則停止優化．此時再利用最新觀測值對粒子集進行權重更新并做歸一化處理．

圖3 人工魚群優化過程Fig.3 Processof artificial fish schoolalgorithm optimization

基于人工魚群優化的擴展卡爾曼粒子濾波算法（AFSA-EKPF）：

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

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

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

對覓食行為和聚群行為進行建模尋找局部最優，設定閾值和迭代上限，當目標函數的偏差小于某閥值，或者迭代次數達到設定上限時終止算法．

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

Step8：當k=k+1時，跳轉至Step2．

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

4 實驗結果分析

為了驗證本文算法的有效性，首先對比了標準粒子濾波（PF）、擴展卡爾曼粒子濾波（EKPF）、人工魚群優化擴展卡爾曼粒子濾波算法（AFSA-EKPF）的濾波實驗，然后將粒子濾波應用于目標跟蹤，對比分析了運動目標遮擋下的目標追蹤實驗．

4.1 粒子濾波實驗及分析

進行人工魚群優化擴展卡爾曼粒子濾波算法（AFSA-EKPF）仿真實驗，并與標準粒子濾波（PF）、擴展卡爾曼粒子濾波（EKPF）進行對比分析，系統模型如公式 (8)、公式 (9)

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

圖4 PF的狀態估計曲線Fig.4 Stateestimation curveof PF

圖5 EKPF的狀態估計曲線Fig.5 Stateestimation curveof EKPF

圖4，圖5，圖6分別是PF、EKPF和AFSA-EKPF的狀態估計曲線，圖7為一次獨立實驗條件下的3種算法的狀態估計曲線，圖8為3種算法進行100次獨立實驗的均方誤差曲線，表1為3種算法進行100次獨立實驗的均方誤差均值和方差．

圖6 AFSA-EKPF的狀態估計曲線Fig.6 Stateestimation curveof AFSA-EKPF

圖7 PF、EKPF和AFSA-EKPF的狀態估計曲線Fig.7 Stateestimation curveof PF,EKPFand AFSA-EKPF

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

圖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 目標跟蹤實驗

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

其中：K為歸一化常數； 為Kroneckerdelta函數．

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

圖9 視頻1跟蹤結果Fig.9 Tracking resultsof the Video 1

圖10 視頻2跟蹤結果Fig.10 Tracking resultsof the Video 2

視頻2是人在走動時被另外一個目標遮擋的情況．從圖10a）可看出在行人在未被遮擋前標準的粒子濾波算法可以穩定的跟蹤目標，但是在17到19幀中被遮擋時跟蹤效果失敗．從圖10b）中可以看出本文提出的算法在整個目標運動中都能準確的跟蹤目標，由于改善了粒子分布情況，增加了目標狀態的多樣性，從而在目標的運動狀態發生變化（被遮擋）的情況下也具有較好的效果．

5 結論

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

[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]．電視技術，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．

[責任編輯 代俊秋]

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

河北省自然科學基金（F2015202239）；天津市科技計劃項目（15ZCZDNC00130）

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