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）