DEGREE： 一種基于Delaunay三角的任意群目標(biāo)外形識別方法

李天成 嚴(yán)瑞波 成明樂 李固沖

摘 要：集群目標(biāo)相比單一甚至多目標(biāo)表現(xiàn)出復(fù)雜時變集群特性， 其外形估計與評價頗具挑戰(zhàn)性。 針對任意形狀的集群目標(biāo)外形估計與評價難題， 本文提出了一種基于數(shù)據(jù)驅(qū)動的多傳感器集群目標(biāo)群形狀建模與識別方法， 以及一種群目標(biāo)外形擬合度評判指標(biāo)。 所提算法由三個部分組成： 首先， 采用信息洪泛（Flooding）方法實現(xiàn)強連接的多傳感器對視場中目標(biāo)信息的采集與傳播； 其次， 采用密度峰值聚類實現(xiàn)觀測數(shù)據(jù)的聚類； 最后， 采用改進Delaunay三角網(wǎng)絡(luò)算法實現(xiàn)群目標(biāo)外形的擬合。 所提群外形擬合度指標(biāo)可用于對群目標(biāo)外形估計準(zhǔn)確度定量評價。 通過與超曲面、 隨機矩陣等經(jīng)典方法進行比較， 證實了所提出算法的有效性和可靠性。

關(guān)鍵詞：? 群目標(biāo)； 傳感網(wǎng)絡(luò)； Delaunay三角網(wǎng)絡(luò)； 超曲面； 隨機矩陣

中圖分類號：? TJ760

文獻標(biāo)識碼： A

文章編號：? 1673-5048（2024）02-0123-08

DOI： 10.12132/ISSN.1673-5048.2023.0227

0 引? 言

集群目標(biāo)是指基于相對位置/間距、 速度、 結(jié)構(gòu)等某些群組約束/組織準(zhǔn)則的具有一定群組整體特征的密集多目標(biāo)的集合［1］。 集群目標(biāo)探測跟蹤與識別［2-3］涉及生物群體研究［4］、 多智能體組網(wǎng)［5］、 協(xié)同控制與信息融合等多學(xué)科的理論方法與技術(shù)， 具備顯著的科學(xué)研究價值［6-7］， 同時也獲得廣泛關(guān)注。 特別是近年來， 伴隨無人機技術(shù)的迅猛發(fā)展， “小、 輕、 巧”無人機的普及程度顯著提高［7-8］， 其具備協(xié)同偵察、 干擾和打擊等強大作戰(zhàn)能力， 同時具備靈活多變的機動性能和自組織能力， 使得難以有效探測與跟蹤， 從而使得集群態(tài)勢識別極具挑戰(zhàn)［9］， 對空天安全造成極大威脅。

當(dāng)前集群目標(biāo)得益于先進控制與智能技術(shù)的發(fā)展， 具備越來越強的任意集群結(jié)伴機動靈活性， 呈現(xiàn)出復(fù)雜時變的集群外形結(jié)構(gòu)， 大大增加了集群的探測跟蹤與識別難度。 本文針對任意形態(tài)的集群目標(biāo)的群形識別與評價難題， 開展群形邊緣提取、 標(biāo)定與擬合評價研究。 集群中心和邊緣的標(biāo)定是群拓?fù)浣Y(jié)構(gòu)的核心組成部分， 是群態(tài)勢的關(guān)鍵因素， 也是區(qū)分和識別不同集群節(jié)點功能、 預(yù)測集群行動意圖的重要依據(jù)： 通過辨識群形與行為時序變化得到元意圖， 再結(jié)合群組成員序列協(xié)作關(guān)系及編隊隊形信息推理出總意圖， 即構(gòu)成一種多層次的目標(biāo)識別與場景認(rèn)知過程［10］。

當(dāng)前研究常將集群目標(biāo)的形狀信息描述為簡單點或者是簡單圖形。 如文獻［11-12］利用隨機矩陣來描述橢圓外形的密集群目標(biāo)； 文獻［13］采用隨機超曲面模型， 通過對增廣向量的估計， 實現(xiàn)對密集群目標(biāo)質(zhì)心運動狀態(tài)和擴展?fàn)顟B(tài)的聯(lián)合估計； 文獻［14-15］依據(jù)極坐標(biāo)系中反映角度到半徑映射的半徑函數(shù)描述星凸外形表面與輪廓； 文獻［16-18］分別采用了水平集隨機超曲面方法和多橢圓外形建模進行任意外形建模； 除此以外， 還有采用機器學(xué)習(xí)等方法進行集群編隊標(biāo)定， 如文獻［19］。 這些研究顯然忽略了集群目標(biāo)狀態(tài)的時變性和復(fù)雜性， 不適用于難以用簡單圖形描述的任意集群類型。

