TLD目標跟蹤算法綜述

楊豐瑞，杜　奎，莊　園

(1．重慶重郵信科集團股份有限公司，重慶400065；2.重慶郵電大學 通信新技術應用研究中心，重慶 400065)

?

TLD目標跟蹤算法綜述

楊豐瑞1，杜奎2，莊園2

(1．重慶重郵信科集團股份有限公司，重慶400065；2.重慶郵電大學 通信新技術應用研究中心，重慶 400065)

TLD目標跟蹤算法將檢測和跟蹤同時加入跟蹤框架，并引入半監督機器學習算法對鎖定目標不斷學習以捕獲其最新外觀，使目標無處可逃，從而實現對未知目標的長時跟蹤。簡要介紹了TLD算法的理論背景和系統框架，并指出其存在的主要缺陷。然后對各個缺陷所提出的改進方法進行詳細地綜述，并給出自己的評述。最后總結全文并展望TLD目標跟蹤算法在未來幾年的發展趨勢。

長時目標跟蹤；半監督機器學習；中直流跟蹤器；隨機森林分類器

目前，基于檢測和半監督學習的目標跟蹤算法已經成為研究的主流[1]。TLD作為一種基于檢測和半監督學習的目標跟蹤算法，因其具有良好的適應性和魯棒性，自問世以來就引起了國內外學者的廣泛關注。

自從Zdenek Kalal提出TLD目標跟蹤算法以來，國內外學者對此提出了很多改進算法，但至今國內外還沒有一篇綜述對此進行詳盡的闡述。本文從TLD目標跟蹤算法所存在的缺陷出發對其進行全面的綜述和分析。

1　TLD框架結構及原理

2009年，Zdenek Kalal先后提出了一種基于學習和分類的新型檢測器[1]、PN學習器[2]和Median-Flow跟蹤器[3]。2010年，在此基礎上他正式提出了一種對未知目標具有長期跟蹤能力的目標跟蹤算法：Tracking-Learning-Detection，即TLD[4]。

1.1TLD提出的背景

傳統跟蹤算法對運動目標初始化后就可以快速地生成目標的運動軌跡，但傳統跟蹤算法由于僅僅依靠先驗信息，所以其在運行時會不斷累積誤差，而且當目標在視野中消失后再次進入視野內，此時將直接導致跟蹤失敗；傳統檢測算法獨立評估每一幀視頻序列，判斷每一幀中是否含有目標，如果有目標就給出目標狀態信息，檢測器不會因目標消失而導致檢測失敗，但是他們需要進行離線訓練，所以無法對未知目標進行檢測。

Zdenek Kalal認為傳統跟蹤算法或者檢測算法不具備獨立應對長時目標跟蹤的條件，因為它們都不直接涉及跟蹤框漂移后的在線處理，誤差積累勢必會越來越嚴重。Zdenek Kalal認為實現長期跟蹤必須滿足以下3點：

1)跟蹤器具備一定的自檢測能力。

2)加入半監督機器學習以實時更新目標模型。

3)檢測模塊與跟蹤模塊搭配。

1.2TLD目標跟蹤系統框架

TLD算法由4個模塊構成：跟蹤模塊、學習模塊、檢測模塊和整合模塊[4]。在TLD算法中，跟蹤模塊和檢測模塊并列運行，二者相互影響，檢測模塊可以重置跟蹤模塊，同時跟蹤模塊又可以通過學習模塊為檢測模塊提供訓練數據，緊接著將它們所生成的正負樣本傳入整合模塊，整合模塊生成正負樣本參與半監督學習，此時負責存儲具備表征當前目標外觀的正負樣本的目標模型得到更新，更新后的目標模型又反作用于跟蹤模塊和檢測模塊。TLD系統框架如圖1所示。

圖1　TLD系統框架圖

2　TLD目標跟蹤算法缺陷

近年來針對TLD算法存在的缺陷涌現出了相當多的改進方案。表1對TLD算法的缺陷、改進模塊和對應的改進算法進行了分類歸納[6-32]。下面3個章節將從表1列出的缺陷出發，以缺陷為單位，對這些改進算法進行全面綜述，并給出相應的評述。

