帶權分塊壓縮感知的預測目標跟蹤算法

羅會蘭鐘寶康孔繁勝

①（江西理工大學信息工程學院 贛州 341000）

②（浙江大學計算機科學技術學院 杭州 310027）

帶權分塊壓縮感知的預測目標跟蹤算法

羅會蘭*①鐘寶康①孔繁勝②

①（江西理工大學信息工程學院 贛州 341000）

②（浙江大學計算機科學技術學院 杭州 310027）

針對矩形跟蹤框在邊緣處包含較多背景信息的問題，該文提出一種基于規范化梯度特征的帶權分塊壓縮感知的目標特征提取方法。該方法將壓縮感知測量矩陣轉化為分塊對角矩陣，且根據塊的重要程度分配適當的權重，縮小測量矩陣規模，簡化特征提取運算，弱化背景干擾。然后將提取的特征輸入變先驗概率的貝葉斯分類器，變先驗概率的分類器充分利用已有的跟蹤結果，從一定程度預測了目標的運動方向，減小候選目標的分類歧義性，使得每一幀的分類函數根據以往跟蹤結果進行變化，提高了分類的準確度。實驗在8個具有常見跟蹤難度的序列中測試，并與目前較流行的4種目標跟蹤算法在跟蹤效果、成功率等方面進行比較，結果從多個角度表明，該文提出的目標跟蹤算法具有較高的準確度和穩定性。

目標跟蹤；分塊壓縮感知；貝葉斯分類器；變先驗概率

1 引言

運動目標的跟蹤是計算機視覺領域的核心問題［1］。由于目標變化的復雜性（如姿態、光照、遮擋、運動模糊等），給運動目標跟蹤帶來很大挑戰。目前，目標跟蹤問題一般采用3種思路解決：基于逐幀檢測［24］-、基于預測［5，6］以及兩者相結合［7］。

基于逐幀檢測的目標跟蹤算法在跟蹤過程中有兩個關鍵問題：樣本特征的準確提取和分類器的設計。在樣本特征提取方面，文獻［8］發現在封閉目標的梯度空間圖上，盡管目標發生形變、光照等變化，只要將目標歸一化到相同的尺度，它們就變得驚人地相似，于是提出一種準確描述封閉目標的規范化梯度特征（Normed G radient， NG），應用于目標檢測，取得非常好的效果。但是，目標跟蹤與目標檢測不同，目標跟蹤要求對每一幀的檢測都是實時進行的，且目標模型需要不斷更新，因此目標跟蹤中提取的特征應盡量簡單有效。文獻［8］提出的規范化梯度特征數量較多，這就需要對特征進行有效壓縮，雖然文獻［4］提出一種壓縮感知方法用于壓縮目標特征，但是由于圖像本身信息量大，導致壓縮感知中測量矩陣規模較大，運算復雜。文獻［9］提出一種分塊壓縮感知方法可以使測量矩陣變成分塊對角矩陣，在后續的感知過程中只需用小塊的測量矩陣感知信號，通過這種方法可以使測量矩陣的規模迅速減小。在分類器設計方面，文獻［4］采用簡單有效的樸素貝葉斯分類器對候選目標的壓縮特征進行分類，取得較好的分類效果，但是在使用樸素貝葉斯分類器的過程中簡單地認為候選區域的目標和背景先驗概率相等，忽略了候選目標先驗概率對分類的影響，沒有充分利用先驗知識進行分類。