針對基于強連接傳感網(wǎng)下的任意形狀的集群目標(biāo)外形估計難題， 本文首先采用信息洪泛方法實現(xiàn)多傳感器的信息共享， 解決目標(biāo)組網(wǎng)探測問題； 其次， 采用密度峰值聚類完成對傳感器目標(biāo)集消噪與群目標(biāo)分簇處理； 最后， 采用Delaunay三角網(wǎng)絡(luò)法描述群目標(biāo)外形， 以擬合任意集群外形， 該方法命名為Delaunay群邊緣提?。―Elaunay GRoup Edge Extraction， DEGREE）。 最后， 提出了一種群目標(biāo)外形擬合度評判指標(biāo)——群外形均方誤差（Shape Root Mean Square Error， SRMSE）， 實現(xiàn)對群目標(biāo)外形擬合估計準(zhǔn)確度的有效評價。

1 場景假設(shè)與問題描述

1.1 場景假設(shè)

集群目標(biāo)往往表現(xiàn)出特定的群組特征， 即群組中各成員之間存在某些約束或行為交互， 例如鄰居成員之間存在某些速度、 距離約束， 因此， 群目標(biāo)并不能簡單理解為更大規(guī)模的多目標(biāo)。 實際上， 隨著時間推移， 群組可能發(fā)生群合并、 群分裂等結(jié)構(gòu)變換， 構(gòu)成復(fù)雜的集群運動態(tài)勢。 現(xiàn)有研究中， 往往采用一些簡單的形狀結(jié)構(gòu)如橢圓形［20］、 矩形［21］等刻畫群組外形， 或者采用多橢圓組合來進行擬合， 無法兼顧精度要求與邊緣結(jié)構(gòu)細節(jié)。 同時， 在實際工程應(yīng)用中， 往往缺乏這些群目標(biāo)外形的先驗信息， 從而難以選擇合適的先驗外形模型來進行擬合。

針對在多傳感器環(huán)境下識別復(fù)雜的任意集群外形的情景， 本文借助于強連接傳感網(wǎng)絡(luò)實現(xiàn)復(fù)雜群形的實時識別與邊緣提取。 根據(jù)群目標(biāo)跟蹤常見處理原則， 本文做出如下假設(shè)約束：

約束1： 同一個傳感器產(chǎn)生的量測不能被分配到同一個聚類簇群中。

約束2： 每個目標(biāo)的觀測/測量結(jié)果彼此獨立。

約束3： 傳感器的量測數(shù)據(jù)包含目標(biāo)的觀測和量測噪聲， 該噪聲通常為零均值高斯噪聲。

約束4： 一個目標(biāo)在每次掃描中最多只能產(chǎn)生一個量測。

假設(shè)1： 每個傳感器中存儲的是基于量測信息處理后的群目標(biāo)的位置狀態(tài)信息。

1.2 問題描述

假設(shè)一個目標(biāo)狀態(tài)數(shù)據(jù)集χ={x1， x2， …， xn}， 其中xi是數(shù)據(jù)集中的目標(biāo)點， n為數(shù)據(jù)集中的點數(shù)。 假設(shè)某傳感器s的目標(biāo)數(shù)據(jù)集為χs={xs1， xs2，? …， xsms}， 其中ms是傳感器s獲得的數(shù)據(jù)集元素數(shù)。 數(shù)據(jù)集χ表示為多傳感器的目標(biāo)數(shù)據(jù)集的并集， 即

χ={χS1，? χS2，? …，? χSN}={x11，? x12，? …，? x1m1，? x21，

x22， …， x2m2， …， xsN1， xsN2， …， xsNmN}（1）

聚類的簇群大小ma是由視場（Field of View，? FoV）內(nèi)傳感器數(shù)量以及各傳感器檢測概率決定的， 其期望為

E（ma）=∑s∈SapD， s（a）Sa （2）

式中： Sa為視場覆蓋面積為a的傳感器集合； ma為視場覆蓋面積為a中探測到的目標(biāo)數(shù)； Sa為集合Sa中元素數(shù)量， 即傳感器所獲得的數(shù)據(jù)規(guī)模。

約束1可表示c≠（xsi， xsj）， i≠j， 即xsi， xsj不屬于同一個聚類簇群/目標(biāo)， 但是可以同為雜波。 基于此， 群目標(biāo)約束聚類問題可如下定義： 多傳感器觀測數(shù)據(jù)集χ可以由聚類算法分成k個不同的聚類簇群， 同時這些簇群滿足1.1節(jié)中的4個約束。

2 DEGREE算法流程

2.1 信息洪泛（Flooding）技術(shù)

