基于最優特征更新分類器的壓縮跟蹤算法

冷建偉　李　鵬

1(天津市復雜系統控制理論及應用重點實驗室　天津 300384)2(天津理工大學自動化學院　天津 300384)

0　引　言

基于視頻的目標跟蹤是計算機視覺領域的一個重要分支。隨著信息技術的發展，目標跟蹤技術也越來越多的應用到現實生活中，給人們的工作和學習帶來了難以想象的便利。同時，也帶來了無限的商機和挑戰，很多研究機構開始致力于目標跟蹤技術的研究與應用。目前，雖然很多目標跟蹤技術已經取得了成功應用，但當環境中影響因素較多時，跟蹤準確性往往會降低。因此，如何降低干擾因素對跟蹤的影響是計算機視覺領域一直以來的研究重點。根據檢測過程與跟蹤過程是否相關，可將跟蹤算法分為生成式和判別式兩大類。

生成式跟蹤算法是從眾多候選目標中尋找最優的候選目標，其跟蹤過程與檢測過程是相互獨立的，二者有一定的先后順序。2003年，Comaniciu等[1]利用目標顏色直方圖建立表觀模型，使用Mean-shift迭代求取最優解實現了目標定位。2012年，Rahmati等[2]對Comaniciu的方法進行了改進，實現了對嬰兒四肢運動的跟蹤。2004年，Li[3]提出一種具有較好魯棒性的PCA算法，該算法使用子空間學習方法建立目標表觀模型，在提高模型準確性的同時減少了算法耗時。2008年，Ross等[4]考慮到樣本均值更新問題，提出使用增量在線更新樣本均值，實現了表觀模型的自適應更新。2009年，Mei等[5]利用稀疏約束優化重構系數，提高了目標模板重構性能，使跟蹤穩定性有所提升。2011年，Li等[6]利用目標壓縮特征建立目標表觀模型，降低算法計算量，實現了對目標的實時跟蹤。生成式跟蹤方法利用目標表觀模型跟蹤目標，但這種方法容易受到背景干擾，特別是背景中存在與目標表觀相似的物體時，容易跟丟目標。同時，由于視角、形態、光照等因素，實際跟蹤目標往往沒有確定的表觀模型，很難對其進行結果性驗證。

判別式跟蹤算法充分利用背景信息，在跟蹤過程中實時檢測目標與背景，通過確定目標與背景的分界線進行分類，進而實現跟蹤。2007年，Liu等[7]在Boosting框架下使用梯度特征成功構建了判別式表觀模型，實現了目標與背景的分類。但該類算法沒有根據特征之間的關系選取特征，導致所選特征重疊度較高，分類器更新比較單一。2011年，Babenko等[8]提出一種通過“包”的形式訓練樣本的多示例學習跟蹤算法，使跟蹤具有較強的學習和判別能力，但由于“包”中包含多個樣本，使特征選擇比較耗時，難以滿足實時性。2012年，Zhang等[9]通過壓縮感知理論降低樣本維度，并使用樸素貝葉斯分類器對樣本壓縮特征進行分類，使跟蹤具有良好的時效性。但該算法也存在一定缺陷：1) 跟蹤過程中使用所有樣本對分類器進行更新，分類器容易受到被污染樣本的干擾，導致跟蹤穩定性下降。2) 跟蹤過程中始終使用固定尺寸的跟蹤框檢測和識別樣本，當目標尺度變化較大時容易引進誤差。為使跟蹤具有更好效果，很多專家和學者改進了CT算法。2014年，毛征等[10]通過對樣本壓縮特征進行在線選擇，提高了算法跟蹤準確性，但沒有解決跟蹤窗口尺度問題。2016年，姜樹明等[11]將Hog特征與多尺度矩形特征融合用于目標跟蹤，并使用多樣本矩形平均的方法確定目標位置，該算法跟蹤穩定性高，不易受干擾影響，但提取目標多種特征比較耗時。同年，朱周元等[12]結合基于隨機映射的外觀模型以及粒子濾波方法，使算法能適應目標尺度變化，提高跟蹤實用性。但該算法使用所有特征更新分類器，易受到被污染樣本干擾。

