改進(jìn)的多擴(kuò)展目標(biāo)PHD濾波算法*

彭聰,王杰貴，朱克凡，程澤新

(國防科技大學(xué) 電子對抗學(xué)院，安徽 合肥 230037)

0 引言

傳統(tǒng)的目標(biāo)跟蹤中一般將運(yùn)動物體視為點目標(biāo)，此時只考慮目標(biāo)的運(yùn)動信息，而忽略了目標(biāo)的外形信息。隨著傳感器技術(shù)的提升，新型的傳感器可提供目標(biāo)的多個量測值，這種在同一時刻能夠得到至少一個量測值的目標(biāo)稱為擴(kuò)展目標(biāo)[1]。擴(kuò)展目標(biāo)不僅提供了目標(biāo)的運(yùn)動狀態(tài)，還提供了運(yùn)動體的外形信息(大小、形狀和朝向等)。

基于數(shù)據(jù)關(guān)聯(lián)的多目標(biāo)跟蹤算法一直是人們解決多目標(biāo)跟蹤問題的一個途徑，但是這類算法會帶來“組合爆炸”的問題[2]，計算量龐大是這類算法的一個缺陷。2007年，Mahler在文獻(xiàn)[3]中提出了隨機(jī)有限集(random finite set,RFS)框架下的多目標(biāo)跟蹤方法，該方法將所有的目標(biāo)狀態(tài)和量測集看作隨機(jī)有限集，然后通過多目標(biāo)貝葉斯濾波計算同時估計出目標(biāo)的個數(shù)和狀態(tài)。由于算法中存在集值積分，求解十分困難，因此很多近似的濾波方法被提出，概率假設(shè)密度(probability hypothesized density,PHD)濾波器便是其中之一，它傳遞的目標(biāo)概率密度的一階統(tǒng)計近似矩。2009年，Mahler在Giholm和Sallmond給出的非均勻泊松點過程的目標(biāo)量測模型的基礎(chǔ)上，將PHD濾波技術(shù)應(yīng)用于擴(kuò)展目標(biāo)，進(jìn)行了擴(kuò)展目標(biāo)PHD(extended target PHD,ET-PHD)濾波的數(shù)學(xué)推導(dǎo)，給出了擴(kuò)展目標(biāo)PHD濾波器的更新方程[4]。2010年，Granstrom等學(xué)者給出了ET-PHD的高斯混合(Gauss mixture,GM)實現(xiàn)形式，即ET-GM-PHD濾波[5]。

量測集的劃分是多擴(kuò)展目標(biāo)跟蹤中的一個重要環(huán)節(jié)，2010年，Granstrom等人提出了一種基于距離閾值的劃分方法，該方法適用于目標(biāo)距離較遠(yuǎn)且量測密度相近的情況[6]；文獻(xiàn)[7]提出了k-means劃分方法，其跟蹤精度好于距離劃分，上述2種方法都是基于距離計算的，對于量測密度差別較大的情況，兩者劃分效果較差。針對這種情況，2015年，文獻(xiàn)[8]提出了一種基于SNN相似度的劃分方法，該方法在目標(biāo)產(chǎn)生量測密度差異較大的情況下劃分效果較好，但存在計算量偏大的不足。

本文在文獻(xiàn)[8]的基礎(chǔ)上，提出了一種改進(jìn)的ET-GM-PHD濾波算法，該算法首先通過LOF(local outlier factor)離群檢測進(jìn)行雜波濾除；然后根據(jù)SNN(shared nearest neighbor)相似度對預(yù)處理后的量測數(shù)據(jù)進(jìn)行劃分，從而達(dá)到縮短計算時間，提高跟蹤穩(wěn)定性的效果。

1ET-GM-PHD濾波算法

1.1 ET-PHD濾波算法

2009年，Mahler在文獻(xiàn)[9]中將PHD濾波器推廣到了擴(kuò)展目標(biāo)跟蹤領(lǐng)域，并給出了數(shù)學(xué)推導(dǎo)：

