俞皓芳，孫力帆,2，付主木

(1.河南科技大學(xué) 信息工程學(xué)院，河南 洛陽471203； 2.電子科技大學(xué) 通信與信息工程學(xué)院，成都611731)

0 引言

多目標(biāo)跟蹤技術(shù)是信息融合方法的重要組成部分，被廣泛用于防空預(yù)警、沿海艦船監(jiān)視、視頻監(jiān)控、智能交通管理系統(tǒng)、移動機器人定位與導(dǎo)航和定位等軍事和民用領(lǐng)域。多目標(biāo)跟蹤的本質(zhì)是使用含雜波的傳感器量測數(shù)據(jù)集持續(xù)地對多個動態(tài)目標(biāo)的運動狀態(tài)和目標(biāo)個數(shù)進行估計[1]，其準(zhǔn)確度直接影響到多目標(biāo)的跟蹤效果。傳統(tǒng)多目標(biāo)跟蹤算法[2-3]均基于“點目標(biāo)”假設(shè)(即將距離傳感器較遠的目標(biāo)建模為點目標(biāo)，并假設(shè)其每一時刻最多只能生成一個量測)，通常利用量測與目標(biāo)點源之間的某種數(shù)據(jù)關(guān)聯(lián)將量測數(shù)據(jù)分配給某個目標(biāo)，但是點源數(shù)量與位置的不確定性影響數(shù)據(jù)關(guān)聯(lián)的準(zhǔn)確性，從而難以應(yīng)對目標(biāo)個數(shù)未知、雜波密集等環(huán)境，為此，在多點目標(biāo)跟蹤算法中引入隨機有限集(Random Finite Set, RFS)概念[4]，該方法不僅能避免量測和目標(biāo)之間的數(shù)據(jù)關(guān)聯(lián)，而且能對實際場景中多目標(biāo)跟蹤涉及到的目標(biāo)出現(xiàn)、分裂、消失以及傳感器漏檢和虛警雜波等現(xiàn)象進行嚴格的數(shù)學(xué)描述。Mahler[5]提出了一種概率假設(shè)密度(Probability Hypothesis Density，PHD)濾波器，它是后驗概率密度的一階矩，也稱為定義在單目標(biāo)狀態(tài)空間上的強度函數(shù)。PHD濾波器不但能夠?qū)崟r地迭代更新后驗概率強度，還具有無需數(shù)據(jù)關(guān)聯(lián)、計算量低、估計精度高、易于實現(xiàn)等優(yōu)勢。

近年來，隨著高分辨率傳感器的飛速發(fā)展以及戰(zhàn)爭環(huán)境的復(fù)雜多變性，當(dāng)目標(biāo)較大或者目標(biāo)距離高分辨率傳感器較近時，目標(biāo)回波可能占據(jù)傳感器的多個分辨單元，導(dǎo)致同一目標(biāo)每一時刻產(chǎn)生多個量測。為更貼近實際跟蹤場景，此類目標(biāo)通常稱為多擴展目標(biāo)[1]。不同于傳統(tǒng)點目標(biāo)，擴展目標(biāo)跟蹤還需要定義多個量測產(chǎn)生過程，為其空間擴展建?；?qū)α繙y集進行有效的劃分[6-8]，以能合理而又準(zhǔn)確描述目標(biāo)狀態(tài)與測量值之間的關(guān)系，故而無法直接使用PHD濾波器實現(xiàn)多擴展目標(biāo)狀態(tài)和個數(shù)的精確估計。文獻[9-12]中提出基于PHD濾波器框架的多擴展目標(biāo)跟蹤算法，以擴展目標(biāo)PHD(Extended Target PHD， ET-PHD)濾波器、擴展目標(biāo)CPHD(Extended Target Cardinalized PHD，ET-CPHD)濾波器、擴展目標(biāo)高斯混合PHD(Extended Target Gaussian Mixture PHD，ET-GM-PHD)濾波器、擴展目標(biāo)高斯混合CPHD(Extended Target Gaussian Mixture Cardinalized PHD， ET-GM-CPHD)濾波器等為代表的濾波器被廣泛應(yīng)用于多擴展目標(biāo)跟蹤中。

