基于mean shift和圖結(jié)構(gòu)的GMPHD擴(kuò)展目標(biāo)跟蹤

程軒, 宋驪平, 姬紅兵

(西安電子科技大學(xué) 電子工程學(xué)院, 陜西 西安　710071)

近幾年來(lái)，隨著雷達(dá)分辨率的不斷提高，針對(duì)擴(kuò)展目標(biāo)跟蹤問(wèn)題的研究已經(jīng)引起國(guó)內(nèi)外學(xué)者的廣泛關(guān)注[1-8]。2009年，Mahler推導(dǎo)出了隨機(jī)有限集框架下擴(kuò)展目標(biāo)概率假設(shè)密度(probability hypothesis density,PHD)濾波器的遞推方程[3]。隨后，Granstrom等學(xué)者在線性高斯條件的假設(shè)下，給出了擴(kuò)展目標(biāo)PHD濾波器的高斯混合(Gaussian mixture,GM)實(shí)現(xiàn)方式[4]。2012年，Granstrom等進(jìn)一步對(duì)擴(kuò)展目標(biāo)GMPHD濾波算法作了詳細(xì)論述，并用實(shí)測(cè)數(shù)據(jù)對(duì)算法進(jìn)行了驗(yàn)證[5]。然而，該算法存在2個(gè)問(wèn)題:①隨著擴(kuò)展目標(biāo)個(gè)數(shù)的增多，量測(cè)劃分?jǐn)?shù)也隨之增多，運(yùn)算量大幅上升；②在擴(kuò)展目標(biāo)發(fā)生交叉運(yùn)動(dòng)的時(shí)刻，目標(biāo)數(shù)目易產(chǎn)生漏估。針對(duì)算法所存在的問(wèn)題，Zhang等提出一種基于快速模糊自適應(yīng)諧振理論(adaptive resonance theory,ART)的擴(kuò)展目標(biāo)量測(cè)集劃分方法[6]，實(shí)現(xiàn)了對(duì)量測(cè)集的快速劃分，提高了算法的實(shí)時(shí)性，然而，在目標(biāo)較為密集和雜波條件下，模糊ART算法易出現(xiàn)“飽和”問(wèn)題導(dǎo)致分類錯(cuò)誤[7]。孔云波等提出一種基于網(wǎng)格密度分布和譜聚類的擴(kuò)展目標(biāo)量測(cè)集劃分算法[7]，與傳統(tǒng)的距離劃分相比，運(yùn)算量降低了38%。劉風(fēng)梅等采用mean shift對(duì)量測(cè)集進(jìn)行劃分，使算法的運(yùn)算量進(jìn)一步降低[8]。鑒于mean shift算法在量測(cè)劃分中表現(xiàn)出的優(yōu)良性能，本文采用該算法對(duì)擴(kuò)展目標(biāo)量測(cè)集進(jìn)行劃分。但以上算法均未能解決擴(kuò)展目標(biāo)交叉時(shí)刻的漏估問(wèn)題。

針對(duì)上述問(wèn)題，本文提出一種基于mean shift和圖結(jié)構(gòu)(graph structure,GS)的擴(kuò)展目標(biāo)GMPHD濾波算法。采用mean shift算法對(duì)擴(kuò)展目標(biāo)的量測(cè)集進(jìn)行劃分，并依據(jù)圖結(jié)構(gòu)更新后反饋回的信息判斷是否需要對(duì)量測(cè)集進(jìn)行子劃分；使用圖理論對(duì)擴(kuò)展目標(biāo)間的關(guān)系進(jìn)行建模，搭建圖結(jié)構(gòu)，并使用濾波值的一步預(yù)測(cè)更新圖結(jié)構(gòu)，反饋更新后的圖結(jié)構(gòu)信息至量測(cè)劃分步用以指導(dǎo)下一時(shí)刻的量測(cè)劃分。仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性和準(zhǔn)確性。

