基于局部分塊和模型更新的視覺跟蹤算法

侯志強 黃安奇余旺盛 劉 翔

(空軍工程大學信息與導航學院 西安 710077)

基于局部分塊和模型更新的視覺跟蹤算法

侯志強 黃安奇*余旺盛 劉 翔

(空軍工程大學信息與導航學院 西安 710077)

針對目標跟蹤過程中的目標表觀變化、背景干擾及發生遮擋等問題，該文提出一種基于局部分塊和模型更新的視覺跟蹤算法。該文采用粗搜索與精搜索相結合的雙層搜索方法來提高目標的定位精度。首先，在包含部分背景區域的初始跟蹤區域內構建目標模型。然后，利用基于積分直方圖的局部窮搜索算法初步確定目標的位置，接著在當前跟蹤區域內通過分塊學習來精確搜索目標的最終位置。最后，利用創建的模型更新域對目標模型進行更新。該文主要針對分塊跟蹤中的背景抑制、模型更新等方面進行了研究，實驗結果表明該算法對目標表觀變化、背景干擾及遮擋情況的處理能力都有所增強。

視覺跟蹤；局部分塊模型；窮搜索；局部分塊學習；模型更新

1 引言

視覺跟蹤作為計算機視覺領域中最困難和最為核心的問題之一，近年來一直是國內外研究的熱點[1?4]。目標在運動過程中外觀的不斷變化、背景元素的干擾以及遮擋情況的處理等問題是視覺跟蹤的研究難點。如何構建能夠適應外觀變化和復雜環境的目標模型并進行及時有效的更新是解決問題的關鍵。經典的均值遷移(mean shift)算法[5,6]利用區域顏色直方圖表示目標模型，對簡單場景下的運動目標可以實現準確有效的跟蹤，但是對光照變化和遮擋情況都比較敏感。文獻[7]使用多示例學習(Multiple Instance Learning, MIL)來訓練分類器，構造了一個更加魯棒的判別式外觀模型。近幾年來，圖像的稀疏表示使其能夠用很少的數據捕獲感興趣目標的重要信息，其被引入到視覺跟蹤中后，提高了算法對光照、姿態變化及遮擋情況的適應性[8]。基于局部分塊模型的跟蹤算法由于能檢測出目標區域中發生遮擋或外觀變化的相應分塊而引起許多學者的關注。根據產生方式的不同，分塊方法可以分為規則分塊和不規則分塊兩大類。其中，規則分塊以文獻[9]提出的基于分塊的跟蹤(Fragments-based Tracking, Frag)最具代表性。另外，文獻[10]提出一種基于直方圖和關節式分塊的跟蹤算法(Tracking with Histograms and articulating Blocks, BHT)，該算法針對非剛體目標提出一種基于動態分塊的目標模型，增強了算法對非剛性形變的適應性。文獻[11]提出一種自適應的分塊方法，并利用尺度不變特征變換(Scale Invariant Feature Transform, SIFT)解決目標的尺度變化問題。不規則分塊以文獻[12]和文獻[13]提出的超像素跟蹤(SuperPixel Tracking, SPT)最具代表性，超像素具有較為明確的語義信息，因此能較好地建立具有結構信息的目標模型，提高了跟蹤算法的魯棒性。

本文使用的分塊方法為規則分塊，而當前基于規則分塊模型的跟蹤算法主要存在以下幾個問題：(1)分塊方式。不考慮子塊之間差異的簡單均勻分塊，容易造成跟蹤漂移。(2)背景抑制。現有的規則分塊跟蹤算法對復雜背景變化的適應性較差。(3)模型更新。在長時間的跟蹤過程中，目標和背景都會發生較大的變化。如果不考慮模型更新，跟蹤結果會逐漸偏離正確位置，因此，更新目標模型以適應目標和背景的變化，是提高視覺跟蹤算法魯棒性必須要考慮的問題[14]。針對以上規則分塊模型存在的問題，本文受超像素跟蹤[12]的啟發，采用聚類分析的方法來抑制背景干擾，并通過創建模型更新域，將跟蹤結果合理地組織起來，從而實現對目標模型的有效更新。需要說明的是，本文雖然同樣涉及聚類分析，但是在分塊方法、模型構建、模型更新以及跟蹤框架上都與超像素跟蹤方法有很大不同。本文主要針對分塊跟蹤中的模型構建、模型更新和背景抑制等問題進行了研究，提出了一種基于局部分塊和模型更新的視覺跟蹤算法。實驗結果表明，本文算法與同類算法相比具有較強的魯棒性。

