基于二級(jí)CFSFDP的擴(kuò)展目標(biāo)量測(cè)集劃分算法

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

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院,西安 710077)

0 概述

在傳統(tǒng)的目標(biāo)跟蹤問(wèn)題中,通常忽略目標(biāo)的外形而將目標(biāo)簡(jiǎn)化為一個(gè)點(diǎn),即假設(shè)一個(gè)目標(biāo)只能產(chǎn)生一個(gè)量測(cè),但隨著科學(xué)技術(shù)的發(fā)展,雷達(dá)等傳感器的分辨率不斷提高,使得一個(gè)目標(biāo)在一個(gè)采樣周期內(nèi)可產(chǎn)生多個(gè)量測(cè),通常稱(chēng)這種目標(biāo)為擴(kuò)展目標(biāo)[1-3]。

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

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

1 擴(kuò)展目標(biāo)高斯混合PHD濾波器

擴(kuò)展目標(biāo)與點(diǎn)目標(biāo)產(chǎn)生的量測(cè)空間區(qū)別如圖1所示,根據(jù)文獻(xiàn)[3]所提出的擴(kuò)展目標(biāo)PHD濾波模型,假設(shè)每個(gè)采樣時(shí)刻傳感器得到每個(gè)目標(biāo)產(chǎn)生的擴(kuò)展目標(biāo)觀測(cè)數(shù)服從Poisson分布,且擴(kuò)展目標(biāo)的觀測(cè)服從以目標(biāo)質(zhì)心為均值的Gaussian分布。

圖1 點(diǎn)目標(biāo)與擴(kuò)展目標(biāo)示意圖

根據(jù)簡(jiǎn)單的數(shù)學(xué)知識(shí),很容易得到每個(gè)目標(biāo)實(shí)際被檢測(cè)到的概率,其表達(dá)式為:

(1)

假設(shè)1目標(biāo)狀態(tài)方程和傳感器的觀測(cè)方程是線(xiàn)性高斯模型,即:

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

(2)

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

(3)

假設(shè)2目標(biāo)存活和檢測(cè)概率與目標(biāo)狀態(tài)獨(dú)立,即:

pD,k(xk)=pD,k

(4)

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

(5)

假設(shè)3目標(biāo)的強(qiáng)度函數(shù)為高斯和的形式,即:

(6)

通常稱(chēng)滿(mǎn)足以上假設(shè)的算法為擴(kuò)展目標(biāo)高斯混合PHD濾波算法。

假設(shè)已知k-1時(shí)刻目標(biāo)的強(qiáng)度函數(shù)γk-1|k-1(x),則擴(kuò)展目標(biāo)高斯混合PHD濾波器的預(yù)測(cè)步和更新步可表示如下:

1)預(yù)測(cè)步

(7)

2)更新步

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

(8)

(9)

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

(10)

k時(shí)刻目標(biāo)后驗(yàn)概率γk|k(x)包括兩部分,分別用于處理未檢測(cè)目標(biāo)和檢測(cè)到目標(biāo)的情況。詳細(xì)推導(dǎo)公式可以參見(jiàn)文獻(xiàn)[1]。

對(duì)于擴(kuò)展目標(biāo)量測(cè)集的劃分給出如下實(shí)例。若某一時(shí)刻傳感器獲得的量測(cè)集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)

顯然,量測(cè)集的所有可能劃分隨著量測(cè)數(shù)的增加而急劇上升,尤其是在雜波密集的環(huán)境下,其計(jì)算量和時(shí)間消耗更是成指數(shù)倍增長(zhǎng)。因此,急需尋找一種合理可行的量測(cè)集劃分算法。

2 基于二級(jí)CFSFDP算法的量測(cè)集劃分

2.1 局部異常因子去噪

