優(yōu)化搜索策略的KCF目標(biāo)跟蹤算法

楊志方，陳 曦

武漢工程大學(xué)電氣信息學(xué)院，湖北 武漢 430205

目標(biāo)跟蹤是計算機視覺領(lǐng)域中的研究熱點，在民用和軍事領(lǐng)域都有著非常廣泛的應(yīng)用。民用方面包括視頻監(jiān)控、人機交互、虛擬現(xiàn)實、移動機器人等；而軍事方面則包括無人機、戰(zhàn)場監(jiān)控、精確制導(dǎo)以及空中預(yù)警等。運動目標(biāo)跟蹤，即通過目標(biāo)的有效表達，給定第一幀圖像中目標(biāo)初始狀態(tài)（通常為位置或范圍），在圖像序列中尋找與目標(biāo)模板最相似的候選目標(biāo)區(qū)位置的過程［1］。盡管多年來目標(biāo)跟蹤領(lǐng)域已取得了不錯的進展，但它仍是一個富有挑戰(zhàn)性的問題。跟蹤技術(shù)的研究重點依舊在于：如何解決部分遮擋、平面外旋轉(zhuǎn)、背景相似以及尺度改變等［2］。如何建立有效的外觀模型是跟蹤算法能否成功的關(guān)鍵。

最早將相關(guān)濾波用于目標(biāo)跟蹤的是誤差最小平方和濾波器［3］（minimum output sum of squared error filter，MOSSF），它采用灰度特征，并用峰值旁瓣比來判斷目標(biāo)是否被遮擋或跟蹤失敗。核循環(huán)結(jié) 構(gòu) 檢 測 跟 蹤［4］（circulant structure of tracking-by-detection with kernels，CSK），速度大幅領(lǐng)先其之前的滑窗檢測法。而文獻［5］引入了循環(huán)矩陣和核的概念，并在核相關(guān)濾波器中提取方向梯度直方圖特征，利用循環(huán)矩陣在傅里葉空間可對角化的性質(zhì)大大降低了運算量。高效卷積算子的跟蹤［6］（efficient convolution operators for tracking，ECO），從模型大小、樣本集大小和更新策略3個方面加速，在多個頂尖目標(biāo)跟蹤數(shù)據(jù)集上性能都是第一，而且沒有過擬合的問題。文獻［7］在判別相關(guān)濾波器的框架下引入一種空間正則化組件，根據(jù)空間位置懲罰相關(guān)濾波器系數(shù)，擴大了訓(xùn)練圖像區(qū)域并提高了分類器性能。文獻［8］計算采樣后分塊粒子的權(quán)值函數(shù)，再利用霍夫投票機制來估計目標(biāo)位置。

1 核相關(guān)濾波跟蹤算法

1.1 循環(huán)矩陣及移位過程

核化相關(guān)濾波器的高速跟蹤（high-speed tracking with kernelized correlation filters，KCF），是目標(biāo)跟蹤領(lǐng)域一種經(jīng)典的算法，具有很高的研究價值。該算法利用循環(huán)矩陣和離散傅里葉變換以及核方法解決了復(fù)雜的矩陣運算問題，提升了跟蹤性能和相關(guān)濾波的魯棒性［9］。

文獻［5］利用嶺回歸去訓(xùn)練跟蹤器。跟蹤器在目標(biāo)的中心位置將目標(biāo)與周圍的小部分背景選做跟蹤窗口，得到大小M×N的樣本圖像塊x。再對xi進行循環(huán)移位，i∈｛0，1，…，M-1｝×｛0，1，…，N-1｝，而每一個yi都對應(yīng)于一個樣本xi的高斯標(biāo)簽（正0負(fù)1）。設(shè)訓(xùn)練樣本集為(xi,yi)，則其線性回歸函數(shù)為f(xi)=ωT⊙xi。ω為列向量，表權(quán)重系數(shù)。ω通過最小二乘法求解：

其中λ是控制過擬合的正則化參數(shù)，以保證分類器的泛化性能?！驯硎驹攸c乘。

該最小化目標(biāo)函數(shù)在頻域中有如下閉式解：

其中，XH為Hermitian轉(zhuǎn)置，即XH=（X*）T，X*為X的復(fù)數(shù)共軛。

圖1 一維向量得到的循環(huán)矩陣Fig.1 Cyclic matrix obtained from one-dimensional vector

對二維圖像，可通過循環(huán)移動x軸和y軸實現(xiàn)不同位置的移動。因此由一個向量x∈Rn可通過不斷地乘上排列矩陣得到n個循環(huán)位移向量，如圖1所示。