上述濾波器均假定量測個數(shù)服從泊松分布且隨機散布在目標(biāo)參考點(可以是質(zhì)心或任何其他點，取決于擴展目標(biāo)的范圍和形狀)周圍空間上[3]，每一時刻觀測到的量測是一組點，而不是幾何結(jié)構(gòu)的整體。故在PHD濾波器框架下，現(xiàn)有眾多算法需要完全劃分量測集，目的是盡可能將源自同一目標(biāo)的量測劃分在同一子集中，其劃分的合理性和準(zhǔn)確性將直接影響后續(xù)跟蹤算法中目標(biāo)狀態(tài)和個數(shù)估計的聯(lián)合性能。傳統(tǒng)量測集劃分方法充分考慮所有可能的劃分，故每一時刻的劃分次數(shù)將隨著目標(biāo)數(shù)增多而變得十分龐大，僅適合擴展目標(biāo)數(shù)量較少的跟蹤場景。Granstr?m等[13]提出一種距離劃分方法以減小計算負擔(dān)，即根據(jù)經(jīng)驗縮小距離閾值范圍，但是其劃分次數(shù)仍然會隨著量測個數(shù)增加而大幅度增加，且在目標(biāo)距離相近環(huán)境下目標(biāo)數(shù)估計不準(zhǔn)確。此外，該方法在PHD濾波更新過程中，會出現(xiàn)因不合理的量測集劃分而額外帶來的計算負荷，特別是在雜波密度較大時，無法取得較為理想的跟蹤效果。K-means聚類算法能將量測集劃分為K個子集，由于多擴展目標(biāo)跟蹤過程中目標(biāo)數(shù)未知且時變，故通常設(shè)置K值區(qū)間為[1，|Zk|]，并通過遍歷K值得到不同的量測集劃分結(jié)果，但是隨著量測個數(shù)增加，K值范圍將擴大，導(dǎo)致量測集劃分次數(shù)十分龐大，造成極大的計算負擔(dān)，同時聚集初始點選取受到隨機性影響，使得量測集劃分非常不穩(wěn)定，從而導(dǎo)致目標(biāo)數(shù)估計存在較大誤差[11,14]。文獻[15]對聚類初始點的選取進行了改進并提出了K-means++聚類算法，該算法雖然提高了量測集劃分的穩(wěn)定性，但是沒有明確討論K的取值范圍，而K的取值直接影響劃分量測集的速度。此外，相比于距離度量所進行的量測集劃分，其目標(biāo)狀態(tài)和個數(shù)估計精度未必得以提升，而且也存在目標(biāo)相近時量測集劃分不準(zhǔn)確的問題。

鑒于上述問題，本文提出一種基于改進K-means++聚類算法的ET-GM-PHD濾波器，旨在準(zhǔn)確劃分量測集以提升多擴展目標(biāo)跟蹤性能。該方法設(shè)置K的上下限，首先利用預(yù)測狀態(tài)選擇初始中心點，然后計算每個量測到初始中心點的距離并遍歷K值，從而最終得到量測集的所有劃分。實驗結(jié)果表明，相比于距離劃分和K-means++劃分方法，該方法能提高聚類算法的穩(wěn)定性，大幅度降低計算復(fù)雜度，同時保證多擴展目標(biāo)的跟蹤效果。

1 多擴展目標(biāo)系統(tǒng)模型

1.1 多擴展目標(biāo)動態(tài)演化模型

若每個目標(biāo)狀態(tài)的動態(tài)演化相互獨立，且服從線性高斯運動模型，則狀態(tài)集合Xk中每個目標(biāo)的動態(tài)演化模型為：

(1)

1.2 多擴展目標(biāo)量測模型

(2)

2 多擴展目標(biāo)的量測集劃分問題

