基于改進K-means++聚類的多擴展目標跟蹤算法

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

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

0 引言

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

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

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

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

1 多擴展目標系統模型

1.1 多擴展目標動態演化模型

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

(1)

1.2 多擴展目標量測模型

(2)

2 多擴展目標的量測集劃分問題

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

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

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

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

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

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

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

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

由于K-means++算法中第一個初始中心點是隨機選取，即便余下的初始中心點依據一定的概率選擇，也會因為量測集的不準確劃分導致目標跟蹤性能不穩定。考慮到預測狀態及其個數在一定程度上能為正確劃分量測集提供依據，本文對聚類初始中心點選取方式進行改進，即根據預測狀態選擇其中Jk-1個初始中心點，以增加量測集劃分的可信度，從而大幅度提高聚類效果的穩定性，其劃分流程如圖1所示。

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

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

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

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

3.2 本文算法流程

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

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

(3)

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

(4)

(5)

其中：

(6)

(7)

(8)

(9)

其中：

(10)

(11)

(12)

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

(13)

(14)

(15)

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

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

(17)

其中：

(18)

(19)

(20)

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

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

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

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

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

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

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

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

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

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

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

cp(n-m)))1/p

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

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

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

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

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

圖3 三種量測集劃分方法的X軸目標狀態估計結果Fig. 3 X-axis target state estimation results of three measurement set partition methods

圖4 三種量測集劃分方法的Y軸目標狀態估計結果Fig. 4 Y-axis target state estimation results of three measurement set partition methods

圖5對比了本文算法、K-means++聚類算法和距離劃分算法下的目標勢估計結果，本文算法的聚類結果遠比K-means++聚類算法穩定，并且能準確地估計真實目標個數，其目標勢估計結果甚至優于距離劃分方法，其原因在于本文算法利用目標的預測狀態選擇初始中心點的選擇，為量測集劃分提供了可靠的劃分依據，而準確的量測集劃分結果提高了后續的目標數估計準確度。

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

圖5 三種量測集劃分方法的目標勢估計對比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++聚類算法以及距離劃分算法在每一時刻量測集的劃分數，從而側面得到這三種算法的計算量對比，可以明顯看出量測集劃分次數隨著目標個數增加而增加。即便如此，本文算法依舊具有更少的量測集劃分數，其原因是本文算法為K值設定了取值范圍，減小了每一時刻量測集的劃分次數，大幅度降低了計算量。

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

為了驗證改進K-means++聚類劃分算法在多擴展目標跟蹤中降低計算量的有效性，考慮上述跟蹤場景，并在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|為當前時刻量測集中的量測個數。結合圖5，隨著目標個數增加，每一時刻量測集劃分的次數將呈指數增長，導致整個跟蹤過程時間延長。距離劃分算法基于兩兩量測之間的距離閾值集進行量測集劃分，每一時刻的距離閾值集中包含的閾值個數為|Zk|(|Zk|-1)/2，當量測數大于3時，閾值個數將大于|Zk|，即隨著目標個數增加，每一時刻距離劃分算法的量測集劃分數將遠大于K-means++聚類算法的量測集劃分數，大幅度增加了計算量，故需要更長的時間完成所有擴展目標的跟蹤。結合圖5，本文算法總體量測集劃分數低，并且隨著目標數增加，本文算法的量測集劃分數增加不明顯，其原因在于本文算法對K值取值范圍進行了合理的限制，進而降低量測集劃分次數，大幅度縮短算法的運行時間；同時結合圖4可知，本文算法不以犧牲跟蹤準確度為代價，在大幅度降低計算量的同時保證了目標跟蹤準確度。

本文算法可以根據跟蹤的實際場景重新設置K值的上下限，即K值的遍歷范圍可限制為Jk-1≤K≤Jk-1+Jbeta,k×Jk-1+Jgam,k，其中Jbeta,k表示單個目標可能衍生的目標個數，Jgam,k表示k時刻可能的新生目標個數，因此，改進K-means++聚類劃分方法的計算復雜度為O((Jbeta,k×Jk-1+Jgam,k)×|Zk|)，而原始K-means++聚類的劃分方法的K值遍歷范圍固定為1≤K≤|Zk|，其計算復雜度為O(|Zk|×|Zk|)；距離劃分方法由于是基于兩兩量測之間距離的劃分方法，要求將兩兩量測之間的距離作為距離閾值，以此對量測集進行劃分，其計算復雜度為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往往遠小于多擴展目標量測數的一半，那么本文算法的計算量也要比距離劃分低。綜上，本文算法的計算量要比K-means++聚類的劃分方法和距離劃分方法低。

綜上，根據同一實驗條件下所獲得仿真性能對比結果可得到如下結論：本文算法不但可以得到更為準確的目標狀態和個數估計，而且因其計算量很低，故而適用于應用資源有限的實時多擴展目標跟蹤系統。

5 結語

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

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