蟻群優(yōu)化粒子濾波視覺(jué)跟蹤算法

苗 彬,侯 燕

(1. 山東警察學(xué)院人事處,山東 濟(jì)南 250014;2. 山東警察學(xué)院計(jì)算機(jī)系,山東 濟(jì)南 250014)

視覺(jué)跟蹤是計(jì)算機(jī)視覺(jué)領(lǐng)域的熱點(diǎn)及難點(diǎn)研究?jī)?nèi)容,是實(shí)現(xiàn)高層次視覺(jué)行為分析的基礎(chǔ). 它是指對(duì)圖像或視頻序列中的運(yùn)動(dòng)目標(biāo)進(jìn)行檢測(cè)、提取、識(shí)別和跟蹤,來(lái)獲得運(yùn)動(dòng)目標(biāo)的運(yùn)動(dòng)參數(shù)信息,以做進(jìn)一步的分析,實(shí)現(xiàn)對(duì)運(yùn)動(dòng)目標(biāo)的行為理解等更高一級(jí)的視覺(jué)任務(wù)[1]. 目前,在粒子濾波算法[2-4]的框架內(nèi)實(shí)現(xiàn)魯棒、快速、準(zhǔn)確的人體跟蹤成為研究者關(guān)注的主要問(wèn)題,這主要是由于粒子濾波算法可以有效處理復(fù)雜場(chǎng)景中的目標(biāo)遮擋、交互等難題,從而為目標(biāo)交互行為分析提供基礎(chǔ). 粒子濾波算法中的2個(gè)關(guān)鍵步驟是建議分布的設(shè)計(jì)和再采樣方法的選擇. 在解決不同的跟蹤難題時(shí),研究者根據(jù)目標(biāo)的外觀特征和動(dòng)力學(xué)模型融合粒子濾波算法框架來(lái)設(shè)計(jì)不同的跟蹤算法. Isard等[2]首次使用粒子濾波算法(Condensation算法)解決視覺(jué)跟蹤問(wèn)題,許多研究者以Condensation算法的工作為基礎(chǔ),提出了多種有效地處理視覺(jué)跟蹤難題的改進(jìn)算法. Kwon等[3]針對(duì)單目標(biāo)跟蹤問(wèn)題,提出一種基于仿射群的粒子濾波跟蹤方法. 在建立目標(biāo)狀態(tài)空間模型時(shí),該算法使用仿射群作為狀態(tài),狀態(tài)轉(zhuǎn)移模型定義為一種幾何自回歸過(guò)程. 在設(shè)計(jì)建議分布時(shí),通過(guò)將建議分布近似為高斯分布,采用局部線性化觀測(cè)方程的方式,得到觀測(cè)方程的一階泰勒展開(kāi)式,其思想類似于擴(kuò)展卡爾曼濾波器(Extended Kalman Filter,EKF),在計(jì)算雅可比矩陣的時(shí)候,非常耗費(fèi)時(shí)間. 文中提出的算法在單目標(biāo)跟蹤中比Condensation算法效果要好. Duffne等[4]針對(duì)考慮多種目標(biāo)特征而引起的狀態(tài)空間維數(shù)過(guò)高的問(wèn)題,提出一種基于動(dòng)態(tài)分治采樣策略(DPS)的粒子濾波算法. DPS策略將高維狀態(tài)空間切分成若干個(gè)子空間,每一個(gè)子空間對(duì)應(yīng)一種目標(biāo)特征,采樣粒子時(shí)使用分層方式在各子空間中進(jìn)行采樣. 在子空間中采樣的順序則是根據(jù)各目標(biāo)特征的可靠性來(lái)進(jìn)行排序,可靠性高的先采樣,以此類推. 目標(biāo)特征的可靠性依據(jù)該特征從背景中區(qū)別出目標(biāo)的能力進(jìn)行度量. DPS-PF算法能夠在復(fù)雜的場(chǎng)景中準(zhǔn)確地跟蹤目標(biāo),具有較好的魯棒性. Li等[5]提出一種漸進(jìn)自調(diào)整粒子濾波算法,應(yīng)用于仿射群上的視覺(jué)目標(biāo)跟蹤. 在該算法框架中,使用尺度不變變換特征來(lái)描述目標(biāo)特征,采用漸進(jìn)主成分分析方法學(xué)習(xí)自適應(yīng)外觀子空間以產(chǎn)生相似性度量,實(shí)驗(yàn)結(jié)果證明該算法能夠以較少的粒子數(shù)獲得較好的魯棒性和高精確度的跟蹤結(jié)果. 文獻(xiàn)[6]針對(duì)目標(biāo)外觀及姿態(tài)變化較大的目標(biāo)跟蹤問(wèn)題,提出了基于記憶的粒子濾波算法,該算法在粒子濾波算法的框架內(nèi)引入基于記憶的機(jī)制來(lái)預(yù)測(cè)先驗(yàn)分布,即:使用歷史目標(biāo)狀態(tài)序列實(shí)現(xiàn)目標(biāo)位姿和外觀的同時(shí)估計(jì). 李培華[7]提出了一種基于自適應(yīng)剖分顏色空間的概率模型和推廣積分圖像的粒子濾波跟蹤算法,旨在處理短時(shí)遮擋等難題,并取得了較好的跟蹤效果. Khan等[8]基于粒子濾波算法框架,采用馬爾科夫隨機(jī)場(chǎng)運(yùn)動(dòng)先驗(yàn)?zāi)Ｐ?并結(jié)合馬氏鏈蒙特卡羅方法,實(shí)現(xiàn)靜態(tài)背景下的可變數(shù)目的多交互目標(biāo)跟蹤問(wèn)題,但Khan所提出的方法僅能適用于靜態(tài)背景下的跟蹤問(wèn)題,其實(shí)驗(yàn)的場(chǎng)景是跟蹤托盤上的數(shù)只螞蟻,具有較大的局限性.

