基于粒子濾波架構(gòu)的實(shí)時目標(biāo)跟蹤算法研究

孟軍英，劉教民，韓 明，王 娟

（1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.石家莊學(xué)院 計算機(jī)系，河北 石家莊 050035）

在視頻序列圖像中，對感興趣的目標(biāo)進(jìn)行跟蹤，獲取其各種運(yùn)動參數(shù)及運(yùn)動軌跡的問題，稱為目標(biāo)跟蹤.目標(biāo)跟蹤可以分為基于參數(shù)估計的跟蹤和基于狀態(tài)估計的跟蹤兩種[1].基于參數(shù)估計的典型跟蹤算法是Camshift算法，該算法具有跟蹤速度快及可以收斂至局部極值的優(yōu)點(diǎn)，但在跟蹤過程中發(fā)生相似顏色干擾、背景復(fù)雜等情況時，容易收斂于非目標(biāo)，導(dǎo)致跟蹤失敗.基于狀態(tài)估計的濾波可以分為針對線性隨機(jī)系統(tǒng)估計問題的線性濾波和針對非線性隨機(jī)系統(tǒng)的非線性濾波.在線性濾波問題上，最著名的就是Kalman濾波器.對于線性和高斯的系統(tǒng)狀態(tài)空間模型Kalman濾波器是一個線性無偏的最小方差估計器，可以提供可靠的解析解[2].但是，現(xiàn)實(shí)世界中多數(shù)系統(tǒng)是非線性、非高斯或包含有非線性、非高斯的因素.因此，目前大量的研究工作都集中在非線性濾波中，并發(fā)展出了多種有效算法，其中最具代表性的有擴(kuò)展卡爾曼濾波（Extended Kalman Filter，EKF）、Unscented卡爾曼濾波（UKF）、粒子濾波器（Particle Filter）等.其中，EKF算法是將非線性狀態(tài)函數(shù)和觀測函數(shù)進(jìn)行局部線性化（一階泰勒級數(shù)展開），然后再進(jìn)行Kalman濾波.EKF要求隨機(jī)系統(tǒng)的狀態(tài)分布是高斯的，對于許多實(shí)際的系統(tǒng)其仍是一種近似精度只有一階的非線性高斯濾波器，對強(qiáng)非線性系統(tǒng)濾波精度低.1993年N.Gordon等人提出一種自舉粒子濾波（Bootstrap）算法，采用蒙特卡洛(Monte Carlo)模擬方法中的序貫重要性采樣（SIS）方法依據(jù)大數(shù)定理來求解貝葉斯估計中的積分運(yùn)算，適用于任何能用狀態(tài)空間模型描述的非線性系統(tǒng)，精度可以逼近最優(yōu)估計[3].它為分析非線性動態(tài)系統(tǒng)提供了一種有效的解決方法，從而得到了廣泛的關(guān)注.

但是，為了逼近最優(yōu)估計，提高跟蹤的準(zhǔn)確性，通常需要大量的粒子，而粒子數(shù)的增加會使計算量成級數(shù)增加，算法實(shí)時性變差.目前在這一領(lǐng)域的優(yōu)化算法主要有自適應(yīng)粒子濾波（adaptiveparticle filter，APF）.APF主要思想是讓粒子數(shù)目隨信號環(huán)境的變化而適應(yīng)改變，從而減少冗余粒子，降低算法的復(fù)雜度和計算量，但其粒子數(shù)受權(quán)值方差影響比較大，粒子間的相關(guān)性強(qiáng)，難以并行實(shí)現(xiàn).RTPF多采用減少粒子集中的粒子數(shù)、丟棄數(shù)據(jù)或組合數(shù)據(jù)的方法來提高算法的實(shí)時性，在實(shí)現(xiàn)上可能會由于粒子數(shù)不足而導(dǎo)致濾波發(fā)散.因此，找到一種在保證濾波精度前提下的實(shí)時性粒子濾波算法，成為目前對粒子濾波算法優(yōu)化的主要方向.