再將這n個向量依序排列到一個矩陣中，就形成了X生成的循環(huán)矩陣C（X）。在傅氏空間中，任意的C（X）都能使用矩陣F來進行對角化：

其中F是離散傅里葉矩陣。表示矩陣X的第一行向量經(jīng)過離散傅里葉變換后的值。循環(huán)移位得到的樣本如圖2所示。

圖2 二維圖像經(jīng)過不同行數(shù)的移位：（a）下移30行，（b）下移15行，（c）基樣本，（d）上移15行，（e）上移30行Fig.2 Two-dimensional images shifting through different lines：（a）down 30，（b）down 15，（c）sample，（d）up 15，（e）up 30

1.2 濾波器系數(shù)及相關(guān)響應(yīng)的求解

利用核方法，將線性問題的輸入映射到非線性特征空間Φ（x）中。過程分為如下兩步：

1）將解ω表達為樣本的線性組合：。其中αi為ω的對偶空間向量，即濾波器系數(shù)。

2）用點積的形式來寫入核方法：k(x,x')=φT(x')?φ(x)，該方法用核函數(shù)k（高斯或多項式）來計算。所有樣本對間的點積保存在一個n×n的核矩陣K中，元素值為Kij=k(xi,xj)。

但核方法的缺點在于，回歸函數(shù)的復(fù)雜性會隨樣本數(shù)目的增加而增加：

存在如下定理：給定循環(huán)數(shù)據(jù)C（x），對任意排列（置換）矩陣M，當(dāng)核函數(shù)滿足k(x,x')=k(Mx,Mx')，則對應(yīng)的K為循環(huán)矩陣。而核化的嶺回歸的解為：α=(K+λ?I)-1y。其中K為核矩陣，α為系數(shù)αi的向量，對偶空間中的解。再像線性情況一樣對角化上述方程，有其中kxx為核矩陣 K=C（kxx）的第一行的向量，y?為標(biāo)簽列向量的傅里葉變換。

很少單獨對一個圖像塊來評估回歸函數(shù)f（z）。為快速檢測感興趣物體，一般在若干圖像位置上評估f（z），這些塊可用循環(huán)移位來建模［10］。再用KZ表示所有訓(xùn)練樣本與候選塊間的核矩陣。而所有訓(xùn)練樣本和圖像塊都分別為基樣本x和基塊z的循環(huán)移位。用循環(huán)矩陣的第一行向量來定義核矩陣：KZ=C（kXZ），由方程（4）可計算所有候選塊的回歸函數(shù)：f（z）=（KZ）T·α。其中f（z）為檢測響應(yīng)，包含了所有z循環(huán)移位的輸出。

為了有效計算上述回歸函數(shù)，結(jié)合上式并對角化f（z），有

2 優(yōu)化搜索策略的改進算法

如1.1節(jié)所述，分類器在M×N的樣本圖像塊x上訓(xùn)練，并以目標(biāo)位置為每一塊的中心。當(dāng)訓(xùn)練結(jié)束后，對于后續(xù)幀，同樣以上一幀目標(biāo)位置為中心（預(yù)測區(qū)域），在大小為M×N的圖像塊z（patch）上檢測并計算響應(yīng)。檢測的候選區(qū)域便是由上一幀的預(yù)測區(qū)域做循環(huán)移位得到的，如圖3所示。通過密集采樣可以提取出圖像塊的全部特征，優(yōu)于只利用每個候選框的局部特征的隨機采樣。

圖3 檢測圖像塊：（a）隨機采樣，（b）密集采樣Fig.3 Sampling of detected image patches：（a）random sampling，（b）dense sampling

雖然密集采樣可以利用圖像塊的全部特征，但是信息冗余非常大，并且會降低搜索速度。由實驗觀察到，視頻前后兩幀中的兩個目標(biāo)區(qū)域塊，其均值和方差應(yīng)該最為接近?；诖颂岢隽艘环N優(yōu)化搜索策略，用于改進KCF算法的密集采樣部分，以達到提高搜索速度，實現(xiàn)目標(biāo)跟蹤實時性的目的。

