一種基于概率密度傳播的目標(biāo)跟蹤算法

高慶華 金明錄 王 潔 王洪玉

(大連理工大學(xué)電子與信息工程學(xué)院 大連 116023)

1 引言

目標(biāo)跟蹤問題是WSN(Wireless Sensor Network)領(lǐng)域的研究熱點。有效的目標(biāo)跟蹤是無線傳感器網(wǎng)絡(luò)在戰(zhàn)場信息監(jiān)測、生活習(xí)性監(jiān)測、室內(nèi)定位等眾多領(lǐng)域得以應(yīng)用的基礎(chǔ)。目標(biāo)跟蹤算法整體上分為兩大類：一類是概率方法，將跟蹤問題轉(zhuǎn)化為狀態(tài)估計問題，采用貝葉斯估計、極大似然估計等方法處理問題；另一類是數(shù)值方法，將跟蹤問題看作優(yōu)化問題，采用求極值的方法處理問題。在目標(biāo)運動軌跡沒有規(guī)律、系統(tǒng)噪聲和觀測噪聲較復(fù)雜的情況下，基于概率的方法通常具有較強(qiáng)的魯棒性和較優(yōu)的跟蹤精度。

近年來，PF(Particle Filter)算法被提出并用來解決非線性、非高斯環(huán)境下的目標(biāo)跟蹤問題。PF算法理論上基于后驗分布進(jìn)行采樣，實際應(yīng)用中很難實現(xiàn)對后驗分布直接采樣，因此通常基于先驗分布采樣，然后利用似然函數(shù)進(jìn)行加權(quán)，這樣處理造成當(dāng)前時刻的觀測信息在采樣中沒有發(fā)揮作用，當(dāng)先驗分布與似然函數(shù)偏差較大時，會造成絕大多數(shù)粒子權(quán)值趨近于零的退化現(xiàn)象發(fā)生，文獻(xiàn)[1]證明隨著時間的推移這種退化必然發(fā)生。一種直觀的克服該問題的方法是增加粒子數(shù)目，但這樣勢必造成計算量的增加。重采樣可以在一定程度上緩解該問題，但會造成粒子多樣性降低，易發(fā)生粒子耗盡、貧化問題。Doucet提出采用擴(kuò)展卡爾曼濾波算法對每個粒子進(jìn)行預(yù)測；文獻(xiàn)[2-4]等人提出基于無跡卡爾曼濾波算法對每個粒子進(jìn)行預(yù)測；文獻(xiàn)[5,6]提出采用高斯函數(shù)對粒子進(jìn)行平滑處理；文獻(xiàn)[7]等提出利用觀測到的參考節(jié)點信息對預(yù)測粒子進(jìn)行mean-shift偏移；文獻(xiàn)[8]提出利用參考節(jié)點信息構(gòu)建目標(biāo)可能出現(xiàn)區(qū)域的方法對粒子采樣區(qū)域進(jìn)行限制；上述算法優(yōu)化了提議分布，使先驗分布與似然函數(shù)的交集變大，一定程度上克服了粒子退化問題，但是，這類算法本質(zhì)上仍然需要對概率密度分布進(jìn)行采樣，不能徹底擺脫粒子退化、貧化的問題。文獻(xiàn)[9]提出一種采用連續(xù)函數(shù)表征目標(biāo)分布的算法實現(xiàn)人臉跟蹤，有效地克服了PF算法采樣困難的問題，但是該算法通過多次采樣、擬合獲得似然函數(shù)，需要計算大量Hessian矩陣、求逆矩陣等復(fù)雜操作，不適用于WSN。

針對上述問題，本文提出一種貝葉斯框架下的概率密度傳播跟蹤算法PDPA(Probability Density Propagation Algorithm)，采用高斯混合模型來表征目標(biāo)概率分布，通過對連續(xù)函數(shù)的一系列操作實現(xiàn)目標(biāo)跟蹤，解決了大噪聲、非線性、非高斯環(huán)境下基于WSN的目標(biāo)跟蹤問題。

2 系統(tǒng)模型

PDPA算法基于貝葉斯框架，采用狀態(tài)空間模型來表述WSN跟蹤問題，令目標(biāo)的狀態(tài)變量序列為{xt, t=1,…,N }，觀測變量序列為{zt, t=1,…,N}，則有

