基于Kalman和雙級(jí)聯(lián)隨機(jī)森林的在線(xiàn)目標(biāo)跟蹤算法

李 婷，趙文杰，楊 帥，李 成

(空軍航空大學(xué) 航空航天情報(bào)系，吉林 長(zhǎng)春 130000)

?

基于Kalman和雙級(jí)聯(lián)隨機(jī)森林的在線(xiàn)目標(biāo)跟蹤算法

李 婷，趙文杰，楊 帥，李 成

(空軍航空大學(xué) 航空航天情報(bào)系，吉林 長(zhǎng)春 130000)

針對(duì)傳統(tǒng)的基于檢測(cè)的在線(xiàn)目標(biāo)跟蹤算法容易產(chǎn)生跟蹤漂移的現(xiàn)象，提出了一種新的在線(xiàn)目標(biāo)跟蹤算法。以基于主方向模板特征的雙級(jí)聯(lián)隨機(jī)森林分類(lèi)器作為檢測(cè)器，卡爾曼濾波器作為跟蹤器。首先利用卡拉曼算法跟蹤目標(biāo)，然后以跟蹤的目標(biāo)位置為中心向外擴(kuò)展一定的范圍作為雙級(jí)聯(lián)隨機(jī)森林分類(lèi)器的檢測(cè)區(qū)域，利用全局隨機(jī)森林分類(lèi)器和局部隨機(jī)森林分類(lèi)器進(jìn)行目標(biāo)檢測(cè)，并將檢測(cè)結(jié)果作為Kalman跟蹤算法下一幀的觀測(cè)值。實(shí)驗(yàn)結(jié)果顯示，提出的算法在跟蹤大小420×320的圖像時(shí)，跟蹤速度達(dá)到24.3 f/s(幀/秒)，目標(biāo)中心位置誤差在30 pixel時(shí)，算法準(zhǔn)確率可達(dá)到80%以上。

視覺(jué)跟蹤；Kalman濾波；主方向模板；級(jí)聯(lián)隨機(jī)森林分類(lèi)器

目標(biāo)跟蹤是視覺(jué)領(lǐng)域一個(gè)重要的研究課題，但由于在目標(biāo)跟蹤過(guò)程中存在各種復(fù)雜情形，包括目標(biāo)的遮擋、相似目標(biāo)的干擾、目標(biāo)的快速運(yùn)動(dòng)、光照的變化、形變和旋轉(zhuǎn)等，提出一種實(shí)時(shí)性高、魯棒性強(qiáng)的跟蹤算法仍然是極具挑戰(zhàn)性的[1]。為了能夠更加準(zhǔn)確地表達(dá)目標(biāo)的外觀模型，Collin[2]首次提出將跟蹤視為二分類(lèi)問(wèn)題，強(qiáng)調(diào)了背景對(duì)目標(biāo)跟蹤的作用；隨后Grabner[3]提出了在線(xiàn)Boosting跟蹤算法，實(shí)現(xiàn)了對(duì)目標(biāo)模型的在線(xiàn)更新，可是如果模板存在誤差，容易導(dǎo)致跟蹤漂移。針對(duì)這一問(wèn)題，2010年Kalal[4]等人提出了一種新穎高效的目標(biāo)跟蹤架構(gòu)——基于檢測(cè)的跟蹤算法，該算法將跟蹤-檢測(cè)-學(xué)習(xí)有效地結(jié)合，實(shí)現(xiàn)了對(duì)單目標(biāo)的長(zhǎng)時(shí)跟蹤，具有較好的魯棒性和實(shí)時(shí)性。算法框架見(jiàn)圖1。但是該算法存在以下4點(diǎn)缺陷：1)當(dāng)目標(biāo)被完全遮擋時(shí)，檢測(cè)器和跟蹤器都無(wú)法捕捉到目標(biāo)，導(dǎo)致跟蹤失敗[5];2)檢測(cè)模塊采用的掃描窗口方法需要遍歷整個(gè)圖像檢測(cè)目標(biāo)，降低了跟蹤速度;3)跟蹤模塊采用的Lucas-Kanade光流法無(wú)法適應(yīng)完全偏離平面的旋轉(zhuǎn)表現(xiàn)，所以當(dāng)目標(biāo)出現(xiàn)劇烈運(yùn)動(dòng)時(shí)，容易跟蹤失敗;4)當(dāng)出現(xiàn)相似目標(biāo)時(shí)，算法跟蹤效果較差[6]。

