基于水平集的目标分群方法

李 镜，刘磊浩，刘 新，马培博，郭胜楠

(1.中国电子科技集团公司第五十四研究所，河北 石家庄 050081； 2.中国人民解放军32299部队，河北 石家庄 050081)

0 引言

目标分群[1-3]是态势评估[4-6]领域的热点，目的是将获得的大量战斗实体聚合为多个战斗群，辅助指挥人员理解各战斗实体之间的关系，减轻指挥人员的认知压力，提高指挥人员的决策速度和效率[7-8]。

当前目标分群多是通过聚类[9-14]方法实现，即将属性相同或相似、地理位置接近的目标判为同一类。但此类方法往往需要事先指定参数，如K-means算法需要事先指定分类数K的值[12-13]；一旦参数选定，用户在分群过程中不易施加干预。即使针对同一战场目标图，不同用户的理解也往往不同，导致同一方法产生的分群结果未必能满足所有用户。

基于几何变形模型的水平集方法诞生于上世纪80年代，其中最具代表性的是1987年提出的Snake模型演化法[15]，该方法利用图像数据作为曲线演化的约束条件，对曲线拓扑结构的变化可以很自然地处理。本文将目标分群归结为一个曲线演化问题，将目标的分布情况视为对曲线演化的约束，提出了面向目标分群的代价函数，通过对代价函数进行优化，迭代求解目标分群问题。由于采用了迭代求解的方式，本文方法允许用户通过曲线的变化趋势了解战场目标分布情况，并允许用户在曲线演化过程中，根据自己对战场态势的理解，实时调节算法参数修正曲线的演化趋势。

1 问题描述

1.1 目标分群的整体流程

目标分群将关于目标对象的可用数据按空间、功能及相互作用等属性逐级分群，以揭示目标之间的相互联系，确定相互合作的功能，从而解释问题领域的各种行为，如图1所示。空间群的形成是目标分群的基础，起着承上启下的作用。目标分群过程通常包含以下4个步骤：

① 目标对象评估：明确战场目标属性；

② 形成空间群：按空间一维或多维簇分类分析而划分的群，同一群中的成员归属一致、类型相同、空间位置相近、行为相似；

③ 形成相互作用群：明确空间群的作战目标以及相互之间的关系之间的系统关系，将同一组中的目标，根据位置关系划分空间群；

④ 形成敌方/我方/中立方群：将所有相互关系群按敌方、我方和中立方标识划分为3个大群，形成战场的3个阵营。

图1 目标分群步骤

1.2 空间群构建的数学模型

空间群的划分通常包括2个步骤，首先通过预设条件，对敌我、类型、速度及方向等属性进行分组；然后将属性相近的目标按照地理空间拓扑关系划分形成群组。在二维态势图上，任何一个空间群均可用至少一条闭合曲线C完全包络。因此，按照地理空间拓扑关系划分形成群组这一步骤的划分可以转化为曲线演化问题。

本文方法首先对战场目标进行分组，即将属性相同或相似的目标划分在同一组中；然后采用式(1)所示的函数描述分组的目标在二维态势图上的分布：

(1)

式中，S为预设系数，本文将其设为255；xi，yi为第i个目标在战场中的坐标；rc为预设门限值。该式的含义是，仅在目标坐标点附近不为0，而在其余位置均为0。因此，必定可以找到一条简单闭合曲线C将函数u(x，y)的所有非零点包络其中。设定曲线演化条件，用一条或多条尽可能短的曲线，将尽量多的非零点包络其中，即可实现目标的空间分群。

曲线C演化的动力分为内力和外力2部分，本文将内力定义为曲线周长最短，将外力定义为曲线内部的非零区域最小。综上所述，本文提出如式(2)所示的优化模型：

(2)

式中，Cresult为曲线演化结果，即分群结果；F(C)为代价函数；μ为系数；length()为曲线周长；in-C为闭合曲线内部区域；out-C为闭合曲线外部区域，c为正常数。式(2)的数学含义为，寻找一条曲线Cresult，使得该曲线能够在周长尽量短的情况下，将函数u(x，y)的非零点包络其中，从而完成目标分群。不难发现，系数μ负责调节曲线周长在算法中占的比重，μ越大则意味着在曲线将尽可能的朝着的周长变短的方向演化。常数c控制着曲线面积所占的比重，c越大则曲线越朝着面积减小的方向演化。代价函数F(C)的第三项的作用是保证闭合曲线C的外部区域的非零元素尽可能的少，它可以保证在曲线演化过程中，函数u(x，y)的所有非零元素尽可能的分布在曲线内部

