在線判別式超像素跟蹤算法

劉雨情， 肖 嵩， 李 磊

(西安電子科技大學 綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071)

基于視頻序列的目標跟蹤技術，一直以來都是計算機視覺領域的核心問題，在智能交通、軍事航天以及人機交互領域都有著廣泛的應用．國內外學者通過不斷研究也提出了許多有效的目標跟蹤算法[1-5]．

近年來，超像素特征作為一種新興的中層視覺特征，被廣泛研究和應用于各種計算視覺任務中，如圖像分割、人體姿態估計和目標識別等．2014年，文獻[5]將超像素用于目標跟蹤中，提出了一種魯棒性的超像素跟蹤(robust SuperPixel Tracking，SPT)算法．該算法能出色解決目標跟蹤中的挑戰性難題，如復雜背景、非剛性形變和快速運動等，并在PASCAL VOC tests上取得了比跟蹤學習檢測(Tracking Learning Detection，TLD)算法[3]、視覺跟蹤分解(Visual Tracking Decomposition，VTD)算法[7]等主流目標跟蹤算法更好的跟蹤性能．但由于該算法每次在更新外觀模型時積累了海量的超像素信息(平均達上千個)，采用MeanShift方法進行聚類對外觀建模非常耗時，達不到實時性要求．此外，該算法在目標遮擋時易出現跟蹤漂移，具有一定的局限性．

1 在線判別式超像素跟蹤方法

針對SPT[5]算法建模速度慢的缺陷，筆者提出了一種新的表觀模型構建機制，創新性地將超像素特征和超限學習機相結合，用于處理超大樣本集的快速特征學習問題，將收集到的大量帶標簽的目標前景-背景數據集結合超限學習機的監督型學習算法，訓練得到一個超像素前景-背景分類器，實現前景-背景粗分類．在此基礎上，結合k-d樹實現快速K近鄰(K-Nearest Neighbor，KNN)聚類，對前景和背景特征空間進行細分割，精確構建目標前景和背景的外觀模型(即特征詞典)．筆者所改進的這種從粗到精的前景-背景建模方法顯著降低了表觀建模的時間開銷，將每次模型構建時間從原來的幾十秒控制在 1 s 以內．最后，算法結合粒子濾波和相關濾波實現了魯棒性的目標跟蹤．文中所提算法的框架如圖1所示．

圖1 目標跟蹤方法訓練和跟蹤過程框架圖

1.1 基于超像素分割的目標前景和背景特征提取

由于顏色統計特征在目標發生非剛性形變、旋轉和快速運動時具備不變性，但不具備光照不變性．而方向梯度直方圖(Histogram of Oriented Gradient，HOG)特征對光照、尺度等具備不變性，但卻不適應非剛性形變和快速運動．文中算法將顏色統計特征和HOG特征相結合，取得對目標更強的描述能力．

設第t幀目標的狀態St={Xt,Yt,Wt,Ht}，其中，{Xt,Yt}表示目標的中心位置，{Wt,Ht}表示目標的寬和高．在訓練階段如圖1(a)所示，收集前幾幀的目標和背景信息，然后將每個訓練幀分割為Nt個超像素s(r,t)，r=1,2,…,Nt，其中，s(r,t)為第t幀的第r個超像素．統計每個超像素中屬于目標框和不屬于目標框的像素個數，將與目標框重合的超像素標記為前景,其余情況全部標記為背景．第r個超像素的標簽l(r)可表示為

(1)

在得到超像素信息后，提取每個超像素的顏色特征構成該超像素塊的特征．

1.2 構建前景-背景特征詞典

針對SPT[5]算法建模耗時大的問題，筆者用超像素特征訓練超限學習機學習前景和背景表觀特征，結合KNN聚類減少建模耗時．文中所提算法在跟蹤中對一定區域內的超像素依據訓練好的超限學習機進行前景-背景特征的分類，之后，依據超像素塊的置信值來收集超限學習機的更新訓練數據．

1.2.1 訓練超限學習機