1　mean shift算法

mean shift算法本質(zhì)上是一種基于密度梯度估計(jì)的非參數(shù)方法，被廣泛應(yīng)用于視頻跟蹤、圖像分割和聚類分析等領(lǐng)域。本文使用mean shift算法對(duì)擴(kuò)展目標(biāo)量測(cè)集進(jìn)行劃分，降低算法的運(yùn)算量。

mean shift算法是從量測(cè)集出發(fā)對(duì)密度函數(shù)進(jìn)行估計(jì)，然后從密度函數(shù)梯度的非參數(shù)估計(jì)中獲得。其中，核密度估計(jì)是最常用的密度估計(jì)方法，它依據(jù)預(yù)先選定的核函數(shù)κ(·)對(duì)擴(kuò)展目標(biāo)量測(cè)集中每個(gè)量測(cè)的密度函數(shù)進(jìn)行計(jì)算。

假定在k時(shí)刻從雷達(dá)屏幕上所獲得的擴(kuò)展目標(biāo)的量測(cè)集為Zk,選取的核函數(shù)用κ(·)表示,則量測(cè)zk的核密度估計(jì)值可計(jì)算如下:

(1)

本文采用較為常用的高斯核函數(shù)[9]:

(2)

(3)

mean shift算法具體步驟如下:

②獲取收斂點(diǎn)。首先,從給定的量測(cè)集中選擇任意一個(gè)量測(cè),沿核密度估計(jì)梯度的方向不斷進(jìn)行搜索,直到其收斂于局部密度極大值點(diǎn);然后,將沿途的所有訪問(wèn)過(guò)的量測(cè)劃分到對(duì)應(yīng)的類別中;最后,在沒(méi)有訪問(wèn)過(guò)的量測(cè)中重新選擇一個(gè)量測(cè)作為起始點(diǎn)再次進(jìn)行遞歸搜索,直到量測(cè)集中所有的量測(cè)都被訪問(wèn)過(guò)為止,便可獲得所有的收斂點(diǎn)。

③收斂點(diǎn)的合并。計(jì)算各收斂點(diǎn)間的馬氏距離,然后將距離小于預(yù)設(shè)門限的收斂點(diǎn)合并,同時(shí)將屬于被合并收斂點(diǎn)的量測(cè)集也合并為一類。

④輸出最終的劃分結(jié)果。

2　擴(kuò)展目標(biāo)的圖結(jié)構(gòu)

當(dāng)擴(kuò)展目標(biāo)發(fā)生交叉時(shí),目標(biāo)產(chǎn)生的量測(cè)相距較近,此時(shí)由于量測(cè)劃分不準(zhǔn)確導(dǎo)致目標(biāo)數(shù)目產(chǎn)生漏估。針對(duì)該問(wèn)題,本文使用圖理論對(duì)擴(kuò)展目標(biāo)間的關(guān)系進(jìn)行建模,通過(guò)搭建圖結(jié)構(gòu)動(dòng)態(tài)地獲取目標(biāo)間的距離關(guān)系,并將圖結(jié)構(gòu)信息反饋回量測(cè)劃分步以判斷是否需要進(jìn)行子劃分。

定義圖結(jié)構(gòu)如下:圖結(jié)構(gòu)由節(jié)點(diǎn)集合No和邊的集合Ed構(gòu)成,記為G=(No,Ed),其中,No表示節(jié)點(diǎn)的有限非空集合,Ed表示邊的集合。將每個(gè)目標(biāo)視為圖結(jié)構(gòu)中的一個(gè)節(jié)點(diǎn),用目標(biāo)的狀態(tài)表示節(jié)點(diǎn)的狀態(tài)。同時(shí)本文使用連通圖的概念來(lái)描述相互鄰近的擴(kuò)展目標(biāo),當(dāng)節(jié)點(diǎn)相距較近時(shí),用邊將之連接,構(gòu)成連通圖。這樣,當(dāng)不同節(jié)點(diǎn)可以構(gòu)成連通圖時(shí),表示節(jié)點(diǎn)對(duì)應(yīng)的目標(biāo)相距較近,否則,對(duì)應(yīng)目標(biāo)相距較遠(yuǎn)。