表1TLD算法缺陷歸納

主要問題具體改進模塊相關文獻手動初始化檢測模塊[6]貪婪搜索檢測模塊[5,12,14,15,16,17,18,19,28]圖像元方差分類器泛化能力相對較弱檢測模塊[12,22]目標模型樣本膨脹學習模塊[7,11,13,20]對相似目標辨識能力相對較弱檢測模塊、整合模塊[13,14,15]發生嚴重遮擋時,目標框易漂移檢測模塊、整合模塊[8,9,10,11,12,13,27,28,32,26]最近鄰分類器耗時巨大檢測模塊[24,30]復雜背景下,目標框易漂移檢測模塊、整合模塊[16,21,29,32]Median-Flow跟蹤器穩定性相對較弱跟蹤模塊[14,23,31]目標發生大尺度形變時,目標框易漂移檢測模塊、跟蹤模塊[6,19,25]

3　針對TLD算法存在問題所提出的解決方案

3.1手動初始化

文獻[6]采用運動目標檢測和SIFT算法來識別出最佳匹配區域作為TLD初始跟蹤區域。具體思想如下：1)利用SURF算法提取這兩幀圖像中匹配特征點對以完成快速注冊；然后利用RANSAC算法剔除錯誤的匹配特征點對[6]；2)估計仿射模型得到仿射變換圖像；3)借助運動直方圖觀察兩個放射變換圖像之間的差異；4)利用多幀關聯技術提煉出前景跟蹤框，同時剔除錯誤的運動目標；5)利用改進型SIFT算法來確定最優的匹配區域。目標自動初始化流程如圖2所示。

圖2目標自動初始化流程圖

文獻[6]所提出的方法確實實現了跟蹤目標自動初始化，但是該方法需要在跟蹤前消耗一定的時間去完整地遍歷視頻序列，相比原始算法，延長了初始化時間。

3.2貪婪搜索

所謂“貪婪搜索”，即TLD 中檢測器是基于滑動窗口掃描的，檢測器需要對圖像中可能包含目標的子窗口進行掃描以確定窗口包含前景目標[12]。對一幀320×240大小的圖像，檢測模塊大概需要遍歷3萬個子掃描窗口，而其中大概只有10%～25%的子窗口才包含目標[4]。

文獻[5]提出ROI(Region Of Interest)理念，采用非全局搜索策略，即直接將目標框長與寬各擴大20像素，如果失敗就利用背景抽離技術得到粗粒度的前景區域，然后通過模板匹配技術得到細粒度的前景區域。實驗表明，該方法同時提高了幀處理速度[5]。

文獻[12，14-15]均將Kalman濾波器預測區域作為目標檢測區域，大同小異。

文獻[16]在 TLD檢測模塊中加入Kalman濾波器和Meanshift算法。首先利用Meanshift算法迭代出置信度最高的目標區域，在該區域上做一外接矩形框，然后將其傳給Kalman濾波器作為預測量，最后將Kalman濾波的預測區域作為Meanshift下一幀的初始搜索區域。

文獻[17]提出一種檢測區域自適應的方法。該方法利用雙Kalman濾波器加速矯正預測區域。但該策略明顯降低了TLD系統的跟蹤精度。

文獻[18]引入金字塔LK光流法獲取目標區域，該策略具備動態生成掃描框的特性。

文獻[19]引入粒子濾波，隨機產生K個特征點作為運動粒子，接著利用Meanshift算法計算這些粒子在下一幀中的位置，然后計算各粒子位置加權和來得到下一幀目標所在的邊界框。另外，為粒子權重設置閾值進一步弱化粒子退化產生的影響。

文獻[28]利用基于幀差法的前景運動目標檢測器替換圖像元方差分類器。該策略在一定程度上增強了系統的實時性和魯棒性。

產生“貪婪搜索”的主要原因就是TLD正負樣本的生成策略不合理，提出新型正負樣本生成方案方能從源頭解決這個問題。

3.3發生嚴重遮擋時，目標框易漂移

基于抗遮擋的目標跟蹤方法多依賴于預測理論，常見的預測手段有：Kalman濾波器、粒子濾波器和馬爾科夫鏈。

