基于MeanShift的跟蹤學習檢測目標跟蹤改進算法

周愛軍， 張 松， 杜宇人

（1.南京師范大學泰州學院，江蘇泰州225300；2.揚州大學信息工程學院，江蘇揚州225000）

0 引 言

運動目標跟蹤集成了人工智能、圖像處理、模式識別以及神經網絡等計算機領域的復雜技術［1-2］，是當前計算機視覺領域中研究的熱門課題，廣泛應用于身份識別、車輛導航、視頻檢索、人機交互、視頻監控以及工業安防等領域。目標跟蹤可以理解為對視頻序列的每幀圖像進行分析和處理，找到目標尺度［3］、顏色［4］、形狀［5］和模式［6］等信息，通過前后幀圖像的匹配［7-8］計算出目標的運動軌跡。

當前主要的跟蹤算法有卡爾曼濾波［9］、Cam shift［10］、粒子濾波［11］和SVM［12］等。當目標跟蹤過程中存在陰影、遮擋、實時性等問題時，傳統算法缺少檢測和修復跟蹤偏差相結合模塊，只能針對特定問題進行處理，并且只能在較短的時間內達到較好的跟蹤效果。當目標初始化后，這些算法都是通過不同規則預測目標位置，當遇到遮擋和光照的變化時，就可能產生跟蹤漂移現象，隨著長時間的漂移累加最終導致目標丟失。

跟蹤學習檢測（Tracking Learning Detection，TLD）由Kalal提出，在單目標長時間跟蹤中具有很大優勢。與傳統算法相比，該算法引入了在線學習機制，找出每1 幀圖像中分類出現錯誤的樣本進行糾正，并及時反饋給訓練集，更新分類器。這種算法由于將跟蹤、學習和檢測相結合，在學習過程中持續更新目標模板參數，所以具有優秀的魯棒性。本文提出了一種基于MeanShift的TLD目標跟蹤算法，通過TLD 跟蹤框的置信度來合理選擇MeanShift跟蹤算法迭代起始點，提高算法抗遮擋能力。在TLD跟蹤模塊用Susan角點代替均勻采樣點，減少計算時間，提高了跟蹤的實時性。

1 TLD算法

相對于傳統的目標跟蹤算法，TLD 將跟蹤和檢測結合起來，并且引用了在線學習機制，使其在跟蹤被遮擋目標和目標形變等情況下更具魯棒性。它采用半監督的學習機制，利用少量監督數據和海量無監督數據相結合，大大提高算法的性能。TLD包括跟蹤、檢測與學習模塊，算法框架圖如圖1 所示。

圖1 TLD算法框架

（1）跟蹤模塊。TLD 跟蹤器是在Median Tracker基礎上增加錯誤檢測功能的新算法。跟蹤模塊采用了LK光流法［13-14］，且增加了前向和后向誤差檢測功能。在目標區域利用Grid 采樣獲得100 個樣本點，用LK光流法對這些點進行2 次跟蹤，然后計算對應的NCC相關系數，并求得中值。最后根據這些可靠跟蹤點來更新目標跟蹤框。

Kalal的Forward-Backward 錯誤檢測算法需要2次利用LK光流法。如圖2 所示，點①跟蹤成功；點②經過2 次光流后未到達原來的點，說明點②跟蹤失敗。

圖2 中值流法跟蹤示意圖

實際情況中，2 次光流后不會剛好回到原來特征點，存在一定的偏差。假設2 次光流的偏差小于設定的閾值，則判定跟蹤成功。2 次光流的差值表示為

式中：p″＝LK（LK（p）），為2 次光流后的點。

TLD算法的跟蹤模塊利用金字塔LK 光流跟蹤和前向后向誤差檢測計算出跟蹤誤差，去除誤差較大的樣本點。最終通過可靠的特征點計算出當前目標的新位置。該算法稱作中值流跟蹤法，算法實現過程如圖3 所示。

圖3 中值流跟蹤算法的實現

（2）檢測模塊。TLD 檢測模塊由方差分類器、級聯分類器和最近鄰分類器組成。它是通過滑動窗口檢測圖像序列。當跟蹤過程中出現目標丟失，跟蹤器無法從錯誤中恢復，這時需要利用檢測器進行目標檢測，找出跟蹤丟失的目標。當檢測窗口被3 個檢測器接受可判斷為目標窗口。TLD 檢測模塊流程圖如圖4所示。