基于預測的目標跟蹤算法，是根據已有跟蹤結果利用數學知識直接求解目標位置。比如基于1e范式最小化的目標跟蹤（L1）［5］，把目標跟蹤問題當成稀疏逼近問題，在粒子濾波框架下將噪聲、遮擋和其他跟蹤難點當成碎片模板，然后將候選目標用目標模板基和碎片模板基進行稀疏表達，最后通過1e范式最小化求解，將最小錯誤投影當作目標位置，從而實現目標位置的預測。文獻［7］中的跟蹤學習檢測（Tracking-Learning-Detection， TLD）算法則是結合了預測和檢測算法，巧妙地把跟蹤、學習、檢測結合在一起。在運動目標部分可見的情況下，用跟蹤器來預測目標在連續幀間的運動。檢測器部分為一個高效的級聯分類器，使用簡單有效的圖像特征對目標進行實時的檢測，同時在必要的情況下糾正跟蹤器。學習模塊評估跟蹤器和檢測器的性能，通過生成有效的訓練樣本完成檢測器的更新，消除檢測器誤差。雖然文獻［5， 7］利用了已有的跟蹤結果，但是對目標預測的計算都非常復雜，難以達到實時性的要求。

本文提出一種基于規范化梯度特征的帶權分塊壓縮感知方法用于特征提取。給規范化梯度特征的每一分塊分配權重，以減小邊緣處背景信息干擾特征的影響。由于在大部分情況下，越靠近矩形框中心位置背景信息越少，因此權重的大小可以使用高斯分布，使得權值從矩形框中心位置向邊緣處逐漸減小。這樣提取的特征可以弱化背景干擾，提高特征的準確度。同時，本文提出一種基于線性貝葉斯分類器的變先驗概率方法，用于分類器的設計，與文獻［4］中判別目標和背景的線性貝葉斯分類器不同，本文提出的算法并不是默認候選目標先驗概率相等，而是通過對已有的跟蹤結果學習得到候選目標的先驗概率。本文提出的變先驗概率的貝葉斯分類器能充分利用已有的跟蹤結果，增強分類器的分類準確性。在8個具有挑戰性的視頻序列上（其中5個是文獻［3］中提供的標準測試序列；另外3個來自文獻［10］）與4種目前較先進的算法進行比較，實驗結果表明本文提出的帶權分塊壓縮感知的預測目標跟蹤算法能夠弱化背景干擾，減小特征的歧義性。同時，基于跟蹤結果的變先驗概率計算能夠增強分類的可信度，達到準確跟蹤目標的目的。

文章的第2節詳細論述了本文提出的算法，接下來是實驗結果及分析，最后是結論。

2 帶權分塊壓縮感知的預測目標跟蹤算法

本文提出了一種基于規范化梯度特征和帶權分塊壓縮感知的預測目標跟蹤算法。通過對封閉目標具有準確表示的規范化梯度特征進行分塊，然后給每一分塊分配權重，提出基于規范化梯度特征的帶權分塊壓縮感知特征提取方法，降低壓縮感知測量矩陣規模，弱化背景干擾。在分類階段，根據先前候選目標的反饋結果，提出一種變先驗概率的貝葉斯分類器，用于預測目標運動方向，增強分類準確度。為方便描述，將本文提出的帶權分塊壓縮感知的預測目標跟蹤算法命名為帶權分塊壓縮感知的預測目標跟蹤算法（Tracking using Weighted B lock Compressed sensing and location Prediction，TWBCP）。

2.1 基于NG特征的帶權分塊壓縮感知

文獻［8］中指出在封閉目標的梯度空間圖上，將圖像規范化到相同的尺寸，目標非常相似，基于此提出規范化梯度（Norm ed G radient， NG）特征用于封閉目標檢測。由于圖像在梯度空間上是稀疏的［11］，因此可以對梯度空間特征進行壓縮感知，降低特征維數。文獻［9］采用相同的高斯測量矩陣對分塊圖像進行感知，提出一種分塊壓縮感知（B lock Compressed Sensing， B lock CS）方法，這種方法使得測量矩陣變成分塊對角矩陣，在感知過程中只需利用小塊的測量矩陣進行測量即可，能迅速降低測量矩陣的規模。考慮到在目標跟蹤問題中，大多數目標都具有良好的封閉性，本文提出一種基于NG特征的帶權分塊壓縮感知方法用于特征提取。

