基于CODHD聚類劃分的多擴(kuò)展目標(biāo)跟蹤算法

苗 露，李鴻艷，馮新喜

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

1 引言

多目標(biāo)跟蹤是利用傳感器量測(cè)對(duì)目標(biāo)數(shù)目和狀態(tài)進(jìn)行估計(jì)的過程，主要受到雜波、漏檢和虛警的影響[1]。傳統(tǒng)目標(biāo)跟蹤所利用的是點(diǎn)目標(biāo)模型，假設(shè)在每一觀測(cè)時(shí)刻每個(gè)目標(biāo)至多產(chǎn)生一個(gè)量測(cè)。隨著傳感器分辨率的提高，這種假設(shè)不再適用，探測(cè)單個(gè)目標(biāo)時(shí)會(huì)得到多個(gè)量測(cè)值，即可以得到更多的目標(biāo)運(yùn)動(dòng)和形態(tài)信息[2]，這種目標(biāo)跟蹤稱之為擴(kuò)展目標(biāo)跟蹤。

Mahler根據(jù)隨機(jī)有限集（RFS）理論[3]，推導(dǎo)出概率假設(shè)密度（Probability Hypothesis Density，PHD）濾波器的遞推方程，避免了傳統(tǒng)目標(biāo)跟蹤所利用的復(fù)雜數(shù)據(jù)關(guān)聯(lián)過程，但存在集值積分無法求解的難題。隨后，Mahler利用RFS的一階統(tǒng)計(jì)矩對(duì)多目標(biāo)的后驗(yàn)概率密度進(jìn)行近似替代，提出了一階統(tǒng)計(jì)矩近似的PHD濾波器，并于2009年將PHD濾波器用于擴(kuò)展目標(biāo)跟蹤，即ET-PHD（Extended Target PHD）濾波器。假定目標(biāo)運(yùn)動(dòng)模型滿足線性高斯條件下，文獻(xiàn)[4]給出了高斯混合PHD（Gaussian Mixture PHD，GM-PHD）濾波器的實(shí)現(xiàn)，文獻(xiàn)[5]給出了擴(kuò)展目標(biāo)高斯混合PHD（ET-GM-PHD）濾波器的實(shí)現(xiàn)。文獻(xiàn)[6]利用核密度估計(jì)方法對(duì)經(jīng)過剪枝、合并后的PHD密度分布函數(shù)進(jìn)行狀態(tài)估計(jì)，將峰值點(diǎn)作為狀態(tài)估計(jì)值，使目標(biāo)估計(jì)結(jié)果更加精確。針對(duì)目標(biāo)漏檢時(shí)致使有用信息丟失和目標(biāo)相近造成濾波性能下降，文獻(xiàn)[7]對(duì)PHD濾波器的預(yù)測(cè)、更新方程加以修正，有效改善了目標(biāo)跟蹤性能。

根據(jù)Mahler的推導(dǎo)[8]，無論是ET-PHD濾波器、GMET-PHD濾波器還是GM-ET-CPHD濾波器，提高濾波器性能就需要對(duì)量測(cè)集進(jìn)行快速準(zhǔn)確的劃分，這在理論上是需要考慮所有可能的劃分。而實(shí)際中隨著目標(biāo)數(shù)和雜波量測(cè)增多，量測(cè)劃分?jǐn)?shù)將急劇增加，將引起計(jì)算災(zāi)難，這對(duì)擴(kuò)展目標(biāo)跟蹤系統(tǒng)而言，實(shí)時(shí)性的要求難以滿足[9]。關(guān)于量測(cè)集劃分問題已經(jīng)提出了多種解決辦法，Granstrom等[5]提出了距離劃分、距離輔助劃分，Li等[10]提出了K-means聚類劃分，以上方法均是利用距離進(jìn)行劃分，在量測(cè)密度差別較大時(shí)效果不佳。Zhang等[11]提出了基于快速模糊自適應(yīng)共振理論（Adaptive Resonance Theory，ART）的劃分方法，能進(jìn)行穩(wěn)定快速的量測(cè)集劃分，但在多雜波環(huán)境下對(duì)多個(gè)擴(kuò)展目標(biāo)進(jìn)行跟蹤，算法易出現(xiàn)“飽和”問題而產(chǎn)生額外錯(cuò)誤劃分。文獻(xiàn)[12]提出CODHD算法，該算法基于凝聚性層次劃分，對(duì)簇合并計(jì)算過程和聚類有效性指標(biāo)進(jìn)行優(yōu)化，得到最優(yōu)聚類結(jié)果。本文基于該方法進(jìn)行量測(cè)集劃分，先通過自適應(yīng)橢球門限進(jìn)行量測(cè)預(yù)處理使無效雜波有效去除，再利用CODHD得到最優(yōu)聚類結(jié)果，利用FCM運(yùn)算得到量測(cè)劃分子集。