2 分塊模型的構建

本文在描述目標時，采用了兩種方式：一種為生成式模型，用于目標的初步搜索；另一種為判別式模型，用于目標的精確定位。本文采用HSI顏色空間的10×10×5歸一化直方圖對目標的顏色特征進行描述。

2.1 生成式模型的構建

用來構建目標生成式模型的目標區域，即目標模板，通過在第1幀圖像中手動標定得到，如圖1紅框內的圖像區域。目標模板用于對目標的初步搜索，并根據搜索結果來確定當前跟蹤區域。目標模板的顏色直方圖可以表示為

式中，r為顏色直方圖的維數。

2.2 判別式模型的構建

文獻[9]提出的分塊跟蹤在進行分塊建模時，沿水平和垂直方向將目標區域分成9×2和2×9的分塊集合，如圖2所示。分塊模型由于在一定程度上考慮了目標的空間結構信息，因此具有較為突出的抗遮擋能力。在初始幀選定目標區域時，往往會包含部分背景信息，這些信息會對目標定位的精度造成不利影響。本文對目標區域及周圍的背景區域共同分塊，通過聚類算法將特征相似的子塊聚到同一類中，從而有效地突出目標特征并抑制背景特征。本文構建目標判別式模型的思路為：

(1)將整個初始跟蹤區域分為n2個子塊。設定其中的背景區域大小為目標區域的3倍，如圖1所示。將目標區域內像素的置信值(屬于目標前景的概率)賦為1，背景區域內像素的置信值賦為-1，像素的置信值記為p(i,j)。每個分塊的初始置信值(k=1,2,…,n2)為分塊內所有像素置信值的平均值。

(2)提取各個分塊的顏色特征，并用顏色直方圖對其進行描述，構建特征空間：

式中，fk為第k個子塊的特征向量，2n為子塊的個數。

(3)在特征空間內對分塊進行聚類，并根據聚類結果計算出聚類成員屬于目標前景的概率。由于均值遷移聚類方法更加注重數據對象間的類似度和分布情況，因此選擇均值遷移聚類方法對分塊特征進行聚類，得到N個不同的聚類clu(m)(m=1,2,…,N)，并且每個聚類包含Nf個特征向量{fk|fk∈clu(m)}。聚類完成后，特征相似的分塊被聚到同一類內，類的置信值為類內所屬分塊初始置信值的均值

圖1 本文算法目標分塊示意圖

圖2 文獻[9]分塊方法

式中，clum為包含分塊特征的聚類結果。圖3所示為目標模型構建的示意圖。

3 本文跟蹤算法

為了提高算法的跟蹤精度，本文采用粗搜索與精搜索相結合的雙層搜索方法來實現目標的定位。當輸入新的一幀圖像時，首先利用基于積分直方圖的窮搜索算法對目標進行快速定位并確定當前跟蹤區域；然后對當前跟蹤區域進行局部分塊，分別計算每個分塊到模型中各類的特征距離，并依據最近鄰準則將模型中聚類的置信值賦給各個分塊；最后根據分塊置信值總和最大準則確定目標的最終位置。

3.1 基于積分直方圖的目標窮搜索

本文在目標初步定位時采用局部窮搜索算法來獲取最優結果。窮搜索算法需要搜索區域內反復計算矩形區域的直方圖，實時性較差。而文獻[15]提出的積分直方圖方法實現了快速窮搜索，能保證在獲得全局最優解的前提下實現快速甚至是實時的跟蹤。本文在進行局部窮搜索時，首先確定目標在當前幀的搜索區域，將搜索范圍設定為以上一幀跟蹤結果為中心的4倍于目標尺寸的范圍。然后利用目標生成式模型在搜索區域內進行快速窮搜索，得到目標的初始位置(x',y')。

3.2 基于分塊學習的目標窮搜索

