基于點軌跡的核相關濾波器跟蹤算法

呂韻秋，劉凱，程飛

1 引言

目標跟蹤技術是計算機視覺領域的重要研究方向之一，其目的是在給定第一幀目標位置的基礎上自動預測后續幀中的目標位置。該技術在行為檢測、視頻監控、智能交通等領域具有廣泛的應用。在空間信息網絡技術中，跟蹤算法具有重要的作用。近年來，隨著單目標跟蹤技術的不斷發展，許多算法已經能夠在輕度遮擋和慢速運動的簡單場景中對目標進行穩定的跟蹤。然而，由于背景雜亂、嚴重遮擋和目標形變的影響，復雜場景中的目標跟蹤仍然是一個復雜且極具挑戰性的任務。

跟蹤算法通常基于其外觀模型分為生成算法和判別算法。生成算法通過對當前幀中目標區域進行建模，在下一幀中搜索與該外觀模型最相似的區域作為預測位置。增量視覺[1]（IVT, incremental visual tracking）跟蹤方法是經典的生成式算法之一，該算法利用增廣子空間模型減小外觀變化的影響。在1l跟蹤器中[2]，該算法利用目標模板和碎片模板的稀疏線性組合對目標進行建模。為減少計算量，Li等[3]使用正交追蹤算法對1l跟蹤器進行加速。判別算法將跟蹤問題轉化為一個二分類問題，以目標區域為正樣本，背景區域為負樣本，使用機器學習方法訓練分類器，在下一幀中使用訓練好的分類器找到最優區域。在線多示例學習（MIL, multiple instance learning）跟蹤方法中，Babenko等[4]提出將多個樣本放入正、負樣本集中，使用自提升集成學習方法（boosting）進行訓練。跟蹤—學習—檢測[5]（TLD, tracking-learning-detection）跟蹤方法將跟蹤算法和檢測算法結合并通過在線學習機制對二者進行更新。Hare等[6]使用在線結構化輸出支持向量機自適應地跟蹤目標。

最近，基于相關濾波器的跟蹤方法引起了人們的廣泛關注。該方法將卷積運算轉換為傅里葉域上的乘法運算，從而減少了計算量。Bolme等[7]設計了一個最小平方誤差和輸出自適應相關濾波器，并在每一幀中用所訓練的濾波器對目標外觀進行編碼。在基于循環矩陣結構（CSK, circulant structure kernel）的跟蹤算法中，Henriques等[8]對給定的圖像塊進行循環移位得到訓練樣本，并利用這些樣本在核空間中訓練了一個相關濾波器。核相關濾波器[9]（KCF, kernelized correlation filter）跟蹤算法將CSK中使用的光線強度特征替換為HOG特征，增強了模型的可靠性。

然而，一旦目標發生遮擋，外觀模型受到噪聲干擾，大多數算法的跟蹤可能會發生漂移甚至丟失目標。針對該問題，國內外學者提出了很多解決方法。子塊匹配法[10-12]將目標分成若干個子塊分別進行跟蹤，該方法能夠對未被遮擋的部分實現有效跟蹤，但是子塊的大小和數量會對跟蹤效果產生嚴重影響。軌跡預測法[13-14]利用目標位置、速度、加速度等信息預測目標在下一幀的位置。但當目標做無規則運動時，跟蹤效果會出現較大滑坡。貝葉斯預測法[15]使用粒子濾波并將跟蹤問題轉化為一個貝葉斯后驗概率最大化問題。但在長時間跟蹤中，隨著迭代次數增加，粒子群很可能出現退化現象，嚴重影響跟蹤效果。

本文針對目標跟蹤過程中的遮擋問題，提出一種基于點軌跡的核相關濾波跟蹤算法。點軌跡是指利用密集光流在視頻序列中追蹤稀疏采樣點形成的運動軌跡，能夠有效地反映物體的運動特征。從長期看，當遮擋發生時，目標與遮擋物的運動方向和速度不同。因此，該算法通過分析視頻中采樣點的長期運動軌跡，將每一幀中的點軌跡標記為目標或背景，從而預測目標在當前幀的狀態并判斷目標是否發生了遮擋或漂移。由于KCF跟蹤算法具有較好的實時性并且能夠解決一部分遮擋問題，因此，所提算法基于 KCF算法對遮擋問題進行研究。所提算法主要分為3個步驟：1)使用 KCF作為預跟蹤器預測目標大致位置；2)對預測位置周圍區域的點軌跡進行分類，判斷目標框中前景點是否占多數，如果在目標框內的點大部分為背景點，則認為目標發生遮擋；3)如果目標漂移或被嚴重遮擋，使用顏色直方圖和巴氏距離重新檢測目標位置。實驗結果表明，所提算法能夠取得良好的效果，并且對于跟蹤過程中的漂移、遮擋、目標形變等問題具有較強的頑健性。

