章 濤 來 燃 吳仁彪

(1. 中國民航大學(xué)天津市智能信號(hào)與圖像處理重點(diǎn)實(shí)驗(yàn)室，天津，300300； 2. 天津大學(xué)電子信息工程學(xué)院，天津，300072)

基于觀測數(shù)據(jù)聚類劃分的擴(kuò)展目標(biāo)跟蹤算法*

章 濤1，2來 燃1吳仁彪1

(1. 中國民航大學(xué)天津市智能信號(hào)與圖像處理重點(diǎn)實(shí)驗(yàn)室，天津，300300； 2. 天津大學(xué)電子信息工程學(xué)院，天津，300072)

針對高斯混合假設(shè)概率密度濾波擴(kuò)展目標(biāo)跟蹤算法中的觀測集合劃分問題，本文分析了距離門限劃分方法存在的問題，提出了一種利用聚類方法進(jìn)行觀測數(shù)據(jù)集合劃分的方法。該方法利用極大似然方法獲得目標(biāo)數(shù)的估計(jì)值，以此作為聚類數(shù)利用K-means聚類對觀測數(shù)據(jù)集合進(jìn)行聚類劃分，并利用橢球門限對觀測數(shù)據(jù)進(jìn)行處理以降低雜波觀測對聚類劃分的影響。實(shí)驗(yàn)結(jié)果表明，該方法能夠獲得正確的劃分觀測集合，計(jì)算復(fù)雜度較距離門限劃分方法有較大降低，同時(shí)在多目標(biāo)跟蹤效果方面優(yōu)于觀測數(shù)據(jù)距離門限劃分的假設(shè)概率密度濾波擴(kuò)展目標(biāo)跟蹤算法。

多目標(biāo)跟蹤; 擴(kuò)展目標(biāo)跟蹤；概率假設(shè)密度濾波；觀測集合劃分；K-means聚類

引 言

多目標(biāo)跟蹤在多傳感器數(shù)據(jù)融合領(lǐng)域既是重要的理論問題又是重要的應(yīng)用問題。目前的多目標(biāo)跟蹤方法可以分為傳統(tǒng)的基于數(shù)據(jù)關(guān)聯(lián)的方法[1-3]和基于隨機(jī)有限集理論[4](Random finite set，RFS)的非關(guān)聯(lián)方法。概率假設(shè)密度(Probability hypothesis density，PHD)濾波方法[5～7]是非關(guān)聯(lián)多目標(biāo)跟蹤方法的代表。無論是傳統(tǒng)的基于數(shù)據(jù)關(guān)聯(lián)的多目標(biāo)跟蹤方法,還是基于隨機(jī)有限集理論的方法，絕大多數(shù)方法都需要滿足這樣一個(gè)假設(shè)：每一個(gè)觀測都來自于一個(gè)可以被看作質(zhì)點(diǎn)的目標(biāo)。然而由于傳感器分辨率、目標(biāo)存在多個(gè)反射點(diǎn)以及傳感器與目標(biāo)相對位置關(guān)系等原因，這一假設(shè)并不一定能成立,從而出現(xiàn)了單個(gè)目標(biāo)同時(shí)產(chǎn)生多個(gè)觀測形成的擴(kuò)展目標(biāo)問題，如圖1所示。

圖1 擴(kuò)展目標(biāo)示意圖Fig.1 Sketch map of extended target