文獻[8]提出一種基于Kalman濾波的TLD跟蹤算法，當TLD跟蹤成功，TLD為Kalman濾波提供觀測值，當TLD跟蹤失敗，則利用Kalman預測值取代觀測值，隨著遞歸的不斷進行，最終輸出目標狀態[8]。

文獻[9]在檢測模塊中加入SURF特征檢測器。當目標出現快速運動、發生遮擋時，啟動SURF特征檢測器提取SURF特征以對目標進行二次檢測，但此時不參與學習過程，防止采集不正確的正樣本而導致跟蹤失敗。這種策略值得借鑒。

文獻[10]提出一種基于參考點的TLD跟蹤算法，所謂“參考點”，即在每一幀中實時地篩選出和目標具有一定聯系的SURF特征點。當目標因發生部分或者完全遮擋而跟蹤失敗時，則可以利用參考點準確預測出目標所在區域。

文獻[11]結合光電跟蹤系統跟蹤背景相對簡單的特點，提出了適用于海空環境的TLD 算法。具體流程如圖3所示。

圖3目標自動初始化流程圖

文獻[13]使用改進的MIL跟蹤器(Online MIL)替換Median-Flow跟蹤器來進行目標跟蹤，提高了目標在被遮擋情況下跟蹤的魯棒性。

文獻[27]提出了完備的遮擋預判定的體系。遺憾的是其提出的抗遮擋解決方案相對于遮擋預判定的體系來說，過于粗略。

文獻[28]提出了一種基于時空上下文目標跟蹤(STC)和Kalman濾波器相結合的新型的跟蹤器，并利用該跟蹤器替代Median-Flow跟蹤器。實驗表明，該新型跟蹤器對嚴重遮擋目標具有較強的容忍性。

文獻[32]利用霍夫森林替換級聯分類器。由于霍夫森林可以充分提取出目標的局部空間信息以及多通道特征，因此該策略可以有效增強系統魯棒性。

在目標跟蹤領域，對遮擋目標的跟蹤始終沒有強魯棒性的算法被提出來，絕大多數的方案局限于在特定環境，將其應用在其他環境下可能就會發生限位框漂移的現象。上述文獻所提出的方法依然是以特定環境為前提。

3.4目標模型樣本膨脹

所謂“樣本膨脹”，即目標模型更新時缺少限制樣本數量的策略，隨著跟蹤系統的不斷運行，目標模型中的正負樣本數量會越來越多。導致目標模型樣本冗余度高。

文獻[7]通過為目標模型中正負樣本總數量設定閾值來抑制正負樣本膨脹，當正負樣本總數量達到飽和狀態時，就替換掉其內表征能力最弱的正樣本或者負樣本。但這種替換策略事實上違背了目標模型的數據結構。

文獻[11]通過分析檢測模塊各級分類器的算法時間復雜度來論證：目標模型內樣本數量過多會嚴重影響檢測器的實時性。設圖像塊Pi(i=1，2，…，n)經過方差過濾器篩選之后剩余數量為N1，經過隨機厥分類器篩選之后剩余圖像塊數量為N2。模型M中當前模板數量為Nt，模板像素數為Nm，則各級分類器算法時間復雜度如表2所示。

表2級聯分類器時間復雜度

分類器圖像元方差分類器隨機厥分類器最近鄰分類器復雜度O(Nb)O(N1·Nf)O(N2·Nt·Nm)

改進更新策略：從正負樣本空間中剔除相似性最大的正樣本數據和相似性最小的負樣本數據。

對于目標模型中正負樣本的限制均是基于這樣一個事實：樣本對當前目標外觀的表征能力與加入目標模型的時間順序成反比。

3.5相似目標辨識能力較弱

文獻[13]在TLD框架內引入MIL跟蹤器同時改進整合模塊判決策略以此來應對具有相似干擾目標的場景。整合模塊判決策略摒棄原有的權重論而是將通過比較跟蹤模塊與檢測模塊的輸出置信度的大小來判決目標在下一幀的位置。另外，MIL跟蹤器非常出色，但在此引入會導致框架過于復雜。

文獻[14]巧妙地將馬爾科夫預測器時域一致性的優點和特定場景進行融合，很好地解決了相似目標相向而行時目標框漂移的問題。