在傳統的分塊跟蹤算法中，首先利用快速窮搜索方法得到各個分塊的位置，然后對分塊的位置進行加權融合得到目標的最終位置。雖然在對各個分塊進行加權時，考慮了分塊與中心位置的空間距離，但是仍然不能很好地抑制背景元素的干擾。因此，本文根據在第1幀建立的判別式分塊模型，采用局部分塊學習的方法來有效地抑制背景干擾。

以目標的初始位置為中心確定目標在當前幀的跟蹤區域，由于窮搜索得到的初始位置已經較為準確，因此適當縮小當前跟蹤區域的范圍以減少計算量，此處設定為以初始位置為中心的2倍于目標尺寸的范圍。基于分塊學習的跟蹤可以分為以下幾個步驟：

步驟1 局部分塊。輸入新的一幀圖像后，在當前跟蹤區域內進行局部分塊，并進行特征描述。

步驟2 計算置信圖。首先計算當前幀每個分塊到目標模型中各類的特征距離，使用巴氏系數進行相似度度量，相似度最大則距離最小。然后將距離最小類的置信值賦給該分塊，分塊內像素的置信值與分塊相同。

步驟3 目標搜索。根據得到的目標置信圖，在當前跟蹤區域內，針對任意一個目標候選區域，都可以計算得到對應的目標置信值。

式中，(x,y)為目標候選區域的中心坐標，λ為歸一化系數，p(i,j)為候選區域內任意一點的置信值。由于目標前景像素的置信值范圍為(0,1]，而背景像素的置信值范圍為[?1,0)，因此跟蹤框所覆蓋像素置信值的總和越大，所覆蓋區域屬于目標的概率就越大。

圖3 目標模型構建示意圖

然而式(5)中計算得到的目標置信值并沒有考慮目標的尺度變化，為了增強算法對目標尺度變化的魯棒性，在式(5)中加入尺度調節系數為

當目標置信值達到最大時，所對應的坐標就是目標最終的中心位置

本文在基于分塊學習的目標搜索過程中，同樣利用了積分圖技術，首先在整張置信圖中根據式(6)構建積分數據結構，然后通過快速窮搜索來實現目標的最終定位。

3.3 基于遮擋判斷的模型更新

模型更新需要解決兩個問題：一個是模型更新時機，即什么時候更新模型；另一個是新模型的選擇，即用什么模型更換舊模型。針對模型更新時機問題，需要重點解決的是遮擋判斷問題，目標被遮擋時不能將遮擋物的信息更新到目標模型內。針對模型選擇問題，本文通過建立一個模型更新域，將L幀圖像的跟蹤結果合理地組織起來，發掘出被跟蹤目標的本質信息，從而更好地解決模型更新問題。

首先根據提出的局部分塊模型，計算得到遮擋判斷因子θt并設定遮擋判斷閾值θ0。當θt＜θ0時，每隔U幀對模型更新域進行更新，每隔W幀對目標模型進行更新；當θt＞θ0時，對模型更新域和目標模型都停止更新，從而防止引入遮擋物的信息，避免發生跟蹤漂移。同時為了減少由于遮擋造成的跟蹤偏差，在判斷遮擋發生后用上一幀的跟蹤結果來代替當前幀的跟蹤結果。遮擋因子定義為

式中，uV為模型更新域內所有目標歸一化置信值的平均值，根據式(5)計算得到。

模型更新域的建立與更新：將跟蹤過程中得到的L幀跟蹤結果，包括當前幀跟蹤區域的分塊結果及目標的最大置信值Vk，存入更新域中并按照置信值大小進行排序。在未發生遮擋的情況下，每隔U幀將當前幀的跟蹤結果存入更新域，并刪除置信值最小的一幀跟蹤結果，從而保證更新域既是最新的又是最優的。

目標模型的更新：由于本文算法在對目標進行定位時，采用了分步跟蹤的方法，對目標的描述也采取了兩種方式。因此，在未發生遮擋的情況下，每隔W幀對兩種形式的目標模型都要進行更新。

(1)生成式模型的更新。對更新域中目標置信值最大的跟蹤結果和初始跟蹤區域中的目標模板進行線性加權來更新目標生成式模型。