2 ET-GM-PHD濾波器

Mahler在ET-PHD濾波框架下將擴(kuò)展目標(biāo)用空間分布模型來描述，假設(shè)擴(kuò)展目標(biāo)滿足線性高斯運(yùn)動(dòng)模型，傳感器觀測(cè)滿足線性模型，目標(biāo)存活概率和檢測(cè)概率相互獨(dú)立，多擴(kuò)展目標(biāo)的預(yù)測(cè)強(qiáng)度函數(shù)就可以通過高斯混合的形式來表示[13]。

假設(shè)在k時(shí)刻，擴(kuò)展目標(biāo)的狀態(tài)集表示為Xk=，量測(cè)集表示為和分別表示k時(shí)刻的第i個(gè)擴(kuò)展目標(biāo)的狀態(tài)和量測(cè)，Nx,k和Nz,k分別表示k時(shí)刻的擴(kuò)展目標(biāo)數(shù)和量測(cè)數(shù)。根據(jù)RFS理論，目標(biāo)的狀態(tài)方程為：

其中，i=1,2,…,Nx,k，F(xiàn)k表示狀態(tài)轉(zhuǎn)移矩陣，表示協(xié)方差為的零均值高斯白噪聲。

目標(biāo)的量測(cè)方程為：

其中，Hk表示觀測(cè)矩陣，表示協(xié)方差為的零均值高斯白噪聲。

在k時(shí)刻，預(yù)測(cè)PHD的GM可表示為：

量測(cè)更新PHD強(qiáng)度可通過預(yù)測(cè)PHD強(qiáng)度和偽似然函數(shù)相乘得到，即：

其中，量測(cè)偽似然函數(shù)為：

式中，λk=βFA,kVs為雜波量測(cè)個(gè)數(shù)的期望，ck(zk)=1/VS為觀測(cè)空間中雜波的空間分布，p∠Zk為對(duì)Zk的P劃分，W為某一劃分中的各非空集合，ωP和dw分別為P和W的權(quán)重。

在每一觀測(cè)時(shí)刻，每個(gè)擴(kuò)展目標(biāo)會(huì)產(chǎn)生多個(gè)量測(cè)，而傳感器得到的量測(cè)由真實(shí)目標(biāo)量測(cè)以及雜波量測(cè)構(gòu)成。假設(shè)在k時(shí)刻，傳感器獲得量測(cè)表示為Zk=則對(duì)其進(jìn)行劃分的所有可能結(jié)果為：

3 量測(cè)集劃分

3.1 自適應(yīng)橢球門限處理

雜波量測(cè)離散、均勻分布在觀測(cè)空間，若雜波和真實(shí)目標(biāo)量測(cè)一同進(jìn)行劃分，將產(chǎn)生額外錯(cuò)誤劃分，最終影響濾波效果。在量測(cè)集劃分前，可采用橢球門限[14]方法進(jìn)行量測(cè)預(yù)處理，在不影響濾波精度的前提下，有效濾除無效雜波來改善跟蹤性能。

假設(shè)在k時(shí)刻，對(duì)預(yù)測(cè)步進(jìn)行計(jì)算后，第i個(gè)觀測(cè)和第j個(gè)高斯分量的殘差向量表示為：

ε(ji)的協(xié)方差矩陣表示為：

通過橢球門限判別對(duì)量測(cè)進(jìn)行預(yù)處理，滿足：