本文在CT算法框架下進行改進，首先，對測量矩陣進行優化，提高測量矩陣壓縮性能；然后，通過置信度和正負類分布差異對特征進行篩選，排除被污染樣本影響，使分類器更新更加準確；最后，利用相鄰兩幀目標仿射變換使跟蹤窗口可隨目標尺度變化實時更新，減少采樣誤差，提高跟蹤魯棒性。

1　壓縮跟蹤算法簡介

由壓縮感知理論可知，通過使用稀疏矩陣R∈Rn×m(n<

V=RX

(1)

且當R滿足Johnson-Lindenstrauss[13]準則時，V可最大限度的保留原始信號的判別信息。壓縮特征由原始特征經稀疏矩陣獲得，稀疏矩陣構造參考文獻[9]，即：

(2)

式中：rij是稀疏矩陣的元素；s是[2,4]內隨機生成的整數。

壓縮跟蹤算法中，特征提取過程如圖1所示。首先，通過使用不同位置和大小的矩形濾波器對高維圖像進行卷積，得到高維圖像特征；然后，將高維圖像特征歸類為一個集合；最后，對該集合使用非常稀疏矩陣進行降維，得到樣本壓縮特征。

圖1　特征提取過程

樣本圖像的低維特征向量v=(v1,v2,…,vn)∈Rn大體上服從獨立分布[14]。因此，CT算法使用對滿足獨立分布變量誤分率低且耗時小的樸素貝葉斯分類器對目標和背景進行分類，分類器模型如下：

(3)

式中：y∈{0,1}為樣本標記，y=1表示樣本為目標，y=0表示樣本為背景。

文獻[15]證明了經稀疏矩陣投影得到的低維特征大體滿足高斯分布，故H(v)中的條件概率p(vi|y=1)和p(vi|y=0)也服從高斯分布，即：

(4)

(5)

(6)

(7)

式中λ>0為學習率。

2　本文算法

2.1　優化測量矩陣

在壓縮感知中，測量矩陣決定了原始信號的壓縮與重構性能。好的測量矩陣需要滿足一定的條件(例如：零空間特征、列相關、RIP等)，在壓縮時可保留原始信號的重要信息，并可以結合測量值重構原始信號。CT算法使用非常稀疏矩陣獲取壓縮特征，降低計算復雜度，但這種矩陣是一種隨機矩陣，在應用上存在著一定的瓶頸：1) 隨機矩陣元素由隨機數構成，矩陣隨機性比較大，導致跟蹤結果重現難度大，且隨機數依賴硬件產生。2) 隨機矩陣很難完全滿足RIP和弱相關條件，壓縮性能并不是很理想。基于以上隨機測量矩陣的不足，引入確定性測量矩陣。

壓縮感知中確定性測量矩陣從構造角度可分為四類：1) 基于有限域的測量矩陣；2) 基于編碼的測量矩陣；3) 基于訓練的測量矩陣；4) 最大Welch界等式矩陣。由文獻[16]可知，基于差集構造算法的最大Welch界等式矩陣滿足RIP和列相干性條件，構造簡單，壓縮性能好，適用于跟蹤算法。所以，本文使用基于差集構造算法的最大Welch界等式矩陣投影獲取樣本壓縮特征。M×N維最大Welch界矩陣構造如下：

(8)

2.2　分類器更新

CT算法使用所有特征對分類器進行更新，當被污染或者不利于分類的特征用于更新分類器時，會影響分類器參數，進而影響跟蹤性能。因此，選取優質的特征更新分類器是很有必要的。針對分類器更新問題，本文對一幀中提取的壓縮特征進行兩次篩選，使用置信度高且正負類分布差異大的特征更新分類器，提高跟蹤抗干擾能力和準確性。

2.2.1初次篩選

初次篩選是通過置信度對特征進行篩選，置信度越高，表明特征包含目標信息越多；置信度越低，表明特征包含目標信息越少。為降低干擾影響，保證跟蹤穩定性，要盡量使用包含目標信息多的特征更新分類器。本文使用徑向對稱的高斯核函數[10](最常用的徑向基函數)來擬合特征置信度，其數學表達式為：

(9)

