鄭運平 李睿君

(華南理工大學 計算機科學與工程學院，廣東 廣州 510006)

自從目標跟蹤的需求出現(xiàn)以來，尤其是近十年來，目標跟蹤算法層出不窮，不同跟蹤算法建立的模型、選取的特征也不相同。目標跟蹤算法根據(jù)模型可大體分為兩類：生成式[1- 5]和判別式[6- 19]。其中生成式先構造一個模型描述目標的外觀信息、結構特征，往往是像素值、梯度等直觀信息，再去候選區(qū)域中尋找與模型最匹配的區(qū)域。判別式的思路是訓練一個分類器，不僅在目標區(qū)域內(nèi)采取正樣本，同時在目標周圍的背景區(qū)域采取負樣本，利用到前景和背景的差異信息，用該分類器去評估候選區(qū)域與目標區(qū)域的接近程度。

比較經(jīng)典的生成式模型有：高斯混合模型(Gaussians Mixture Model，GMM)、貝葉斯模型(Bayesian Network Model，BNM)、馬爾可夫隨機場模型(Markov Random Field，MFR)[1]。早在1999年，Marques等[2]就結合高斯混合模型和隱馬爾科夫模型提出了一種跟蹤具有復雜形狀的目標的算法。2016年，Miao等[3]為目標確定基于SURF(Speeded Up Robust Features)的關鍵點，為每個關鍵點構建動態(tài)的縮放-旋轉(zhuǎn)空間，以加強其變化和獨特性，并用高斯混合模型為每個關鍵點分配一個內(nèi)核權重，以確保使用更加可靠的關鍵點，提高了跟蹤算法在復雜場景變化下的魯棒性。2018年，Zhu等[4]基于Vibe和高斯混合模型，使用視頻序列訓練“虛擬”背景模型而不是用第一幀圖像建模，然后基于像素分類提取前景像素，比主流的背景減法更能適應復雜場景，且速度更快；同年，Ahmad等[5]提出一種概率推理方法，根據(jù)實際應用情況和貝葉斯網(wǎng)絡預測目標的意圖預測它的目的地和軌跡，充分利用了軌跡中潛在的長期依賴性，在實際應用中很有價值。

比較著名的判別式算法有：Struck、TLD(Tracking-Learning-Detection)、CT(Compressive Tracking)和基于CF改進的KCF(Kernelized Correlation Filter)[6- 19]。2011年，Hare等[6- 7]提出的Struck算法風靡一時，與當時其他算法相比不僅跟蹤效果好，還能達到實時要求；該算法提出一種基于結構輸出預測的自適應視覺目標跟蹤框架，通過明確引入輸出空間滿足跟蹤功能，能夠避免中間分類環(huán)節(jié)，直接輸出跟蹤結果； 同時，為了保證實時性，該算法還引入了閾值機制，防止跟蹤過程中支持向量的過增長。TLD算法[8- 9]是一種主要針對單目標長時間的跟蹤算法，分為檢測、追蹤、學習3個模塊； 該算法與傳統(tǒng)跟蹤算法的顯著區(qū)別在于將跟蹤算法和檢測算法相結合，來應對目標發(fā)生較大形變或長時間遮擋等情況；后來也有許多研究者對其進行改進，或者應用它的思想優(yōu)化其他跟蹤算法[10- 12]。CT算法[13]利用了壓縮感知的理論，先獲取圖像的高維特征，再用稀疏隨機測量矩陣對特征進行降維，從而大幅減少運算量，這令CT算法以跟蹤速度快而聞名。2011年，Babenko等[14]引入MIL(Multipe Instance Learning)方法取代傳統(tǒng)的有監(jiān)督學習，以便產(chǎn)生魯棒性更強且參數(shù)設定更少的追蹤器。KCF[15- 18]是基于相關濾波的代表性算法之一，借助循環(huán)矩陣和傅里葉變換，將矩陣運算轉(zhuǎn)換為向量的點積，實現(xiàn)極高的跟蹤速度，同時保有不錯的跟蹤準確性；與之相似的還有DCF(Discriminative Correlation Filter)[19]，兩者都是基于CSK改進的，只是核函數(shù)不同——KCF采用高斯核函數(shù)，而DCF采用線性核函數(shù)。