3.2 基于CODHD算法的量測(cè)集劃分

利用聚類實(shí)現(xiàn)擴(kuò)展目標(biāo)量測(cè)集劃分是有效途徑，CODHD算法基于凝聚型層次聚類，在簇合并過程中對(duì)生成的不同劃分進(jìn)行聚類質(zhì)量評(píng)估得到最優(yōu)聚類結(jié)果。該算法對(duì)簇合并過程和聚類評(píng)估指標(biāo)加以優(yōu)化，使計(jì)算復(fù)雜度降低并提高聚類有效性。

對(duì)去除雜波后的量測(cè)集劃分過程如下：對(duì)量測(cè)進(jìn)行區(qū)間掃描生成合理劃分；層次式生成不同量測(cè)劃分，計(jì)算各劃分中的量測(cè)局部密度并將密度最大點(diǎn)作為聚類中心點(diǎn)，得到該中心點(diǎn)和更高密度量測(cè)之間的最小距離；將每次得到的聚類質(zhì)量構(gòu)造為質(zhì)量曲線并提取極大值點(diǎn)；通過剪枝[15]原理得到最優(yōu)聚類結(jié)果并進(jìn)行FCM運(yùn)算，得到量測(cè)劃分子集。

聚類質(zhì)量評(píng)估指標(biāo)Q定義為：

量測(cè)局部密度Ni計(jì)算過程如下：

（1）將量測(cè)標(biāo)準(zhǔn)差作為鄰域半徑：

（2）在鄰域半徑所構(gòu)成區(qū)域內(nèi)計(jì)算局部密度：

δi表示最小距離，；對(duì)于密度最高點(diǎn)有：。Q表示聚類中心量測(cè)密度與最小距離乘積之和的均值，若i為聚類中心，則Ni和（或）δi取較大值的可能性就越大，衡量指標(biāo)Niδi也就有較大值。

凝聚型層次聚類算法在起始階段將每個(gè)數(shù)據(jù)看做單獨(dú)子簇，根據(jù)簇合并準(zhǔn)則將子簇不斷進(jìn)行合并，最后使所有數(shù)據(jù)成為一個(gè)集合。假設(shè)k時(shí)刻量測(cè)集為Z={z1,z2,…,zn} ∈Rd×n，其中 d 為量測(cè)維度，n為量測(cè)個(gè)數(shù)。簇合并過程如下：

（1）初始化 S=S0。

（2）將量測(cè)進(jìn)行屬性值大小排序，生成序列Ai，在有限區(qū)間內(nèi)掃描，尋找量測(cè)x的第i維相似量測(cè)y。

（3）每過程 S 增大 Δ(Δ={Δ1,Δ2,…,Δd})，并在上一掃描區(qū)間基礎(chǔ)上進(jìn)行擴(kuò)張，繼續(xù)掃描尋找相似量測(cè)進(jìn)行合并：

（4）S增大到所有量測(cè)劃分到一個(gè)集合。

圖1表示在不同劃分?jǐn)?shù)下得到的聚類質(zhì)量并構(gòu)造為質(zhì)量曲線。

圖1 不同劃分?jǐn)?shù)目下的聚類質(zhì)量

FCM通過隸屬度決定量測(cè)劃分，是傳統(tǒng)硬劃分K-means的改進(jìn)，對(duì)劃分歸屬模糊問題能進(jìn)行較好處理。將剪枝得到的聚類結(jié)果進(jìn)行FCM操作，可有效改善劃分效果，其實(shí)現(xiàn)過程如下：

（1）提取質(zhì)量曲線極值點(diǎn)，進(jìn)行剪枝操作得到聚類數(shù)l和聚類中心集V0=(v1,v2,…,vl)，進(jìn)行相關(guān)參數(shù)設(shè)置：權(quán)重指數(shù) m(m=2)，終止閾值 ε(ε=0.01)，迭代記步器t=0。

（2）計(jì)算、更新劃分矩陣Ut：

（3）更新聚類中心Vt+1：