超限學習機(Extreme Learning Machine，ELM)[6]是一種含單個隱藏層的前饋型神經網絡，在1.1節中通過超像素分割和特征提取獲得大量帶有標記的超像素訓練樣本(Xj,tj),j=1,2,…,N，Xj= (x1,x2,…,xn)T∈Rn，為提取的超像素特征向量，tj為每個特征對應的類別．假設隱藏層節點數為L，需訓練得到一個超限學習機最小化網絡預測標簽與訓練數據標簽間的差值:

其中，σ1>0，σ2>0，u，v=2，H為隱藏層輸出矩陣(隨機初始化的矩陣)，β為隱藏層與輸出層的連接權矩陣．網絡的前向預測輸出fL(X)為

(3)

其中，ai為隱藏層神經元的輸入權值，bi為偏置，βi為隱藏層與輸出層的連接權值，Gi(·)為隱藏層神經元的特征映射函數．例如，在映射函數為徑向基函數的情況下，隱藏層節點的響應為

(4)

在目標跟蹤的初始訓練階段，由于在訓練樣本集中采用區域規劃策略采集到大量的負樣本，冗余的負樣本會影響ELM的分類性能．為此在訓練過程中采用困難負樣本挖掘策略將負樣本分組，每次迭代求解ELM時僅將后一組中的假正樣本加入到前面組組成的背景特征集，學習到更具區分性的負樣本集，從而提高超限學習機的分類準確率．

1.2.2 KNN聚類

在收集到目標表觀特征池，Ft= {s(i,t)|l(i)=1}，Fb= {s(i,t)|l(i)=0} 的基礎上，在特征池內部采用k-d樹實現快速KNN聚類，分割前景和背景特征空間，構建帶置信度的前景-背景特征詞典．在聚類中將近鄰的參數設置為常數(近鄰的參數設置過高會降低跟蹤的準確度，過低會影響算法的實時運行速度，為了兼顧跟蹤的速度與準確度，通過大量實驗仿真將近鄰的參數設置為經驗值10)，并將距離小于固定值的近鄰聚為一類．記C(j)為每類的置信度，則有

C(j)=S+(i)-S-(i)S+(i)+S-(i) ，i=1,2,…,Nt,(7)

其中，S+(i)和S-(i)分別為屬于和不屬于目標框的像素數．在特征空間中，與目標框重合度高的類其前景置信度就越高(置信值越趨近于1)；相反，與目標框重合度低的類其背景置信度就越高(置信值越趨近于 -1)．

1.3 目標位置估計

跟蹤過程中，文中算法在一定的搜索區域Pt內，依據目標的大小變化先進行變尺度超像素分割，搜索區域Pt以{Xt-1,Yt-1}為中心，以λd{Wt-1,Ht-1}為大小．隨后提取每個超像素的特征并輸入到超限學習機，對超像素進行前景-背景分類，之后，通過模塊匹配快速找到其最近鄰和所屬的類j．每個超像素的前景-背景置信度由其所屬類的置信度C(j)和其最小類內距計算得出，即

(8)

?l=1,2,…,N．(9)

1.4 目標尺度估計

(10)

在頻域表示內，對式(10)中的H進行逐元素求偏導，最終得所需濾波器H*的解析解為

(11)

在當前目標中心位置{Xt,Yt}處，利用所得相關濾波器搜索目標的尺寸，搜索尺寸設置為尺度金字塔的m個尺度級數．當新的一幀到來時，提取不同尺度目標圖像塊的HOG特征并求得其頻域為Z，利用得到的濾波器計算每個尺度的相關響應，求得相關得分為

yi=F-1(H*⊙Zi) ,i=1,2,…,m．(12)

從中將響應值最大的尺度和粒子濾波的結果進行加權處理后，作為當前幀的尺度S，后續依據固定的學習速率對濾波器進行更新．

2 實驗分析

文中所提算法仿真的實驗環境配置為3.30 GHz Intel(R) Core(TM)i3-3220 CPU的臺式機，軟件環境為Matlab R2016b (64 bit)．