(1) 預(yù)測部分

設(shè)k-1時刻的后驗強(qiáng)度vk-1，則ET-PHD預(yù)測強(qiáng)度為

βk|k-1(xk|xk-1)]vk-1(xk-1)dxk-1,

(1)

式中:γk(xk)為k時刻新生目標(biāo)的RFS的強(qiáng)度函數(shù)；pS,k(xk-1)為目標(biāo)在k時刻存活的概率；fk|k-1(xk|xk-1)為k時刻單目標(biāo)的轉(zhuǎn)移概率密度；βk|k-1(xk|xk-1)為衍生目標(biāo)的強(qiáng)度。

(2) 更新部分

設(shè)k時刻的預(yù)測強(qiáng)度vk|k-1(x)和量測集Zk，且量測個數(shù)服從Poisson分布，ET-PHD更新方程為

vk(x)=LZ(x)vk|k-1(x),

(2)

式中：LZ(x)為量測的偽似然函數(shù),

(3)

式中：γ(·)為擴(kuò)展目標(biāo)所產(chǎn)生的量測值的均值；PD(·)為目標(biāo)被檢測概率；p∠Zk為p為量測集合的Zk的一個劃分子集；ωp為劃分p的權(quán)值；|W|為子集W內(nèi)元素的個數(shù)；dW為觀測子集W的非負(fù)系數(shù)；φZ(x)為擴(kuò)展目標(biāo)量測的似然函數(shù)；λk為單位空間內(nèi)的雜波個數(shù)；ck(Zk)為雜波的分布函數(shù)[10]。

1.2 ET-GM-PHD濾波算法

2006年，VO等人在文獻(xiàn)[11]中給出了PHD濾波的高斯混合實現(xiàn)形式，在此基礎(chǔ)上，2010年，Granstrom等人提出了ET-GM-PHD濾波。ET-GM-PHD濾波算法和標(biāo)準(zhǔn)的GM-PHD濾波算法的預(yù)測步和更新步一致，本文只給出了標(biāo)準(zhǔn)GM-PHD濾波算法的預(yù)測和更新方程。

GM-PHD濾波器滿足以下假設(shè)條件:

(1) 每個目標(biāo)的運(yùn)動模型和量測模型均為高斯線性的；

(2) 目標(biāo)的生存概率和檢測概率與目標(biāo)狀態(tài)相互獨立；

(3) 新生目標(biāo)的RFS強(qiáng)度為高斯混合形式。

基于以上假設(shè)，GM-PHD濾波器的預(yù)測步可表示為

(4)

更新步可表示為

(5)

1.3 量測劃分問題描述

可見，隨著量測點的增加，劃分?jǐn)?shù)目將急劇增加，計算量將大幅增大，影響跟蹤的實時性，因此尋找準(zhǔn)確快速的量測劃分算法，是ET-GM-PHD濾波中的重要環(huán)節(jié)。針對這個問題，本文提出了一種基于LOF檢測的SNN相似度的量測劃分算法。

2 基于LOF檢測的SNN相似度的聚類算法

本文針對不同擴(kuò)展目標(biāo)產(chǎn)生量測密度差異較大的情況，結(jié)合局部異常因子離群檢測技術(shù)和SNN相似度，提出了一種改進(jìn)的ET-GM-PHD濾波算法，減小了算法的運(yùn)行時間，提高跟蹤的穩(wěn)定性。

2.1 基于LOF的量測集預(yù)處理

定義1第k距離dk(p)：對于點p的第k距離dk(p)有如下定義：dk(p)=d(p,o)，d(p,o)表示p，o2點之間的歐式距離，即直線距離，并且dk(p)滿足以下要求：①在集合中至少有不包含p點在內(nèi)的k個點o，∈C{x≠p}，滿足d(p,o,)≤d(p,o)；②在集合中最多有不包括p在內(nèi)的k-1個點o，∈C{x≠p}，滿足d(p,o,)

圖1 點p的第5距離Fig.1 The fifth distance of point p

