馮俊凱，舒莉，何軍，石佩生

（四川大學計算機學院，成都 610065）

0 引言

遮擋是目標跟蹤過程中常見的情況，圖像中目標被局部或全部遮擋，會對目標跟蹤造成極大的干擾，如何在目標局部受到遮擋的情況下，也能有效地跟蹤目標，是評價跟蹤算法魯棒性的關(guān)鍵指標之一[1]。傳統(tǒng)的跟蹤與檢測算法在跟蹤過程中易出現(xiàn)錯誤積累，從而導致目標飄逸或丟失。將多示例學習思想融合進跟蹤過程中，則可以較好的實現(xiàn)目標的長時間穩(wěn)定跟蹤[2-3]。跟蹤-學習-檢測（Tracking-Learning-Detection：TLD）相結(jié)合的算法[4]是目前常用的跟蹤算法，它可以有效解決目標全部被遮擋后重新出現(xiàn)時的定位問題，但當目標被局部遮擋時，這類算法常常發(fā)生定位漂移的問題。而基于遮擋檢測的跟蹤算法[5]可以較好地解決局部遮擋問題，但對目標完全被遮擋的情況效果較差。子塊跟蹤方法可以同時有效解決局部遮擋與完全遮擋的情況[6-8]，它將目標區(qū)域劃分為數(shù)個子塊，將其分為候選塊與非候選快，之后對候選塊進行獨立跟蹤，根據(jù)子塊的位置定位目標位置。如果候選塊區(qū)域被遮擋，則更換候選塊，進行跟蹤。

已有的子塊跟蹤算法，或是由于不更新子塊信息，或是由于只更新候選塊的信息，不更新非候選塊，導致并不能很好地適應目標較大的逐步形變。并且在使用多尺度滑動窗口對圖像上所有目標可能出現(xiàn)的位置進行檢測時，檢測算法速度較為緩慢的情況。為解決上述問題，提出一種帶運動預測的改進多示例學習目標分塊跟蹤方法。該方法使用Online AdaBoost作為基礎(chǔ)檢測器，弱分類器為隨機蕨叢林，并結(jié)合多示例學習的思想來解決學習模型的誤差積累問題。在對某一幀圖像檢測前首先預測目標大致位置，之后對預測位置附近的區(qū)域進行檢測來減小計算量，縮短檢測耗時。為適應目標較大的逐步形變，在定位完成后更新學習模型時，首先判斷是否有某個子塊被遮擋，之后更新所有未受遮擋的子塊對應的學習模型。

1 多示例學習目標分塊跟蹤

1.1 多示例學習

多示例學習將傳統(tǒng)監(jiān)督學習的學習樣本劃分成包，每個包包含多個示例。它并不為每個示例都進行標記，而是對整個包進行標記，一個包中至少含有一個正示例，則該包為正包，反之為負包。假設(shè)Bi表示多示例學習的第i個包，bij表示包Bi中的第j個示例，令Yi為包 Bi的標記，且 Yi∈{0,1}，yij為 bij的標記，且 yij∈{0,1}，則，通過Online AdaBoost方法訓練學習器，并通過Noisy-OR模型[9]判斷新包的類型P（Yi|Bi）：

其中P（yi|xij）為各示例的似然概率，計算方法如下：

式中H（x）為采用Online AdaBoost訓練的強分類器。sigmoid函數(shù)為

在跟蹤過程中，第一幀給出初始目標位置。學習器將第當前幀目標初始位置及附近的一定數(shù)目的等大小的圖像塊，以及它們的仿射變換，作為一個正包；在正包區(qū)域之外，選取一定數(shù)量的等大小的塊作為負包，進行訓練。在隨后的幀序列中，檢測器使用學習器上一幀學習到的模型，對目標可能出現(xiàn)的區(qū)域進行檢測，選取可能性最高的位置作為這一幀目標的預測位置，并更新學習模型。

1.2 Online AdaBoost分類器