圖1 TLD算法框架

針對(duì)上述缺陷，本文將具有較強(qiáng)預(yù)測(cè)性的Kalman算法與雙級(jí)聯(lián)隨機(jī)森林分類(lèi)器結(jié)合起來(lái)，利用Kalman算法對(duì)目標(biāo)進(jìn)行跟蹤，一方面將具有可靠置信度的跟蹤結(jié)果作為檢測(cè)器的正樣本輸入，防止分類(lèi)器對(duì)錯(cuò)誤樣本的學(xué)習(xí)，導(dǎo)致外觀模型構(gòu)建時(shí)誤差的累積；另一方面以目標(biāo)位置為中心擴(kuò)展一定范圍作為檢測(cè)器的檢測(cè)區(qū)域，則有效縮小了檢測(cè)模塊的檢測(cè)范圍，提高算法實(shí)時(shí)性和檢測(cè)的準(zhǔn)確性。同時(shí)雙級(jí)聯(lián)隨機(jī)森林分類(lèi)器以主方向模板作為檢測(cè)特征，利用全局隨機(jī)森林分類(lèi)器和局部隨機(jī)森林分類(lèi)器逐級(jí)進(jìn)行分類(lèi)，充分考慮了目標(biāo)的局部和整體信息，具有分類(lèi)速度快、檢測(cè)精度高的特點(diǎn)。

1 基于Kalman算法的目標(biāo)跟蹤

卡爾曼濾波器[7]在最小均方誤差的準(zhǔn)則下，利用一組數(shù)學(xué)方程采用遞歸的計(jì)算方法對(duì)目標(biāo)的下一狀態(tài)進(jìn)行有效的估計(jì)，并能根據(jù)當(dāng)前的觀測(cè)值修正預(yù)測(cè)結(jié)果，是一個(gè)不斷預(yù)測(cè)-修正的過(guò)程，具有無(wú)偏、穩(wěn)定、最優(yōu)的特點(diǎn)。因此本文選擇其作為跟蹤算法，這樣在目標(biāo)發(fā)生遮擋、形變等情況時(shí)，仍能實(shí)現(xiàn)對(duì)目標(biāo)的有效跟蹤。

1.1 數(shù)學(xué)模型

在建立Kalman濾波的數(shù)學(xué)模型時(shí)，假設(shè)所有的噪聲為高斯白噪聲，并且目標(biāo)在相鄰兩幀間的運(yùn)動(dòng)為勻速運(yùn)動(dòng)。在建立Kalam濾波器中的狀態(tài)向量和觀測(cè)向量時(shí)，本文充分利用了每幀圖像中目標(biāo)中心位置的相關(guān)參數(shù)，包括目標(biāo)中心在水平方向的坐標(biāo)值px和豎直方向上的坐標(biāo)值py，以及目標(biāo)在水平方向的速度vx和豎直方向上的速度vy，具體見(jiàn)下式

(1)

Kalman濾波的計(jì)算過(guò)程如下：

第一步建立目標(biāo)的狀態(tài)方程

(2)

第二步預(yù)測(cè)系統(tǒng)狀態(tài)的協(xié)方差

(3)

第三步計(jì)算卡爾曼增益

Gk=PkHT(HPkHT+R)-1

(4)

(5)

最后修正協(xié)方差矩陣

(6)

(7)

同時(shí)由于狀態(tài)轉(zhuǎn)移噪聲wk-1和觀測(cè)噪聲vk被假設(shè)為2個(gè)相互獨(dú)立的零均值高斯白噪聲，則狀態(tài)轉(zhuǎn)移噪聲和觀測(cè)噪聲的協(xié)方差矩陣分別為Q=10-5I4，R=10-1I2，其中I4為4×4的單位矩陣，I2為2×2的單位矩陣。