本文在粒子濾波的基本架構(gòu)上，選取EKF產(chǎn)生的高斯分布作為重要性概率密度函數(shù)，使粒子分布更接近實(shí)際的后驗(yàn)分布，然后，應(yīng)用Camshift算法，使粒子向真實(shí)后驗(yàn)分布進(jìn)一步聚集，使有效粒子增多，排除權(quán)值過小的無效粒子，從而提高算法效率.

1 粒子濾波基本架構(gòu)

動態(tài)狀態(tài)空間模型分為狀態(tài)轉(zhuǎn)移模型 |1和觀測模型 | ，其中 為系統(tǒng)在 時刻的狀態(tài)變量， 為系統(tǒng)在 時刻的測量值.對于非線性、非高斯過程，其模型可表示為

其中： 與 分別為過程噪聲和觀測噪聲，并且相對獨(dú)立、協(xié)方差分別為 和 的零均值加性噪聲序列； : , : 為有界非線性映射.假設(shè)系統(tǒng)的狀態(tài)轉(zhuǎn)移是一個Markov過程，那么

在時刻 的后驗(yàn)概率密度可近似表示為

大多數(shù)情況下，直接從0:|1:抽樣十分困難，所以一般從與其同分布的重要性函數(shù)0:|1:抽取樣本[3]，此時權(quán)值定義為

分解后，權(quán)值更新公式如下

后驗(yàn)概率密度的加權(quán)近似為

粒子濾波算法一個不可避免的問題就是權(quán)值退化.經(jīng)過多次迭代，大多數(shù)粒子的權(quán)值變得很小，狀態(tài)空間中的有效粒子越來越少，大量的計算浪費(fèi)在對估計后驗(yàn)濾波概率分布幾乎不起作用的粒子更新上，使得跟蹤性能下降.針對此問題，Gordon等人提出了重采樣方法[4].其基本思想是通過對概率密度函數(shù)重新采樣，過濾掉權(quán)值較小的粒子，復(fù)制權(quán)值大的粒子.但是，如果不斷復(fù)制權(quán)值大的粒子，不可避免的出現(xiàn)樣本枯竭問題，損失信息，因此可以在重采樣前根據(jù)一定準(zhǔn)則判斷是否需要進(jìn)行重采樣.考慮到實(shí)時性，目前常用的準(zhǔn)則是通過有效粒子數(shù) 與閥值 的關(guān)系來進(jìn)行判定.

2 實(shí)時粒子濾波算法設(shè)計

粒子濾波的跟蹤精度與采樣的粒子數(shù)目成正比，粒子數(shù)目增加會使計算復(fù)雜度大大增加，實(shí)時性變差.因此，本文將EKF和Camshift算法嵌入到粒子濾波架構(gòu)，從重要性概率密度函數(shù)選取以及粒子聚類兩方面優(yōu)化粒子濾波算法，提高其實(shí)時性.

2.1 重要性概率密度函數(shù)的選取

無論是從提高實(shí)時性或是避免樣本枯竭角度考慮，重要性密度函數(shù)的選擇都是一個十分關(guān)鍵的問題．選擇可以滿足重要性權(quán)值的方差最小原則，但在實(shí)際應(yīng)用中，由于目標(biāo)概率密度并不能寫成一般的解析式，所以直接從中抽取樣本幾乎是不可能實(shí)現(xiàn)的．目前，多數(shù)應(yīng)用選取先驗(yàn)分布作為重要性函數(shù)，即．但由于先驗(yàn)分布并未包含 時刻的最新測量值，因而產(chǎn)生的粒子常常位于后驗(yàn)分布的尾部，使得權(quán)值變化較大，容易導(dǎo)致濾波發(fā)散，而且當(dāng)似然函數(shù)的高似然區(qū)域出現(xiàn)在先驗(yàn)概率分布的尾部時，還會出現(xiàn)退化現(xiàn)象，并且在隨后的離散分布重采樣過程中極易導(dǎo)致嚴(yán)重的粒子衰退現(xiàn)象．