為了解決傳統(tǒng)的粒子濾波跟蹤算法中再采樣方法引起的粒子貧乏問(wèn)題,提高跟蹤的準(zhǔn)確性,本文提出了蟻群優(yōu)化粒子濾波跟蹤算法.該算法采用蟻群優(yōu)化的思想改進(jìn)傳統(tǒng)粒子濾波算法的再采樣過(guò)程,從而避免樣本貧乏現(xiàn)象引起的失跟問(wèn)題,提高算法的跟蹤成功率.

1 粒子濾波算法

假設(shè)k時(shí)刻系統(tǒng)的狀態(tài)為xk,觀測(cè)值序列為y1:k={y1,y2,…，yk},粒子濾波算法的基本思想是用一組由N個(gè)帶權(quán)粒子構(gòu)成的集合近似后驗(yàn)概率密度p(xk-1|y1:k-1),即:

(1)

(2)

粒子濾波算法中的一個(gè)關(guān)鍵步驟是再采樣步驟,將權(quán)值較小的粒子剔除,保留并復(fù)制權(quán)值較大的粒子,可以抑制退化現(xiàn)象的影響. 但是,當(dāng)粒子集合中只有少數(shù)粒子權(quán)值較大時(shí),再采樣過(guò)程將僅集中到少數(shù)的粒子上,使得粒子多樣性缺失,出現(xiàn)樣本貧乏現(xiàn)象. 目前的解決方法是在再采樣之后引入一個(gè)馬氏鏈蒙特卡羅采樣步驟,來(lái)恢復(fù)粒子多樣性,但計(jì)算復(fù)雜性非常高. 本文將引入蟻群優(yōu)化算法[9]的思想來(lái)取代再采樣,通過(guò)模擬螞蟻覓食路徑的構(gòu)建過(guò)程,來(lái)模擬粒子在狀態(tài)空間中傳遞的過(guò)程,這樣就可以避免樣本貧乏現(xiàn)象的出現(xiàn).

2 基于蟻群優(yōu)化的粒子濾波算法

圖1 基于蟻群優(yōu)化的粒子濾波算法

(3)

每一只螞蟻都以一定的概率訪問(wèn)搜索空間中的粒子,并最終確定在下一個(gè)時(shí)刻的位置. 搜索空間中共N個(gè)粒子,但最終能吸引螞蟻的粒子總數(shù)不一定為N,粒子的權(quán)值越大,吸引的螞蟻就越多.

步驟3:當(dāng)所有的螞蟻全部訪問(wèn)搜索空間后,重新對(duì)已經(jīng)聚集了螞蟻的粒子的權(quán)值進(jìn)行歸一化,移除沒(méi)能吸引螞蟻的粒子.

步驟4:根據(jù)蟻群優(yōu)化算法中的更新步驟,更新信息素,信息素為螞蟻的協(xié)方差.

步驟5:根據(jù)相應(yīng)的粒子生成策略得到N個(gè)k-1時(shí)刻的最終粒子,并計(jì)算系統(tǒng)狀態(tài)估計(jì)值.

經(jīng)過(guò)以上步驟之后,得到了當(dāng)前時(shí)刻的粒子集合,基于該粒子集合近似后驗(yàn)概率密度p(xk-1|y1:k-1),然后估計(jì)當(dāng)前時(shí)刻目標(biāo)的位置信息.

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

