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

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

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

0 引言

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

近年來，隨著高分辨率傳感器的飛速發(fā)展以及戰(zhàn)爭環(huán)境的復雜多變性，當目標較大或者目標距離高分辨率傳感器較近時，目標回波可能占據(jù)傳感器的多個分辨單元，導致同一目標每一時刻產生多個量測。為更貼近實際跟蹤場景，此類目標通常稱為多擴展目標[1]。不同于傳統(tǒng)點目標，擴展目標跟蹤還需要定義多個量測產生過程，為其空間擴展建模或對量測集進行有效的劃分[6-8]，以能合理而又準確描述目標狀態(tài)與測量值之間的關系，故而無法直接使用PHD濾波器實現(xiàn)多擴展目標狀態(tài)和個數(shù)的精確估計。文獻[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)濾波器等為代表的濾波器被廣泛應用于多擴展目標跟蹤中。

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

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

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

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

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

(1)

1.2 多擴展目標量測模型

(2)

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

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

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

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

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

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

綜上所述，假設k-1時刻估計得到的目標個數(shù)為Jk-1，Jbeta,k表示單個目標可能衍生的目標個數(shù)，Jgam,k表示k時刻可能的新生目標個數(shù)，若令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時刻的目標個數(shù)Jk-1所代替。

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

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

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

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

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

3.2 本文算法流程

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

假設擴展目標的動態(tài)演化和量測生成機制均為線性高斯模型，如式(1)和(2)所示。由于擴展目標的存活概率、傳感器的檢測概率和目標狀態(tài)相互獨立，預測強度函數(shù)和后驗強度函數(shù)均為高斯混合形式，則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表示克羅內克函數(shù)；|W|表示單元W中量測的個數(shù)；ck(zk)表示由雜波產生量測的分布函數(shù)，一般假設其服從均勻分布；λk表示由雜波產生量測個數(shù)的期望，通常設為常數(shù)λ。

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

(17)

其中：

(18)

(19)

(20)

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

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

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

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

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

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

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

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

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，仿真實驗使用的量測數(shù)據(jù)由Matlab代碼產生。為驗證所提方法的有效性，在以上場景中與現(xiàn)有方法進行跟蹤性能對比。

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

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

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

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

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

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

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

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

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

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

本文算法可以根據(jù)跟蹤的實際場景重新設置K值的上下限，即K值的遍歷范圍可限制為Jk-1≤K≤Jk-1+Jbeta,k×Jk-1+Jgam,k，其中Jbeta,k表示單個目標可能衍生的目標個數(shù)，Jgam,k表示k時刻可能的新生目標個數(shù)，因此，改進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往往遠小于多擴展目標量測數(shù)的一半，那么本文算法的計算量也要比距離劃分低。綜上，本文算法的計算量要比K-means++聚類的劃分方法和距離劃分方法低。

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

5 結語

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

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