自適應(yīng)多策略融合快速KCF跟蹤算法

王 玲 馬勝楠 王 鵬

(長春理工大學(xué)計算機科學(xué)技術(shù)學(xué)院 吉林 長春 130022)

0 引 言

目標(biāo)跟蹤是計算機視覺中重要的研究領(lǐng)域,在人機交互[1]、監(jiān)控、增強現(xiàn)實、無人駕駛等場景有著廣泛的應(yīng)用。近幾年,深度學(xué)習(xí)與相關(guān)濾波這兩類算法推動了目標(biāo)跟蹤領(lǐng)域的發(fā)展。深度學(xué)習(xí)類算法雖然跟蹤精度高但實時性較差;相關(guān)濾波類算法跟蹤精度和實時性都具有良好的性能,逐漸成為廣大學(xué)者的研究對象。

Bolme等[2]首次將相關(guān)濾波理論應(yīng)用到目標(biāo)跟蹤算法中,提出最小平方誤差和(Minimum Output Sum of Squared Error filter,MOSSE)算法。Henriques等[3]在MOSSE算法的基礎(chǔ)上引入循環(huán)矩陣和核函數(shù),提出CSK(Circulant Structure of tracking-by-detection with Kernels)算法,之后又在CSK的基礎(chǔ)上擴展了多通道HOG(Histogram of Oriented Gradient)特征,提出了核相關(guān)濾波(Kernelized Correlation Filters,KCF)算法[4],有效地提升了跟蹤速度和精度。Danelljan等[5]在MOSSE算法基礎(chǔ)上通過添加尺度濾波器解決目標(biāo)尺度變化問題,提出多尺度空間濾波(Discriminative Scale Space Tracking,DSST)算法,又在CSK算法基礎(chǔ)上通過增加顏色特征對目標(biāo)進行跟蹤,提出了CN(Color Name)算法[6]。Li等[7]融合HOG和CN特征并引入七尺度的尺度因子解決尺度不變的問題,提出SAMF(Scale Adaptive Multiple Feature)算法,但實時性較差。Bertinetto等[8]融合HOG和CN特征,添加尺度濾波器,提出Staple——基于互補學(xué)習(xí)的目標(biāo)跟蹤(Complementary Learners for Real-Time Tracking)算法,提高了算法在目標(biāo)形變下的魯棒性,但增加了計算量實時性較差。經(jīng)過不斷地改進,目標(biāo)跟蹤算法在速度與精度上已有很大的提升,但由于復(fù)雜的背景環(huán)境、目標(biāo)外觀與尺度的變化等眾多影響因素,使目標(biāo)能夠在復(fù)雜場景中實現(xiàn)精準(zhǔn)快速地跟蹤依然充滿著巨大挑戰(zhàn)。

本文以KCF算法為基礎(chǔ),首先針對該算法無法應(yīng)對跟蹤目標(biāo)尺度變化的問題,提出尺度自適應(yīng)更新策略[9]來完善KCF算法采用固定尺度窗口進行跟蹤的缺陷;然后分別提取FHOG(F Histogram of Oriented Gradient)特征和利用PCA降維[10]后的CN特征進行串聯(lián)融合,來提高算法在復(fù)雜背景下的跟蹤精度;最后利用自適應(yīng)目標(biāo)響應(yīng)策略訓(xùn)練KCF濾波器,并用子網(wǎng)格插值算法[11]代替簡單線性插值算法,來提高跟蹤器的整體性能。本文算法能夠以較高的精度與速度完成復(fù)雜場景下的魯棒跟蹤。

1 KCF算法

KCF算法對樣本循環(huán)采樣,增加樣本容量;利用循環(huán)矩陣對角化性質(zhì)將矩陣運算轉(zhuǎn)化成向量點乘,減少運算量;提取HOG特征,提高分類器識別能力;利用核函數(shù),將特征映射到高維空間使其線性可分。KCF利用最小二乘法訓(xùn)練更新分類器,公式如下:

