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

(空軍航空大學(xué) 航空航天情報系，吉林 長春 130000)

?

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

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

(空軍航空大學(xué) 航空航天情報系，吉林 長春 130000)

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

視覺跟蹤；Kalman濾波；主方向模板；級聯(lián)隨機森林分類器

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

圖1 TLD算法框架

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

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

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

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

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

(1)

Kalman濾波的計算過程如下：

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

(2)

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

(3)

第三步計算卡爾曼增益

Gk=PkHT(HPkHT+R)-1

(4)

(5)

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

(6)

(7)

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

1.2 確定檢測區(qū)域

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

2 在線目標(biāo)分類器

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

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

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

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

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

2.2 目標(biāo)檢測

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

(8)

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

(9)

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

3 實驗結(jié)果及其分析

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

3.1 評估準(zhǔn)則

本文從定性和定量兩個方面評估算法的性能，在進行定量分析時采用精度和成功率作為評價指標(biāo)，對跟蹤算法的魯棒性進行評估。

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

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

3.2 結(jié)果分析

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

3.2.1 整體性能

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

圖3 OPE圖

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

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

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

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

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

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

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

4 結(jié)論

本文將雙級聯(lián)隨機森林分類器結(jié)合到了Kalman跟蹤算法中，根據(jù)目標(biāo)這一時刻的運動狀態(tài)和位置信息，利用Kalman濾波預(yù)測出目標(biāo)下一時刻可能的位置，以該位置為中心，在一定的范圍內(nèi)，采用雙級聯(lián)隨機森林分類器進行目標(biāo)的檢測，確定出目標(biāo)的最終位置，并以此作為Kalman算法在下一幀中的起始位置。通過多個視頻數(shù)據(jù)對本文算法和TLD算法、CT算法進行了測試，實驗結(jié)果表明本文算法能有效應(yīng)對跟蹤過程中目標(biāo)的尺度、光照、旋轉(zhuǎ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] 高帆，吳國平，刑晨，等.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].計算機應(yīng)用研究，2015，32(7)： 2196-2199.

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

李 婷(1991— )，女，碩士生，主要從事視覺跟蹤和運動分析方面的研究；

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

楊 帥(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

國家自然科學(xué)基金項目(61301233)

李婷，趙文杰，楊帥，等.基于Kalman和雙級聯(liá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