1.2 確定檢測(cè)區(qū)域

檢測(cè)器的搜索策略是基于滑動(dòng)窗口的掃描機(jī)制，往往需要遍歷整個(gè)圖像，這種方法計(jì)算量大，如1幀420×320的圖像，僅有10%的子窗口為目標(biāo)，其他90%的子窗口只包含部分目標(biāo)甚至不包含目標(biāo)。因此本文充分利用Kalman算法的預(yù)測(cè)性對(duì)檢測(cè)器的搜索范圍進(jìn)行預(yù)估，從而提高檢測(cè)速度。以Kalman算法的最優(yōu)估計(jì)值為圓心，以2倍的目標(biāo)半徑為半徑，確定目標(biāo)搜索范圍。如果在這一范圍仍然沒(méi)有搜索到目標(biāo)，則將搜索范圍擴(kuò)大1倍。

2 在線(xiàn)目標(biāo)分類(lèi)器

雙級(jí)聯(lián)隨機(jī)森林檢測(cè)器以主方向模板特征[8]為目標(biāo)的表征特征，同時(shí)利用全局檢測(cè)器(Holistic Detector)和局部檢測(cè)器(Patch-based Detector)實(shí)現(xiàn)對(duì)目標(biāo)全局信息和局部信息的融合，進(jìn)而實(shí)現(xiàn)多層檢測(cè)[9]，具有檢測(cè)精度高、運(yùn)算時(shí)間短的特點(diǎn)。方法的主要流程如圖2所示。

圖2 級(jí)聯(lián)隨機(jī)森林檢測(cè)器方法流程圖

2.1 分類(lèi)器訓(xùn)練與更新

對(duì)局部隨機(jī)森林分類(lèi)器的訓(xùn)練方法與全局隨機(jī)森林分類(lèi)器相似，不過(guò)選取的樣本圖像塊尺寸更小，并且在考慮圖像塊主方向模板特征的同時(shí)，將圖像塊中心相對(duì)樣本目標(biāo)塊中心的位置偏移量加入到分裂函數(shù)中。對(duì)每棵樹(shù)單獨(dú)訓(xùn)練，當(dāng)滿(mǎn)足下列條件時(shí)，停止對(duì)節(jié)點(diǎn)的分裂：1)達(dá)到樹(shù)的最大深度depthmax=15；2)節(jié)點(diǎn)中樣本數(shù)達(dá)到最小值nummin=10。

在目標(biāo)跟蹤過(guò)程中，目標(biāo)的外觀會(huì)不斷發(fā)生變化，因此外觀模型也要做出相應(yīng)的更新，具體來(lái)說(shuō)就是不斷用置信度滿(mǎn)足要求的正樣本更新隨機(jī)森林決策樹(shù)。將Kalman跟蹤到的新樣本和分類(lèi)器檢測(cè)到的新樣本加入到?jīng)Q策樹(shù)的生長(zhǎng)過(guò)程中。在分類(lèi)器的學(xué)習(xí)過(guò)程中，如果隨機(jī)森林的某個(gè)分支對(duì)應(yīng)的檢測(cè)結(jié)果是錯(cuò)誤樣本，表明該分支已經(jīng)不能表征目標(biāo)的外觀信息，可以對(duì)其進(jìn)行修剪[9]。

2.2 目標(biāo)檢測(cè)

檢測(cè)階段，利用滑動(dòng)窗口掃描策略在Kalman算法確定的待檢測(cè)范圍內(nèi)進(jìn)行順序掃描，得到窗口樣本S；然后將S放入全局隨機(jī)森林分類(lèi)器的T棵樹(shù)中(全局隨機(jī)森林中T=10)，得到窗口S在隨機(jī)森林每棵樹(shù)中得分的平均值，即score值

(8)