由于跟蹤的目標常常是不規則的，矩形跟蹤框邊緣處通常包含較多背景信息。把背景特征當成目標特征進行學習會影響學習的準確性，并且會降低對于背景變化的魯棒性，影響跟蹤效果。因此，在基于NG特征的分塊壓縮感知特征提取階段，給每個NG特征塊進行權重分配。考慮到通常情況下越靠近跟蹤框中心位置，背景信息越少，在分配權重時，給中心位置分配較大的權重，而邊緣位置分配較小的權重，以弱化邊緣處背景的干擾。將NG特征分成L塊，第k塊的權重函數定義為

式（2）中（corex，corey）和（kx， ky）分別表示分塊的NG特征按照從左到右、從上到下的順序生成的2維中心塊位置坐標和第k塊位置坐標。（σx，σy）表示（kx， ky）離中心塊位置（corex，corey）的標準差。根據式（2）的定義，離中心塊位置越近的塊權重越大，表明其對特征的貢獻越大，反之越小。通過給邊緣處不重要的塊分配較小權重，中心處重要的塊分配較大權重的方法，可以減輕邊緣處的背景信息對目標特征提取的干擾。

于是，基于NG特征的帶權分塊壓縮感知特征計算為

2.2 變先驗概率的貝葉斯分類器

將式（4）代入文獻［12］提出的線性貝葉斯分類器整理得，第t幀第n個候選目標變先驗概率的貝葉斯分類判別函數為

式（6）的分類函數表明，該分類函數在每一幀都會根據先前跟蹤結果進行變化。對于每一個候選目標而言，如果正樣本先驗概率越大，分類函數中后半部分越大，從而影響候選目標的分類函數的值。式（6）定義的變先驗概率的貝葉斯分類器在某種程度上有根據以往跟蹤結果預測目標運動方向的作用，例如當目標向下運動時，會導致在目標下方的候選目標先驗概率集體增大，從而使得分類器具有運動方向預測作用。通過式（6）計算的分類得分很好地結合了本幀檢測和預測的結果。

2.3 算法流程

帶權分塊壓縮感知的預測目標跟蹤算法流程圖如圖1所示，算法在每跟蹤一幀圖像后都要重新更新相關參數，更新跟蹤參數使跟蹤算法能夠適應目標狀態的變化。在跟蹤當前幀的過程中，先計算候選目標的帶權分塊壓縮感知特征，然后將該特征輸入變先驗概率的貝葉斯分類器計算候選目標的分類得分。在所有候選目標分類得分計算完成后，取得分最大的候選目標作為本幀目標位置，完成本幀目標跟蹤。

3 實驗結果與分析

在8個具有代表性的數據集（序列）上實驗比較了本文提出的算法（TWBCP）與目前比較流行的4種目標跟蹤算法：多示例學習（M u ltip le Instance Learning， M IL）［3］、壓縮跟蹤（Com pressive Tracking，CT）［4］、基于1e范式最小化的目標跟蹤（L1）［5］和跟蹤學習檢測跟蹤（TLD）［7］。本文提出的跟蹤算法TW BCP與多示例學習（M IL）［3］跟蹤算法都是通過訓練好的分類器判別候選目標的得分，選取得分最大者作為本幀跟蹤位置，與M IL算法不同，本算法計算了候選目標位置的先驗概率，使得分類器對候選目標位置具有記憶性，增強分類能力。在壓縮感知方面，與CT算法不同，本算法采用分塊的壓縮感知方法減小了感知矩陣的規模，特征的提取比CT算法更簡單有效。基于預測的目標跟蹤算法（L1）以及基于檢測與預測結合的目標跟蹤算法（TLD）都是對目標具體位置進行預測，而本文提出的算法是通過候選目標位置的先驗概率預測目標的運動方向。

3.1 實驗數據集及參數設置

為了驗證本文提出算法的有效性和穩定性，選擇8個具有代表性的視頻數據集進行測試。其中david， dollar， faceocc， faceocc2和surfer是文獻［3］中提供的標準數據集；boy， mhyang和fish數據集來自文獻［10］。這些數據集包含多種目標跟蹤難點，如目標姿態變化、光照變化、遮擋、背景混亂、運動模糊、攝像頭抖動等。

