基于粒子群優(yōu)化算法的目標(biāo)跟蹤方法

高 翔 李志浩

（甘肅聯(lián)合大學(xué) 電子信息工程學(xué)院，蘭州 730000）

0 引言

在視頻監(jiān)控系統(tǒng)中，實(shí)現(xiàn)對目標(biāo)物快速、準(zhǔn)確的跟蹤，首先必須提取到目標(biāo)物區(qū)別于背景的明顯特征。目標(biāo)跟蹤中，常提取的特征有顏色、紋理、形狀，輪廓和運(yùn)動等，它們各自有其特有的優(yōu)缺點(diǎn)。傳統(tǒng)的目標(biāo)跟蹤中，一般只提取目標(biāo)物的單一特征來對其進(jìn)行跟蹤，有時(shí)很難實(shí)現(xiàn)準(zhǔn)確的跟蹤效果。本文擬采用顏色與運(yùn)動特征相融合，建立多特征融合的觀測模型，來克服提取單一特征所造成的跟蹤失敗。

常用的跟蹤濾波算法是卡爾曼濾波以及擴(kuò)展卡爾曼濾波，對于濾波假定的目標(biāo)狀態(tài)應(yīng)該遵循高斯分布，因此通過卡爾曼濾波方程估計(jì)的均值向量和協(xié)方差矩陣能夠完全刻畫目標(biāo)的行為。然而許多因素可能導(dǎo)致非線性、非高斯分布的出現(xiàn)，如復(fù)雜的目標(biāo)運(yùn)動模型和系統(tǒng)狀態(tài)表示方式，而最常見的原因是由于圖像中雜物的存在而導(dǎo)致觀測密度是非線性的。本文所采用的粒子濾波其完全適用于非線性，非高斯的環(huán)境，可以克服卡爾曼濾波的缺點(diǎn)?；诿商乜_方法和遞推貝葉斯估計(jì)的統(tǒng)計(jì)濾波方法依據(jù)大數(shù)定理采用蒙特卡羅方法來求解貝葉斯估計(jì)中的積分運(yùn)算是粒子濾波的基本原理?；驹硎牵合雀鶕?jù)系統(tǒng)狀態(tài)向量的經(jīng)驗(yàn)條件分布在狀態(tài)空間產(chǎn)生一組隨機(jī)樣本的集合，樣本被稱為粒子，接著依據(jù)測量值調(diào)整粒子的權(quán)重和位置，通過調(diào)整后的粒子信息完善已經(jīng)建立的經(jīng)驗(yàn)條件分布。

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

1 特征提取

對目標(biāo)進(jìn)行準(zhǔn)確跟蹤的前提是能夠準(zhǔn)確的檢測到目標(biāo)，如何準(zhǔn)確檢測到目標(biāo)的核心問題是如何精確地提取到目標(biāo)物區(qū)別與背景的獨(dú)特特征。傳統(tǒng)的目標(biāo)跟蹤系統(tǒng)中，一般只提取目標(biāo)物單一特征來對其進(jìn)行識別，當(dāng)背景較為復(fù)雜或目標(biāo)物被遮擋時(shí)往往很難把目標(biāo)物提取出來。近些年來提取目標(biāo)多個(gè)特征來對其進(jìn)行跟蹤成為科研者們研究的重點(diǎn)。

2 模型建立

2.1 狀態(tài)轉(zhuǎn)移模型

使用粒子濾波進(jìn)行目標(biāo)跟蹤時(shí)，為了描繪目標(biāo)在兩幀之間的運(yùn)動特性首先要針對目標(biāo)建立一個(gè)系統(tǒng)模型即狀態(tài)轉(zhuǎn)移模型，模擬狀態(tài)變量的進(jìn)化規(guī)律。

目標(biāo)運(yùn)動狀態(tài) 由目標(biāo)在 平面上的位置和速度組成：

其中， 表示目標(biāo)的中心， 表示目標(biāo)的速度。

本文采用二階自回歸模型做為目標(biāo)狀態(tài)轉(zhuǎn)移模型：

2.2 多特征融合的觀測模型

對目標(biāo)進(jìn)行準(zhǔn)備跟蹤的前提是獲取被跟蹤目標(biāo)的準(zhǔn)備信息，并充分利用這些信息建立目標(biāo)的模型。本文選用顏色與紋理信息構(gòu)建系統(tǒng)的觀測模型。那么如何衡量每個(gè)參考目標(biāo)直方圖 和候選目標(biāo)直方圖 之間的相似度呢?

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

兩個(gè)分布之間的距離為：

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