將目標區域、候選區域的方差進行比較，并將方差小于原始目標方差一半的區域過濾掉，方差計算式為

圖4 檢測模塊流程圖

式中：D（x）表示灰度方差；E（x2）為圖像塊灰度平方的均值；E2（x）為灰度均值的平方。利用方差檢測器將圖像中不可能成為前景目標的區域濾除。

TLD級聯分類器就是對比一些像素的亮度值，對每個檢測窗口計算其概率PPOS，滿足PPOS＞0.5 才能被接受。

通過方差檢測器和級聯檢測器的窗口最后需要通過最近鄰檢測器的篩選，選擇與上1 幀目標相似度高的為最后的檢測結果。這兩個圖像塊之間的相似性度量為

（3）學習模塊。TLD學習模塊應用半監督學習方法，使用P-N學習的方法對檢測器中的每1 幀進行估計，利用P專家找出錯誤的負樣本，N專家找出錯誤的正樣本。把結果反饋給訓練集，從而更新分類器。這樣就可以不斷在線更新學習。

2 基于MeanShift的TLD跟蹤算法

2.1 MeanShift算法原理

假設給定d 維空間Rd中n 個樣本點xi（i ＝1，2，…，n）。在x點的MeanShift向量的基本形式定義為

式中：k是落入Sh區域內的所有樣本點的個數；Sh是一個高維球區域，半徑為h。滿足以下關系的y 點的集合

采樣點平均偏移量常用MeanShift向量表示，模板匹配時往樣本分布占比多的區域迭代。一般而言，Sh中與x越靠近的樣本點，其與x 周圍的統計特征關聯越大，所以引入核函數，并根據每個樣本點位置不同賦予其對應的權值，擴展的MeanShift向量表示為

式中：G（x）是核函數，一般選擇高斯核函數；wi為樣本點的權值。對于樣本空間中某一點z的概率密度可由核概率密度通過下式進行估計：

式中，k（x）表示核函數K（x）的輪廓函數。

MeanShift算法是一個不斷迭代直至達到最佳位置的過程。如果假設初始點為x，允許的誤差為ε，則MeanShift算法的具體步驟：①計算Mh（x）；②把Mh（x）賦給x；③如果mh（x）-x ＜ε，結束循環，否則執行①。

2.2 基于MeanShift的TLD跟蹤算法

首先對MeanShift 搭建模型和參數選擇。選擇RGB空間計算目標模板的直方圖，目標模板的像素個數用N 表示，選擇Epanechikov 核函數計算其核顏色直方圖，則目標模板的概率密度估計可以表示為

根據上1 幀的跟蹤結果確定當前幀的搜索中心坐標y。以y為中心的區域中的每個像素用｛xi，i ＝1，2，…，n｝表示，則候選模板的概率密度估計為

采用式（11）求Bahttacharyya（BH）系數，計算待匹配目標和待選模板間的相似度，BH系數越大，相似度越高

在迭代搜索候選目標的過程中，常用的偏移量小于閾值。實際應用中，迭代次數更多用來控制搜索，通常情況下擇迭代次數設為20。如果只用迭代，只能適應單一尺度的目標，不能適應目標的尺度變化。若前1 幀核函數帶寬hp，則可以分別利用以下3 種核函數（h ＝hp，h ＝hp＋Δh，h ＝hp-Δh）來迭代搜索3 次。將BH系數最大的帶寬作為最優帶寬。為避免過度調節，將當前幀中的帶寬修正

式中：χ是一個調節參數，經過試驗測試本文選擇0.1。

基于MeanShift的TLD跟蹤算法步驟如下：

（1）讀入視頻幀，利用鼠標手動標定待跟蹤目標，然后分別初始化TLD和MeanShift跟蹤器。

（2）分別啟動TLD 和MeanShift 跟蹤器。通過TLD跟蹤器預估目標位置，判斷其置信度。當置信度較高時，以TLD 輸出的目標中心位置作為MeanShift跟蹤算法的迭代起點；當置信度低時，將前1 幀中目標跟蹤框的中心位置作為跟蹤的迭代開始點。

