目標跟蹤算法綜述

孟琭 楊旭

運動目標跟蹤一直以來都是一項具有挑戰性的工作,也是研究的熱點方向.現階段,隨著硬件設施的不斷完善和人工智能技術的快速發展,運動目標跟蹤技術越來越重要.目標跟蹤在現實生活中有很多應用,包括交通視頻監控、運動員比賽分析、智能人機交互[1]、跟蹤系統的設計[2]等.由于在目標跟蹤中存在形態變化、圖像分辨率低、背景復雜等情況,因此研究出一個性能優良的跟蹤器勢在必行.

早期的目標跟蹤算法主要是根據目標建模或者對目標特征進行跟蹤,主要的方法有:1)基于目標模型建模的方法:通過對目標外觀模型進行建模,然后在之后的幀中找到目標.例如,區域匹配、特征點跟蹤、基于主動輪廓的跟蹤算法、光流法等.最常用的是特征匹配法,首先提取目標特征,然后在后續的幀中找到最相似的特征進行目標定位,常用的特征有:SIFT[3]特征、SURF[4]特征、Harris角點[5]等.2)基于搜索的方法:隨著研究的深入,人們發現基于目標模型建模的方法[6]對整張圖片進行處理,實時性差.人們將預測算法加入跟蹤中,在預測值附近進行目標搜索,減少了搜索的范圍.常見一類的預測算法有Kalman[7]濾波、粒子濾波[8]方法.另一種減小搜索范圍的方法是內核方法:運用最速下降法的原理,向梯度下降方向對目標模板逐步迭代,直到迭代到最優位置.諸如,Meanshift[9?10]、Camshift[11]算法.綜上所述,傳統的目標跟蹤算法存在兩個致命的缺陷:1)沒有將背景信息考慮在內,導致在目標遮擋,光照變化以及運動模糊等干擾下容易出現跟蹤失敗.2)跟蹤算法執行速度慢(每秒10幀左右),無法滿足實時性的要求.

在過去的4年中,目標跟蹤取得了突破性的進展,主要由于將通信領域的相關濾波(衡量兩個信號的相似程度)引入到了目標跟蹤中.一些基于相關濾波的跟蹤算法 (MOSSE[12]、CSK[13]、KCF[14]、BACF[15]、SAMF[16])等,也隨之產生,速度可以達到數百幀每秒,可以廣泛地應用于實時跟蹤系統中.其中不乏一些跟蹤性能優良的跟蹤器,諸如SAMF、BACF在OTB[17]數據集和VOT2015[18]競賽中取得優異成績.近期,人們開始將深度學習方法應用到目標跟蹤中,取得了很好的效果,ECO[19]在VOT2017[20]競賽中獲得了冠軍.

據我們所知[21],目前還沒有關于目標跟蹤進展完整的文獻綜述和詳細調查.在這項工作中,我們由時間順序回顧現有的跟蹤算法,并根據最新算法在OTB數據集上的結果進行分析.此外,我們從以下幾個方面對目標跟蹤算法進行了分析、總結和綜述:

1)分析了生成式追蹤和判別式追蹤兩類方法的基本原理,并介紹了每種類型方法的跟蹤算法.

2)總結了早期跟蹤算法的發展過程以及Meanshift算法的改進策略.

3)詳細解釋了時域到頻域的轉換原理,以及相關濾波算法如何減少計算的復雜度,從而提升計算速度.

4)通過特征的選擇、尺度的變化、框架的改變三個方面對相關濾波改進策略進行分析,并列舉了一系列改進的方法.

5)分析深度學習類方法的結構特點,通過對比深度學習方法和相關濾波方法,分析了今后的發展方向.

本文結構如下:在第1節中,我們簡要介紹了跟蹤中常見的問題以及生成式追蹤和判別式追蹤的特點.在第2節中,我們簡要介紹了幾種經典的跟蹤方法,并從三個方面對Meanshift的改進算法進行了分析.在第3節中,首先對相關濾波的理論基礎及其數學推導進行介紹,然后從特征的選擇、尺度的變化、模型的改變三個方面對現有的相關濾波器進行了回顧.第4節中,簡要介紹深度學習類跟蹤算法并對其進行分類討論.第5節中,針對基于相關濾波的目標跟蹤算法和基于深度學習的目標跟蹤算法,進行比較和分析.總結了全文并展望目標跟蹤算法下一步的發展方向.

1 背景和相關工作

1.1 跟蹤中常見的問題

研究人員對運動目標跟蹤技術的探索已有多年,目標跟蹤算法的性能逐漸改善,但是在復雜條件下對運動目標實現實時、穩定的跟蹤仍存在很大的挑戰,面臨的挑戰主要如下[22]:

1)形態變化.姿態變化是目標跟蹤中常見的干擾問題.運動目標發生姿態變化時,會導致它的特征以及外觀模型發生改變,容易導致跟蹤失敗.例如:體育比賽中的運動員、馬路上的行人.

2)尺度變化.尺度的自適應也是目標跟蹤中的關鍵問題.當目標尺度縮小時,由于跟蹤框不能自適應跟蹤,會將很多背景信息包含在內,導致目標模型的更新錯誤:當目標尺度增大時,由于跟蹤框不能將目標完全包括在內,跟蹤框內目標信息不全,也會導致目標模型的更新錯誤.因此,實現尺度自適應跟蹤是十分必要的.