(2)判別式分塊模型的更新。首先選擇更新域中前L/2幀目標置信值較大的跟蹤結果，對選擇的所有分塊進行聚類分析，重新對類和分塊進行標記，從而實現模型的更新。

本文跟蹤算法的流程圖如圖4所示，灰色區域為算法的模型更新過程。

4 實驗結果與分析

圖4 本文跟蹤算法流程圖

實驗中，本文算法的參數設置為：分塊數目n2=144，均值遷移聚類的帶寬B=0.2，遮擋判斷閾值θ0=0.48，模型更新參數L=6, U=1, W=6。上述參數在所有實驗中的設置是一樣的。本文算法的仿真環境為：Intel G1610 CPU, 2G內存，Windows XP系統，MATLAB 7.12.0。

為了驗證本文算法在處理遮擋、背景干擾及光照變化等情況的有效性，在6組具有挑戰性的視頻序列上進行了對比測試，各組序列的跟蹤難點如表1所示，視頻序列及目標真實位置全部來自文獻[2]。本文算法采用分塊模型并且涉及模型的在線更新，因此有針對性地選擇以下4種參考算法：Frag[9], BHT[10], MIL[7]和SPT[12]。Frag算法和MIL算法的代碼來自文獻[2]，BHT算法的代碼來自文獻[10], SPT算法的代碼來自文獻[13]發布的最新版本。為了保證實驗對比的公平性，本文對每個算法的參數都進行了仔細調整，或是直接采用算法設定好的參數，比如SPT算法在測試序列Lemming, Bolt和Basketball時的參數，并從5組測試結果中選擇最優的一組用來實驗對比。

4.1 定性對比

(1)Faceocc1序列 如圖5(a)所示，Frag算法、BHT算法、SPT算法和本文算法都采用了分塊模型，因此能夠有效地處理遮擋情況。MIL算法不能適應遮擋情況，跟蹤誤差較大。

圖5 跟蹤算法性能的定性比較

表1 測試視頻序列說明

(2) Lemming序列 如圖5(b)所示：Frag算法和BHT算法由于不能有效地抑制背景干擾，跟蹤誤差較大，最終丟失了目標。SPT算法剛開始可以較好地跟蹤目標，但是隨著跟蹤的進行，在模型更新過程中引入了過多的誤差，最終導致目標丟失(從第902幀開始)。MIL算法和本文算法都可以較好地跟蹤上目標，但本文算法在處理目標旋轉上更有優勢，如第998幀。

(3)Bolt序列 如圖5(c)所示：Frag算法和MIL算法跟蹤誤差較大，最終都丟失了目標。BHT算法由于其在處理非剛性形變上的優勢，跟蹤誤差較小。SPT算法和本文算法通過聚類分析能夠很好地突出前景目標，抑制背景干擾，從而增強了對非剛性形變的適應性。

(4)Basketball序列 如圖5(d)所示：Frag算法雖然成功完成了跟蹤，但是跟蹤誤差較大。BHT算法和MIL算法開始時可以較為準確地跟蹤目標，但是后面都出現了丟失目標的情況。SPT算法的跟蹤誤差最小。本文算法對遮擋和背景干擾都有一定的魯棒性，跟蹤誤差也比較小。

(5)David序列 如圖5(e)所示：Frag算法和BHT算法由于都不具有有效的模型更新機制，跟蹤誤差較大。SPT算法在更新模型的過程中引入了一定的背景元素，跟蹤誤差較大。MIL算法能夠對構建的判別式外觀模型進行有效地在線更新，跟蹤誤差較小。本文算法在更新模型的過程中，通過合理地選擇特征信息，有效地抑制了背景干擾，取得了較好的跟蹤結果。

(6)Trellis序列 如圖5(f)所示：Frag算法和BHT算法顯然不能適應這種復雜場景，跟蹤誤差較大。MIL雖然對光照變化具有一定的魯棒性，但是不能夠有效地抑制背景干擾，導致跟蹤算法失效。SPT算法和本文算法能夠在更新模型的同時有效地抑制背景元素的干擾，取得了較為準確的跟蹤結果。

4.2 定量分析

為了定量地評價跟蹤算法的性能，本文采用中心位置誤差(Center Location Error, CLE)來對以上4種算法的跟蹤結果進行比較。CLE用來衡量算法的跟蹤精度，第k幀CLE的計算公式為