由于傳感器獲得的觀測(cè)數(shù)據(jù)中不但包含對(duì)目標(biāo)觀測(cè)的有用信息,也包含著雜波信息,同時(shí)這些雜波均勻的分布在觀測(cè)空間中,對(duì)量測(cè)集的劃分存在很大的干擾。本文首先采用局部異常因子來(lái)對(duì)量測(cè)為雜波的程度進(jìn)行度量,通過(guò)設(shè)定閾值的算法進(jìn)行雜波濾除,接著將層次聚類(lèi)與新近發(fā)表在《Science》上的采用密度極點(diǎn)的算法相結(jié)合對(duì)量測(cè)集進(jìn)行劃分,提高了量測(cè)集劃分的準(zhǔn)確度。

局部異常因子(Local Outlier Factor,LOF)是一種基于密度的離群點(diǎn)檢測(cè)算法,它通過(guò)判斷觀測(cè)樣本與其最近鄰k個(gè)鄰居的孤立程度來(lái)考慮數(shù)據(jù)的孤立性,實(shí)現(xiàn)對(duì)偏離大部分?jǐn)?shù)據(jù)的異常數(shù)據(jù)進(jìn)行檢測(cè)。

首先,計(jì)算x到x′的可達(dá)距離:

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

(12)

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

然后,計(jì)算x的局部可達(dá)密度:

(13)

應(yīng)用這個(gè)局部可達(dá)密度,可計(jì)算出x的局部異常因子:

(14)

圖2表示局部異常因子的實(shí)例,可見(jiàn),偏離大部分正常值的數(shù)據(jù)點(diǎn)具有較高的異常值。各個(gè)樣本周?chē)膱A的半徑與樣本的局部異常因子的值成正比,圓的半徑越大,其樣本越傾向于異常值。經(jīng)多次實(shí)驗(yàn)仿真,本文設(shè)局部異常因子大于2的點(diǎn)為異常值。

圖2 局部異常因子實(shí)例

2.2 二級(jí)CFSFDP量測(cè)集劃分算法

2.2.1 CFSFDP算法

2014年,文獻(xiàn)[13]提出了一種新的聚類(lèi)算法CFSFDP。該算法簡(jiǎn)單新穎、靈活性強(qiáng),對(duì)目標(biāo)的外形信息不敏感,可以有效處理大數(shù)據(jù)集,同時(shí)解決了聚類(lèi)初始中心選擇難的問(wèn)題。CFSFDP算法的主要思想為在一個(gè)類(lèi)族中,密度高的類(lèi)中心總是被密度較低的鄰居點(diǎn)包圍,且與具有更高密度的任何點(diǎn)都有相對(duì)較大的距離。該算法處理流程是:1)通過(guò)密度極點(diǎn)確定聚類(lèi)中心;2)按照一定順序?qū)?shù)據(jù)點(diǎn)歸類(lèi)到距離其最近且密度比它自身密度高的點(diǎn)所屬的類(lèi)中。

對(duì)于每一個(gè)數(shù)據(jù)點(diǎn),該算法只需要計(jì)算局部密度ρi、該數(shù)據(jù)點(diǎn)與密度比它高的最近點(diǎn)的距離δi。算法具體步驟為:

步驟1計(jì)算觀測(cè)點(diǎn)間的距離,構(gòu)造相似度矩陣。

步驟2通過(guò)相似度矩陣和截?cái)嗑嚯x計(jì)算每個(gè)觀測(cè)點(diǎn)的局部密度ρi。

步驟3計(jì)算每個(gè)觀測(cè)點(diǎn)與密度比它高的最近點(diǎn)的距離δi。

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

步驟5按密度降序?qū)τ^測(cè)集劃分。

算法偽代碼如下:

輸入觀測(cè)集為X={X1,X2,…,Xn};截?cái)嗑嚯x為dc

輸出聚類(lèi)結(jié)果為C={C1,C2,…,Cn}

for each point i do

for each point j do

dij=distance from i to j;

//計(jì)算每對(duì)數(shù)據(jù)點(diǎn)之間的距離

endfor

endfor

for each point i do

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

//計(jì)算數(shù)據(jù)點(diǎn)的局部密度