(1)

式中:X為訓(xùn)練樣本;g為目標(biāo)響應(yīng)峰值;λ為正則化系數(shù)。通過訓(xùn)練找到一組權(quán)值w,w=(XHX+λI)-1XHg,其中,XH=(X*)T,X*為X的共軛;在傅里葉域中,利用循環(huán)矩陣可對角化性質(zhì)求解w,公式如下:

(2)

(3)

于是可以得到檢測樣本的響應(yīng)值,公式如下:

(4)

2 自適應(yīng)多策略融合快速KCF算法

本文算法架構(gòu)圖如圖1所示。首先,對輸入的視頻幀(除了第一幀以外)使用自適應(yīng)尺度[12]更新策略,判斷是否需要更新跟蹤目標(biāo)的尺度,采用SSIM(Structural Similarity)作為衡量依據(jù),如果SSIM值小于閾值T則進行多尺度采樣;然后,從多個尺度的目標(biāo)樣本中分別提取FHOG特征和利用PCA降維后的CN特征進行串聯(lián)融合,計算多個尺度圖像塊的特征響應(yīng)圖,其中響應(yīng)值最大的圖像塊即為最佳尺度;否則,認為目標(biāo)尺寸沒有發(fā)生變化,延用上一幀圖像尺寸,不進行尺寸更新;最后,利用自適應(yīng)目標(biāo)相應(yīng)策略訓(xùn)練位置濾波器,并用子網(wǎng)格插值算法代替線性插值算法,減少離散傅里葉變換次數(shù),提高核相關(guān)濾波算法速度,更新訓(xùn)練集與濾波模板,在對下一幀圖像進行同樣操作,直到最后一幀為止。

圖1 算法架構(gòu)圖

2.1 自適應(yīng)尺度更新策略

KCF算法采用固定尺寸窗口對目標(biāo)進行跟蹤,跟蹤過程中,目標(biāo)的尺寸易于發(fā)生變化,KCF算法難以應(yīng)對此問題,因此,本文采用自適應(yīng)尺度更新策略來解決跟蹤窗口尺寸固定不變的問題,自適應(yīng)尺度更新策略如圖2所示。

圖2 自適應(yīng)尺度更新策略

首先預(yù)定義尺度池P={Sp|p=1,2,…,p},Sp為尺度因子,設(shè)第t幀圖像目標(biāo)中心位置為(rt,ct),目標(biāo)尺度為St,當(dāng)輸入第t+1幀圖像時,以(rt,ct)為中心,然后提取尺度大小為St的圖像塊,第t幀與第t+1幀圖像提取到的圖像塊分別為F1與F2,尺度池的引入嚴(yán)重增加算法計算量,導(dǎo)致算法難以滿足實時性的需求,基于此,本文通過添加SSIM校驗,來提高算法運行速度。計算第t幀與第t+1幀目標(biāo)響應(yīng)圖像的SSIM值,公式如下:

(5)

式中:μF1與μF2分別表示圖像塊F1與F2的平均值,σF1F2表示圖像的協(xié)方差,σF12與σF22表示圖像F1與F2的方差,C1=(k1L)2,C2=(k2L)2,C1與C2是使分母不為0,維持穩(wěn)定的常數(shù),L是像素值,k1=0.01,k2=0.03。設(shè)定閾值T(取值范圍0到1)作為判斷圖像相似的標(biāo)準(zhǔn),當(dāng)SSIM的值大于閾值T時,認為F1與F2響應(yīng)圖像相似[13],則保持當(dāng)前目標(biāo)的尺寸,不對目標(biāo)進行尺度更新;如果SSIM的值小于閾值T,認為F1與F2不相似,即可認為目標(biāo)尺寸發(fā)生變化,這時候在分別提取大小為Sp·St的p個圖像塊,歸一化圖像塊為Zp,求出所有圖像塊的響應(yīng)值,其中最大值y即為跟蹤目標(biāo)的最佳尺度。y的計算公式為:

(6)

式中:F-1為傅里葉逆變換。y取最大值時的Zp對應(yīng)的Sp即為第t+1幀的最佳尺度St+1。在訓(xùn)練階段更新濾波器系數(shù)和目標(biāo)模板。通過添加尺度更新機制來減少算法計算量以此提高算法運行速度。

2.2 特征融合策略

KCF算法提取單一的HOG特征訓(xùn)練分類器,無法滿足目標(biāo)特征的多樣性,在背景復(fù)雜的環(huán)境中,由于特征信息量不足,分類器難以有效地區(qū)分出目標(biāo),導(dǎo)致跟蹤精度低、魯棒性差,將HOG特征與CN特征進行融合的確是一個很好的解決辦法,目前一些算法利用這種方式對其進行改進,效果顯著,但是特征信息量的增加也增大了算法計算量,導(dǎo)致算法運行速度慢,難以滿足實時性需求。因此,本文提出采用FHOG特征與利用PCA降維后的CN特征進行融合,在不過多損失特征信息量與增加算法計算量的雙重情況下,為分類器提供更充分的特征信息,提高復(fù)雜背景下,分類器的辨別能力。

FHOG特征具有31個維度,是在36維HOG特征的基礎(chǔ)上降維得到的,包含了HOG特征的所有信息,在對目標(biāo)的特征提取中具有同樣的效果,提取FHOG特征前后的圖像如圖3所示。

(a) 原圖

(b) FHOG圖圖3 提取FHOG特征圖

PCA首先將11維度的CN特征通過線性變換表示成線性無關(guān)的向量,利用協(xié)方差矩陣計算向量的分散程度,取方差最大的方向做投影,使降維后的數(shù)據(jù)最大限度地包含全部信息。設(shè)特征向量為X={x(1),x(2),…,x(m)},x(i)∈Rn,m=11,協(xié)方差矩陣為:

(7)

由特征值λ與特征向量u變換后得到:

WT=(u1,u2,…,um)m

(8)

式中:(u1,u2,…,um)是按特征值λ1,λ2,…,λn由大到小序列對應(yīng)排放組成的矩陣,通過Y=WTX計算降維后的CN特征為:

(9)

式中:WCN是由協(xié)方差矩陣的前2個最大特征值向量組成。本文通過PCA對CN顏色特征自適應(yīng)[14]降維至2維,實時地選擇2維比較顯著的顏色特征與31維FHOG特征再加1維灰度特征進行串聯(lián)融合,最終的特征信息量為34維向量,避免損失過多特征信息量的同時最大限度地提高算法的速度。

2.3 自適應(yīng)目標(biāo)響應(yīng)策略

KCF跟蹤算法在第一幀圖像初始化目標(biāo)位置,然后提取目標(biāo)特征訓(xùn)練分類器,在下一幀圖像中找到響應(yīng)最大的位置,更新分類器。因此在跟蹤過程中,目標(biāo)的外觀會隨著的時間的推移發(fā)生變化,在檢測[15]步驟容易出現(xiàn)錯誤,對于每一幀模板都進行更新,這樣可能會導(dǎo)致錯誤累積,最終模板不完全適合目標(biāo),發(fā)生偏移甚至完全跟丟目標(biāo),同時,KCF跟蹤器應(yīng)用一個簡單的線性插值(α)t=(1-η)(α)t-1+η(α)t與一個固定的學(xué)習(xí)率η來更新模板,這樣會導(dǎo)致算法運算效率低,模板不能很好地適應(yīng)目標(biāo)外觀的變化。因此,本文提出了自適應(yīng)目標(biāo)響應(yīng)策略使濾波模板的更新更貼合目標(biāo)形變,其中g(shù)作為每一幀圖像的響應(yīng),第一幀的目標(biāo)響應(yīng)為g0。測量響應(yīng)最大值的相關(guān)性與目標(biāo)運動特性和目標(biāo)外觀特性相結(jié)合,所以對式(1)的優(yōu)化如下:

(10)

設(shè)圖像響應(yīng)g與g0的關(guān)系為g=g0+ε,并且g∈N(g0,diag-1(1/2ξ))。模型訓(xùn)練時,需要對樣本進行移位,響應(yīng)最大值為目標(biāo)估計位置。接下來我們要計算這些移位的相關(guān)的分?jǐn)?shù)作為模板的更新參數(shù),使用高斯插值來填充其余分?jǐn)?shù)。模板w用下式表示:

(11)

利用KCF算法巧妙地使用內(nèi)核技巧,將輸入向量通過高斯核函數(shù)映射到高維空間做運算,以此得到對偶域的閉型解,公式如下:

(12)

與此同時,由于子網(wǎng)格插值算法可以使用更粗的特征網(wǎng)格來訓(xùn)練和檢測樣本,因此利用三角多項式插值方法代替簡單線性插值方法,通過對高頻零填充來獲得(α)t的大小,使其大小等于插值網(wǎng)格的大小,然后獲得差值分?jǐn)?shù),減少目標(biāo)樣本與模板相關(guān)響應(yīng)時的離散傅里葉變換次數(shù),降低計算量,從而提高分類器的運行速度。

3 實 驗

3.1 實驗環(huán)境

實驗數(shù)據(jù)環(huán)境為OTB2015數(shù)據(jù)集[16]中的51組視頻序列,涵蓋了11種復(fù)雜場景屬性。實驗運行環(huán)境為Windows 10 64 bit操作系統(tǒng)、處理器Intel @R Xeon @R SILVER4110C @2.10 GHz 16 GB的計算機,程序代碼的編譯環(huán)境為MATLAB軟件R2016b版本。實驗參數(shù)環(huán)境設(shè)置與KCF算法基本一致,尺度因子P設(shè)置為5,具體為{0.96,0.98,1,1.02,1.04},SSIM閾值T為0.9。本文采用以上實驗環(huán)境進行跟蹤實驗。

3.2 評價標(biāo)準(zhǔn)

本文采用跟蹤精度、跟蹤成功率和跟蹤速度來評估算法性能。

設(shè)視頻總幀數(shù)為N,跟蹤精度P是指中心位置誤差D在閾值T1范圍內(nèi)的幀數(shù)與N的比值,計算公式如下:

(13)

式中:精度閾值T1的范圍為0到50,P取值為閾值T1等于20像素時所對應(yīng)的結(jié)果。中心位置誤差D的計算公式如下:

(14)

式中:x1、y1表示目標(biāo)真實位置;x2、y2表示目標(biāo)預(yù)測位置。

跟蹤成功率S是指計算跟蹤目標(biāo)預(yù)測位置和真實位置的重疊率O在給定閾值T2范圍內(nèi)的幀數(shù)和N的比值。計算公式如下:

(15)

式中:閾值T2的取值范圍為0到1,S取值為取閾值T2等于0.5時所對應(yīng)結(jié)果。重疊率O的計算公式如下:

O=area(RZ∩RY)/area(RZ∪RY)

(16)

式中:RZ為目標(biāo)真實區(qū)域;RY為目標(biāo)預(yù)測區(qū)域。

FPS代表算法跟蹤速度,是N與算法處理整個視頻序列所耗費的時間Ttoc的比值。計算公式如下:

(17)

FPS的值越大,代表跟蹤算法的速度越快。

3.3 跟蹤性能測評

3.3.1消融實驗分析

為了驗證本文算法的有效性,首先在OTB 2015數(shù)據(jù)集上進行了消融實驗,對比算法及實驗結(jié)果如表1所示。實驗結(jié)果表明,在KCF算法基礎(chǔ)上逐個添加改進策略,算法的跟蹤精度與成功率在逐步提高,驗證了本文算法的有效性。