就當前比較先進的算法而言，生成式算法的表現(xiàn)整體不如判別式算法，但是目標跟蹤的場景多種多樣，不同場景的目標運動特征不同，由于生成式算法比判別式算法帶有更豐富的圖像信息，對于快速移動、環(huán)境復雜的情景往往更具優(yōu)勢。此外，部分判別式算法用到了深度學習來訓練分類器，這要求較大的訓練數(shù)據(jù)量，而大部分時候目標跟蹤問題只會在視頻的第一幀給出目標區(qū)域，這個數(shù)據(jù)量是不夠的。因此，具體到某些實際應用問題，生成式算法也有自己的優(yōu)勢。

生成式算法表現(xiàn)欠佳，主要的一個原因是跟蹤速度慢，因為生成式模型需要的計算量較大。針對這個問題，有一類模型可以進行優(yōu)化，即分塊模型。由于圖像的冗余性，可以用分塊整體代替多個像素來描述局部特征，同時減少運算量，各塊的特征則共同描述了該目標的內(nèi)部特征。值得注意的是這類模型與很多經(jīng)典的生成式模型并不沖突，比如高斯混合模型是對每個像素建模，這種方法將點組合成塊，以塊為單位對整個子空間進行操作，顯然能大幅減少運算時間。對于這種模型，分塊數(shù)目與目標跟蹤速度直接相關，分塊越多，跟蹤速度越慢。

2015年張文俊等[20]提出了一種基于四叉樹分塊的模型，基本思路是將圖像等分為4部分，對每一個子塊進行判斷，若該子塊各像素的灰度值相似程度達到某個閾值，則計算該子塊的特征，反之將該子塊進一步等分為4部分，重復上述過程。他們在實驗中將同一分塊的像素近似為高斯分布，并用兩個分布之間的KL距離來衡量兩個相同規(guī)模分塊的相似程度。其實驗結果表明，該模型應用于目標跟蹤，在準確率上普遍優(yōu)于CT算法、MIL算法，但是在耗時上還是處于劣勢。

有效的圖像表示方法不僅能節(jié)省圖像的存儲空間，而且還能提高圖像處理的速度[21- 23]?？紤]到耗時與分塊數(shù)直接相關，上述跟蹤算法的效率很大程度上受限于四叉樹模型產(chǎn)生的分塊數(shù)，本研究將采用分塊數(shù)大幅減少的二叉樹模型作為目標特征的描述模型；同時，在分塊時采用自己關于同類塊的定義，從而使得后面計算每個分塊的特征時能用分塊均值來近似表示，避免計算高斯分布參數(shù)時繁雜的平方計算；另外，在跟蹤時依據(jù)下一幀選取的目標區(qū)域與當前幀的目標區(qū)域之間的差值來判斷是否需要重新劃分，更好地適應目標發(fā)生變化的情況。

1 圖像的二叉樹分塊模型

1.1 二叉樹分塊方法

基本的二叉樹分塊方法主要步驟有：

步驟1將當前圖像記為當前塊，壓入容器中。

步驟2從頭開始遍歷容器，對遍歷到的當前塊作判斷，直至容器結尾——若當前塊符合終止劃分條件則不做處理，繼續(xù)遍歷容器中的下一個塊； 反之，對當前塊進行二等分，將分割得到的兩個子塊壓入該容器中，并將其父塊(即當前塊)從容器中去除。

在以上步驟中，需要考慮兩個問題：一是判定是否終止劃分的標準； 二是需要采用何種數(shù)據(jù)結構和哪些特征信息來描述每個分塊和整幅圖像。

1.2 同類塊判定標準

本研究采用判斷當前塊是否符合同類塊的定義來作為終止劃分的標準[24]。同類塊的定義見定義1。

定義1給定一個誤差容許量ε，若一個矩形塊B內(nèi)所有像素值g(x，y)均滿足|g(x，y)-gest(x，y)|≤ε，則稱該矩形塊為同類塊(如圖1所示)，其中，x1≤x≤x2、y1≤y≤y2，gest(x，y)是B中坐標(x，y)處的近似灰度值，其計算公式為

gest(x，y)=g5+(g6-g5)×i1

(1)