在多傳感器網(wǎng)絡(luò)應(yīng)用背景下， 本文采用泛洪（Flooding）方法［22-24］實現(xiàn)信息傳播與共享。 以下簡述方法基本原理： 假設(shè)某傳感器i所儲存的目標(biāo)狀態(tài)集合為χi={x1， x2， …， xn}， i∈S， 在第t次鄰居節(jié)點通信迭代中更新至χi（t）。 假設(shè)χi（0）χi代表傳感器網(wǎng)絡(luò)S中的初始數(shù)據(jù)， 當(dāng)?shù)螖?shù)t=1時， 各傳感器與其相鄰傳感器交換初始信息。 則此時各傳感器的信息集為

χi（1）=χi（0）∪j∈Niχj（0）=∪j∈Ni（≤1）χj（0）（3）

當(dāng)?shù)螖?shù)t≥2時， 各傳感器與相鄰傳感器交換上一次迭代后的信息。 則此時各傳感器包含的信息集為

χi（t+1）=χi（t）∪∪j∈Ni［χj（t）/χj（t－1）］=

∪j∈Ni（≤t+1）χj（0）（4）

式中： A/B指的是兩個集合之間的差集。

當(dāng)?shù)螖?shù)t≥Dm時， 網(wǎng)絡(luò)中的所有傳感器將具有相同且完備的信息集， 即

χi（t≥Dm）=∪j∈Sχj（0）（5）

2.2 密度峰值聚類（DPC）［25］

考慮如下兩個約束條件［26］：

（1） 聚類簇中心被簇中其他密度較低的目標(biāo)點或空白區(qū)域所包圍。

（2） 不同聚類簇中心之間的距離相對較遠。

在DPC中， 首先應(yīng)當(dāng)計算數(shù)據(jù)集χ中， 任意兩點之間的歐氏距離dij：

dij=xsi－xmj2=（xsi－xmj）T（xsi－xmj）（6）

繼而， 計算任意兩點之間的歐氏距離， 并由小到大進行排序獲得距離矩陣DN×N， 選擇排列順序在前百分比μ的距離作為截斷距離dc。 根據(jù)經(jīng)驗與典型場景實驗效果， μ的值為2%較為適宜［22］。

局部密度可采用截斷核函數(shù)：

ρi=∑nj=1χ（dij－dc）（7）

或者高斯核函數(shù)進行運算：

ρi=∑nj=1， j≠ie－（dijdc）2（8）

式中： n為目標(biāo)點集的模； χ（x）為指示函數(shù)， 當(dāng)x<0時， χ（x）=1， 否則χ（x）=0。 除此以外， 相對距離如下：

δi=min（dij）? if ρi≠ρmax& ρi<ρ

max（dij）otherwise （9）

最后， 在遍歷獲得所有目標(biāo)點的局部密度和相對距離后， 選取局部密度與相對距離最大的點， 即為聚類中心點。 繼而為這些中心點分別分配標(biāo)簽， 并按照設(shè)定的局部密度判斷每個點歸屬于哪個簇或者噪聲點， 其流程如圖1所示。

2.3 Delaunay三角網(wǎng)絡(luò)（DT）算法

2.3.1 相關(guān)定義［25］

定義1： 三角網(wǎng)絡(luò)， 假設(shè)χ是二維實數(shù)域上的有限點集， 邊e是由點集χ中的點作為端點構(gòu)成的封閉線段， E為e的集合。 那么， 該點集χ的一個三角網(wǎng)絡(luò)T=（χ， E）呈現(xiàn)在二維平面上為一個平面圖， 則該平面圖滿足如下條件：

（1） 所有三角形的端點恰好構(gòu)成集合χ；

（2） 任意兩個三角形的邊不相交；

（3） 所有三角形的合集構(gòu)成χ的凸包（對于空間中的對象K， 如果對象中的任意兩點構(gòu)成的線段， 也包含在對象K內(nèi)， 則稱對象K是凸的）。

定義2： Delaunay邊， 若存在一個圓經(jīng)過a、 b兩點， 且圓內(nèi)不含點集中任何其他的點， 則由a、 b兩個端點構(gòu)成的邊e稱為Delaunay邊。

定義3： Delaunay三角網(wǎng)絡(luò)（以下簡稱D-三角網(wǎng)）， 如果點集χ的一個三角網(wǎng)絡(luò)T只包含Delaunay邊， 那么該三角網(wǎng)絡(luò)稱為D-三角網(wǎng)。

定義4： 假設(shè)T為χ的任一三角網(wǎng)絡(luò)， 則當(dāng)前僅當(dāng)T中的每個三角形的外接圓的內(nèi)部不包含χ中任何的點時， T為χ的一個D-三角網(wǎng)。

2.3.2 D-三角網(wǎng)的性質(zhì)

