改進的核相關濾波跟蹤算法

孫 健，向 偉，譚舒昆，劉云鵬

SUN Jian1，2,XIANG Wei1,TAN Shukun1,2,LIU Yunpeng1

1.中國科學院 沈陽自動化研究所，沈陽 110016

2.中國科學院大學，北京 100049

1.Shenyang Institute ofAutomation,ChineseAcademy of Sciences,Shenyang 110016,China

2.University of ChineseAcademy of Sciences,Beijing 100049,China

1 引言

目標跟蹤是機器視覺領域一項重要的課題，并且有廣泛的應用場景，如機器人、視頻監控、智能交通等[1-4]。近年來，雖然隨著機器學習的引入，目標跟蹤技術有了明顯提升，但是依舊面臨很多挑戰，如尺度變化、光照變化、目標形變、目標遮擋等[5]。

基于檢測的目標跟蹤算法表現出良好的跟蹤性能，是近年來的主流跟蹤算法。這些算法通常將跟蹤過程看成一個分類問題，通過已有的視頻幀離線或在線訓練分類器，再用訓練好的分類器來判別下一幀目標位置。如核結構化輸出（Structured output tracking with kernel，Struck）[6]跟蹤算法，跟蹤-學習-檢測（Tracking-Learning-Detection，TLD）[7]跟蹤算法，多樣例學習（Multiple Instance Learning，MIL）[8]跟蹤算法等。這些算法的采樣方式一般為稀疏采樣，在跟蹤精度及計算效率上都有明顯不足。相關濾波器在目標檢測和識別中已有廣泛的應用，Bolme等[9]提出的一種最小平方誤差和輸出（Minimum Output Sum of Squared Error，MOSSE）跟蹤算法，首次將其應用到目標跟蹤領域并取得了很好效果。隨后Henriques等[10]提出基于核循環結構檢測跟蹤（Circulant Structure of tracking-by-detection with kernel，CSK）跟蹤算法，創新地采用循環結構編碼密集采樣并用核方法訓練正則化最小二乘（RLS）非線性分類器。之后又在核相關濾波（Kernelized Correlation Filter，KCF）[11]跟蹤算法中使用梯度方向直方圖（Histogram of Oriented Gradients，HOG）[12]特征對CSK進行改進。Danelljan等[13]提出的區分尺度空間（Discriminative Scale Space Tracker，DSST）跟蹤算法則是在MOSSE跟蹤算法的基礎上解決了跟蹤過程中目標尺度變化問題。

因此，本文首先在KCF跟蹤算法的基礎上借鑒DSST跟蹤算法來解決跟蹤過程中目標尺度變化問題，之后針對算法不能有效處理長時間跟蹤中遇到的目標大面積遮擋或丟失問題提出了一種再檢測方法，解決了目標跟蹤中丟失重捕問題，從而進一步提高了跟蹤算法的精確度與魯棒性。

2 KCF跟蹤算法改進

KCF跟蹤算法利用循環采樣來訓練分類器，這種密集采樣的方式明顯優于稀疏采樣的跟蹤算法，又因為將運算轉換到頻域進行，跟蹤速度也有了提升。但在跟蹤過程中跟蹤框無法隨著目標尺度自適應變化，在目標丟失后也無法捕獲目標重新進行跟蹤，從而導致跟蹤性能降低。

2.1 判別式相關濾波器

KCF跟蹤算法訓練位移濾波器的主要思想是學習一個判別式相關濾波器來對新一幀圖像目標定位。具體做法是從目標及其背景提取出一組灰度圖像塊x1，x2…，xt作為訓練樣本，其中每一個圖像塊都會對應一個目標輸出g1，g2…，gt，一般而言gj預期輸出函數為高斯函數，其峰值位于xj中心。本文在位移濾波器的基礎上增加了一個尺度濾波器，尺度濾波器也是一個判別式相關濾波器，最大的不同點是通過建立目標尺度金字塔來提取訓練樣本。兩個濾波器相互獨立，選用了不同的特征用來訓練。算法中使用脊回歸求得最優相關濾波器hj：

根據Parseval定理，將運算轉換到頻域：

其中 fj，gj和ht的大小均為 M×N，為復共軛矩陣。λ≥0是正則化項，可以用來防止過擬合。于是可以得到：

2.2 密集采樣

不難看出式（3）的計算量很大，因此也很大程度上影響了跟蹤算法的實時性。改進方法是對目標區域進行循環采樣即密集采樣，這樣不僅可以提高計算效率而且還可以提高跟蹤精度。區別于其他算法的稀疏采樣方式，相關濾波并不嚴格區分正負樣本，算法使用變換矩陣P來對目標圖像塊x進行循環移位。對于一維圖像，變換矩陣可以為：

變換后的圖像則構成循環矩陣：

循環矩陣有一個很好的特性，即無論x是什么形式，其循環矩陣X 都可表示成 X=Fdiag(x?)FH，代入式（3）可大大簡化計算。

