基于P-N跟蹤器的自適應粒子濾波算法

薛亞陽，李晉惠，肖 鋒

（1.西安工業大學 計算機科學與工程學院，陜西 西安 710032;2.西安工業大學 理學院，陜西 西安 710032）

粒子濾波算法因為在非線性、非高斯模型中的良好表現，近年來在目標跟蹤問題中得到廣泛應用[1]。此類算法多是和目標顏色特征結合以基于模型的方法實現對目標的跟蹤。但仍存在一定問題，歸結如下：1）跟蹤穩健性不夠，當背景與目標接近時容易出現錯跟、丟失等情況。2）粒子衰退和運算量大的問題，粒子濾波算法對樣本數量過于依賴，由大樣本量來保證跟蹤精度，當樣本較少時，精度便相應降低。

針對以上問題，筆者提出了結合P-N跟蹤器的自適應粒子濾波算法。首先在跟蹤系統中引入了P-N跟蹤器，對目標進行實時跟蹤并給出對跟蹤準確性的估計，以此作為目標物體的初次定位依據。針對粒子退化問題，在粒子濾波算法過程中充分利用P-N跟蹤器的跟蹤結果，由P-N跟蹤器跟蹤結果的準確性來控制粒子濾波算法中粒子采樣的范圍以及采樣數目的多少。這樣在保證粒子質量的情況下控制粒子數量，從而有效地消除了粒子退化現象，降低了運算量。

1 粒子濾波概述

1.1 SIS 粒子濾波算法

SIS是一種用蒙特-卡洛仿真來實現遞歸的貝葉斯濾波器的方法。其關鍵在于用一組帶權值的樣本來表示/計算后驗概率密度。

如果有樣本點{xk-1（i）：i=1，…，N}，及相應權值{wk-1（i）：i=1，…，N}。那么k時刻的后驗概率可以表示為：

其中 δ（）為 Dirac delta 函數；wk（i）為對應粒子的權值，其值由重要性采樣[2]的原則來得到。

由于p（xk|Dk）通常難以采樣，因此引入重要性函數的概念：q（）是與 p（xk|Dk）同分布的概率密度函數，且易于從中采樣。根據Smith與Gelfand的研究結果[3]，重要性權值可以由式

得到。為了構成迭代過程，將重要性采樣函數分解代入式（2）中，得到權值的遞推公式[4]：

算法過程描述如下：

步驟1：從重要性函數中隨機抽樣n個粒子；

步驟2：依照式進行權值更新；

步驟3：依照式計算系統狀態值；

步驟4：重復以上步驟，直到過程結束。

1.2 SIR粒子濾波算法

SIS算法里存在問題是粒子衰退。粒子衰退指經過多次迭代，選取的粒子樣本集的方差越來越大。這意味著其中有大量的粒子權值極小，幾乎對近似系統狀態的概率分布起不到作用，而大量的計算依然花費在這些粒子上。文獻[5]指出粒子衰退問題是不可避免的。

目前解決方案有兩種：1）選取更好的重要性函數，以提高的粒子的質量。2）加入重采樣過程。重采樣是指在SIS的每一步迭代中，對粒子的重要性權值進行分析，復制一些權值大的粒子，淘汰一些權值小的粒子，從而使粒子集里的粒子質量得以提高，可以更好的描述系統的概率分布。

2 P-N學習與P-N跟蹤器

P－N學習是新近由Zdenek Kalal[6]等人提出的一種改善二元分類器（Binary classifier）性能的機制。其思路為：首先用給定的目標模板，來訓練一個初始分類器（classifier），用該分類器對圖像序列中的數據進行標記；然后由目標信息和背景信息的結構性（Constructural）來構造約束條件，用約束條件識別被分類器錯誤標記的數據改變其標記（label）；最后將改正后的樣本加入到樣本訓練集（Training Set）中，重新訓練分類器。通過上以上過程的不斷迭代，使分類器的性能不斷改善。流程如圖1所示。

圖1 P－N學習過程Fig.1 Process of P－N learning

在文獻[6]中，Zdenek Kalal等人用實驗證明了P－N跟蹤器在實時視頻跟蹤中效果良好：不僅定位更加準確，響應時間短，同時對于目標丟失后再次回到跟蹤視野內時的情況，也具有再次識別目標的能力。因此，若粒子濾波算法的重采樣過程能充分利用P－N跟蹤器定位的結果，參考目標位置信息來確定合理的重采樣策略，其改善空間將會是可觀的。

3 自適應重采樣策略

文獻[7]提出了一種基于Mean－Shift迭代的自適應重抽樣。先用Mean－Shift迭代確定候選目標中心位置yc，k，再用Bhattacharyya系數判斷候選目標分布與模板分布q之間的相似性。若y）值大，說明目標模板與候選目標相似度高，所以可在目標中心yc，k較近的范圍內采樣相對少量的粒子，保證跟蹤的實時性；若值較小，說明相似度低，所以相應的yc，k相對較寬的范圍內來采樣，采樣數量適當增大，保證跟蹤的準確性。該重采樣策略取得了良好的跟蹤效果，在解決粒子退化問題和定位準確度上都有較好的效果。受此成果的鼓勵與啟發，進行了本文重采樣策略的研究。算法過程如下：

步驟一：用P－N跟蹤器確定當前幀候選目標位置，記錄該位置的置信度（confidence）。

步驟二：根據置信度 （confidence）Cconfi進行自適應重采樣，即動態確定粒子采樣范圍R與采樣數量N。