假設(shè)存在一定義在Rn空間內(nèi)的有限點集V， Ω為點集V的一個凸包， T為凸包Ω的一個三角網(wǎng)絡(luò)， fI， T表示定義在Ω上的一個連續(xù)凸函數(shù)f的分段線性有限元插值， 則給出由閔可夫斯基距離定義的基于誤差的網(wǎng)格質(zhì)量［26］：

Q（T， f， p）=∫Ωf（x）－fI， T（x）pdx1p（10）

式（10）表征了有限點集的網(wǎng)格質(zhì)量， 其值越小代表網(wǎng)格劃分質(zhì)量越高， 也即當(dāng)三角網(wǎng)絡(luò)T*滿足式（11）時是最優(yōu)的：

Q（T*， f， p） = infT∈PNQ（T， f， p）（11）

而對于Delaunay三角網(wǎng)絡(luò)， 文獻［26］證明了D-三角網(wǎng)滿足：

Q（DT， f， p）≤Q（T*， f， p）（12）

式中： fx2， 即歐氏空間； PN為點集V在凸包Ω中的所有可能的三角網(wǎng)絡(luò)集。

式（12）表示D-三角網(wǎng)在歐氏空間中是最優(yōu)的。 除此以外， 文獻［27-28］證明有限點集在二維歐氏平面中所產(chǎn)生的D-三角網(wǎng)是唯一的。

D-三角網(wǎng)具備如下兩個屬性， 如圖2所示。

屬性1： 空圓性， Delaunay三角網(wǎng)絡(luò)是唯一的， 即任意四點不能共圓， 同時該網(wǎng)絡(luò)中的任意一個三角形內(nèi)部不能有其他點存在。

屬性2： 最大化最小角， 在觀測集投影產(chǎn)生的散點集可能形成的三角網(wǎng)絡(luò)中， 由Delaunay三角網(wǎng)絡(luò)產(chǎn)生的三角形的最小角最大。

上述表明， D-三角網(wǎng)是二維平面三角網(wǎng)中唯一的、 最好的， 適用于任意群形你好。

2.3.3 改進的DT算法

D-三角網(wǎng)絡(luò)可由分治算法、 逐點插入法、 三角網(wǎng)生長法等［29-31］方法實現(xiàn)。 其中較為經(jīng)典的是Bowyer-Watson算法（以下簡稱BW算法）， 屬于逐點插入法［30-32］， 如圖3所示， 該算法時間復(fù)雜度為O（nlogn）， 其中n為點集內(nèi)元素數(shù)。 幾種Delaunay三角網(wǎng)生成算法的時間復(fù)雜度如表1所示。

文獻［33］分析了影響B(tài)W算法速度的兩個原因： ①第一個超級三角形的尋找與刪除； ②點集的插入與排序。 針對第一個因素， 本文將初始超級三角形再擴大來避免產(chǎn)生虛三角形。 即根據(jù)離散點的最大分布， 產(chǎn)生一個超級三角形， 該三角形包含了點集χ中所有點。 常見的方法是相似三角形定理構(gòu)造， 但是這并不足以包含所有點， 仍需再擴大三角形。

針對第二個因素， 文獻［33］提出了一種基于O（n）階搜索樹的逐點插入優(yōu)化方法， 其核心是相鄰排列和分級加入， 將點集χ按下列方式分級：

χ=∪mi=0χ（i）

（13）

式中： χ（i）為χ的第i級節(jié)點集， 且χ（i）在不同的分布上具有一定的均勻性， 且按角標(biāo)由小到大順序排列后仍符合相鄰原則， 既能保證插點過程中的適度均勻性， 又能確保一定的相鄰性， 其時間復(fù)雜度降到了O（n）。 該方法與Bowyer-Watson算法的復(fù)雜度比較如例1所示， 證明見文獻［33］。

例1： 假設(shè)存在兩個點集S1和S2分別為

S1={Pk1（xk1， yk1）}

S2={Pk2（xk2， yk2）}

其中， 對于點集S1， 有xk1=in1－1， 當(dāng)i為偶數(shù)時yk2=jn2－1， 當(dāng)i為奇數(shù)時yk2=n2－1－jn2－1， 其中k=in2+j+1， 0≤i

對于這兩個點集， 分別采用方法1（經(jīng)典BW方法）與方法2（基于O（n）階搜索樹的逐點插入優(yōu)化法）進行D-三角網(wǎng)的構(gòu)建， 將兩種方法遍歷經(jīng)過的三角形數(shù)進行比較， 如表2～3所示。

從表2～3可以看出， 第2種樹搜索方法是O（n）階的， 且明顯優(yōu)于經(jīng)典BW方法。

同時在基于O（n）階搜索樹的逐點插入優(yōu)化法的基礎(chǔ)上， 對其進一步優(yōu)化， 加入了凸包檢測， 將外緣凹陷的邊緣進行補齊， 來完善D-三角網(wǎng)。 首先引入向量叉乘（如圖4所示）：