endfor

//畫(huà)出決策樹(shù),確定聚類(lèi)中心

sort points by density descend order;

for each point I do

Ci=Cnearest_higer_density_neighbor(i);

//對(duì)量測(cè)集按密度降序排序,然后按此順序?qū)?shù)據(jù)點(diǎn)//分配,進(jìn)行聚類(lèi)

endfor

該算法存在一個(gè)很大的缺陷,即當(dāng)某一類(lèi)中存在多個(gè)密度極點(diǎn)時(shí),那么,一個(gè)類(lèi)將被錯(cuò)誤的劃分成多個(gè)子簇,造成量測(cè)集劃分不準(zhǔn)確的后果。在實(shí)際擴(kuò)展目標(biāo)跟蹤問(wèn)題中,跟蹤的目標(biāo)存在多種多樣的外形特征,不同的外形可能會(huì)導(dǎo)致由傳感器獲得的量測(cè)集中存在多個(gè)密度極點(diǎn)的現(xiàn)象,此時(shí),若采用CFSFDP聚類(lèi)對(duì)量測(cè)集進(jìn)行劃分,則可能錯(cuò)誤的將一個(gè)目標(biāo)劃分為多個(gè)目標(biāo)。因此,還需要考慮對(duì)劃分的類(lèi)再進(jìn)行合并,以此來(lái)實(shí)現(xiàn)對(duì)任意外形目標(biāo)的量測(cè)集劃分,確保算法的跟蹤性能。

2.2.2 層次聚類(lèi)合并準(zhǔn)則

在一個(gè)多維空間中,不同聚類(lèi)間通過(guò)低密度點(diǎn)集進(jìn)行劃分,每一個(gè)聚類(lèi)都可以表示為一個(gè)密度分布相對(duì)密集的連通區(qū)域。由以上聚類(lèi)劃分思想,即聚類(lèi)是相對(duì)密集的連通區(qū)域,聚類(lèi)之間通過(guò)含有密度相對(duì)較低的點(diǎn)集的區(qū)域來(lái)劃分的原則,因此相對(duì)整個(gè)聚類(lèi)來(lái)說(shuō),聚類(lèi)邊界的密度是較低的。由此,提出一種合理的假設(shè),即聚類(lèi)邊界區(qū)域密度小于聚類(lèi)平均密度[15-16],當(dāng)邊界密度大于等于聚類(lèi)平均密度時(shí),則被認(rèn)為是劃分開(kāi)的不完整聚類(lèi)的子簇。平均密度和邊界區(qū)域密度的計(jì)算公式定義如下:

(15)

(16)

其中,|Ci|表示第i個(gè)聚類(lèi)中觀測(cè)點(diǎn)的總數(shù),ρk表示每個(gè)觀測(cè)點(diǎn)的局部密度。聚類(lèi)合并判定準(zhǔn)則如下:

ρbord(Ci,Cj)≥ρa(bǔ)vg(Ci)

(17)

ρbord(Ci,Cj)≥ρa(bǔ)vg(Cj)

(18)

當(dāng)式(16)或式(17)成立時(shí),則判定Ci、Cj屬于同一聚類(lèi),此時(shí)需將Ci、Cj進(jìn)行聚類(lèi)合并;反之,則無(wú)需進(jìn)行合并。該聚類(lèi)合并準(zhǔn)則,只需遍歷一次由CFSFDP算法劃分的子簇,即可將滿(mǎn)足條件的所有子簇合并得到最終的聚類(lèi)劃分結(jié)果,本文稱(chēng)之為二級(jí)聚類(lèi)的CFSFDP量測(cè)集劃分。

2.2.3 二級(jí)CFSFDP算法