通過分析發(fā)現(xiàn)，大多數(shù)系統(tǒng)的過程噪聲都是高斯的，或者屬于類高斯分布，也就意味著其先驗(yàn)建議分布是類高斯的，那么，利用高斯分布作為重要性密度函數(shù)是可行的[5]．而且由于高斯建議分布疊加了真實(shí)建議分布與最新測量值 ，使先驗(yàn)分布朝著高似然區(qū)域移動，與測量值有關(guān)粒子的權(quán)值相應(yīng)增大，經(jīng)過重采樣過程，這些粒子在總的粒子中的比例增加，而與觀測信息無關(guān)的粒子將被舍棄，使運(yùn)算代價不會無謂浪費(fèi)，因而能夠有效提高粒子濾波的效率和精度．

因此，本算法在生成粒子時，利用EKF濾波算法中產(chǎn)生最優(yōu)的高斯分布作為重要性分布，結(jié)合最新的測量值，通過高斯近似不斷更新后驗(yàn)概率分布，實(shí)現(xiàn)遞推估計．也就是說，EKF在任意時刻按照如下方式對后驗(yàn)概率密度進(jìn)行近似

然后，讓新粒子從各自的重要性密度函數(shù)中產(chǎn)生出來，然后執(zhí)行權(quán)值更新過程，并根據(jù)判定準(zhǔn)則對粒子執(zhí)行重采樣步驟.

2.2 基于均值漂移的粒子聚類

均值偏移算法本質(zhì)上是一種基于核概率密度估計的無參數(shù)方法[7]．對于一個服從概率密度函數(shù) 的數(shù)據(jù)集{,=1,2,... ,n}，對數(shù)據(jù)集中的每一點(diǎn)分別執(zhí)行均值偏移迭代，使它們朝著相似度高的區(qū)域移動，直到算法最終收斂．

而均值偏移向量可以表示為

均值偏移向量總是指向概率密度梯度的方向.從圖1可以看出，狀態(tài)轉(zhuǎn)移完成后，采用Camshift算法，對粒子進(jìn)行均值偏移迭代，那么粒子就會沿著概率密度梯度的方向移動，最后粒子在后驗(yàn)概率密度函數(shù)值大的區(qū)域聚集，完成粒子聚類.

圖1 基于Camshif算法的粒子聚類示意圖Fig.1 Particle clusterbased on Camshift

3 算法具體實(shí)現(xiàn)

融合了Kalman和Camshift的完整粒子濾波算法流程如下：

2）應(yīng)用Kalman濾波遞推公式更新采樣粒子，進(jìn)行狀態(tài)預(yù)測；

4）采用Camshift算法對每個粒子進(jìn)行漂移，得到聚類后的粒子集；

5）權(quán)值更新與歸一化權(quán)重；

6）均值與方差估計；

4 算法的實(shí)驗(yàn)結(jié)果及分析

將所提出的改進(jìn)的粒子濾波算法在交通目標(biāo)跟蹤和違章檢測中進(jìn)行了應(yīng)用測試.系統(tǒng)中采用的交通監(jiān)控視頻分辨率為480×640，實(shí)現(xiàn)了對單目標(biāo)以及多目標(biāo)的跟蹤.

如圖2所示，有4輛車同時被系統(tǒng)檢測出并進(jìn)行了有效的實(shí)時跟蹤.在右側(cè)車道中，車輛行駛路線上有陰影干擾，但是系統(tǒng)還是比較好的識別了目標(biāo)，并未發(fā)生目標(biāo)丟失，說明了本算法在存在干擾因素的復(fù)雜環(huán)境中仍然可以正常工作，魯棒性較強(qiáng).

圖2 干擾情況下的車輛跟蹤（從左到右分別是第11、15、20幀）Fig.2 Target tracking under distribution(Frame11,15,20)

通過實(shí)驗(yàn)，將本算法與Camshift濾波算法和基本粒子濾波算法進(jìn)行了性能比較，圖3為算法性能比較圖，通過對x方向圖3a），y方向圖3b）和歐式距離圖3c）3個參數(shù)進(jìn)行對比，可以看到本算法的在跟蹤誤差上優(yōu)于其他兩個算法，跟蹤精度更高.

表1 算法時間性能和跟蹤精度比較Tab.1 Comparison of time performance and tracking accuracy

