DEGREE： 一种基于Delaunay三角的任意群目标外形识别方法

李天成 严瑞波 成明乐 李固冲

摘 要：集群目标相比单一甚至多目标表现出复杂时变集群特性， 其外形估计与评价颇具挑战性。 针对任意形状的集群目标外形估计与评价难题， 本文提出了一种基于数据驱动的多传感器集群目标群形状建模与识别方法， 以及一种群目标外形拟合度评判指标。 所提算法由三个部分组成： 首先， 采用信息洪泛（Flooding）方法实现强连接的多传感器对视场中目标信息的采集与传播； 其次， 采用密度峰值聚类实现观测数据的聚类； 最后， 采用改进Delaunay三角网络算法实现群目标外形的拟合。 所提群外形拟合度指标可用于对群目标外形估计准确度定量评价。 通过与超曲面、 随机矩阵等经典方法进行比较， 证实了所提出算法的有效性和可靠性。

关键词：  群目标； 传感网络； Delaunay三角网络； 超曲面； 随机矩阵

中圖分类号：  TJ760

文献标识码： A

文章编号：  1673-5048（2024）02-0123-08

DOI： 10.12132/ISSN.1673-5048.2023.0227

0 引  言

集群目标是指基于相对位置/间距、 速度、 结构等某些群组约束/组织准则的具有一定群组整体特征的密集多目标的集合［1］。 集群目标探测跟踪与识别［2-3］涉及生物群体研究［4］、 多智能体组网［5］、 协同控制与信息融合等多学科的理论方法与技术， 具备显著的科学研究价值［6-7］， 同时也获得广泛关注。 特别是近年来， 伴随无人机技术的迅猛发展， “小、 轻、 巧”无人机的普及程度显著提高［7-8］， 其具备协同侦察、 干扰和打击等强大作战能力， 同时具备灵活多变的机动性能和自组织能力， 使得难以有效探测与跟踪， 从而使得集群态势识别极具挑战［9］， 对空天安全造成极大威胁。

当前集群目标得益于先进控制与智能技术的发展， 具备越来越强的任意集群结伴机动灵活性， 呈现出复杂时变的集群外形结构， 大大增加了集群的探测跟踪与识别难度。 本文针对任意形态的集群目标的群形识别与评价难题， 开展群形边缘提取、 标定与拟合评价研究。 集群中心和边缘的标定是群拓扑结构的核心组成部分， 是群态势的关键因素， 也是区分和识别不同集群节点功能、 预测集群行动意图的重要依据： 通过辨识群形与行为时序变化得到元意图， 再结合群组成员序列协作关系及编队队形信息推理出总意图， 即构成一种多层次的目标识别与场景认知过程［10］。

当前研究常将集群目标的形状信息描述为简单点或者是简单图形。 如文献［11-12］利用随机矩阵来描述椭圆外形的密集群目标； 文献［13］采用随机超曲面模型， 通过对增广向量的估计， 实现对密集群目标质心运动状态和扩展状态的联合估计； 文献［14-15］依据极坐标系中反映角度到半径映射的半径函数描述星凸外形表面与轮廓； 文献［16-18］分别采用了水平集随机超曲面方法和多椭圆外形建模进行任意外形建模； 除此以外， 还有采用机器学习等方法进行集群编队标定， 如文献［19］。 这些研究显然忽略了集群目标状态的时变性和复杂性， 不适用于难以用简单图形描述的任意集群类型。

针对基于强连接传感网下的任意形状的集群目标外形估计难题， 本文首先采用信息洪泛方法实现多传感器的信息共享， 解决目标组网探测问题； 其次， 采用密度峰值聚类完成对传感器目标集消噪与群目标分簇处理； 最后， 采用Delaunay三角网络法描述群目标外形， 以拟合任意集群外形， 该方法命名为Delaunay群边缘提取（DElaunay GRoup Edge Extraction， DEGREE）。 最后， 提出了一种群目标外形拟合度评判指标——群外形均方误差（Shape Root Mean Square Error， SRMSE）， 实现对群目标外形拟合估计准确度的有效评价。

1 场景假设与问题描述