（CA×CD）×（CB×CD）≤0（14）

若滿足式（14）， 則認(rèn)為兩條線段相交， 否則不相交。 在此基礎(chǔ)上， 利用已生成的邊緣點， 按照一定幾何順序， 依次隔一個點連接一條線段， 如果這條線段和已生成的三角網(wǎng)絡(luò)中的線段不相交， 則將其作為這兩點之間的邊緣線段來補齊， 并將新三角形歸入三角網(wǎng)絡(luò)中。

綜上， 改進后的DT算法如圖5所示。

2.4 群外形均方誤差（SRMSE）

在集群目標(biāo)外形的識別擬合算法中， 選用何種標(biāo)準(zhǔn)來評判其擬合準(zhǔn)確度是非常關(guān)鍵的。 受超平面理論（Random Hyperface Model， RHM）［14， 34-35］的啟發(fā)， 本節(jié)提供了一個綜合評估集群外形擬合算法準(zhǔn)確度的指標(biāo)： SRMSE。 該指標(biāo)綜合考慮了目標(biāo)形狀匹配度、 擬合精度和魯棒性等關(guān)鍵性質(zhì)， 旨在提供一個全面的評估方法。 以角度φ為橫坐標(biāo)軸， 半徑r為縱坐標(biāo)軸， 不同外形展開函數(shù)誤差如下定義：

SRMSE=1n∑p∈P（rpest （φ）-rptrue （φ））2（15）

該指標(biāo)建立在以估計的群目標(biāo)聚類中心為原點的極坐標(biāo)系， 其中n為群目標(biāo)外形估計中的外形點集P中的點數(shù)， p為點集P中的點， φ為p在極坐標(biāo)系中的角度， rpest（φ）為點p與原點之間的距離， rtrue為與點p相同角度下群目標(biāo)真實外形上的點的極坐標(biāo)半徑。 SRMSE值越小代表擬合準(zhǔn)確度越高。 如圖6所示。 相比于傳統(tǒng)的RMSE， 該指標(biāo)可用于對群目標(biāo)外形估計的準(zhǔn)確度進行定量評價。

2.5 DEGREE算法偽代碼

綜上， 本文所提出的基于Delaunay三角網(wǎng)絡(luò)法的多傳感器協(xié)同任意集群外形邊緣提取與識別算法偽代碼如表4所示。

3 實驗仿真

本文實驗是在一臺聯(lián)想PC機上完成， 采用64位Windows10操作系統(tǒng)。

3.1 仿真場景設(shè)置

設(shè)置傳感器視場以及觀測范圍在［-15 000 m， 10 000 m］×［-15 000 m， 10 000 m］之間。 考慮三個群目標(biāo)， 分別為： ①梭形群目標(biāo)， 其四個頂點分別為（7 000 m， 7 000 m），（0 m， 0 m），（6 000 m， 1 000 m），（1 000 m， 6 000 m）； ②三角形群目標(biāo)， 其三個頂點分別為（-10 000 m， 6 000 m），（-6 000 m， 1 000 m），（-500 m， 8 000 m）； ③橢圓形群目標(biāo)， 其中心為（-8 000 m， -8 000 m）， 長軸長度為a=5 500 m， 短軸長度為b=4 000 m， 旋轉(zhuǎn)角度為θ=－π/4。

假定傳感器無法測量到這些群目標(biāo)數(shù)量與狀態(tài)的確切信息， 且傳感器探測中含有雜波從而造成一定比例的虛警估計。 本次仿真實驗采取泊松率為2的泊松分布來擬合虛警。 由多個傳感器獲得集群目標(biāo)探測結(jié)果如圖7所示。

通過在時刻t產(chǎn)生了對當(dāng)前場景的目標(biāo)， 再結(jié)合本文中所提出的DEGREE算法來進行實驗， 以此來展示所提出算法的有效性以及準(zhǔn)確性。

3.2 仿真實驗結(jié)果

首先針對原始數(shù)據(jù)集進行了DPC聚類以分簇， 仿真結(jié)果如圖7（b）所示。 通過DPC聚類分簇后， 獲得了三個群目標(biāo)點集， 從直觀上來看與原數(shù)據(jù)集之間較為吻合。

接下來通過優(yōu)化后的DT算法進行D-三角網(wǎng)劃分以及邊緣識別， 其結(jié)果如圖7（c）和圖7（d）所示。 可以觀察到相應(yīng)的結(jié)果。 同時采用2.4節(jié)中所提出的SRMSE來對群目標(biāo)外形提取結(jié)果進行精度識別， 結(jié)果分別如圖8與表5所示。

