基于壓縮感知的粒子濾波跟蹤算法

吳曉雨，吳凌琳，楊 磊

（中國傳媒大學信息工程學院，北京100024）

基于壓縮感知的粒子濾波跟蹤算法

吳曉雨，吳凌琳，楊 磊

（中國傳媒大學信息工程學院，北京100024）

針對運動目標跟蹤存在的目標遮擋和光照變化問題，提出一種基于壓縮感知的粒子濾波跟蹤算法。將改進的壓縮感知跟蹤算法提取的特征融合到粒子濾波跟蹤框架中，并對壓縮感知提取的特征和原始粒子濾波中的顏色特征進行可信度判定，能夠較好地處理圖像序列中由于目標遮擋和光照變化所帶來的影響。此算法在公開數據庫中進行測試，實驗結果表明，提出的算法與已有改進壓縮感知跟蹤算法和粒子濾波跟蹤算法相比，魯棒性更好，能準確實時地對目標進行跟蹤。

運動目標跟蹤；粒子濾波；壓縮感知；可信度判定

0 引 言

運動目標跟蹤作為機器視覺研究領域中的一個研究熱點，已經被廣泛應用到智能人機交互、交通安全監控、醫療成像、軍事指導、天文探測、電視制作等領域。作為一個研究熱點，運動目標跟蹤針對不同的環境場景存在不同的問題，如目標旋轉、大小改變、光照變化、目標遮擋等，這些問題都給目標跟蹤帶來不同方面的難題。

近年來，針對這些問題，學者們提出了不同的跟蹤算法。文獻［1］提取了目標區域的SIFT特征并結合meanshift的跟蹤算法，較好地解決了跟蹤目標的尺度及旋轉變化的問題。文獻［2］提出的局部無序跟蹤（locally orderless tracking，LOT）算法，對于運動目標大小變化，都能有效地跟蹤。但文獻［1- 2］對于光照變化和有遮擋的運動跟蹤魯棒性有待提高。文獻［3- 5］基于粒子濾波框架實現對目標的跟蹤，粒子重采樣策略較好應對了目標被遮擋問題，但在目標環境的光照發生變化時，粒子濾波的魯棒性很差。文獻［7］基于文獻［6］的壓縮感知跟蹤（compressive tracking，CT）算法提出了改進的算法，在原始的特征提取矩陣的基礎上，生成一個提取灰度的特征提取矩陣，該算法能在目標形態和光照發生劇變等情況下準確實時地跟蹤目標。但當目標被遮擋時，改進的CT算法則由于正負樣本不斷更新，正樣本被遮擋物取代，導致遮擋后無法跟上。

視頻序列中，經常會同時出現目標遮擋和光照變化的情況，而上述算法都不能對其進行有效的跟蹤。針對上述存在的跟蹤問題，本文首先剖析了粒子濾波跟蹤和壓縮感知跟蹤算法的優缺點，而后提出了一種基于壓縮感知的粒子濾波跟蹤算法，即在粒子濾波框架下結合改進的CT算法中的壓縮感知提取特征。在公開測試庫上的實驗結果表明，提出的跟蹤算法同時解決光照變化和目標遮擋時跟蹤失敗的問題，在復雜場景下具有較好的跟蹤效果。

1 相關算法介紹

1.1 粒子濾波跟蹤算法

式中，δ（·）為狄克拉函數；N為粒子總數；k為序列幀數；i為粒子標志。

總體來說，粒子濾波跟蹤［810］主要步驟總結如下：首先隨機采樣一個粒子集并提取粒子特征；其次通過特征計算粒子權重來表示后驗密度函數，找到最相似粒子作為跟蹤目標；最后對粒子進行重采樣。

1.2 壓縮感知跟蹤算法

文獻［6］提出了基于壓縮感知的跟蹤算法，利用圖像的稀疏性和壓縮感知［1113］算法生成了一個稀疏的隨機測量矩陣，然后圖像原始特征通過向此隨機測量矩陣投影，去除了大量的冗余信息，并得到壓縮的低維特征。對這些低維特征采用樸素貝葉斯分類學習的跟蹤算法框架進行目標分類跟蹤。上述壓縮感知提取特征的公式為

