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

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

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

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

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

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

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

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

在時刻 的后驗概率密度可近似表示為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6）均值與方差估計；

4 算法的實驗結(jié)果及分析

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

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

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

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

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

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

5 結(jié)論

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

[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]王鑫，唐振民.一種改進的基于Camshift的粒子濾波實時目標跟蹤算法 [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]魏武，張亞楠，裴海龍，等.融合多模型的粒子濾波運動目標實時跟蹤算法 [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.