1、2011年4月15日第34卷第8期ModernElectronicsTechnique現代電子技術Apr.2011Vol.34No.8基于粒子群算法和卡爾曼濾波的運動目標跟蹤算法竇永梅,冀小平,杜肖山(太原理工大學信息工程學院,山西太原 030024)摘 要:針對目前一些常用的運動目標跟蹤算法存在跟蹤精度不高、實時性低、對遮擋問題處理不佳等問題,提出一種粒子群算法與卡爾曼濾波相結合的新的運動目標跟蹤方法。利用卡爾曼濾波預測目標中心在下一幀圖像中的位置,從而極大減少了搜索范圍,并以該位置為中心建立目標搜索區域。然后以目標的灰度統計特征對目標模板和候選區域進行匹配,確保跟蹤準確性。為了有效減少搜索

2、匹配次數、提高實時性,利用粒子群算法在搜索區域找到和目標模板最相似的區域,從而找到最優中心位置,并以該位置作為卡爾曼濾波的觀測值,進行下一幀跟蹤。仿真實驗結果表明新算法顯著提高了跟蹤的實時性、精確性,并對部分遮擋能較好地處理。關鍵詞:粒子群算法;卡爾曼濾波;運動目標跟蹤;灰度統計特性中圖分類號:TN911 34;TP391.41 文獻標識碼:A 文章編號:1004 373X(2011)08 0133 04TrackingAlgorithmofMovingObjectBasedonParticleSwarmOptimizationandKalmanFilterDOUYong mei,JIXiao

3、 ping,DUXiao shan(CollegeofInformationEngineering,TaiyuanUniversityofTechnology,Taiyuan030024,China)Abstract:Aimingattheinaccuracy,lowreal timeandpoortreatmentofcommonlyusedtrackingalgorithmofmovingob ject,anewtrackingalgorithmofmovingobjectbasedonparticleswarmoptimization(PSO)andKalmanfilterispropo

4、sed.ThepossiblepositionofmovingtargetcenterinthenextframeimageispredictedbyKalmanfilter,whichreducedthesearchscopegreatlyandsetsearchregionoftargetwhichisgeneratedaroundthecenterposition.Thenmatchingthetargettemplateandthecandidateregionswiththegraystatisticalcharacteristicstoensurethetrackingaccura

5、cy.Inordertoreducethesearchformatchingandimprovereal timeperformance,PSOisutilizedtosearchthebestareawhichismostsimilartothetargettemplateinthesearchregion,asaresult,theoptimalcenterisfoundandthebestpositionisusedasanobservedvalueofKalmanfilterfornextprediction.Theexperimentalresultsshowthatthenewme

6、thodiseffectiveandrobustandcanhandlepartialocclusionbetter.Keywords:particleswarmoptimization(PSO);Kalmanfilter;trackingofmovingobject;graystatisticalcharacteristic0 引 言計算機視覺領域中,運動目標跟蹤是關鍵問題之一,其在視頻編碼、視頻監控、軍事、交通等領域有著重要而廣泛的應用1。目標跟蹤,就是在一段圖像序列的每幅圖像中找到所感興趣的運動目標所處的位置,從而達到跟蹤的目的。跟蹤算法的實時性取決于匹配搜索策略和濾波預測算法,跟蹤算法

7、的精度和魯棒性很大程度上取決于對運動目標的表達和相似性度量的定義。但迄今為止,運動目標跟蹤算法的魯棒性、準確性和實時性的統一仍是尚未解決好和正在努力追求的目標。目前常用的跟蹤算法如均值漂移算法(Meanshift)在目標跟蹤過程中沒有利用目標在空間中的運動方向和運動速度信息,當周圍環境存在干擾(如光線、遮擋)或運動速度過快時容易丟失目標。連續自適應均值漂移算法(Camshift)在均值漂移算法的基礎上雖結合目標色彩信息進行了改進,但需在開始前由人工指定跟蹤目標2。粒子濾波算法在非線性、非高斯系統取得了較好的跟蹤效果但計算量相對較大,實時性有待提高。而Kalman濾波算法可以方便地預測目標的位置