1.1 场景假设

集群目标往往表现出特定的群组特征， 即群组中各成员之间存在某些约束或行为交互， 例如邻居成员之间存在某些速度、 距离约束， 因此， 群目标并不能简单理解为更大规模的多目标。 实际上， 随着时间推移， 群组可能发生群合并、 群分裂等结构变换， 构成复杂的集群运动态势。 现有研究中， 往往采用一些简单的形状结构如椭圆形［20］、 矩形［21］等刻画群组外形， 或者采用多椭圆组合来进行拟合， 无法兼顾精度要求与边缘结构细节。 同时， 在实际工程应用中， 往往缺乏这些群目标外形的先验信息， 从而难以选择合适的先验外形模型来进行拟合。

针对在多传感器环境下识别复杂的任意集群外形的情景， 本文借助于强连接传感网络实现复杂群形的实时识别与边缘提取。 根据群目标跟踪常见处理原则， 本文做出如下假设约束：

约束1： 同一个传感器产生的量测不能被分配到同一个聚类簇群中。

约束2： 每个目标的观测/测量结果彼此独立。

约束3： 传感器的量测数据包含目标的观测和量测噪声， 该噪声通常为零均值高斯噪声。

约束4： 一个目标在每次扫描中最多只能产生一个量测。

假设1： 每个传感器中存储的是基于量测信息处理后的群目标的位置状态信息。

1.2 问题描述

假设一个目标状态数据集χ={x1， x2， …， xn}， 其中xi是数据集中的目标点， n为数据集中的点数。 假设某传感器s的目标数据集为χs={xs1， xs2，  …， xsms}， 其中ms是传感器s获得的数据集元素数。 数据集χ表示为多传感器的目标数据集的并集， 即

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

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

聚类的簇群大小ma是由视场（Field of View，  FoV）内传感器数量以及各传感器检测概率决定的， 其期望为

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

式中： Sa为视场覆盖面积为a的传感器集合； ma为视场覆盖面积为a中探测到的目标数； Sa为集合Sa中元素数量， 即传感器所获得的数据规模。

约束1可表示c≠（xsi， xsj）， i≠j， 即xsi， xsj不属于同一个聚类簇群/目标， 但是可以同为杂波。 基于此， 群目标约束聚类问题可如下定义： 多传感器观测数据集χ可以由聚类算法分成k个不同的聚类簇群， 同时这些簇群满足1.1节中的4個约束。

2 DEGREE算法流程

2.1 信息洪泛（Flooding）技术

在多传感器网络应用背景下， 本文采用泛洪（Flooding）方法［22-24］实现信息传播与共享。 以下简述方法基本原理： 假设某传感器i所储存的目标状态集合为χi={x1， x2， …， xn}， i∈S， 在第t次邻居节点通信迭代中更新至χi（t）。 假设χi（0）χi代表传感器网络S中的初始数据， 当迭代次数t=1时， 各传感器与其相邻传感器交换初始信息。 则此时各传感器的信息集为

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

当迭代次数t≥2时， 各传感器与相邻传感器交换上一次迭代后的信息。 则此时各传感器包含的信息集为

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

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

式中： A/B指的是两个集合之间的差集。

当迭代次数t≥Dm时， 网络中的所有传感器将具有相同且完备的信息集， 即

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

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

考虑如下两个约束条件［26］：

（1） 聚类簇中心被簇中其他密度较低的目标点或空白区域所包围。

（2） 不同聚类簇中心之间的距离相对较远。

在DPC中， 首先应当计算数据集χ中， 任意两点之间的欧氏距离dij：

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

继而， 计算任意两点之间的欧氏距离， 并由小到大进行排序获得距离矩阵DN×N， 选择排列顺序在前百分比μ的距离作为截断距离dc。 根据经验与典型场景实验效果， μ的值为2%较为适宜［22］。

局部密度可采用截断核函数：

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

或者高斯核函数进行运算：

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

式中： n为目标点集的模； χ（x）为指示函数， 当x<0时， χ（x）=1， 否则χ（x）=0。 除此以外， 相对距离如下：

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

