基于二級CFSFDP的擴展目標量測集劃分算法

遲珞珈,馮新喜,蒲 磊,曹 倬

(空軍工程大學 信息與導航學院,西安 710077)

0 概述

在傳統的目標跟蹤問題中,通常忽略目標的外形而將目標簡化為一個點,即假設一個目標只能產生一個量測,但隨著科學技術的發展,雷達等傳感器的分辨率不斷提高,使得一個目標在一個采樣周期內可產生多個量測,通常稱這種目標為擴展目標[1-3]。

近年來,人們越來越重視雜波環境下多擴展目標的跟蹤問題。傳統算法中需要對數據進行關聯,但其計算復雜度較高,容易出現組合爆炸,且在實用性和可靠性上面臨著考驗。對此,文獻[3]在隨機集理論基礎上,提出了擴展目標概率假設密度(Probability Hypothesis Density,PHD)濾波,有效避免了數據關聯問題。隨后,勢概率假設密度(Cardinalized Probability Hypothesis Density,CPHD)濾波、擴展目標高斯混合PHD濾波[4]、擴展目標高斯混合CPHD濾波[5]等濾波算法又相繼提出。但無論采取哪種濾波算法,在擴展目標跟蹤問題中都涉及到量測集的劃分,直接決定了整個跟蹤算法的復雜度與狀態估計的精確度。同時,由于擴展目標的提出,使得量測集的劃分數目隨量測數的增加而急劇上升[6-8]。因此,急需尋找一種快速高效的量測集劃分算法。針對此問題,文獻[1,4]提出了基于距離的劃分算法。但由于跟蹤過程中存在大量的雜波噪聲,同時對擴展目標的形狀存在不確定性,因此很難精準劃分量測集。此外,為了找到正確的劃分,需要選取閥值區間中所有的值,這樣做增加了算法的計算量及時間復雜度,影響跟蹤算法的實時性。文獻[9-10]提出了一種基于K-means聚類法的量測集劃分算法。該算法運算速度較快,適用于大量樣本的情況,但聚類結果受初始聚類中心隨機性的影響很大。文獻[11]提出了一種基于模糊自適應共振原理(Adaptive Resonance Theory,ART)的擴展目標量測集劃分算法,相比于現有的距離劃分法和其它聚類算法,模糊ART算法劃分的速度更快且具有較好的穩定性,但是對步長的選擇比較敏感。文獻[12]提出一種利用譜聚類進行量測集的劃分算法,但需要人為確定聚類數目,且存在對初始聚類中心敏感和魯棒性較差等問題。

2014年,文獻[13]提出一種基于密度峰值的空間聚類算法CFSFDP(Clustering by Fast Search and Find of Density Peaks),這種算法對目標的外形不敏感,可實現對任意外形目標的量測集劃分。在此基礎上,本文針對雜波環境下多擴展目標高斯混合PHD量測集劃分難、計算量大的問題,提出一種基于局部異常因子去噪和二級CFSFDP算法的擴展目標量測集劃分算法。

1 擴展目標高斯混合PHD濾波器

擴展目標與點目標產生的量測空間區別如圖1所示,根據文獻[3]所提出的擴展目標PHD濾波模型,假設每個采樣時刻傳感器得到每個目標產生的擴展目標觀測數服從Poisson分布,且擴展目標的觀測服從以目標質心為均值的Gaussian分布。

圖1 點目標與擴展目標示意圖

根據簡單的數學知識,很容易得到每個目標實際被檢測到的概率,其表達式為:

(1)

假設1目標狀態方程和傳感器的觀測方程是線性高斯模型,即:

fk|k-1(xk|xk-1)=N(xk;Fk-1xk-1,Qk-1)

(2)

fk(zk|xk)=N(zk;Hkxk,Rk)

(3)

假設2目標存活和檢測概率與目標狀態獨立,即:

pD,k(xk)=pD,k

(4)

pS,k(xk-1)=pS,k

(5)

假設3目標的強度函數為高斯和的形式,即:

(6)

通常稱滿足以上假設的算法為擴展目標高斯混合PHD濾波算法。

假設已知k-1時刻目標的強度函數γk-1|k-1(x),則擴展目標高斯混合PHD濾波器的預測步和更新步可表示如下:

1)預測步

(7)

2)更新步

γk|k(x|Z)=LZ(x)γk|k-1(x|Z)

(8)

(9)

其中,LZ(x)表示量測偽似然函數,對傳感器檢測概率、噪聲模型、虛警等特性進行了全面的描述,其表達式為:

(10)

k時刻目標后驗概率γk|k(x)包括兩部分,分別用于處理未檢測目標和檢測到目標的情況。詳細推導公式可以參見文獻[1]。

對于擴展目標量測集的劃分給出如下實例。若某一時刻傳感器獲得的量測集Z={z1,z2,z3},則其所有劃分為:

D1={{z1,z2,z3}}

D2={{z1},{z2},{z3}}

D3={{z1,z2},{z3}}

D4={{z1,z3},{z2}}

D5={{z1},{z2,z3}}

(11)

顯然,量測集的所有可能劃分隨著量測數的增加而急劇上升,尤其是在雜波密集的環境下,其計算量和時間消耗更是成指數倍增長。因此,急需尋找一種合理可行的量測集劃分算法。

2 基于二級CFSFDP算法的量測集劃分

2.1 局部異常因子去噪

由于傳感器獲得的觀測數據中不但包含對目標觀測的有用信息,也包含著雜波信息,同時這些雜波均勻的分布在觀測空間中,對量測集的劃分存在很大的干擾。本文首先采用局部異常因子來對量測為雜波的程度進行度量,通過設定閾值的算法進行雜波濾除,接著將層次聚類與新近發表在《Science》上的采用密度極點的算法相結合對量測集進行劃分,提高了量測集劃分的準確度。

局部異常因子(Local Outlier Factor,LOF)是一種基于密度的離群點檢測算法,它通過判斷觀測樣本與其最近鄰k個鄰居的孤立程度來考慮數據的孤立性,實現對偏離大部分數據的異常數據進行檢測。

首先,計算x到x′的可達距離:

RDk(x,x′)=max(k-distance(x′),d(x-x′))

(12)

其中,k-distance(x)表示樣本x與離它第k近的樣本之間的距離,d(x-x′)表示x與x′之間的距離。

然后,計算x的局部可達密度:

(13)

應用這個局部可達密度,可計算出x的局部異常因子:

(14)

圖2表示局部異常因子的實例,可見,偏離大部分正常值的數據點具有較高的異常值。各個樣本周圍的圓的半徑與樣本的局部異常因子的值成正比,圓的半徑越大,其樣本越傾向于異常值。經多次實驗仿真,本文設局部異常因子大于2的點為異常值。

圖2 局部異常因子實例

2.2 二級CFSFDP量測集劃分算法

2.2.1 CFSFDP算法

2014年,文獻[13]提出了一種新的聚類算法CFSFDP。該算法簡單新穎、靈活性強,對目標的外形信息不敏感,可以有效處理大數據集,同時解決了聚類初始中心選擇難的問題。CFSFDP算法的主要思想為在一個類族中,密度高的類中心總是被密度較低的鄰居點包圍,且與具有更高密度的任何點都有相對較大的距離。該算法處理流程是:1)通過密度極點確定聚類中心;2)按照一定順序將數據點歸類到距離其最近且密度比它自身密度高的點所屬的類中。

對于每一個數據點,該算法只需要計算局部密度ρi、該數據點與密度比它高的最近點的距離δi。算法具體步驟為:

步驟1計算觀測點間的距離,構造相似度矩陣。

步驟2通過相似度矩陣和截斷距離計算每個觀測點的局部密度ρi。

步驟3計算每個觀測點與密度比它高的最近點的距離δi。

步驟4使用每一個觀測點確定的(ρi,δi)建立決策圖,確定聚類中心。

步驟5按密度降序對觀測集劃分。

算法偽代碼如下:

輸入觀測集為X={X1,X2,…,Xn};截斷距離為dc

輸出聚類結果為C={C1,C2,…,Cn}

for each point i do

for each point j do

dij=distance from i to j;

//計算每對數據點之間的距離

endfor

endfor

for each point i do

ρi=∑jχ(dij-dc) ;

//計算數據點的局部密度

endfor

//畫出決策樹,確定聚類中心

sort points by density descend order;

for each point I do

Ci=Cnearest_higer_density_neighbor(i);

//對量測集按密度降序排序,然后按此順序對數據點//分配,進行聚類

endfor

該算法存在一個很大的缺陷,即當某一類中存在多個密度極點時,那么,一個類將被錯誤的劃分成多個子簇,造成量測集劃分不準確的后果。在實際擴展目標跟蹤問題中,跟蹤的目標存在多種多樣的外形特征,不同的外形可能會導致由傳感器獲得的量測集中存在多個密度極點的現象,此時,若采用CFSFDP聚類對量測集進行劃分,則可能錯誤的將一個目標劃分為多個目標。因此,還需要考慮對劃分的類再進行合并,以此來實現對任意外形目標的量測集劃分,確保算法的跟蹤性能。