8、和速度,具有穩定、計算量小的特點,但是單純使用Kalman濾波跟蹤準確性不高。文獻3中提出了一種基于遺傳算法和卡爾曼濾波的運動目標跟蹤算法,取得較好的效果。粒子群算法是一種高效的搜索算法,具有實現方便、收斂速度快、參數設置少的優點。與遺傳算法比較,所有的粒子在大多數情況下可能更快的收斂于最優值4。綜合以上考慮,本文提出了粒子群算法和卡爾曼相結合的新的運動目標跟蹤算法。利用卡爾曼濾波預測目標中心在下一幀圖像中的位置,并以該位置為中心建立目標搜索區域。然后以目標的灰度統計特征對目標,134現代電子技術2011年第34卷群算法在搜索區域找到和目標模板最相似的區域,粒子所在的位置即為最優中心位置,并以

9、該位置作為卡爾曼濾波的觀測值,進行下一幀跟蹤。1 算法原理依據1.1 卡爾曼濾波卡爾曼濾波是由一系列遞推數學公式描述。其信號模型是由離散的狀態方程和觀測方程組成的5。設離散時間過程狀態變量x R,狀態方程可描述為:xk=Axk-1+Buk-1+wk-1(1)式中:xk是在k時刻系統的n維狀態矢量;A是系統從k-1時刻到k時刻的n n一步狀態轉移矩陣;n l階矩陣B代表可選的控制輸入u Rl的增益;wk-1為k-1時刻時的過程激勵噪聲。設觀測變量z R,得到觀測方程:zk=Hxk+vkm n階觀測矩陣;vk是觀測噪聲。離散卡爾曼濾波器的工作原理,算法的具體實現是由時間更新方程和測量更新方程來實現

10、。具體形式如下:離散卡爾曼濾波器的時間更新方程:xkk-1=Axk-1+Buk-1T5mn一只鳥可以看作是每一個優化問題的解,也就是 粒子 ,所有的粒子都有一個被優化的適應值,每一個粒子還有一個速度v來確定它們飛行的方向和距離。然后,粒子們像鳥群在離食物最近的鳥周圍搜索一樣,追隨當前最優粒子(離食物最近的鳥)在解空間中搜索7。PSO在每次的搜索過程中,粒子通過跟蹤兩個極值來更新自己:一個為粒子自身所找到的最優解,稱為個體極值Pbest,另一個為整個種群當前找到的最優解,稱為全局極值Gbest。例如,在一個D維的目標搜索空間中,每個粒子看成是空間內的一個點,設群體由m個粒子構成。設zi=(zi1

11、,zi2, ,ziD)為第i個粒子(i=1,2, ,m)的D維位置根據設定的矢量,根據設定的適應值函數計算zi當前的適應值,可衡量粒子位置的優劣;vi=(vi1,vi2, ,vid, ,viD)為粒子i的飛行速度,即粒子移動的距離;pb=(pb1,pb2, ,pbd, ,pbD)為粒子迄今為止搜索到的最優位置;pg=(pg1,pg2, ,pgd, ,pgD)為整個粒子群迄今為止搜索到的最優位置。在每次迭代中,粒子根據以下式子更新速度和位置:1kkvk+id=wvkid+c1r1(pbd-zid)+c2r2(pgd-zid)(8)zid=zid+vid(9)式中:i=1,2, ,m;d=1,2,

12、 ,D;k為迭代次數,r1和r2為0,1之間的隨機數;c1和c2為學習因子;由于粒子群算法中沒有實際的機制來控制粒子的速度,所以有必要對速度的最大值進行限制,設其為vmax,位置zi的取值范圍為zminzmax;w為慣性權重,它起著權衡局部最優能力和全局最優能力的作用。大量實驗表明,不把慣性權重設為定值,而是設為一個隨時間線性減少的函數效果更好,慣性權重的函數形式通常為:maxmink(10)w=wmax-itermax式中:wmax為初始權重;wmin為最終權重;k為當前迭代次數;itermax為最大迭代次數2 算法的具體實現過程2.1 目標灰度特征和粒子群適應度函數目標灰度特征對目標的形變