max（dij）otherwise （9）

最后， 在遍历获得所有目标点的局部密度和相对距离后， 选取局部密度与相对距离最大的点， 即为聚类中心点。 继而为这些中心点分别分配标签， 并按照设定的局部密度判断每个点归属于哪个簇或者噪声点， 其流程如图1所示。

2.3 Delaunay三角网络（DT）算法

2.3.1 相关定义［25］

定义1： 三角网络， 假设χ是二维实数域上的有限点集， 边e是由点集χ中的点作为端点构成的封闭线段， E为e的集合。 那么， 该点集χ的一个三角网络T=（χ， E）呈现在二维平面上为一个平面图， 则该平面图满足如下条件：

（1） 所有三角形的端点恰好构成集合χ；

（2） 任意两个三角形的边不相交；

（3） 所有三角形的合集构成χ的凸包（对于空间中的对象K， 如果对象中的任意两点构成的线段， 也包含在对象K内， 则称对象K是凸的）。

定义2： Delaunay边， 若存在一个圆经过a、 b两点， 且圆内不含点集中任何其他的点， 则由a、 b两个端点构成的边e称为Delaunay边。

定义3： Delaunay三角网络（以下简称D-三角网）， 如果点集χ的一个三角网络T只包含Delaunay边， 那么该三角网络称为D-三角网。

定义4： 假设T为χ的任一三角网络， 则当前仅当T中的每个三角形的外接圆的内部不包含χ中任何的点时， T为χ的一个D-三角网。

2.3.2 D-三角网的性质

假设存在一定义在Rn空间内的有限点集V， Ω为点集V的一个凸包， T为凸包Ω的一个三角网络， fI， T表示定义在Ω上的一个连续凸函数f的分段线性有限元插值， 则给出由闵可夫斯基距离定义的基于误差的网格质量［26］：

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

式（10）表征了有限点集的网格质量， 其值越小代表网格划分质量越高， 也即当三角网络T*满足式（11）时是最优的：

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

而对于Delaunay三角网络， 文献［26］证明了D-三角网满足：

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

式中： fx2， 即欧氏空间； PN为点集V在凸包Ω中的所有可能的三角网络集。

式（12）表示D-三角网在欧氏空间中是最优的。 除此以外， 文献［27-28］证明有限点集在二维欧氏平面中所产生的D-三角网是唯一的。

D-三角网具备如下两个属性， 如图2所示。

属性1： 空圆性， Delaunay三角网络是唯一的， 即任意四点不能共圆， 同时该网络中的任意一个三角形内部不能有其他点存在。

属性2： 最大化最小角， 在观测集投影产生的散点集可能形成的三角网络中， 由Delaunay三角网络产生的三角形的最小角最大。

上述表明， D-三角网是二维平面三角网中唯一的、 最好的， 适用于任意群形你好。

2.3.3 改进的DT算法

D-三角网络可由分治算法、 逐点插入法、 三角网生长法等［29-31］方法实现。 其中较为经典的是Bowyer-Watson算法（以下简称BW算法）， 属于逐点插入法［30-32］， 如图3所示， 该算法时间复杂度为O（nlogn）， 其中n为点集内元素数。 几种Delaunay三角网生成算法的时间复杂度如表1所示。

文献［33］分析了影响BW算法速度的两个原因： ①第一个超级三角形的寻找与删除； ②点集的插入与排序。 针对第一个因素， 本文将初始超级三角形再扩大来避免产生虚三角形。 即根据离散点的最大分布， 产生一个超级三角形， 该三角形包含了点集χ中所有点。 常见的方法是相似三角形定理构造， 但是这并不足以包含所有点， 仍需再扩大三角形。

针对第二个因素， 文献［33］提出了一种基于O（n）阶搜索树的逐点插入优化方法， 其核心是相邻排列和分级加入， 将点集χ按下列方式分级：

χ=∪mi=0χ（i）

（13）

式中： χ（i）为χ的第i级节点集， 且χ（i）在不同的分布上具有一定的均匀性， 且按角标由小到大顺序排列后仍符合相邻原则， 既能保证插点过程中的适度均匀性， 又能确保一定的相邻性， 其时间复杂度降到了O（n）。 该方法与Bowyer-Watson算法的复杂度比较如例1所示， 证明见文献［33］。