定義2第k距離鄰域Nk(p)：p的第k距離以內(nèi)的所有點，包括第k距離點。

定義3可達(dá)距離reach-distk(p,o)：點o到點p的可達(dá)距離定義為reach-distk(p,o)=max{dk(o),d(p,o)}，如圖2所示，o1到p點的第5可達(dá)距離為d(p,o1)，o2到p點的第5可達(dá)距離為d5(o2)。

圖2 可達(dá)距離示意圖Fig.2 Reachable distance schematic diagram

定義4局部可達(dá)密度lrdk(p)：表示點p的第k鄰域內(nèi)的點到p點的平均可達(dá)距離的倒數(shù)，定義為

(6)

定義5局部異常因子LOFk(p)：表示點p的鄰域Nk(p)的局部可達(dá)密度與點p的局部可達(dá)密度之比的平均數(shù)，定義為

(7)

這個比值越接近于1，說明p和其鄰域點的密度越接近，p可能和鄰域?qū)儆谕淮兀蝗绻@個比值小于1，說明p點的密度大于其鄰域點，p為密集點；如果比值大于1，則p點密度小于其鄰域，p點傾向于異常點[12]。

圖3是LOF的實例圖，量測點周圍的圓的半徑與局部異常因子成正比，圓的半徑越大，量測點越偏向于異常值[13]。通過選取合適的LOF閾值，對量測集進(jìn)行雜波濾除，將局部異常因子大于閾值的量測點視為雜波濾除。LOF閾值可以通過以下方法來選擇：將局部異常因子從大到小排列，并繪制曲線，選取斜率最大部位的點作為LOF閾值即可。經(jīng)過LOF異常值檢測過濾后，雜波大量被剔除，算法計算復(fù)雜度降低25%～35%。

圖3 LOF實例圖Fig.3 LOF instance diagram

2.2 基于SNN相似度的聚類算法

定義1(共享最近鄰相似度)：共享最近鄰相似度的基本思想是：當(dāng)2個量測點包含一定數(shù)量的最鄰近點時，則認(rèn)為這2個量測點相似。本文中引用文獻(xiàn)[14-15]的相關(guān)概念對SNN相似度進(jìn)行定義：假設(shè)量測集X={x1,x2,x3,…,xN},xi,xj∈X，定義xi的k-鄰域為

(8)

式中：Vk(xj)為xj的k-鄰域。

如果xi∈Vk(xj)且xj∈Vk(xi)，則xi和xj的共享最近鄰SNN(i,j)=|Vk(xi)∩Vk(xj)|，|·|表示集合中元素的個數(shù)；否則SNN(i,j)=0。

SNN相似度計算的偽代碼如下

初始化k；

令Xun=X；

計算數(shù)據(jù)集X的距離矩陣；

IfXun≠?，則

{任意選擇一個x∈Xun;

計算x的k-領(lǐng)域Vk(x)={x1,x2,…,xk},

其中x1,x2,…,xk是x的k-領(lǐng)域中的數(shù)據(jù)點

Fori=1,i≤k

{ifx∈Vk(xi)則

SNN(x,xi)=Vk(x)∩Vk(xi);

else SNN(x,xi)=?;}

Xun=Xun-Vk(x);}

End If

算法中的k值需要人為設(shè)定，k值的大小與單個目標(biāo)產(chǎn)生量測點的個數(shù)有關(guān)，量測值數(shù)目的多少由傳感器精度和擴(kuò)展目標(biāo)距離傳感器的距離決定。當(dāng)傳感器精度較差或者擴(kuò)展目標(biāo)距傳感器距離較遠(yuǎn)的情況下，單個擴(kuò)展目標(biāo)產(chǎn)生的量測點可能少于20個；反之，若傳感器精度較好或者擴(kuò)展目標(biāo)距傳感器較近時，單個目標(biāo)可能會產(chǎn)生大于20個量測值。在控制其他變量的情況下，改變單個目標(biāo)產(chǎn)生的量測點個數(shù)，對劃分結(jié)果進(jìn)行分析，統(tǒng)計k值的合適取值。本文借鑒文獻(xiàn)[8]的統(tǒng)計結(jié)果，結(jié)論中覆蓋范圍較廣，本文假設(shè)單個目標(biāo)產(chǎn)生的量測值個數(shù)均值分別為10個、20個和30個，在表1的統(tǒng)計結(jié)論范圍之內(nèi)。

