基于粒子分組優化的自適應跟蹤算法

劉振濤， 王朝英， 劉衛群

(1.空軍工程大學電訊工程學院，西安 710077; 2.中國人民解放軍63751部隊技術室，西安 710028)

0 引言

序列圖像中運動目標跟蹤技術是計算機視覺領域的一個重要課題，在視頻監控、物體識別、人機界面等領域中有著廣泛的應用前景［1］。運動目標跟蹤的難點在于對復雜環境中非剛性運動目標的跟蹤。目標的輪廓和所處背景復雜，目標發生旋轉或被遮擋等都對跟蹤造成不同程度上的影響［2］。

粒子濾波是一種基于蒙特卡羅仿真的遞推貝葉斯估計方法，常用于解決非線性、非高斯噪聲環境下的狀態估計問題［3］。粒子濾波算法因其在目標跟蹤領域中良好的魯棒性，受到廣大學者的關注，相應的改進算法層出不窮［4－6］。

粒子濾波算法中，系統狀態的后驗分布由一組帶有權值的離散采樣(稱為粒子)來表達。經過若干幀跟蹤后常常會出現粒子退化現象，而解決這一問題的有效方法之一就是對粒子進行重采樣。但伴隨而來的負面作用就是粒子衰竭，特別是當觀測值比較準確或似然函數位于先驗概率分布尾部時，在權值更新之后很多粒子的權值都變得很小［7］。導致個別具有較大權值的粒子在濾波過程中被多次選擇，從而喪失了粒子的多樣性［8］。因此如何防止粒子退化并保持粒子多樣性就成為了解決重采樣問題的關鍵。現有的重采樣方法主要有:重要性重采樣、殘差重采樣、分層重采樣、優化組合重采樣等等［9－11］。

針對上述問題，本文提出一種基于特征區分度量化分析和粒子分組優化的自適應粒子濾波跟蹤算法。首先提出一種新的背景區分度量化分析準則，通過計算目標與背景的特征顯著性和相似性二者間比值關系，提取出背景區分度較高的候選特征建立目標概率分布直方圖。并針對每一幀所有粒子的不同分布情況，以其當前幀所得權值為度量標準，采用復制、線性組合、淘汰等不同形式對粒子進行分組重采樣，實現對粒子數量和位置分布的自適應調整。使得粒子性能得到優化，提高算法的魯棒性。

1 傳統粒子濾波算法

粒子濾波算法的基本思想是蒙特卡羅模擬，其中狀態的后驗密度由一組具有權值的粒子來近似。除了初始化之外，對于圖像序列中的每一幀，算法主要包括4步:采樣、計算權值、輸出和重采樣［12］。具體算法如下所述。

1)初始化。當時刻k=0時，從先驗密度函數p(x0)中提取N個樣本點x(i)0，設置初始權值為

3)計算權值并歸一化。計算粒子的權值為

權值歸一化。

4)輸出階段。

6)k=k+1，若繼續跟蹤轉到步驟2)，否則算法結束。

2 自適應粒子濾波算法

本文在傳統粒子濾波算法的基礎上，分別從特征直方圖的建立和粒子重采樣策略兩個角度對原有算法進行改進。

2.1 特征直方圖

在建立特征直方圖的過程中，必須選取那些使得目標與背景之間具有良好區分度的特征［13］。本文綜合考慮特征顯著性與相似性兩個因素建立一種新的區分度量化分析準則，選取兩個區分度最大的候選特征，將二者的區分度量化所得數值作為權值，而該權值則決定了目標直方圖中所選特征區間數。

2.1.1 特征區分度量化分析

對于一個給定的特征，假定Hobj(i)和Hbg(i)分別表示該特征下的目標和背景直方圖，將其與對應的像素數相除后，得到下面兩個概率分布函數為:p(i)=Hobj(i)/nobj和 q(i)=Hbg(i)/nbg，nobj和 nbg分別表示目標和背景區域內的像素數。對于每一個特征值i，采用式(5)的對數似然比值得到顯著性函數，并采用相應的方差來衡量目標區域與背景區域之間的顯著性［14］。式(5)中ε為接近于0的極小值，本文取0.0001，保證除數不會出現為0的情況，式(6)中E(·)表示求均值，var(·)表示求方差。

同時根據目標加權直方圖和背景加權直方圖的BH系數來判斷目標與背景的相似性，選取BH系數小的候選特征建立模型進行跟蹤［15］。類似于目標模型與目標候選模型的相似性計算方法，得到目標與背景的加權直方圖的相似性計算公式為