量測(cè)集劃分的典型方法和改進(jìn)方法有距離閾值法、K-means聚類方法、ART方法等。距離閾值法為保證劃分中能包含正確的劃分子集，需要選取較大的閾值范圍，這造成較多錯(cuò)誤劃分并使目標(biāo)狀態(tài)估計(jì)誤差增大。K-means算法由于K值難以選取且隨機(jī)選擇初始聚類中心，致使聚類結(jié)果不穩(wěn)定，在量測(cè)密度差異較大時(shí)難以進(jìn)行有效劃分。ART算法對(duì)輸入警戒參數(shù)β比較敏感，在多擴(kuò)展目標(biāo)的多雜波環(huán)境下，易造成算法“飽和”問題使權(quán)向量無法自適應(yīng)調(diào)整權(quán)重以適應(yīng)訓(xùn)練模式，產(chǎn)生額外錯(cuò)誤劃分，使跟蹤效果下降。

基于CODHD聚類劃分算法的量測(cè)集劃分在層次簇合并過程中對(duì)生成的不同劃分進(jìn)行聚類評(píng)估，得到最優(yōu)聚類結(jié)果后進(jìn)行FCM運(yùn)算得到量測(cè)劃分子集。由于簇合并過程中簇生成個(gè)數(shù)只與量測(cè)分布結(jié)構(gòu)有關(guān)，使其可識(shí)別量測(cè)密度差異；采用標(biāo)準(zhǔn)差作為鄰域半徑計(jì)算量測(cè)局部密度，能夠反映量測(cè)集的量測(cè)真實(shí)分布情況[16]；避免對(duì)量測(cè)數(shù)據(jù)直接進(jìn)行反復(fù)聚類，自適應(yīng)生成最佳聚類數(shù)和聚類中心后執(zhí)行FCM運(yùn)算，有效加快收斂速度?？紤]真實(shí)擴(kuò)展目標(biāo)跟蹤場(chǎng)景，在雜波環(huán)境下目標(biāo)個(gè)數(shù)未知并隨時(shí)間而不斷發(fā)生變化，并存在目標(biāo)緊鄰、分裂、量測(cè)生成數(shù)未知等情形，這都影響到多目標(biāo)跟蹤性能。所提方法根據(jù)量測(cè)分布情況自適應(yīng)得到最優(yōu)聚類結(jié)果，因此適合于在雜波和目標(biāo)量測(cè)未知情形下進(jìn)行快速準(zhǔn)確地?cái)U(kuò)展目標(biāo)量測(cè)集劃分，確保目標(biāo)跟蹤的實(shí)時(shí)性。

3.3 擴(kuò)展目標(biāo)跟蹤算法流程

基于CODHD算法對(duì)量測(cè)集劃分的擴(kuò)展目標(biāo)跟蹤算法流程歸結(jié)如下：

（1）已知k-1時(shí)刻的目標(biāo)強(qiáng)度函數(shù)Dk-1(x )，預(yù)測(cè)得到k時(shí)刻的目標(biāo)強(qiáng)度函數(shù)

（2）將新生目標(biāo)和存活目標(biāo)的高斯分量作為k時(shí)刻的狀態(tài)預(yù)測(cè)，進(jìn)行殘差和橢球門限值的計(jì)算，對(duì)量測(cè)集Zk進(jìn)行門限處理后只保留門限內(nèi)的有效量測(cè)

（3）參數(shù)初始化：k=n,Un={z1,z2,…,zn},S=S0，Qn=Q(Un)，將量測(cè)根據(jù)第i維屬性排序生成Ai。

（4）從k=n運(yùn)行至k=1：

②通過簇合并生成新劃分，計(jì)算Nx和δx，求得有效性指標(biāo)Qk；

③生成聚類質(zhì)量曲線。

（5）提取曲線極值點(diǎn)得到量測(cè)劃分，并利用剪枝原理獲得最優(yōu)聚類數(shù)和聚類中心。

（6）進(jìn)行FCM運(yùn)算獲得若干量測(cè)劃分子集，并將其對(duì)目標(biāo)強(qiáng)度函數(shù)進(jìn)行更新。

4 仿真結(jié)果及分析