2.2.2 層次聚類合并準則

在一個多維空間中,不同聚類間通過低密度點集進行劃分,每一個聚類都可以表示為一個密度分布相對密集的連通區域。由以上聚類劃分思想,即聚類是相對密集的連通區域,聚類之間通過含有密度相對較低的點集的區域來劃分的原則,因此相對整個聚類來說,聚類邊界的密度是較低的。由此,提出一種合理的假設,即聚類邊界區域密度小于聚類平均密度[15-16],當邊界密度大于等于聚類平均密度時,則被認為是劃分開的不完整聚類的子簇。平均密度和邊界區域密度的計算公式定義如下:

(15)

(16)

其中,|Ci|表示第i個聚類中觀測點的總數,ρk表示每個觀測點的局部密度。聚類合并判定準則如下:

ρbord(Ci,Cj)≥ρavg(Ci)

(17)

ρbord(Ci,Cj)≥ρavg(Cj)

(18)

當式(16)或式(17)成立時,則判定Ci、Cj屬于同一聚類,此時需將Ci、Cj進行聚類合并;反之,則無需進行合并。該聚類合并準則,只需遍歷一次由CFSFDP算法劃分的子簇,即可將滿足條件的所有子簇合并得到最終的聚類劃分結果,本文稱之為二級聚類的CFSFDP量測集劃分。

2.2.3 二級CFSFDP算法

由于CFSFDP算法能夠高效準確地確定密度峰值點,層次聚類能對其存在的將一個類錯誤劃分成多個子類的缺陷制定合并準則,因此本文采用將CFSFDP 算法與層次聚類相結合的二級CFSFDP算法對擴展目標量測集進行劃分。該算法對目標的外形不敏感,可實現對任意外形目標的量測集劃分,如圖3所示。由圖3可以看出,使用二級CFSFDP聚類算法對量測集進行劃分,能夠在目標處于雜波、近鄰、存在多個密度極點等情況下進行精確劃分,從而保證對目標的跟蹤性能。

圖3 雜波環境下具有不同形狀的目標量測集劃分

本文所提二級CFSFDP劃分擴展目標量測集算法基本步驟如下:

步驟2已知k-1時刻目標的強度函數表示為γk-1|k-1(x),通過式(7)進行一步預測,得γk|k-1(x)。

步驟3計算量測集Zk中觀測點間的距離,構造相似度矩陣。

步驟4計算每個觀測點的局部密度ρi和高密度距離δi,其表達式為:

ρi=∑jχ(dij-dc)

(19)

(20)

步驟5確定聚類中心。使用點集(ρi,δi)建立決策圖,選取同時具有較大ρi值和δi值的點為聚類中心。這里,為了避免用肉眼進行人為觀察判斷,使該算法可以自主尋找密度峰值點,引進變量α,其表達式為:

α=ρi×δi

(21)

顯然,α值越大,越有可能是聚類中心;本文將α進行降序排序,選取前m個點為密度峰值點。

步驟6劃分子簇。對前m個點為密度峰值點進行聚類,得到初始子簇{C1,C2,…,Cm}。

步驟7計算每個子簇Ci的平均密度ρavg(Ci)和邊界區域密度ρbord(Ci,Cj),按照本文提出的層次聚類合并準則將滿足條件的所有子簇合并得到最終的量測集劃分結果。

步驟8將劃分好的若干個量測集代入式(1)、式(9)中,更新目標強度函數γk|k(x)。

步驟9對更新的γk|k(x)的高斯項進行處理,獲得目標狀態估計。

3 仿真實驗與分析

本文分別在擴展目標處于交叉、近鄰2種情景下,將所提二級CFSFDP量測集劃分算法與經典的距離劃分[9]、K-means++劃分[17]、DBSCAN[18]劃分等3種算法進行比較分析。對所提算法跟蹤擴展目標如下3個方面的性能進行驗證:

1)算法的有效性、實時性。

2)是否能發現任意形狀的目標。

3)是否能在量測密度差異較大時準確劃分量測集。

3.1 擴展目標交叉情景跟蹤

3.1.1 實驗參數設置