式中，X∈Rm×1為目標候選區域轉換成1維后的信號；R∈Rn×m（n?m）為特征提取矩陣；V∈Rn×1為特征。而式（2）中不同的R會提取出不同的特征。文獻［6］對R定義如下：

式中，s通過平均概率在2～4中隨機選取，文獻［7］指出實際特征提取為

2 基于壓縮感知的粒子濾波算法

由于粒子濾波跟蹤算法中粒子隨機采樣和重采樣的核心思想，使得該算法對于目標有遮擋的運動有很好的跟蹤效果；但粒子濾波跟蹤算法中僅用到顏色特征，對于光照的變化魯棒性很差。而CT算法可以快速提取到低維且有效的灰度和紋理特征，有效解決粒子濾波存在的問題，然而由于對正樣本的不斷更新，導致在目標遮擋后正樣本偏離原始目標而使跟蹤丟失。因此，本文提出將CT算法中的壓縮感知提取特征融合到粒子濾波框架中，能夠同時解決視頻跟蹤過程中遮擋和光照變化的問題。本文算法流程圖如圖1所示，首先在目標區域周圍采樣兩組粒子集，利用直方圖和壓縮感知分別提取顏色特征和灰度紋理特征；其次通過直方圖距離和貝葉斯分類分別計算兩組粒子的權重；再以一定的決策方法對兩組粒子的跟蹤結果進行可信度判定來確定當前的跟蹤結果；最后進行重采樣來防止粒子退化。

圖1 本文算法流程圖

2.1 粒子濾波框架下的特征提取

第一組粒子P1利用直方圖來提取粒子特征，顏色直方圖在目標遮擋前后變化不大，并且在目標區域周圍選用了高斯分布隨機采樣，讓采樣粒子盡可能覆蓋目標的各種狀態。另外利用重采樣降低粒子退化現象，保持粒子的有效性和多樣性。因此，粒子濾波能夠有效地解決目標遮擋問題。但對于跟蹤過程中的光照變化，顏色直方圖魯棒性很差。

為了減少光照的影響，需要加入圖像灰度和紋理等特征，而這些特征的提取比較又會大大增加算法的計算量。而壓縮感知中心思想是采樣和壓縮共同進行，得到的壓縮樣本數據量遠遠小于傳統采樣所得的數據量。因此，第二組粒子P2采用壓縮感知來提取圖像灰度和紋理特征。

文獻［7］指出特征提取矩陣（見式3）每行中1和－1同時存在的概率為0.71，提取的特征更多地表現為圖像的紋理特征，紋理特征在目標形態和光照發生劇變等情況下并不穩定。為了增強跟蹤的穩定性，文獻［7］中利用式（3）生成R1，而后根據R1生成新的特征提取矩陣R2，從而利用R1和R2提取具有互補的紋理特征和灰度兩種特征。新的特征提取矩陣生成公式如下：式中，i表示特征提取矩陣R1和R2的第i行；k表示R1中第i行中第k個非零值。因此本文參考文獻［7］，將兩個特征矩陣融入到粒子濾波跟蹤框架中，對采樣的粒子集P2提取紋理特征和灰度均值特征。

2.2 粒子權重

2.2.1 提取顏色特征的粒子權重計算

本文通過計算兩組粒子的權重來表示兩個后驗密度函數。其中針對粒子集P1，本文采用經典的巴特沃斯距離來表示粒子與目標模板之間顏色直方圖的相似度（存放的是粒子的顏色直方圖），希望找到與目標顏色分布最接近的粒子。因此，巴特沃斯距離越大相似度越高，而粒子的權重也就越大。

2.2.2 提取灰度和紋理特征的粒子權重計算