這里F為狀態(tài)預(yù)測函數(shù)，H為狀態(tài)觀測函數(shù)，wt為過程噪聲，vt為觀測噪聲。

在預(yù)測方程和觀測方程的作用下，狀態(tài)分布先驗概率密度函數(shù)p(xt|z1,…,t?1)和后驗概率密度函數(shù)p(xt|z1,…,t)按式(3)，式(4)進(jìn)行狀態(tài)預(yù)測和更新：

狀態(tài)轉(zhuǎn)移概率函數(shù)p(xt|xt?1)由式(1)確定，觀察似然概率函數(shù)p(zt|xt)由式(2)確定。

GMM(Gaussian Mixture Model)具有近似表示任意概率分布的能力，文獻(xiàn)[10，11]對此作了詳細(xì)研究，本文亦采用GMM來表示概率分布函數(shù)如式(5)所示。

這里c為高斯核個數(shù)，λm為第m個核的權(quán)值，μm為其均值，Σm為其方差，高斯函數(shù)定義為

這里d為變量x的維數(shù)，文中T代表轉(zhuǎn)置。

3 概率密度傳播跟蹤算法

PDPA算法采用GMM表征先驗分布、似然函數(shù)、后驗分布，有效地克服了PF算法退化、貧化、采樣效率低的問題，同時，具有處理非線性、非高斯問題的能力。整個算法基于貝葉斯框架，分為預(yù)測、似然函數(shù)構(gòu)建、后驗分布計算、目標(biāo)位置確定4部分。

3.1 預(yù)測

這里Σw用于補(bǔ)償運動噪聲。對GMM中每個高斯函數(shù)均進(jìn)行UT變換，獲得的先驗分布如式(10)所示

3.2 似然函數(shù)構(gòu)建