TLD檢測模塊在面對相似目標時容易被干擾目標同化，最有效的解決方法是通過融合前景和背景信息設計一個對相似干擾目標具有強魯棒性的檢測器。

3.6目標發生大尺度形變時，目標框易漂移

文獻[6]引入綜合性能優于SIFT和SURF算法的ORB描述器來增強TLD算法的跟蹤器，改進型跟蹤器與原始TLD跟蹤器不同，在限位框內不再是均勻產生10×10個像素點，而是僅僅產生5×5個均勻像素點，剩下75個像素點是不均勻分布的ORB特征點。

文獻[19]提出一種基于SAMS算法的尺度自適應策略，即使尺度跟隨目標動態變化。

大尺度變換和目標遮擋長期以來被視作阻礙視覺目標跟蹤發展的攔路虎。在滿足實時性的前提下，目前尚沒有很好的應對策略。

3.7復雜背景下，目標框易漂移

文獻[16]針對在復雜場景下，目標與背景灰度差異小，方差分類器無法準確剔除背景目標。于是利用顏色特征彩色直方圖替換灰度直方圖，使方差分類器正常工作。

文獻[21]所提出的方法依然是對引入顏色特征直方圖對圖像元方差分類器進行改進。總體與文獻[16]大同小異。

文獻[29]經實驗發現，當檢測器沒有輸出時，恰恰就是檢測器中的最后一級分類器沒有輸出，但隨機厥分類器的輸出已經很接近目標位置了。于是，該文對第二級隨機厥分類結果進行聚類分析，取其外接矩形框作為最終輸出。

上述3篇文獻介紹了TLD框架中檢測模塊和整合模塊的缺陷，并且提出了行之有效的解決方案，實驗表明，上述改進方案確實可以很好地解決復雜背景下跟蹤框易漂移的問題。

3.8Median-Flow跟蹤器穩定性相對較弱

導致Median-Flow跟蹤器不穩定的主要因素是Lucas-Kanade光流法，Median-Flow跟蹤器依賴后者產生具體的跟蹤軌跡。但是光流法又是基于目標運動一致性假設的，當目標運動速度過快時，顯然違背了該假設。在現實生活中，只有極少數的情景才滿足目標運動一致性假設。

文獻[14]所提出的跟蹤器，是基于Cell FoT+算法的。跟蹤器框架如圖4所示。

圖4　跟蹤器框架

文獻[23]引入粒子濾波和積分直方圖來改進跟蹤器。由于中值流跟蹤器采用FB誤差來實現跟蹤自檢測，其需要連續運用兩次金字塔光流法跟蹤特征點。顯然，此舉無形中增大了出錯的風險。粒子濾波算法跟蹤比較準確，但在長期跟蹤中會面臨粒子退化和粒子匱乏的問題。粒子濾波和金字塔光流法相結合的策略，不僅可以減少中值流跟蹤器中累積的誤差，還可以有效緩解粒子退化和粒子匱乏等現象。

在上述所述的方法中，文獻[14]所提出的方法比較優秀，跟蹤精度高，但是比較復雜，時間復雜度高。

3.9 最近鄰分類器耗時巨大

目標模型中樣本數量越大，最近鄰分類器耗時越大[24]。

文獻[24]將其提出的在目標遮擋和跟蹤準確性上有著良好表現的MGACT算法替換最近鄰分類器。MGACT 算法通過特征的壓縮，在執行最后檢測時，可以憑借壓縮特征實現高速檢測，進而大幅度提升幀處理速度。改進檢測模塊邏輯圖見圖5。

圖5　改進檢測模塊邏輯圖

文獻[30]通過將前景檢測、方差濾波、集成分類器和模板匹配串聯起來替代原始的檢測模塊，如圖3所示。在該新型檢測模塊中，前景檢測依賴于背景抽離技術，在每一幀中將所有圖像塊與背景模型進行比較，如果兩者相似度低于閾值，那么就濾除該圖像塊，反之將此圖像塊標記為正樣本圖像塊，接著傳入到下一級方法中；模板匹配技術在這4種“去噪”方法中對于負樣本圖像塊的濾除是最嚴格、最有效果的，因為圖像塊之間的比較都是在像素級展開的，先后通過計算NCC、d(p1，p2)和d+/-，最后將這4個參數歸一化為1個參數P+，以此來精確篩選出正負圖像塊樣本。