2.3 濾波器響應

為了進一步簡化計算，本文對式（3）的分子Aj和分母Bj分別進行更新：

可以得到魯棒的近似結果，其中θ為學習率。因此，對于新一幀輸入圖像z，目標位置可以求解最大相關濾波器響應y得到：

2.4 再檢測

之前提到過KCF跟蹤算法在各項跟蹤性能指標均有很好表現，但是對目標丟失的場景無法實現有效跟蹤。那是因為KCF跟蹤算法采樣過程中并不明確區分正負樣本，訓練的分類器只是取置信值最大的點作為目標，所以，當目標被完全遮擋時采樣全為負樣本，導致訓練的分類器失去了判別目標與背景的能力，從而使得跟蹤失敗。針對這一問題，本文在KCF算法的基礎上，增加了一個支持向量機訓練分類器，當目標丟失時可以進行再檢測，從而實現跟蹤目標的丟失重捕。

支持向量機是定義在特征空間上間隔最大化的二分類模型[14-15]。其基本思想是求解能夠正確劃分訓練數據集并且幾何間隔最大的分離超平面。在機器視覺領域SVM常用來做識別及分類，訓練時通常從訓練圖像提取特征，然后用特征向量來表示圖像。當使用像素作為特征時，圖像按字典順序掃描以形成特征向量。給定N 列向量 xi∈Rd和類標簽SVM分類器將找到一個超平面滿足下式：

其中，上標T表示轉置，w和b表示超平面（w表示超平面的法線，b為偏置），εi為松弛變量，C＞0稱為懲罰參數，一般由應用問題決定，表示對誤分類的懲罰程度。

在改進算法中，使用了兩個閾值threshold1和threshold2。threshold1用來判斷目標的遮擋程度，實驗中取值為0.4，當置信值大于threshold1時，表示此幀目標未受到大面積遮擋，則這一幀圖像可以用來訓練SVM分類器即再檢測分類器。Threshold2則用來判斷是否需要進行再檢測，實驗中取值為0.2，當分類器響應小于threshold2時，表示檢測到目標的置信度不高，需要使用SVM分類器來進行再檢測。

3 改進算法流程

綜合前面的算法改進分析，在KCF跟蹤算法的基礎上，本文構造出改進的核相關濾波跟蹤算法流程如下所示：

基于SVM相關濾波目標跟蹤算法

1：參數初始化；

2：讀取第i幀圖片序列：

3：if i＞1：

8： 使用SVM分類器檢測目標。

9：根據式（6）和式（7）更新移位濾波器及尺度濾波器。

11：根據式（9）訓練SVM分類器。

12：返回第2步開始下一幀跟蹤。

4 實驗與分析

為了驗證本文算法的有效性，從文獻[5]中選用了10組視頻序列進行測試，這些視頻序列包含光照變化、尺度變化、目標遮擋、目標丟失、旋轉等問題（如表1所示）。在對比實驗中，本文選取了多個優秀跟蹤算法進行比較，包括Struck、TLD、MIL、KCF、DSST等。同時，將增加尺度濾波器的KCF算法（用KCF+S表示）也加入了對比實驗。實驗時利用作者論文中公布的代碼在同一實驗環境進行。

表1 視頻序列

4.1 實驗環境及評價指標

考慮到運行效率，本文程序采用MATLAB與C語言混編，實驗軟件平臺為Matlab R2014b，并且配置了Opencv3.0及VLFeat兩個庫文件。運行環境配置為Intel Core i7-4790 CPU，主頻3.6 GHz，4 GB內存。為了定量分析算法性能，實驗中使用了文獻[5]中的3個評價指標：中心位置誤差（Center Location Error，CLE）、距離精度（Distance Precision，DP）、重疊精度（Overlap Precision，OP）。CLE是跟蹤結果目標中心與人工標注的目標中心的歐氏距離，其值越小越好并以像素為單位。DP是CLE小于閾值（一般為20個像素）的幀數占視頻序列幀數的百分比。OP則是跟蹤得分：score=大于某一閾值（本文取0.5）的幀數占總跟蹤序列長度的百分比，其中，Bt表示第t幀跟蹤框，Bg表示真實標注跟蹤框，?表示重疊區域，?表示總覆蓋區域。

4.2 實驗結果及分析

實驗中，本文算法與其他優秀跟蹤算法對表1中的視頻序列進行測試，得到CLE、DP、OP、FPS取平均值，結果如表2所示。表中將最優的結果進行加粗處理，次優的則用下劃線標出。

表2 測試結果

從表2可以看出，本文算法相對其他算法在3個評價指標上均是最優。對比KCF跟蹤算法，CLE平均減少了11.1 pixel，DP平均增加了7.8%，OP平均增加了9.7%，改進效果明顯。但是由于引入了尺度濾波器與再檢測分類器，勢必會增加運算復雜度，導致跟蹤速度變慢，但仍然能保證實時跟蹤。實驗還繪制了6組視頻的跟蹤精度曲線（DP曲線），如圖1所示。