3)遮擋與消失.目標在運動過程中可能出現被遮擋或者短暫的消失情況.當這種情況發生時,跟蹤框容易將遮擋物以及背景信息包含在跟蹤框內,會導致后續幀中的跟蹤目標漂移到遮擋物上面.若目標被完全遮擋時,由于找不到目標的對應模型,會導致跟蹤失敗.

4)圖像模糊.光照強度變化,目標快速運動,低分辨率等情況會導致圖像模型,尤其是在運動目標與背景相似的情況下更為明顯.因此,選擇有效的特征對目標和背景進行區分非常必要.

1.2 目標跟蹤算法的基本分類

近20年,涌現出大量的目標跟蹤算法,根據其工作原理,我們將其分為生成式模型和鑒別式模型兩種.

1.2.1 生成式模型

早期的工作主要集中于生成式模型跟蹤算法的研究,如光流法[23?24]、粒子濾波[8]、Meanshift算法[9?10]、Camshift[11]算法等.此類方法首先建立目標模型或者提取目標特征,在后續幀中進行相似特征搜索.逐步迭代實現目標定位.但是這類方法也存在明顯的缺點,就是圖像的背景信息沒有得到全面的利用.且目標本身的外觀變化有隨機性和多樣性特點,因此,通過單一的數學模型描述待跟蹤目標具有很大的局限性.具體表現為在光照變化,運動模糊,分辨率低,目標旋轉形變等情況下,模型的建立會受到巨大的影響,從而影響跟蹤的準確性;模型的建立沒有有效地預測機制,當出現目標遮擋情況時,不能夠很好地解決.

1.2.2 鑒別式模型

鑒別式模型是指,將目標模型和背景信息同時考慮在內,通過對比目標模型和背景信息的差異,將目標模型提取出來,從而得到當前幀中的目標位置.文獻在對跟蹤算法的評估中發現[25],通過將背景信息引入跟蹤模型,可以很好地實現目標跟蹤.因此鑒別式模型具有很大的優勢.2000年以來,人們逐漸嘗試使用經典的機器學習方法訓練分類器,例如MIL[26]、TLD[27]、支持向量機[28]、結構化學習[29]、隨機森林[30]、多實例學習[31]、度量學習[32].2010年,文獻[12]首次將通信領域的相關濾波方法引入到目標跟蹤中.作為鑒別式方法的一種,相關濾波無論在速度上還是準確率上,都顯示出更優越的性能.然而,相關濾波器用于目標跟蹤是在2014年之后.自2015年以后,隨著深度學習技術的廣泛應用,人們開始將深度學習技術用于目標跟蹤.

2 早期的跟蹤算法

運動目標跟蹤,首先對目標進行有效地表達.然后在接下來的視頻序列的每一幀中找到相似度與目標最大的區域,從而確定目標在當前幀中的位置.早期的生成式方法主要有兩種思路:1)依賴于目標外觀模型.通過對目標外觀模型進行建模,然后在之后的幀中找到目標.例如:光流法.2)不依賴于目標外觀模型.選定目標建立目標模型,然后在視頻中搜索找到目標模型.例如:Meanshift.

2.1 光流法

2.1.1 光流法思想

光流法(Lucas-Kanade)的概念首先在1950年提出,它是針對外觀模型對視頻序列中的像素進行操作.通過利用視頻序列在相鄰幀之間的像素關系,尋找像素的位移變化來判斷目標的運動狀態,實現對運動目標的跟蹤.但是,光流法適用的范圍較小,需要滿足三種假設:圖像的光照強度保持不變;空間一致性,即每個像素在不同幀中相鄰點的位置不變,這樣便于求得最終的運動矢量;時間連續.光流法適用于目標運動相對于幀率是緩慢的,也就是兩幀之間的目標位移不能太大.

2.1.2 基于光流法的改進

隨后,人們開始在光流法的基礎上進行了改進.文獻[33]中將Harris角點檢測與光流法相結合,將光流法中的像素換成Harris特征點進行目標跟蹤,這樣減少了跟蹤像素的數量,使得算法的復雜度降低,處理速度加快.同時,相比于普通的像素,Harris角點對目標的描述更好,具有很強的魯棒性.相似的,文獻[34]中將光流法與SIFT特征進行融合,提取SIFT特征進行跟蹤,取得了很好的效果.文獻[35]中首次提出人造光流的概念,將真實光流與人造光流進行比較,通過矢量差判斷目標的運動.文獻[36]中,為了提高算法匹配的準確性,在光流法的框架上引入了前景約束.

然而,基于光流的目標跟蹤有很多的缺點.它對視頻中所有的像素進行計算,實時性差.因此,采用一定的縮小計算范圍的算法,具有重大意義.其中常見的算法有Kalman濾波、粒子濾波等.

2.2 Kalman濾波

Kalman濾波是一種能夠對目標的位置進行有效預測的算法.它建立狀態方程,將觀測數據進行狀態輸入,對方程參數進行優化.通過對前n幀數據的輸入,可以有效地預測第n幀中目標的位置,Kalman估計也叫最優估計.因此,在目標跟蹤過程中,當目標出現遮擋或者消失時,加入Kalman濾波可以有效地解決這種問題.缺點是是Kalman濾波只適合于線性系統,適用范圍小.

