基于粒子群優化算法的目標跟蹤方法

高 翔 李志浩

（甘肅聯合大學 電子信息工程學院，蘭州 730000）

0 引言

在視頻監控系統中，實現對目標物快速、準確的跟蹤，首先必須提取到目標物區別于背景的明顯特征。目標跟蹤中，常提取的特征有顏色、紋理、形狀，輪廓和運動等，它們各自有其特有的優缺點。傳統的目標跟蹤中，一般只提取目標物的單一特征來對其進行跟蹤，有時很難實現準確的跟蹤效果。本文擬采用顏色與運動特征相融合，建立多特征融合的觀測模型，來克服提取單一特征所造成的跟蹤失敗。

常用的跟蹤濾波算法是卡爾曼濾波以及擴展卡爾曼濾波，對于濾波假定的目標狀態應該遵循高斯分布，因此通過卡爾曼濾波方程估計的均值向量和協方差矩陣能夠完全刻畫目標的行為。然而許多因素可能導致非線性、非高斯分布的出現，如復雜的目標運動模型和系統狀態表示方式，而最常見的原因是由于圖像中雜物的存在而導致觀測密度是非線性的。本文所采用的粒子濾波其完全適用于非線性，非高斯的環境，可以克服卡爾曼濾波的缺點。基于蒙特卡羅方法和遞推貝葉斯估計的統計濾波方法依據大數定理采用蒙特卡羅方法來求解貝葉斯估計中的積分運算是粒子濾波的基本原理。基本原理是：先根據系統狀態向量的經驗條件分布在狀態空間產生一組隨機樣本的集合，樣本被稱為粒子，接著依據測量值調整粒子的權重和位置，通過調整后的粒子信息完善已經建立的經驗條件分布。

盡管粒子濾波有著卡爾曼濾波無法比擬的優點，但它自身也存在著一定的缺點。如由于隨著時間的延長重要性權重的方差逐漸遞增，使粒子的權重慢慢集中到個別粒子上，也可能在經過幾次遞歸后，系統中只剩一個粒子具有非零權值，其它粒子的權值太小，我們忽略不計，更新那些不起作用的粒子浪費了大量的計算工作，而產生實際的后驗概率分布無法表達的退化問題；重采樣技術被用來克服退化問題，我們復制權值較大的粒子，剔除權值較小的粒子時又使粒子的多樣性特征降低，引來了粒子匱乏的問題。本文提出了一種基于粒子群優化算法的改進粒子濾波算法，這種算法驅動粒子向高似然區域遷移，克服粒子退化與匱乏問題有效方法就是增加粒子的多樣性。

1 特征提取

對目標進行準確跟蹤的前提是能夠準確的檢測到目標，如何準確檢測到目標的核心問題是如何精確地提取到目標物區別與背景的獨特特征。傳統的目標跟蹤系統中，一般只提取目標物單一特征來對其進行識別，當背景較為復雜或目標物被遮擋時往往很難把目標物提取出來。近些年來提取目標多個特征來對其進行跟蹤成為科研者們研究的重點。

2 模型建立

2.1 狀態轉移模型

使用粒子濾波進行目標跟蹤時，為了描繪目標在兩幀之間的運動特性首先要針對目標建立一個系統模型即狀態轉移模型，模擬狀態變量的進化規律。

目標運動狀態 由目標在 平面上的位置和速度組成：

其中， 表示目標的中心， 表示目標的速度。

本文采用二階自回歸模型做為目標狀態轉移模型：

2.2 多特征融合的觀測模型

對目標進行準備跟蹤的前提是獲取被跟蹤目標的準備信息，并充分利用這些信息建立目標的模型。本文選用顏色與紋理信息構建系統的觀測模型。那么如何衡量每個參考目標直方圖 和候選目標直方圖 之間的相似度呢?

Bhattacharyya(BH)距離測度系數[1]是一個很優的解決方案， Bhattacharyya系數可以定義為：

兩個分布之間的距離為：

可定義顏色特征的距離為：

紋理距離為：

似然函數為：

得到序列圖像的似然分布 是跟蹤算法的關鍵，由于本文的跟蹤算法使用了自適應的多特征融合，每個濾波粒子的觀測值都由顏色和紋理兩部分組成，自適應的融合兩者的似然函數形成最終的觀測似然函數 。

因為分布距離 越小相似度越高，我們得到的觀測信息就越多，而特征能提供的信息就更精確，定義 為最小距離，則利用各個特征的最小距離定義分布系數：

3 粒子群優化算法原理

粒子群優化算法(Particle Swarm Op tim ization,PSO)是在1995年由Kennedy和Eberhart提出的[3]。它是一種模擬鳥群飛行覓食的行為，當一只鳥發現食物，并飛向食物時，其它鳥也跟隨著這只鳥飛向食物，形成鳥群。PSO算法是一種有效的全局尋優算法，通過個體間的競爭與合作所產生的群體智能指導優化搜索。它把每個個體看作是在n維空間中飛行的沒有體積和重量的微粒，其飛行速度由個體的飛行經驗和整體的飛行經驗進行調整。

我們可以描述PSO算法為，隨機初始化一個粒子群(數量為 )，其中，第 個粒子在 維空間表示成：

速度為：

每一次迭代，通過下面兩個極值來更新粒子的速度和所在位置：

第一個極值是粒子本身從開始到當前迭代次數搜索所產生的最優解，稱為個體極值

第二個極值稱為全局極值，是該種群當前最優解， 。時，算法局部搜索能力較強；大時，算法全局搜索能力較強。為[0,1]之間的隨機數。

每個粒子根據找到的兩個最優值，通過下式更新粒子速度和位置：