在隨機(jī)有限集框架下，2003年Mahler提出傳遞后驗(yàn)概率密度的一階統(tǒng)計(jì)矩的PHD濾波器[5]。2006年 Vo提出了線性高斯條件下PHD濾波器的近似形式GM-PHD (Gaussian mixture PHD)濾波器[8]。2009年Mahler 提出了利用假設(shè)概率密度濾波算法解決擴(kuò)展目標(biāo)的跟蹤問題，并給出了相關(guān)算法理論框架，即ET-PHD(Extended target PHD)算法[9]。2012年，Granstrom提出了基于ET-PHD框架線性條件下的高斯混合模型實(shí)現(xiàn)方法，即ET-GM-PHD濾波算法[10]。在Mahler 提出的ET-PHD擴(kuò)展目標(biāo)跟蹤算法理論框架中，需要將觀測數(shù)據(jù)(包括目標(biāo)及雜波)劃分為多種可能的集合，然后利用所有可能集合劃分進(jìn)行目標(biāo)狀態(tài)更新計(jì)算，這種方法對于目標(biāo)數(shù)和雜波較多的情況幾乎是無法計(jì)算的[10]。Granstrom針對這個(gè)問題提出了一種利用距離門限實(shí)現(xiàn)觀測數(shù)據(jù)集合劃分的方法[10]。但距離門限范圍的設(shè)置依賴于實(shí)驗(yàn)數(shù)據(jù)，導(dǎo)致算法性能與觀測距離門限范圍參數(shù)選取情況密切相關(guān)，跟蹤估計(jì)性能很不穩(wěn)定。

本文提出了一種利用K-means聚類進(jìn)行觀測數(shù)據(jù)集合劃分的方法。該方法利用極大似然方法獲得目標(biāo)數(shù)的估計(jì)值，以此作為聚類數(shù)并利用K-means對觀測數(shù)據(jù)集合進(jìn)行劃分，并利用橢球門限對觀測數(shù)據(jù)進(jìn)行處理以降低雜波觀測對聚類劃分的影響。實(shí)驗(yàn)結(jié)果表明，該方法能夠獲得正確的觀測集合劃分，計(jì)算復(fù)雜度較距離門限劃分方法有較大降低，同時(shí)在多目標(biāo)跟蹤效果方面優(yōu)于距離門限劃分的假設(shè)概率密度濾波擴(kuò)展目標(biāo)跟蹤算法。

1 概率假設(shè)密度濾波擴(kuò)展目標(biāo)跟蹤

1.1 目標(biāo)跟蹤模型

(1)

(2)

在傳統(tǒng)的目標(biāo)跟蹤問題中，一般假設(shè)每一個(gè)觀測都來自于一個(gè)可以被看作質(zhì)點(diǎn)的目標(biāo)，但對于擴(kuò)展目標(biāo)，這一假設(shè)將不再成立，一個(gè)目標(biāo)會(huì)產(chǎn)生多個(gè)觀測，Mahler在其提出的ET-PHD濾波框架中將每一個(gè)目標(biāo)產(chǎn)生的擴(kuò)展觀測數(shù)假設(shè)為Poisson分布。

1.2 擴(kuò)展目標(biāo)觀測集合劃分

在ET-PHD濾波擴(kuò)展目標(biāo)跟蹤框架中，觀測集合劃分方法是將觀測任意組合構(gòu)成多個(gè)觀測集合劃分可能，并利用觀測集合的所有集合劃分可能對擴(kuò)展目標(biāo)的狀態(tài)進(jìn)行更新，當(dāng)觀測數(shù)較大時(shí)計(jì)算量過大，對于目標(biāo)數(shù)較多和雜波較多的情況幾乎是無法實(shí)現(xiàn)的。

(3)

式中：Rk為觀測噪聲協(xié)方差矩陣。該距離服從χ2分布，因此可以通過設(shè)置概率Pg獲得在該概率下合理的觀測集合劃分距離閾值。文獻(xiàn)[10]通過實(shí)驗(yàn)方法，總結(jié)出閾值取值滿足Pg∈(0.3,0.8)時(shí)可較好地兼顧正確集合劃分和算法計(jì)算復(fù)雜度,但由于這種閾值范圍的選取依賴于實(shí)驗(yàn)數(shù)據(jù)所總結(jié)的經(jīng)驗(yàn)，導(dǎo)致跟蹤估計(jì)性能對于不同數(shù)據(jù)很不穩(wěn)定。

1.3ET-GM-PHD濾波器

(4)

(5)

假設(shè)每個(gè)目標(biāo)都滿足式(1)線性動(dòng)態(tài)模型，每個(gè)傳感器觀測滿足式(2)線性觀測模型，目標(biāo)的存活概率與檢測概率狀態(tài)獨(dú)立，目標(biāo)的強(qiáng)度函數(shù)可以表示為高斯混合形式，則針對擴(kuò)展目標(biāo)的ET-GM-PHD算法的遞推公式可以分為預(yù)測步和更新步兩個(gè)步驟，其中預(yù)測步與傳統(tǒng)點(diǎn)目標(biāo)GM-PHD方法相同，即預(yù)測步為