Online AdaBoost算法對模型的訓練，分為模型初始化和模型更新兩個階段。在模型初始化階段，Online AdaBoost算法與經(jīng)典AdaBoost相似[10]。而在模型更新階段，Online AdaBoost算法并不是對檢測到的目標位置重新學習建模，而是保留上一幀學習到的t個錯誤率最低的弱分類器，替換剩下T-t個錯誤率較高的弱分類器為本次學習過程中產(chǎn)生的最優(yōu)弱分類器來實現(xiàn)模型更新。本文使用隨機蕨森林作為弱分類器。

蕨（ferns）是一種簡化的樹[11]，隨機蕨森林即是一種隨機森林的衍生算法，它高效，精確，并且能夠適應在線更新[12]。隨機蕨森林首先隨機的選擇一個特征子集，用以生成數(shù)個蕨，分類時使用半樸素貝葉斯的方式，即公式（3），綜合各個蕨的分類結(jié)果計算最終結(jié)果。

公式中，y∈{0,1}，是圖像子塊的標記。L為特征子集的總數(shù)，F(xiàn)i為特征子集。單個蕨會在圖像樣本上隨機的做S次2bitBP[13]（2bit Binary Patterns）特征提取運算，每次提取得到一個特征值xi∈[0,3]，S次提取運算后得到由xi組成的特征向量x，作為一個特征子集。每個特征都有四種可能取值，因此單個蕨是一棵深度為S+1的完全四叉樹，非葉子節(jié)點的每一層都是一個特征，根據(jù)特征值的不同走向不同的分支。葉子節(jié)點則是不同特征向量所表示的圖像塊是否是目標區(qū)域的后驗概率，S個特征就會產(chǎn)生4s個葉節(jié)點。

1.3 目標分塊跟蹤

為解決局部遮擋問題，需要將目標區(qū)域分成若干子塊，從子快中選出數(shù)塊作為候選快，之后對每個候選塊進行獨立跟蹤，當某個跟蹤的子塊被遮擋，可以換其他非候選塊進行跟蹤。

首先將目標區(qū)域均勻分割為K塊，如圖1所示，所有塊的集合記作P。需要注意，K越大，每個子塊所包含的信息越少，跟蹤效果越差，本文K為8。分塊時，記錄每塊的位置信息和偏移信息，以供定位目標時使用。中，是每個塊的第一個像素坐標（即最左上角的像素坐標）為每塊的寬和高。設(shè)為t幀的目標坐標，t為幀序號，則Ok中各值的計算方法如下：

計算每個滑動窗口?j和子塊Pi之間特征向量的相似度Sij，得到Sij最大的M個子塊構(gòu)成候選塊集合SP，余下子塊放入非候選塊集合UP。本文實驗中M=4。之后對候選塊進行獨立跟蹤，如果某個候選塊在跟蹤過程中遭遇遮擋，則從非候選塊集合中選擇一塊替換被遮擋的候選塊進行跟蹤定位。在每一幀的所有候選塊定位完成后，根據(jù)各候選塊的位置與其偏移信息，定位目標在當前幀的最終位置。

圖1 目標區(qū)域分割

2 運動預測與子塊模型更新

2.1 運動預測

檢測算法在t幀需要對圖像中所有目標可能出現(xiàn)的區(qū)域進行檢測，以確定目標的位置，通常這個區(qū)域是整個圖像。在結(jié)合多尺度滑動窗口之后，分類器需要對大量的圖像塊進行分類，這個過程非常消耗時間。在現(xiàn)實情況中，視頻中的目標較少會進行無規(guī)則的運動，因此對其運動情況進行快速預測，可以有效減少檢測器需要檢測的區(qū)域。

本文使用拉格朗日插值算法對目標運動情況進行近似擬合，算法公式如下：

其中n為插值次數(shù)。li(x)為插值基函數(shù)，可以表示為：

