基于隨機森林的長期目標跟蹤方法

張 丹，陳興文，趙姝穎，程立英，3

(1.大連民族學院創(chuàng)新教育中心，遼寧大連116605;2.東北大學信息科學與工程學院，遼寧沈陽110819;3.沈陽師范大學物理科學與技術學院，遼寧沈陽110034)

目標跟蹤的研究與應用是計算機視覺的一個重要分支，也是其研究領域中的難點和熱點，廣泛應用于科學研究、航空航天、醫(yī)學、國防軍事、人機交互、機器人及國民經濟的各個領域。目標跟蹤的關鍵技術在于合理提取特征和準確的識別目標，實時、準確的長期目標跟蹤對于人機交互技術、人工智能等技術的發(fā)展具有重要的理論意義和應用價值。

長期目標跟蹤過程中，易出現目標的遮擋、丟失、運動速度過快等問題。光照干擾、復雜多變背景使得跟蹤過程中計算量大、處理滯后，影響跟蹤效果。這些問題給快速、精確的長期目標跟蹤造成很大的難度。

國內外學者已經對長期跟蹤作了大量研究，Jorge［1］等人提出區(qū)域跟蹤算法，利用分割結果，將連續(xù)幀的目標匹配起來進行跟蹤;Moravec［2］提出利用圖像灰度自相關函數的特征點檢驗算子;Kass［3］等人提出 Snake 模型，Menet［4］提出 B-Snake模型，解決了快速跟蹤的問題;Deilamani M.J［5］等人提出了將色彩與邊緣特征相結合的Mean-Shift算法，可以很好的克服部分遮擋和光照的變化;Dr.Zdenek Kalal［6］在 2007 年到 2010 年間提出來并不斷完善的TLD算法，適合長時間跟蹤;chen等人［7］提出基于四元數的光流估計跟蹤方法，提高了算法的魯棒性;陳添丁等人［8］提出的稀疏光流快四計算動態(tài)目標檢測與跟蹤算法，一定程度上提高了跟蹤的實時性;Wang等人［9］提出在線學習跟蹤的方法，提高了目標跟蹤的精度，王愛平［10］等人提出增量式隨機森林分類器，提高了短視屏流跟蹤的準確性;袁紅衛(wèi)等人［11］提出一種基于光流的運動小目標檢測算法;佟國峰等人［12］提出一種基于隨機蕨叢的長期目標跟蹤方法，提高了跟蹤的適應性;李勁菊［13］，郝志成［14］等人提出了一種復雜背景下運動目標檢測與跟蹤的方法，提高了復雜背景下目標跟蹤的準確性。這些方法一定程度上解決了目標遮擋、快速運動的跟蹤問題，但是目標一旦丟失，無法快速恢復跟蹤，在復雜背景快速變化的過程中也難以實現實時、準確的跟蹤。

本文針對長期跟蹤情況下目標由于遮擋、快速運動易丟失、跟蹤實時性、準確性差等問題，結合正負樣本相互作用的思想和隨機森林算法，提出了一種基于TLD的隨機森林目標跟蹤方法。該方法在TLD算法的基礎上，采用隨機森林方法，構建在線學習模型，融合大運動捕捉跟蹤器，分別從跟蹤實時性、準確性上進行改進。

1 隨機森林算法及分析

1.1 隨機森林算法

單棵決策樹可以按照結點屬性值進行分類，為了明顯提高精度，很容易想到種植一片樹林，并讓所有樹參加投票，選出最好的分類，這就是隨機森林［13］的思想。對第k棵樹引入隨機變量θk，它與前面的k-1 個隨機變量 θ1，θ2，…θk-1是獨立同分布的。通過訓練集θk來生成第k棵樹，相當于產生一個分類器h(X，θk)，其中X是一個輸入量。隨機森林有較好的數學理論基礎，不會出現過度擬合，符合大數定律。構建隨機森林有多種形式和方法，可以根據實際需要，采用不同的方式構建隨機森林。本文中采用更新權重構建方法中的Adaboost方法進行構建。Adaboost方法是由Freund和 Schapire于1996年正式提出的，它是在前面分類器錯誤分類的基礎之上，為下一個分類器的輸入，更新訓練集上的權重，每個分類器都可以利用一個訓練集和一個權重訓練集來改進。