除了距離劃分方法，聚類算法也可用于量測集劃分。以K-means聚類算法為例，為了得到多個可能的劃分，一般使量測子集數(shù)K在[1,|Zk|]區(qū)間內(nèi)遍歷，其中|Zk|表示當(dāng)前時刻量測集中量測的個數(shù)；然而，使用K-means聚類算法進行量測集劃分所取得的跟蹤性能不穩(wěn)定，其原因在于K-means聚類算法中初始中心點采用隨機選取。針對上述問題，文獻[15]中提出了K-means++算法，根據(jù)選擇概率來確定初始中心點。雖然該方法在一定程度提高了聚類結(jié)果的穩(wěn)定性；但是易受到雜波干擾，以致后續(xù)的量測集劃分準(zhǔn)確度不高，從而無法獲得較為優(yōu)異的多擴展目標(biāo)跟蹤性能。

3 改進的ET-GM-PHD濾波器

3.1 改進K-means++聚類算法的多擴展目標(biāo)量測集劃分

由于每一時刻的擴展目標(biāo)個數(shù)K未知，其取值范圍通常為[KL,KU]，上下限取值一般為KL=1，KU=|Zk|；然而在此區(qū)間內(nèi)遍歷K值，每一時刻得到的量測劃分集合會隨著量測個數(shù)的增多而呈指數(shù)增長，從而導(dǎo)致計算量大幅度增加。

因此，本文考慮下一時刻目標(biāo)可能出現(xiàn)的情況縮小K值范圍，具體分析如下：若k-1時刻已存在目標(biāo)xk-1，則在k時刻，該目標(biāo)可能繼續(xù)存在，或者衍生出新的目標(biāo)xbeta,k-1；若k-1時刻不存在的目標(biāo)xgam,k，則它有可能在k時刻出現(xiàn)。

綜上所述，假設(shè)k-1時刻估計得到的目標(biāo)個數(shù)為Jk-1，Jbeta,k表示單個目標(biāo)可能衍生的目標(biāo)個數(shù)，Jgam,k表示k時刻可能的新生目標(biāo)個數(shù)，若令KL=Jk-1，那么KU=Jk-1+Jbeta,k×Jk-1+Jgam,k，相應(yīng)地

Jk-1≤K≤Jk-1+Jbeta,k×Jk-1+Jgam,k

其中Jbeta,k、Jgam,k通常未知，一般使用k-1時刻的目標(biāo)個數(shù)Jk-1所代替。

由于K-means++算法中第一個初始中心點是隨機選取，即便余下的初始中心點依據(jù)一定的概率選擇，也會因為量測集的不準(zhǔn)確劃分導(dǎo)致目標(biāo)跟蹤性能不穩(wěn)定?？紤]到預(yù)測狀態(tài)及其個數(shù)在一定程度上能為正確劃分量測集提供依據(jù)，本文對聚類初始中心點選取方式進行改進，即根據(jù)預(yù)測狀態(tài)選擇其中Jk-1個初始中心點，以增加量測集劃分的可信度，從而大幅度提高聚類效果的穩(wěn)定性，其劃分流程如圖1所示。

圖1 量測集劃分流程Fig. 1 Flowchart of measurement set partition

4)計算每個量測到初始中心點集合C內(nèi)每個初始中心點的距離，依據(jù)最小距離對量測集進行劃分。

6)重復(fù)步驟4)、5)，直到中心點幾乎不變。

7)遍歷K值，最終得到不同的量測集劃分結(jié)果。

3.2 本文算法流程

文獻[1]中針對多擴展目標(biāo)跟蹤提出了ET-GM-PHD濾波器。對比標(biāo)準(zhǔn)的GM-PHD濾波器[13]，ET-GM-PHD的預(yù)測方程、刪減合并高斯混合項以及狀態(tài)提取步驟與GM-PHD濾波器一致，最大的不同在于量測更新部分，其主要原因是擴展目標(biāo)不同于傳統(tǒng)點目標(biāo)，每一時刻同一目標(biāo)至少產(chǎn)生多個量測的性質(zhì)決定ET-GM-PHD的量測更新步驟不再是簡單地將所有量測逐一進行高斯混合項更新。本文針對K-means++聚類算法隨機選取初始中心點導(dǎo)致聚類精度不高、跟蹤效果不理想的問題，考慮目標(biāo)個數(shù)在下一時刻的可能動態(tài)變化以及預(yù)測狀態(tài)為準(zhǔn)確劃分量測集提供的可靠信息，提出了一種基于改進K-means++量測集劃分的ET-GM-PHD濾波器算法。