其中，g1、g2、g3和g4是該塊4個角落的灰度值，g5=g1+(g2-g1)×i2，g6=g3+(g4-g3)×i2，i1=(y-y1)/(y2-y1)，i2=(x-x1)/(x2-x1)，x1

若當前塊是一個同類塊，則終止劃分；否則繼續(xù)劃分。

圖1 同類塊B的示意圖

1.3 特征記錄

對于每個同類塊，需要記錄的信息包括位置信息和特征信息。

對于位置信息，直接記錄同類塊的左上角頂點位置和長寬信息。

對于特征信息，參考了張文俊等[20]的實驗。文獻[20]中指出，四叉樹分塊的結果會使每個分塊的像素分布呈高斯分布，因此他們記錄了每個分塊的均值和方差。對于二叉樹分塊來說這也同樣適用，但是筆者在實驗中發(fā)現(xiàn)了兩個問題：一是計算方差的效率非常低，很難達到實時跟蹤的效果； 二是在尋找接近目標區(qū)域的候選框時，同一分塊內(nèi)的像素并不適合用高斯分布來近似，這是因為對候選區(qū)域采用的劃分方法需要與目標區(qū)域的劃分方法保持一致，但這不能保證候選區(qū)域分割得到的分塊同樣滿足同類塊定義，即同一分塊的像素并不滿足高斯分布，此時繼續(xù)用高斯分布來近似和計算候選區(qū)域與目標區(qū)域之間的KL距離，意義不大，尤其是分塊較小時，由于像素個數(shù)太少，比較容易出現(xiàn)方差為0的情況，此時KL距離會趨于無窮大，不易處理。因此本研究采用了更簡化的評估方式，僅記錄每個分塊的大小和均值。首先它在運算時間上是能達到實時跟蹤的； 其次，實驗表明這種特征描述方式是有效的。

為了適應在跟蹤過程中目標區(qū)域發(fā)生大小變化，本研究記錄同類塊位置信息和大小時均采用其相對于目標區(qū)域的百分比來記錄。

綜上，本研究采用的特征描述向量為

(average，percent，x，y，width，height)，

即：(灰度均值，面積權重，左上角頂點橫坐標，左上角頂點縱坐標，寬度，高度)。

后面5個值均是[0，1]之間的百分數(shù)。

本研究采用的二叉樹分塊算法如下。

/*給定一幅M×N的灰度圖像和誤差(閾值)ε，指定目標區(qū)域B，輸出一個描述B特征的同類塊特征模型(特征表)F*/

步驟1初始化一個元素類型為矩形的隊列V，將目標區(qū)域B對應的矩形壓入V中。

步驟2判斷V是否為空，若V為空，算法結束； 否則轉(zhuǎn)入步驟3。

步驟3取出隊列V頭部的矩形，根據(jù)式(1)判斷其是否為同類塊。如果它是同類塊，計算它的特征描述向量，將特征向量壓入特征表F中；若它不是同類塊，將其二等分，將得到的兩個矩形依次壓入隊列V尾部。

步驟4返回步驟2。

1.4 二叉樹與四叉樹的比較

每1次四叉樹劃分，都可以把它分解為3次二叉樹劃分的疊加。對于1個父塊，先二分為2個中間塊，每個中間塊再分別進行1次二分，最終得到4個子塊，該結果與1次四叉樹劃分是完全相同的。因此如果一個二叉樹未提前終止，持續(xù)劃分下去，最終必定會達到與四叉樹劃分相同的結果(相同閾值下)。在劃分過程中，分塊數(shù)顯然是遞增的，因此二叉樹的分塊數(shù)目不可能超過四叉樹分塊數(shù)目。而由于二叉樹會對中間塊進行判斷，如果中間塊達到同類塊的要求，則終止劃分，此時二叉樹的分塊數(shù)目就會比四叉樹少。在本研究后續(xù)的實驗中統(tǒng)計了相同閾值下二叉樹和四叉樹的分塊結果，證明了二叉樹分塊數(shù)明顯少于四叉樹分塊數(shù)。

2 二叉樹模型在目標跟蹤中的應用