本文使用鄰接矩陣Ak表示k時(shí)刻的圖結(jié)構(gòu),其計(jì)算方法如下:

(4)

式中,ak(i,j)的計(jì)算方法如下:

(5)

鄰接矩陣Ak中為1的位置表示對(duì)應(yīng)的2個(gè)節(jié)點(diǎn)構(gòu)成連通圖,對(duì)應(yīng)目標(biāo)相距較近,存在交叉或靠近運(yùn)動(dòng)。

圖1　圖結(jié)構(gòu)示意圖

4個(gè)擴(kuò)展目標(biāo)T1、T2、T3和T4對(duì)應(yīng)的圖結(jié)構(gòu)如圖1所示,點(diǎn)跡“·”分別表示4個(gè)擴(kuò)展目標(biāo)節(jié)點(diǎn),箭頭表示不同節(jié)點(diǎn)的運(yùn)動(dòng)方向,橢圓表示預(yù)先選定的門限ε,不同節(jié)點(diǎn)之間的連線表示構(gòu)成連通圖的邊。該圖結(jié)構(gòu)對(duì)應(yīng)的鄰接矩陣為:

3　基于mean shift和圖結(jié)構(gòu)的GMPHD擴(kuò)展目標(biāo)跟蹤

3.1　擴(kuò)展目標(biāo)運(yùn)動(dòng)模型和量測(cè)模型

假設(shè)擴(kuò)展目標(biāo)都是線性運(yùn)動(dòng)的,且不同擴(kuò)展目標(biāo)之間的運(yùn)動(dòng)狀態(tài)相互獨(dú)立,其狀態(tài)方程和量測(cè)方程分別為:

xk=Fk-1xk-1+ωk-1

(6)

zk=Hkxk+vk

(7)

式中,xk表示擴(kuò)展目標(biāo)在k時(shí)刻的運(yùn)動(dòng)狀態(tài),Fk為其對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移矩陣;zk表示擴(kuò)展目標(biāo)在該時(shí)刻產(chǎn)生的量測(cè),Hk為其對(duì)應(yīng)的量測(cè)矩陣。ωk表示過(guò)程噪聲,是一個(gè)均值為0,協(xié)方差矩陣為Qk的高斯白噪聲;vk表示量測(cè)噪聲,也是一個(gè)均值為0的高斯白噪聲,其協(xié)方差矩陣用Rk表示。

3.2　算法流程

1) 初始化

根據(jù)所給目標(biāo)初始狀態(tài)集X0,按公式(4)與公式(5)計(jì)算得到初始化鄰接矩陣A0,進(jìn)而得到初始化的圖結(jié)構(gòu)G0。

2) 量測(cè)劃分

(8)

式中，pois(·)表示泊松分布函數(shù)，|Wj|表示子集Wj中的量測(cè)個(gè)數(shù)。

3) 擴(kuò)展目標(biāo)GMPHD濾波

本文重點(diǎn)在于mean shift聚類和圖結(jié)構(gòu)兩部分內(nèi)容,因此這里僅對(duì)擴(kuò)展目標(biāo)GMPHD濾波器進(jìn)行簡(jiǎn)單介紹,濾波器的其他內(nèi)容如預(yù)測(cè)、高斯項(xiàng)的修剪合并以及擴(kuò)展目標(biāo)狀態(tài)提取等可參見(jiàn)文獻(xiàn)[4-5]。假設(shè)k時(shí)刻擴(kuò)展目標(biāo)預(yù)測(cè)強(qiáng)度函數(shù)的高斯混合形式表示為:

(9)

(10)

4) 圖結(jié)構(gòu)更新