假設(shè)擴展目標(biāo)的動態(tài)演化和量測生成機制均為線性高斯模型，如式(1)和(2)所示。由于擴展目標(biāo)的存活概率、傳感器的檢測概率和目標(biāo)狀態(tài)相互獨立，預(yù)測強度函數(shù)和后驗強度函數(shù)均為高斯混合形式，則ET-GM-PHD濾波器的預(yù)測方程描述如下：

(3)

由ET-PHD濾波器的更新方程推導(dǎo)得到ET-GM-PHD濾波器更新如下：

(4)

(5)

其中：

(6)

(7)

(8)

(9)

其中：

(10)

(11)

(12)

Γ(j)=e-γ(γ)|W|

(13)

(14)

(15)

其中：ωP表示對應(yīng)劃分P的權(quán)重；δ|W|,1表示克羅內(nèi)克函數(shù)；|W|表示單元W中量測的個數(shù)；ck(zk)表示由雜波產(chǎn)生量測的分布函數(shù)，一般假設(shè)其服從均勻分布；λk表示由雜波產(chǎn)生量測個數(shù)的期望，通常設(shè)為常數(shù)λ。

濾波算法中其余的高斯分量均值和協(xié)方差更新可直接在卡爾曼濾波框架內(nèi)進行。需要注意的是，所有劃分結(jié)果均由本文提出的改進K-means++量測劃分方法得到，另外本文不同于傳統(tǒng)GM-PHD濾波器的更新步，該算法需用所有分區(qū)中每個子集單元W更新每個高斯分量，具體計算如下：

(17)

其中：

(18)

(19)

(20)

綜上，本文提出的算法流程歸納如下：

1)已知k-1時刻的目標(biāo)強度函數(shù)Dk-1|k-1(x)，計算得到k時刻的預(yù)測目標(biāo)強度函數(shù)Dk|k-1(x)；

2)利用k-1時刻的目標(biāo)個數(shù)Jk-1|k-1計算得到K值取值區(qū)間[KL,KU]，其中包含nK個不同的K值；

3)對于任意整數(shù)ki∈[KL,KU]，利用預(yù)測目標(biāo)強度函數(shù)中高斯混合項的均值得到改進K-means++量測集劃分方法的初始中心點集C={c1,c2,…,cki}；

4)利用改進K-means++量測集劃分方法將k時刻的量測集Zk劃分為ki個子集；

5)重復(fù)步驟3)、4)，依次遍歷K值，得到nK種不同的劃分結(jié)果；

6)將量測集的所有劃分結(jié)果代入式(4)、(5)、(9)對預(yù)測目標(biāo)強度函數(shù)進行更新，得到更新后的目標(biāo)強度函數(shù)Dk|k(x)；

7)對更新后的目標(biāo)強度函數(shù)的高斯混合項進行刪除合并、狀態(tài)提取，得到目標(biāo)狀態(tài)和個數(shù)估計。

4 仿真實驗對比與性能評估

其中σW=2 m/s2，σe=20 m。

圖2 真實目標(biāo)運動軌跡及觀測Fig. 2 Trajectories and measurements of true objects

cp(n-m)))1/p

仿真使用計算機的CPU為Intel Core i3- 2130、內(nèi)存為4 GB，仿真實驗使用的量測數(shù)據(jù)由Matlab代碼產(chǎn)生。為驗證所提方法的有效性，在以上場景中與現(xiàn)有方法進行跟蹤性能對比。

1)MK-means++：本文提出基于改進K-means++量測劃分的多擴展目標(biāo)跟蹤算法。

2)K-means++：基于K-means++量測劃分的多擴展目標(biāo)跟蹤算法。

3)DP(Distance Partition)：基于距離度量量測劃分的多擴展目標(biāo)跟蹤算法。