(1)

(2)

(3)

4　總結

當前絕大多數的研究者都將注意力放在“貪婪搜索”和“目標遮擋”上。而“手動初始化”和“最近鄰分類器耗時巨大”這兩大缺陷卻沒有得到太多的關注。“手動初始化”這一缺點會在跟蹤啟動的時候就將誤差等干擾因子引入整個系統，隨著跟蹤系統的不斷進行，誤差會不斷累積，最終將導致跟蹤失敗；“最近鄰分類器耗時巨大”這一問題，是關乎TLD系統實時性的決定性因素，亟待解決。

就目前來說，國內外對TLD的理論研究還不是很成熟，隨著對TLD算法研究的不斷深入，越來越多的缺陷會被挖掘，同時也會涌現出越來越多的優質高效地解決方案。

[1]KALALZ，MIKOLAJCZYKK，MATASJ.Forward-backwarderror：automaticdetectionoftrackingfailures[C]//Proc. 20thInternationalConferenceonPatternRecognition(ICPR). [S.l.]：IEEE，2010：2756-2759.

[2]KALALZ，MATASJ，MIKOLAJCZYKK.Onlinelearningofrobustobjectdetectorsduringunstabletracking[C]//Proc.IEEE12thInternationalConferenceonComputerVisionWorkshops(ICCVWorkshops) . [S.l.]：IEEE，2009：1417-1424.

[3]KALALZ，MATASJ，MIKOLAJCZYKK.Pnlearning：bootstrappingbinaryclassifiersbystructuralconstraints[C]//Proc.IEEEConferenceonComputerVisionandPatternRecognition(CVPR) . [S.l.]：IEEE，2010：49-56.

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

[5]NEMADEB，BHARADIVA.Adaptiveautomatictracking，learninganddetectionofanyrealtimeobjectinthevideostream[C]//Proc.IEEE5thInternationalConferenceonConfluenceTheNextGenerationInformationTechnologySummit(Confluence). [S.l.]：IEEE，2014： 569-575.

[6]HAILONGW，GUANGYUW，JIANXUNL.Animprovedtracking-learning-detectionmethod[C]//Proc.IEEE34thChineseControlConference(CCC). [S.l.]：IEEE，2015： 3858-3863.

[7]ZHANGP，SUNYQ，YA-LIWU，etal.AparallelimplementationofTLDalgorithmusingCUDA[C]// 2013全國高性能計算學術年會. 桂林：[出版者不詳]，2013：220-224.

[8]龔小彪，何濤. 基于卡爾曼濾波的抗遮擋TLD跟蹤算法[J]. 信息與電腦(理論版)，2014(4)：195-196.

[9]劉朵. 基于特征描述子的目標跟蹤研究[D]. 西安：西安電子科技大學，2013.

[10]李敏敏.基于TLD模型的目標跟蹤方法[D]. 西安：西安電子科技大學，2013.

[11]王建剛，李醒飛，陳誠，等. 改進TLD算法在光電跟蹤中的應用[J].紅外技術，2015(10)：824-830.

[12]張帥領.基于TLD的視頻目標跟蹤算法的研究[D]. 西安：西安電子科技大學，2014.

[13]高帆，吳國平，刑晨，等.TLD目標跟蹤算法研究[J].電視技術，2013，37(11)：70-74.

[14]周鑫，錢秋朦，葉永強，等.改進后的TLD視頻目標跟蹤方法[J].中國圖象圖形學報，2013(9)：1115-1123.

[15]SUNC，ZHUS，LIUJ.FusingKalmanfilterwithTLDalgorithmfortargettracking[C]//Proc. 2015 34thChineseControlConference(CCC). [S.l.]：IEEE，2015：3736-3741.

[16]金龍，孫涵.TLD視頻目標跟蹤方法改進[J].計算機與現代化，2015(4)：42-46.