（3）將最大迭代次數設為20，在每1 次迭代搜索中，移動搜索中心位置至相似度大的中心位置。

（4）為了進行自適應尺度變化，動態調整Mean Shift跟蹤的核函數半徑。利用相似度最大候選目標的核函數半徑求解最后的候選目標尺度。

（5）將MeanShift輸出的目標框作為最終的跟蹤預測框。

（6）判斷它是否是最后1 幀。如果不是，返回步驟（2）判斷新的1 幀；如果是，循環結束。

3 算法改進

基于MeanShift 的TLD 目標跟蹤算法計算量大，無法實現跟蹤的實時性。本文在TLD 算法的跟蹤模塊引入Susan角點，將Susan算法與TLD算法結合，用角點替換原均勻采樣點，大大減少了采樣點數量，降低了跟蹤器的運行時間。

3.1 Susan角點

Susan 算法通過圓形模板遍歷圖像，選擇圓形模板圓心作為核心點，對比模板內像素灰度值和核心點灰度值［15］，表示為

式中：I（x，y）是圓形模板中像素點的灰度值（核心像素點除外）；I（x0，y0）表示圓形模板核心像素點灰度值；C（x0，y0）為相似比較函數；t是設定的閾值。圓形模板中的像素點是否在USAN 區域，由該像素點的C值決定。模板中所有符合條件的像素組成核相似區。一般情況選擇37 像素的模板，Susan 圓形模板如圖5所示。

如圖6 所示，當模板位于a 處，USAN 面積和模板面積一樣；當模板往直線邊沿挪動過程中，USAN 區域面積逐漸減小；當窗口模板核心點為c 和d 處，USAN區域面積等于模板面積的1／2；當模板進入b 處，USAN區域又會慢慢變大。當模板繼續移動，到達圖6中的h所示目標區域，此時USAN區域面積達到最大。當模板核心點到達角點時（如圖6 中的e，f，g），此時USAN區域面積略等于模板面積1／4，這時USAN面積最小。

USAN區域面積表示圖像局部特征強度。面積越小，核心點越有可能是角點，像素點處的USAN區域面積可用下式計算：

式中，n（x0，y0）的值表示USAN區域的面積。

對比每個像素點的USAN 值和幾何閾值g，通過下式計算當前像素點的初始響應函數值。

式中：g可根據需要動態調整，不同g 值，Susan 算子具有不同檢測結果。通常角點檢測中g ＝0.5Amax（Amax對應USAN最大面積，通常由模板大小決定，大多數情況下Amax＝37）。滿足R響應的像素點作為候選角點，在此基礎上利用非極大值抑制確定其是否為角點。

Susan算法的具體步驟如下：①利用圓形模板遍歷整個圖像，判斷USAN區域；②計算核心點USAN面積值；③用式（15）計算角點初始響應函數；④計算待選所有角點的非極大值的抑制。

圖5 Susan圓形模板

圖6 Susan特征檢測原理

3.2 算法改進

原TLD算法的跟蹤模塊中均勻采樣的100 個樣本點集有很多會成為無用樣本點，這樣不僅會導致跟蹤器的漂移，而且還會造成大量的計算量。本文為了解決均勻采樣隨機產生的特征點無法精確描述跟蹤目標，將Susan算法與TLD算法相結合，利用Susan 算法獲得的角點作為跟蹤點，舍棄原Grid 采樣點，大大提高了跟蹤的魯棒性。改良的跟蹤模塊如圖7 所示。

圖7 改良的跟蹤模塊示意圖

4 實驗分析

本文實驗硬件配置：Core i7 ＠ 2.8 GHz，8 GB 內存，軟件環境為：Visual Studio2012 和Matlab2012a，Opencv2.4.9。

4.1 跟蹤穩定性

實驗中跟蹤器部分采用MeanShift 算法迭代尋找最相似目標，并且在跟蹤器初始化時引入Susan 角點。學習模塊和檢測模塊與原TLD 保持一致，對公開的Motocross、David、Car視頻序列以及攝像頭獲取的視頻進行跟蹤測試。圖8 基于Motocross視頻序列，對比了本文算法和原TLD算法目標跟蹤的結果，紅色框標是原TLD算法，黃色框為本文算法跟蹤標記。

圖8 Motocross視頻序列的跟蹤