表1 消融實驗

3.3.2定量分析

本文選取5種具有代表性的跟蹤算法與4種近年較優(yōu)秀的跟蹤算法進行對比實驗,這些算法包括KCF算法、CN算法、DSST算法、KCFHS算法[17]、SAMF算法、FDSST算法[18]、CFNet算法[19]、LMCF算法[20],以及ECO-CH[21]算法,在OPE測試方法下,評測這些算法的跟蹤精度和跟蹤成功率,實驗結(jié)果如圖4-圖5所示。

圖4 跟蹤精度

圖5 跟蹤成功率

實驗結(jié)果表明本文算法在跟蹤精度與成功率上優(yōu)于近幾年較優(yōu)秀的相關(guān)濾波類跟蹤算法LMCF、FDSST和融合了淺層深度特征的CFNet、ECO-HC算法,同時大幅度提升了基礎(chǔ)算法KCF的跟蹤性能,驗證了本文算法的有效性。

另外,本文算法在11種復(fù)雜場景中均表現(xiàn)良好,特別在目標(biāo)形變、尺度變化、平面內(nèi)旋轉(zhuǎn)、背景復(fù)雜這4種屬性下,本文算法展現(xiàn)了較為優(yōu)異的跟蹤精度,實驗結(jié)果如圖6-圖9所示。自適應(yīng)尺度更新策略避免算法每一幀都進行多個尺度循環(huán)檢測運算,減少了大量計算量的同時解決了KCF算法無法處理目標(biāo)尺度變化的問題,使算法實現(xiàn)自適應(yīng)調(diào)節(jié)跟蹤框的大小;多特征融合策略利用PCA對特征降維后再融合,避免增加過多計算量的同時提取更加豐富的特征信息,提高濾波器的分辨能力,使算法以更加魯棒的性能應(yīng)對目標(biāo)形變、背景復(fù)雜等跟蹤場景;自適應(yīng)目標(biāo)響應(yīng)策略通過結(jié)合第一幀的目標(biāo)響應(yīng)值獲取目標(biāo)外觀信息并結(jié)合目標(biāo)運動信息調(diào)節(jié)每一幀目標(biāo)的響應(yīng)值,使目標(biāo)響應(yīng)的最大值更接近目標(biāo)真實位置,提高了跟蹤算法在目標(biāo)形變與平面旋轉(zhuǎn)等復(fù)雜場景下的跟蹤精度。

圖6 形變跟蹤精度

圖7 尺度變化跟蹤精度

圖8 平面內(nèi)旋轉(zhuǎn)跟蹤精度

圖9 背景復(fù)雜跟蹤精度

3.3.3定性分析

本文選取濾波類跟蹤算法KCF、SAMF、FDSST和融合淺層深度特征算法ECO-HC在4種具有代表性的視頻序列上進行定性分析,每個視頻序列具有的屬性如表2所示,可視化結(jié)果如圖10所示。

表2 視頻序列屬性

(a) Shaking

(b) Soccer

(c) Football

(d) CarScale

圖10 部分視頻序列可視化結(jié)果

(1) Shaking序列。第23幀,跟蹤目標(biāo)的形狀與尺度略微變化,KCF算法與SAMF算法嚴(yán)重漂移;第147幀,被跟蹤目標(biāo)發(fā)生了劇烈形變且伴有平面外旋轉(zhuǎn)、光照變化等干擾因素,本文算法對目標(biāo)定位的最好;第242幀,跟蹤目標(biāo)產(chǎn)生尺度變化與形狀變化,此時本文算法對目標(biāo)尺度控制得最好。