式中，(xk,yk)為第k幀跟蹤結果中目標中心位置的坐標，(,)為對應幀目標真實位置的中心坐標。CLE的單位為像素，數值越小，表明算法的跟蹤精度越高。

圖6所示為各個算法在跟蹤視頻序列時的中心位置誤差，由CLE曲線可見：Frag算法在Faceocc1序列和Basketball序列上的跟蹤誤差較小，而在其他幾段序列上的跟蹤誤差都比較大。BHT算法在Bolt序列上的跟蹤結果較為準確，而在其他序列上的跟蹤誤差都比較大。MIL算法在Lemming序列和David序列中具有較小的跟蹤誤差。除了Lemming序列，SPT算法在其余幾段序列上都取得了較為理想的跟蹤結果。本文算法在構建目標模型時采取分塊的方式，有效地利用了目標的空間信息，增強了對遮擋情況的適應性；在構建目標的判別式外觀模型時，通過聚類的方法有效地突出了前景目標，增強了算法抑制背景干擾的能力；在進行模型更新時，通過構建模型更新域，既保留了目標可靠的歷史信息，又不斷學習目標新的特征，利用聚類算法使得在更新模型的同時有效地抑制了背景干擾。相對而言，本文算法在所有測試序列上得到的CLE都比較小，驗證了本文算法的優勢。

表2給出了各個算法的平均中心誤差。由表中數據可知：本文算法在Lemming序列、Bolt序列和David序列上取得了最優結果，在其余序列上取得了次優結果。SPT算法也取得了較好的跟蹤結果，在Basketball序列和Trellis序列上取得了最優結果。

4.3 與SPT算法的對比分析

SPT算法有效地利用了目標的中層視覺特征，增強了算法對遮擋及表觀變化的適應性。但是SPT算法依然存在一些問題，首先SPT算法需要建立在上一幀具有一定的跟蹤精度且目標運動在空間上連續的基礎上，否則容易引入跟蹤誤差。雖然SPT算法具有一定的從跟蹤漂移中恢復的能力，但是需要被引入的特征在背景中大量存在，才能通過聚類分析將跟蹤框中引入的錯誤信息聚類到背景中。其次，SPT算法通過一個簡單的滑動窗口來利用存儲的所有特征信息對模型進行更新，同樣容易帶來跟蹤偏差，如圖5(b)所示。

圖6 中心位置誤差比較

表2 目標中心位置平均誤差比較

本文算法通過局部窮搜索來確定目標的初始位置，保證了用于分塊提取的當前跟蹤區域的正確性。并且本文算法通過構建模型更新域，選擇其中可靠的特征信息用于更新，從而防止在更新過程中引入跟蹤誤差。實驗證明，本文算法取得了與SPT算法相近或是更好的跟蹤結果。本文算法在分塊提取和置信圖計算上的復雜度也比較低，并在快速窮搜索的框架下進行實現，實時性較好。

5 結束語

針對現有分塊跟蹤算法存在的問題，本文提出了一種基于局部分塊和模型更新的視覺跟蹤算法。算法通過聚類分析，構建了一種能夠有效突出前景特征并抑制模型漂移的判別式分塊模型。在所構建的模型基礎上，首先利用基于積分直方圖的快速窮搜索算法初步確定目標的位置，然后通過分塊學習，得到的目標最大置信值對應的位置即為目標的最終位置。算法在構建模型更新域的基礎上還提出了一種基于遮擋判斷的模型更新方法，能夠在對模型進行更新的同時有效地抑制背景元素。實驗結果表明，本文算法能夠較好地處理遮擋、背景干擾和目標表觀變化等情況，得到了更為準確的跟蹤結果。本文算法只采用了簡單的HSI顏色特征，下一步工作將考慮融合多種特征對目標進行描述，進一步提高算法的有效性和魯棒性。

[1] Yang Han-xuan, Shao Ling, Zheng Feng, et al.. Recent advances and trends in visual tracking: a review[J]. Neurocomputing, 2011, 74(18): 3823-3831.