2 KCF算法

由于 KCF算法具有較高的效率和準確率，因此所提算法將其作為預跟蹤器，得到目標的大致位置并確定目標的搜索區域。本節簡單介紹了 KCF跟蹤算法，讀者可參考文獻[9]進一步了解該方法的實現細節。

KCF算法的主要思路是根據當前幀和之前幀的信息訓練出一個濾波器w，然后與下一幀進行相關性計算，將響應值最大的樣本作為跟蹤結果。在當前幀中，以目標位置為中心，取一個訓練圖像塊x，其尺寸為M×N。對該圖像塊進行循環移位得到訓練樣本 xm,n,m,n ∈ {0 ,1,… ,M ? 1 } × { 0 ,1,… ,N ?1}。將訓練樣本 xm,n與濾波器w進行相關性計算，使用嶺回歸方法最小化相關性計算結果和輸出 y的平方誤差，對w進行訓練，有

其中，λ為歸一化參數， y (m,n)為 xm,n的標簽值，φ(?)為映射函數，該函數將樣本映射到一個希爾伯特空間中，使其在該空間內線性可分。φ(?)的具體形式未知，但能夠用核函數K計算其點積φ′( x ) φ ( x ′ ) = K(x,x′)。輸出y是服從高斯分布的，其在訓練圖像塊上取值為 1，而在其他移位圖像塊中的取值逐漸減小為0。

其中，F(?)和F?1(?)分別表示離散傅里葉變換（DFT）及其逆變換，y為標簽集合。文獻[9]中定理描述如下：給定循環矩陣 C ( x)，如果一個核函數對于任意排列矩陣B滿足 K ( x,x′ ) = K ( B x, B x′)，則其對應的核矩陣是循環矩陣。因此，如果核函數滿足該定理，式(2)可寫為

其中，kxx為核函數 K = C ( kxx)的第一行。

對于一個新的尺寸為M×N圖像塊z，可由式(4)計算其置信圖為

其中，⊙表示元素與元素之間的乘積，kxz為K = C ( kxz)的第一行。將式(4)中的響應值 f?(z)變換到空間域中，則響應值 f (z)最大的樣本為KCF算法得到的跟蹤結果。

3 基于點軌跡的核相關濾波器算法

本節主要介紹了基于點軌跡的遮擋處理算法。該算法首先將核相關濾波器跟蹤作為預跟蹤器得到目標的預測位置，在該位置周圍生成點軌跡；然后使用譜聚類方法對點軌跡聚類，對過分割所產生的多余的類進行合并；最終將點軌跡標記為目標類和背景類。根據預測目標框中2類點軌跡的分布情況，判斷目標被遮擋的情況。記錄未發生遮擋時的目標樣本作為模板，如果發生遮擋，取候選樣本，計算候選樣本與模板之間的相似度，將響應值最大的樣本作為最終跟蹤結果。

3.1 點軌跡生成

通過對視頻序列進行分析，可將遮擋的情況分為以下2種：目標與遮擋物的方向相反；目標與遮擋物的方向相同但速度不同，從而相互靠近導致遮擋發生。因此，從長期角度看，目標與遮擋物的運動方向或運動速度不同，通過分析目標及其周圍物體像素點的長期運動軌跡，能夠判斷目標是否被遮擋。

為了得到物體的長期運動軌跡，需要對物體中每個像素點的歷史運動規律進行分析。點軌跡利用光流方法對第一幀中生成的像素點進行跟蹤，從而在視頻序列中得到一條運動軌跡。點軌跡的質量依賴于光流方法的準確性，因此，算法選取效果較好的大位移光流法（LDOF, large displacement optical flow）[16]和 Lucas-Kanade方法[17]用于測試視頻序列。由于算法的計算復雜度與點軌跡的數量成正比，則對搜索區域中所有的像素點進行跟蹤會降低算法的速度，為了減少計算量，點軌跡在以預跟蹤器結果為中心的取樣區域中進行下采樣。取下采樣因子為c，在原始圖像中使用尺寸為cc×的窗口進行滑動，在每個窗口中隨機選取一個像素點，則對于一個尺寸為MN×的圖像，樣本的數量由MN×減少到了。由于物體外觀變化或光流誤差等原因，點軌跡在向后續幀傳遞的過程中有可能由一個物體漂移到其他物體上，因此，需要清除這些點軌跡，避免一個點軌跡同時具有目標和遮擋物的特征，從而導致標記錯誤。在非遮擋情形下，像素點的前向和反向光流的方向相反，并且當后一幀的點軌跡反向映射到前一幀時，應落在前一幀對應像素點的周圍區域內。因此，可以通過定義一致性條件檢測點軌跡是否發生漂移，一致性條件由式(5)和式(6)給出。