由于CFSFDP算法能夠高效準(zhǔn)確地確定密度峰值點(diǎn),層次聚類(lèi)能對(duì)其存在的將一個(gè)類(lèi)錯(cuò)誤劃分成多個(gè)子類(lèi)的缺陷制定合并準(zhǔn)則,因此本文采用將CFSFDP 算法與層次聚類(lèi)相結(jié)合的二級(jí)CFSFDP算法對(duì)擴(kuò)展目標(biāo)量測(cè)集進(jìn)行劃分。該算法對(duì)目標(biāo)的外形不敏感,可實(shí)現(xiàn)對(duì)任意外形目標(biāo)的量測(cè)集劃分,如圖3所示。由圖3可以看出,使用二級(jí)CFSFDP聚類(lèi)算法對(duì)量測(cè)集進(jìn)行劃分,能夠在目標(biāo)處于雜波、近鄰、存在多個(gè)密度極點(diǎn)等情況下進(jìn)行精確劃分,從而保證對(duì)目標(biāo)的跟蹤性能。

圖3 雜波環(huán)境下具有不同形狀的目標(biāo)量測(cè)集劃分

本文所提二級(jí)CFSFDP劃分?jǐn)U展目標(biāo)量測(cè)集算法基本步驟如下:

步驟2已知k-1時(shí)刻目標(biāo)的強(qiáng)度函數(shù)表示為γk-1|k-1(x),通過(guò)式(7)進(jìn)行一步預(yù)測(cè),得γk|k-1(x)。

步驟3計(jì)算量測(cè)集Zk中觀測(cè)點(diǎn)間的距離,構(gòu)造相似度矩陣。

步驟4計(jì)算每個(gè)觀測(cè)點(diǎn)的局部密度ρi和高密度距離δi,其表達(dá)式為:

ρi=∑jχ(dij-dc)

(19)

(20)

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

α=ρi×δi

(21)

顯然,α值越大,越有可能是聚類(lèi)中心;本文將α進(jìn)行降序排序,選取前m個(gè)點(diǎn)為密度峰值點(diǎn)。

步驟6劃分子簇。對(duì)前m個(gè)點(diǎn)為密度峰值點(diǎn)進(jìn)行聚類(lèi),得到初始子簇{C1,C2,…,Cm}。

步驟7計(jì)算每個(gè)子簇Ci的平均密度ρa(bǔ)vg(Ci)和邊界區(qū)域密度ρbord(Ci,Cj),按照本文提出的層次聚類(lèi)合并準(zhǔn)則將滿(mǎn)足條件的所有子簇合并得到最終的量測(cè)集劃分結(jié)果。

步驟8將劃分好的若干個(gè)量測(cè)集代入式(1)、式(9)中,更新目標(biāo)強(qiáng)度函數(shù)γk|k(x)。

步驟9對(duì)更新的γk|k(x)的高斯項(xiàng)進(jìn)行處理,獲得目標(biāo)狀態(tài)估計(jì)。

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

本文分別在擴(kuò)展目標(biāo)處于交叉、近鄰2種情景下,將所提二級(jí)CFSFDP量測(cè)集劃分算法與經(jīng)典的距離劃分[9]、K-means++劃分[17]、DBSCAN[18]劃分等3種算法進(jìn)行比較分析。對(duì)所提算法跟蹤擴(kuò)展目標(biāo)如下3個(gè)方面的性能進(jìn)行驗(yàn)證:

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

2)是否能發(fā)現(xiàn)任意形狀的目標(biāo)。

3)是否能在量測(cè)密度差異較大時(shí)準(zhǔn)確劃分量測(cè)集。

3.1 擴(kuò)展目標(biāo)交叉情景跟蹤

3.1.1 實(shí)驗(yàn)參數(shù)設(shè)置

仿真中假設(shè)有3個(gè)不同形狀的擴(kuò)展目標(biāo)在監(jiān)測(cè)區(qū)域[-1 000 m,1 000 m]×[-1 000 m,1 000 m]內(nèi)運(yùn)動(dòng),它們的初始狀態(tài)如表1所示,在第50 s時(shí),3個(gè)擴(kuò)展目標(biāo)交叉。其中,目標(biāo)的存活概率Ps=0.99,檢測(cè)概率PD=0.99,傳感器采樣間隔T=1 s,整個(gè)跟蹤過(guò)程持續(xù)100 s,共進(jìn)行200次蒙特卡洛實(shí)驗(yàn)。