圖3～4是在相同運行環(huán)境下，分別采用本文算法、K-means++聚類算法和基于距離度量的量測劃分算法得到的X、Y軸目標(biāo)狀態(tài)跟蹤結(jié)果。對比圖3(a)、圖3(c)、圖4(a)和圖4(c)，可以粗略地判斷本文算法與距離劃分算法的多擴展目標(biāo)跟蹤效果接近。圖3(b)和圖4(b)顯示K-means++聚類算法的跟蹤效果十分不理想，尤其當(dāng)目標(biāo)數(shù)增加時，不能完整跟蹤所有目標(biāo)，其主要原因是K-means++聚類算法隨機選取初始中心點，導(dǎo)致量測集劃分不合理，直接影響多擴展目標(biāo)跟蹤效果。

圖3 三種量測集劃分方法的X軸目標(biāo)狀態(tài)估計結(jié)果Fig. 3 X-axis target state estimation results of three measurement set partition methods

圖4 三種量測集劃分方法的Y軸目標(biāo)狀態(tài)估計結(jié)果Fig. 4 Y-axis target state estimation results of three measurement set partition methods

圖5對比了本文算法、K-means++聚類算法和距離劃分算法下的目標(biāo)勢估計結(jié)果，本文算法的聚類結(jié)果遠比K-means++聚類算法穩(wěn)定，并且能準(zhǔn)確地估計真實目標(biāo)個數(shù)，其目標(biāo)勢估計結(jié)果甚至優(yōu)于距離劃分方法，其原因在于本文算法利用目標(biāo)的預(yù)測狀態(tài)選擇初始中心點的選擇，為量測集劃分提供了可靠的劃分依據(jù)，而準(zhǔn)確的量測集劃分結(jié)果提高了后續(xù)的目標(biāo)數(shù)估計準(zhǔn)確度。

圖6是三種算法的OSPA距離對比。圖5可以更加清晰地看出，相比于K-means++聚類算法，本文算法能大幅度改善目標(biāo)的跟蹤效果，并且不論從目標(biāo)個數(shù)估計還是目標(biāo)狀態(tài)估計的角度，本文算法皆具有比距離劃分算法較好的效果，其原因是本文算法利用預(yù)測狀態(tài)提高聚類精度，大幅度提高了目標(biāo)狀態(tài)和個數(shù)估計的準(zhǔn)確性。

圖5 三種量測集劃分方法的目標(biāo)勢估計對比Fig. 5 Comparison of target number estimated by three measurement set partition methods

圖6 三種量測集劃分方法的OSPA距離對比Fig. 6 Comparison of OSPA distance of three measurement set partition methods

圖7對比本文算法、K-means++聚類算法以及距離劃分算法在每一時刻量測集的劃分數(shù)，從而側(cè)面得到這三種算法的計算量對比，可以明顯看出量測集劃分次數(shù)隨著目標(biāo)個數(shù)增加而增加。即便如此，本文算法依舊具有更少的量測集劃分數(shù)，其原因是本文算法為K值設(shè)定了取值范圍，減小了每一時刻量測集的劃分次數(shù)，大幅度降低了計算量。

圖7 三種量測集劃分方法的量測集劃分數(shù)對比Fig. 7 Comparison of partition number of three measurement set partition methods

為了驗證改進K-means++聚類劃分算法在多擴展目標(biāo)跟蹤中降低計算量的有效性，考慮上述跟蹤場景，并在Matlab軟件上采用50次Monte Carlo仿真進行對比，得到MK-means++、K-means++、DP的平均運行時間分別為72.857 1 s、155.832 5 s、178.398 1 s。由此可見，本文算法的平均運行時間遠遠低于K-means++和DP，分別降低了53.25%和59.16%。每一時刻，K-means++聚類算法要遍歷K值，共需進行|Zk|次劃分，其中|Zk|為當(dāng)前時刻量測集中的量測個數(shù)。結(jié)合圖5，隨著目標(biāo)個數(shù)增加，每一時刻量測集劃分的次數(shù)將呈指數(shù)增長，導(dǎo)致整個跟蹤過程時間延長。距離劃分算法基于兩兩量測之間的距離閾值集進行量測集劃分，每一時刻的距離閾值集中包含的閾值個數(shù)為|Zk|(|Zk|-1)/2，當(dāng)量測數(shù)大于3時，閾值個數(shù)將大于|Zk|，即隨著目標(biāo)個數(shù)增加，每一時刻距離劃分算法的量測集劃分數(shù)將遠大于K-means++聚類算法的量測集劃分數(shù)，大幅度增加了計算量，故需要更長的時間完成所有擴展目標(biāo)的跟蹤。結(jié)合圖5，本文算法總體量測集劃分數(shù)低，并且隨著目標(biāo)數(shù)增加，本文算法的量測集劃分數(shù)增加不明顯，其原因在于本文算法對K值取值范圍進行了合理的限制，進而降低量測集劃分次數(shù)，大幅度縮短算法的運行時間；同時結(jié)合圖4可知，本文算法不以犧牲跟蹤準(zhǔn)確度為代價，在大幅度降低計算量的同時保證了目標(biāo)跟蹤準(zhǔn)確度。