表1 參數(shù)k的設(shè)定范圍Table 1 Setting range of parameter k

SNN聚類是將SNN相似度大于一定閾值sl的量測劃分到同一簇中，具體的實現(xiàn)步驟如下：

步驟1:計算經(jīng)過LOF檢測濾波后的量測兩兩之間的歐式絕對距離，找到每個點的k個最近鄰點。

步驟2:計算每2個量測值之間的SNN相似度，并建立n維SNN相似度矩陣S，n是量測點的個數(shù)，矩陣S建立的示意圖如圖4所示。

圖4 建立SNN相似度矩陣Fig.4 Establishing SNN similarity matrix

步驟3:從{0,k-1}之間選取合適的相似度閾值sl，不同的sl得到不同的劃分結(jié)果，經(jīng)過多次的實驗結(jié)果分析統(tǒng)計，本文選取sl=k/2。

步驟4:對于相似度矩陣S中≥sl的相似度用1

表示，其余用0表示，得到矩陣Sth，圖5是圖4b)在sl取3時得到的矩陣，將矩陣Sth中同一個的1連通域?qū)?yīng)的量測置于同一個簇，連通域的個數(shù)即為簇的個數(shù)。

圖5 SNN相似度矩陣SthFig.5 SNN similarity matrix Sth

2.3 SNN聚類仿真實驗

如圖6所示，分別是采用k-means劃分算法和本文算法對量測密度差異較大的3個量測集產(chǎn)生的劃分結(jié)果，圖6a)中2個目標(biāo)量測集劃分出現(xiàn)了混淆，這是因為目標(biāo)兩目標(biāo)量測密度差異較大，且距離相近；圖6b)是本文算法得到的劃分結(jié)果，可以看到，量測集得到了正確的劃分。

3 仿真實驗與分析

在本次仿真實驗中，采用ET-GM-PHD濾波器，進(jìn)行100次蒙特卡羅仿真，共設(shè)置4個量測密度相差較大的跟蹤目標(biāo)，其中目標(biāo)1，2的量測密度服從λ=10的Poisson分布，目標(biāo)3，4的量測密度分別服從λ=20和λ=30的Poisson分布，使用基于距離劃分的算法和基于k-means劃分的算法和本文提出的算法進(jìn)行比較，驗證本文算法的可行性。

圖6 k-means劃分和SNN相似度劃分效果圖Fig.6 k-partition and SNN similarity partition effect diagram

3.1 仿真場景設(shè)置

本次實驗對[1 000,1 000] m×[1 000,1 000] m的二維空間區(qū)域進(jìn)行觀測，如圖8所示，擴(kuò)展目標(biāo)的運(yùn)動區(qū)域限定在x軸的-1 000 m至1 000 m，y軸的-1 000 m至1 000 m。擴(kuò)展目標(biāo)的運(yùn)動狀態(tài)和始末時間如表2所示。

表2 目標(biāo)初始狀態(tài)和始末時間Table 2 Target initial state and start-end time

(9)

(2 m/s)2I2的高斯白噪聲，I2是二維單位矩陣。

量測方程為

(10)

式中：量測噪聲vk是均值為0，協(xié)方差為Rk=(20 m/s)2I2的高斯白噪聲，各目標(biāo)產(chǎn)生的量測相互獨立。

新生目標(biāo)強(qiáng)度為

衍生目標(biāo)強(qiáng)度為

γβ(x)=0.05N(x;ξ,Pβ)，

式中:ξ為本體狀態(tài)，Pβ=diag(100,100,400,400)。