根據(jù)圖8與表5， 可以較為直觀地看出DEGREE算法的外形擬合準(zhǔn)確度比隨機超平面法更高。 表5對比了兩種算法之間的SRMSE， 可以發(fā)現(xiàn)DEGREE算法較之隨機超平面算法有明顯的提升， 分別對不同的群目標(biāo)外形提升了75.59%、 56.99%、 4.17%， 平均提高了45.58%。

通過上述結(jié)果， 可以發(fā)現(xiàn)在圖8（c）中， DEGREE與隨機超平面法在橢圓形群目標(biāo)外形擬合中的差距不相上下， 精度提升有限， 造成這種情況的原因主要是隨機超曲面法擬合出來的是橢圓形， 用來對橢圓形群目標(biāo)非常合適， 所以針對群目標(biāo)邊緣點擬合的DEGREE算法所繪制出來的群目標(biāo)外形就會與隨機超平面法繪制出來的基本相似。 而在圖7（a）～（b）中等非橢圓的星凸形群目標(biāo)外形擬合中， DEGREE所擬合出的邊緣點基本都分布在原外形的半徑函數(shù)上， 準(zhǔn)確度明顯要比隨機超曲面法更好。 這證明當(dāng)群目標(biāo)外形為非常規(guī)或其他任意外形時， DEGREE算法的外形擬合具有更好更精準(zhǔn)的效果。

4 總結(jié)與展望

本文針對任意形狀的集群目標(biāo)外形估計與評價難題， 提出了一種基于數(shù)據(jù)驅(qū)動的多傳感器集群目標(biāo)群形狀建模與識別方法， 該算法首先通過信息洪泛， 將傳感器產(chǎn)生的多群目標(biāo)觀測集進行共享， 之后通過DPC聚類降噪分簇， 再通過一個改進的DT算法針對多群目標(biāo)進行外形擬合， 獲得多群目標(biāo)的外形信息。 同時提出了一個用于對群目標(biāo)外形擬合準(zhǔn)確度進行評判的指標(biāo)。 相對于基于模型驅(qū)動的群目標(biāo)外形擬合方法， 本文提出的DEGREE算法既不需要先驗?zāi)Ｐ托畔ⅲ?還獲得了更高的外形擬合精度。 在此基礎(chǔ)上， 未來的研究工作將考慮時序多集群目標(biāo)重構(gòu)、 聚合、 分散以及跟蹤等問題。

參考文獻：

［1］ 陳雨迪， 武敏， 焦義文， 等. 密集群目標(biāo)跟蹤的研究進展［J］. 電訊技術(shù)， 2023， 63（4）： 589-597.

Chen Yudi， Wu Min， Jiao Yiwen， et al. Research Progress of Dense Group Target Tracking［J］. Telecommunication Engineering， 2023， 63（4）： 589-597.（in Chinese）

［2］ Li G C， Li G， He Y. Distributed Multiple Resolvable Group Targets Tracking Based on Hypergraph Matching［J］. IEEE Sensors Journal， 2023， 23（9）： 9669-9676.

［3］ Li G C， Li G， He Y. Labeled Multi-Bernoulli Filter Based Multiple Resolvable Group Targets Tracking with Leader-Follower Model［J］. IEEE Transactions on Aerospace and Electronic Systems， 2023， 59（5）： 6683-6694.

［4］ 高瑋， 饒彬， 周永坤. 仿生物學(xué)無人機集群目標(biāo)的雷達跟蹤與辨識［J］. 航空兵器， 2023， 30（3）： 103-111.

Gao Wei， Rao Bin， Zhou Yongkun. Radar Tracking and Identification of Biobimetic UAV Cluster Targets［J］. Aero Weaponry， 2023， 30（3）： 103-111.（in Chinese）

［5］ 高樹一， 林德福， 鄭多， 等. 針對集群攻擊的飛行器智能協(xié)同攔截策略［J］. 航空學(xué)報， 2023， 44（18）： 328301.

Gao Shuyi， Lin Defu， Zheng Duo， et al. Intelligent Cooperative Interception Strategy of Aircraft Against Cluster Attack［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（18）： 328301.（in Chinese）

［6］ Xiong W， Xiong Z Y， Zhang Y， et al. A Deep Cross-Modality Hashing Network for SAR and Optical Remote Sensing Images Retrieval［J］. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing， 2020， 13： 5284-5296.

［7］ Xiong W， Xiong Z Y， Cui Y Q. An Explainable Attention Network for Fine-Grained Ship Classification Using Remote-Sensing Images［J］. IEEE Transactions on Geoscience and Remote Sensing， 2022， 60： 5620314.

［8］ Zheng S Q， Li X D. An Adaptive Multi-UAV Area Coverage Method［C］∥ International Conference on Advanced Robotics and Mechatronics （ICARM）， 2022： 882-885.