13、、旋轉等不敏感,具有良好的穩定性。在目標圖像和候選圖像匹配過程中,采用圖像的灰度特征進行匹配8。設圖像灰度級為L(0L-1),一般L為256。為加快運算速度,提高跟蹤實時性,把灰度級映射為m級,如m=8,即把灰度級劃分為8個級別。則目標模板直方圖特征可表示為:q=qu,u=0,1,2, ,m-1。qu=i=14k+1kk+1(2)式中:zk是k時刻的m維觀測信號矢量;H是k時刻的(3)式中:xk|k-1Pk|k-1=APk-1A+Q(4)為狀態一步預測矢量,即向前推算狀態變量;xk-1為k-1時刻的狀態濾波值;Pk|k-1為一步預測均方誤差陣,即向前推算誤差協方差;Pk-1為k-1時刻的濾波均

14、方誤差陣,由上可知時間更新方程主要完成預測。離散卡爾曼濾波器的測量更新方程為:Kk=Pk|k-1H(HPk|k-1H+R)xk=xk|k-1+Kk(zk-Hxk|k-1)Pk=(I-KkH)Pk|k-1TT-1(5)(6)(7)。式中:Kk為濾波增益矩陣;zk為觀測值,它聯合增益矩陣Kk來修正一步預測值xk|k-1,即由觀測變量更新估計;Pk用來更新誤差協方差。1.2 粒子群算法粒子群算法最早是在1995年由Eberhart和Ken nedy共同提出的,其基本思想源于對鳥類群體行為的研究6。假設一個場景:一群鳥在某一區域搜索食物,但是它們都不知道食物的具體位置,而知道當前的位置離食物到底有多遠

15、,這樣,找到食物最有效的方法就是搜索當前離食物最近的鳥的周圍區域。PSO就是基于 b(x)-inu,u=0,1,2, ,m-1。其中b(xi)是第8期竇永梅等:基于粒子群算法和卡爾曼濾波的運動目標跟蹤算法135位于點xi灰度值特征映射函數,設該點灰度值為g,則b(xi)=g;x表示取不大于x的整數; ( )為LKroneckerdelta函數;n是目標模板的像素總數。相應的,假設中心點在y點,則候選目標的灰度特征可以表示為p(y)=pu(y),u=0,1,2, ,m-1。其中pu(y)=n9i=1b(x)-i3nu,u=0,1,2, ,m-1,。采用Bhattacharyya系圖2 程序流程圖

16、xi是候選目標區域的像素點數來度量目標模板與候選目標區域的相似性,其定義為:m-13 實驗結果與分析該算法實現都在Matlab7.0.1環境下,采用CAVIAR數據集中WalkByShop1front和OneLeave ShopReenter2cor兩段視頻測試序列為實驗對象。視頻序列的分辨率都為384 288,第一段視頻序列中的跟蹤目標為視頻中出現的一個行人,跟蹤從820幀開始到900幀結束,在820幀中由人工選定模板,大小為50 130像素,用矩形框來定位表示,實驗中目標搜索區域的寬w設為32個像素,高h也設為32個像素。卡爾曼濾波的初始化為10:R=0.2845,0.0045 ,0.00

17、45,0.0455 ;Q=0.01*eye(4);P0=100*eye(4);A=1,0,0,0 ,0,1,0,0 ,dt,1,0,0 ,0,dt,0,1 ;H=1,0 ,0,1 ,0,0 ,0,0 (y)= p(y)q=u=0u(y)qu(11)于是,跟蹤過程中的目標定位問題轉化成了求使上式取得極大值的候選目標區域的問題。當 (y)越接近1,表示目標與候選區域越相似;當 (y)=1時,表示目標和候選區域完全相似。式(11)是作為粒子群算法采用的適應度函數。2.2 粒子群與卡爾曼濾波的結合利用Kalman濾波可以預測跟蹤目標在下一幀圖像的位置,其中心點設為(x0,y0),以該點為中心,取寬度為