高斯混合相關(guān)修剪與合并參數(shù)：最大高斯分量數(shù)J=100，修剪門限T=1e-5，合并門限U=5，勢誤差與狀態(tài)誤差的調(diào)節(jié)因子c=10，OSPA取二階距離p=2。

3.2 仿真結(jié)果分析

圖7給出了目標(biāo)和雜波的態(tài)勢圖，目標(biāo)1,2起始于1 s，消亡于100 s；目標(biāo)3,4起始于66 s，消亡于100 s，雜波的個數(shù)服從λ=10的Poisson分布。

圖8給出了3種算法進(jìn)行一次濾波遞推的運(yùn)行時間，從圖8中可以看出，基于距離劃分和基于k-means劃分的ET-GM-PHD濾波耗時明顯高于本文提出的算法。這是因為本文算法在進(jìn)行量測劃分階段前進(jìn)行了LOF檢測雜波濾除，并且基于SNN相似度的劃分算法在劃分量測密度差異較大的量測集時具有優(yōu)勢。

圖7 目標(biāo)和雜波的態(tài)勢圖Fig.7 Situation map of target and clutter

圖9是3種算法對目標(biāo)個數(shù)估計的方針圖，從圖9中可以看到，在k=16,34,50～63,67～72,75,90,96 s時刻，基于距離劃分的ET-GM-PHD濾波算法對目標(biāo)個數(shù)的估計與真實值出現(xiàn)了誤差；k=11,25,47,60,61,63,64,67～71,82,83,92,98,99 s時刻，基于k-means劃分的算法對目標(biāo)個數(shù)出現(xiàn)錯誤估計；本文算法只在k=31,60,61,67～71,86 s時刻出現(xiàn)了目標(biāo)個數(shù)的誤估。這是由于本次實驗仿真中的目標(biāo)產(chǎn)生量測密度差異較大，當(dāng)目標(biāo)接近時，傳統(tǒng)的基于歐式距離的劃分方法會出現(xiàn)量測集的錯分，因而出現(xiàn)目標(biāo)個數(shù)估計的偏差，而本文的算法是基于SNN相似度，考慮的是量測值周圍的信息，因此劃分效果比較理想，提高了濾波器跟蹤的穩(wěn)定性。

最優(yōu)子模式指派(optimalsubpatternassignment,OSPA)距離是一種評價隨機(jī)有限集框架下多目標(biāo)跟蹤性能的指標(biāo)[16]，它是度量2個集合間差異度的誤差距離，其表達(dá)式為

(11)

圖10給出了3種算法的OSPA距離，可以看到，代表基于距離劃分算法的藍(lán)色虛線和代表k-means劃分算法的紫色點畫線波動次數(shù)較多，并且波動時間較長，而代表本文算法的紅色實線僅有4處波動，且波動時間持續(xù)較短，說明本文算法的跟蹤穩(wěn)定性更好。

從上述仿真結(jié)果中可見，本文提出的算法相較于傳統(tǒng)的基于距離和k-means劃分的算法具有明顯的優(yōu)勢，算法的運(yùn)行時間和跟蹤的穩(wěn)定性都有一個較好的優(yōu)化。

圖8 一次濾波遞推耗時對比Fig.8 Comparison of once filter recurrence time consuming

圖9 目標(biāo)估計個數(shù)對比Fig.9 Comparison of the number of target estimates

圖10 OSPA距離對比Fig.10 OSPA distance contrast

4 結(jié)束語

在擴(kuò)展目標(biāo)產(chǎn)生的量測密度差異較大的情況下，傳統(tǒng)基于距離劃分的ET-GM-PHD濾波算法跟蹤效果不佳。針對這個問題，本文提出了一種基于LOF檢測的SNN相似度的ET-GM-PHD濾波算法，并進(jìn)行了仿真對比實驗。實驗結(jié)果表明，本算法在減少計算時間的同時，跟蹤性能的穩(wěn)定性也得到了保證，對比于傳統(tǒng)方法具有較大優(yōu)勢。