圖1 帶權分塊壓縮感知的預測目標跟蹤算法流程圖

3.2 跟蹤效果比較

將本文提出的算法（TWBCP）與壓縮跟蹤（CT）、多示例學習（M IL）， TLD跟蹤（TLD）和基于1e范式最小化的目標跟蹤（L1）算法的跟蹤結果繪制于每一幀圖像，在dollar， faceocc2， faceocc和fish序列上的跟蹤定性比較結果如圖2所示。在算法的跟蹤結果中如果出現跟蹤丟失的現象，則跟蹤框不顯示在圖像上。

圖2 遮擋、光照變化對跟蹤結果的影響

圖2（a）dollar序列包含一個與目標非常相似的物體，由實驗結果可知，本文提出的TWBCP算法在第132幀目標與相似物體分離的過程、第227幀目標在運動的過程和第254幀目標與相似物體靠近的過程都能夠較準確地跟蹤選定的目標，跟蹤結果幾乎與CT算法一致。這表明基于NG特征的帶權分塊壓縮感知特征能夠準確地表征目標，使得分類器在跟蹤過程中能夠根據特征準確跟蹤目標。在包含遮擋、姿態變化的圖2（b）faceocc2序列，本文提出的TWBCP算法在第265幀對于障礙物的遮擋適應性較好；在第422幀姿態變化和遮擋同時發生的情況下，TWBCP算法仍然能夠準確跟蹤人臉；甚至在第709幀臉部幾乎被完全遮擋的情況下也沒有丟失目標。而對于把目標跟蹤問題當成稀疏逼近問題的L1算法，在第422幀和第709幀目標姿態變化和存在遮擋的情況下，都出現目標跟蹤錯誤。

圖2（c）faceocc序列中，不管是遮擋目標左部（第400幀）還是遮擋目標右部（第563幀），本文提出的TWBCP算法都能準確地定位目標位置；在后續目標在遮擋過后重現（第812幀）的情況下，本文提出的TWBCP算法跟蹤結果沒有被干擾，跟蹤位置比直接利用樸素貝葉斯分類器的CT算法更準確。這表明盡管目標遮擋對特征的提取造成干擾，TWBCP算法提出的變先驗概率的貝葉斯分類器充分利用已有跟蹤結果，預測目標將要運動的方向，在目標被遮擋或者目標由遮擋重現的過程中，算法預測的目標方向能夠幫助分類器正確分類。圖2（d）fish序列是包含大量光照變化和攝像頭抖動的序列，在第164幀光照突然變暗和第301幀光照突然變亮的前提下，本文提出的TWBCP算法定位的結果較為準確；TLD算法在301幀后直到跟蹤結束，出現目標丟失現象，這表明攝像頭抖動和光照對TLD算法影響較大。由于本文提出的TWBCP算法是基于梯度空間特征的，梯度特征對光照變化等具有很好的魯棒性。

3.3 跟蹤成功率比較

為了定量比較算法的跟蹤準確性，參照文獻［4］的做法，將跟蹤目標與真實目標矩形框的交集除以它們的并集作為跟蹤重合率，跟蹤重合率大于0.5即認為是跟蹤成功的，將跟蹤成功的幀除以總幀數即得該序列的跟蹤成功率。

本文提出的TWBCP算法與壓縮跟蹤（CT）、多示例學習（M IL）， TLD跟蹤（TLD）和基于1e范式最小化的目標跟蹤（L1）算法在8個序列上的跟蹤成功率比較如表1所示。從表1中的實驗結果可以看出，本文提出的TWBCP算法在6個序列中獲得了最好的跟蹤成功率，且在8個序列上的平均跟蹤成功率高出次好的TLD算法22%。而且本文提出的TWBCP算法在相對簡單的dollar序列和相對難的surfer序列都獲得最好的跟蹤成功率，這表明本文提出的TWBCP算法采用的基于NG特征的帶權壓縮感知特征對目標的描述準確，且變先驗概率的貝葉斯分類器學習了以往的跟蹤結果，使得分類算法對常見的跟蹤難點魯棒性較好，對序列的適應性較強，跟蹤的結果不依賴于特定的序列。

