基于KCF框架的長時間視頻目標跟蹤算法

梁 碩，陳金勇，吳金亮，王長力

(1.中國電子科技集團公司第五十四研究所，河北 石家莊050081；2.中國人民解放軍91635部隊，北京102249)

基于KCF框架的長時間視頻目標跟蹤算法

梁 碩1，陳金勇1，吳金亮1，王長力2

(1.中國電子科技集團公司第五十四研究所，河北 石家莊050081；2.中國人民解放軍91635部隊，北京102249)

針對視頻目標跟蹤中因遮擋產生的目標丟失后無法重新自動鎖定目標的問題，提出了一種能夠對視頻目標進行長時間跟蹤的算法。基于KCF(Kernelized Correlation Filters)算法的框架，增加篩選模塊，通過三重分類器的篩選，對目標重新自動鎖定。實驗結果表明，提出的算法能夠實現對目標的穩定跟蹤，并且在目標跟丟后自動重新鎖定并繼續跟蹤，實現對目標長時間跟蹤的目的。

KCF；遮擋；視頻目標跟蹤；長時間跟蹤

0 引言

隨著機器學習的不斷發展，越來越多的學者提出了視頻目標跟蹤算法，視頻目標跟蹤的性能得到了極大地改善。但是，由于視頻中噪聲、光照變化以及遮擋等問題的存在，當前的算法只能滿足于特定的約束條件，并不能夠在任何條件下都滿足實時性和魯棒性的要求。其中，尤其是遮擋問題的存在，對目標的跟蹤變得尤其困難。在現實世界中，遮擋是普遍存在的。目標可能被靜止的物體遮擋，也可能被運動的物體遮擋；可能被遮擋一部分，也可能被全部遮擋。無論哪種情況，目標都會因遮擋而改變其外觀，影響跟蹤的準確性。而當遮擋消失的時候，如何能夠繼續對正確的目標進行跟蹤，也是當前亟待解決的一個問題。

1 視頻目標跟蹤基本框架

視頻目標跟蹤是根據目標的表觀特征信息和目標運動模型，在視頻中估計目標的位置。因此，視頻目標跟蹤一般包含2個方面的內容：目標表觀特征描述和目標跟蹤算法。

視頻中目標具有細節豐富的表觀信息，需要通過相應的目標表觀特征描述方法將其中相對穩定的統計特性或某些不變特性提取出來，以此對目標和背景進行區分。原始圖像特征直接將目標區域的原始圖像信息或經簡單處理得到的底層圖像特征作為對目標的描述。通常選取的特征有灰度[2]、顏色[3]及梯度[4]等。該類特征提取簡單快速，但對目標特征的挖掘程度低，適應力較差。直方圖特征[5]，通過統計目標區域內某種特征在每個像素位置上出現的頻次，并進行歸一化，構成該目標區域對應特征的概率密度函數。直方圖有效描述了特征的統計特性，對于非剛體形變具有較好的魯棒性，但對于光照變化和背景雜波有一定欠缺。稀疏表示理論[6]，通過超完備字典將目標映射為稀疏向量，作為表觀描述特征，計算量小，但有一定的隨機性，不能保證最優。

為了估計目標的位置和范圍，需要選擇合適的跟蹤算法對目標進行跟蹤。文獻[7-9]提出貝葉斯估計理論，在所構建的狀態空間模型基礎上，依據目標的先驗運動模型和后驗觀測，通過預測和更新2個步驟實現先驗與后驗信息的有效融合，進而得到目標的估計狀態。文獻[10-12]提出均值漂移理論，通過分別構建權重與核函數對樣本點的特征和空間位置賦予不同的重要性，進而計算偏移均值向量，并移動到該點重新依據樣本點的重要性計算新的偏移均值向量，由此迭代對目標位置進行估計。文獻[13-15]采用基于機器學習的方法將目標和背景都作為樣本進行訓練，通過分類器對目標和背景進行區分，由此獲得目標的位置。

2 KCF跟蹤算法

KCF跟蹤算法通過對嶺回歸分類器的學習來完成對目標的跟蹤，具體流程如圖1所示。