設w(1)，…w(k)(∑wi(k)=1，wi(k)≥0)為關于訓練集的k個不同的權重向量，對訓練集進行k種不同方式加權，這樣，得到的加權數據構成一個大集合。取權重概率p(1)，p(2)，…p(k)且(i)=1 時，依據概率p(1)，p(2)，…p(k)從1，2，…k抽取整數，記為θ。利用訓練集與權重w(k)產生分類器h(x，θ)。

在 Adaboost算法中，w(k+1)= φ(w(k))，φ是由起初分類器定義的函數。設第k個分類器為h(x，wk)，其投票權重為Q(wk)，所以對于將輸入x分類為j的規(guī)范化投票等于:

Adaboost算法主要針對一個訓練集訓練不同的分類器，然后把這些弱分類器集合起來，構成一個最終分類器(強分類器)。

1.2 算法分析

隨機森林有很多優(yōu)點:精度高，穩(wěn)定性好，可以有效的處理大數據集，在分類的過程中給出變量重要性的估計等，與其他集成方法相比，對于數據噪聲更穩(wěn)定［15］。隨機森林方法雖然支持在線學習，但是在學習過程中也較為容易出現誤判，如果數據集較大，算法運行時間長，那么積累的誤差就更大，分類錯誤率將會上升［15］。而TLD方法加入正負樣本互限思想，進行誤差一致矯正，提高樣本判別的準確性。因此，本文提出一種基于TLD的隨機森林方法。

2 基于TLD的目標跟蹤方法

2.1 在線學習模型

本文在線學習的過程主要使用正樣本增長、負樣本減少的方法。正樣本增長與負樣本減少同時進行，主要基于一個相似的閾值θ，當兩個目標窗口樣本的距離小于θ時就認為其與目標軌跡相似，反之亦然，這樣不斷的更新在線學習模型中的特征，使得特征更加精確。正樣本增長過程為從跟蹤軌跡中選擇相似的樣本并進行模型的更新。在負樣本減少過程中，假設被跟蹤的目標在場景中是唯一的，如果跟蹤器和檢測器都認為其中探測點是正確的，那么其余的探測點就被認為是負樣本，并且從模型中移走。

在線學習模型主要依靠正負樣本學習框架進行特征的更新。與目標軌跡接近的特征窗口使用正樣本更新探測器，正樣本增長。使用檢測器檢測目標，非最大置信度的探測點使用負樣本更新，即負樣本減少。它們相互作用產生誤差，并不斷的消除誤差，使得學習更穩(wěn)固，特征更精確。相互作用關系如圖1。

圖1 正負樣本相互作用關系示意圖

2.2 基于在線學習的隨機森林目標檢測器

將隨機森林的思想與在線學習模型結合起來，以實現目標的在線學習檢測模型，具體步驟如下:

(1)初始化分類器。提取正樣本訓練隨機森林分類器，包含目標物體的矩形區(qū)域為正樣本區(qū)域，其他部分被視為負樣本區(qū)域，將大小規(guī)則的圖像塊作為樣本進行處理，相對于單個像素而言，圖像塊包含更豐富的信息。在此階段，為了給分類器提供足夠的訓練樣本，在正樣本區(qū)域和負樣本區(qū)域內隨機產生大量子窗口，這些窗口可相互重疊，且位置隨機，每個子窗口從9×9像素大小到整幅圖像大小隨機產生，子窗口對應的圖像塊即可作為樣本進行處理，這樣即可完成分類器的初始化。