在第t幀中，由最大響應(yīng)得到了目標(biāo)的位置，該圖像塊大小為目標(biāo)框加擴大1.5倍的padding窗口。其數(shù)據(jù)存放在二維數(shù)組中，數(shù)組的元素即為圖像的像素。先將第t幀中圖像塊的均值和標(biāo)準(zhǔn)差記為μm和σm。而下一幀中，經(jīng)循環(huán)移位的n個圖像塊的均值和標(biāo)準(zhǔn)差分別為：μ1,μ2,…,μn和σ1,σ2,…,σn。再把它們與μm和σm作比較，滿足以下條件的圖像塊優(yōu)先檢測并計算響應(yīng)：

手動選擇閾值并測試數(shù)據(jù)集中的6個視頻序列（Basketball，Bird2，Box，Car4，F(xiàn)reeman1，Girl），本文算法的平均跟蹤幀率提升為10.1%～12.1%。然而，在實際跟蹤過程中，多次手動設(shè)置閾值會影響跟蹤效率，統(tǒng)一設(shè)置固定閾值又會降低算法的自適應(yīng)性，使得跟蹤準(zhǔn)確度受到影響［11］。

為避免上述問題，本文將閾值設(shè)為能夠使算法的平均跟蹤幀率提升10%時的閾值大小。為求得該自適應(yīng)閾值，需要先確定平均每幀所需的用于匹配的圖像塊個數(shù)。假設(shè)算法幀率提升達到10%時，平均每幀需要用到k（k＜n）個候選圖像塊用來跟蹤并計算目標(biāo)的中心位置。再依據(jù)最相似圖像塊間的均值和標(biāo)準(zhǔn)差的距離應(yīng)最小的原理，這k個候選塊取自排序隊列中距離最小的前k個，其中，排序隊列按照如下公式計算所得的距離大小進行排列：

公式（7）中，di反應(yīng)了當(dāng)前幀中的圖像塊i與上一幀中的目標(biāo)圖像塊m之間的均值和標(biāo)準(zhǔn)差的距離大小，α∈(0,1)為排序時分別賦予均值和方差的權(quán)重，當(dāng)圖像塊的均值對跟蹤結(jié)果的影響更大時，算法取α＞0.5，當(dāng)圖像塊的標(biāo)準(zhǔn)差對跟蹤結(jié)果影響更大時，算法取α＜0.5。將全部n個塊都按上述公式算出值并按由小到大的順序排序，那么，序列中的前k個距離所對應(yīng)的k個圖像塊，即為算法在實際跟蹤時用于匹配的k個圖像塊。后續(xù)n-k個塊由于誤差較大，因此舍棄不用。

設(shè)定平均幀率提升10%的情況下，可以確定每幀平均所需的匹配圖像塊個數(shù)k，在此基礎(chǔ)上，閾值T1，T2可以通過上一幀目標(biāo)中心圖像塊m與當(dāng)前幀第k塊之間的均值、標(biāo)準(zhǔn)差的差值得到。而且每個測試集由于圖像的像素不同（720×400，576×432等）和面臨的問題不同（比如遮擋、背景相似、尺度變化等），閾值會根據(jù)滿足標(biāo)準(zhǔn)的μk、σk自動調(diào)整，達到自適應(yīng)的效果。

3 結(jié)果與討論

實驗平臺為Windows7 64位旗艦版系統(tǒng)和MATLAB R2014a軟件，在筆記本電腦上進行了調(diào)試運行。CPU為英特爾酷睿i5-3210M@2.50 GHz雙核，內(nèi)存為 DDR3 1 600 MHz 4 GB［12］。

選取OTB100［13］上的6個具有挑戰(zhàn)性的視頻序列（Basketball，Bird2，Box，Car4，F(xiàn)reeman1，Girl）進行測試，并對比分析了實驗結(jié)果。這些序列中的目標(biāo)會受到諸如光照變化、快速運動、尺度變化、遮擋以及平面外旋轉(zhuǎn)等多種復(fù)雜因素的影響。實驗中改進算法的MATLAB源碼是由作者公開的個人網(wǎng)站上獲取的，可以保證實驗數(shù)據(jù)的公正客觀。

3.1 候選圖像塊數(shù)量的影響

實驗首先測試了算法幀率是否會受到圖像塊數(shù)量的影響。將原文中用于擴展背景信息的pad?ding窗口由1.5倍目標(biāo)框擴大倍數(shù)修改為0.5和1.0，再進行對目標(biāo)候選區(qū)域的分塊測試。實驗結(jié)果表明改變padding大小對跟蹤的精度并無顯著影響，在3個視頻序列上分為不同大小圖像塊的幀率如表1所示。

表1 不同padding大小下的算法幀率Tab.1 Algorithm frame per second performance at different padding sizes frames/s