2 数学模型的水平集解法

本节主要讨论式(2)所示数学模型的水平集解法。水平集方法的基本思想是将曲线C视为曲面函数z=φ(x，y)在z=0处的一个特例[16]；从而将曲线C的演化问题转化为曲面z=φ(x，y)的演化问题[17-18]。

2.1 曲线C的构造

简单闭合曲线C的构造方法有很多，本文仅给出一种较为常见的曲线构造方案[17]，如式(3)所示：

(3)

其中，δ()为Dirac函数；r为正常数。可见，函数φ(x，y)表示三维空间中的一个圆锥曲面，此时曲线C表示以原点为中心，以r为半径的圆。因此，只要r足够大，就可保证曲线C将所有目标位置点包络其中。

2.2 曲线C的演化

结合式(3)可知，曲线C的内外部区域分别对应φ(x，y)>0和φ(x，y)<0的区域，则

(4)

其中，H( )为Heaviside函数，即：

(5)

将曲线C对应φ(x，y)=0的部分，根据文献[13]可知，借助函数φ(x，y)，式(2)中曲线的周长length(C)可表述为：

length(C)=length(φ(x，y)=0)=
∮δ(φ(x，y))|φ(x，y)|dxdy

(6)

将式(4)、式(6)代入式(2)中，即可得曲线C的演化方程：

(7)

式(7)的含义是曲线C的演化结果Cresult对应于曲面φ(x，y)的演化结果z=φresult(x，y)与平面z=0的交集，而φresult(x，y)可通过对代价函数F(φ)的优化得出。

2.3 曲线C的计算

根据欧拉-拉格朗日方程，式(7)所示的最优化问题可按下式迭代解出：

(8)

式中，Δt为迭代步长，式(8)中的迭代初始值依式(3)确定。

在实际计算中，为了避免由于计算误差等原因陷入局部最优解，通常选用式(9)所示的近似函数δε()替代Dirac函数δ()[15-16]：

(9)

式中，ε为预设常数，ε越趋于0，则δε()越接近δ()，本文将ε统一选为0.1。

3 仿真试验

本节依照上述算法对图1所示的想定划分空间群。目标分群脚本如图2所示。

图2 目标分群脚本

首先将式(1)中的参数rc选为400，根据式(1)计算目标组空间拓扑结构映射，如图3(a)所示；再根据2.1节介绍的方法，构造包络所有目标的曲线C，如图3(b)所示。本文将式(9)中的迭代步长选为200，系数选为0.13×2552，将常数c选为30。

图3 目标分群脚本

在Matlab7.5.0下仿真算法，分别迭代2 000，3 200，6 300，6 800次的分群结果如图4所示。在迭代6 800次后，结果趋于稳定，本文将提取最终曲线并将其映射到地图上，得到第1组目标的最终分群结果如图5所示。

图4 目标分群过程示意

图5 目标最终分群结果

综上所述，由于采用了曲线演化的方式，能够直观地显示分群结果和趋势。曲线演化过程可以辅助指挥人员理解战场态势，指挥人员也可以随时终止迭代过程，或者改变演化参数，控制演化结果。

4 结束语

本文将水平集曲线演化理论引入目标分群应用中，提出了一种新的解决方法。该方法将目标的空间分布结构视为曲线演化的约束条件，使曲线自动地在目标边沿处停止演化，从而实现分群。需要指出的是，目标分群技术本质上是利用计算机来模拟人大脑思考的过程。即使针对同一战场情形，不同人的理解也可能存在偏差。即使同一种方法，当参数选择不同数值时，结果也会有偏差。从现阶段看，这2种偏差都是难以彻底克服的。本文方法允许用户观察曲线演化的全过程，因此，即使最终分群结果与用户的理解存在偏差，用户也可参考曲线演化过程理解战场态势。