針對Kalman濾波適用范圍小這一問題,人們提出了粒子濾波的方法.粒子濾波的思想源于蒙特卡洛思想,它利用特征點表示概率模型.這種表示方法可以在非線性空間上進行計算,其思想是從后驗概率中選取特征表達其分布.最近,人們也提出了改進平方根容積卡爾曼濾波的方法來減小誤差[37],從而實現精準跟蹤.

2.3 核方法

2.3.1 基本思想

另一類基于搜索的方法是核方法.核跟蹤方法是目標跟蹤的主要方法,應用非常廣泛.例如Meashift、Camshift算法,它直接運用最速下降法的原理,向梯度下降方向對目標模板逐步迭代,直到迭代到最優位置.它的核心就是一步一步迭代尋找最優點,在跟蹤中,就是為了尋找相似度值最大的候選區間.我們這樣定義方向矢量:滿足計算范圍內的t個樣本點與區域幾何中心的矢量和.其中xi為樣本點,x為區域的幾何中心.Sh為符合計算區域的半徑為r的球區域.

Meanshift就是對樣本點與中心點的矢量差求平均值.矢量和的方向就是概率密度增加的方向,沿著概率密度增加的方向移動向量,逐步迭代直到找到最優解.但是這種搜索方法存在缺陷,只對樣本點進行計算,無論距離中心點的遠近,其貢獻是一樣的.當目標出現遮擋或運動模糊時,外層的特征容易受到背景的影響,其準確性降低.針對這一情況,我們應該賦予不同的采樣點不同的權值,離中心點越近,權值越高;反之亦然.因此,我們應該選擇合適的系數來提高跟蹤算法的魯棒性.為了解決這一問題,Du等[9]將Epannechnikov核函數引入到Meanshift中.

圖1 Meanshift跟蹤原理圖Fig.1 The tracking schematic of Meanshift

圖1表達了Meanshift的跟蹤原理示意圖:可以看出,算法通過逐步迭代尋找概率密度最大的方向.當偏移量小于某一設定閾值時,則可以認為樣本迭代到最佳位置,達到目標跟蹤的目的.跟蹤的過程分為三個步驟:

1)目標模型的建立:在初始幀中選中目標模型,對初始幀中的目標區域建立RGB顏色空間直方圖.目標的模型表示如下:

其中,c是歸一化系數,K表示內核函數,在本算法中使用Epanechikov核函數,δ函數是判斷點xi是否屬于目標區域,在區域內為1,不在區域內為0.

2)模型的搜索:在后續幀中,在前一幀的基礎上逐步搜索,得到目標區域的模型如下.其中,y為窗口的中心坐標,h表示核窗口的寬度.

3)相似度判別:相似度判別式是判斷是否繼續迭代的條件.當目標模型與跟蹤模型的相似度小于特定的閾值時,迭代停止,得到待跟蹤的目標區域.引入BH系數進行判斷,系數值越大,相似度越高.Su為目標模板,Qu為候選區域模板.

Meanshift算法雖然實現了較好的跟蹤效果,但是對目標尺度的變化不能進行自適應的跟蹤.針對這一缺陷,人們提出了Camshift算法.Camshift算法是在Measnhift基礎上的改進,在其中加入了尺度自適應機制,可以根據目標的大小自動調節跟蹤框的尺度,算法的流程圖如圖2:首先,Camshift算法中使用的是HSV顏色直方圖.這是由于HSV顏色直方圖具有較強的魯棒性.其次,根據所求得的顏色直方圖將初始輸入圖像轉化為概率分布圖像.最后是Meanshift迭代過程.進行Meanshift迭代,將前一幀的輸出作為后續幀的輸入.其思想與Meanshift相同,移動窗口中心到質心,逐步迭代,直到滿足迭代終止條件.在迭代的過程中,通過零階距調整窗口的大小.

圖2 Camshift算法流程圖Fig.2 Camshift algorithm flow chart

2.3.2 改進方向

隨著核方法的應用越來越廣泛,近年來基于其改進的算法層出不窮,主要針對背景復雜,遮擋與消失和算法的融合三個方面,改進的結構如圖3所示.

背景復雜:追蹤過程中視頻序列會存在光照干擾,背景混亂等復雜情況.通過對特征提取的改進,可以使得跟蹤效果得到提高.文獻[38]中在Camshift算法的基礎上擴展了顏色空間,使得對光照強度變化不敏感.文獻[39]中提出了將紋理特征加入到Meanshift算法中進行跟蹤的方法,因為紋理特征能夠更好地描述目標的表觀特征,能夠克服背景顏色相似干擾.文獻[40]中使用全局匹配和局部跟蹤方法,提出一個啟發式局部異常因子來提高跟蹤精度.Harris角點具有抗干擾、旋轉不變性等優點,因此文獻[41]中將Harris角點加入到Meanshift算法中.由于優質角點的引入,不但減少了計算量,提高了算法的效率;還能夠提高算法在復雜情況下的跟蹤效果.