從表1可得出padding越小時算法幀率也越小的結(jié)論。由于padding較小時會增加預(yù)測區(qū)域循環(huán)移位的次數(shù)，導(dǎo)致分塊得到的patch數(shù)量增加，使公式（5）計算核相關(guān)的次數(shù)也相應(yīng)地增加，因此算法的速度會稍微降低。本實驗未對padding做更大值的測試，原因是分塊尺度過大，搜索窗可能占滿整個圖像甚至超過原圖像的尺寸，故無法對原圖進行分塊，也無法對目標(biāo)進行跟蹤。因此，padding為1.5倍大小時跟蹤效果最顯著。

3.2 不同算法對比分析

實驗中控制過擬合的正則化參數(shù)λ設(shè)為10-4。高斯核條件下的σ為0.2。padding窗經(jīng)過上述分析取1.5。k在Basketball序列中取13（總共40個），即前32.5%的圖像塊，在Girl序列中取11（總共24個），即前45.8%的圖像塊。自適應(yīng)閾值T1和T2根據(jù)上述不同k值計算出的μk、σk自動調(diào)整時效果較好。

在MATLAB上選用距離精度作為衡量算法性能的指標(biāo)，目標(biāo)的中心位置誤差（center position error，CLE）小于某一固定閾值時，符合的幀數(shù)與視頻總幀數(shù)的比值即為算法精度。這里的閾值通常以20個像素返回精度。

圖4的實驗結(jié)果集成了改進算法OSKCF（Op?timized Searching Strategy for KCF，OSKCF）與較早的9種性能較好的跟蹤算法，并橫向?qū)Ρ攘似渲蠧SK、KCF、Struck［14］（structured output tracking with kernels，Struct）和檢測學(xué)習(xí)跟蹤［15］（tracking-learn?ing-detection，TLD）4種算法的性能。橫坐標(biāo)為目標(biāo)誤差像素閾值，以10像素為1個單位，縱坐標(biāo)則表示算法精度。各算法曲線基本呈半梯形（左半部分）狀，閾值在30像素后曲線基本不再增長，因此取20像素來計算閾值是合理的。

圖4 不同跟蹤算法的精度圖Fig.4 Precision of different tracking algorithms

從圖4可看出，經(jīng)過優(yōu)化候選區(qū)域的搜索策略并篩選圖像塊后，改進算法OSKCF的性能在較早的10個測試算法中最好，優(yōu)于2012年以前最快的算法Struct以及經(jīng)典的long-term算法TLD。在測試Basketball序列時，OSKCF平均精度為0.942，平均幀率為115.83幀/秒。而原KCF平均精度和幀率為0.923和103.34幀/秒，幀率提升達12.1%；測試Girl序列時，OSKCF平均精度和幀率分別為0.879和 157.67幀/秒，原 KCF分別為 0.864和143.25幀/秒，幀率提升10.1%。而測試其他幾個挑戰(zhàn)性更大的序列，涉及目標(biāo)的快速運動及遮擋問題，精度較低只有50%左右。本算法的精度較KCF，Struct，TLD，CSK 分 別 提 升 2.2%，14.4%，24.9%，35.3%。測試6個視頻序列的平均幀率如表2所示。

表2 算法在6個視頻序列上的平均幀率Tab.2 Average frame rates of algorithms in 6 video sequences frames/s

經(jīng)過分析，優(yōu)化搜索策略后的OSKCF雖然對跟蹤精度提升不大，但是可以明顯提升原算法的幀率，從而使得目標(biāo)跟蹤算法的實時性進一步得到提高。

4 結(jié) 語

本文提出了一種優(yōu)化候選圖像塊搜索策略的OSKCF算法，通過T1和T2這兩個自適應(yīng)閾值和最相似圖像塊間的均值方差的距離應(yīng)最小的原理，選取排序隊列中距離最小的前k個候選圖像塊，明顯提升算法的FPS。實驗結(jié)果表明，本文算法較原算法速度提升10%左右，性能較好，可滿足大多數(shù)情況下的目標(biāo)跟蹤檢測需求。但是在目標(biāo)受到諸如光照變化、快速運動、遮擋以及平面外旋轉(zhuǎn)等多種復(fù)雜因素的影響時，部分測試視頻出現(xiàn)無法準(zhǔn)確跟蹤目標(biāo)的現(xiàn)象。如何解決這些當(dāng)前跟蹤領(lǐng)域的一些共同難點，避免產(chǎn)生跟蹤漂移等問題，將在未來的工作中做進一步研究。