(2)在線學習模型。將分類器與在線學習模型相結合，構成增量式的隨機森林分類器。采用2bitBP特征形成特征空間，利用滑動窗口方法，在線學習模型分別對同一視頻圖像進行分類識別，正樣本增長模型將自身置信度高的樣本給特征空間進行增量學習分類，同時負樣本減少模型根據自身樣本的置信度判斷特征空間中的不正確樣本，將其從特征空間中去掉。這樣他們相互作用使得特征空間在不斷擴大的同時，使得其特征更加精確，也使得分類更加精確。

得到的分類器與在線學習模型相結合，不斷訓練樣本，如圖2，具體步驟為:

(1)使用分類器標記未標記的樣本;

(2)識別并重新標記違背結構限制的樣本;

(3)不斷的擴大訓練集;

(4)重新訓練分類器。

圖2 在線學習與分類器訓練數據示意圖

其中Xu為未標記的用于訓練的數據，(X1，Y1)為已經標記的訓練集數據，(Xt，Yt)為訓練集輸出的數據，需要再進行訓練的數據，結構限制主要是正樣本增長和負樣本減少，(Xc，Yc)是通過在線學習輸出的數據，θ為在線學習所對應的分類器的估計數據。

2.3 基于捕獲最大運動的目標跟蹤器

基于在線學習的隨機森林方法可進行目標檢測，但是無法實現較大運動的目標跟蹤。本文集合金字塔技術，采用LK光流法，根據所取特征，使用均值方式預測目標的運動和位移方向，與目標檢測器相結合，實現長期的目標跟蹤。

LK光流法［16］最初于1981年提出，由于算法易于應用在輸入圖像中的一組點上，后來成為求稀疏光流的一種重要方法，該方法基于亮度恒定、時間連續(xù)或者運動是“小運動”、空間一致三個假設，光流約束方程如(4)式所示。

將亮度的定義I(x(t)，t)表示，應用偏微分鏈式規(guī)則:

其中，Ix是圖像的偏導數，It是隨時間的導數，v是要求的速度。

前面是LK光流法在一維空間上的用法，將其擴展到二維圖像上，速度的y分量為v，x分量為u，得到:

孔徑問題即用小孔或小窗口去測量運動，只能觀測到物體邊緣而觀測不到角點，只依靠邊緣是不足以判斷整個運動物體的運動朝向的。而角點是可用于跟蹤的良好特征點，其檢測幾乎不受攝像機姿態(tài)和光照條件的影響，具有旋轉不變性，在圖像配準與匹配、運動估計等計算機視覺領域有著非常重要的作用。

但是，對于大多數30HZ的攝像機，大而不連貫的運動是普遍存在的。也正因為這個原因LK光流法在實際中的跟蹤效果并不是很好，本文結合金字塔技術，計算所取特征均值進行改進，解決此問題。

該方法的思想如下:原圖像作為金字塔基層I=0，將原圖減采樣至原尺寸的(一般N=1)，獲得I=1層圖像，則該層相鄰幀間的目標像素運動距離為(D為原圖中相鄰幀間的目標像素運動距離)。當I達到一定值時(一般3≤I≤5)，可滿足光流約束條件。在最高層Vf=0，圖像細節(jié)最少，ΔVf是f層的光流計算結果，作為下一層圖像的運動估計。

LK算法在幀與幀之間跟蹤這些點，產生矢量光流場，根據所取的特征，使用均值的方式預測下一幀中目標的運動和位移方向。在每一幀中都有一系列的新的特征點被跟蹤，因此使得跟蹤具有較強的適應性，對部分遮擋的物體跟蹤具有較好的魯棒性，跟蹤算法示意圖如圖3。

圖3 跟蹤算法示意圖

2.4 算法描述

本文算法流程描述如下，算法流程圖如圖4:

1)根據視頻幀，獲得相應的訓練集;

2)進行特征在線學習學習;

3)根據獲得的特征不斷的更新檢測器和跟蹤器，同時跟蹤器和檢測器也將得到的數據反饋給在線學習模型;

