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

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

基于KCF框架的長時(shí)間視頻目標(biāo)跟蹤算法

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

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

針對視頻目標(biāo)跟蹤中因遮擋產(chǎn)生的目標(biāo)丟失后無法重新自動(dòng)鎖定目標(biāo)的問題，提出了一種能夠?qū)σ曨l目標(biāo)進(jìn)行長時(shí)間跟蹤的算法?；贙CF(Kernelized Correlation Filters)算法的框架，增加篩選模塊，通過三重分類器的篩選，對目標(biāo)重新自動(dòng)鎖定。實(shí)驗(yàn)結(jié)果表明，提出的算法能夠?qū)崿F(xiàn)對目標(biāo)的穩(wěn)定跟蹤，并且在目標(biāo)跟丟后自動(dòng)重新鎖定并繼續(xù)跟蹤，實(shí)現(xiàn)對目標(biāo)長時(shí)間跟蹤的目的。

KCF；遮擋；視頻目標(biāo)跟蹤；長時(shí)間跟蹤

0 引言

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

1 視頻目標(biāo)跟蹤基本框架

視頻目標(biāo)跟蹤是根據(jù)目標(biāo)的表觀特征信息和目標(biāo)運(yùn)動(dòng)模型，在視頻中估計(jì)目標(biāo)的位置。因此，視頻目標(biāo)跟蹤一般包含2個(gè)方面的內(nèi)容：目標(biāo)表觀特征描述和目標(biāo)跟蹤算法。

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

為了估計(jì)目標(biāo)的位置和范圍，需要選擇合適的跟蹤算法對目標(biāo)進(jìn)行跟蹤。文獻(xiàn)[7-9]提出貝葉斯估計(jì)理論，在所構(gòu)建的狀態(tài)空間模型基礎(chǔ)上，依據(jù)目標(biāo)的先驗(yàn)運(yùn)動(dòng)模型和后驗(yàn)觀測，通過預(yù)測和更新2個(gè)步驟實(shí)現(xiàn)先驗(yàn)與后驗(yàn)信息的有效融合，進(jìn)而得到目標(biāo)的估計(jì)狀態(tài)。文獻(xiàn)[10-12]提出均值漂移理論，通過分別構(gòu)建權(quán)重與核函數(shù)對樣本點(diǎn)的特征和空間位置賦予不同的重要性，進(jìn)而計(jì)算偏移均值向量，并移動(dòng)到該點(diǎn)重新依據(jù)樣本點(diǎn)的重要性計(jì)算新的偏移均值向量，由此迭代對目標(biāo)位置進(jìn)行估計(jì)。文獻(xiàn)[13-15]采用基于機(jī)器學(xué)習(xí)的方法將目標(biāo)和背景都作為樣本進(jìn)行訓(xùn)練，通過分類器對目標(biāo)和背景進(jìn)行區(qū)分，由此獲得目標(biāo)的位置。

2 KCF跟蹤算法

KCF跟蹤算法通過對嶺回歸分類器的學(xué)習(xí)來完成對目標(biāo)的跟蹤，具體流程如圖1所示。

圖1 KCF算法流程

在訓(xùn)練階段，利用循環(huán)矩陣?yán)碚摚瑢σ曨l目標(biāo)區(qū)域進(jìn)行稠密采樣，獲取正負(fù)樣本，提取方向梯度直方圖[16](Histogram of Oriented Gradients，HOG)特征，將所有樣本對嶺回歸分類器進(jìn)行訓(xùn)練。在檢測階段，以視頻前一幀目標(biāo)位置為中心進(jìn)行稠密采樣，將得到的所有樣本輸入到嶺回歸分類器，經(jīng)過嶺回歸分類器的分類，得到目標(biāo)的位置。

2.1 稠密采樣

KCF跟蹤算法為了保證跟蹤的準(zhǔn)確度，引入循環(huán)矩陣?yán)碚撝R(shí)，對視頻目標(biāo)區(qū)域采取稠密采樣的策略，訓(xùn)練的樣本是利用基樣本的循環(huán)移動(dòng)進(jìn)行稠密采樣。稠密采樣的示意圖如圖2所示，其中，實(shí)線矩形框所包含的圖像塊為基樣本，以x=(x1,x2…xn)表示，虛線矩形框表示在水平方向上，分別向左右2個(gè)方向移動(dòng)采樣的結(jié)果，移動(dòng)后分別為x=(x2…xn,x1)和x=(xn,x1…xn-1)。如此在水平方向和垂直方向進(jìn)行循環(huán)，則可以以基樣本為中心，對其周圍的所有可能圖像塊進(jìn)行采樣，由此得到完備的樣本空間。