(6)

更新步為

(7)

(8)

其中

(9)

(10)

(11)

(12)

其中

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

式中：觀測zk屬于觀測子集W，集合的勢為|W|；每個(gè)周期觀測中雜波觀測數(shù)服從Poisson分布，其均值為λk，一般情況下假設(shè)雜波觀測數(shù)均值為常數(shù)，即λk=λ；ck(zk)為觀測空間中雜波的分布函數(shù)，假設(shè)其服從均勻分布，即ck(zk)=1/V，V為觀測空間；HW，RW分別表示擴(kuò)維后的觀測矩陣及觀測噪聲協(xié)方差矩陣；blkdiag (·)表示塊對角矩陣計(jì)算；δ|W|,1為克羅內(nèi)克(Kronecker delta)函數(shù)；p'表示觀測集合劃分的每一種可能；W′表示每一個(gè)觀測集合劃分可能中的觀測子集；ωp表示當(dāng)前觀測劃分可能的權(quán)重。

2 觀測數(shù)據(jù)聚類劃分

2.1 目標(biāo)數(shù)估計(jì)

每一個(gè)周期獲得的觀測包括目標(biāo)的擴(kuò)展觀測和雜波觀測，每個(gè)目標(biāo)的擴(kuò)展觀測數(shù)服從γ為均值的Posson分布，雜波觀測數(shù)服從λ為均值的Poisson分布。由于多個(gè)獨(dú)立Poisson分布的和仍然服從Poisson分布，因此每一個(gè)周期獲得的觀測服從均值為γNX,k+λ的Poisson分布，即

(25)

式中：NX,k表示k時(shí)刻的目標(biāo)數(shù)，Mk表示k時(shí)刻的觀測數(shù)。

每個(gè)目標(biāo)的擴(kuò)展觀測數(shù)均值γ已知，雜波觀測數(shù)均值λ已知，對于k時(shí)刻獲得的Mk個(gè)觀測可通過極大似然估計(jì)方法獲得目標(biāo)數(shù)NX,k的估計(jì)值，即

(26)

2.2 觀測數(shù)據(jù)K-means聚類劃分

由于每一個(gè)周期獲得的觀測中不僅包括目標(biāo)觀測還包括雜波觀測，但是雜波均勻分布在觀測空間中，離散分布的雜波觀測會(huì)嚴(yán)重影響聚類劃分的效果。如圖2(a)所示，由于雜波存在影響了K-means的相似度計(jì)算，使得A，B兩目標(biāo)的觀測被劃分到同一觀測子集中。為了解決這個(gè)問題，本文首先利用橢球門限對進(jìn)行更新計(jì)算的觀測數(shù)據(jù)進(jìn)行門限處理，以減少觀測數(shù)據(jù)中的雜波成分，從而改善了觀測數(shù)據(jù)集合劃分效果。如圖2(b)所示，對觀測數(shù)據(jù)進(jìn)行橢球門限處理后，部分雜波被剔除掉，K-means聚類能夠正確劃分觀測子集。

(a) 消除雜波前劃分 (b) 消除雜波后劃分(a) Partitioning before clutter removal (b) Partitioning after clutter removal圖2 雜波對聚類劃分影響的示意圖Fig.2 Influence of clutter measurements on partitioning

在k時(shí)刻預(yù)測步計(jì)算后，殘差向量可以表示為

(27)

殘差協(xié)方差矩陣可以表示為

(28)

式中：Hk為測量矩陣；Pk(j)為第j個(gè)預(yù)測協(xié)方差矩陣；Rk為觀測噪聲矩陣。

利用橢球門限[11]判別對觀測數(shù)據(jù)進(jìn)行門限處理，以減少觀測數(shù)據(jù)中的雜波成分，即有

(29)

當(dāng)觀測空間的維數(shù)為2時(shí)，橢球門限閾值表示為

(30)

