白 俊 郭賀彬

(北京京北職業(yè)技術(shù)學(xué)院機(jī)電工程系，北京 101400)

這些年來(lái)，粒子濾波算法的應(yīng)用主要在于視頻追蹤方面［1-2］。粒子濾波算法可以有效處理非線性、非高斯?fàn)顟B(tài)估計(jì)的問(wèn)題，適合在環(huán)境復(fù)雜的情況下對(duì)目標(biāo)的跟蹤。粒子跟蹤算法在應(yīng)用中常見(jiàn)問(wèn)題如下:

(1)粒子濾波跟蹤算法需要很長(zhǎng)的運(yùn)算時(shí)間，難以滿足實(shí)時(shí)性的要求。

(2)粒子濾波算法的另一個(gè)缺點(diǎn)是退化現(xiàn)象［1］。經(jīng)過(guò)多次迭代后，大量的粒子只集中了較小的權(quán)值，它們對(duì)后驗(yàn)概率的估計(jì)不起作用，這樣浪費(fèi)了大量的計(jì)算時(shí)間。

為了解決退化現(xiàn)象問(wèn)題并縮短計(jì)算時(shí)間，本文提出了一種改進(jìn)的粒子濾波算法。改進(jìn)之處說(shuō)明如下:

(1)對(duì)每個(gè)原始粒子，比較其本身和對(duì)該粒子進(jìn)行均值漂移搜索調(diào)整后得到的新粒子的特征，選擇其中更接近目標(biāo)原始分布特征的粒子作為調(diào)整后的分布粒子，提高收斂速度。

(2)原算法中使用直方圖進(jìn)行統(tǒng)計(jì)工作，新算法中用粒子所在的矩形區(qū)域4個(gè)頂點(diǎn)的積分直方圖進(jìn)行加減運(yùn)算，從而避開(kāi)重復(fù)的計(jì)算，節(jié)省運(yùn)算時(shí)間。

1 標(biāo)準(zhǔn)的粒子濾波算法流程

粒子濾波算法的步驟如下:

步驟1 粒子初始化:

采樣x0i～p( x0)，即根據(jù)p( x0)分布采樣得到x0i，i=1，2，…，N。

步驟2 重要性權(quán)值計(jì)算:

設(shè)定k=k+1

步驟3 重采樣:

步驟4 輸出:

狀態(tài)估計(jì):

方差估計(jì):

步驟5 判斷跟蹤是否結(jié)束，若跟蹤結(jié)束則退出本算法，否則返回步驟2。

2 均值漂移算法與視頻目標(biāo)跟蹤

均值漂移是一種基于非參數(shù)的核密度估計(jì)理論，是在概率空間中求解概率密度極值的優(yōu)化算法。均值漂移算法已廣泛應(yīng)用于目標(biāo)跟蹤領(lǐng)域［3-7］。Dorin Comaniciu等人以加權(quán)顏色直方圖作為目標(biāo)特征，表示相似度的Bhattacharyya距離最大，等價(jià)于求概率密度極值，從而將均值漂移算法應(yīng)用于目標(biāo)跟蹤領(lǐng)域［8］。

3 改進(jìn)的算法

3.1 粒子的均值漂移采樣調(diào)整

在本文算法中，均值漂移算法被用來(lái)調(diào)整采樣粒子的位置。粒子的均值漂移采樣調(diào)整算法的流程如下:

步驟1 初始化:

步驟3 計(jì)算Bhattacharyya系數(shù):

步驟4 計(jì)算權(quán)值:{wi}i=1，…，nh

其中b(xi)表示顏色xi對(duì)應(yīng)的直方圖bin。

步驟5 計(jì)算新位置:

步驟6 計(jì)算Bhattacharyya系數(shù):

步驟7 更新粒子位置:

步驟8 迭代:

3.2 圖像的積分直方圖表達(dá)

圖像的積分直方圖匹配算法如下:

3.3 算法描述

3.3.1 運(yùn)動(dòng)模型

在本文中，對(duì)運(yùn)動(dòng)目標(biāo)用一個(gè)矩形窗口來(lái)表示，目標(biāo)的狀態(tài)定義為:

式中:u，v—表示矩形的中心位置;w，h— 表示矩形的長(zhǎng)和寬。