假定所要跟蹤的目標在第一幀中人為給出，通過第1節(jié)的算法可得到由目標區(qū)域分塊而來的特征表F，此后，在每一幀中，尋找最接近目標特征的區(qū)域。假設有m個矩形候選區(qū)域，對每一個候選區(qū)域進行分塊，分塊方式與目標區(qū)域的分塊方式相同，按F的分塊順序計算候選區(qū)域每個分塊的特征，可得到與F相同大小的候選框特征表Fi，假設分塊塊數(shù)為n，第i(1≤x≤m)個候選區(qū)域與目標區(qū)域之間的特征差值計算方法如下：

di=∑(disi，j×F(j)percent)

(2)

disi，j=Fi(j)average-F(j)average

(3)

其中：disi，j表示第i個候選區(qū)域第j個分塊與目標區(qū)域第j個分塊之間的差距，文中用像素均值的差值來表示；F(j)average表示F(j)的均值分量(F(j)表示目標區(qū)域第j個分塊對應的特征，即特征表F的第j個元素)；F(j)percent和F(j)average依此類推。

考慮目標跟蹤的特性，本研究總是從當前目標區(qū)域附近選取候選框，比較各候選框的特征，從中選取最接近目標特征的一個作為結果。選定結果后，需根據(jù)該結果更新目標區(qū)域的特征表。更新特征表有兩種情況，如果下一幀選取的目標區(qū)域與當前幀的目標區(qū)域差別過大，超出設定的閾值，則認為目標區(qū)域很可能發(fā)生較大改變，將重新進行二叉樹劃分； 反之，如果兩者差別不大，未超過閾值，將參考在原來的劃分基礎上對特征表的均值進行更新。具體算法如下。

/*給定一系列連續(xù)幀，給出初始目標區(qū)域B的位置，在每幀中找出目標區(qū)域并框選出來*/

步驟1應用第1節(jié)的二叉樹分塊算法對目標區(qū)域B進行劃分，得到描述目標信息的特征表F。

步驟2設定候選框搜索半徑r，以當前目標區(qū)域位置為中心、r為半徑、3為步長在下一幀搜索候選區(qū)域，并計算每個候選區(qū)域的特征表； 按式(2)和式(3)計算每一個候選框與當前目標區(qū)域B間的特征差值di，將di最小的候選框記為temptRect。

步驟3以temptRect為中心、1為半徑、1為步長在下一幀搜索候選區(qū)域，并計算每個候選區(qū)域的特征表； 按式(2)和式(3)計算每一個候選框與當前目標區(qū)域B間的特征差值di，將temptRect重新賦值為di最小的候選框。

步驟4判斷temptRect與當前幀目標區(qū)域的特征差值di是否大于閾值threshold，如果是，則進入步驟5； 否則進入步驟7。

步驟5設定放大及縮小參數(shù)increase和decrease，以temptRect為中心，分別放大increase、increase×increase倍和縮小至decrease、decrease×decrease得到矩形候選區(qū)域，并計算每個候選區(qū)域的特征表。計算每一個候選框與當前目標區(qū)域間的特征差值di，將temptRect重新賦值為di最小的候選框。

步驟6將temptRect作為下一幀的目標區(qū)域，判斷temptRect與當前幀目標區(qū)域的特征差值di是否大于閾值threshold，如果是，重新對temptRect進行二叉樹劃分得到新的特征表F，否則不需要進行二叉樹劃分，直接通過下式更新特征表F：

F(j)average=temptRect(j)average×λ+

F(j)average×(1-λ)

(4)

其中：F(j)average、tempRect(j)average分別表示F(j) 的均值分量、temptRect第j個分塊的均值分量；λ為變化速度參數(shù)，計算方法為

λ=rate/(1+di)

(5)

其中rate是設定的更新參數(shù)。

步驟7如果沒有后續(xù)幀，則算法終止，否則返回步驟2。

3 實驗結果與分析

文中從準確性和跟蹤速度兩個方面對CT算法、基于四叉樹模型的算法(簡稱QT算法)和本研究提出的基于二叉樹模型的算法(簡稱BT算法)進行了比較。CT算法代碼來自張開華等[13]提供的開源代碼：http：∥www4.comp.polyu.edu.hk/～cslzhang/CT/CT.htm。QT算法參考了張文俊等[20]的論文。