紋理距離為：

似然函數(shù)為：

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

因?yàn)榉植季嚯x 越小相似度越高，我們得到的觀測信息就越多，而特征能提供的信息就更精確，定義 為最小距離，則利用各個(gè)特征的最小距離定義分布系數(shù)：

3 粒子群優(yōu)化算法原理

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

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

速度為：

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

第一個(gè)極值是粒子本身從開始到當(dāng)前迭代次數(shù)搜索所產(chǎn)生的最優(yōu)解，稱為個(gè)體極值

第二個(gè)極值稱為全局極值，是該種群當(dāng)前最優(yōu)解， 。時(shí)，算法局部搜索能力較強(qiáng)；大時(shí)，算法全局搜索能力較強(qiáng)。為[0,1]之間的隨機(jī)數(shù)。

每個(gè)粒子根據(jù)找到的兩個(gè)最優(yōu)值，通過下式更新粒子速度和位置：

4 粒子群優(yōu)化算法改進(jìn)粒子濾波算法

眾所周知粒子濾波算法本身無法克服粒子退化與粒子匱乏問題，在實(shí)際應(yīng)用中有一定的局限性。由于沒有考慮到當(dāng)前的量測值產(chǎn)生粒子退化現(xiàn)象，真實(shí)后驗(yàn)概率密度采樣得到的樣本與重要性密度函數(shù)中取得的樣本存在較大偏差，特別是當(dāng)似然函數(shù)位于先驗(yàn)概率的尾部或呈尖峰狀態(tài)時(shí)，這種偏差更明顯[5]。粒子匱乏問題是因?yàn)橐肓酥夭蓸臃椒▉砜朔嘶瘑栴}，這樣的做法使系統(tǒng)復(fù)制權(quán)值較大的粒子，刪除權(quán)值較小的粒子，最終讓粒子的多樣性減少。

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

Step1 取得量測值：

其中 為最新觀測值， 為預(yù)測觀測值[6]。

Step2 初始化：

重要性密度函數(shù)取轉(zhuǎn)移先驗(yàn)概率：

Step3 重要性權(quán)值計(jì)算：

根據(jù)最新量測值更新當(dāng)前粒子權(quán)值[7]：

根據(jù)下式利用粒子群優(yōu)化算法來更新每個(gè)粒子的位置與速度，使粒子陸續(xù)向真實(shí)狀態(tài)逼近[8]。

Step4 權(quán)值歸一化：

Step5 重采樣過程將

原來的帶權(quán)粒子重采樣[9]，得等權(quán)粒子：

Step6 狀態(tài)估計(jì)：

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

圖1 PSOPF算法流程圖

5 改進(jìn)算法實(shí)驗(yàn)結(jié)果分析

為了客觀驗(yàn)證本文給出的粒子群優(yōu)化粒子濾波算法的優(yōu)越性，本文對標(biāo)準(zhǔn)粒子濾波和粒子群優(yōu)化粒子濾波進(jìn)行了對比實(shí)驗(yàn)。本文采用Matlab對算法進(jìn)行仿真，算法模型如下：

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

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

圖2 PSOPF和PF單次仿真實(shí)驗(yàn)圖 圖3 PSOPF和PF殘差圖

表1 濾波數(shù)據(jù)統(tǒng)計(jì)表

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

6 仿真實(shí)驗(yàn)結(jié)果分析

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

由以上實(shí)驗(yàn)結(jié)果可以看出，傳統(tǒng)的粒子濾波沒有對采樣粒子進(jìn)行有效處理，在逼近目標(biāo)狀態(tài)時(shí)會產(chǎn)生較大誤差，隨著時(shí)間的推移系統(tǒng)所追蹤的目標(biāo)與真實(shí)目標(biāo)逐漸偏離。本文給出的PSOPF算法通過不斷更新粒子的速度與位置對其進(jìn)行優(yōu)化，有效地抑制了粒子的退化與匱乏現(xiàn)象，能夠較好的覆蓋跟蹤區(qū)域，可以較好的提高跟蹤性能。

圖5 PSOPF算法的目標(biāo)跟蹤

7 結(jié)論

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

[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] 孫俊.量子行為粒子群優(yōu)化:原理及其應(yīng)用[M].清華大學(xué)出版社.2011.

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

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

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

[7] 康健,張仲凱,芮國勝.基于均值漂移粒子濾波的目標(biāo)跟蹤算法研究[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] 王敏.殘差分析在統(tǒng)計(jì)中的應(yīng)用[J].江蘇統(tǒng)計(jì).2000.