遮擋和消失:Meanshift算法中沒有模型的預測機制,當目標被遮擋或者短暫消失時,跟蹤框會將包含的背景等干擾信息當成目標模型進行更新,從而導致跟蹤失敗.文獻[42]將Camshift算法與Kalman濾波相結合,運用Kalman濾波的預測機制來優化Camshift算法,在目標短暫消失的情況下仍能很好的跟蹤.在文獻[43]中,作者提出了一種基于加權片段的方法來處理部分遮擋,權重來源于片段和背景顏色之間的差異.這種方法不僅對光照不敏感,而且能夠很好地解決目標遮擋問題.

多算法的融合:算法的融合是為了讓每個算法優勢互補,提高融合后算法的性能.文獻[44?45]中將Camshift算法與粒子濾波相結合,通過粒子濾波選擇特征點,然后將選擇的特征點進行Camshift跟蹤,這樣可以對原始算法進行優化,但是計算速度變慢.之后的算法也有將Meanshift算法與光流法進行融合[46],對每個像素進行操作,解決運動速度過快問題,取得了較好的效果.文獻[47]提出了一種結合Meanshift算法和運動矢量分析的新型算法,在算法中選擇視頻序列進行分析,可以得到目標運動的方向和速度,為Meanshift的迭代指出反向,減少了迭代次數,提高算法的效率.

核方法由于其快速收斂的性質在實際中得到越來越廣泛的應用,研究人員逐步將優質的特征,尺度自適應以及模型的預測機制加入到核方法中并取得了很好的效果.但是跟蹤的速度難以得到本質上的提高,人們開始考慮使用新的跟蹤算法來提高跟蹤精度.

3 相關濾波跟蹤算法

在相關濾波方法用于目標跟蹤之前,所有的跟蹤算法都是在時域上進行處理.在運算過程中,涉及到復雜的矩陣求逆計算,運算量大,實時性差.基于相關濾波的目標跟蹤方法將計算轉換到頻域,利用循環矩陣可以在頻域對角化的性質,大大減少了運算量,提高運算速度.KCF在相關濾波基礎上進行了優化,引入了循環矩陣.目標跟蹤過程中缺少大量的負樣本,通過循環矩陣可以增加負樣本的數量,提高分類器訓練的質量.將高斯核加入到嶺回歸中,能夠將非線性的問題轉換到高維的線性空間中,簡化計算.

3.1 相關濾波跟蹤理論

相關是描述兩個信號之間的關系,而卷積是計算激勵信號作用于系統所產生的系統零狀態相應.在函數對稱情況下,卷積和相關具有相同的效果[12].

相關:

卷積:

基本思想為越是相似的兩個目標相關值越大,也就是視頻幀中與初始化目標越相似,得到的相應也就越大.我們知道,時域的卷積可以轉化為頻域的相乘來實現:訓練的目標就是得到這樣的一個濾波器模板,使得響應輸出最大化.

圖3 核跟蹤算法改進結構圖Fig.3 The improved structure diagram of kernel tracking algorithm

時間域上公式表示(f:輸入;h:濾波器;g:輸出):

頻域公式表示(G、F、H分別為g、f、h對應的傅里葉變換結果):

所計算的目標為:

MOSSE濾波器方法目標如下:

對目標函數求導,得到結果如下:

3.2 核相關濾波器(KCF)

在KCF中,作者將目標跟蹤問題的求解轉化為一個分類問題(圖像中的目標和背景).這個分類問題的求解應用了嶺回歸方法[13?14],所得到的分類器中包含了矩陣的逆運算,其運算量復雜,嚴重影響跟蹤系統的實時性.KCF在分類器的計算中引入了循環矩陣,巧妙地規避了矩陣的逆運算,大大減少了分類器的運算量.高斯核函數的引入可以將非線性問題轉化為高維空間中的線性問題,使得算法更具有一般性.KCF可以分為:模型建立、在線匹配、模板更新三個部分.

1)模型建立.目標函數為:

我們的目標是最小化采樣數據與下一幀真實目標位置的距離.

在解方程組中求解極值時,只要對w進行微分,使導數為0,即可得到最小值:

轉化在傅里葉域為:

但是,大多數情況下是非線性問題.我們引入了高維核函數的概念.在高維空間中非線性問題w可以變成一個線性問題.

那我們的目標函數就可以表示成:

其中,k表示核函數的定義運算如下:

將之前求w的問題轉換成了求α的問題:

對于核方法,一般不知道非線性函數?(x)的詳細表達,而只是刻畫在核空間的核矩陣?(x)?T(x).那么令K表示核空間的核矩陣.由核函數得到,那么:

2)在線匹配.定義Kz是測試樣本和訓練樣本間在核空間的核矩陣.通過推導[14]最終得到各個測試樣本的響應:

其中,Kxz是指核矩陣Kz的第一行,找到最大值對應的位置即為所求.

3)模板更新.針對外觀模型的變化,將雙線性插值方法加入到目標模型的更新中.濾波器系數α和目標觀測模型x為:

3.3 相關濾波算法發展

根據相關濾波算法的結構,在本節中,我們將從特征的選擇,尺度的估計以及分類器的模型三個方面進行討論.本節的框架圖如圖4所示:特征分為單一特征和混合特征兩類;尺度的估計包括尺度池估計、分塊估計、特征點估計三類;跟蹤模型的改進分為模型結構上的改進和模型融合.