針對粒子集P2，本文通過樸素貝葉斯分類器對壓縮感知提取的特征進行相似性判別，尋找與標準目標最相似的粒子。對每個樣本X∈Rm×1，它的低維表示是V∈Rn×1（n?m），假定V中的各元素是獨立分布的，構建樸素貝葉斯分類器為

其中，假設兩個類的先驗概率相等p（y＝1）＝p（y＝0），y∈｛0，1｝代表二值樣本標簽，y＝0表示負樣本，y＝1表示正樣本。文獻［14］指出高維向量隨機投影向量幾乎滿足高斯分布。所以，分類器H（V）中的條件概率p（vi｜y＝1）和p（vi｜y＝0）被假定屬于高斯分布，那么

H（V）為后驗概率，其值越大則與標準目標特征區域越相似，因此第二組粒子以H（V）值作為粒子權重。選取H（V）值最大的粒子作為新一幀的目標區域，并對相關系數和進行更新

式中，l＝1代表目標樣本，l＝0對應背景樣本；r＝1時利用R1求取特征，r＝2時利用R2計算特征；λ對應著更新率，其值越大更新越慢，保留之前特征越多。

2.3 粒子跟蹤結果決策

以兩組粒子中權重最大粒子位置作為最相似粒子位置，P1和P2的最相似粒子位置分別為pk和ck，可以確定目標的最優估計位置：lk＝αpk＋（1－α）ck。這里α是融合的權重。由于兩組粒子的特征都不能同時解決目標遮擋和光照變化的情況，因此需要有個判斷條件來調整粒子融合權值α。

對于粒子集P1采用顏色直方圖特征，粒子集越聚合，估計的目標位置方差就會越小，故基于顏色直方圖特征估計的目標位置被賦予高的可信度。當在畫面出現光照變化時，粒子空間位置會從原來較為集中變得相對分散，其位置方差隨之變大，因此當方差大于某一閾值T1時，可判定為粒子濾波不可信（本文取T1＝45），則α＝0。

對于粒子集P2采用壓縮感知提取特征，當目標被遮擋時，采樣的圖像片與負樣本更為相似，因此H（V）將突然變小，即小于某一閾值T2（本文取T2＝2），以此來判斷壓縮感知提取的特征是否可信，則α＝1。

當第一組粒子空間位置方差D和第二組壓縮感知概率值H（V）均在設定的閾值內，則代表兩組粒子都可信。對兩組粒子的結果進行歸一化來確定α取值。對于P1粒子，歸一化值為a＝（T1－D）／T1；對于P2粒子，歸一化值為b＝（H（V）－T2）／T3，T3為設定的一個壓縮感知概率中可能存在的最大值，本文取T3＝100，當b＞1時，將b置為1。那么兩組粒子的融合權重為：α＝a／（a＋b）。

2.4 粒子重采樣

粒子濾波器在歷經幾輪迭代后，大多數粒子權重都變得很小，即出現粒子退化現象，此時的粒子集將無法準確描述實際的目標后驗概率分布。為解決粒子退化問題，重采樣方法思想在保證粒子采樣總數不變的基礎下，通過復制權重較大的粒子，增多了權值大的粒子數量，消除了權值小的粒子，提高了粒子的多樣性。本文對兩組粒子都采用此重采樣方法來防止粒子的退化。

2.5 本文算法流程

概括起來本文算法主要步驟如下：

步驟1初始化跟蹤目標。手動框選初始化跟蹤區域，確定跟蹤目標。

步驟2采樣粒子。在目標區域周圍按照高斯分布采樣兩組粒子集P1和P2。

步驟3粒子特征提取。粒子集P1以顏色直方圖提取顏色特征；粒子集P2通過壓縮感知提取灰度和紋理特征。

步驟4粒子權重計算。采用巴特沃斯距離計算P1粒子與目標模板之間顏色直方圖的相似度，以確定第k幀粒子集P1各個粒子的權重；以貝葉斯分類器計算P2粒子的權重，在目標位置周圍進行采樣正負樣本，用第2.1節中提到的R1和R2，對這些樣本進行壓縮感知特征提取，得到特征向量V1和V2，使用式（6）對P2粒子集的特征向量V1和V2進行分類，以H（V）值大小作為P2粒子的權重。