仿真中假設有3個不同形狀的擴展目標在監測區域[-1 000 m,1 000 m]×[-1 000 m,1 000 m]內運動,它們的初始狀態如表1所示,在第50 s時,3個擴展目標交叉。其中,目標的存活概率Ps=0.99,檢測概率PD=0.99,傳感器采樣間隔T=1 s,整個跟蹤過程持續100 s,共進行200次蒙特卡洛實驗。

表1 目標初始狀態

擴展目標運動模型為:

(22)

其中,Xk=[xk,yk,vx,vy]T,(xk,yk)表示目標的位置信息,(vx,vy)表示目標的速度信息,過程噪聲標準差為σw1=σw2=2 m/s2。假設整個過程都是在擴展目標高斯混合PHD模型框架下進行。則擴展目標的強度函數可以表示為:

Db(x)= 0.1×N(x;mb(1),Pb)+0.1×

N(x;mb(2),Pb)+0.1×N(x;mb(3),Pb)

(23)

其中:

mb(1)=[-800,-600,0,0]T,mb(2)=[-900,100,0,0]T,mb(3)=[-700,700,0,0]T,Pb=diag(100,100,25,25)。

擴展目標量測方程為:

(24)

其中,Zk=[xk,yk]T量測噪聲標準差σR1=σR2=20 m。背景雜波數服從均值為10泊松分布,且在監測區域內均勻分布。仿真參數設置最大高斯分量數目為Jmax=100,修剪門限Tp=10-4,合并門限U=4。

3.1.2 實驗分析

在擴展目標處于交叉情況下,選擇3個不同形狀的擴展目標,使其產生的量測個數分別服從均值為10,20,40 的泊松分布,將所提二級CFSFDP量測集劃分算法與經典的距離劃分、K-means++劃分、DBSCAN劃分等3種算法進行比較分析。用目標估計數、OSPA距離[19]、平均計算時間3個指標對算法的性能進行評價。

由圖4可以看出,K-means++劃分算法對目標的估計數與實際目標數偏差較大,該算法不能準確辨別錯誤劃分中的量測,使擴展目標數被高估。同時,在目標量測密度差異較大時,距離劃分、DBSACAN劃分也無法準確估計出目標數,具有一定的局限性。在第50 s 3個擴展目標相交時,相對于其他算法,本文所提的二級CFSFDP由于是根據密度峰值點及低密度邊界點進行量測集劃分,當擴展目標相交時,只要其密度峰值點不重合,即能夠較好地對量測集進行劃分,且在其他時刻均能準確估計出任意形狀擴展目標的真實數目。

圖4 目標交叉時目標數目估計

由圖5可以看出,在目標量測密度差異較大且存在交叉情況時,本文所提的二級CFSFDP對任意形狀擴展目標量測集的劃分結果明顯優于其他算法。

圖5 目標交叉時OSPA距離

由圖6可以看出,本文所提的二級CFSFDP在具有較好擴展目標量測集劃分效果的同時,也具有較好的時效性。二級CFSFDP聚類算法雖然是在CFSFDP聚類基礎上對劃分的類再進行合并,增加了算法的運算復雜度,但是從圖6可以看出,該算法的運算效率依然較高,雖然相比于DBSCAN劃分,所用時間較多一些,但與距離劃分和K-means++劃分相比,則顯示出明顯的優勢。在圖5中,DBSCAN劃分在目標密度差異較大、存在交叉情況下無法準確估計出目標的數目,跟蹤性能明顯下降。可以看出,在綜合考慮目標跟蹤性能與時效性方面,本文所提的二級CFSFDP聚類算法具有較好的優勢。

圖6 目標交叉時平均計算時間

3.2 擴展目標近鄰情景跟蹤

3.2.1 參數設置

3.2.2 結果分析

在擴展目標處于近鄰情況下,選擇2個擴展目標,使其產生的量測個數均服從均值為10的泊松分布。用目標估計數、OSPA距離、平均計算時間3個指標對算法的性能進行評價。

由圖7～圖9可知,當擴展目標處于近鄰情況時,由于本文所提的二級CFSFDP是跟據密度峰值點來劃分量測集的,因此2個近鄰的擴展目標會因密度峰值點的差異而被劃分開,能夠對任意形狀擴展目標量測集進行較好的劃分,且時效性相對較好,雖然時效性上略差于DBSCAN算法,但DBSCAN算法容易將近鄰的不同擴展目標劃分為同一目標,低估目標數目。

圖7 目標近鄰時目標數目估計

圖8 目標近鄰時OSPA距離

圖9 目標近鄰時平均計算時間