表1 跟蹤成功率（取整）比較（%）

3.4 實驗分析

從上面實驗對比結果可以看出，本文提出的算法在具有各種跟蹤難點的序列中都具有較好的表現。從跟蹤效果來看，在具有大量遮擋的faceocc序列和faceocc2序列、光照變化強烈的fish序列和背景相似物體干擾的dollar序列，本算法具有較好的跟蹤效果（見圖2）。從算法的跟蹤成功率來看（見表1），本算法比性能優秀的結合預測和檢測的TLD跟蹤算法平均成功率高出22%，比其他算法高出更多。這些實驗結果從各個方面充分證明本文提出的基于NG特征的帶權分塊壓縮感知特征能較好地表達目標，同時變先驗概率的貝葉斯分類器能根據以往跟蹤結果預測目標的運動方向，實現準確跟蹤。

4 結束語

本文將分塊壓縮感知應用于目標跟蹤，提出一種基于NG特征的帶權分塊壓縮感知用于目標特征提取，削弱了背景干擾，增強了特征的表達能力。在跟蹤階段，候選目標的先驗概率是根據以往的跟蹤結果計算得出的，并不是簡單地認為正負樣本先驗概率相等，從某種程度上預測了目標的運動方向，提高了算法的準確度。實驗結果從多個角度表明，本文提出的算法對常見的跟蹤難度，如遮擋、光照變化、姿態變化具有較好的適應性。本文算法采用的特征是基于簡單的圖像梯度特征，對封閉目標有較好的效果。在后續的研究中嘗試融合更加復雜的特征，如哈爾（Haar）特征［13］、尺度不變特征變換（Scale-Invariant Feature Transform， SIFT）特征［14］以及方向梯度直方圖（Histogram of Oriented Gradient， HOG）特征［15］，從而使得算法對跟蹤的目標有更寬松的要求。

［1］ Yilmaz A， Javed O， and Shah M. Ob ject tracking:a survey［J］. ACM Computing Surveys， 2006， 38（4）: 1-29.

［2］ Saffari A， Godec M， Pock T， et al.. On line multi-class LPBoost［C］. Preceed ings of the IEEE Conference on Com puter Vision and Pattern Recognition， San Francisco，USA， 2010: 3570-3577.

［3］ Babenko B， Yang M H， and Belongie S. Robust ob ject tracking w ith online multiple instance learning［J］. IEEE Transactions on Pattern Analysis and M achine Intelligence，2011， 33（8）: 1619-1632.

［4］ Zhang Kai-hua， Zhang Lei， and Yang M H. Real-time comp ressive tracking［C］. Preceedings of the European Conference on Computer Vision， Florence， Italy， 2012， 3: 864-877.

［5］ Mei Xue and Ling Hai-bin. Robust visual tracking and vehicle classification via sparse representation［J］. IEEE Transactions on Pattern Analysis and M achine Intelligence， 2011， 33（11）: 2259-2272.

［6］ 孫景樂， 唐林波， 趙保軍， 等. 基于瑞利分布的粒子濾波跟蹤算法［J］. 電子與信息學報， 2013， 35（4）: 763-769. Sun Jing-le， Tang Lin-bo， Zhao Bao-jun， et al.. A new particle filter tracking algorithm based on Ray leigh distribu tion［J］. Journal of Electron ics & Inform ation Techno logy， 2013， 35（4）: 763-769.

［7］ Kalal Z， M ikolajczyk K， and M atas J. Face-TLD: trackinglearning-detection applied to faces［C］. Preceedings of the IEEE International Conference on Image Processing， Hong Kong， China， 2010: 3789-3792.

［8］ Cheng M ing-m ing， Zhang Zi-ming， Lin Wen-yan， et al.. BING: binarized normed gradients for ob jectness estimation at 300fps［OL］. http://mm cheng.net/bing/， 2014.