步驟5確定跟蹤目標。對粒子集P1的權重進行降序排列，找到最大權重粒子作為粒子濾波的參考位置pk，并計算粒子空間位置方差D；找到粒子集P2中最大分類值Hmax的粒子作為壓縮感知的參考位置ck。

將兩組粒子的參考位置pk和ck加權：lk＝αpk＋（1－α）ck。當D＞T1時，α＝0；當Hmax＜T2時，α＝1（本文T1取45，T2取2）；當D≤T1且Hmax≥T2時，將兩組粒子的值分別歸一化為a和b，則α＝a／（a＋b）。

步驟6對兩組粒子進行重采樣，粒子權重大的位置粒子數增加，權重小的位置粒子數減少。

3 實驗結果與分析

3.1 算法實驗結果

實驗基于文獻［15］中的測試庫（http：∥visualtracking.net），該測試庫包含目標遮擋、光照變化等多種情況的視頻序列。實驗在Win7系統上利用vs2010結合OpenCV2.4.5實現本文算法、粒子濾波算法［5］和改進的CT算法［7］3種算法，并在Matlab上對實驗數據進行分析比較。

針對目標遮擋的情況，本文以序列David3為例進行分析。圖2為3種算法對David3序列中發生目標遮擋的第81幀前后序列圖像的跟蹤效果。由圖2可以看出，因目標遮擋，改進的CT算法因正樣本更新為目標遮擋物導致跟蹤錯誤，而粒子濾波算法因保留初始目標作為跟蹤模板跟蹤正確，本文提出的的自適應算法跟蹤正確。因本文算法將改進的CT算法和粒子濾波結合，根據第2.3節提到的算法可信度判定準則，依據H（V）的值判定CT算法不可信，及時將其特征排除，即只利用粒子濾波算法計算的第一組粒子位置有效地在目標遮擋后恢復跟蹤。

圖2 3種算法對David3序列的測試效果

圖3 每幀圖像P2粒子集中最相似粒子的H（V）值

圖3是本文算法中每幀P2粒子集中最相似粒子的H（V）值數據統計圖，在第81幀和第184幀時，H（V）都出現急劇變小的情況。根據第2.3節的算法可信度判定準則，判定在第81幀和第184幀時壓縮感知提取的特征不可信，而該序列正是在第81幀和第184幀處出現目標被遮擋，因此本文提出的依據H（V）的判定準則對于CT算法不可信時，能準確地進行判定。

針對光照變化的情況，本文選取序列Singer2來進行分析，Singer2是歌手在舞臺表演的視頻，其中多次出現燈光閃爍，即光照變化的情況。本文選取第11幀處的光照變化進行分析。圖4是3種算法在視頻序列中出現光照變化的第11幀前后序列圖像的跟蹤效果。

由圖4可以看出，在第11幀處由于光照變化導致標準位置模板與目標模板相似度低，導致后續幀（如第33幀）基于粒子濾波跟蹤失敗；而改進CT算法由于正樣本的不斷更新，在后續幀（如第33幀）跟蹤結果正確。本文算法根據第2.3節提到的算法可信度判定準則，通過計算粒子集P1粒子位置方差判定粒子P1失效，自動利用粒子集P2壓縮感知的粒子位置估計準確地跟蹤到了目標。

圖4 3種算法對Singer2序列的測試效果

圖5中可以明顯看到，第11幀處，粒子位置方差有突然變大的現象，可見本文采用粒子位置方法作為粒子濾波對于光照變化不可信的判定準則是可行的。因此，本文算法能有效利用改進的CT算法對于光照變化的魯棒性，很好地在燈光閃爍等光照變化環境下對目標進行跟蹤。

圖5 每幀圖像粒子空間位置方差