實驗中的測試圖像全部來自OTB100[25- 26]。實驗操作系統(tǒng)為64位的Windows10系統(tǒng)，處理器為Intel(R)Core(TM)i5-8500，處理器頻率為3GHz，運行內(nèi)存RAM為8GB。

對于QT算法和BT算法，參數(shù)設定如下：

同類塊判定閾值ε=20；

候選框搜索半徑r=25；

特征差值閾值threshold=30；

候選框大小的增幅increase=1.1；

候選框大小的縮幅decrease=0.9；

更新速率rate=0.5；

實驗結果如圖2、圖3及表1所示。圖2中藍色矩形框、紅色矩形框、黃色矩形框分別代表CT算法、QT算法和BT算法的結果，綠色矩形框代表正確的目標區(qū)域。

(a)Coupon跟蹤結果

(b)Dancer 2跟蹤結果

(c)Dog 1跟蹤結果

(d)FaceOcc 2跟蹤結果

(e)Jumping跟蹤結果

(f)Mhyang跟蹤結果

(g)Vase跟蹤結果

就BT算法與QT算法而言，由圖2的直接觀察和圖3的量化統(tǒng)計可知，BT算法的跟蹤準確性與QT算法大致相當。但由表1可以算出，與QT算法相比，BT算法的跟蹤速度大幅提高，提高了27.18%((131-103)/103×100%)。主要原因是分塊數(shù)目明顯減少，同類塊平均分塊數(shù)減少了33.19%((919-614)/919×100%)，由此可見BT算法比起QT算法在跟蹤速度上有很大優(yōu)勢。

就BT算法與CT算法而言，圖3表明，在跟蹤準確性方面，無論是以跟蹤區(qū)域與目標區(qū)域間的中心誤差，還是以跟蹤區(qū)域與目標區(qū)域間的重疊率作為評價標準，BT算法都要遠遠優(yōu)于CT算法。從圖2可以看出，BT算法的跟蹤效果要明顯優(yōu)于CT算法。而在跟蹤速度方面，表1所示結果表明BT算法的平均水平也高于CT算法。單獨分析基于二叉樹模型的跟蹤算法不難看出，其跟蹤速度與分塊數(shù)直接相關。

綜上所述，與基于QT的跟蹤算法相比，基于BT的跟蹤算法在準確性方面幾乎不受影響的前提下，跟蹤速度顯著提升； 與基于判別式的CT算法相比，在跟蹤速度大致相當?shù)那疤嵯?，基于BT的跟蹤算法跟蹤準確性卻更好。因此，文中提出的基于BT的跟蹤算法是一種更有效的目標跟蹤方法。

圖3 3種算法跟蹤準確率的比較

表13種算法平均分塊數(shù)和跟蹤速度比較

Table1Comparison of average number of blocks and tracking speed of the three algorithms

實驗序列CT算法QT算法BT算法平均分塊數(shù)/(塊·幀-1)跟蹤速度/fps平均分塊數(shù)/(塊·幀-1)跟蹤速度/fps平均分塊數(shù)/(塊·幀-1)跟蹤速度/fpsCoupon118155349100666Dancer211410366367284Dog1122412142262199FaceOcc212212145966898Jumping117136217121232Mhyang123457144305184Vase123162347126457平均值120919103614131

4 結語

通過用二叉樹分塊模型描述目標區(qū)域的特征，文中提出了一種基于二叉樹模型的目標跟蹤算法。本算法與著名的壓縮跟蹤算法以及基于四叉樹模型的跟蹤算法進行比較，理論分析和實驗結果證明了本算法在速度和準確性上的優(yōu)越性。事實上，文中提出的算法還可以進一步優(yōu)化，比如在候選框的選取、二叉樹分塊終止條件等方面進行改進，可以減少候選框的個數(shù)或目標區(qū)域的分塊數(shù)，從而提高跟蹤速度； 或者是修改同類塊特征的選取。文中主要是從分塊的角度論述二叉樹模型在目標跟蹤中的應用價值，在描述分塊特征時完全可以結合其他特征表示模型來進行改進，比如梯度直方圖、高斯混合模型等； 還可以將同類塊閾值設置為可動態(tài)自適應的，從而適應不同類型視頻的要求、穩(wěn)定跟蹤速度等等。因此這一模型還有很大的潛力和改進空間。