其中，tω表示點的前向流向量，?tω表示后向流向量。式(6)右側為算法所設置的容忍區間，允許點軌跡在傳遞過程中出現一定的誤差，該值的大小與光流大小呈線性關系。如果不滿足式(5)和式(6)定義的一致性條件，則認為點軌跡在該幀中發生了漂移。

前向—反向光流匹配準則示意如圖1所示，點a和點b表示點軌跡在第t幀和第 1t+幀的位置，點a′表示點a在第 1t+幀中的映射。箭頭①和箭頭②分別表示前向光流向量和反向光流向量，箭頭③和箭頭④分別表示點軌跡的前向和反向運動過程，箭頭⑤表示漂移情況下點軌跡的反向運動過程。當點軌跡未發生漂移時，反向光流將第 1t+幀中的點b映射到灰色區域所表示的容忍區間中，如箭頭④所示；若發生漂移，該點被反向光流映射到了圖 1左側容忍區間外的點c上，如箭頭⑤所示。由箭頭①和箭頭②可得，當點軌跡未發生漂移時，前向流和反向流向量方向相反。因此，當反向流終點不在容忍區間內或方向與前向流向量相同時，點軌跡被終止。

圖1 前向—反向光流匹配準則示意

生成點軌跡的步驟如下：若當前幀為第一幀，以核相關濾波器算法生成的初始目標框為中心，取該目標框2倍大小的取樣區域，在該取樣區域進行下采樣得到點軌跡樣本；若當前幀不是第一幀，判斷點軌跡是否滿足一致性條件，剔除不滿足式(5)和式(6)的點軌跡，使用與第一幀中相同的方法選擇取樣區域，保留未發生漂移的點軌跡并在取樣區域的空白部分采集新的點軌跡樣本。

3.2 點軌跡標記

本節采用譜聚類（spectral clustering）[18]的方法對點軌跡進行聚類。譜聚類方法是近年來流行的聚類方法之一，與K均值（K-means）和混合高斯模型（GMM,Gaussian mixture model）等傳統方法相比具有更好的聚類效果和較低的計算復雜度。

譜聚類方法是一種基于圖論的聚類方法，該方法將每個數據點作為節點，連接節點的線作為邊，從而構造完全圖。其中，每條邊的權重表示數據點之間的相似度，則該完全圖的鄰接矩陣即數據的相似度矩陣。為了降低對不規則誤差數據的敏感度，利用該相似度矩陣的譜（即矩陣的特征值）對數據進行降維，再使用K均值算法進行聚類。

首先，需要定義一個相似度矩陣。當2個點軌跡的運動規律越相同時，表示它們之間的相似度越高。為了更加有效地區分物體，對于軌跡i和軌跡j，應考慮二者之間運動規律相差最大的時刻。因此，軌跡i和軌跡j之間的距離定義為

由于相似度需要包含點軌跡的長期運動信息，定義軌跡i和軌跡j在T幀間的平均距離和為

對于軌跡i和軌跡j，二者之間的相似度與它們之間的距離成反比，定義為

其中，α是尺度參數，為了防止式(10)中的相似度變得過小，通常取0.1α=。由式(10)得到一個nn×的相似性矩陣 S，n為點軌跡的個數。根據該相似性矩陣S，使用譜聚類方法標記生成的點軌跡。

光流向量的灰度表示如圖2所示，圖2(a)為測試視頻序列中的一幀，圖2(b)為該幀中光流向量的灰度表示，其中左邊為光流在x方向上分量的可視化灰度圖，右邊為在y方向上分量的可視化灰度圖。由圖2(b)可以看出，目標位置與周圍物體的灰度值具有明顯的對比，說明該位置與周圍位置的光流向量具有較為明顯的差異。圖2(b)中的橫、縱坐標分別表示圖中像素點對應位置的橫、縱坐標，右側圖例中的坐標表示圖中顏色對應的灰度值級別。

3.3 合并過分割的類