在前n個(gè)窗口確定的檢測(cè)區(qū)域映射到第二層高尺度空間，然后利用局部隨機(jī)森林分類(lèi)器在高尺度空間進(jìn)行局部檢測(cè)。首先利用大小16×16的掃描圖像塊pm進(jìn)行掃描，記錄每個(gè)掃描圖像塊的位置x及特征信息f，然后才有局部隨機(jī)森林分類(lèi)器對(duì)每個(gè)窗口的掃描圖像塊進(jìn)行分類(lèi)，并計(jì)算圖像塊pm對(duì)可能目標(biāo)中心的投票分值

(9)

其中：DL為圖像塊pm達(dá)到的葉子節(jié)點(diǎn)的偏移向量集合，并利用高斯Parzen窗來(lái)估計(jì)每個(gè)圖像塊偏移向量的投票概率;x-di表示圖像塊pm的一個(gè)投票位置;CL為該葉子節(jié)點(diǎn)中正樣本比率。對(duì)于DL集合，最后在所有圖像塊都分類(lèi)完畢后，用每個(gè)圖像塊的score值除以T，得到最終Hough圖，通過(guò)聚類(lèi)算法確定目標(biāo)的最終位置。

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

本文選用了3組不同場(chǎng)景下具有代表性的測(cè)試視頻Suv，sylvester，trellis，包含了在對(duì)目標(biāo)長(zhǎng)時(shí)間跟蹤過(guò)程中可能出現(xiàn)的各種嚴(yán)峻的情形，比如目標(biāo)部分遮擋或全部遮擋、目標(biāo)發(fā)生二維和三維旋轉(zhuǎn)、光照變化、目標(biāo)快速運(yùn)動(dòng)，以及存在相似目標(biāo)等。選擇經(jīng)典的TLD[4]和CT[10]跟蹤算法作為對(duì)比算法，利用OpenCV2.4.9在VisualStudio2010平臺(tái)上實(shí)現(xiàn)。

3.1 評(píng)估準(zhǔn)則

本文從定性和定量?jī)蓚€(gè)方面評(píng)估算法的性能，在進(jìn)行定量分析時(shí)采用精度和成功率作為評(píng)價(jià)指標(biāo)，對(duì)跟蹤算法的魯棒性進(jìn)行評(píng)估。

精確度圖:采用精確度圖對(duì)算法的整體跟蹤精度進(jìn)行評(píng)估，其能夠顯示跟蹤的目標(biāo)位置在給定的實(shí)際目標(biāo)位置的某一閾值范圍之內(nèi)的幀數(shù)占總幀數(shù)的百分比。為了對(duì)每個(gè)跟蹤器進(jìn)行具有代表性的精度評(píng)分，本文選用閾值等于20pixel時(shí)每個(gè)跟蹤器的精度值進(jìn)行比較。

魯棒性評(píng)估:在對(duì)跟蹤算法進(jìn)行魯棒性評(píng)估時(shí)，根據(jù)第一幀中的準(zhǔn)確位置進(jìn)行初始化，然后在一個(gè)測(cè)試序列中運(yùn)行算法，最后得出平均精確度或成功率的結(jié)果報(bào)告，即一次通過(guò)的評(píng)估(One-PassEvaluation，OPE)。

3.2 結(jié)果分析

本文算法的實(shí)驗(yàn)參數(shù)設(shè)置為：全局隨機(jī)森林分類(lèi)器大小T=10棵樹(shù)，每棵樹(shù)最大深度為10，局部隨機(jī)森林分類(lèi)器大小為T(mén)=15棵樹(shù)，每棵樹(shù)最大深度為15。對(duì)于其他兩種跟蹤算法均采用原文中的參數(shù)設(shè)置。

3.2.1 整體性能

每一個(gè)跟蹤算法的整體性能以成功率圖和精確度圖的形式展示在圖3中。右上角為排序結(jié)果。通過(guò)圖3可以發(fā)現(xiàn)，不管是在成功率圖還是在精度圖中，本文提出的算法整體性能較優(yōu)異，這說(shuō)明本文算法具有較強(qiáng)的魯棒性。但是在精度圖中，本文算法的性能略低于TLD算法，這是由于受Kalman濾波器預(yù)測(cè)結(jié)果的限制，本文算法的檢測(cè)區(qū)域較TLD的檢測(cè)區(qū)域小，降低了跟蹤精度。但是本文算法的成功率明顯高于TLD和CT算法。