表1 目標(biāo)初始狀態(tài)

擴(kuò)展目標(biāo)運(yùn)動(dòng)模型為:

(22)

其中,Xk=[xk,yk,vx,vy]T,(xk,yk)表示目標(biāo)的位置信息,(vx,vy)表示目標(biāo)的速度信息,過(guò)程噪聲標(biāo)準(zhǔn)差為σw1=σw2=2 m/s2。假設(shè)整個(gè)過(guò)程都是在擴(kuò)展目標(biāo)高斯混合PHD模型框架下進(jìn)行。則擴(kuò)展目標(biāo)的強(qiáng)度函數(shù)可以表示為:

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)。

擴(kuò)展目標(biāo)量測(cè)方程為:

(24)

其中,Zk=[xk,yk]T量測(cè)噪聲標(biāo)準(zhǔn)差σR1=σR2=20 m。背景雜波數(shù)服從均值為10泊松分布,且在監(jiān)測(cè)區(qū)域內(nèi)均勻分布。仿真參數(shù)設(shè)置最大高斯分量數(shù)目為Jmax=100,修剪門(mén)限Tp=10-4,合并門(mén)限U=4。

3.1.2 實(shí)驗(yàn)分析

在擴(kuò)展目標(biāo)處于交叉情況下,選擇3個(gè)不同形狀的擴(kuò)展目標(biāo),使其產(chǎn)生的量測(cè)個(gè)數(shù)分別服從均值為10,20,40 的泊松分布,將所提二級(jí)CFSFDP量測(cè)集劃分算法與經(jīng)典的距離劃分、K-means++劃分、DBSCAN劃分等3種算法進(jìn)行比較分析。用目標(biāo)估計(jì)數(shù)、OSPA距離[19]、平均計(jì)算時(shí)間3個(gè)指標(biāo)對(duì)算法的性能進(jìn)行評(píng)價(jià)。

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

圖4 目標(biāo)交叉時(shí)目標(biāo)數(shù)目估計(jì)

由圖5可以看出,在目標(biāo)量測(cè)密度差異較大且存在交叉情況時(shí),本文所提的二級(jí)CFSFDP對(duì)任意形狀擴(kuò)展目標(biāo)量測(cè)集的劃分結(jié)果明顯優(yōu)于其他算法。

圖5 目標(biāo)交叉時(shí)OSPA距離

由圖6可以看出,本文所提的二級(jí)CFSFDP在具有較好擴(kuò)展目標(biāo)量測(cè)集劃分效果的同時(shí),也具有較好的時(shí)效性。二級(jí)CFSFDP聚類(lèi)算法雖然是在CFSFDP聚類(lèi)基礎(chǔ)上對(duì)劃分的類(lèi)再進(jìn)行合并,增加了算法的運(yùn)算復(fù)雜度,但是從圖6可以看出,該算法的運(yùn)算效率依然較高,雖然相比于DBSCAN劃分,所用時(shí)間較多一些,但與距離劃分和K-means++劃分相比,則顯示出明顯的優(yōu)勢(shì)。在圖5中,DBSCAN劃分在目標(biāo)密度差異較大、存在交叉情況下無(wú)法準(zhǔn)確估計(jì)出目標(biāo)的數(shù)目,跟蹤性能明顯下降?？梢钥闯?在綜合考慮目標(biāo)跟蹤性能與時(shí)效性方面,本文所提的二級(jí)CFSFDP聚類(lèi)算法具有較好的優(yōu)勢(shì)。

圖6 目標(biāo)交叉時(shí)平均計(jì)算時(shí)間

3.2 擴(kuò)展目標(biāo)近鄰情景跟蹤

3.2.1 參數(shù)設(shè)置

3.2.2 結(jié)果分析