本文算法可以根據(jù)跟蹤的實際場景重新設(shè)置K值的上下限，即K值的遍歷范圍可限制為Jk-1≤K≤Jk-1+Jbeta,k×Jk-1+Jgam,k，其中Jbeta,k表示單個目標(biāo)可能衍生的目標(biāo)個數(shù)，Jgam,k表示k時刻可能的新生目標(biāo)個數(shù)，因此，改進K-means++聚類劃分方法的計算復(fù)雜度為O((Jbeta,k×Jk-1+Jgam,k)×|Zk|)，而原始K-means++聚類的劃分方法的K值遍歷范圍固定為1≤K≤|Zk|，其計算復(fù)雜度為O(|Zk|×|Zk|)；距離劃分方法由于是基于兩兩量測之間距離的劃分方法，要求將兩兩量測之間的距離作為距離閾值，以此對量測集進行劃分，其計算復(fù)雜度為O(|Zk|×(|Zk|+1)/2)。

由于Jbeta,k、Jgam,k均用Jk-1近似，而Jbeta,k×Jk-1+Jgam,k比|Zk|小，所以本文算法的計算量要比K-means++聚類劃分方法低。同理在實際跟蹤場景中，Jbeta,k×Jk-1+Jgam,k往往遠小于多擴展目標(biāo)量測數(shù)的一半，那么本文算法的計算量也要比距離劃分低。綜上，本文算法的計算量要比K-means++聚類的劃分方法和距離劃分方法低。

綜上，根據(jù)同一實驗條件下所獲得仿真性能對比結(jié)果可得到如下結(jié)論：本文算法不但可以得到更為準(zhǔn)確的目標(biāo)狀態(tài)和個數(shù)估計，而且因其計算量很低，故而適用于應(yīng)用資源有限的實時多擴展目標(biāo)跟蹤系統(tǒng)。

5 結(jié)語

雖然現(xiàn)有基于距離度量和K-means++聚類的量測集劃分方法能在一定程度上提高了跟蹤精度，但卻是以較高的計算復(fù)雜度為代價。針對這一問題，本文提出了一種基于改進K-means++聚類算法的多擴展目標(biāo)跟蹤算法，該方法首先依據(jù)下一時刻目標(biāo)個數(shù)可能變化情況，縮小K值遍歷范圍；然后利用預(yù)測狀態(tài)選取改進K-means++聚類算法的初始中心點，以此遍歷K值得到不同的量測集劃分結(jié)果。實驗結(jié)果表明：該方法極大程度上提高了K-means++聚類算法的聚類精度，得到比距離劃分算法較好的目標(biāo)跟蹤效果，同時其計算量遠遠低于距離劃分算法和K-means++聚類算法。

下一步的研究將針對多個擴展目標(biāo)相近時由量測集劃分不準(zhǔn)確而導(dǎo)致的目標(biāo)個數(shù)低估問題提出更有效的方法。近年來，隨著現(xiàn)代傳感器分辨率的提高可以得到擴展目標(biāo)的擴展形態(tài)估計，但在多擴展目標(biāo)跟蹤場景中很難同時解決多個擴展目標(biāo)的跟蹤和識別問題，因此，如何快速、有效地實現(xiàn)多擴展目標(biāo)的聯(lián)合跟蹤和識別會是我們的研究重點。