當(dāng)目標(biāo)探測到的參考節(jié)點個數(shù)k≥2時，假設(shè)獲得的參考節(jié)點位置、距離信息集合為為參考節(jié)點i的位置，di為其與目標(biāo)的距離，任意兩個參考節(jié)點{i, j| i∈之間的距離dij=如果滿足約束條件(di+dj則求解以(xi, yi)為圓心di為半徑的圓與以(xj, yj)為圓心dj為半徑的圓的交點，將求得的交點作為GMM模型的均值，觀測噪聲的方差作為GMM模型的方差，權(quán)值為交點總個數(shù)的倒數(shù)。

當(dāng)未收到參考節(jié)點信息時，令似然函數(shù)為常數(shù)1。

3.3 后驗分布計算

后驗分布函數(shù)為先驗分布函數(shù)與似然函數(shù)的乘積，如式(11)所示

這里c1為先驗分布核個數(shù)，c2為似然函數(shù)核個數(shù)，相乘得到核個數(shù)為c1×c2的GMM函數(shù)，新GMM參數(shù)如下

新的GMM函數(shù)綜合了先驗信息以及當(dāng)前時刻的觀測信息，代表了目標(biāo)的后驗分布信息。但是，直接將該函數(shù)作為后驗分布勢必造成GMM函數(shù)中核個數(shù)隨時間不斷增加，導(dǎo)致算法計算量災(zāi)難性增長。本文采用以下3種方法對新GMM函數(shù)進(jìn)行擬合處理，以確保后驗分布核個數(shù)的恒定。

方法1 基于核系數(shù)選擇 直接選擇模型中系數(shù)最大的c1個核構(gòu)成新的GMM函數(shù)。

方法2 EM擬合 首先，對c1×c2個樣本點μmn進(jìn)行重采樣，各樣本點被選擇的概率正比于λmn?1，重采樣獲得樣本集{s, i=1,…,N }，通i常令樣本個數(shù)N=10×c1×c 2。然后，采用EM算法對這些樣本點的分布進(jìn)行擬合處理，轉(zhuǎn)化為具有c1個核的GMM函數(shù)，EM算法分為E-step和M-step兩個步驟。

E-step：

方法3 K-mean擬合 與EM算法相比，K-mean算法具有簡單、計算量小的優(yōu)點。算法首先從c1×c2個權(quán)值為的樣本點mnμ中隨機(jī)選取c1個點作為聚類中心，然后，根據(jù)各樣本點與各聚類中心的歐式空間距離對樣本點分類，計算各類樣本點的加權(quán)質(zhì)心作為新的聚類中心。此過程進(jìn)行多次后收斂，此時聚類樣本的聚類中心、方差、樣本個數(shù)占總樣本個數(shù)的比例即為GMM模型中的均值、方差與權(quán)值。

擬合處理后的后驗分布GMM函數(shù)為

3.4 目標(biāo)位置確定

PDPA算法將后驗分布p(x)各高斯核均值的加權(quán)質(zhì)心作為當(dāng)前時刻的目標(biāo)位置，如式(18)所示

整個PDPA算法遵循貝葉斯框架，基于上一時刻的后驗分布進(jìn)行預(yù)測，獲取當(dāng)前時刻的似然函數(shù)，然后求解當(dāng)前時刻的后驗分布，同時，計算后驗分布中各模式的加權(quán)質(zhì)心并將其作為當(dāng)前時刻的位置。算法初始時刻直接將似然函數(shù)確定的位置作為其估計位置。

4 性能仿真與分析

4.1 仿真模型與環(huán)境

實驗中目標(biāo)基于CV/CT混合模型運動，具體模型參見文獻(xiàn)[12]。運動噪聲與觀察噪聲均為對稱雙峰非高斯噪聲，運動噪聲模型為w1N(μ1, Σ1)+(1?w1)N(?μ1, Σ1)，運動噪聲均值默認(rèn)為μ1=1，方差Σ1=1，系數(shù)w1∈[0.2,0.8]；觀察噪聲模型為w2N(μ2, Σ2)+(1?w2)N(?μ2, Σ2)，觀察噪聲均值默認(rèn)為μ2=20，方差Σ2=20，系數(shù)w2∈[0.2,0.8]。其它默認(rèn)仿真參數(shù)如表1所示。

表1 仿真參數(shù)

將PDPA算法分別與經(jīng)典PF算法，ML(Maximum Likelihood)算法進(jìn)行對比分析。誤差定義為估計位置與真實位置的均方誤差，實驗結(jié)果均為100次實驗的均值。

4.2 跟蹤效果分析

3種算法跟蹤效果如圖1所示，理想軌跡為橢圓形，右下角處受噪聲影響軌跡發(fā)生突變，PF算法在軌跡突變處跟蹤誤差加大，而PDPA算法表現(xiàn)出較好的跟蹤能力，證明其克服了PF算法在先驗分布與似然分布差別較大時產(chǎn)生的退化現(xiàn)象，同時，PDPA算法克服了ML算法跟蹤軌跡跳變、不穩(wěn)定的問題。

4.3 環(huán)境適應(yīng)能力分析

3種算法隨運動噪聲均值變化效果如圖2所示，隨著運動噪聲的加大，真實軌跡與理想軌跡偏差加大，致使先驗分布與似然函數(shù)交集變小，造成PF算法出現(xiàn)退化現(xiàn)象；ML算法最大誤差較大，定位性能變化嚴(yán)重。PDPA算法在均值誤差、最大誤差方面均表現(xiàn)出良好性能。

圖1 跟蹤效果圖

從圖3可以看出，隨著觀測噪聲的增加，ML算法誤差顯著增加，PDPA算法誤差緩慢增加，在觀察噪聲方差小于60時PDPA性能優(yōu)于PF算法，表明PDPA算法對觀測噪聲具有較好的適應(yīng)能力。

參考節(jié)點間距的變化造成目標(biāo)可獲得的有效觀測信息量發(fā)生變化，從而影響跟蹤精度。圖4顯示出ML算法性能隨間距變化較劇烈，而PDPA算法與PF算法對間距變化不是很敏感，表現(xiàn)出較好的密度適應(yīng)性。

4.4 性能分析

PDPA算法與PF算法、ML算法性能對比如表2所示，總體來說PDPA算法適合在運動噪聲與觀察噪聲均較大、參考節(jié)點分布不均勻的條件下工作，且算法跟蹤效果波動較小。

表2 算法性能比較

3.3節(jié)中3種擬合方法性能對比如表3所示。通常情況下，在WSN應(yīng)用中核系數(shù)最大的幾個核函數(shù)基本上代表了后驗分布的特征，基于核系數(shù)選擇的方法即可滿足性能要求。

表3 擬合方法性能比較

用于表征概率分布的GMM函數(shù)核個數(shù)通常根據(jù)具體的應(yīng)用環(huán)境采用實驗的方法來確定，Ding在文獻(xiàn)[11]中介紹了AIC與BIC兩種核個數(shù)確定準(zhǔn)則，亦可采用這些準(zhǔn)則確定核個數(shù)。核個數(shù)過少會造成有用信息的丟失，同時，過多的核個數(shù)也會使一些虛假信息得到傳播，GMM核個數(shù)要與噪聲的多峰值特征相匹配。

5 結(jié)束語

圖2 誤差隨運動噪聲均值變化

圖3 誤差隨觀測噪聲均值變化

圖4 誤差隨參考節(jié)點間距離變化

PDPA算法本質(zhì)上是一種基于GMM模型表征的連續(xù)函數(shù)實現(xiàn)貝葉斯估計的跟蹤算法，解決了PF算法采樣困難的問題，實現(xiàn)了大噪聲、非線性、非高斯環(huán)境下的目標(biāo)跟蹤。實驗結(jié)果表明，PDPA算法適用于不同參考節(jié)點密度場合，且能在運動與觀測模型噪聲較大的惡劣條件下工作，是一種適用于WSN的健壯跟蹤算法。進(jìn)一步的研究方向為PDPA算法收斂性的證明及將該算法應(yīng)用到復(fù)雜參數(shù)估計等問題中。

致謝 感謝羅海勇博士和Ding Min博士在相關(guān)算法方面的探討。

[1] Doucet A, Godsill S, and Andrieu C. On sequential Monte Carlo sampling methods for Bayesian filtering[J]. Statistics and Computing, 2000, 10(3): 197-208.

[2] Merwe R, Doucet A, and Freitas N, et al.. The unscented particle filter[C]. 14th Annual Neural Information Processing Systems Conference, Denver, Colorado, USA, Nov.27-Dec.2,2000: 584-590.

[3] Rui Yong and Chen Yun-qiang. Better proposal distributions:object tracking using unscented particle filter[C]. Proceeding of the Conference on Computer Vision and Pattern Recognition, Hawaii, USA, Dec.9-14, 2001: 786-793.

[4] Cheng Qi and Bondon P. A new unscented particle filter[C].International Conference on Acoustics, Speech and Signal Processing, Las Vegas, Nevada, USA, March 30-April 4, 2008:3417-3420.

[5] Kotecha J H and Djuric P M. Gaussian sum particle filtering[J]. IEEE Transactions on Signal Processing, 2003,51(10): 2602-2612.

[6] Kotecha J H and Djuric P M. Gaussian particle filtering[J].IEEE Transactions on Signal Processing, 2003, 51(10):2592-2601.

[7] Luo Hai-yong, Li Jin-tao, and Zhao Fang, et al.. Mobile target localization based on mean shift in wireless sensor networks[C]. Third International Conference on Pervasive Computing and Applications, Alexandria, Egypt, October 6-8, 2008: 248-253.

[8] Baggio A and Langendoen K. Monte Carlo localization for mobile wireless sensor networks[J]. Ad hoc Networks, 2008,6(5): 718-733.

[9] Han Bohyung, Zhu Ying, and Comaniciu D, et al.. Visual tracking by continuous density propagation in sequential Bayesian filtering framework[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(5):919-930.

[10] Sheng Xiao-hong, Hu Yu-hen, and Ramanathan P.Distributed particle filter with GMM approximation for multiple targets localization and tracking in wireless sensor network[C]. Fourth International Symposium on Information Processing in Sensor Networks, Los Angeles, California, USA,April 25-27, 2005: 181-188.

[11] Ding Min and Cheng Xiu-zhen. Fault tolerant target tracking in sensor networks[C]. Proceedings of the 10th ACM International Symposium on Mobile Ad hoc Networking and Computing, New Orleans, LA, USA, May 18-21, 2009:125-134.

[12] Yuan Xiang-hui, Han Chong-zhao, and Duan Zhan-sheng, et al.. Comparison and choice of models in tracking target with coordinated turn motion[C]. IEEE 8th International Conference on Information Fusion, Philadelphia, PA, USA,July 25-28, 2005, 2: 1497-1502.