由圖8 可知，圖像在第96 幀和第291 幀分別發生了較大的尺度變化和遮擋，原TLD算法出現跟蹤目標丟失。由于本文引入MeanShift算法，所以具有較強的抗遮擋能力，同時加入了角點后的改進算法有效解決了目標尺度變化，所以能夠準確跟蹤目標。相比于原TLD算法，本文算法跟蹤成功率大大提升。表1 為TLD算法和本文算法分別對Motocross、David、Car序列進行多次反復實驗，最終取平均值作為統計結果。

表1 跟蹤結果對比

從表1 可看出，由于本文算法結合了MeanShift算法，有效地解決遮擋和尺度變化問題，跟蹤成功率進一步提高。

對發生遮擋的車輛進行跟蹤測試，視頻序列共159 幀，如圖9 所示。

圖9 遮擋車輛跟蹤結果

本文TLD算法能夠檢測更多穩定點數目，從而增強了跟蹤的魯棒性。當目標存在尺度變化、旋轉、遮擋、消失后重現等情況時，原TLD 算法產生跟蹤漂移甚至跟蹤失敗，本文算法能夠準確跟蹤目標。如圖9所示，紅色框標記為原TLD 算法跟蹤結果，黃色框標記是基于MeanShift的TLD算法跟蹤結果。在第10 幀黃色框和紅色框都初始化選定了紅色轎車（如圖9 中的a），在第30 ～53 幀之間出現遮擋后，原TLD算法跟蹤樣本點出現擴散漂移和跟蹤錯誤的情況；在第71 幀目標重新出現后，原TLD 算法沒能重新獲取目標，出現了跟蹤丟失。本文算法能夠重新捕捉到目標（結果如134 幀），成功跟蹤被遮擋的目標，具有很強的魯棒性。

對攝像頭獲取的視頻跟蹤測試結果如圖10 所示。圖10（a）為通過人工標定跟蹤目標對象，圖10（b）目標在外界條件良好的情況下的跟蹤結果，圖10（c）表示跟蹤過程遇到嚴重遮擋時的跟蹤效果。實驗表明，本文算法相對于原TLD算法具有較強的抗遮擋能力。

圖10 攝像頭采集目標遮擋下跟蹤測試

4.2 跟蹤實時性

由圖11 和表2 可以看出，由于均勻采樣產生了很多無用點，導致原TLD算法特征點丟失嚴重。雖然本文算法具有較少特征點，但經過LK光流跟蹤后，特征點基本保持不變。經過Susan算法得到的采樣點能夠有效表達目標特征，且大大減少跟蹤中的計算量。證明本文算法具有更快的跟蹤速度，滿足實時跟蹤要求。

圖11 特征點提取

表2 特征點數量的變化

本文選用跟蹤幀率的平均值作為衡量跟蹤實時性指標，通過視頻對Motocross、David、Car 視頻序列以及攝像頭輸出的視頻序列作為實驗樣本。各個視頻序列在不同跟蹤算法下的平均幀率見表3。

表3 不同算法處理速度的比較

通過表3 的比較可以看出：原TLD 算法和基于MeanShift的TLD算法的平均幀率基本相差不大。本文算法由于在跟蹤模塊中引入了角點算法，大大減少了計算量，所以實時性有明顯提高。上述視頻序列經過本文的改進算法實時性基本都有20%左右的提高。

5 結 語

針對跟蹤過程中目標被遮擋容易丟失，本文研究了一鐘將MeanShift 和TLD 結合的目標跟蹤改進算法。當TLD跟蹤框有較高的可信度時，以TLD輸出的目標中心位置作為MeanShift跟蹤算法的迭代起點；當置信度低時，將前1 幀中目標跟蹤框的中心位置作為跟蹤的迭代開始點。實驗結果表明，改進算法能實現穩定跟蹤。同時針對TLD 算法均勻采樣獲得的特征點中存在較多的無用點，在TLD跟蹤模塊引入了更具魯棒性的Susan角點作為目標的特征點。選擇角點后采用金字塔LK 光流法跟蹤，跟蹤過程中保留信息豐富的特征點，抑制了目標關鍵信息點集較少導致的跟蹤漂移。通過實驗表明，本文算法具備比較高的魯棒性和實時性。