［9］ Liu Gan. B lock com pressed sensing of natural im ages［C］. Preceed ings of the International Conference on Digital Signal Processing， Cardiff， B ritain， 2007: 403-406.

［10］ Wu Y， Lim J， and Yang M H. On line ob ject tracking: a benchmark［C］. Preceedings of the IEEE Conference on Com puter Vision and Pattern Recognition， Portland， USA，2013: 2411-2418.

［11］ 李然， 干宗良， 崔子冠， 等. 聯合時空特征的視頻分塊壓縮感知重構［J］. 電子與信息學報， 2014， 36（2）: 285-292. Li Ran， Gan Zong-liang， Cui Zi-guan， et al.. Block com p ressed sensing reconstruction of video combined w ith temporal spatial characteristic［J］. Journal of Electronics & Inform ation Techno logy， 2014， 36（2）: 285-292.

［12］ Ng Y A and Jordan I M. On discrim inative vs. generative classifier: a com parison of logistic regression and naive bayes［C］. Preceedings of the Advances in Neural Information Processing System s， W histler， Canada， 2002: 841-848.

［13］ Papageorgiou P C， Oren M， and Poggio T. A general fram ework for ob ject detection［C］. Preceedings of the International Conference on Com puter V ision， Bombay， India， 1998: 555-562.

［14］ 董文會， 常發亮， 李天平. 融合顏色直方圖及SIFT特征的自適應分塊目標跟蹤方法［J］. 電子與信息學報， 2013， 35（4）: 770-776. Dong W en-hui， Chang Fa-liang， and Li T ian-p ing. Adaptive fragm ents-based target tracking m ethod fusing color histogram and SIFT features［J］. Journal of Electronics & Information Technology， 2013， 35（4）: 770-776.

［15］ Dalal N and Triggs B. Histogram s of oriented gradients for human detection［C］. Preceedings of the IEEE Conference on Com pu ter V ision and Pattern Recogn ition， San D iego， USA，2005， 1: 886-893.

羅會蘭： 女，1974年生，博士，教授，研究方向為機器學習、模式識別.

鐘寶康： 男，1988年生，碩士生，研究方向為目標跟蹤、模式識別.

孔繁勝： 男，1946年生，博士生導師，教授，研究方向為人工智能與知識發現.

Tracking Using Weighted Block Com p ressed Sensing and Location Prediction

Luo Hui-lan①Zhong Bao-kang①Kong Fan-sheng②①（School of Information Engineering， Jiangxi University of Science and Techno logy， Ganzhou 341000， China）
②（College of Computer Science and Technology， Zhejiang University， Hangzhou 310027， China）

To reduce side effects of background in formation included in the outer parts of tracking rectangular boxes， a weighted b lock com pressed sensing feature extraction method is p roposed based on normalized gradient features. The com pressed sensing m easurem ent matrix is converted to a b lock diagonal m atrix. App rop riate weights are assigned to different blocks according to the im portance of the blocks. It aims to reduce the measurement matrix size， weaken background interference and sim plify feature extraction. Then the extracted features are inputted into Bayesian classifier w ith adaptive p riori probabilities， which is proposed to make full use of existing tracking resu lts. To some extent the classifier w ith variable p riori p robabilities can p redict the direction of the moving targets， and reduce the ambiguities of target candidates. Each frame classification function changes according to the results of the previous track to im prove the classification accuracy. In the experim ents com pared w ith four state-of-the-art tracking algorithms on 8 common ly used tracking test sequences， the proposed target tracking algorithm has higher accuracy and stability in term s of tracking results and success rate.

Ob ject tracking； B lock com pressed sensing； Bayes classifier； Variable p riori p robability

TP391

： A

：1009-5896（2015）05-1160-07

10.11999/JEIT140997

2014-07-25收到，2014-09-28改回

國家973計劃項目（2010CB327900），國家自然科學基金（61105042，61462035）和江西省教育廳科技項目（GJJ13421）資助課題

*通信作者：羅會蘭 luohuilan@sina.com