圖4 相關濾波類算法發展方向Fig.4 Development direction of correlation filters algorithm

3.3.1 特征的選取

1)單特征.最早的相關濾波器MOSSE[12]使用的是灰度特征.由于灰度特征的單一性,使得其優點是跟蹤速度快,可以達到669幀每秒,但缺點是跟蹤精度低.隨后的算法CSK[13]是在MOSSE的基礎上增加了循環矩陣和核函數進行估計,但在特征上沒有做進一步的優化,仍使用灰度特征,其目標跟蹤速度可達320幀每秒.隨后CN[48]是在2014年在CSK的基礎上提出,它采用的是顏色特征(Color name).為了提高運算速度,論文中還用了PCA將11維的特征降到2維,并改進了模型跟蹤方案.KCF[14]與CSK[13]是同一作者,可以說是KCF是對CSK的進一步完善.KCF中使用的是HOG[53]特征,目標的表面紋理特征和輪廓形狀能夠很好地被HOG特征來描述.

2)多特征.隨著研究的深入,人們逐漸發現使用單獨的特征在跟蹤準確率和跟蹤速度上存在著性能瓶頸.因此,多特征融合成為了目標跟蹤的研究熱點.SAMF[16]是將CN、灰度特征和HOG特征進行矢量鏈接,將鏈接后的特征作為跟蹤的特征.STAPLE[54]是在DSST[50]算法基礎上將特征進行融合,DSST算法中使用的HOG特征,其對運動模糊、光照變化具有很強的魯棒性;而對于目標發生形變時跟蹤效果差.由于目標在運動過程中顏色分布不會改變,顏色直方圖可以很好地處理目標形變情況.因此,作者將HOG特征與顏色統計特征進行互補,共同作為目標的輸入特征.MOCA[51]中使用的是MC-HOG特征,首先,將輸入的RGB圖像轉換為顏色空間;然后,分別從顏色空間中的每個通道提取HOG;最后,將所有HOG特征結合在一起,形成一個三維矩陣或一個長向量,作為特征矩陣或特征向量.

近年來,隨著深度學習方法的廣泛應用,人們考慮將深度特征運用在目標跟蹤算法中.HCF[52],將深度學習提取的卷積特征用于目標跟蹤.Deep-SRDCF[64]算法中,采用單卷積層進行建模,用輸出的深度特征進行目標跟蹤,這樣能夠更好地區別目標與背景.

由上述的討論我們可以得出,目標特征的選擇經歷了由簡單到復雜的過程.最開始人們使用灰度、顏色、HOG、深度特征等單一的特征.隨著研究的進展,為了發揮每種特征的優勢,人們將多種特征進行融合,將融合后的特征作為目標特征.后續的研究可以考慮更多的有效特征或特征融合方式.

3.3.2 尺度自適應

早期的相關濾波類算法,如:KCF[14]、CSK[13]、CN[48]等,其目標跟蹤尺度是固定的.當跟蹤目標發生旋轉、形變或者尺度變化時,跟蹤器不能自適應地進行跟蹤.跟蹤框內會包含很多干擾信息,從而導致跟蹤失敗.因此,針對這一問題的改進,主要有以下幾種方法.

1)基于尺度池的方法.尺度池方法就是將原有的目標進行不同尺度的放大和縮小.計算變化后的目標,選擇響應值最大的作為跟蹤目標,從而達到尺度自適應追蹤.

穩健的尺度估計是視覺對象追蹤中的一個挑戰性問題.為了解決這一難點,人們提出SAMF[16]算法.其工作原理如圖5所示:跟蹤窗口i的大小為二維向量Si,S0為目標的輸入,k為尺度因子,k={k1,k2,···,ki},Si=ki?S0.對初始目標進行七個尺度的縮放,經過相關濾波器后分別得到對應的響應值.然后比較不同尺度響應值,并取響應值最大一個,作為最佳的目標尺度值.在SAMF中七個固定的尺度池:k={0.985,0.99,0.995,1.0,1.005,1.01,1.015}SAMF中使用最佳的尺度值對目標進行跟蹤,能夠解決目標跟蹤過程中目標尺度變化的問題,并在2014年的VOT視頻跟蹤競賽中取得第一名[55].DSST[50]中提出了一種基于三維尺度空間相關濾波器的聯合平移尺度跟蹤方法.在設計濾波器時,在二維位置平移的基礎上增加一維尺度.兩個濾波器工作相互獨立,分別進行目標定位與尺度縮放,這樣可以更加高效的工作,方便將該算法移植到其他算法中.追蹤時在目標周圍矩形區域計算一個特征金字塔,由于特征金字塔的引入,使得DSST算法的尺度變化有33種.

圖5 SAMF算法原理示意圖Fig.5 Schematic diagram of SAMF algorithm

2)基于分塊的方法.分塊方法是將目標分成若干個小塊,計算當前幀中塊與塊之間的距離.其核心思想是通過判斷分塊間的距離是否達到所設定的閾值來估計目標的尺度變化.