4)檢測器對目標進行檢測，與跟蹤器相融合，對比置信度，實現目標的跟蹤。

圖4 算法流程圖

3 實驗結果與分析

實驗計算機為 CPU E5500@2.80GHz，2GB內存，在Matlab R2009a環(huán)境下運行。本文中圖像是RGB格式，分辨率為320*240，幀率為30幀每秒。視頻包括原參考文獻中的及自己錄制的，分別為摩托車的運動［17］，由2917幀組成(2分33秒)，在這段視頻中包含了目標的遮擋、消失、快速運動、特征的突然變化等;復雜背景下的非剛性球的運動，由(2452)幀組成(1分22秒)，包括了目標的遮擋、消失和相機的移動;復雜邊緣物體的運動由(4740)幀組成(2分36秒)，包括了目標由慢向快的運動、遮擋、丟失、相似背景干擾和相機的移動。

圖5中被跟蹤的目標是非剛性軟球，5(a)中由于手力的作用使得球變形，雖然深色采樣點所取范圍變小，但是從圖中可以看出本算法依然可以找到跟蹤目標的中心點，實現跟蹤;5(b)中球面進行了滾動，即所跟蹤的球面已經不是第一幀獲得運動目標時的球面，但是通過球在運動過程中，對特征的不斷學習，使得算法越來越精確，雖然球換面，但是依然能實現目標跟蹤;5(c)中可以看到在手離開之后，本算法恢復了對變形球的跟蹤，而且跟蹤效果較好，這就是跟蹤器、檢測器和在線學習共同作用的結果。

圖5 非剛性物體跟蹤效果圖

目標跟蹤過程中獲得的樣本圖如圖6，6(a)中為所有樣本，既包括目標樣本也包括背景樣本，6(b)為目標樣本，即在跟蹤過程中，通過計算與第一幀獲得的標準目標樣本的重合率大于50%的樣本，這些樣本主要是通過在線學習模型獲得，雖然這些樣本有各種變化，各不相同，但是還是可以搜索到漂移，時刻進行修正，跟蹤目標。

圖6 跟蹤目標樣本圖

對三個目標的跟蹤如圖7，第一個是復雜背景的非剛性球跟蹤，第二個是復雜背景下復雜邊緣物體跟蹤，第三個雖然背景較為簡單，但是目標的運動速度非常的快。從圖中可以看出無論是出現部分遮擋還是快速運動，本算法都進行了較好的跟蹤。在7(a)和7(b)中運動目標的背景相當復雜，甚至有些背景的灰度與目標很接近，但是從跟蹤效果可以看出，本算法在復雜背景下進行了實時準確的跟蹤。在測試摩托車手的視頻中，在出現部分遮擋之后，目標丟失，目標中心點與深色取樣點出現了較大的偏差，但是在下一幀時，依然能檢測到運動的目標，原因就是在前后兩幀中運動目標由于運動速度非?？?，位置發(fā)生很大的變化，而追蹤對象的搜索范圍較小產生的，但是在下一幀時算法便克服其誤差，進行大范圍的搜索，得到了運動目標。

圖7 跟蹤效果圖

本文采用文獻［18］中的評估標準，將跟蹤過程中算法選擇的所有目標窗口數(樣本)定義為ST，手動選擇的目標窗口(樣本)個數定義為GT，如果跟蹤獲得的窗口和手動選擇的窗口的重合率超過70%，就認為獲得是正樣本，用TP表示，否則為FP，準確率用P表示，定義為:

用R來表示正樣本和手動選擇目標窗口的比，定義為:

本文使用P和R這兩個參數估計跟蹤方法的質量。將本文方法與Mean-Shift算法和原TLD算法進行對比，跟蹤質量見表1。

表1 跟蹤質量表