距離劃分雖然可以較好估計目標數目,但其平均計算時間久,時效性差。K-means++劃分算法對擴展目標的跟蹤效果最差。可以看出,在綜合考慮目標跟蹤性能與時效性方面,本文所提的二級CFSFDP聚類算法具有較好的優勢。

4 結束語

針對擴展目標處于交叉及近鄰情況下量測集劃分難的問題,本文提出一種基于二級CFSFDP的擴展目標量測集劃分算法。實驗結果表明,在目標量測密度差異較大,且存在交叉或近鄰情況時,該算法能夠較為準確地對任意形狀擴展目標量測集進行劃分,在保證跟蹤有效性和可行性的同時,有效減少了計算時間,其結果明顯優于其他傳統算法。下一步將研究當擴展目標交叉時,該算法目標密度峰值點的重合情況,從而進一步優化算法。

[1] GRANSTROM K,LUNDQUIST C,ORGUNER U.Extended target tracking using a gaussian-mixture PHD filter[J].IEEE Transactions on Aerospace and Electronic Systems,2012,48(4):3268-3286.

[2] 劉風梅.多擴展目標跟蹤量測集劃分算法研究[D].無錫:江南大學,2015.

[3] MAHLER R.PHD filters for nonstandard targets,i:extended targets[C]//Proceedings of the 12th International Conference on Information Fusion.Washington D.C.,USA:IEEE Press,2009:915-921.

[4] GRANSTROM K,LUNDQUIST C,ORGUNER U.A gaussian mixture PHD filter for extended target tracking[C]//Proceedingsof the 13th International Conference on Information Fusion.Washington D.C.,USA:IEEE Press,2010:1-8.

[5] ORGUNER U,LUNDQUIST C,GRANSTROM K.Extended target tracking with a cardinalized probability hypothesis density filter[C]//Proceedings of the 14th International Conference on Information Fusion.Washington D.C.,USA:IEEE Press,2011:1-8.

[6] 劉妹琴,蘭 劍.目標跟蹤前沿理論與應用[M].北京:科學出版社,2015.

[7] YANG Jinlong,LIU Fengmei,GE Hongwei,et al.Measurement partition algorithm based on density analysis and spectral clustering for multiple extended target tracking[C]//Proceedings of CCDC’14.Washington D.C.,USA:IEEE Press,2014:4401-4405.

[8] 孔云波,馮新喜,危 璋.利用高斯混合概率假設密度濾波器對擴展目標量測集進行劃分[J].西安交通大學學報,2015,49(7):126-133.

[9] LI Yunxiang,XIAO Huaitie,SONG Zhiyong.A new multiple extended target tracking algorithm using PHD filter [J].Signal Processing,2013,93 (12):3578-3588.

[10] 程艷云,周 鵬.動態分配聚類中心的改進K均值聚類算法[J].計算機技術與發展,2017,27(2):33-36.

[11] ZHANG Yongquan,JI Hongbing.Gaussian mixture reduction based on fuzzy ART for extended target tracking[J].Signal Processing,2014,97(7):232-241.

[12] YANG Jinlong,LIU Fengmei,GE Hongwei,et al.Multiple extended target tracking algorithm based on GM-PHD filter and spectral clustering[J].EURASIP Journal on Advances in Signal Processing,2014,117:1-8.

[13] RODRIGUEZ A,LAIO A.Clustering by Fast Search and Find of Density Peaks[J].Science,2014,344(6191):1492-1496.

[14] 章 濤,吳仁彪.近鄰傳播觀測聚類的多擴展目標跟蹤算法[J].西安交通大學學報,2016,31(4):764-768.

[15] 許合利,牛麗君.基于層次與密度的任意形狀聚類算法[J].計算機工程,2016,42(7):159-164.

[16] 張文開.基于密度的層次聚類算法研究[D].合肥:中國科學科技大學,2015.

[17] ARTHUR D,VASSILVITSKII S.K-means++:the advantages of careful seeding[C]//Proceedings of the 18th Acm-siam Symposium on Discrete Algorithms.New Orleans,Louisiana:Society for Industrial and Applied Mathematics Philadelphia,2007:1027-1035.

[18] ESTER M,KRIEGEL HP,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the International Conference on Knowledge Discovery and Data Mining.Oregon,Porland:the Association for the Advancement of Artificial Intelligence,1996:226-231.

[19] SCHUHMACHER D,VO B N.A consistent metric for performance evaluation of multi-object filters[J].IEEE Transactions on Signal Processing,2008,56(8):3447-3457.