圖1 KCF算法流程

在訓練階段，利用循環矩陣理論，對視頻目標區域進行稠密采樣，獲取正負樣本，提取方向梯度直方圖[16](Histogram of Oriented Gradients，HOG)特征，將所有樣本對嶺回歸分類器進行訓練。在檢測階段，以視頻前一幀目標位置為中心進行稠密采樣，將得到的所有樣本輸入到嶺回歸分類器，經過嶺回歸分類器的分類，得到目標的位置。

2.1 稠密采樣

KCF跟蹤算法為了保證跟蹤的準確度，引入循環矩陣理論知識，對視頻目標區域采取稠密采樣的策略，訓練的樣本是利用基樣本的循環移動進行稠密采樣。稠密采樣的示意圖如圖2所示，其中，實線矩形框所包含的圖像塊為基樣本，以x=(x1,x2…xn)表示，虛線矩形框表示在水平方向上，分別向左右2個方向移動采樣的結果，移動后分別為x=(x2…xn,x1)和x=(xn,x1…xn-1)。如此在水平方向和垂直方向進行循環，則可以以基樣本為中心，對其周圍的所有可能圖像塊進行采樣，由此得到完備的樣本空間。

2.2 嶺回歸分類器

對線性嶺回歸分類器進行訓練的目標就是找到一個函數f(x)=wTx，使得損失函數最小，即：

(1)

式中，x=(x1,x2…xn)表示樣本，λ為正則項，防止過擬合，w為所求的參數。由式(1)求得一個封閉解的模式：

w=(XTX+λI)-1XTy，

(2)

式中，矩陣X為基樣本組合的循環矩陣，y為每個樣本的標簽值的集合。針對那些不能在原始空間進行分類的樣本，則需要引入核函數理論，將低維空間中線性不可分的模式通過核函數映射到高維空間實現線性可分，核函數的格式如下：

k(x,z)=φ(x)φ(z)，

(3)

式中，k(x,z)為核函數，φ(x)和φ(z)為低維空間到高維空間的映射函數。當使用核函數將樣本x映射為φ(x)時，所求的分類器f(x)=wTx中的系數w轉化為對偶空間中的a。由RepresenterTheorem知，系數w是樣本x的線性組合，即：

(4)

(5)

由式(1)和式(5)聯合求得：

a=(K+λI)-1y，

(6)

式中，K為映射之后的核矩陣，Ki,j=k(xi,xj)。在檢測階段，輸入的視頻經過嶺回歸分類器的分類來確定最終的目標位置信息，將得到的目標位置信息繼續訓練嶺回歸分類器，如此反復，完成對目標的跟蹤。

3 對KCF算法的改進

KCF跟蹤算法因其在準確度和速度方面的綜合優勢，在視頻目標跟蹤中獲得了優異的表現。盡管如此，其仍不能夠有效地抵抗遮擋，在對目標跟丟之后，也無法重新找回目標進行跟蹤。針對這2個問題，對KCF算法進行了改進，增加了篩選模塊，將篩選模塊和跟蹤得到的目標位置信息進行融合處理，最終得到準確的目標位置信息，提高準確度。具體的流程如圖3所示。

圖3 改進后算法流程圖

3.1 篩選模塊設計

篩選模塊設計3個分類器，輸入視頻幀的樣本只有通過這3次分類器的篩選才有可能成為目標區域，具體流程如圖4所示。

圖4 檢測模塊流程圖

3.1.1 方差篩選

在該階段,要檢測的圖像塊中如果所有像素點的灰度值方差總體小于被跟蹤的目標區域中所有像素點整體方差的50%，這個圖像塊就被方差分類器丟棄掉。圖像塊p中的所有像素點的灰度值方差可以用式E(p2)-E2(p)來表示，其中利用積分圖來獲得E(p)。經過方差篩選之后，大約能過濾掉一半與目標無關的圖像塊。

3.1.2 級聯決策樹篩選