本節(jié)采用5個(gè)視頻序列來(lái)評(píng)價(jià)本文提出算法的性能,如表1所示. 將本文算法與基本粒子濾波算法(PF)[2]、MCMC-PF算法[8]進(jìn)行對(duì)比,從定性和定量2個(gè)方面進(jìn)行分析.

表1 實(shí)驗(yàn)視頻序列

3.1 定性分析

在其中的Face序列上的跟蹤結(jié)果如圖2所示,從上到下依次為本文算法、PF、MCMC-PF. 結(jié)果顯示本文算法能夠持續(xù)準(zhǔn)確的跟蹤人臉,而其他2種算法則頻繁失去人臉,MCMC-PF算法比PF稍好. 在Marry序列上的跟蹤結(jié)果如圖3所示,從上到下依次為本文算法、PF、MCMC-PF. 從該圖可以看出,本文算法在目標(biāo)發(fā)生旋轉(zhuǎn)、遮擋時(shí)仍然能準(zhǔn)確的跟蹤目標(biāo),表現(xiàn)出較好的魯棒性. 在其他3個(gè)序列上的跟蹤結(jié)果分別如圖4～6所示.

分別為第3，19，28，30幀

分別為第33，107，173，250幀

分別為第16，19，26，28，31幀

分別為第17，18，24，26幀

分別為第69，303，458，512幀

3.2 定量分析

在定量分析實(shí)驗(yàn)中,考察算法在5個(gè)視頻序列上的跟蹤成功率. 首先定義跟蹤成功為:算法估計(jì)的目標(biāo)區(qū)域中心與目標(biāo)真實(shí)區(qū)域位置中心距離小于目標(biāo)真實(shí)區(qū)域?qū)挾鹊亩种? 跟蹤成功率定義為算法成功跟蹤到目標(biāo)的幀數(shù)與視頻序列總幀數(shù)之比. 實(shí)驗(yàn)結(jié)果如表2所示. 本文算法在2個(gè)視頻序列上的跟蹤成功率為91.53%,明顯高于其他2種算法.

表2 算法跟蹤成功率對(duì)比

4 結(jié) 論

本文提出一種基于蟻群優(yōu)化方法的粒子濾波算法. 在粒子濾波算法框架內(nèi),取代傳統(tǒng)的再采樣方法,避免了樣本貧乏現(xiàn)象的出現(xiàn),在跟蹤過(guò)程中可以提高算法的跟蹤準(zhǔn)確性和魯棒性,有效處理遮擋、交互等跟蹤難題. 實(shí)驗(yàn)結(jié)果表明本文提出的算法與傳統(tǒng)的粒子濾波算法相比,表現(xiàn)出出色的跟蹤性能.

參考文獻(xiàn):

[1] 侯志強(qiáng),韓崇昭. 視覺(jué)跟蹤技術(shù)綜述[J]. 自動(dòng)化學(xué)報(bào),2006,32(4):603-617.

[2] Isard M,Blake A. Condensation-conditional density propagation for visual tracking[J]. International Journal of Computer Vision,1998,28(1):5-28.

[3] Kwon J,Lee K,Park F. Visual Tracking via Geometric Particle Filtering on the Affine Group with Optimal Importance Functions[C]//Proceedings of International Conference on Computer Vision and Pattern Recognition. Miami: IEEE,2009:991-998.

[4] Duffner S,Odobez J. Dynamic Partitioned Sampling for Tracking with Discriminative Features[C]//Proceedings of British Machine Vision Conference. London: BMVA,2009:710-718.

[5] Li Min,Chen Wei,Huang Kaiqi,et al. Visual Tracking via Incremental Self-tuning Particle Filtering on the Affine Group[C]//Proceedings of International Conference on Computer Vision and Pattern Recognition. San Francisco: IEEE,2010:1315-1322.

[6] Mikami D,Otsuka K,Yamato J.Memory-based particle filter for tracking objects with large variation in pose and appearance[C]//Proceedings of European Conference on Computer Vision. Greece: Springer,2010:215-228.

[7] 李培華. 一種新穎的基于顏色信息的粒子濾波器跟蹤算法[J]. 計(jì)算機(jī)學(xué)報(bào),2009,32(12):2454-2463.

[8] Khan Z,Balch T,Dellaert F. MCMC-based particle filtering for tracking a variable number of interacting targets[J]. Pattern Analysis and Machine Intelligence,2005,27(11):1805-1819.

[9] Dorigo M,Stutzle T. 蟻群優(yōu)化[M]. 北京:清華大學(xué)出版社,2007.