圖1 DP曲線

從表2的測試結果還可以看出，KCF跟蹤算法的CLE、DP兩個評價指標要略優于KCF+S跟蹤算法，說明KCF跟蹤算法的跟蹤精度較好。另一方面，KCF跟蹤算法的OP評價指標要略差于KCF+S跟蹤算法，不僅說明KCF+S跟蹤算法跟蹤框和標注框重疊率高，也說明KCF+S跟蹤算法對跟蹤中目標尺度變化確有改進作用。

本文方法是在KCF跟蹤算法的基礎上進行尺度變化及目標丟失問題的解決。由于尺度變化的改進是參考DSST跟蹤算法。因此，從圖1的DP曲線可以看到，對于dog1、fish、dudek三組主要挑戰為尺度變化、光照變化、部分遮擋等的視頻序列，本文算法與DSST跟蹤算法表現相近。然而，對于coke、lemming、tiger2這三組主要挑戰為目標丟失的視頻，本文方法的DP曲線明顯優于DSST跟蹤算法。這也說明本文方法不僅繼承了原有算法的優點，而且進行了有效而顯著的改進。

為了便于更加直觀的對比，圖2列出了部分幀的跟蹤結果。在實驗時可以觀察到coke視頻的第254～266幀，lemming視頻的第337～362幀以及suv視頻的第677～686幀均出現目標完全遮擋的情況。不難看出，本文方法在目標丟失并重新出現后能夠迅速找到目標位置進行跟蹤，因此在這些視頻序列的表現要優于其他跟蹤算法。由此說明本文算法具有再檢測功能，并且能夠改善算法跟蹤精度。

圖2 幾種算法跟蹤結果

5 結束語

本文在KCF跟蹤算法的基礎上，提出了一種改進的核相關濾波目標跟蹤算法。通過在原有算法的基礎上，增加了尺度濾波器及再檢測分類器，解決了KCF跟蹤算法尺度及目標丟失問題。在與其他幾種優秀跟蹤算法的比較實驗表明：本文方法在各項評價指標中表現優異，并且對光照變化、尺度變化、旋轉等問題有一定魯棒性，具有一定研究及應用價值。下一步工作將優化各個分類器性能、簡化運算，進一步提高算法跟蹤性能。

參考文獻：

[1]Chen Z，Hong Z，Tao D.An experimental survey on correlation filter-based tracking[J].arXiv preprint arXiv：1509.05520，2015.

[2]Smeulders A W M，Chu D M，Cucchiara R，et al.Visual tracking：An experimental survey[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36（7）：1442-1468.

[3]Yilmaz A，Javed O，Shah M.Object tracking：A survey[J].ACM Computing Surveys，2006，38（4）：81-93.

[4]牛長鋒，陳登峰，劉玉樹.基于SIFT特征和粒子濾波的目標跟蹤方法[J].機器人，2010，32（2）：241-247.

[5]Wu Y，Lim J，Yang M H.Object tracking benchmark[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2015，37（9）：1834-1848.

[6]Hare S，Saffari A，Torr P H S.Struck：Structured output tracking with kernels[C]//2011 IEEE International Conference on Computer Vision（ICCV），2011：263-270.

[7]Kalal Z，Mikolajczyk K，Matas J.Tracking-learning-detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（7）：1409-1422.

[8]Babenko B，Yang M H，Belongie S.Robust object tracking with online multiple instance learning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（8）：1619-1632.

[9]Bolme D S，Beveridge J R，Draper B A，et al.Visual object tracking using adaptive correlation filters[C]//2010 IEEE Conference on Computer Vision and Pattern Recognition（CVPR 2010），2010：2544-2550.

[10]Henriques J F，Caseiro R，Martins P，et al.Exploiting the circulant structure of tracking-by-detection with kernels[C]//European Conference on Computer Vision（ECCV 2012）.Berlin Heidelberg：Springer，2012：702-715.

[11]Henriques J F，Caseiro R，Martins P，et al.High-speed tracking with kernelized correlation filters[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2015，37（3）：583-596.

[12]Dalal N，Triggs B.Histograms of oriented gradients for human detection[C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR 2005），2005：886-893.

[13]Danelljan M，H?ger G，Khan F，et al.Accurate scale estimation for robust visual tracking[C]//Proceedings of British Machine Vision Conference，Nottingham，September 1-5，2014.

[14]Rodriguez A，Boddeti V N，Kumar B V，et al.Maximum margin correlation filter：A new approach for localization and classification.[J].IEEE Transactions on Image Processing，2013，22（2）：631-643.

[15]Rodriguezperez A F.Maximum margin correlation filters[D].Carnegie Mellon University，2012.