例1： 假设存在两个点集S1和S2分别为

S1={Pk1（xk1， yk1）}

S2={Pk2（xk2， yk2）}

其中， 对于点集S1， 有xk1=in1－1， 当i为偶数时yk2=jn2－1， 当i为奇数时yk2=n2－1－jn2－1， 其中k=in2+j+1， 0≤i

对于这两个点集， 分别采用方法1（经典BW方法）与方法2（基于O（n）阶搜索树的逐点插入优化法）进行D-三角网的构建， 将两种方法遍历经过的三角形数进行比较， 如表2～3所示。

从表2～3可以看出， 第2种树搜索方法是O（n）阶的， 且明显优于经典BW方法。

同时在基于O（n）阶搜索树的逐点插入优化法的基础上， 对其进一步优化， 加入了凸包检测， 将外缘凹陷的边缘进行补齐， 来完善D-三角网。 首先引入向量叉乘（如图4所示）：

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

若满足式（14）， 则认为两条线段相交， 否则不相交。 在此基础上， 利用已生成的边缘点， 按照一定几何顺序， 依次隔一个点连接一条线段， 如果这条线段和已生成的三角网络中的线段不相交， 则将其作为这两点之间的边缘线段来补齐， 并将新三角形归入三角网络中。

综上， 改进后的DT算法如图5所示。

2.4 群外形均方误差（SRMSE）

在集群目标外形的识别拟合算法中， 选用何种标准来评判其拟合准确度是非常关键的。 受超平面理论（Random Hyperface Model， RHM）［14， 34-35］的启发， 本节提供了一个综合评估集群外形拟合算法准确度的指标： SRMSE。 该指标综合考虑了目标形状匹配度、 拟合精度和鲁棒性等关键性质， 旨在提供一个全面的评估方法。 以角度φ为横坐标轴， 半径r为纵坐标轴， 不同外形展开函数误差如下定义：

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

该指标建立在以估计的群目标聚类中心为原点的极坐标系， 其中n为群目标外形估计中的外形点集P中的点数， p为点集P中的点， φ为p在极坐标系中的角度， rpest（φ）为点p与原点之间的距离， rtrue为与点p相同角度下群目标真实外形上的点的极坐标半径。 SRMSE值越小代表拟合准确度越高。 如图6所示。 相比于传统的RMSE， 该指标可用于对群目标外形估计的准确度进行定量评价。

2.5 DEGREE算法伪代码

综上， 本文所提出的基于Delaunay三角网络法的多传感器协同任意集群外形边缘提取与识别算法伪代码如表4所示。

3 实验仿真

本文实验是在一台联想PC机上完成， 采用64位Windows10操作系统。

3.1 仿真场景设置

设置传感器视场以及观测范围在［-15 000 m， 10 000 m］×［-15 000 m， 10 000 m］之间。 考虑三个群目标， 分别为： ①梭形群目标， 其四个顶点分别为（7 000 m， 7 000 m），（0 m， 0 m），（6 000 m， 1 000 m），（1 000 m， 6 000 m）； ②三角形群目标， 其三个顶点分别为（-10 000 m， 6 000 m），（-6 000 m， 1 000 m），（-500 m， 8 000 m）； ③椭圆形群目标， 其中心为（-8 000 m， -8 000 m）， 長轴长度为a=5 500 m， 短轴长度为b=4 000 m， 旋转角度为θ=－π/4。

假定傳感器无法测量到这些群目标数量与状态的确切信息， 且传感器探测中含有杂波从而造成一定比例的虚警估计。 本次仿真实验采取泊松率为2的泊松分布来拟合虚警。 由多个传感器获得集群目标探测结果如图7所示。

通过在时刻t产生了对当前场景的目标， 再结合本文中所提出的DEGREE算法来进行实验， 以此来展示所提出算法的有效性以及准确性。

3.2 仿真实验结果