常規(guī)的視頻序列中的目標(biāo)運(yùn)動(dòng)通常是非線性的，例如，行人可能在前進(jìn)的時(shí)候突然停下或者轉(zhuǎn)彎。為了使?fàn)顟B(tài)估計(jì)具有通用性，本文采用隨機(jī)游走模型描述目標(biāo)的運(yùn)動(dòng)。

式中:Wk-1是一個(gè)多變量高斯噪聲且各個(gè)變量相互獨(dú)立。

3.3.2 觀測(cè)模型

將顏色分布做觀測(cè)模型。目標(biāo)區(qū)域的顏色分布用離散化的顏色柱狀圖表示，柱狀圖分割(bin)取為B。假設(shè)候選目標(biāo)區(qū)域的狀態(tài)變量為X，中心坐標(biāo)y=(u，v)，{x(i)}i=1，…，n是區(qū)域內(nèi)像素點(diǎn)的位置，bin(xi)表示xi在直方圖中的顏色索引值，那么區(qū)域顏色概率分布(X)={(X)，b=1，…，B}計(jì)算為

其中δ表示Delta函數(shù)。

目標(biāo)區(qū)域的顏色分布也可以按照上述步驟求出，表示為 ^q={qb，b=1，…，B}。我們用 Bhattacharryya系數(shù)來(lái)定義候選區(qū)域和目標(biāo)區(qū)域的相似程度，兩個(gè)顏色分布的Bhattacharryya系數(shù)定義為:

相似度函數(shù)定義為:

3.3.3 算法描述

本文提出的基于積分直方圖和均值漂移采樣的粒子濾波跟蹤算法如下:

步驟1 初始化:k=0

(1)計(jì)算圖像目標(biāo)的普通直方圖{qu}u=1，…，m

(2)FOR l=1，…，N

從先驗(yàn)概率p(x0)中采樣{x(l)0}

END FOR

步驟 2 FOR k=1，2，…

(1)圖像積分的直方圖的計(jì)算

(2)粒子均值漂移采樣FOR l=1，…，N

①重要性采樣x(l)k～p(xk|x(l)k-1)

②根據(jù)x(l)k的4個(gè)頂點(diǎn)的積分直方圖，計(jì)算普通直方圖 {pu}u=1，…，m

④均值漂移采樣調(diào)整，對(duì)x(l)k進(jìn)行均值漂移調(diào)整，得到x'(l)k

⑤根據(jù)x'(l)k的4個(gè)頂點(diǎn)的積分直方圖，計(jì)算普通直方圖 {p'u}u=1，…，m

⑦如果ρ'＜ρ，則令x(l)k=x'(l)k

END FOR

(3)計(jì)算重要性權(quán)值FOR l=1，…，N

END FOR

(4)歸一化重要性權(quán)值FOR l=1，…，N

END FOR

(5)粒子重采樣FOR l=1，…，N

從{x(i)k|i=1，2，…，N}集合中根據(jù)權(quán)值重新采樣得到新的N個(gè)粒子的集合{|i=1，2，…，N}，并重新分配粒子權(quán)值==1/N。

END FOR

3.4 實(shí)驗(yàn)結(jié)果及分析

3.4.1 均值漂移采樣調(diào)整

圖1是對(duì)PETS2001視頻庫(kù)中的一段視頻的跟蹤，以說(shuō)明均值漂移操作對(duì)粒子分布的影響。通過(guò)對(duì)比，可以看出，均值漂移后，粒子集中到目標(biāo)周圍。

圖1 均值漂移前后粒子的分布對(duì)比圖

3.4.2 積分直方圖和普通直方圖計(jì)算耗時(shí)的對(duì)比1(粒子數(shù)固定)

使用Highway II采集的視頻，對(duì)該視頻分別使用積分直方圖和普通直方圖方法進(jìn)行跟蹤，比較它們?cè)诟欉^(guò)程中直方計(jì)算的時(shí)間。跟蹤用的計(jì)算機(jī)CPU為雙核Intel Xeon 3 GHz，內(nèi)存為2 G。

首先，固定粒子數(shù)為100，不同大小的目標(biāo)對(duì)計(jì)算消耗時(shí)間的影響見(jiàn)表1。為簡(jiǎn)單起見(jiàn)，假設(shè)所有粒子的大小都相同。