拉格朗日插值算法的具體數(shù)學定義請參見文獻[14]。分別使用兩次插值算法，根據(jù)已有目標運動信息，對目標中心點在X軸與Y軸上的運動情況進行擬合，兩部分結(jié)合以預測下一幀目標的大致位置。該算法應用中，xi是作為插值節(jié)點的幀序號，yi是在xi幀中目標中心位置的X軸或Y軸坐標，x則為需要預測的那一幀的幀序號?？紤]到只需要預測下一幀目標的中心位置，在這里x=xn+1，計算結(jié)果為xn+1幀的X軸或Y軸坐標。拉格朗日插值算法計算速度很快，但是在插值節(jié)點數(shù)量過多時會產(chǎn)生Range現(xiàn)象，插值節(jié)點數(shù)量的不同會影響預測精度。如圖2所示，實驗發(fā)現(xiàn)，每次預測插值節(jié)點數(shù)量定為2效果最好，這也意味著，事實上兩次預測均為線性預測，因此式（5）可以簡化為兩點式：

從視頻第三幀開始，每次執(zhí)行檢測算法檢測t幀目標位置之前，先令x0=t-2和x1=t-1，x2=t時的計算結(jié)果即為目標的預測位置，之后檢測器對其周圍區(qū)域進行檢測。如果檢測失敗，則對整個圖像進行檢測。如果依然失敗，說明目標受到大面積遮擋，接下來的幀將不執(zhí)行預測，直到重新檢測到目標。

3.2 改進的子塊模型更新策略

在理想情況下，第一幀之后的幀序列，每一幀都能檢測出M個候選塊對應的目標子塊根據(jù)分塊時記錄的每塊偏移信息，對整體目標進行定位，可以使用如下方法進行定位：

圖2 五種場景共3059幀環(huán)境下不同節(jié)點數(shù)量預測值與實際值的平均誤差

方法中的Xt，Yt表示目標區(qū)域第一個像素所在坐標，Wt，Ht表示目標區(qū)域的寬和高，k表示候選塊集合SP中的塊序號。定位算法計算后的結(jié)果即為本幀目標所在區(qū)域At+1。在沒有遮擋的情況下，可以在得到t+1幀目標區(qū)域后，重新分塊、提取樣本、使用Online Ada?Boost的算法，更新每一個目標子塊對應的學習模型。但如果目標區(qū)域遭到遮擋，目標的檢測與學習模型的更新都可能會出現(xiàn)問題。

當目標出現(xiàn)局部遮擋，并且遮擋出現(xiàn)在候選塊區(qū)域，檢測時就能發(fā)現(xiàn)。檢測器在對當前幀進行檢測時，如果某一塊出現(xiàn)在多尺度滑動窗口內(nèi)所有的樣本檢測概率均小于50%的情況，則認為該塊受到遮擋。候選塊中某一塊SPk被遮擋時，可以從非候選塊集合UP中選擇一塊，替換SPk對當前幀進行檢測。如果依然被遮擋，重復此過程。如果遮擋出現(xiàn)在非候選塊區(qū)域，檢測時由于只檢測候選塊區(qū)域，所以不會影響目標的檢測，但同時檢測階段也無法發(fā)現(xiàn)目標被遮擋。

當檢測與定位完成后，如果直接更新所有子塊的學習模型，被遮擋區(qū)域的更新將會產(chǎn)生巨大的誤差，因此在更新前，需要使用t+1幀的目標位置，對UP集合內(nèi)的子塊做一次自檢測，即使用每個子塊的檢測器，對其在t幀對應的目標區(qū)域的子塊作為樣本進行分類，分類結(jié)果為正的概率即為該子塊的自檢正確率，過程如圖3。自檢正確率小于50%的子塊認為被遮擋，本次不對其學習模型進行更新。結(jié)合在線多示例學習分類器，本文算法整體如下：

算法1運動預測的多示例學習分塊目標跟蹤算法

輸入：·圖像序列 I1，I2，···，In，并給出第一幀 I1的初始目標區(qū)域A1；

執(zhí)行：