圖2和圖4也說明了，本文提出的融入壓縮感知特征的粒子濾波算法能同時解決目標遮擋和光照變化兩個問題，較單一的粒子濾波算法和改進CT算法取得了更佳的跟蹤效果。

3.2 算法性能評估

評估跟蹤算法的性能，除了視覺上看到的跟蹤效果，在跟蹤數據上也有一定的評估方法。文獻［15］中提出的對跟蹤算法性能評估的方法，能夠從準確率和成功率兩方面對算法進行客觀的評估。

為進一步評估本文提出的算法，利用文獻［15］的測試評估方法及給出測試庫對本文算法、改進的CT算法和粒子濾波算法進行測試。將錯誤閾值設置為0～50，重疊閾值設置為0～1。對于測試庫中25個視頻共16 970幀，3種算法的準確率和成功率曲線如圖6所示。從圖中可以看出，本文算法在總體上準確率和成功率都優于改進的CT算法和粒子濾波算法。在圖6（a）中，當錯誤閾值大于8時，本文算法的準確率就一直高于另外兩種算法。另外，由于本文將兩種算法的跟蹤結果作平均，所以在較小錯誤閾值范圍內，準確率稍微偏低一點。但結合了兩種算法的核心思想后，本文算法對于目標遮擋和光照變化都有較好的跟蹤效果，因此整體上的準確率也就相應地提高了。同理，在圖6（b）中，本文算法的成功率整體上高于改進的CT算法和粒子濾波算法，但當重疊閾值大于0.6時，成功率略有偏低。

圖6 3種算法的性能評估圖

另外，算法運算速度也是評價跟蹤算法的標準之一。本文對David3（640×480），Singer2（624×352），Dudek（720 ×480），Boy（640×480）等4個不同分辨率的視頻序列進行測試（測試環境CPU：Intel Core i3＠2.3GHz，RAM：4GB），計算出3種算法對每幀圖像的平均運算時間，如表1所示。可以看出，加入壓縮感知提取的特征后，本文算法運算速度仍然滿足跟蹤實時性要求。本文算法對每幀圖像運算時間僅比粒子濾波算法慢2～3 ms，這是由于加入的壓縮感知提取的特征數據量極少，整個算法運算速度幾乎不受影響。本文還將CT算法的每幀采樣圖像片用粒子濾波的每幀重采樣替換，運算量比CT算法降低很多，因此每幀圖像的運算速度比CT算法提高了一倍。

表1 算法運行速度比較 ms／fp

4 結 論

針對目標跟蹤存在目標遮擋和環境光照變化的情況，本文提出將改進的CT算法中的壓縮感知特征融合入粒子濾波框架中。由于利用壓縮感知提取灰度和紋理特征，使得在圖像信號壓縮后數據量大大減少的情況下，可以有效地緩解光照變化對目標跟蹤的影響。而粒子濾波中采用了顏色直方圖特征，以及隨機采樣和重采樣的核心思想，從而能在目標有遮擋的情況下，對其進行有效的跟蹤。因此，融入壓縮感知特征的粒子濾波算法在運算速度并沒有降低的情況下，能同時解決目標遮擋和光照變化兩個問題，從而提高了算法的魯棒性。未來，如何自適應地調節判定算法可信度的閾值來使跟蹤算法更為穩定是本文的研究重點。

［1］Zhao Q J，Zhang Y，Zhao D B.A scale and rotation adaptive algorithm for object tracking［J］.Journal of Central South University-Science and Technology，2013，44（6）：2354- 2360.（趙欽君，張勇，趙東標.一種尺度和旋轉自適應的目標跟蹤算法［J］.中南大學學報（自然科學版），2013，44（6）：2354- 2360.）

［2］Oron S，Bar-Hillel A，Levi D，et al.Locally orderless tracking［C］∥Proc.of the IEEEConference on Computer Vision and Pattern Recognition，2012：1940- 1947.