基于分塊的跟蹤也能很好的解決自適應跟蹤問題.文獻[49]中提出了一種基于多個相關濾波器的跟蹤方法(RPAC).其原理如圖6所示:首先在圖像中心選擇一個塊,在其上下左右依次選擇4個大小相同的塊.在跟蹤過程中,計算當前幀中間塊和上下左右塊中心點的距離.通過判斷各中心點間的距離是否達到尺度更新的閾值來進行尺度自適應跟蹤.

PSC[56]中,將目標分成4個小塊,計算初始幀中4個塊最大響應位置之間的距離.然后在后續幀中使用CN跟蹤器檢測4個塊中最大響應值的位置.通過比較位置變化的大小來判斷目標尺度的變化.文獻[57]中,將目標分成兩個塊,通過比較兩個塊在當前幀位置的關系來判斷目標尺度的變化.當兩個塊距離變小時,目標尺度減小;當兩個塊距離變大時,目標尺度變大.通過當前幀兩個塊之間的距離的變化,來確定目標尺度的變化.

圖6 RPAC算法原理示意圖Fig.6 Schematic diagram of RPAC algorithm

3)基于特征點的跟蹤.隨著研究的深入,人們想到使用特征點進行目標跟蹤.在目標跟蹤與特征匹配中,常用的特征點有SIFT[3]、SURF[4]、FAST[58]、BRIEF[59]等特征點.在sKCF[60]中,在視頻序列相鄰幀中提取特征點,賦予特征點不同的權值,離目標中心近,權重大;離目標中心遠,權重小.通過比較特征點的位置變化實現尺度自適應變化.早期的相關濾波方法MOSSE、CSK、CN、KCF,重點工作放在了對目標特征的改進上,對跟蹤尺度沒有進行改進.隨著研究的深入,后續的研究算法大多數解決了尺度變化的問題.SAMF和DSST中采用了尺度池策略,對目標尺度進行估計.但是由于尺度池有限,有時不能實現準確跟蹤.后續人們采用了分塊跟蹤策略和特征點跟蹤策略,對尺度池方法進行完善.特征點位置的變化對目標尺度更加敏感.相比之下,針對待跟蹤目標的特點,自適應的定義尺度是最好的選擇.

3.3.3 基于跟蹤框架的改進

1)基于模型的改進.更多的算法集中于相關濾波框架的改進[61],如SRDCF[62]和BACF[15].由于相關濾波是模板類方法,如果目標快速運動或者發生形變,HOG特征不能實時地跟上目標的變化,會產生錯誤樣本造成分類器性能下降,導致邊界效應的產生.SRDCF針對這一問題,擴大了搜索區域,加入空間正則化約束,其原理如圖7所示,離目標中心越近,約束越小;離目標中心越近越遠,約束越大;這樣減少了背景區域的權重,提高了分類器的可靠性.SRDCFdecon[63]在SRDCF基礎上將學習率從固定值改為自適應函數.BACF算法直接從訓練分類器入手,擴大樣本數量的同時又增加樣本的質量.先擴大循環采樣區域,這樣樣本數量會大量增加;同時為了保證樣本質量,縮小搜索區域,減少背景信息的干擾.

LMCF[64]使用CF來優化結構化SVM,提高計算速度.相比于傳統SVM,結構化SVM 具有更強大的判別力.但是在求解結構化SVM時計算量大,實時性差,因此只能進行稀疏的采樣.相關濾波思想出現后,通過使用循環矩陣增加采樣范圍,在頻域進行計算,提高了計算速度.因此可以使用CF來對結構化SVM 進行優化.同時,文中對目標檢測以及模型更新策略也進行了改進.如圖8所示:在目標檢測時,當響應值為明顯的峰值時,正常進行跟蹤;當響應值為多個峰值時,說明存在干擾信息,不能選取盲目地取峰值最高的位置,應該在產生峰值的位置重新進行比較.在模型更新時,當產生多個峰值時,停止對目標模板的更新,這樣可以減少相似干擾、目標遮擋等情況下錯誤的目標更新.

圖7 SRDCF空間正則化示意圖[62]Fig.7 SRDCF space regularization diagram[62]

圖8 LMCF模型在線檢測示意圖[64]Fig.8 LMCF model online detection diagram[64]

上述的目標跟蹤算法都是在短時間內進行在線跟蹤,若需要進行長時間目標跟蹤,必須配合在線檢測機制才能實現.LCT[65]中,在DSST二維位置濾波器和一維尺度濾波器的基礎上,增加一個檢測器并給檢測器設置兩個閾值,用來判斷跟蹤是否正確.當響應值小于最小閾值,說明跟蹤不可靠,應重新跟蹤;當響應值大于最大閾值時,目標跟蹤準確,應進行在線學習.通過使用短時間跟蹤算法和在線檢測器可以實現目標的長時間跟蹤.

相比于傳統的算法,隨著深度學習技術的發展,研究人員將深度學習用于目標模型的建立.CF2[66]中采用分層卷積進行建模.其中第一個卷積層提供更精確的定位,但無法處理待跟蹤目標的外觀劇烈變化的情況;第二個卷積層的輸出對目標的表觀信息,并且這種表示可以處理待跟蹤目標的外觀劇烈變化的情況,但是,它們無法精確定位目標.將兩個卷積層融合可以得到目標精確的位置.