[2] Wu Yi, Lim J, and Yang M H. Online object tracking: a benchmark[C]. Proceedings of the Computer Vision and Pattern Recognition, Portland, United States, 2013: 2411-2418.

[3] Smeulders A W M, Chu D M, Cucchiara R, et al.. Visual tracking: an experimental survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013: DOI: 10. 1109/TPAMI. 2013. 230.

[4] Lu Zhang and Laurens V D M. Structure preserving object tracking[C]. Proceedings of the Computer Vision and Pattern Recognition, Portland, United States, 2013: 1838-1845.

[5] Comaniciu D, Ramesh V, and Meer P. Real-time tracking of non-rigid objects using mean shift[C]. Proceedings of the Computer Vision and Pattern Recognition, Hilton Head Island, United States, 2000: 142-149.

[6] Comaniciu D, Ramesh V, and Meer P. Kernel-based objecttracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-577.

[7] Babenko B, Yang M H, and Belongie S. Robust object tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1619-1632.

[8] Wang Dong, Lu Hu-chuan, and Yang M H. Online object tracking with sparse prototypes[J]. IEEE Transactions on Image Processing, 2013, 22(1): 314-315.

[9] Adam A, Rivlin E, and Shimshoni I. Robust fragments-based tracking using the integral histogram[C]. Proceedings of the Computer Vision and Pattern Recognition, New York, United States, 2006: 798-805.

[10] Nejhum S, Ho J, and Yang M H. Online visual tracking with histograms and articulating blocks[J]. Computer Vision and Image Understanding, 2010, 114(8): 901-914.

[11] 董文會, 常發亮, 李天平. 融合顏色直方圖及SIFT特征的自適應分塊目標跟蹤方法[J]. 電子與信息學報, 2013, 35(4): 770-776. Dong Wen-hui, Chang Fa-liang, and Li Tian-ping. Adaptive fragments-based target tracking method fusing color histogram and SIFT features[J]. Journal of Electronics & Information Technology, 2013, 35(4): 770-776.

[12] Wang Shu, Lu Hu-chuan, Yang Fan, et al.. Superpixel tracking[C]. Proceedings of the IEEE International Conference on Computer Vision, Barcelona, Spain, 2011: 1323-1330.

[13] Yang Fan, Lu Hu-chuan, and Yang M H. Robust superpixel tracking[J]. IEEE Transactions on Image Processing, 2014, 23(4): 1639-1651.

[14] Matthews I, Ishikawa T, and Baker S. The template update problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(6): 810-815.

[15] Porkili F. Integral histogram: a fast way to extract histograms in cartesian spaces[C]. Proceedings of the Computer Vision and Pattern Recognition, San Diego, United States, 2005: 829-836.

侯志強： 男，1973年生，博士，教授，研究方向為圖像處理、計算機視覺和信息融合.

黃安奇： 男，1988年生，碩士生，研究方向為視覺跟蹤.

余旺盛： 男，1985年生，博士生，研究方向為圖像分割、視覺跟蹤.

Visual Object Tracking Method Based on Local Patch Model and Model Update

Hou Zhi-qiang Huang An-qi Yu Wang-sheng Liu Xiang
(The Information and Navigation Institute, Air Force Engineering University, Xi'an 710077, China)

In order to solve the problems of appearance change, background distraction and occlusion in the object tracking, an efficient algorithm for visual tracking based on the local patch model and model update is proposed. This paper combines rough-search and precise-search to enhance the tracking precision. Firstly, it constructs the local patch model according to the initialized tracking area which includes some background areas. Secondly, the target is preliminarily located through the local exhaustive search algorithm based on the integral histogram, then the final position of the target is calculated through the local patches learning. Finally, the local patch model is updated with the retained sequence during the tracking process. This paper mainly studies the search strategy, background restraining and model update, and the experimental results show that the proposed method obtains a distinct improvement in coping with appearance change, background distraction and occlusion.

Visual tracking; Local patch model; Exhaustive search; Local patches learning; Model update

TP391.4

： A

：1009-5896(2015)06-1357-08

10.11999/JEIT141134

2014-09-01收到，2014-11-02改回

國家自然科學基金(61175029, 61473309)和陜西省自然科學基金(2011JM8015)資助課題

*通信作者：黃安奇 13319270512@163.com