·將A1分割為K塊，計算并記錄每塊信息Pk；

·選擇自檢率最高的M塊作為候選塊，其余塊為非候選塊；

·為每一個子塊作為目標區(qū)域，建立檢測器，并訓練學習模型；

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

為驗證本文提出的多示例跟蹤方法的有效性，本文從公開的跟蹤測試視頻庫中選取五種場景共3059幀的圖像序列進行測試，同時對改進前的多示例學習分塊目標跟蹤（MFT[8]）算法，以及常用的 TLD[13]，MIL[15]，CT[16]三種算法與本文改進后的算法進行比較。在實驗中，每個隨機蕨提取6次特征，每個蕨森林擁有8個蕨，強分類器由5個隨機蕨森林構(gòu)成，更新時設(shè)置t=3，即保留3個錯誤率最低的隨機蕨森林。每次更新運動預測完成后，檢測區(qū)域為以預測點為中心，長寬均為max（length,width）*0.8的矩形區(qū)域進行檢測。其他算法的參數(shù)參考相應文獻。在誤差表示上，使用中心誤差與重疊率。中心誤差表示跟蹤結(jié)果的中心與實際目標的中心之間的歐幾里得距離；重疊率為跟蹤標注的矩形框與目標真實位置的矩形框的重疊比率，計算方法為 overlap=area（A∩B）/area（A∪B），其中 A，B 為跟蹤標注的矩形框與目標真實位置的矩形框，area（）計算面積。

圖3 自檢正確率計算過程，此處8個樣本對應8個檢測器

表1 各算法在各場景下的中心誤差，重疊率與平均幀數(shù)

如表1所示，在算法的處理速度上，本文算法相比改進前的MFT算法有明顯提升，但處理速度的提升幅度并不如檢測面積縮小的那么大，原因在于本算法并沒有降低學習階段的計算量，而且在學習模型更新前加入了遮擋檢測，學習模型更新時要為所有未遮擋的子塊進行更新，加大了計算量。目標分塊的方法需要對每一個子塊分別建立學習模型與檢測器，雖然這將使計算量提升，但各子塊間的學習與檢測計算完全獨立，互相之間并無同步問題，使用多線程計算后處理速度并不比TLD與MIL算法慢。CT算法則主要是基于壓縮感知的特征降維，降維后特征提取簡單，分類過程也是樸素貝葉斯分類器，處理速度非?？臁?/p>

圖4 各算法在各場景下的跟蹤結(jié)果

在算法的精度上，改進算法相比原算法有小幅提升。在FaceOcc2與David場景中，MFT改進算法與原算法差別不大，可能是這兩個序列跟蹤的目標是人臉，整個跟蹤過程中目標形狀并未出現(xiàn)變化，而在Walk?ing2與Woman中跟蹤的是走動的行人，行人身體的小幅擺動在受遮擋之后，使改進算法的表現(xiàn)更好。

從圖4可以更清晰的看出各個算法的跟蹤效果。FaceOcc2與David是兩種對人臉進行跟蹤的場景。在FaceOcc2中，背景基本保持不變，各算法均能保持較好的跟蹤，但是最后一張圖片中，在帽子與書本同時遮擋面部的情況下，改進前與改進后的多示例分塊學習算法都跟蹤卻失敗了，這是因為改進后的算法在更新學習模型之前，會先進行遮擋檢測，發(fā)現(xiàn)遮擋后不更新被遮擋的子塊，使被帽子遮擋的子塊不會被更新，而改進前的算法則不會更新非候選塊，這樣的策略導致在書本遮擋之后，目標被遮擋面積過大，跟蹤失敗。