2)基于融合的模型.每一種跟蹤算法都有自己的優勢.有的是通過提取優良的特征進行跟蹤,有的是引入可變化尺度進行跟蹤.通過將不同的算法進行合理地集成,可以進行優勢互補,達到更好的效果.文獻[67]中提出了一種基于集成(EBT)的方法,將多種算法結合在一起,每個跟蹤器獨立的負責目標跟蹤過程中的一個部分,例如:利用DLT[68]提取深度特征進行特征提取,利用LSST[69]估計尺度,利用Struct[70]和CSK作為跟蹤模型,并對跟蹤結果進行集成處理,集成多個跟蹤器的優勢提高跟蹤的穩定性,但其缺點是實時性差.

4 深度學習方法

最近,隨著深度學習方法的廣泛應用,人們開始考慮將其應用到目標跟蹤中[71].人們開始使用深度特征并取得了很好的效果.之后,人們開始考慮用深度學習建立全新的跟蹤框架,進行目標跟蹤.

深度學習方法的效果之所以火熱,是由于通過多層卷積神經網絡訓練大量的數據.但是將深度學習方法用到目標跟蹤存在嚴重的缺陷:

1)因為在目標跟蹤中的正樣本只有初始幀中的目標,沒有大量的數據難以訓練出性能優良的分類器.

2)深度學習方法通過將多層網絡連接訓練分類器來提高跟蹤精度,但是隨著卷積層數量的提高以及訓練網絡的復雜,算法的實時性很低,不能滿足快速運動目標的實時跟蹤.

雖然深度學習方法存在著缺陷,但是由于其在結構上的巨大優勢,研究人員逐步將其缺點進行改進.從改進的方向上看主要可以分成兩個部分.

4.1 基于相關濾波方法改進

優良的特征是實現良好跟蹤的基礎,深度學習方法得出的深度特征比傳統的手工特征(HOG、灰度、CN、Harris等)更加精確.相關濾波的核心思想是將計算轉化到頻域,相比于傳統方法,跟蹤速度得到了大幅度的提升.為了結合兩種方法的優點,人們開始將深度學習引入到相關濾波中.

HCF[52]中將深度特征與相關濾波算法相結合,由于卷積神經網絡不同層提取的特征具有不同的特點.前層圖像分辨率高,特征包含更多的位置信息;后層的特征包含更多的語義信息.作者使用三層網絡分別訓練相關濾波器,加權后得到目標的最終響應位置.DeepLMCF是在LMCF的基礎上引入了深度特征,提高了跟蹤的精度和算法在復雜情況下的魯棒性.由于前層的網絡包含更多的位置信息,DeepSRDCF[62]在SRDCF的基礎上建立單層網絡,這樣不但減少了深度特征的計算量,而且極大提升了算法的性能.C-COT[72]獲得了VOT2016競賽的第一名,文中提出了一種連續卷積濾波器的方法,在SRDCFdecon[63]的基礎上,采用多層深度特征,通過連續空間域差值轉換操作,實現了濾波器的輸入可以是不同分辨率的特征.ECO[19]是C-COT的改進版本,從模型大小、樣本集大小以及更新策略三個方面進行改進.首先篩選去除貢獻小的濾波器;然后簡化訓練樣本集,減少相鄰樣本間的冗余;最后每隔6幀更新一次模型,既減少了模型更新的次數,又能有效地減輕目標遮擋時的影響.

深度學習用于相關濾波方法中不局限于特征提取一個方向,人們開始考慮用深度學習方法構建分類器.SiamFC[73]一種孿生網絡的思想:其主要任務就是學習一個相似匹配函數,一個分支是保存目標信息,另一個分支是搜索特征,然后將兩部分特征進行相關操作,最后置信度高的區域即為目標的位置.

4.2 基于網絡結構的改進

DLT[68]算法首先將深度學習方法應用到目標跟蹤中.它針對在線訓練時正樣本缺失的問題,提出了一種離線訓練與在線調整相結合的方法.

作者首先在輔助數據集上進行離線訓練,獲取目標的特征表示.然后在跟蹤時,初始幀給定的情況下對網絡結構進行微調,實現準確地跟蹤.在模型更新時設置閾值機制,因為過多次數的模型更新會導致算法的復雜度增加,實時性差,因此作者通過比較當前幀目標與初始幀目標的相似度是否達到確定的閾值來判斷模型是否更新.

雖然DLT算法成功地將深度學習應用到了目標跟蹤中,但是仍存在以下缺陷:數據集上的圖片分辨率低,使得訓練的分類器效果差,很難得到有效的特征.訓練時會存在很多干擾,比如數據集中圖片的目標很有可能成為追蹤時的背景.當發生目標姿態變化,背景雜亂等干擾時,會導致目標模型一直更新,會增加算法的復雜度,實時性差.

由于訓練時存在樣本分辨率不高的情況,對于樣本與背景的定義非常模糊,為了解決這類問題.文獻[74]將高斯函數引入到卷積神將網絡中訓練中,來提高深度特征提取的精度

針對目標與背景對比度差異較大的情況,文獻[75]中降低了網絡的層次,減少了減法的復雜度.同時在模型更新時,由于初始幀是目標的正確描述,采用與訓練相同的網絡進行調整;在后續的跟蹤中會存在跟蹤漂移等問題,作者改變了更新策略,簡化了網絡結構,提高算法的實時性[76].