2.2 嶺回歸分類器

對線性嶺回歸分類器進(jìn)行訓(xùn)練的目標(biāo)就是找到一個(gè)函數(shù)f(x)=wTx，使得損失函數(shù)最小，即：

(1)

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

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

(2)

式中，矩陣X為基樣本組合的循環(huán)矩陣，y為每個(gè)樣本的標(biāo)簽值的集合。針對那些不能在原始空間進(jìn)行分類的樣本，則需要引入核函數(shù)理論，將低維空間中線性不可分的模式通過核函數(shù)映射到高維空間實(shí)現(xiàn)線性可分，核函數(shù)的格式如下：

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

(3)

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

(4)

(5)

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

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

(6)

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

3 對KCF算法的改進(jìn)

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

圖3 改進(jìn)后算法流程圖

3.1 篩選模塊設(shè)計(jì)

篩選模塊設(shè)計(jì)3個(gè)分類器，輸入視頻幀的樣本只有通過這3次分類器的篩選才有可能成為目標(biāo)區(qū)域，具體流程如圖4所示。

圖4 檢測模塊流程圖

3.1.1 方差篩選

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

3.1.2 級(jí)聯(lián)決策樹篩選

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

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

圖5 圖像塊到二進(jìn)制的轉(zhuǎn)換

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

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

3.1.3 最近鄰篩選

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

3.2 融合目標(biāo)信息

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

① 當(dāng)跟蹤算法與篩選算法都能得到目標(biāo)的位置信息(篩選算法可能得到多個(gè)目標(biāo)位置信息)，并且位置信息比較接近(目標(biāo)矩形框的重疊率較大)時(shí)，則將跟蹤算法得到的目標(biāo)位置信息與篩選算法得到的目標(biāo)位置信息按10：1的權(quán)重進(jìn)行加權(quán)平均，得到一個(gè)新的目標(biāo)位置信息。

② 當(dāng)跟蹤算法與篩選算法得到的目標(biāo)位置信息相差較大，并且篩選算法得到的結(jié)果更加準(zhǔn)確時(shí)，則由篩選算法的結(jié)果為準(zhǔn)重新初始化目標(biāo)信息。

③ 當(dāng)篩選算法無法得到目標(biāo)信息時(shí)，以跟蹤算法的結(jié)果為目標(biāo)最終位置信息。

4 實(shí)驗(yàn)結(jié)果展示

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

(a) 第7幀

(b) 第70幀

(c) 第81幀

(d) 第85幀

由對比結(jié)果展示可以看出，本文算法較之KCF算法更加魯棒。在沒有干擾的情況下，本文算法和KCF算法都能夠?qū)δ繕?biāo)進(jìn)行準(zhǔn)確跟蹤(視頻第7幀和第70幀)，但當(dāng)存在遮擋干擾時(shí)，KCF算法則無法抵抗遮擋，會(huì)出現(xiàn)跟丟目標(biāo)的現(xiàn)象并且不會(huì)重新鎖定目標(biāo)，本文算法能夠自動(dòng)重新鎖定目標(biāo)繼續(xù)跟蹤(第81幀和第85幀)。

5 結(jié)束語

在KCF算法的基礎(chǔ)之上，提出了一種魯棒的能夠?qū)σ曨l目標(biāo)進(jìn)行長時(shí)間跟蹤的算法。在對視頻目標(biāo)進(jìn)行跟蹤時(shí)，篩選算法與KCF跟蹤算法共同輸出目標(biāo)的位置信息。經(jīng)過實(shí)驗(yàn)證明，提出的算法能夠有效地抵抗物體遮擋的干擾，尤其是在出現(xiàn)跟丟目標(biāo)的情況下，能夠重新初始化目標(biāo)的準(zhǔn)確位置，提高了跟蹤的魯棒性。

[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] 張洪建.基于有限集統(tǒng)計(jì)學(xué)的多目標(biāo)跟蹤算法研究[D].上海：上海交通大學(xué)，2009.

[8] 宋驪平.被動(dòng)多傳感器目標(biāo)跟蹤方法研究[D].西安：西安電子科技大學(xué),2008.

[9] 楊柏勝.被動(dòng)多傳感器探測目標(biāo)跟蹤技術(shù)研究[D].西安：西安電子科技大學(xué),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框架的長時(shí)間視頻目標(biāo)跟蹤算法[J].無線電通信技術(shù)，2017，43(2)：55-58,82.

2016-11-08

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

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

TP391.4

A

1003-3114(2017)02-55-4