(2) Soccer序列。第59幀,跟蹤目標(biāo)發(fā)生快速移動且伴有嚴(yán)重模糊,ECO-HC算法與SMAF算法開始產(chǎn)生漂移;第179幀,ECO-HC算法與SMAF算法由于提取到過多背景信息而完全丟失目標(biāo),KCF與FDSST算法輕微漂移;第252幀,跟蹤目標(biāo)的尺度發(fā)生變化且伴有背景復(fù)雜、光照變化等影響因素,此時本文算法依然可以準(zhǔn)確地跟蹤到目標(biāo)的位置,對尺度的控制優(yōu)于FDSST算法。

(3) Football序列。第286幀,目標(biāo)發(fā)生快速移動且被相似障礙物嚴(yán)重遮擋,此時本文算法與FDSST算法可以準(zhǔn)確捕獲目標(biāo)的位置,SAMF、KCF與ECO-HC算法發(fā)生略微漂移,被相似障礙物牽引;第298幀,跟蹤目標(biāo)輕微形變且伴有平面內(nèi)旋轉(zhuǎn)等干擾因素,此時SAMF算法與KCF算法已經(jīng)完全漂移,其他算法還可以勉強跟蹤到目標(biāo);第319幀,跟蹤目標(biāo)快速移動且伴有平面外旋轉(zhuǎn),此時本文算法對目標(biāo)的定位最好。

(4) Carscale序列。第188幀到220幀再到最后240幀,跟蹤目標(biāo)尺度由小到大逐漸變化著,且伴有平面內(nèi)外旋轉(zhuǎn)、快速移動等干擾因素,這些算法都能順利完成跟蹤任務(wù),由于本文算法與SAMF算法采用尺度因子對目標(biāo)尺度變化有一定的局限性,超過最大限度,本文算法也失去了對尺度的控制能力,此時基于尺度濾波器的FDSST算法與采用淺層深度特征的ECO-HC算法對目標(biāo)的尺度定位的最好,本文算法雖沒有FDSST與ECO-HC算法對目標(biāo)尺度產(chǎn)生大幅度變化時定位得好,但是當(dāng)目標(biāo)的尺度在一定范圍內(nèi)變化時,本文算法對尺度的控制較優(yōu)于其他算法。

3.3.4實時性分析

復(fù)雜的背景下,跟蹤速度也是衡量一個跟蹤算法的重要指標(biāo)。表3是本文實驗比較的10種跟蹤算法的FPS值,本文算法的FPS較KCF算法雖然有所降低,但是權(quán)衡算法的跟蹤精度和成功率的提高,損失的速度也是值得的,并且相比于其他跟蹤算法,本文算法仍然占據(jù)一定的優(yōu)勢。SSIM檢測標(biāo)準(zhǔn)對多尺度更新的效驗、利用PCA對CN顏色特征的降維、將子網(wǎng)格插值算法代替線性插值均在保證算法跟蹤精度的同時大幅度降低算法的計算量,提高計算效率,使算法快速運算滿足實時性需求。

表3 跟蹤速度

4 結(jié) 語

針對KCF算法存在的缺陷以及提高算法在復(fù)雜跟蹤場景下的綜合性能,提出了一種自適應(yīng)多策略融合快速KCF跟蹤算法。在Benchmark評測集OTB2015上進行了大量實驗,對比了9種優(yōu)秀的相關(guān)濾波類跟蹤算法,充分驗證本文對算法所做的改進具有實際效果,能夠在目標(biāo)形變、平面外旋轉(zhuǎn)、背景復(fù)雜、尺度變化多種復(fù)雜場景挑戰(zhàn)下,準(zhǔn)確、魯棒、快速地跟蹤目標(biāo),滿足實時性需求。但改進后的算法缺乏對跟蹤目標(biāo)重檢測機制,一旦目標(biāo)被遮擋或者經(jīng)歷嚴(yán)重外觀形變,分類器難以適應(yīng)目標(biāo)瞬時的變化,導(dǎo)致跟蹤失敗,將再也不會檢測到跟蹤目標(biāo),進行后續(xù)的跟蹤,完善此缺陷將是接下來的研究重點。