式中：x為函數變量，xc為核函數中心，σ為函數寬度。函數值表示變量x到函數中心xc的歐式距離。

壓縮特征服從高斯分布，因此可利用相鄰兩幀同一特征均值的差異來度量特征置信度，即：

(10)

式中：μk+1是某一特征后一幀概率分布均值，μk是該特征前一幀概率分布均值。若得到函數值較大，則說明此特征在相鄰兩幀均值差異較大，特征很有可能遭到污染；若得到的函數值較小，則說明此特征在相鄰兩幀均值差異較小，包含目標信息較多。

在初次篩選階段，首先利用式(10)計算同一特征在相鄰兩幀均值的差異，然后按得到的函數值大小對特征進行升序排列，選出前M個置信度高的特征等待二次篩選。通過使用置信度對特征進行篩選，可有效抑制由不良樣本引入的噪聲，降低對分類器選擇的影響。此外，為了充分利用背景信息，不對背景進行置信度評價，而是隨機選取負樣本更新分類器。

2.2.2二次篩選

在CT算法中，分類器是通過尋找目標與背景的界限來分類的，特征正負類分布差異越大，目標與背景界限越明顯，越有利于分類；特征正負類分布差異越小，目標與背景界限越模糊，越不利于分類。經過初次篩選以后，得到M個置信度高的特征，但由于這些特征正負類分布差異不同，所以分類能力也不同，因此，二次篩選的目的就是選取更利于分類的特征更新分類器。本文采用巴氏系數[17]度量特征正負類分布差異，對于連續分布，其表達式為：

(11)

式中：p(x)和q(x)是兩個樣本，B∈[0,1]表示巴氏系數，可用來評價特征正負類分布差異。B越小，正負類差異越大；B越大，正負類差異越小。

