基于均值漂移采樣調(diào)整和積分直方圖表達的粒子濾波跟蹤算法

白 俊 郭賀彬

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

這些年來，粒子濾波算法的應用主要在于視頻追蹤方面［1-2］。粒子濾波算法可以有效處理非線性、非高斯狀態(tài)估計的問題，適合在環(huán)境復雜的情況下對目標的跟蹤。粒子跟蹤算法在應用中常見問題如下:

(1)粒子濾波跟蹤算法需要很長的運算時間，難以滿足實時性的要求。

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

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

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

(2)原算法中使用直方圖進行統(tǒng)計工作，新算法中用粒子所在的矩形區(qū)域4個頂點的積分直方圖進行加減運算，從而避開重復的計算，節(jié)省運算時間。

1 標準的粒子濾波算法流程

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

步驟1 粒子初始化:

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

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

設定k=k+1

步驟3 重采樣:

步驟4 輸出:

狀態(tài)估計:

方差估計:

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

2 均值漂移算法與視頻目標跟蹤

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

3 改進的算法

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

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

步驟1 初始化:

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

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

其中b(xi)表示顏色xi對應的直方圖bin。

步驟5 計算新位置:

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

步驟7 更新粒子位置:

步驟8 迭代:

3.2 圖像的積分直方圖表達

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

3.3 算法描述

3.3.1 運動模型

在本文中，對運動目標用一個矩形窗口來表示，目標的狀態(tài)定義為:

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

常規(guī)的視頻序列中的目標運動通常是非線性的，例如，行人可能在前進的時候突然停下或者轉(zhuǎn)彎。為了使狀態(tài)估計具有通用性，本文采用隨機游走模型描述目標的運動。

式中:Wk-1是一個多變量高斯噪聲且各個變量相互獨立。

3.3.2 觀測模型

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

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

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

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

3.3.3 算法描述

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

步驟1 初始化:k=0

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

(2)FOR l=1，…，N

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

END FOR

步驟 2 FOR k=1，2，…

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

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

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

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

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

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

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

END FOR

(3)計算重要性權(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個粒子的集合{|i=1，2，…，N}，并重新分配粒子權(quán)值==1/N。

END FOR

3.4 實驗結(jié)果及分析

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

圖1是對PETS2001視頻庫中的一段視頻的跟蹤，以說明均值漂移操作對粒子分布的影響。通過對比，可以看出，均值漂移后，粒子集中到目標周圍。

圖1 均值漂移前后粒子的分布對比圖

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

使用Highway II采集的視頻，對該視頻分別使用積分直方圖和普通直方圖方法進行跟蹤，比較它們在跟蹤過程中直方計算的時間。跟蹤用的計算機CPU為雙核Intel Xeon 3 GHz，內(nèi)存為2 G。

首先，固定粒子數(shù)為100，不同大小的目標對計算消耗時間的影響見表1。為簡單起見，假設所有粒子的大小都相同。

表1 普通直方圖和積分直方圖計算耗時對比1

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

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

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

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

表2 普通直方圖和積分直方圖計算消耗時間對比2

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

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

4 結(jié)語

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

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

通過圖像的積分直方圖表達方法，可以減少在計算大量粒子的直方圖中產(chǎn)生的冗余，將粒子的直方圖計算變?yōu)閷αＷ游恢玫?個頂點的積分直方圖的線性組合。實驗表明，改進后的算法比標準粒子濾波算法效率更高，收斂速度更快。隨著粒子數(shù)增多，粒子所在區(qū)域面積越大，本算法的優(yōu)勢越明顯。

［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］單勇.復雜條件下視頻運動目標檢測和跟蹤［D］.長沙:國防科技大學，2006.

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

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

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

［7］張波.基于粒子濾波的圖像跟蹤算法研究［D］.上海:上海交通大學，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.