［9］ 郭鵬程， 王晶晶， 楊龍順. 雷達地面目標(biāo)識別技術(shù)現(xiàn)狀與展望［J］. 航空兵器， 2022， 29（2）： 1-12.

Guo Pengcheng， Wang Jingjing， Yang Longshun. Status and Prospects of Radar Ground Target Recognition Technology［J］. Aero Weaponry， 2022， 29（2）： 1-12.（in Chinese）

［10］ 李偉生. 信息融合系統(tǒng)中態(tài)勢估計技術(shù)研究［D］. 西安： 西安電子科技大學(xué)， 2004.

Li Weisheng. Study of Situation Assessment Techniques in Information Fusion System［D］.Xian： Xidian University， 2004. （in Chinese）

［11］ Koch J W. Bayesian Approach to Extended Object and Cluster Tracking Using Random Matrices［J］. IEEE Transactions on Aerospace and Electronic Systems， 2008， 44（3）： 1042-1059.

［12］ 甘林海， 王剛， 劉進忙， 等. 群目標(biāo)跟蹤技術(shù)綜述［J］. 自動化學(xué)報， 2020， 46（3）： 411-426.

Gan Linhai， Wang Gang， Liu Jinmang， et al. An Overview of Group Target Tracking［J］. Acta Automatica Sinica， 2020， 46（3）： 411-426.（in Chinese）

［13］ Baum M， Hanebeck U D. Extended Object Tracking with Random Hypersurface Models［J］. IEEE Transactions on Aerospace and Electronic Systems， 2014， 50（1）： 149-159.

［14］ 陳輝， 杜金瑞， 韓崇昭. 基于星凸形隨機超曲面模型多擴展目標(biāo)多伯努利濾波器［J］. 自動化學(xué)報， 2020， 46（5）： 909-922.

Chen Hui， Du Jinrui， Han Chongzhao. A Multiple Extended Target Multi-Bernouli Filter Based on Star-Convex Random Hypersurface Model［J］. Acta Automatica Sinica， 2020， 46（5）： 909-922.（in Chinese）

［15］ Wahlstrm N， zkan E. Extended Target Tracking Using Gaussian Processes［J］. IEEE Transactions on Signal Processing， 2015， 63（16）： 4165-4178.

［16］ Zea A， Faion F， Baum M， et al. Level-Set Random Hypersurface Models for Tracking Nonconvex Extended Objects［J］. IEEE Transactions on Aerospace and Electronic Systems， 2016， 52（6）： 2990-3007.

［17］ Lan J， Li X R. Tracking of Extended Object or Target Group Using Random Matrix： Part II： Irregular Object［C］∥15th International Conference on Information Fusion IEEE， 2012： 2185-2192.

［18］ Lan J， Li X R. Tracking of Maneuvering Non-Ellipsoidal Extended Object or Target Group Using Random Matrix［J］. IEEE Transactions on Signal Processing， 2014， 62（9）： 2450-2463.

［19］ 張會霞， 梁彥， 馬超雄， 等. 數(shù)據(jù)和知識驅(qū)動的空戰(zhàn)目標(biāo)集群類型綜合識別［J］. 航空學(xué)報， 2023， 44（8）： 327266.

Zhang Huixia， Liang Yan， Ma Chaoxiong， et al. Comprehensive Recognization of Aerial Combat Target Cluster Type Driven by Data and Knowledge［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（8）： 327266.（in Chinese）

［20］ Lan J. Extended Object Tracking Using Random Matrix with Extension-Dependent Measurement Numbers［J］. IEEE Transactions on Aerospace and Electronic Systems， 2023， 59（4）： 4464-4477.

［21］ 王代維. 復(fù)雜環(huán)境下的非規(guī)則擴展目標(biāo)跟蹤算法研究［D］. 成都： 電子科技大學(xué)， 2021.

Wang Daiwei. Research on Extended Targets with Irregular Shape Tracking Algorithms in Complex Environment［D］.Chengdu： University of Electronic Science and Technology of China， 2021. （in Chinese）

［22］ Rodriguez A， Laio A. Clustering by Fast Search and Find of Density Peaks［J］. Science， 2014， 344（6191）： 1492-1496.

［23］ Li T C， Corchado J M， Chen H M. Distributed Flooding-then-Clustering： A Lazy Networking Approach for Distributed Multiple Target Tracking［C］∥21st International Conference on Information Fusion （FUSION）， 2018： 2415-2422.

［24］ Li T C， Corchado J M， Sun S D， et al. Clustering for Filtering： Multi-Object Detection and Estimation Using Multiple/Massive Sensors［J］. Information Sciences， 2017， 388/389： 172-190.

［25］ Delaunay B. Sur la Sphere Vide. Bulletin of the Academy of Sciences of the USSR［J］.? Classe des Sciences Mathematiques et Naturelles， 1934（8）： 793-800.