依據(jù)狀態(tài)方程對(duì)濾波后的擴(kuò)展目標(biāo)狀態(tài)進(jìn)行一步預(yù)測(cè),得到下一時(shí)刻各擴(kuò)展目標(biāo)的大致位置,并根據(jù)公式(4)與公式(5)計(jì)算下一時(shí)刻的鄰接矩陣,更新圖結(jié)構(gòu)。最后,將代表下一時(shí)刻圖結(jié)構(gòu)信息的鄰接矩陣反饋回量測(cè)劃分步以指導(dǎo)下一時(shí)刻擴(kuò)展目標(biāo)的量測(cè)劃分。

4　仿真實(shí)驗(yàn)與分析

為驗(yàn)證本文所提基于mean shift和圖結(jié)構(gòu)的擴(kuò)展目標(biāo)GMPHD濾波算法的性能,本文通過(guò)仿真對(duì)比所提算法(MSGS-GMPHD)與基于mean shift的擴(kuò)展目標(biāo)GMPHD算法(MS-GMPHD)以及基于距離劃分的擴(kuò)展目標(biāo)GMPHD算法(DP-GMPHD)在同一仿真場(chǎng)景中的跟蹤效果來(lái)驗(yàn)證所提算法的性能。matlab仿真所使用的PC機(jī)硬件平臺(tái)是3.00GHz Inter(R) Pentium(R), 內(nèi)存4.00 GB。

觀測(cè)區(qū)域大小為[-500,500]m×[-500,500]m,考慮存在交叉情況的4個(gè)擴(kuò)展目標(biāo),整個(gè)過(guò)程持續(xù)40 s。目標(biāo)存活時(shí)間為:目標(biāo)1,1～40時(shí)刻;目標(biāo)2,1～40時(shí)刻;目標(biāo)3,25～40時(shí)刻;目標(biāo)4,33～40時(shí)刻。將擴(kuò)展目標(biāo)運(yùn)動(dòng)模型建模為CV模型,采樣時(shí)間間隔為Ts=1 s,各目標(biāo)產(chǎn)生量測(cè)的泊松率為γ(x)=15,目標(biāo)存活概率為ps=0.99,檢測(cè)概率為pd=0.99。雜波平均數(shù)為5,均勻分布在觀測(cè)區(qū)域內(nèi)。本文采用OSPA距離[11]作為算法性能的評(píng)價(jià)指標(biāo),其參數(shù)設(shè)置為p=2,c=200,高斯項(xiàng)的修剪門限T=1×10-5,合并門限U=4,最大高斯項(xiàng)數(shù)設(shè)置為Jmax=100。過(guò)程噪聲標(biāo)準(zhǔn)差設(shè)置為σw=2,量測(cè)噪聲標(biāo)準(zhǔn)差為σv=10,狀態(tài)轉(zhuǎn)移矩陣Fk和量測(cè)矩陣Hk分別為:

單次蒙特卡羅仿真的結(jié)果如圖2所示,從中可以看出,3種算法均可實(shí)現(xiàn)對(duì)擴(kuò)展目標(biāo)的穩(wěn)定跟蹤,但在目標(biāo)交叉時(shí)刻,MS-GMPHD與DP-GMPHD產(chǎn)生了漏估,而本文所提MSGS-GMPHD算法可以給出準(zhǔn)確的估計(jì)。

經(jīng)100次蒙特卡羅仿真后的平均目標(biāo)數(shù)估計(jì)如圖3所示,圖4為其對(duì)應(yīng)的OSPA距離,可以看出,在目標(biāo)交叉時(shí)刻,本文所提算法可以給出更為準(zhǔn)確的估計(jì),而MS-GMPHD與DP-GMPHD均存在漏估問(wèn)題。