[17]曲海成，單曉晨，孟煜，等.檢測區域動態調整的TLD目標跟蹤算法[J].計算機應用，2015(10)：2985-2989.

[18]鄭遠力，胡志坤. 基于滑動掃描框的高速物體的圖像實時跟蹤算法[J]. 計算機科學，2015(10)：287-291.

[19]滕飛，劉清，朱琳. 一種快速魯棒的內河CCTV系統船舶跟蹤算法[J]. 武漢理工大學學報，2014(5)：80-85.

[20]江博.基于Kalman的TLD目標跟蹤算法研究[D]. 西安：西安科技大學，2013.

[21]肖慶國，葉慶衛，周宇，等.基于Mean-Shift優化的TLD視頻長時間跟蹤算法[J].計算機應用研究，2015(3)：925-928.

[22]齊楠楠，揭斐然，謝熙，等.基于TLD的艦船目標跟蹤方法研究[J].紅外技術，2013(12)：780-787.

[23]周雅琪. 結合濾波理論的內河視頻序列船舶TLD跟蹤算法研究[D].武漢：武漢理工大學，2013.

[24]黃坤. 基于在線學習算法的目標跟蹤技術研究[D]. 北京：北京理工大學，2015.

[25]程立英，張丹，趙姝穎，等.一種基于TLD改進的視覺跟蹤算法[J].科學技術與工程，2013(9)：2382-2386.

[26]包涵，黃學航，陸星家.TLD目標追蹤算法研究[J]. 寧波工程學院學報，2012(1)：52-54.

[27]楊萌，楊陽，王藝，等. 一種改進的TLD算法[J]. 傳感器與微系統，2014(12)：130-133.

[28]呂枘蓬，蔡肖芋，董亮，等. 基于TLD框架的上下文目標跟蹤算法[J]. 電視技術，2015，39(9)：6-9.

[29]成正國，潘廣貞. 基于TLD的動態背景下視覺跟蹤技術研究[J]. 電視技術，2015，39(7)：111-114.

[30]NEBEHAYG.Robustobjecttrackingbasedontracking-learning-detection[EB/OL]. [2015-12-18].http://www.gnebehay.com/publications/master_thesis/master_thesis.pdf.

[31]CHENGS，LIUG，SUNJ.Robustandfasttracking-learning-detection[C]//Proc. 2015InternationalConferenceonComputerScienceandIntelligentCommunication. [S.l.]：Atlantis，2015.

[32]李俊，謝維信，李良群. 基于空時線索的TLD視頻跟蹤算法[J]. 信號處理，2015，31(10)：1287-1293.

杜奎(1990— )，碩士生，主研視覺目標跟蹤；

楊豐瑞(1963— )，博士，教授，主要研究方向為通信新技術應用與電信增值業務；

莊園(1990— )，女，碩士生，主研蜂窩網下D2D通信的干擾協調技術。

責任編輯：閆雯雯

Survey on TLD object tracking algorithm

YANG Fengrui1，DU Kui2，ZHUANG Yuan2

((1.ChongqingInformationTechnology(Group)Co.，Ltd.，Chongqing400065，China；2.ApplicationofNewTechnologiesofCommunicationResearchCenter，ChongqingUniversityofPostandTelecommunications，Chongqing400065，China)

In order to enable long-term tracking for unknown objects， a semi-supervized machine learning algorithm is added in object tracking based on TLD algorithm which matches traditional tracking algorithm and detection algorithm for keeping capturing the newest appearances by continuous learning. Firstly， TLD’s theoretical background， tracking framework and major defects are introduced. Then， the improvements of the original algorithm are elaborately disscussed. Finally， the propspects of object tracking based on TLD algorithm are presented.

object tracking；semi-supervized machine learning；median flow tracker；random forest classifier

TN391.41

ADOI： 10.16280/j.videoe.2016.10.021

2015年重慶市研究生科研創新項目(CYS15166)

2015-12-18

文獻引用格式：楊豐瑞，杜奎，莊園. TLD目標跟蹤算法綜述[J].電視技術，2016，40(10)：101-106.YANG F R，DU K，ZHUANG Y. Survey on TLD object tracking algorithm [J]. Video engineering，2016，40(10)：101-106.