在二次篩選階段，首先計算經過初次篩選的M個特征的正負類分布差異，然后將特征按差異大小進行升序排列，選取前N(N

2.3　尺度更新過程

CT算法在跟蹤過程中始終使用初始跟蹤框采集和檢測樣本，當目標尺度發生變化時，跟蹤窗口不能很好的包圍目標，易產生采樣誤差。為了避免采集樣本帶來的誤差，本文通過求解相鄰兩幀目標仿射變換實時更新跟蹤窗口。相鄰兩幀目標的仿射變換關系如下式所示：

It=H×It-1

(12)

式中：It表示t幀目標，It-1表示t-1幀目標，H為3×3仿射變換矩陣，H可以表示為如下形式：

(13)

式中：ρ是尺度因子，θ是旋轉角度，(tx,ty)是平移向量。從上述公式可知，未知參數有4個，所以至少要存在4組匹配的特征點才能計算出仿射變換參數，而目標SIFI特征點可以提供多組(大于4)匹配特征。

跟蹤窗口更新的步驟如下：

(1) 提取初始幀目標SIFT特征點。

(2) 隨機選取固定數目(大于4)的特征點，作為目標特征庫。

(3) 從第二幀開始，提取當前幀目標SIFT特征點并與特征庫中的特征點進行匹配，得到固定數目(大于4)的特征匹配組。

(4) 利用匹配的特征點求解目標仿射變換參數，更新跟蹤窗口。

(5) 根據當前幀目標特征點更新目標特征庫。

通過以上方式，獲得相鄰兩幀目標的仿射變換參數，實時調整跟蹤窗口尺度，防止目標尺度變化影響樣本采集，使跟蹤準確性和魯棒性更高。

2.4　算法流程

本文算法使用初始幀壓縮特征構造分類器，對其他幀壓縮特征進行分類，通過其他幀最優特征更新分類器，并根據目標變化實時更新跟蹤窗口。算法流程如下：

2.4.1初始階段

(1) 手工選取目標，設置初次篩選數目M，二次篩選數目N，初始特征置信度等。

(2) 根據目標位置和跟蹤窗口尺度，分別采集正負樣本圖像集合Dα={z‖l(z)-l‖<α}和Dζ,β={z|ζ<‖l(z)-l‖<β}，其中l是初始幀的跟蹤位置，且α<ζ<β。

(3) 計算初始幀正負樣本的多尺度矩形特征，使用基于差集構造算法的最大Welch界等式矩陣對樣本投影得到壓縮域特征。

(4) 利用初始幀壓縮特征構造分類器。

2.4.2跟蹤階段

(1) 利用樸素貝葉斯分類器對上一幀壓縮特征進行分類，得到目標位置。

(2) 使用目標仿射變換參數調整跟蹤窗口大小和位置。

(3) 對上一幀壓縮特征進行篩選，得到最優特征。

(4) 使用最優特征更新分類器參數，為下一幀做準備。

(5) 重復跟蹤階段的(1)-(4)進行連續跟蹤。

3　實驗結果及分析

為了驗證本文算法性能，選取4個標準測試序列進行結果驗證，并在測試過程中與CT和MIL算法進行對比。實驗平臺基于Windows7操作系統，采用VS2013+OpenCV2.4.9實現算法運行，主要參數設置如下：M=100，N=50，初始置信度為1，特征庫中特征點個數為30，并從匹配的特征點中隨機選取6組用于計算目標仿射變換參數。在跟蹤過程中，采用中心誤差(目標實際中心與跟蹤結果中心之間的歐式距離)對跟蹤精度進行定量評價。

3.1　準確性比較

Sylvester序列中，目標姿態多次變化，同時伴有光照和相似物干擾。由圖2可知，當目標姿態小幅度變化時，三種算法跟蹤都比較穩定；當#1040幀時，目標向左旋轉并靠近光源，CT算法跟丟目標，MIL算法產生跟蹤漂移；當#1306幀時，背景中存在相似物干擾，導致CT和MIL算法均產生較大漂移，而本文算法始終對目標進行著準確跟蹤。可以看出，本文算法可有效抵抗光線、姿態、相似物等因素的干擾，抗干擾能力更強。

圖2　Sylvester

carScale序列中，目標尺度隨序列越來越大。由圖3可知，CT算法由于在跟蹤中沒有調整跟蹤窗口，導致跟蹤誤差越來越大；MIL和本文算法可隨目標變化實時更新跟蹤窗口，但MIL算法以“包”的形式訓練樣本，跟蹤窗口更新具有一定的不穩定性。而本文算法根據目標仿射變換更新跟蹤窗口，使跟蹤窗口可以很好的包圍目標，滿足多尺度跟蹤要求，減少采樣誤差。

圖3　carScale

jogging序列中，目標存在遮擋影響。由圖4可知，當#72幀時，跟蹤目標完全被障礙物遮擋，三種算法都暫時失去目標；當#94幀時，遮擋物消失，目標重新出現，CT和MIL算法已將遮擋物誤認為目標，導致跟蹤失敗。而本文算法可保留目標特征，當遮擋物消失后，可以重新定位目標，并對目標持續跟蹤。

圖4　jogging

Freeman4序列中，目標在靠近鏡頭過程中伴隨著左右旋轉和遮擋等干擾因素，嚴重影響目標跟蹤。由圖5可知，當#0108幀時，由于目標左右旋轉，CT和MIL算法出現了跟蹤漂移；當#0262幀時，經過嚴重遮擋后，CT算法將遮擋物誤認為目標，MIL算法跟丟目標。而本文算法能適應目標變化，始終對目標進行著有效跟蹤。

圖5　Freeman4

圖6為中心誤差曲線，是對跟蹤精度的定量評價。由圖6可知，與CT和MIL算法相比，在4個測試序列中本文算法具有最低的中心誤差，在跟蹤過程中，有效降低了光線突變、尺度變化、大面積遮擋等因素的影響，可對目標進行持續且穩定的跟蹤。

圖6　中心誤差曲線

3.2　算法速度比較

本文算法只使用部分優質特征更新分類器，間接降低了特征計算量。跟蹤算法中特征計算次數如公式所示：

N=m1×n1×NF+m2×n2×NF

(14)

式中：m1為初次篩選候選特征，n1是初次篩選特征數目，m2為二次篩選候選特征，n2是二次篩選特征數目，NF為特征對應部分的計算次數。兩種算法的特征計算次數如表1所示。由表1可知，本文算法所使用的特征數遠小于CT算法所使用的特征數，因此，本文算法特征計算量也相應減少，提高了跟蹤時效性。

表1　各算法計算次數及相關參數　次

為比較各算法運行速度，將每個序列測試20次，得出每一幀的平均處理時間，實驗結果如表2所示。由表2可知，由于本文在線篩選特征和更新跟蹤窗口，使算法耗時增加，但平均可達到27.57 ms/frame，滿足實時性要求。

表2　各算法運行速度比較　ms/frame

4　結　語

本文提出一種基于最優特征更新分類器的壓縮跟蹤算法。首先，優化測量矩陣，提高測量矩陣壓縮性能；然后，對壓縮特征進行篩選，使用置信度高且正負類分布差異大的優質特征更新分類器；最后，針對跟蹤窗口尺度問題，通過計算相鄰兩幀目標仿射變換實時更新跟蹤窗口。實驗結果表明，本文算法可有效抵抗光照、遮擋、尺度等因素的干擾，跟蹤穩定性更高，魯棒性更好，且滿足實時性要求。與CT算法相比，雖然本文算法減少了特征計算量，但特征篩選和跟蹤窗口更新還是比較耗時，使得本文算法在實時性方面與CT算法存在一定差距，如何減少耗時，將是本文后續研究重點。

[1] Comaniciu D, Ramesh V, Meer P. Kernel-based object tracking[J]. IEEE Transactions on Pattern Analysis and Ma-chine Intelligence, 2003, 25(5):564-577.

[2] Rahmati H, Aamo O M, Stavdahl φ, et al. Kernel-based object tracking for cerebral palsy detection[C]//Proceedings of the 2012 International Conference on Image Processing ,Computer Vision, and Pattern Recognition (IPCV). United States: CSREA Press, 2012:17-23.

[3] Li Y M. On incremental and robust subspace learning[J]. Pattern Recognition, 2004,37(7):1509-1518.

[4] Ross D A, Lim J, Lin R S, Yang M H. Incremental learning for robust visual tracking[J].International Journal of Computer Vision, 2008,77(1-3):125-141.

[5] Mei X,Ling H B.Robust visual tracking using l1minimization[C]//Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto, Japan: IEEE, 2009:1436-1443.

[6] Li H X, Shen C H, Shi Q F.Real-time visual tracking using compressive sensing[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence,RI,USA:IEEE,2011:1305-1312.

[7] Liu X M, Yu T. Gradient feature selection for online boosting[C]//Proceedings of the 11th IEEE International Conference on Computer Vision. Rio de Janeiro, Brazil: IEEE,2007:1-8.

[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] Zhang K H, Zhang L, Yang M H. Real-time object tracking via online discriminative feature selection[J]. IEEE Transactions on Image Processing, 2013,22(12):4664-4677.

[10] 毛征, 袁建建, 吳珍榮, 等. 基于在線特征選擇的實時壓縮跟蹤[J]. 光學精密工程, 2014,22(3):730-736.

[11] 姜樹明, 李鳳嬌, 張元元. 基于多特征融合的壓縮跟蹤算法[J]. 計算機工程與應用, 2016,52(15):203-207.

[12] 朱周元, 張超, 吳小培, 等. 尺度自適應的壓縮跟蹤算法[J]. 計算機工程與應用, 2016,52(14):180-185.

[13] Achlioptas D.Database-friendly random projection: Johnson-Linden straus with binary coins[J]. Journal of Computer and System Sciences, 2003,66(4):671-687.

[14] Ng A Y, Jordan M I. On discriminative vs. generative classifiers: a comparison of logistic regression and naive Bayes[J].Proceedings of Advances in Neural Information Processing, 2002,28(3):169-187.

[15] Diaconis P, Freedman D. Asymptotics of graphical projec-tion pursuit[J]. The Annals of Statistics, 1984,12(3):793-815.

[16] 王強, 李佳, 沈毅. 壓縮感知中確定性測量矩陣構造算法綜述[J]. 電子學報, 2013,41(10):2041-2050.

[17] Comaniciu D, Ramesh V, Meer P.Real-time tracking of nonrigid objects using mean shift[C]//Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head Island, USA: IEEE, 2000, 2:142-149.