［26］ Chen L， Xu J C. Optimal Delaunay Triangulations ［J］. Journal of Computational Mathematics， 2004， 22（2）： 299-308.

［27］ Sibson R. Locally Equiangular Triangulations ［J］. The Computer Journal， 1978， 21（3）： 243-245.

［28］ Tsai V J D. Delaunay Triangulations in TIN Creation： An Overview and a Linear-Time Algorithm ［J］. International Journal of Geographical Information Systems， 1993， 7（6）： 501-524.

［29］ 武曉波， 王世新， 肖春生. Delaunay三角網(wǎng)的生成算法研究 ［J］. 測繪學(xué)報， 1999， 28（1）： 30-37.

Wu Xiaobo， Wang Shixin， Xiao Chunsheng. A New Study of Delaunay Triangulation Creation ［J］. Acta Geodaetica et Cartographica Sinica， 1999， 28（1）： 30-37.（in Chinese）

［30］ 周雪梅， 黎應(yīng)飛. 基于Bowyer-Watson三角網(wǎng)生成算法的研究 ［J］. 計算機工程與應(yīng)用， 2013， 49（6）： 198-200.

Zhou Xuemei， Li Yingfei.Algorithm Research to Generate Triangulation Network Based on Bowyer-Watson ［J］. Computer Engineering and Applications， 2013， 49（6）： 198-200. （in Chinese）

［31］ Rebay S. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm ［J］. Journal of Computational Physics， 1993， 106（1）： 125-138.

［32］ 劉士和， 羅秋實， 黃偉. 用改進的Delaunay三角化方法生成二維非結(jié)構(gòu)網(wǎng)格［J］. 武漢大學(xué)學(xué)報（工學(xué)版）， 2005， 38（6）： 1-5.

Liu Shihe， Luo Qiushi， Huang Wei. Generation of 2-D Nonstructural Grid by Modified Delaunay Method［J］. Engineering Journal of Wuhan University， 2005， 38（6）： 1-5.（in Chinese）

［33］ 鄔吉明， 沈隆鈞， 張景琳. Delaunay三角網(wǎng)格的一種快速生成法［J］. 數(shù)值計算與計算機應(yīng)用， 2001， 22（4）： 267-275.

Wu Jiming， Shen Longjun， Zhang Jinglin. A Fast Algorithm for Generating Delaunay Triangulation［J］. Journal of Unmerical Methods and Computer Applications， 2001， 22（4）： 267-275.（in Chinese）

［34］ 瞿晨敏， 戚國慶， 李銀伢， 等. 基于隨機超曲面模型的無人機群目標(biāo)跟蹤算法［C］∥ 第十屆中國指揮控制大會論文集（上冊）， 2022： 739-743.

Qu Chenmin， Qi Guoqing， Li Yinya， et al. Target Tracking Algorithm for Unmanned Aerial Vehicle Swarm Based on Random Hypersurface Model ［C］∥10th China Command and Control Conference， 2022： 739-743.（in Chinese）

［35］ 朱越， 戚國慶， 李銀伢， 等. 基于星凸形隨機超曲面的無人機群目標(biāo)自適應(yīng)跟蹤算法研究［C］∥ 第十屆中國指揮控制大會論文集（上冊）. 北京， 2022： 764-769.

Zhu Yue， Qi Guoqing， Li Yinya， et al. Research on Adaptive Tracking Algorithm for Unmanned Aerial Vehicle Group Target Based on Starconvex Random Hypersurfaces ［C］∥10th China Command and Control Conference， 2022： 764-769.（in Chinese）

DEGREE： A Delaunay Triangle-Based Approach to Arbitrary Group Target Shape Recognition

Li Tiancheng*， Yan Ruibo， Cheng Mingle， Li Guchong

（School of Automation， Northwestern Polytechnical University， Xian 710129， China）

Abstract： Compared with the single or even multiple targets， the group targets exhibit complex and time-varying structure， making the group shape estimation and evaluation quite challenging. This paper proposes a data-driven multi-sensor target group shape modeling and recognition approach to arbitrary shape estimation for group targets， and a group target shape fitting evaluation metric. The proposed approach consists of three parts. Firstly， the information flooding method is used to realize the collection and dissemination of the target information in the field of view by strongly connected sensors. Secondly， a density peak clustering method is utilized to cluster the data set. Finally， an improved Delaunay triangular network algorithm is used to fit the shape of group targets. The proposed group shape fitting evaluation metric can quantitatively evaluate the accuracy of any group target shape estimate. The effectiveness and reliability of the proposed algorithm are verified in comparison with the classic target shape fitting methods such as the hypersurface and random matrices.

Key words： group targets; sensor network; Delaunay triangulation; hypersurface; random matrix