當目標與背景相似時,為了提高特征的精確度,需要采用多層次的網絡.文獻[77]提出一種網狀結構的神經網絡,它的思想是利用多個卷積神經網絡進行加權處理,每隔10幀更新一個神經網絡,并根據更新時間順序賦予每個神經網絡不同的權重.這種算法可以有效地提高跟蹤的精度,但是實時性差,每秒更新1.5幀.文獻[78]中針對正負樣本之間存在嚴重不平衡分布問題,用生成式對抗網絡來豐富高質量正樣本;同時提出了一個高階敏感損失來減小簡單負樣本對于分類器訓練的影響,跟蹤效果超過了ECO.

5 實驗分析討論

在本節中,首先對數據集OTB-2013[17,79]及目標跟蹤算法的性能評估方法進行介紹;然后,在數據集OTB-2013上,對50種目標跟蹤算法進行比較、分析;最后對目標跟蹤發展趨勢進行展望.

5.1 評估方法

為了比較各個算法的性能,我們使用了三種指標進行度量[79].第一種指標是精準度(Precision).在視頻序列中跟蹤的中心位置與標準中心位置差值小于某一個閾值所占視頻總幀數的比例.

其中,N表示一個視頻序列中的幀數,CLE表示一幀中的中心位置誤差,d表示一個特定閾值,dis(·)表示兩點之間的歐氏距離,p1表示被跟蹤目標的中心,p2表示實際目標中心.

第二種是成功率(Success rate).將當前幀中跟蹤框和標準框的重疊部分的面積與其覆蓋總面積做比值,得到數值(VOR).若所得到的數值超過特定的閾值,我們認為追蹤成功.Success rate是指計算跟蹤成功視頻所占總視頻的比例.公式為:

式中,BT表示當前幀的跟蹤區域;BG表示標準的目標區域;T表示兩者重疊區域;S表示兩者總的覆蓋區域.

第三種是跟蹤算法的速度,采用幀/秒(FPS)表示.

5.2 實驗與討論

隨著深度學習技術的廣泛應用,人們開始將深度特征應用到目標跟蹤領域.之后,人們開始考慮用深度學習建立全新的跟蹤框架進行目標跟蹤.近兩年,基于深度學習的目標跟蹤算法層出不窮,例如 ECO[19]、MDNet[80]、SANet[81]、BranchOut[82]、TCNN[77]等,并取得了很好的效果.本文將相關濾波方法、深度學習方法和傳統的目標跟蹤算法在OTB-2013上進行了對比.圖9中給出了50種目標跟蹤算法在OTB-2013中的總體精確度和成功率曲線.

由圖9的比較結果可以看出,相比于相關濾波類方法,深度學習方法的精度和成功率更高.在數據集OTB-2013中,排名前10的算法有9個是基于深度學習類的算法.ECO算法在各種條件下都有很好的跟蹤精度,ECO-HC中將ECO的特征換成傳統的HOG特征,提高了處理速度達到20FPS/s.相關濾波類算法 SRDCF[62]、LCT[65]、SAMF[16]、KCF[14]在精度上排名都比較靠后.這是由于深度學習方法提取出優秀的特征具有很高的魯棒性,深度學習方法訓練出的模型更加完善.傳統算法SCM、TLD、VTD排名最后,由此可見,經典方法已經被遠遠落后.但是由表1可以看出,深度學習類算法跟蹤速度過慢都多都在0.1～5幀每秒之間,不能達到實時跟蹤;而相關濾波類算法跟蹤速度可以達到百幀每秒,可以對目標實時跟蹤.在表1中:AUC表示跟蹤的精度,FPS表示每秒跟蹤的幀數.

6 結論

通過本文的討論,未來的研究方向可以從以下幾個方面來進行:

1)選擇有效的特征.強大的特征是良好跟蹤的基礎,HOG、CN、CNN特征已經取得了很好的效果.如何將優秀的特征進行融合是接下來的發展趨勢.而且,從實驗中可以看出CNN的特征優勢是明顯的,我們應該研究如何將深度特征運用到所有的算法中.

圖9 50種目標跟蹤算法在數據集OTB-2013上的總體性能對比,這里只顯示了排名前30的算法Fig.9 The overall performance comparison of 50 object tracking algorithms in the data set OTB-2013,only the top 30 algorithms are shown here

表1 各種目標跟蹤算法的速度比較Table 1 Speed comparison of various object tracking algorithms

2)強大的分類器.在好的跟蹤算法中,都有一個強大的分類器.LMCF中的結構化SVM、BACF中的嶺回歸以及ECO中的CNN深度學習架構.如何選擇好的分類器進行結合是我們接下來需要考慮的問題.

3)模型的更新.模型更新一直是目標跟蹤中重要的問題.好的模型更新機制可以避免將遮擋物以及背景作為目標來更新,從而有效地解決目標遮擋問題.因此,研究出好的模型更新機制勢在必行.

4)由以上分析可以看出,相關濾波方法和深度學習方法各具特點,如何能夠將二者進行融合,發揮各自的優勢值得我們深入研究.

圖10 50種目標跟蹤算法,在數據集OTB-2013中11種屬性下的成功率曲線Fig.10 50 object tracking algorithms,success rate curves under 11 attributes in data set OTB-2013