在該階段，由多個串聯的決策樹對圖像塊進行篩選。每個決策樹i會對輸入的圖像塊中特定位置的像素點進行灰度值檢測，將輸入圖像塊的像素點與已知灰度值進行對比，把對比的差值結果來生成一個二進制的編碼x，如圖5所示。決策樹中某個葉子節點的后驗概率Pi(y|x)用編碼x代表，其中y∈(0,1)。由于決策樹是相互獨立的，因此要計算出各個決策樹的后驗概率的平均值，如果計算出的后驗概率的均值大于50%，則該圖像塊通過篩選。

每個決策樹是基于初始化時確定的一組像素點對的比較。是在離線的情況下，隨機生成像素點對，并且在運行過程中，保持像素點對的穩定性。首先,用高斯卷積對要跟蹤的圖像進行模糊，從而使圖像的魯棒性有所加強，進而還能對圖像噪聲有所降低。接著按照預先生成的像素點對，在圖像塊中比較像素點對的差值，每個像素對比較的差值返回0或1,這些返回值順序地連接到一起，就完成了對x的編碼。

圖5 圖像塊到二進制的轉換

該階段至關重要的條件是各個決策樹是相互獨立的。所以我們采取以下的措施：首先把圖像塊進行歸一化然后把像素點的位置進行離散化處理，進而在圖像塊中生成所有可能的垂直和水平方向的像素點對的比較值。這些像素對的比較值，就是圖像塊的特征值。接下來,把像素對的比較值合并，并將合并后的像素對比較值分發到決策樹中。因此,每一個決策樹都可以保證是基于一組不同的特性值組合，并且所有的這些特征值結合在一起唯一地表示一個樣本。

每一個決策樹i維持著一個后驗概率y∈(0,1)，總共有2d個后驗概率。其中d是像素對比較的個數，通常像素對d取值為13個，因此對于二進制編碼x就有可能8 192的編碼方式，而對于所有的二進制編碼x都用其各自的后驗概率所代表。

3.1.3 最近鄰篩選

在該階段,將通過方差篩選和級聯決策樹篩選的圖像塊與已有的目標模板進行相似度檢測。如果一個圖像塊與已有模板的相關相似度大于給定的閾值，即Sr(p,M)>θNN。就把這樣的圖像塊分類為目標樣本，認為其含有目標。

3.2 融合目標信息

該部分將篩選得到的結果與跟蹤算法得到結果進行融合，共同輸出目標位置信息。其中，存在以下幾種情況：

① 當跟蹤算法與篩選算法都能得到目標的位置信息(篩選算法可能得到多個目標位置信息)，并且位置信息比較接近(目標矩形框的重疊率較大)時，則將跟蹤算法得到的目標位置信息與篩選算法得到的目標位置信息按10：1的權重進行加權平均，得到一個新的目標位置信息。

② 當跟蹤算法與篩選算法得到的目標位置信息相差較大，并且篩選算法得到的結果更加準確時，則由篩選算法的結果為準重新初始化目標信息。

③ 當篩選算法無法得到目標信息時，以跟蹤算法的結果為目標最終位置信息。

4 實驗結果展示

為了驗證算法的有效性，本文算法與KCF算法進行了對比。算法運行環境為Intel Core i7-3770、CPU 3.40 GHz、RAM 3.47 GB的PC機，視頻圖像尺寸為480*640。對比結果如圖6所示，其中顏色較深的矩形框表示改進后的算法結果，顏色較亮的矩形框表示KCF跟蹤算法的結果。

(a) 第7幀

(b) 第70幀

(c) 第81幀

(d) 第85幀

由對比結果展示可以看出，本文算法較之KCF算法更加魯棒。在沒有干擾的情況下，本文算法和KCF算法都能夠對目標進行準確跟蹤(視頻第7幀和第70幀)，但當存在遮擋干擾時，KCF算法則無法抵抗遮擋，會出現跟丟目標的現象并且不會重新鎖定目標，本文算法能夠自動重新鎖定目標繼續跟蹤(第81幀和第85幀)。

5 結束語

