基于粒子群算法和卡爾曼濾波的運(yùn)動(dòng)目標(biāo)跟蹤算法

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

2、匹配次數(shù)、提高實(shí)時(shí)性,利用粒子群算法在搜索區(qū)域找到和目標(biāo)模板最相似的區(qū)域,從而找到最優(yōu)中心位置,并以該位置作為卡爾曼濾波的觀測(cè)值,進(jìn)行下一幀跟蹤。仿真實(shí)驗(yàn)結(jié)果表明新算法顯著提高了跟蹤的實(shí)時(shí)性、精確性,并對(duì)部分遮擋能較好地處理。關(guān)鍵詞:粒子群算法;卡爾曼濾波;運(yùn)動(dòng)目標(biāo)跟蹤;灰度統(tǒng)計(jì)特性中圖分類號(hào):TN911 34;TP391.41 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):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 引 言計(jì)算機(jī)視覺領(lǐng)域中,運(yùn)動(dòng)目標(biāo)跟蹤是關(guān)鍵問題之一,其在視頻編碼、視頻監(jiān)控、軍事、交通等領(lǐng)域有著重要而廣泛的應(yīng)用1。目標(biāo)跟蹤,就是在一段圖像序列的每幅圖像中找到所感興趣的運(yùn)動(dòng)目標(biāo)所處的位置,從而達(dá)到跟蹤的目的。跟蹤算法的實(shí)時(shí)性取決于匹配搜索策略和濾波預(yù)測(cè)算法,跟蹤算法

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

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

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

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

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

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

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

14、方誤差陣,由上可知時(shí)間更新方程主要完成預(yù)測(cè)。離散卡爾曼濾波器的測(cè)量更新方程為: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為觀測(cè)值,它聯(lián)合增益矩陣Kk來修正一步預(yù)測(cè)值xk|k-1,即由觀測(cè)變量更新估計(jì);Pk用來更新誤差協(xié)方差。1.2 粒子群算法粒子群算法最早是在1995年由Eberhart和Ken nedy共同提出的,其基本思想源于對(duì)鳥類群體行為的研究6。假設(shè)一個(gè)場(chǎng)景:一群鳥在某一區(qū)域搜索食物,但是它們都不知道食物的具體位置,而知道當(dāng)前的位置離食物到底有多遠(yuǎn)

15、,這樣,找到食物最有效的方法就是搜索當(dāng)前離食物最近的鳥的周圍區(qū)域。PSO就是基于 b(x)-inu,u=0,1,2, ,m-1。其中b(xi)是第8期竇永梅等:基于粒子群算法和卡爾曼濾波的運(yùn)動(dòng)目標(biāo)跟蹤算法135位于點(diǎn)xi灰度值特征映射函數(shù),設(shè)該點(diǎn)灰度值為g,則b(xi)=g;x表示取不大于x的整數(shù); ( )為L(zhǎng)Kroneckerdelta函數(shù);n是目標(biāo)模板的像素總數(shù)。相應(yīng)的,假設(shè)中心點(diǎn)在y點(diǎn),則候選目標(biāo)的灰度特征可以表示為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是候選目標(biāo)區(qū)域的像素點(diǎn)數(shù)來度量目標(biāo)模板與候選目標(biāo)區(qū)域的相似性,其定義為:m-13 實(shí)驗(yàn)結(jié)果與分析該算法實(shí)現(xiàn)都在Matlab7.0.1環(huán)境下,采用CAVIAR數(shù)據(jù)集中WalkByShop1front和OneLeave ShopReenter2cor兩段視頻測(cè)試序列為實(shí)驗(yàn)對(duì)象。視頻序列的分辨率都為384 288,第一段視頻序列中的跟蹤目標(biāo)為視頻中出現(xiàn)的一個(gè)行人,跟蹤從820幀開始到900幀結(jié)束,在820幀中由人工選定模板,大小為50 130像素,用矩形框來定位表示,實(shí)驗(yàn)中目標(biāo)搜索區(qū)域的寬w設(shè)為32個(gè)像素,高h(yuǎn)也設(shè)為32個(gè)像素?？柭鼮V波的初始化為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)于是,跟蹤過程中的目標(biāo)定位問題轉(zhuǎn)化成了求使上式取得極大值的候選目標(biāo)區(qū)域的問題。當(dāng) (y)越接近1,表示目標(biāo)與候選區(qū)域越相似;當(dāng) (y)=1時(shí),表示目標(biāo)和候選區(qū)域完全相似。式(11)是作為粒子群算法采用的適應(yīng)度函數(shù)。2.2 粒子群與卡爾曼濾波的結(jié)合利用Kalman濾波可以預(yù)測(cè)跟蹤目標(biāo)在下一幀圖像的位置,其中心點(diǎn)設(shè)為(x0,y0),以該點(diǎn)為中心,取寬度為

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

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

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

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