式中：Pg為目標(biāo)觀測落入橢球門限的概率。

2.3 算法流程

本文提出的基于觀測數(shù)據(jù)聚類劃分的擴(kuò)展目標(biāo)遞歸跟蹤算法流程歸納如下。

(1) 已知k-1時(shí)刻的目標(biāo)強(qiáng)度函數(shù)υk-1(x)；

(2) 利用式(6)預(yù)測目標(biāo)強(qiáng)度函數(shù)得到υk|k-1(x);

(6)對目標(biāo)強(qiáng)度函數(shù)υk|k(x)的高斯項(xiàng)進(jìn)行裁剪合,具體方法詳見參考文獻(xiàn)[12]。

3 仿真試驗(yàn)

圖3 目標(biāo)運(yùn)動(dòng)軌跡及觀測值Fig．3 True trajectories and measurements

驗(yàn)證本文算法的實(shí)驗(yàn)場景為一個(gè)[-100,100]×[-100,100]的監(jiān)視區(qū)域，4個(gè)目標(biāo)勻速直線運(yùn)動(dòng)(如圖3所示)。傳感器采樣周期為1 s，仿真獲得40個(gè)采樣周期數(shù)據(jù)，目標(biāo)狀態(tài)用向量[x,x',y,y']T表示，其中(x,y)表示目標(biāo)的位置，(x',y')表示目標(biāo)的速度，觀測獲得目標(biāo)的二維位置信息(即nz=2)，目標(biāo)運(yùn)動(dòng)方程及觀測方程滿足線性高斯模型，目標(biāo)存活概率設(shè)置為Ps=0.99，檢測概率設(shè)置為PD=0.9，雜波服從Poisson分布，強(qiáng)度設(shè)置為λ=10，雜波位置均勻分布在觀測空間中。每個(gè)目標(biāo)擴(kuò)展觀測數(shù)服從γ=5的Poisson分布。新生目標(biāo)的概率假設(shè)密度函數(shù)為

(31)

圖4 本文方法的狀態(tài)估計(jì)結(jié)果Fig．4 Estimates of proposed algorithm圖5 觀測劃分?jǐn)?shù)比較Fig．5 Comparison of partition number

圖6 目標(biāo)數(shù)估計(jì)結(jié)果比較Fig．6 Comparison of target number estimation圖7 OSPA距離比較Fig．7 Comparison of OSPA distance

4 結(jié)束語

本文提出了一種基于觀測數(shù)據(jù)聚類劃分的擴(kuò)展目標(biāo)跟蹤算法，該方法首先利用橢球門限對觀測數(shù)據(jù)進(jìn)行處理以降低雜波觀測對聚類劃分的影響，然后利用極大似然方法獲得目標(biāo)數(shù)估計(jì)，并以此作為聚類數(shù)利用K-means對觀測數(shù)據(jù)進(jìn)行劃分。實(shí)驗(yàn)結(jié)果表明，該方法在正確劃分觀測集合的基礎(chǔ)上，計(jì)算復(fù)雜度有較大降低，同時(shí)在多目標(biāo)跟蹤效果方面優(yōu)于觀測數(shù)據(jù)距離門限劃分的假設(shè)概率密度濾波擴(kuò)展目標(biāo)跟蹤算法。

[1]Bar-ShalomY,LiXR.Multitarget-multisensortracking:Principlesandtechniques[M].Storrs,CT:YBSPublishing, 1995.

[2]Bar-ShalomY,FortmannTE.Trackinganddataassociation[M].SanDiego,CA:AcademicPress, 1988, 1-6.

[3] 李鵬飛, 黃建軍, 黃敬雄,等. 一種模糊Kalman濾波機(jī)動(dòng)目標(biāo)跟蹤的新算法 [J]. 數(shù)據(jù)采集與處理, 2009, (4):483-486.

LiPengfei,HuangJianjun,HuangJingxiong,etal.FuzzyKalmanfilterformaneuveringtargettracking[J].JournalofDataAcquisitionandProcessing, 2009, (4):483-486.

[4]MahlerR.Randomsets:Unificationandcomputationforinformationfusion—Aretrospectiveassessment[C] // 7thInternationalConferenceonInformationFusion.Stockholm,Sweden:IEEEComputerSocietyPress, 2004:1-20.