從表1中可以看出TLD算法的準確率明顯高于Mean-Shift算法，無論是哪種視頻資源，都進行了很好的跟蹤，復雜背景并沒有影響跟蹤效果;正樣本對于手動選擇的樣本比例，本文算法也明顯高于Mean-Shift算法，且高于TLD算法。由此可見，本文算法得到了較好的跟蹤效果，準確率較高，可以進行復雜背景下運動目標的跟蹤。

4 結論

對隨機森林算法進行分析研究，結合TLD的思想，構建在線學習模型進行結構限制，使得分類結果更準確;為捕捉大運動目標，改進光流法構建跟蹤器，設計結構，實現檢測器與跟蹤器的融合，并通過一系列實驗對本文方法的有效性進行驗證。實驗表明，本文算法實現了剛性物體、非剛性物體在快速運動、部分遮擋、完全丟失、攝像機運動等情況下的跟蹤，取得了較好的跟蹤效果，跟蹤準確率可以達到93%以上。

［1］JORGE B，BOBER M，PLA F.Motion and intensity based segmentation and its application to traffic monitoring［C］.In Proceedings，International Conference on Image Analysis and Processing ICIAP，Florence，Italy，1997:502-509.

［2］MORAVEC H P.Towards automatic visual obstacle avoidance［C］.In Proceedings of the 5th International Joint Conference on Artificial Intelligence，1977.

［3］KASS M，WITKINM A，TERZOPOULOS D.Active contour models［J］.International Journal on Computer Vision(IJCV)，1988，1(4):321-331.

［4］ MENET S，SAINT-MARC P，MEDIONI G.BSnakes:Implementation and application to stereo［C］.DARPA Image Understanding Workshop，1990，720-726.

［5］ DEILAMANI M.J，ASLI R N Moving object tracking based on mean shift algorithm and features fusion ［J］.Artificial Intelligence and Signal Processing(AISP).2011:48-53.

［6］KALAL Z，MIKOLAJCZYK K，MATAS J.Face-TLD:Tracking-Learning-Detection Applied to Faces［J］.International Conference on Image Processing，2010.

［7］CHEN E，XU Y，YANG X K，et al.Quaternion based optical flow estimation for robust object tracking［J］.Digital Signal Processing，2013，23(1):118-125.

［8］陳添丁，胡鑒，吳滌.稀疏光流快速計算的動態(tài)目標檢測與跟蹤［J］.中國圖象圖形學報，2013，18(12):1593-1600.

［9］WANG J，CHEN F，YANG J M，et al.Transferring visual Prior for online object tracking［J］.IEEE Transactions on Image Processing，2012，21(7):3296-3305.

［10］王愛平，萬國偉，程志全，等.支持在線學習的增量式極端隨機森林分類器［J］.軟件學報，2011，22(9):2059-2074.

［11］袁衛(wèi)紅，盧雁，毛海岑，等.基于光流的運動小目標檢測算法［J］.光學與光電技術，2012，1(10):67-70.

［12］佟國峰，蔣昭炎，谷久宏，等.基于隨機蕨叢的長期目標跟蹤算法［J］.東北大學學報:自然科學版，2013，43(1):4-8.

［13］李勁菊，朱青，王耀南.一種復雜背景下運動目標檢測與跟蹤方法［J］.儀器儀表學報，2010，31(10):2242-2247.

［14］郝志成.決策主導的多模式融合目標跟蹤算法［J］.儀器儀表學報，2013，34(3):487-492.

［15］BREIMAN L.Random forests［J］.Machine Learning，2001，45(1):5-32.

［16］LUCAS B，KANADE T.An iterative image registration technique with an application to stereo vision［C］.Proceedings of DARPA Image Understanding WorkShop.San Francisco，USA:Morgan Kaufmann Publishers Inc.1981，147-151.

［17］CHAN T，VESE L.Active contours without edges［J］.IEEE Transaction on Image Processing，2001，10(2):266-277.

［18］ZDENEK K，JIRI M，KRYSTIAN M.Online learning of robust object detectors during unstable tracking ［J］.On-line Learning for Computer Vision Workshop，2009.