在擴(kuò)展目標(biāo)處于近鄰情況下,選擇2個(gè)擴(kuò)展目標(biāo),使其產(chǎn)生的量測(cè)個(gè)數(shù)均服從均值為10的泊松分布。用目標(biāo)估計(jì)數(shù)、OSPA距離、平均計(jì)算時(shí)間3個(gè)指標(biāo)對(duì)算法的性能進(jìn)行評(píng)價(jià)。

由圖7～圖9可知,當(dāng)擴(kuò)展目標(biāo)處于近鄰情況時(shí),由于本文所提的二級(jí)CFSFDP是跟據(jù)密度峰值點(diǎn)來(lái)劃分量測(cè)集的,因此2個(gè)近鄰的擴(kuò)展目標(biāo)會(huì)因密度峰值點(diǎn)的差異而被劃分開(kāi),能夠?qū)θ我庑螤顢U(kuò)展目標(biāo)量測(cè)集進(jìn)行較好的劃分,且時(shí)效性相對(duì)較好,雖然時(shí)效性上略差于DBSCAN算法,但DBSCAN算法容易將近鄰的不同擴(kuò)展目標(biāo)劃分為同一目標(biāo),低估目標(biāo)數(shù)目。

圖7 目標(biāo)近鄰時(shí)目標(biāo)數(shù)目估計(jì)

圖8 目標(biāo)近鄰時(shí)OSPA距離

圖9 目標(biāo)近鄰時(shí)平均計(jì)算時(shí)間

距離劃分雖然可以較好估計(jì)目標(biāo)數(shù)目,但其平均計(jì)算時(shí)間久,時(shí)效性差。K-means++劃分算法對(duì)擴(kuò)展目標(biāo)的跟蹤效果最差?？梢钥闯?在綜合考慮目標(biāo)跟蹤性能與時(shí)效性方面,本文所提的二級(jí)CFSFDP聚類(lèi)算法具有較好的優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

針對(duì)擴(kuò)展目標(biāo)處于交叉及近鄰情況下量測(cè)集劃分難的問(wèn)題,本文提出一種基于二級(jí)CFSFDP的擴(kuò)展目標(biāo)量測(cè)集劃分算法。實(shí)驗(yàn)結(jié)果表明,在目標(biāo)量測(cè)密度差異較大,且存在交叉或近鄰情況時(shí),該算法能夠較為準(zhǔn)確地對(duì)任意形狀擴(kuò)展目標(biāo)量測(cè)集進(jìn)行劃分,在保證跟蹤有效性和可行性的同時(shí),有效減少了計(jì)算時(shí)間,其結(jié)果明顯優(yōu)于其他傳統(tǒng)算法。下一步將研究當(dāng)擴(kuò)展目標(biāo)交叉時(shí),該算法目標(biāo)密度峰值點(diǎn)的重合情況,從而進(jìn)一步優(yōu)化算法。

[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] 劉風(fēng)梅.多擴(kuò)展目標(biāo)跟蹤量測(cè)集劃分算法研究[D].無(wú)錫:江南大學(xué),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] 劉妹琴,蘭 劍.目標(biāo)跟蹤前沿理論與應(yīng)用[M].北京:科學(xué)出版社,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] 孔云波,馮新喜,危 璋.利用高斯混合概率假設(shè)密度濾波器對(duì)擴(kuò)展目標(biāo)量測(cè)集進(jìn)行劃分[J].西安交通大學(xué)學(xué)報(bào),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] 程艷云,周 鵬.動(dòng)態(tài)分配聚類(lèi)中心的改進(jìn)K均值聚類(lèi)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,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] 章 濤,吳仁彪.近鄰傳播觀測(cè)聚類(lèi)的多擴(kuò)展目標(biāo)跟蹤算法[J].西安交通大學(xué)學(xué)報(bào),2016,31(4):764-768.

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

[16] 張文開(kāi).基于密度的層次聚類(lèi)算法研究[D].合肥:中國(guó)科學(xué)科技大學(xué),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.