［3］Nummiaro K，Koller-Meier E，Van Gool L.An adaptive colorbased particle filter［J］.Image and Vision Computing，2003，21（1）：99- 110.

［4］Mei X，Ling H.Robust visual tracking and vehicle classification via sparse representation［J］.IEEE Trans.on Pattern Analysis and Machine Intelligence，2011，33（11）：2259- 2272.

［5］Hess R，Fern A.Discriminatively trained particle filters for complex multi-object tracking［C］∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition，2009：240- 247.

［6］Zhang K，Zhang L，Yang M H.Real-time compressive tracking［C］∥Proc.of the 12th European Conference on Computer Vision，2012：864 -877.

［7］Zhu Q P，Yan J，Zhang H，et al.Real-time tracking using multiple features based on compressive sensing［J］.Optics and Precision Engineering，2013，21（2）：437- 443.（朱秋平，顏佳，張虎，等.基于壓縮感知的多特征實時跟蹤［J］.光學精密工程，2013，21（2）：437- 443.）

［8］Hu S Q，Jing Z L.Overview of particle filter algorithm［J］.Control and Decision，2005，20（4）：361- 365.（胡士強，敬忠良.粒子濾波算法綜述［J］.控制與決策，2005，20（4）：361- 365.）

［9］Sanjeev A M，Maskell S，Gordon N，et al.A tutorial on particle filters for online nonlinear／non-Gaussian Bayesian tracking［J］.IEEE Trans.on Signal Processing，2002，50（2）：174- 188.

［10］Djuric P M，Kotecha J H，Zhang J，et al.Particle filtering［J］.IEEE Trans.on Signal Processing Magazine，2003，20（5）：19- 38.

［11］Donoho D.Compressed sensing［J］.IEEE Trans.on Information Theory，2006，52（4）：1289- 1306.

［12］Candes E，Tao T.Near optimal signal recovery from random projections and universal encoding strategies［J］.IEEE Trans. on Information Theory，2006，52（12）：5406- 5425.

［13］Candes E，Wakin M.An introduction to compressive sampling［J］.IEEE Trans.on Signal Processing Magazine，2008，25（2）：21- 30.

［14］Diaconis P，Freedman D.Asymptotics of graphical projection pursuit［J］.The Annals of Statistics，1984，12（3）：793- 815.

［15］Wu Y，Lim J，Yang M H.Online object tracking：a benchmark［C］∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition，2013：2411- 2418.

吳凌琳（199-0- ），通信作者，女，碩士研究生，主要研究方向為圖像處理、視頻智能分析。

E-mail：carinel＠163.com

楊 磊（1960- ），男，教授，主要研究方向為安防領域、視頻分析。

E-mail：yanglei＠cuc.edu.cn

Particle filtering tracking based on compressive sensing

WU Xiao-yu，WU Ling-lin，YANG Lei
（School of Information Engineering，Communication University of China，Beijing 100024，China）

To deal with the target occlusion problem and illumination changes in moving target tracking，a particle filtering algorithm based on compressive sensing is proposed.The extracted features are added by compressive sense of the improved compressive tracking（CT）algorithm into the framework of particle filtering tracking.The credibility of extracted features including the color features of original particle filtering and compressive sensing features is judged，which deals with the target occlusion effects and illumination changes.The algorithm is tested in public database and experimental results show that the proposed algorithm brings about better robustness and tracks targets accurately in real time in comparison with the improved CT algorithm and particle filtering algorithm.

moving target tracking；particle filter；compressive sensing；credibility judge

TN 911.73

A

10.3969／j.issn.1001-506X.2015.11.30

吳曉雨（1979- ），女，副教授，博士，主要研究方向為圖像處理、視頻智能分析。

E-mail：wuxiaoyu＠cuc.edu.cn

1001-506X（2015）11-2617-06

2014- 12- 29；

2015- 04- 24；網絡優先出版日期：2015- 07- 06。

網絡優先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150706.1705.015.html

國家科技支撐計劃（2014BAH10F00，2012BAH01F01- 01）資助課題