表1 普通直方圖和積分直方圖計(jì)算耗時(shí)對(duì)比1

通過(guò)對(duì)比普通直方圖的計(jì)算耗時(shí)(第二列)和積分直方圖的計(jì)算耗時(shí)(第五列)可以看出，粒子較小時(shí)，普通直方圖比積分直方圖的耗時(shí)稍短一些;粒子較大時(shí)，普通直方圖的耗時(shí)約是積分直方圖的10倍;粒子很大時(shí)，積分直方圖計(jì)算耗時(shí)比普通直方圖計(jì)算耗時(shí)要少很多。

3.4.3 普通直方圖和積分直方圖計(jì)算耗時(shí)的對(duì)比2(粒子大小固定)

在粒子大小(37×46)固定的條件下，積分直方圖和普通直方圖計(jì)算耗時(shí)的對(duì)比見(jiàn)表2。當(dāng)粒子數(shù)從20增加到1 000時(shí)，普通直方圖的計(jì)算耗時(shí)急劇增加;而積分直方圖的計(jì)算耗時(shí)變化較小。

上述分析表明，粒子越大，粒子數(shù)越多，粒子可能出現(xiàn)的區(qū)域就越大，采用積分直方圖計(jì)算的優(yōu)勢(shì)越明顯。

表2 普通直方圖和積分直方圖計(jì)算消耗時(shí)間對(duì)比2

3.4.4 本文算法與傳統(tǒng)粒子濾波跟蹤算法的效果對(duì)比

圖2是對(duì)ATON視頻庫(kù)的Highway II視頻的第118幀的跟蹤結(jié)果。采用本文算法，使用較少的粒子數(shù)(20)就可以得到較好的效果。

4 結(jié)語(yǔ)

通過(guò)對(duì)粒子的均值漂移采樣調(diào)整，在標(biāo)準(zhǔn)粒子濾波跟蹤算法的基礎(chǔ)上，提出基于均值漂移采樣調(diào)整和積分直方圖表達(dá)的粒子濾波跟蹤算法，使得粒子集中于其鄰近的局部極大值區(qū)域內(nèi)，減少退化現(xiàn)象的發(fā)生。

圖2 不同粒子數(shù)對(duì)原算法和本文算法的影響對(duì)比

通過(guò)圖像的積分直方圖表達(dá)方法，可以減少在計(jì)算大量粒子的直方圖中產(chǎn)生的冗余，將粒子的直方圖計(jì)算變?yōu)閷?duì)粒子位置的4個(gè)頂點(diǎn)的積分直方圖的線性組合。實(shí)驗(yàn)表明，改進(jìn)后的算法比標(biāo)準(zhǔn)粒子濾波算法效率更高，收斂速度更快。隨著粒子數(shù)增多，粒子所在區(qū)域面積越大，本算法的優(yōu)勢(shì)越明顯。

［1］Arulampalam M，Maskell S，Gordon N.A Tutorial on Particle Filters for Online Nonlinear/non-gaussian Bayesian Tracking ［J］.IEEE Transactions on Signal Processing，2002，50(2):174-188.

［2］Gunnarsson F，Bergman N.Particle Filter for Positioning，Navigation，and Tracking［J］.IEEE Transactions on Signal Processing，2002，50(2):425-437.

［3］單勇.復(fù)雜條件下視頻運(yùn)動(dòng)目標(biāo)檢測(cè)和跟蹤［D］.長(zhǎng)沙:國(guó)防科技大學(xué)，2006.

［4］盧曉鵬.視頻序列中目標(biāo)跟蹤技術(shù)研究［D］.北京:中國(guó)科學(xué)院研究生院，2007.

［5］李安平.復(fù)雜環(huán)境下的視頻目標(biāo)跟蹤算法研究［D］.上海:上海交通大學(xué)，2006.

［6］賈靜平.圖像序列中目標(biāo)跟蹤技術(shù)研究［D］.西安:西北工業(yè)大學(xué)，2006.

［7］張波.基于粒子濾波的圖像跟蹤算法研究［D］.上海:上海交通大學(xué)，2007.

［8］Comaniciu D，Ramesh V，Meer P.Real-time Tracking of Non-rigid Objects Using Mean Shift［C］.Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Hiltom Head，SC，USA，2000:142-149.