圖3 OPE圖

3.2.2 基于跟蹤序列特性的性能分析

抗遮擋能力：圖4為各個(gè)跟蹤算法在Suv視頻序列中的跟蹤效果截圖。由于TLD算法和CT算法缺少遮擋判斷機(jī)制，在目標(biāo)遮擋時(shí)，仍然更新目標(biāo)模型，產(chǎn)生錯(cuò)誤的目標(biāo)樣本，所以在目標(biāo)被遮擋時(shí)，跟蹤框發(fā)生嚴(yán)重漂移；而本文算法在目標(biāo)發(fā)生遮擋時(shí)，利用Kalman算法對(duì)目標(biāo)下一幀可能出現(xiàn)的區(qū)域進(jìn)行評(píng)估，并且利用獲得的目標(biāo)樣本不斷更新級(jí)聯(lián)隨機(jī)森林分類(lèi)器，實(shí)現(xiàn)了對(duì)目標(biāo)穩(wěn)健的跟蹤。

圖4 Suv視頻序列跟蹤結(jié)果

處理二維、三維旋轉(zhuǎn)的能力：為了測(cè)試本文算法處理目標(biāo)發(fā)生二維和三維旋轉(zhuǎn)的能力，在sylvester視頻進(jìn)行試驗(yàn)，在sylvester視頻#600～#699幀中目標(biāo)發(fā)生了各種角度的旋轉(zhuǎn)，圖5為各算法跟蹤效果截圖。結(jié)果顯示，本文算法的跟蹤框能夠始終穩(wěn)定地框定目標(biāo)。這是由于本文算法選用的目標(biāo)特征，能夠充分考慮特征點(diǎn)位置和方向信息，通過(guò)不斷地學(xué)習(xí)目標(biāo)外觀的實(shí)時(shí)形變信息，并將其應(yīng)用到目標(biāo)在線(xiàn)模型的更新中，因此在整個(gè)跟蹤過(guò)程中能夠魯棒地跟蹤目標(biāo)。而TLD算法和CT算法的跟蹤框都發(fā)生了輕微的偏移。

圖5 sylvester視頻序列跟蹤結(jié)果