如果目標與遮擋物上的點軌跡運動差異較大，由3.2節中定義的相似度矩陣，根據物體的長期運動特征，譜聚類方法能夠成功地將點軌跡分為目標類和背景類。然而，當二者運動差異較小或目標及周圍物體的運動情況較為復雜時，可能會造成對點軌跡的過分割。此時，需要對具有相似特征的類進行進一步合并，最終將屬于目標的點軌跡合并為一類，屬于背景的點軌跡合并為一類。合并過分割類的過程示意如圖3所示。

圖2 光流向量的灰度表示

圖3 合并過分割類的過程示意

假設最終的類別數為k，Ochs等[20]定義了一個包含空間約束項的能量方程，并且通過最小化該能量方程確定k的大小。設λi為聚類過程中相似度矩陣的第i個特征值，是第i個特征向量的第A個元素， uA是所有特征向量的第A個元素組成的向量。上標 A對應一條單獨的點軌跡。設N ( A)為點軌跡A在空間鄰域中的點軌跡集合。初始化聚類個數K，最小化式(11)得到聚類結果πA∈ { 1,… ,K }為

其中，范數定義為

式(11)中，第一項為一元項，kμ為類別k的質心。第二項為對多余類別的懲罰項。使用克羅內克積定義，當軌跡A和B被歸為不同的類時，該值為0，否則，該值為1。因此，當2個軌跡被歸為不同類時，使用類間特征向量差的倒數進行懲罰。當相似性較大的區域被分割時，該項的值較大，而將不連續的區域分割開所產生的懲罰值較小。ν

最小化式(11)是一個較為復雜的問題，因為該式有很多局部最小值。Brox等[19]將該問題轉化為一個質心未知的多標簽馬爾可夫隨機場（MRF,Markov random field）問題，該問題解決方法的具體描述可參考文獻[20]。

3.4 算法步驟

本節主要對所提算法進行詳細的闡述。首先，如果當前幀為視頻序列的第一幀，在初始目標框box1周圍取采樣區域，并在該采樣區域中的像素點進行下采樣，得到初始點軌跡樣本；否則，將核相為平衡參數，通常取關濾波器跟蹤算法作為預跟蹤器得到目標的預測邊界框tbox，利用光流方法得到由前一幀傳遞的點軌跡，清除漂移的點軌跡樣本并在采樣區域內產生新的樣本。然后，根據式(10)定義的相似度矩陣，利用譜聚類方法對點軌跡進行標記，將其劃分到不同的類別中，并通過最小化式(11)所定義的能量函數合并過分割的類，最終實現對目標和背景的標記。根據預測邊界框tbox中目標點軌跡和背景點軌跡的分布情況，可以判斷預跟蹤器的結果是否偏移目標，從而判斷遮擋是否發生。當不發生遮擋或目標被輕度遮擋時，繼續使用核相關濾波器進行跟蹤；當目標被嚴重遮擋時，利用前一幀結果訓練濾波器，并且不更新預跟蹤器參數；當目標長期發生漂移或被遮擋時，則啟用重檢測機制對目標狀態進行檢測。重檢測機制的工作原理描述如下：記錄未遮擋時的目標跟蹤框作為模板，以當前幀的預測邊界框tbox為中心，取2倍大小的區域作為候選樣本采樣區域，并在該區域中利用滑動窗口采集候選樣本，利用巴氏距離和顏色直方圖計算候選樣本與目標模板之間的相似度，最終將響應值最大的樣本作為新的目標跟蹤框。本文所提算法流程如下。

Step1 在第一幀中，訓練回歸方程 ()fz，記錄1box為目標模板，取點軌跡樣本。

Step2 在第t幀中，取點軌跡樣本并標記點軌跡，分別計算目標框中正、負樣本數所占比例 Ppos和Pneg，計算目標框 b oxt中正樣本外接矩形 Prect。

Step3 如果 Pneg＜ 6 0%，則認為不發生遮擋或輕度遮擋，更新KCF參數，否則，轉到Step4。如果Ppos＞ 7 0%，將該幀的結果作為目標模板，用于重檢測。如果 Prect＜ 6 0%，則認為目標發生漂移，重新檢測目標并更新 b oxt。

Step4 如果 Pneg＞ 6 0%，則將目標狀態判定為嚴重遮擋，不更新 KCF參數；若上一幀狀態也是嚴重遮擋，則對目標進行重檢測并更新 b oxt。

Step5 若視頻未結束， t = t+ 1，轉到Step2。

4 實驗分析

本節使用Wu等[21]提出的流行目標跟蹤測試平臺 OTB測試集對算法進行測試，并且重點分析了算法在遮擋、快速運動和目標形變等復雜場景中的跟蹤效果。算法的測試平臺為Windows 7的64位操作系統，硬件配置為3.0 GHz主頻的Intel CPU以及8 GB的內存。此外，本節還將本文所提算法與一些跟蹤方法進行了比較。