其中:p(i)為目標加權直方圖中i分量的概率分布函數;q(i)為背景加權直方圖中i分量的概率分布函數。

為了提取出使得目標與背景顯著性大、相似度小的候選特征，建立如式(8)所示的二者比值關系式。M值越大則說明待測特征的背景區分度越高，反之區分度越低。

2.1.2 確定特征區間數

在建立目標特征直方圖的過程中，如果對特征區間數分得過細，會影響算法的實時性，特別是融合多特征建立直方圖時，但是如果對特征區間分的過于稀疏，則違背了引入多特征進行跟蹤的初衷［16］。本文以特征的目標與背景區分度作為權值，來決定所選特征的區間數。

由特征區分度量化分析可得兩個M值最大的候選特征，將兩者的M值作為權值，按式(9)、式(10)所示確定所選的區間數N1、N2為

其中，M1、M2分別為所選特征分量的區分度量化數值。

2.2 粒子重采樣策略

在粒子重采樣的過程中，對于粒子數量的選取以及粒子分布位置的調整是提高算法魯棒性的關鍵［17］，既要防止粒子退化問題，同時又要保持粒子的多樣性［18］，對于每一幀跟蹤過程中的粒子不同分布情況，應相應采取不同的重采樣策略。基于這一思想，本文提出一種新的粒子采樣策略，通過預先設定的粒子數閾值來判定當前幀粒子分布情況，主要是分析當前幀具有較大權值粒子的數量，共分為大權值粒子數較多、適中和較小3種情況進行討論，再把每個粒子權值與預先設定的粒子權值閾值進行比較，并采用復制、線性組合、淘汰等不同形式對該粒子進行調整。

首先設定當前幀粒子數為N，粒子權值閾值為ωpre、ωpre1、ωpre2，粒子數閾值為 npre1，npre2。再統計權值大于ωpre的粒子個數n，按照3種情況分別進行討論。

粒子分布情況1，當n≥npre1時，此時大權值粒子較多。

1) 若 ωi＜ωpre1，淘汰該粒子。

2) 若 ωi≥ωpre1，得到該粒子復制數 ωi×N，分布位置不變。

粒子分布情況2，當npre2≤n＜npre1時，此時大權值粒子數量適中。

1)若ωi＜ωpre1，淘汰該粒子，并統計該組粒子數n1。

2) 若 ωpre1≤ωi＜ ωpre2，按照式(11)調整該粒子分布位置，并統計該組粒子數n2。

其中:xni為該粒子分布位置;xnj為第3組粒子的分布位置;n3為第3組粒子數。

粒子分布情況3，當n＜npre2時，此時大權值粒子較少。

1)若ωi≥ωpre1，粒子保留，但不復制，并統計該組粒子數n0。

2)若ωi＜ωpre1，按照式(12)調整該粒子分布位置。

其中:xni為該粒子分布位置;xnj為上一組粒子的分布位置。

2.3 算法具體流程

Step 1 在第一幀手動確定跟蹤目標的中心位置;

Step 2 選取經由背景區分度分析所得的候選特征建立特征直方圖，并初始化粒子集;

Step 3 從建議性分布采樣得到新的粒子集，計算權值，并歸一化;

Step 4 輸出階段，由各個粒子線性加權計算新的目標中心位置;

Step 5 按照2.2節重采樣策略對粒子進行重采樣;

Step 6 若繼續跟蹤則轉到Step 3，否則算法結束。

3 仿真結果及分析

本文選取兩段測試視頻對給定的運動目標進行跟蹤實驗。首先，對顏色空間特征中的H(色調)分量、S(飽和度)分量、I(亮度)分量以及梯度特征、紋理特征的背景區分度進行量化分析，結果如表1、表2所示，實驗1中顏色空間特征的H分量和梯度特征的M值較大，實驗2中顏色空間特征的H分量和S分量的M值較大，因而選擇相應的特征建立目標直方圖。同時列出本文所用參數值表格，如表3所示。最后通過不同情況下的多組測試實驗驗證所提跟蹤方法的有效性。

表1 實驗1特征區分度分析表Table 1 Figure discrimination table of test 1

表2 實驗2特征區分度分析表Table 2 Figure discrimination table of test 2

表3 本文參數表Table 3 Parameter table