4 粒子群優化算法改進粒子濾波算法

眾所周知粒子濾波算法本身無法克服粒子退化與粒子匱乏問題，在實際應用中有一定的局限性。由于沒有考慮到當前的量測值產生粒子退化現象，真實后驗概率密度采樣得到的樣本與重要性密度函數中取得的樣本存在較大偏差，特別是當似然函數位于先驗概率的尾部或呈尖峰狀態時，這種偏差更明顯[5]。粒子匱乏問題是因為引入了重采樣方法來克服退化問題，這樣的做法使系統復制權值較大的粒子，刪除權值較小的粒子，最終讓粒子的多樣性減少。

本文將PSO算法引入到粒子濾波中，把采樣種群中的粒子看成濾波粒子，向高似然區域驅動粒子的移動，可以增加有效的粒子數，從而提高粒子多樣性，實現有效克服粒子退化與粒子匱乏問題的目的。算法具體實現步驟敘述如下：

Step1 取得量測值：

其中 為最新觀測值， 為預測觀測值[6]。

Step2 初始化：

重要性密度函數取轉移先驗概率：

Step3 重要性權值計算：

根據最新量測值更新當前粒子權值[7]：

根據下式利用粒子群優化算法來更新每個粒子的位置與速度，使粒子陸續向真實狀態逼近[8]。

Step4 權值歸一化：

Step5 重采樣過程將

原來的帶權粒子重采樣[9]，得等權粒子：

Step6 狀態估計：

PSOPF算法流程圖如圖1所示。

圖1 PSOPF算法流程圖

5 改進算法實驗結果分析

為了客觀驗證本文給出的粒子群優化粒子濾波算法的優越性，本文對標準粒子濾波和粒子群優化粒子濾波進行了對比實驗。本文采用Matlab對算法進行仿真，算法模型如下：

粒子數目設N=100，仿真中的量測噪聲方差設R=1，過程噪聲方差設Q=10，仿真次數設為50次，時間步長設為為50，最大迭代次數做為算法結束條件，設n=50次。

兩種算法單次實驗的仿真如圖2所示，兩種算法的殘差變化情況如圖3所示，表1給出了兩種算法實驗50次的數據平均值：

圖2 PSOPF和PF單次仿真實驗圖 圖3 PSOPF和PF殘差圖

表1 濾波數據統計表

通過圖2所示的估計仿真圖，比起PF算法，PSOPF算法實現了更精確描繪粒子真實狀態的目的。如圖3所示殘差[10]圖中顯示，PSOPF的波動變化最小，說明它的估計值和真實量測值比較接近，也可以說PSOPF的估計精度是高于PF算法的。根據表1對實驗數據的平均值統計，可看出兩種算法的估計時間相差不大，因為PSOPF算法的標準誤差最小，可證明PSOPF算法在估計時間沒有太大變化的情況下，能夠有效地提高算法精度。

6 仿真實驗結果分析

為了驗證PSOPF目標跟蹤方法，本文選用校園散步者圖像，通過四幀自拍圖像序列做目標跟蹤實驗。實驗在Pen tium(R) 4 CPU 2.6GHz、內存1G的PC機上實現，我們采用MATLAB 7.0軟件平臺。圖4和圖5為PF和PSOPF算法在第1幀、第43幀，第102幀和第168幀的跟蹤情況。

由以上實驗結果可以看出，傳統的粒子濾波沒有對采樣粒子進行有效處理，在逼近目標狀態時會產生較大誤差，隨著時間的推移系統所追蹤的目標與真實目標逐漸偏離。本文給出的PSOPF算法通過不斷更新粒子的速度與位置對其進行優化，有效地抑制了粒子的退化與匱乏現象，能夠較好的覆蓋跟蹤區域，可以較好的提高跟蹤性能。

圖5 PSOPF算法的目標跟蹤

7 結論

為了能夠有效地克服粒子退化與粒子匱乏問題，我們利用粒子群算法把種群中的粒子看成濾波粒子，通過粒子群算法的快速收斂能力和全局搜優能力，為提高粒子多樣性，驅動粒子向高似然區域移動，增加了有效粒子數。實驗結果顯示，本文所示的改進算法能夠較好的覆蓋跟蹤區域，降低了計算時間，較明顯的提高了跟蹤準確程度。

[1] Pitt M K, Shephard N. Filtering via sim u lation:Auxiliary particle filters [J].J of the Am erican Statistical Association,1999,94(2):590-599.

[2] Belviken E,Acklam P J. Monte Carlo filters for non-linear state estim ation[J].Autom atica,2001,37(1):177-183.

[3] 孫俊.量子行為粒子群優化:原理及其應用[M].清華大學出版社.2011.

[4] 曾建潮,介婧,崔志華. 微粒群算法[M]. 科學出版社.2004.

[5] 王國宏.先驗概率和似然函數未知時的分布式檢測融合[J]. 電光與控制.2004.

[6] Kenned y J,Eberhart RC.Particle Sw arm Op tim izati onProcoftheIEEE ternational ConferenceonNeuraltworks[J].Perth,Australia,1995:1942-1948.

[7] 康健,張仲凱,芮國勝.基于均值漂移粒子濾波的目標跟蹤算法研究[J].2009.

[8] Reyno lds C W. Flocks,Herds and Schools: A Distributed Behavioral Model. Com puterGraphics[J].1987,1(4):25-34.

[9] Angeline P J.Using Selection to Im p rove Particle Sw arm Op tim ization//Proc of the IEEE International Con ference on Evo lu tionary Com p u tation.An cho rage[J].USA,1998:84-89.

[10] 王敏.殘差分析在統計中的應用[J].江蘇統計.2000.