[5]MahlerR.Multi-targetBayesfilteringviafirst-ordermulti-targetmoments[J].IEEETransactionsonAerospaceandElectronicSystems, 2003, 39(4):1152-1178.

[6] 章濤, 吳仁彪. 自適應(yīng)門限GM-CPHD多目標(biāo)跟蹤算法[J]. 數(shù)據(jù)采集與處理, 2014, 29(4):549-554.

ZhangTao,WuRenbiao.AdaptivegatingGM-CPHDformultitargettracking[J].JournalofDataAcquisitionandProcessing, 2014, 29(4):549-554.

[7] 連峰, 韓崇昭, 劉偉峰, 等. 高斯混合擴(kuò)展目標(biāo)概率假設(shè)密度濾波器的收斂性分析[J].自動(dòng)化學(xué)報(bào), 2012, 38(8):1343-1352.

LianFeng,HanChongzhao,LiuWeifeng,etal.ConvergenceanalysisoftheGaussianmixtureextended-targetprobabilityhypothesisdensityfilter[J].ActaAutomaticaSinica, 2012, 38(8):1343-1352.

[8]VoBN,MaWK.TheGaussianmixtureprobabilityhypothesisdensityfilter[J].IEEETransactionsonSignalProcessing, 2006, 54(11): 4091-4104.

[9]MahlerR.PHDFilterfornonstandardtargets,I:Extendedtargets[C] // 12thInternationalConferenceonInformationFusion.Seattle,WA,USA:IEEEComputerSocietyPress, 2009: 915-921.

[10]GranstromK,OrguneU.ExendedtargettrackingusingaGaussian-mixturePHDfilter[J].IEEETransactionsonAerospaceandElectronicSystems, 2012, 48(4): 3268-3286.

[11]BlackmanSS,PopoliR.Designandanalysisofmoderntrackingsystems[M].Norwood,MA:ArtechHouse, 1999.

[12]RisticB,VoBN,ClarkD,etal.Ametricforperformanceevaluationofmulti-targettrackingalgorithms[J].IEEETransactionsonSignalProcessing, 2011, 59( 7 ): 3452-3457.

[13]Granstr?mK,OrgunerU.ImplementationoftheGIW-PHDfilter[M].Stockholm,Sweden:Link?pingUniversityElectronicPress, 2013.

Extended Target Tracking with Clustering of Measurement Partitioning

Zhang Tao1，2， Lai Ran1，Wu Renbiao1

(1. Tianjin Key Laboratory for Advanced Signal Processing, Civil Aviation University of China, Tianjin, 300300, China;2. School of Electronic Information Engineering, Tianjin University, Tianjin, 300072,China)

A novel K-means algorithm of measurement partitioning is proposed to overcome the problem of distance partitioning algorithm in Gaussian mixture probability hypothesis density filter for extended target tracking. The number of the targets is estimated by maximum-likelihood estimator and then the estimates of the target number are used as the cluster number of K-means. An elliptical gate is introduced to remove the clutter measurements for depressing the influence of clusters. Simulation results show that the proposed algorithm reduces the computational complexity obviously, and obtains an improved performance.

multiple-target tracking; extended target tracking; GM-PHD filter; measurement partitioning; K-means clustering

國家自然科學(xué)基金(61471365，61231017，61571442)資助項(xiàng)目；中國民航大學(xué)中央高?；?3122015D003)資助項(xiàng)目。

2014-05-09；

2016-10-14

TP391

A

章濤(1980-)，男，博士，研究方向：目標(biāo)跟蹤、雷達(dá)信號(hào)處理，E-mail:t-zhang@cauc.edu.cn。

來 燃(1990-)，男，碩士研究生，研究方向：多目標(biāo)跟蹤，E-mail:rlai@cauc.edu.cn。

吳仁彪(1966-)，男，博士，教授，研究方向：自適應(yīng)信號(hào)處理和陣列信號(hào)處理在雷達(dá)、通信和導(dǎo)航中的應(yīng)用，E-mail:rbwu@cauc.edu.cn。