在本文所提算法執行之前，需要對參數進行設置。為使回歸方程更加穩定，式(1)中的嶺回歸歸一化因子設置為 λ = 1 0?4。KCF算法中采樣區域的尺寸取目標尺寸的2.5倍，使算法能夠取得更多的負樣本。為減少計算量，3.1節中的下采樣因子取為6，式(10)中的歸一化因子設置為α=0.1。

本文主要采用3個標準對跟蹤效果進行評價：1)中心位置誤差，定義為真實目標框和估計目標框中心的歐氏距離，圖4展示了各個算法中心誤差的結果；2)距離準確度，定義為估計跟蹤結果在給定真實目標框中幀數所占的百分比；3)成功率，定義為，其中，TROI是估計目標框，ROIG是真實目標框。如果該得分大于0.5，則認為跟蹤成功。準確率與成功率的實驗結果如表1所示。

本文所提算法在大多數視頻序列中取得了較好的效果，根據上述3個標準可以看出，該算法能夠成功地解決遮擋問題。圖5直觀地展示了各個算法在不同視頻序列中的跟蹤目標框。在 Coke序列中，物體被周圍葉片遮擋，而 KCF、DFT和 TLD算法的跟蹤結果發生了漂移。例如，在第255幀到第263幀中，目標幾乎被全部遮擋，直到269幀才完全出現。雖然遮擋時間較長且遮擋程度嚴重，本文算法仍可以成功地對目標進行定位。由于在Coke序列中所跟蹤的目標相對遮擋物運動速度較快，因此，通過點軌跡聚類能夠成功地將目標從背景中分離，從而可以準確地判斷遮擋是否發生。在Girl序列中，目標為一個女孩的面部，而在第412幀中出現一個另一人物并逐漸靠近目標，并從453幀開始對目標進行了較長時間的遮擋，直至467幀目標才完全出現。于是 KCF將跟蹤目標轉移為該人物，跟蹤失敗。由中心誤差圖可以看出，本文所提算法在Girl序列中的中心誤差與KCF、DFT和TLD算法相比較小。由于遮擋物與目標人物的運動規律不同，所提算法能夠準確地將二者區分開。

另外，該算法也能夠很好地解決漂移問題。在Singer1序列中，由于目標外觀及尺寸變化，KCF跟蹤的結果發生了嚴重的漂移。但是，由圖5可以看出，該算法始終能夠跟蹤目標。由表1可知，該算法的成功率和準確率與其他算法相比是最優的。表1中在統計準確率時允許目標位置與真實位置有20px的誤差。

圖4 中心誤差曲線

表1 4種算法在測試序列上成功率和準確率比較

該算法在空間信息網絡中能夠進行應用，為了驗證其在遙感視頻跟蹤目標的有效性，本文使用無人機拍攝的場景對目標進行跟蹤[22]，跟蹤效果如圖6所示。在數據集Car9中，第257幀到第278幀被廣告牌遮擋。由圖6可以看出，本文所提算法能夠在遮擋結束后成功定位目標。

以上實驗證明了本文所提算法能夠有效地解決遮擋、漂移、光照變化、目標形變等問題。但是，根據表2可得，該算法與KCF算法相比速度較慢，在后續工作中，可根據文獻[23-26]，利用GPU對本文所提算法的實時性進行優化。另外，由于點軌跡是基于光流方法選取的，當攝像機抖動劇烈時，本文所提算法無法準確地判斷遮擋；當目標窗口尺寸太小時，基于顏色直方圖的重檢測機制無法有效地檢測目標位置。針對這些問題，需要對本文所提算法做進一步的改進。

表2 2種算法在測試視頻中的幀率（單位為幀·秒-1）

5 結束語

圖5 目標跟蹤框示意

圖6 算法在遙感視頻數據集Car9序列中的跟蹤結果

本文針對視頻跟蹤中的遮擋問題提出了一種創新的跟蹤算法。該算法的主要目的是判斷跟蹤過程中遮擋問題的發生并在遮擋結束時重新定位目標。首先使用核相關濾波器跟蹤作為預跟蹤器確定目標的大致位置和搜索區域。然后通過分析該位置周圍物體的運動規律，利用點軌跡分割對目標和背景進行標記，并根據標記結果判斷是否發生遮擋。當目標受到嚴重遮擋時，選取與未遮擋目標模板相似度最大的候選樣本作為跟蹤的最終結果。實驗結果證明，所提算法對于遮擋和漂移具有較強的頑健性。