18、w,高度為h的區域為搜索區域(如圖1所示),也就是要在該區域找到和目標模板最相似的候選區域中心點。為了使用粒子群算法和卡爾曼濾波相結合,在該區域中心點(x0,y0)的周圍撒一些粒子,如圖1所示,再以每個粒子為中心,分別建立寬度為w,高度為h的搜索區域,這樣就形成了m(粒子群規模)個候選區域,而以上知道粒子群的適應度函數為目標模板和候選區域的灰度特征相似性,這樣就可以應用粒子群算法求一個最優解,即與目標模板最相似的運動目標中心(pg1,pg2),將這個最優解賦值給式(6)中的zk,再與Hxk|k-1做差,得到的差值結合增益Kk來修正卡爾曼的狀態一步預測值xk|k-1,得到當前時刻的狀態濾波值xk

19、,得到的xk再代入式(3)進行下一步的預測。具體的程序流程圖如圖2所示。矩陣A中dt=1,粒子群算法的種群大小設定為8,其中初始種群中一個點為卡爾曼預測的目標區域中心位置點,其他七個點在其周圍隨機選定。粒子群迭代總代數為30,c1=c2=1.4962,慣性權重中wmax=0.9,wmin=0.4。設在一代群體中,如果適應度最高的個體其適應度函數值大于設定的閾值0.88就停止迭代,表示已搜索到目標。當粒子群算法迭代次數達到最大迭代次數時,如果所有個體適應度函數值較小,可推測目標被部分遮擋,當最優個體適應度函數值低于0.65,則可推測目標被嚴重遮擋,在這兩種情況下,直接把卡爾曼濾波的預測結果作為最

20、優值來處理。因文中采用的粒子群算法為連續優化算法,而圖像像素位置為整數值,所以迭代過程中用floor函數對粒子的位置進行近似取整以對其候選區域精確化。實驗表明此處理并不影響跟蹤效果,結果如圖3所示。從圖3可以看出跟蹤目標與圖像背景比較相似,這種情況下利用本文的算法還是取得了較好的跟蹤效果,只是在處理部分幀的情況下需要一定的運算時間,但是在實驗中,平均每秒可以處理10幀左右的圖像,可以基本滿足跟蹤實時性的要求。本文的粒子群與卡爾曼結合的算法還能有效處理,幀,從圖1 候選目標中心搜索區域136中挑選幾幀跟蹤實驗結果如圖4所示。現代電子技術2011年第34卷跟蹤效果,一般當運動目標運動速度快,方向變

21、換頻繁時,搜索區域設置要大。4 結 語本文運用卡爾曼濾波預測運動目標中心在下一幀中可能出現的位置,結合目標灰度統計特性,以候選區域與目標模板的相似度作為粒子群算法的適應值函數,實行精確搜索,使運算速度大大加快,基本滿足了跟蹤的實時性和魯棒性,并能處理部分遮擋以及短暫的全部遮擋。如何解決多目標跟蹤,以及更加復雜的遮擋問題,進一步提高跟蹤實時性是本文下一步的研究方向。圖3 WalkByShop1front測試序列跟蹤結果參 考 文 獻1COLLNSR,LIPTONA,KANADEANDT.AsystemforvideosurveillanceandmonitoringVSAMfinalreportR.CarnegieMellonUniversity,2000.2李洪海.一種改進的CAMShift目標跟蹤算法J.現代電子技術,2010,33(16):106 108.3胡建華,徐健健.一種基于遺傳算法和卡爾曼濾波的運動目標跟蹤方法J.計算機應用,2007,27(4):916 918.4紀震,廖惠蓮,吳青華.粒子群算法及應用M.北京:科學出版社,2009.5趙樹杰,趙建勛.信號檢測與估計理論M.北京:清華大學出版社,2008.圖4 OneLeaveShopReenter2cor測試序列跟蹤結果6胡煒薇,楊雷,楊莘元,等.粒子群算法在多傳感器多目標跟蹤