優化搜索策略的KCF目標跟蹤算法

楊志方，陳 曦

武漢工程大學電氣信息學院，湖北 武漢 430205

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

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

1 核相關濾波跟蹤算法

1.1 循環矩陣及移位過程

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

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

其中λ是控制過擬合的正則化參數，以保證分類器的泛化性能。⊙表示元素點乘。

該最小化目標函數在頻域中有如下閉式解：

其中，XH為Hermitian轉置，即XH=（X*）T，X*為X的復數共軛。

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

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

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

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

圖2 二維圖像經過不同行數的移位：（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 濾波器系數及相關響應的求解

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

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

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

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

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

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

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

2 優化搜索策略的改進算法

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

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

雖然密集采樣可以利用圖像塊的全部特征，但是信息冗余非常大，并且會降低搜索速度。由實驗觀察到，視頻前后兩幀中的兩個目標區域塊，其均值和方差應該最為接近。基于此提出了一種優化搜索策略，用于改進KCF算法的密集采樣部分，以達到提高搜索速度，實現目標跟蹤實時性的目的。

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

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

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

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

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

3 結果與討論

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

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

3.1 候選圖像塊數量的影響

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

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

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

3.2 不同算法對比分析

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

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

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

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

從圖4可看出，經過優化候選區域的搜索策略并篩選圖像塊后，改進算法OSKCF的性能在較早的10個測試算法中最好，優于2012年以前最快的算法Struct以及經典的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%。而測試其他幾個挑戰性更大的序列，涉及目標的快速運動及遮擋問題，精度較低只有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

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

4 結 語

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