在KCF算法的基礎之上，提出了一種魯棒的能夠對視頻目標進行長時間跟蹤的算法。在對視頻目標進行跟蹤時，篩選算法與KCF跟蹤算法共同輸出目標的位置信息。經過實驗證明，提出的算法能夠有效地抵抗物體遮擋的干擾，尤其是在出現跟丟目標的情況下，能夠重新初始化目標的準確位置，提高了跟蹤的魯棒性。

[1] Henriques J F,Caseiro R,Martins P,et al.High-Speed Tracking with Kernelized Correlation Filters[J].IEEE Transactiongs on Pattern Analysis And Machine Intelligence,2015,37(3)：583-596.

[2] Hare S,Saffari A,Torr P H S.Struck：Structured Output Tracking with Kernels[C]∥Computer Vision,IEEE International Conference on.IEEE,2011：263-270.

[3] Kwon J,Lee K M.Tracking by Sampling Trackers[C]∥Computer Vision,IEEE International Conference on.IEEE,2011：1195-1202.

[4] Oron S,Bar-Hillel A,Levi D,et al.Locally Orderless Tracking[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2012：1940-1947.

[5] Godec M,Roth P M,Bischof H.Hough-based Tracking of Non-rigid Objects[J].Computer Vision and Image Understanding,2013,117(10)：1245-1256.

[7] 張洪建.基于有限集統計學的多目標跟蹤算法研究[D].上海：上海交通大學，2009.

[8] 宋驪平.被動多傳感器目標跟蹤方法研究[D].西安：西安電子科技大學,2008.

[9] 楊柏勝.被動多傳感器探測目標跟蹤技術研究[D].西安：西安電子科技大學,2008.

[10] Ning J,Zhang L,Zhang D,et al.Scale and Orientation Adaptive Mean Shift Tracking[J].IET Computer Vision,2012,6(1)：52-61.

[11] Beyan C,Temizel A.Adaptive Mean-shift for Automated Multi Object Tracking[J].IET Computer Vision,2012,6(1)：1-12.

[12] Mazinan A H,Amir-Latifi A.Improvement of Mean Shift Tracking Performance Using a Convex Kernel Function and Extracting Motion Information[J].Computers & Electrical Engineering,2012,38(6)：1595-1615.

[13] Grabner H,Grabner M,Bischof H.Real-Time Tracking via On-line Boosting[C]∥The British Machine Vision Conference,2006：47-56.

[14] Ross D,Lim J,Lin R S,et al.Incremental Learning for Robust Visual Tracking[J].International Journal of Computer Vision,2008,77(1)：125-141.

[15] Babenko B,Yang M H,Belongie S.Visual Tracking with Online Multiple Instance Learning[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2009：983-990.

[16] Dalal N,Triggs B.Histograms of Oriented Gradients for Human Detection[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2005：886-893.

Long-time Video Object Tracking Algorithm Based on KCF Framework

LIANG Shuo1,CHEN Jin-yong1,WU Jin-liang1,WANG Chang-li2

(1.The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China；2.Unit 91635,PLA,Beijing 102249,China)

To solve the problem of being unable to rediscover the object automatically after the loss of the object because of occlusion,an algorithm which can track the object with a long time is proposed.Based on the KCF algorithmic framework,this algorithm adds filtrating modules and can rediscover the object automatically by the three-time filtration of the classifier.Experiment results show that the proposed algorithm could track the object stably,rediscover the object automatically after the loss of the object,and keep tracking the object,which realizes the purpose of long-time tracking the object.

KCF;occlusion;video object tracking;long-time tracking

10.3969/j.issn.1003-3114.2017.02.14

梁 碩，陳金勇，吳金亮，等.基于KCF框架的長時間視頻目標跟蹤算法[J].無線電通信技術，2017，43(2)：55-58,82.

2016-11-08

海洋公益性科研專項資助項目(201505002)

梁 碩(1991— )，男，碩士研究生，主要研究方向：視頻圖像處理。陳金勇(1970—) ，男，研究員，博士生導師，主要研究方向：航天地面應用、電子信息系統。

TP391.4

A

1003-3114(2017)02-55-4