(1) 算法耗時分析．文中選取4個典型的視頻序列，通過平均聚類樣本數、外觀建模時間和平均跟蹤速度3項對比分析了SPT[5]算法和文中所提算法，具體數據如表1所示．SPT[5]算法在4個視頻序列中聚類的樣本數每次均達到 4 000 以上，每次的聚類耗時最少的為Bird2序列達到了 22.68 s．SPT[5]算法在外觀模型聚類上的耗時導致算法每幀的跟蹤用時至少為 2 s，達不到實時要求．文中所提算法將表觀建模時間降至 1 s 以內，每幀的處理時耗降至 0.15 s 左右，顯著提高了目標跟蹤的速度．

表1 算法時間性能對比分析表

(2) 算法性能驗證．SPT[5]算法針對12個測試視頻進行了性能分析，由于原算法需由作者根據視頻序列目標的運動信息預先人工設定不同的運動參數(共6個)，所以筆者基于這12個視頻序列和原算法以及一些主流跟蹤算法進行比較，包括TLD算法[3]、核結構輸出(Structured output kernels，Struck)算法[1]、VTD算法[7]．算法針對各個測試視頻的跟蹤性能采用中心位置誤差(Center Location Error，CLE)和成功跟蹤幀數(Successfully Tracked Frames，STF)指標表示，其中，CLE表示跟蹤算法預測出的目標中心與真實目標中心的像素距離值在每個序列上的平均值，STF表示序列中跟蹤算法預測出的目標框與真實目標框的重合率在50%以上的總幀數．

由表2可知，文中所提算法在9個測試視頻上具有穩定的跟蹤效果，且算法的總體平均性能優于TLD算法[3]、Struck算法[1]和VTD算法[7]的性能．

表2 算法對于測試視頻序列的CLE、STF性能指標

(3) 算法性能分析．為了進一步驗證算法的性能，選取另外一些測試視頻并將算法與一些跟蹤算法進行了跟蹤結果的比較，部分視頻序列的跟蹤結果如圖2所示．比較算法包括TLD算法[3]、稀疏聯合模型(Sparsity-based Collaborative Model，SCM)算法[8]和核關聯濾波(Kernelized Correlation Filters，KCF)算法[4]．

圖2 不同算法的跟蹤結果

3 結 束 語

筆者在超像素分割的基礎上提出了一種新的目標跟蹤算法，算法利用超像素分割和特征提取分別獲取大量前景和背景模板，之后利用ELM和KNN聚類分別構建目標和背景的判別式外觀模型，實現前景和背景建模的分離，并結合粒子濾波得到目標的最優位置；最后，結合相關濾波策略對目標進行尺度估計．在大量測試視頻序列上，通過定量的實驗分析，證明了文中所提算法在處理速度上優于原算法，并針對目標的遮擋、快速移動、形變以及尺度變化，均具有良好的魯棒性．

[1] HARE S, GOLODETZ S, SAFFARI A, et al. Struck: Structured Output Tracking with Kernels[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(10): 2096-2109.

[2] 張浪, 侯志強, 余旺盛, 等. 利用快速傅里葉變換的雙層搜索目標跟蹤算法[J]. 西安電子科技大學學報, 2016, 43(5): 153-159.

ZHANG Lang, HOU Zhiqiang, YU Wangsheng, et al. Two-level Searching Tracking Algorithm Based on Fast Fourier Transform[J]. Journal of Xidian University, 2016, 43(5): 153-159.

[3] KALAL Z, MIKOLAJCZYK K, MATAS J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1409-1422.

[4] LI Y, ZHU J. A Scale Adaptive Kernel Correlation Filter Tracker with Feature Integration[C]//Lecture Notes in Computer Science: 8926. Heidelberg: Springer Verlag, 2014: 254-265.

[5] YANG F, LU H, YANG M H. Robust Superpixel Tracking[J]. IEEE Transactions on Image Processing, 2014, 23(4): 1639-1651.

[6] KWON J, LEE K M. Visual Tracking Decomposition[C]//Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2010: 1269-1276.

[7] TANG J, DENG C, HUANG G B. Extreme Learning Machine for Multilayer Perceptron[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(4): 809-821.

[8] ZHONG W, LU H, YANG M H. Robust Object Tracking via Sparsity-based Collaborative Model[C]//Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2012: 1838-1845.