運(yùn)行時(shí)間上,100次蒙特卡羅仿真的平均劃分?jǐn)?shù)如圖5所示,各時(shí)刻的平均運(yùn)行時(shí)間如圖6所示。可以看出,傳統(tǒng)的DP-GMPHD算法隨目標(biāo)數(shù)增多,劃分?jǐn)?shù)在不斷增多,運(yùn)算量也隨之增大,運(yùn)算時(shí)間也在不斷增加。由于mean shift能夠直接給出擴(kuò)展目標(biāo)量測(cè)集的正確劃分,因而總是只有一種劃分結(jié)果,運(yùn)算量大幅下降。為了更清楚地看出同樣基于mean shift的2種算法中量測(cè)劃分?jǐn)?shù)和運(yùn)行時(shí)間方面所表現(xiàn)出的異同,將圖5和圖6中DP-GMPHD算法結(jié)果去除,結(jié)果如圖7所示,2種算法劃分?jǐn)?shù)相同,而本文所提算法MSGS-GMPHD由于在交叉時(shí)刻要進(jìn)行子劃分,所以在交叉時(shí)刻運(yùn)算時(shí)間多于MS-GMPHD,但本文算法解決了交叉時(shí)刻擴(kuò)展目標(biāo)數(shù)目的漏估問(wèn)題。

圖2　單次蒙特卡羅仿真　　圖3　目標(biāo)數(shù)估計(jì)結(jié)果圖4　OSPA距離

圖5　量測(cè)劃分?jǐn)?shù)比較　　　　圖6　運(yùn)行時(shí)間比較圖7　MS與MSGS劃分?jǐn)?shù)和運(yùn)行時(shí)間比較

下面給出3種算法運(yùn)行情況的定量比較,結(jié)果如表1中。表中給出了3種算法單次蒙特卡羅仿真的平均量測(cè)劃分?jǐn)?shù)和平均運(yùn)行時(shí)間。

表1　3種算法運(yùn)行情況對(duì)比

從表1可以看出，相比于傳統(tǒng)的DP-GMPHD擴(kuò)展目標(biāo)跟蹤算法，MS-GMPHD和MSGS-GMPHD算法的量測(cè)劃分?jǐn)?shù)大大減少，運(yùn)算效率大幅提升。其中，MS-GMPHD算法的運(yùn)算時(shí)間降低為傳統(tǒng)的DP-GMPHD濾波算法的5.68%，而本文所提MSGS-GMPHD算法則降低為DP-GMPHD算法的6.00%。本文所提MSGS-GMPHD算法的運(yùn)行時(shí)間略高于MS-GMPHD算法，但是本文算法解決了擴(kuò)展目標(biāo)交叉時(shí)刻的漏估問(wèn)題，以極小的時(shí)間代價(jià)獲得了更準(zhǔn)確的估計(jì)結(jié)果。

5　結(jié)　論

本文針對(duì)傳統(tǒng)的基于距離劃分的擴(kuò)展目標(biāo)GMPHD濾波算法量測(cè)劃分?jǐn)?shù)多、運(yùn)算量大的問(wèn)題以及交叉時(shí)刻產(chǎn)生的目標(biāo)數(shù)漏估問(wèn)題，提出一種基于mean shift和圖結(jié)構(gòu)的擴(kuò)展目標(biāo)GMPHD濾波算法。采用mean shift聚類代替?zhèn)鹘y(tǒng)的距離劃分，有效地降低了算法的運(yùn)算量。使用圖理論對(duì)不同擴(kuò)展目標(biāo)間的關(guān)系進(jìn)行建模，實(shí)時(shí)動(dòng)態(tài)地獲取目標(biāo)間的距離關(guān)系，并將該信息反饋回量測(cè)劃分步以判斷是否進(jìn)行子劃分，圖結(jié)構(gòu)的引入很好地解決了目標(biāo)交叉時(shí)刻的漏估問(wèn)題。仿真實(shí)驗(yàn)證明，本文所提MSGS-GMPHD算法擁有比傳統(tǒng)算法更好的估計(jì)性能。