自適應多策略融合快速KCF跟蹤算法

王 玲 馬勝楠 王 鵬

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

0 引 言

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

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

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

1 KCF算法

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

(1)

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

(2)

(3)

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

(4)

2 自適應多策略融合快速KCF算法

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

圖1 算法架構圖

2.1 自適應尺度更新策略

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

圖2 自適應尺度更新策略

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

(5)

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

(6)

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

2.2 特征融合策略

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

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

(a) 原圖

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

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

(7)

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

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

(8)

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

(9)

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

2.3 自適應目標響應策略

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

(10)

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

(11)

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

(12)

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

3 實 驗

3.1 實驗環境

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

3.2 評價標準

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

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

(13)

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

(14)

式中:x1、y1表示目標真實位置;x2、y2表示目標預測位置。

跟蹤成功率S是指計算跟蹤目標預測位置和真實位置的重疊率O在給定閾值T2范圍內的幀數和N的比值。計算公式如下:

(15)

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

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

(16)

式中:RZ為目標真實區域;RY為目標預測區域。

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

(17)

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

3.3 跟蹤性能測評

3.3.1消融實驗分析

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

表1 消融實驗

3.3.2定量分析

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

圖4 跟蹤精度

圖5 跟蹤成功率

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

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

圖6 形變跟蹤精度

圖7 尺度變化跟蹤精度

圖8 平面內旋轉跟蹤精度

圖9 背景復雜跟蹤精度

3.3.3定性分析

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

表2 視頻序列屬性

(a) Shaking

(b) Soccer

(c) Football

(d) CarScale

圖10 部分視頻序列可視化結果

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

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

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

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

3.3.4實時性分析

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

表3 跟蹤速度

4 結 語

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