為證明本文方法的有效性和可行性，假定在二維平面，傳感器對(duì)四個(gè)擴(kuò)展目標(biāo)進(jìn)行跟蹤，觀測(cè)區(qū)域?yàn)閇-500,500]m×[-500,500]m，采樣周期T=1 s，觀測(cè)時(shí)長為40 s。目標(biāo)運(yùn)動(dòng)和觀測(cè)方程均滿足線性高斯模型，各擴(kuò)展目標(biāo)的初始狀態(tài)以及出生、消失時(shí)間見表1。

表1 目標(biāo)初始狀態(tài)和運(yùn)動(dòng)軌跡

在不考慮目標(biāo)衍生的條件下，PHD濾波器的新生過程表示為強(qiáng)度是γk的泊松有限集。即：

擴(kuò)展目標(biāo)的存活概率Ps,k=0.99，檢測(cè)概率PD,k=0.95。每一觀測(cè)時(shí)刻，擴(kuò)展目標(biāo)的量測(cè)生成分別服從均值為10、15、20、30的泊松分布，雜波生成量測(cè)服從均值為30的泊松分布，并在觀測(cè)空間內(nèi)服從均勻分布。高斯項(xiàng)修剪門限Tp=10-4，最大高斯個(gè)數(shù)Jmax=200，融合門限U=4，橢球門限參數(shù)Pg=0.95。

進(jìn)行200次蒙特卡洛仿真，將本文方法和距離劃分法、ART劃分法用于ET-GM-PHD濾波器進(jìn)行比較。采用最優(yōu)子模式分配（OSPA）距離[17]（參數(shù)設(shè)置p=2,c=80）對(duì)各算法性能做出評(píng)估：

圖2給出了擴(kuò)展目標(biāo)在雜波環(huán)境下的運(yùn)動(dòng)軌跡，圖3和圖4是不同算法得到的目標(biāo)數(shù)估計(jì)和OSPA距離對(duì)比圖。

圖2 雜波環(huán)境下的目標(biāo)運(yùn)動(dòng)軌跡

由圖3和圖4可知本文方法有更加準(zhǔn)確的目標(biāo)數(shù)估計(jì)結(jié)果以及更小的OSPA距離。這是由于通過橢球門限進(jìn)行量測(cè)預(yù)處理使雜波干擾降低，利用量測(cè)分布得到最優(yōu)聚類結(jié)果繼續(xù)進(jìn)行FCM運(yùn)算從而保證聚類劃分準(zhǔn)確度，而距離劃分和ART劃分在多雜波環(huán)境下進(jìn)行多擴(kuò)展目標(biāo)跟蹤均產(chǎn)生了較多錯(cuò)誤劃分，致使跟蹤效果下降。

圖3 目標(biāo)數(shù)目估計(jì)比較

圖4 OSPA距離比較

由圖5可知，本文劃分方法具有較高的運(yùn)行效率，這是因?yàn)樵陬A(yù)處理階段將雜波進(jìn)行了有效濾除使后續(xù)劃分算法的計(jì)算復(fù)雜度降低，利用CODHD輸出最優(yōu)聚類結(jié)果避免了對(duì)量測(cè)數(shù)據(jù)直接進(jìn)行反復(fù)聚類并使FCM收斂速度加快。

圖5 劃分時(shí)間比較

5 結(jié)束語

針對(duì)雜波環(huán)境下，概率假設(shè)密度濾波器對(duì)擴(kuò)展目標(biāo)跟蹤存在量測(cè)集劃分難且效率低的問題，提出基于CODHD聚類算法進(jìn)行劃分的方法。先利用橢球門限將量測(cè)集中的無效雜波量測(cè)進(jìn)行去除，再通過CODHD聚類劃分得到最優(yōu)聚類結(jié)果，進(jìn)行FCM運(yùn)算得到量測(cè)劃分子集。結(jié)果表明所提方法可以對(duì)量測(cè)集進(jìn)行快速準(zhǔn)確的劃分，保證在雜波環(huán)境下對(duì)多擴(kuò)展目標(biāo)的實(shí)時(shí)跟蹤。