實驗1為辦公室內人臉跟蹤視頻序列(500幀，像素大小為128*96)。第88幀時，跟蹤目標發生旋轉，第314幀時，視頻中出現相似目標，如圖1所示，本文算法利用新的粒子重采樣策略優化了粒子分布，能夠較好地定位跟蹤目標，同時融合梯度特征建立目標直方圖，提高算法對顏色相似目標的鑒別性。

圖1 相似顏色目標跟蹤結果Fig.1 Tracking result of similar color target

實驗2為行人監控錄像視頻序列(120幀，像素大小為352*288)。如圖2所示，第39幀、第57幀、第81幀目標被遮蔽物連續遮擋，本文算法中的重采樣策略較好地保證了粒子的多樣性，即使受到遮擋，當目標重新出現時也能夠迅速準確地搜尋目標的正確位置。

圖2 連續多幀遮擋情況下目標跟蹤結果Fig.2 Tracking result of sequential multi-frame occlusion

4 結束語

針對粒子濾波算法中粒子退化問題，本文提出一種基于粒子分組優化的自適應跟蹤算法。在傳統粒子濾波算法的基礎上，分別從特征直方圖的建立和粒子重采樣策略兩個角度進行了改進。綜合利用特征顯著性和相似性對候選特征背景區分度進行量化分析，并以區分度為權值確定直方圖中所選特征的區間數，提高算法的魯棒性。同時通過分析每一幀粒子的具體分布情況，對粒子的數量和分布位置進行分組自適應調整。最后通過大量視頻序列驗證了本文算法對運動目標跟蹤的精度。

［1］ WANG J Q，YA S S.Integrating shape and color features for adaptive real-time object tracking［C］//Proceedings of the 2006 IEEE International Conference on Robotics and Biomimetics，2006:1-6.

［2］ 李金，胡文廣.基于顏色的快速人體跟蹤及遮擋處理［J］.智能系統學報，2010，5(4):353-359.

［3］ 趙豐，湯磊，張武，等.一種高實時性粒子濾波重采樣算法［J］.系統仿真學報，2009，21(18):5789-5793.

［4］ BOGDAN K.Finding location using a particle filter and histogram matching［C］//Poland:Proceedings of Artificial Intelligence and Soft Computing，2004:786-791.

［5］ 梁曉龍，馮金富，楊嘯天，等.基于集群智能粒子濾波的彈道導彈跟蹤［J］.電光與控制，2009，16(7):29-33.

［6］ BOLIC M，DJURIC P M，SANGJIN H.Resampling algorithms and architectures for distributed particle filters［C］//USA:IEEE Transactions on Signal Processing，2005:2442-2450.

［7］ 吳川，楊冬，郝志成.基于粒子濾波的彩色圖像跟蹤［J］.光學精密工程，2009，17(10):2542-2547.

［8］ 曾偉，朱桂斌，陳杰，等.多特征融合的魯棒粒子濾波跟蹤算法［J］.計算機應用，2010，30(3):643-646.

［9］ 劉杰，董育寧.基于預測和粒子濾波的運動目標跟蹤算法［J］.計算機工程與科學，2009，31(10):30-32.

［10］ 夏克寒，許化龍，張樸睿.粒子濾波的關鍵技術及應用［J］.電光與控制，2005，12(6):1-4.

［11］ 張淼，胡建旺，周云鋒，等.粒子濾波的重采樣方法［J］.火力與指揮控制，2009，34(10):18-21.

［12］ 張濤，費樹岷，李曉東，等.基于色彩相關直方圖的粒子濾波跟蹤算法［J］.系統仿真學報，2009，21(17):5422-5426.

［13］ COLLINS R T，LIU Y.Online selection of discriminative tracking features［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27(10):1631-1643.

［14］ 尹宏鵬，柴毅，匡金駿，等.一種基于多特征自適應融合的運動目標跟蹤算法［J］.光電子·激光，2010，21(6):917-923.

［15］ 汪沁，江淑紅，張建秋，等.提高Mean-shift跟蹤算法性能的方法［J］.復旦學報:自然科學版，2007，46(1):85-90.

［16］ 齊飛，羅予頻，胡東成.基于均值漂移的視覺目標跟蹤方法綜述［J］.計算機工程，2007，33(21):24-27.

［17］ 云廷進，郭永彩，高潮.基于粒子Mean Shift遷移的紅外人體目標跟蹤算法［J］.計算機學報，2009，32(6):1222-1228.

［18］ 姚紅革，雷松澤，齊華，等.基于自適應粒子濾波的紅外目標跟蹤［J］.光子學報，2009，38(6):1507-1511.