處理光照變化的能力：選擇在trellis視頻序列上測(cè)試算法應(yīng)對(duì)光照變化的能力。圖6為跟蹤效果截圖。trellis視頻中背景的光照變化從弱到強(qiáng)再到弱，在第242幀、296幀、340幀時(shí)由于光照的改變，TLD和CT都出現(xiàn)跟蹤漂移，而本文算法在(#179，#242，#340，#382)都表現(xiàn)了較強(qiáng)的跟蹤魯棒性。

圖6 trellis視頻序列跟蹤結(jié)果

4 結(jié)論

本文將雙級(jí)聯(lián)隨機(jī)森林分類(lèi)器結(jié)合到了Kalman跟蹤算法中，根據(jù)目標(biāo)這一時(shí)刻的運(yùn)動(dòng)狀態(tài)和位置信息，利用Kalman濾波預(yù)測(cè)出目標(biāo)下一時(shí)刻可能的位置，以該位置為中心，在一定的范圍內(nèi)，采用雙級(jí)聯(lián)隨機(jī)森林分類(lèi)器進(jìn)行目標(biāo)的檢測(cè)，確定出目標(biāo)的最終位置，并以此作為Kalman算法在下一幀中的起始位置。通過(guò)多個(gè)視頻數(shù)據(jù)對(duì)本文算法和TLD算法、CT算法進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明本文算法能有效應(yīng)對(duì)跟蹤過(guò)程中目標(biāo)的尺度、光照、旋轉(zhuǎn)、方向變化等，具備更高的跟蹤精度和更快的運(yùn)算速度。

[1]WUY，LIMJ，YANGMH.Onlineobjecttracking：abenchmark[C]//Proc.IEEEConferenceonComputerVision&PatternRecognition. [S.l.]：IEEE，2013：2411-2418.

[2]COLLINSTR，LIUY，LEORDEANUM.Onlineselectionofdiscriminativetrackingfeatures[J].IEEEtransactionsonpatternanalysisandmachineintelligence，2005，27(10)：1631-1643.

[3]GRABNERH，SOCHMANJ，BISCHOFH，etal.Trainingsequentialon-lineboostingclassifierforvisualtracking[C]//Proc.InternationalConferenceonPatternRecognition(ICPR).[S.l.]：IEEE，2008：1-4.

[4]KALALZ，MATASJ，MIKOLAJCZYKK.Tracking-learning-detection[J].IEEEtransactionsonpatternanalysisandmachineintelligence，2012，34(7)： 1409-1422.

[5] 呂枘蓬，蔡肖字，董亮. 基于TLD框架的上下文目標(biāo)跟蹤算法[J].電視技術(shù)，2015，39(9)：6-9.

[6] 高帆，吳國(guó)平，刑晨，等.TLD目標(biāo)跟蹤算法研究[J].電視技術(shù)，2013，37(11)： 70-74.

[7]KALMANRE.Anewapproachtolinearfilteringandpredictionproblems[J].TransactionsoftheASME-journalofbasicengineering，1960，82(SeriesD)：35-45.

[8]HINTERSTOISSERS，LEPETITV，ILICS，etal.Dominantorientationtemplatesforreal-timedetectionoftexture-lessobjects[C]//Proc.InternationalConferenceonPatternRecognition. [S.l.]：IEEE，2010：2257-2264.

[9] 向濤，李濤，李旭冬，等. 基于隨機(jī)森林的層次行人檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用研究，2015，32(7)： 2196-2199.

[10]ZHANGK，ZHANGL，YANGMH.Real-timecompressivetracking[C]//Proc.EuropeanConferenceonComputerVision. [S.l.]：Springer-Verlag，2012：864-877.

李 婷(1991— )，女，碩士生，主要從事視覺(jué)跟蹤和運(yùn)動(dòng)分析方面的研究；

趙文杰(1968— )，女，博士，教授，主要從事光學(xué)成像自動(dòng)目標(biāo)識(shí)別方面的研究；

楊 帥(1992— )，碩士生，主研數(shù)字圖像處理和目標(biāo)定位；

李 成(1985— )，博士，講師，主要從事圖像處理方面的研究。

責(zé)任編輯：閆雯雯

Online object tracking algorithm based on Kalman and cascaded random forest classifier

LI Ting， ZHAO Wenjie， YANG Shuai，LI Cheng

(DepartmentofAerospaceIntelligence，AviationUniversityofAirForce，Changchun130000，China)

As the traditional online tracking algorithm based on detection is easy to cause the tracking drift， a new online target tracking algorithm is proposed in this paper， where the Cascaded Random Forest with Dominant Orientation Templates is used as a detector， while the Kalman filter is the tracker. First， the Kalman filter is used to track the target， then the holistic detector and patch-based detector is applied to detect the object with the track result as the area center， and the detecting result is used as next frame’s observed value of Kalman tracking algorithm. The experimental results show that in the video sequence of 320 pixel×240 pixel， the speed can keep in 24.3 frame/s， and the object center position error is in 30 pixel， while the accuracy can reach above 80%.

visual tracking； Kalman filter； DOT； cascaded random forest

國(guó)家自然科學(xué)基金項(xiàng)目(61301233)

李婷，趙文杰，楊帥，等.基于Kalman和雙級(jí)聯(lián)隨機(jī)森林的在線(xiàn)目標(biāo)跟蹤算法[J].電視技術(shù)，2016，40(12)：23-27. LI T， ZHAO W J， YANG S，et al. Online object tracking algorithm based on Kalman and cascaded random forest classifier [J]. Video engineering，2016，40(12)：23-27.

TP391

A

10.16280/j.videoe.2016.12.005

2016-05-27