在Walking2、Woman與Suv中，目標都是在運動中遭到遮擋的，這里可以明顯看出改進前與改進后的多示例學習分塊跟蹤算法都有較高的魯棒性。在Walk?ing2場景中，目標受到相似物體的遮擋時，預先預測目標位置以減小檢測區(qū)域的改進算法與跟蹤-學習-檢測相結(jié)合的TLD算法能更好的跟蹤目標。Suv場景中，目標在運動中經(jīng)常遭到樹木的完全遮擋，CT算法與MIL算法在前期跟蹤就失敗了，而MFT與其改進算法在整個跟蹤過程中均有較好表現(xiàn)，可見本文算法在局部遮擋與完全遮擋后目標重新出現(xiàn)兩種情況下均能實現(xiàn)穩(wěn)定的跟蹤。

4 結(jié)語

目標跟蹤是計算機視覺領(lǐng)域的重要研究內(nèi)容，應用場景廣泛。本文在多示例學習目標分塊跟蹤方法的基礎(chǔ)上進行改進，在對圖像進行檢測前首先預測目標的大致位置，以減少檢測區(qū)域來提升算法處理速度，同時在更新學習模型前先檢測目標是否被局部遮擋，之后更新所有未被遮擋的子塊，以提高跟蹤會發(fā)生形變目標的能力。試驗表明，算法改進后，算法處理速度有明顯提升，并且在被跟蹤目標有一定程度形變時，跟蹤精度也有所提升。但算法改進后，依然不能對變化較大的目標進行穩(wěn)定跟蹤，這是下一步工作需要解決的問題。

參考文獻：

[1]薛陳，朱明，劉春香.遮擋情況下目標跟蹤算法綜述[J].中國光學與應用光學,2009,2（5）:388-394.

[2]X Qi,Y Han.Incorporating Multiple SVMs for AutoMatic Image Annotation.Pattern Recognition,2007,40（2）:728-741.

[3]Viola P,Platt J C,Zhang C.Multiple Instance Boosting for Object Detection[C].International Conference on Neural Information Processing Systems.MIT Press，2005:1417-1424.

[4]J Gall,A Yao,N Razavi.Hough Forests for Object Detection,Tracking,and Action Recognition[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2011，33（11）:2188-202.

[5]邢晨,薛模根,袁廣林,等.基于Online AdaBoost的偏振圖像目標跟蹤[J].合肥工業(yè)大學學報（自然科學版）,2011（11）:1650-1654.

[6]Naik N,Patil S,Joshi M.A Fragment Based Scale Adaptive Tracker with Partial Occlusion Handling[C].TENCON 2009-2009 IEEE Region 10 Conference.IEEE,2009:1-6.

[7]Adam A,Rivlin E,Shimshoni I.Robust Fragments-Based Tracking Using the Integral Histogram[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition,New York,USA,2006:798-805.

[8]才華,陳廣秋,劉廣文.遮擋環(huán)境下多示例學習分塊目標跟蹤[J].吉林大學學報（工學版）.2017,47（1）:281-287.

[9]Zhang C，Platt J C，Viola P A.Multiple Instance Boostingfor Object Detection[C].Advances in Neural Information Processing Systems，2005：1417-1424.

[10]邢晨,薛模根,袁廣林,等.基于Online AdaBoost的偏振圖像目標跟蹤[J].合肥工業(yè)大學學報（自然科學版）,2011（11）:1650-1654.

[11]M.Ozuysal,P.Fua,V.Lepetit.Fast Keypoint Recognition in Ten Lines of Code.CVPR，2007，5.

[12]Zdenek Kalal,Jiri Matas,Krystian Mikolajczyk P-N Learning:Bootstrapping Binary Classifiers by Structural Constraints.CVPR,2010 June 13-18.

[13]Z.Kalal,J.Matas,K.Mikolajczyk.Online Learning of Robust Object Detectors During Unstable Tracking.OLCV,2009.3,5,7.

[14]李慶揚.數(shù)值分析[M].清華大學出版社，2008.

[15]Babenko B,Yang M H,Belongie S.Robust Object Tracking with Online Multiple Instance Learning[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2011,33（8）:1619.

[16]Zhang K,Zhang L,Yang M H.Fast Compressive Tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36（10）:2002-2015.