為了測試算法的實(shí)時性，將所開發(fā)的實(shí)時跟蹤算法與Camshift及基本粒子濾波算法進(jìn)行了時間性能及誤差的聯(lián)合比較.從表1中看出，Camshift算法雖然跟蹤速度最快，但是其誤差是本文算法的8倍左右.而基本粒子濾波算法在采用相同粒子數(shù)目的情況下，跟蹤的實(shí)時性及誤差明顯低于本文所提出的算法，隨著粒子數(shù)目增加，這種現(xiàn)象更加明顯.另外，從表中可以清楚的看出，基本粒子濾波算法在粒子數(shù)減少時，跟蹤精度下降十分明顯，而本文算法在粒子數(shù)為100時，其跟蹤精度與基本粒子濾波算法粒子數(shù)為500時基本相當(dāng).實(shí)驗(yàn)結(jié)果說明，基于粒子濾波架構(gòu)嵌入Camshift的跟蹤算法在跟蹤效率上具有明顯的優(yōu)勢.其中，誤差采用均方根誤差來衡量.

5 結(jié)論

粒子濾波算法因其較強(qiáng)的非線性處理能力而成為目前的研究熱點(diǎn).但由于算法的局限，實(shí)時性較差，限制了其在工程上的應(yīng)用.通過分析發(fā)現(xiàn)，許多非線性系統(tǒng)都可以看作是一個包含線性子結(jié)構(gòu)的狀態(tài)空間模型，因此，可以利用Kalman濾波器處理線性的狀態(tài)預(yù)測過程，選取優(yōu)化的重要性概率密度函數(shù)，使先驗(yàn)分布向高似然區(qū)域移動，增加與量測值有關(guān)的粒子權(quán)值.進(jìn)一步利用Camshift算法，使粒子向后驗(yàn)概率密度高的區(qū)域聚類，進(jìn)一步降低計算復(fù)雜度，使粒子濾波算法效率大大改善.實(shí)驗(yàn)結(jié)果表明，改進(jìn)的粒子濾波算法可以有效減少計算量，在復(fù)雜環(huán)境下也可以實(shí)現(xiàn)對目標(biāo)的有效、實(shí)時跟蹤.

[1]Gordon N J，Salmond D J，Smith A FM.A novelapproach tononlinearand non-Gaussian Bayesian stateestimation[J].IEEEproceeding，1993，140：107-113.

[2]Julier SJ，Uhlmann JK.A new extension of the Kalman filter to nonlinear systems[C]//The11th IntSymposium on Aerospace/Defense Sensing，Simulation and Controls，Orlando:IEEE，1997:54-65.

[3]Arnaud Doucet，Nando De Freitas.SequentialMonte Carlo Methods in Practice[M].Berlin:The Springer press，2001:97-118.

[4]Doucet A，Gordon N J，Krishnamurthy V.Particle filters for state estimation of jump Markov linear systems[J].IEEE Transactions on Signal Processing，2001，49：613-624.

[5]Schoh T，Gustafsson F，Nordlund P J.Marginalized particle filters for m ixed linear/nonlinear state-space models[J].IEEE Trans On Signal Processing，2005，53（7）：2279-2289.

[6]劉軍.科學(xué)計算中的蒙特卡羅策略 [M].北京：高等教育出版社，2009：110-116.

[7]王鑫，唐振民.一種改進(jìn)的基于Camshift的粒子濾波實(shí)時目標(biāo)跟蹤算法 [J].中國圖象圖形學(xué)報，2010，15（10）：1507-1514.

[8]Collins R T.Mean shift Blob Tracking through Scale Space[C]//Proc of the IEEECSConference on Computer Vision and Pattern Recognition，San Francisco:IEEE，2003:234-240.

[9]魏武，張亞楠，裴海龍，等.融合多模型的粒子濾波運(yùn)動目標(biāo)實(shí)時跟蹤算法 [J].公路交通科技，2010，27（1）：95-100.

[10]Taek Lyul Song，Dong Gwan Lee，Jonha Ryu.A probabilistic nearestneighbor filter algorithm for tracking in a clutter environment[J].Signal Processing，2005，85（10）：2044-2053.