首先针对原始数据集进行了DPC聚类以分簇， 仿真结果如图7（b）所示。 通过DPC聚类分簇后， 获得了三个群目标点集， 从直观上来看与原数据集之间较为吻合。

接下来通过优化后的DT算法进行D-三角网划分以及边缘识别， 其结果如图7（c）和图7（d）所示。 可以观察到相应的结果。 同时采用2.4节中所提出的SRMSE来对群目标外形提取结果进行精度识别， 结果分别如图8与表5所示。

根据图8与表5， 可以较为直观地看出DEGREE算法的外形拟合准确度比随机超平面法更高。 表5对比了两种算法之间的SRMSE， 可以发现DEGREE算法较之随机超平面算法有明显的提升， 分别对不同的群目标外形提升了75.59%、 56.99%、 4.17%， 平均提高了45.58%。

通过上述结果， 可以发现在图8（c）中， DEGREE与随机超平面法在椭圆形群目标外形拟合中的差距不相上下， 精度提升有限， 造成这种情况的原因主要是随机超曲面法拟合出来的是椭圆形， 用来对椭圆形群目标非常合适， 所以针对群目标边缘点拟合的DEGREE算法所绘制出来的群目标外形就会与随机超平面法绘制出来的基本相似。 而在图7（a）～（b）中等非椭圆的星凸形群目标外形拟合中， DEGREE所拟合出的边缘点基本都分布在原外形的半径函数上， 准确度明显要比随机超曲面法更好。 这证明当群目标外形为非常规或其他任意外形时， DEGREE算法的外形拟合具有更好更精准的效果。

4 总结与展望

本文针对任意形状的集群目标外形估计与评价难题， 提出了一种基于数据驱动的多传感器集群目标群形状建模与识别方法， 该算法首先通过信息洪泛， 将传感器产生的多群目标观测集进行共享， 之后通过DPC聚类降噪分簇， 再通过一个改进的DT算法针对多群目标进行外形拟合， 获得多群目标的外形信息。 同时提出了一个用于对群目标外形拟合准确度进行评判的指标。 相对于基于模型驱动的群目标外形拟合方法， 本文提出的DEGREE算法既不需要先验模型信息， 还获得了更高的外形拟合精度。 在此基础上， 未来的研究工作将考虑时序多集群目标重构、 聚合、 分散以及跟踪等问题。

参考文献：

［1］ 陈雨迪， 武敏， 焦义文， 等. 密集群目标跟踪的研究进展［J］. 电讯技术， 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］ 高玮， 饶彬， 周永坤. 仿生物学无人机集群目标的雷达跟踪与辨识［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］ 高树一， 林德福， 郑多， 等. 针对集群攻击的飞行器智能协同拦截策略［J］. 航空学报， 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］ 郭鹏程， 王晶晶， 杨龙顺. 雷达地面目标识别技术现状与展望［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］ 李伟生. 信息融合系统中态势估计技术研究［D］. 西安： 西安电子科技大学， 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］ 甘林海， 王剛， 刘进忙， 等. 群目标跟踪技术综述［J］. 自动化学报， 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］ 陈辉， 杜金瑞， 韩崇昭. 基于星凸形随机超曲面模型多扩展目标多伯努利滤波器［J］. 自动化学报， 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］ 张会霞， 梁彦， 马超雄， 等. 数据和知识驱动的空战目标集群类型综合识别［J］. 航空学报， 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］ 王代维. 复杂环境下的非规则扩展目标跟踪算法研究［D］. 成都： 电子科技大学， 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三角网的生成算法研究 ［J］. 测绘学报， 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］ 周雪梅， 黎应飞. 基于Bowyer-Watson三角网生成算法的研究 ［J］. 计算机工程与应用， 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三角化方法生成二维非结构网格［J］. 武汉大学学报（工学版）， 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三角网格的一种快速生成法［J］. 数值计算与计算机应用， 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］ 瞿晨敏， 戚国庆， 李银伢， 等. 基于随机超曲面模型的无人机群目标跟踪算法［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］ 朱越， 戚国庆， 李银伢， 等. 基于星凸形随机超曲面的无人机群目标自适应跟踪算法研究［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