設跟蹤區域的中心為T（x，y），則該中心應該是后驗概率分布最密集的區域，重采樣的粒子應該集中于該區域。通過實驗數據分析，當Cconfi＞80%時，可以認為P－N跟蹤器的結果是準確的，即跟蹤區域包含了大部分的目標。因此采取80%作為閥值，當 Cconfi＞80%時，為了保證跟蹤的實時性，在 T（x，y）附近抽取的粒子數量可較少，位置以T（x，y）為中心范圍可相對集中。 當 Cconfi＜80%，為確保跟蹤的準確性，在 T（x，y）附近的抽樣粒子數理可較多，范圍可放寬。

具體策略為：選取的重要性函數為 q（xk（i）|xk－1（i））=μt，μ～N（0，。 每當置信度下降 5%，則將以 T（x，y）為圓心的原始采樣區域的半徑（RPN）擴大20%（本文采取較為積極的策略，根據具體實驗環境該可以適當放大、縮小），同時將粒子數量N采樣區域半徑的線性關系可以表述為：

若用N表示重采樣粒子數量，則N應該隨著Rr的增大而增大，隨著Rr的減小而減小。實驗證明，線性關系即可滿足變化的需要：隨著搜索區域半徑的變化，將粒子數量進行同比例的增加/減小。

4 跟蹤實例及分析

如圖 2所示，以人臉面對攝像頭從左往右慢慢移動，移出攝像頭視野再往右重新進入攝像頭視野的實時跟蹤畫面。其中目標逐漸移出攝像頭視野，導致跟蹤難度增大。

圖2 本文算法的跟蹤過程Fig.2 Tracking process of the solution

可看到，在背景不復雜的室內，本文算法跟蹤效果良好。跟蹤區域（圖中圓形）幾乎完全包括了目標，并能保證目標處于跟蹤區域的中心。從第5幅圖像開始，目標逐漸移出攝像頭的捕捉范圍，但跟蹤框始終包圍畫面中目標可見部分，這表明對于部分遮擋、嚴重遮擋的情況依然能保證良好的跟蹤效果。在第8幅圖像中，目標完全脫離視野，此時跟蹤框停留在最后目標出現的位置，并錯誤的將背景里與目標相近的箱子鎖定。但在第10幅圖，當目標重新回到攝像頭視野時，跟蹤框迅速跟上，重新將目標鎖定。這得益于P-N跟蹤器基于窗口搜索的目標檢測策略和P-N學習機制提供的對目標模板學習更新的能力。跟蹤過程中粒子數目的變化情況如表1所示。

表1 粒子數目N的變化情況Tab.1 Change of particle number N

由表1可以看出，本算法在初始粒子數目設為50的情況下，可以根據實時跟蹤狀況及時地調整粒子數目。在第8、10、12幀，因為目標運動平穩，所以重采樣時粒子數目呈逐步下降的走勢。在第13幀時降到最低點，粒子數目只有37。在第15幀時，由于目標部分離開了攝像頭視野，粒子數目相應升高到70。證實重采樣策略起了作用，以較多的粒子數目來保證跟蹤的準確性。接下來，粒子數目下降為60并保持不變。這是因為目標已經完全脫離跟蹤視野，跟蹤框錯誤鎖定了與目標顏色相近的靜態背景。在第45幀，當目標重新回到跟蹤視野時，跟蹤框重新將目標鎖定，重采樣粒子數目又恢復到與初始值50相近水平，為47個。可以推測，在接下來，目標如果運動平衡并且不出現遮擋情況，粒子數目有繼續下降的空間。

5 結 論

針對實時目標跟蹤難點問題[8]，本文提出了基于P-N跟蹤器的自適應粒子濾波算法。首先構造P-N跟蹤器對目標進行跟蹤，確定目標的范圍區域與置信度；在粒子濾波階段，依據P-N跟蹤器輸出結果，動態調節粒子重采的樣范圍和數量，實現了重采樣的自適應過程。通過對攝像頭實時捕捉運動人臉的實驗，證明本文算法在解決粒子退化問題與調節粒子數目方面有較好的效果。由于結合P-N跟蹤器的優點，一定程度上解決了目標丟失后重新捕捉的問題。

[1]Kwok C， Fox D， Meila M.Real-time particle filters[J].Proceedings of the IEEE， 2004（92）:469-84.

[2]Doucet A，Andrieu C，Fitzgerald W.Bayesian filtering for hidden Markov modelsvia Monte Carlo methods[C]//Proceedings of the 1998 8th IEEE Workshop on Neural Networks for Signal Processing VIII，1998:194-203.

[3]Smith AFM，Gelfand AE.Bayesian statistics without tears:A sampling-resampling perspective [J]. The American Statistician， 1992（46）:84-88.

[4]Arulampalam MS，Maskell S，Gordon N，et al.A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking[J].IEEE Transactions on Signal Processing.2002（50）:174-88.

[5]Doucet A，Godsill S，Andrieu C.On sequential Monte Carlo sampling methods for Bayesian filtering[J].Statistics and Computing， 2000（10）:197-208.

[6]Kalal Z， Matas J， Mikolajczyk K.P-N learning:Bootstrapping binary classifiers by structural constraints[C]//2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2010:49-56.

[7]姚紅革，齊華，郝重陽.復雜情形下目標跟蹤的自適應粒子濾波算法[J].電子與信息學報， 2009，31（2）:275-278.YAO Hong-ge.Visual target tracking based on the adaptive particle filter in the complete situation[J].Journal of Electronics&Information Technology，2009，31（2）:275-278.

[8]竇永梅，冀小平，杜肖山.基于粒子群算法和卡爾曼濾波的運動目標跟蹤算法[J].現代電子技術，2011(08):133-136.DOU Yong-mei，JI Xiao-ping，DU Xiao-shan.Tracking algorithm ofmoving objectbased on particle swarm optimization and Kalman filter [J].Modern Electronics Technique,2011(08):133-136.