基于模糊聚类的群分离与合并跟踪算法

杜明洋，毕大平，王树亮，潘继飞

(国防科技大学电子对抗学院，安徽 合肥 230037)

0 引言

杂波环境下的密集多目标跟踪是目标跟踪领域的难点问题，尤其是当目标空间位置很近、互相遮挡现象严重，如迁徙的鸟群、监控录像中的行人、低空飞行的飞机编队等[1-2]。Blackman于1977年对群问题进行了分类，他将问题分为中心群跟踪(Centroid Group Tracking, CGT)和编队群跟踪(Formation Group Tracking, FGT)[3]。这两种算法也是目前群目标跟踪中比较实用的方法[4]，其中，CGT算法在20世纪70年代由Frazier和Scott提出。该算法直接利用群的中心对群进行跟踪，最为直接，计算复杂度也相对较小；但当目标处于较强的背景噪声中时，群中的虚假量测会破坏群的分布矩阵，使量测的互联出现较大误差，造成跟踪效果恶化，在实际的军事应用中将带来很大的威胁[5]。文献[6]采用群内聚类的方法，将群内的波动考虑到群中心的计算中，相比于传统算法，能够更加适应杂波的影响，航迹更加稳定。

从20世纪70年代开始，信息融合逐渐被广泛应用于军事和非军事的各个领域[7-8]。在多目标跟踪领域，传统的数据关联算法例如最近邻(NN)、概率数据关联(PDA)、联合概率数据关联(JPDA)等都只利用了目标的运动状态(距离、速度、方位)信息[9]。信息融合可以利用有关目标的属性信息，如特征信息(空间分布特征、外形尺寸特征、电磁辐射特征等)、身份信息(敌我识别应答)等。以跟踪飞机编队为例，在海湾战争中，美军首次突袭巴格达时，攻击机群编队由32架轰炸机、16架护航机、12架电子战飞机、15架加油机组成。不同型号的飞机特征信息不同，但相对固定，而杂波的特征信息随机性较强。基于此，可以利用多特征信息融合的方法对杂波进行筛选，提高对飞机编队的跟踪精度。

在飞机编队的运动过程中，基于特定的战术要求，会出现分离、合并等机动模式[10]，这种成员的合并与分离对于群目标跟踪来说，都会引起群规模和质心的变化，造成跟踪误差变大，甚至丢失目标。现有的群目标分离、合并跟踪算法大体可以分为两类：一类从位置、方向、航迹历史等方面检测群分离与合并，基于PDA、模式空间、MCMC粒子滤波、SMC-PHDF、等方法进行群机动的处理[11-14]，文献[15]通过区分弹道导弹与诱饵的微动多普勒特征，基于时频图的周期相关性进行群目标的分离检测；另一类从群的结构模型出发，通过演化图网络模型估计群的结构及状态，描述群的分离与合并运动[16]。基于此，本文通过多特征信息融合理论对回波进行筛选，提出了基于模糊聚类的群合并与分离算法。

1 多特征信息融合

关联度定义为根据某个特征信息判定跟踪门内的各个有效量测与真实目标的关联程度。多特征信息融合，是基于目标多种特征信息的量测值，计算与真实目标的关联度[17]。本文融合目标的运动状态信息和电磁辐射信息，应用于CGT算法中的数据关联，计算确认量测与真实目标之间的关联度，一定程度上克服了杂波的干扰，使得量测值与预测值可以准确互联。

假设航迹已经起始，则系统的动态方程可表示为：

X(k+1)=F(k)X(k)+G(k)u(k)+V(k)

(1)

量测方程为：

z(k)=H(k)X(k)+W(k)

(2)

式(2)中，H(k)为量测矩阵，z(k)表示k时刻群的量测值，W(k)表示零均值高斯白噪声，设Z(k)为k时刻的量测集合，

(3)

式(3)中，mk为k时刻的量测个数。

1) 目标运动状态关联度

将目标运动状态量测的关联度记为ms，群中第i个有效量测的ms(i)定义为

(4)

式(4)中，di(k)为确认波门内有效状态量测与预测值的距离。可以看出，ms(i)∈(0,1]，di(k)越小，ms(i)越大，则关联度越大。

2) 目标载频关联度

基于目标载频的关联度记为mf，在第k次采样中，群中各个确认量测对应的目标载频分别用f1(k)，f2(k)，…，fM(k)表示。设第k-1次采样时群跟踪门所对应目标载频的观测值用f(k-1)表示，记观测频差Δfi(k)=|fi(k)-f(k-1)|。观测频差越大，则该量测与真实目标的关联度就越小。此外，频率关联度的定义还与目标的频率类型有关。基于此，对固定频率(FIX)的目标，群中第i个有效量测的mf定义为：

(5)

对频率捷变(FA)的目标，群中第i个有效量测的mf定义为：

(6)

式(6)中，fA是频率捷变范围，fε是门限值。mf(i)∈(0,1]，mf(i)越大，则关联程度越高。

3) 目标脉宽关联度

将脉宽(Pulse Width, PW)的关联度记为mPW，mPW的定义也与目标的脉宽类型有关。定义原则与频率关联度相同。mPW(i)∈(0,1]，mPW(i)越大，说明关联程度越高。

4) 目标脉冲重复间隔关联度

第k次采样时，各个有效量测的脉冲重复周期(Pulse Repetition Interval, PRI)分别用Tr1(k)，Tr2(k)，…，TrM(k)表示。假设第k-1次采样时该确认波门所对应目标的PRI为Tr(k-1)，PRI的观测差记为ΔTri(k)=|Tri(k)-Tr(k-1)|，简记为ΔTri。

将PRI的关联度记为mTr，表示脉冲重复间隔的观测差对关联程度的影响，mTr的定义与目标PRI的类型有关。若目标为重频固定(PRIFIX)，则关联度mTr的定义与固定频率类型的mf的定义类似。若目标为重频参差(PRIST)，以二参差为例，设二参差重频的差值记为DTr，则确认波门中第i个有效量测的关联度mTr的定义为：

(7)

式(7)中，Trε是由系统噪声与量测噪声导致的PRI测量误差。mTr(i)∈(0,1]，mTr(i)越大，说明关联程度越高。

完成上述各项特征信息的关联度计算后，还需考虑各关联度的权值分配。以a1，a2，a3，a4分别表示在运动状态、目标载频、脉宽、重频等方面确认量测与真实目标的关联度的权值，则群中第i个有效量测在多特征信息共同作用下的关联度可以记为：

m(i)=a1ms(i)+a2mf(i)+a3mPW(i)+a4mTr(i)

(8)

权值满足归一化条件，即a1+a2+a3+a4=1。

权值的选择在不同环境中需要视具体情况而定。以飞机编队为例，如引言中所述，在实际应用中，作战方式不同，飞机的力量编成也会不同。在合成空袭作战中，常常将各种飞机统一编组，形成执行不同任务的群体，在统一指挥下协同作战，共同完成攻击任务。因此目标的载频、脉宽、重频等电磁辐射信息也会不尽相同。本文以融合目标的运动状态信息和载频信息为例，由于在密集杂波背景下，位置的量测信息会受到杂波的干扰，因此运动状态关联度ms的权值a1应当相对较小；另一方面，与杂波频率的随机性相比，目标载频更具有确定性，因此通过载频信息可以更加准确地区分杂波和真实量测，所以目标载频关联度mf的权值a2应当相对较大。在本文中，运动状态关联度ms权值a1取0.3，目标载频关联度mf权值a2取0.7。

根据相关指标信息，设定关联度门限值η，对候选回波进行筛选，

(9)

在遍历每一时刻确认波门内量测之后，即完成了对群内目标数量的估计。在本文中，η取0.5。

2 基于聚类的群跟踪算法

按照所采用的基本策略不同，可将聚类算法分为两类。一是层次(hierarchical)或凝聚式(agglomerative)算法，这类算法一开始将每个点都看成是一个簇，簇与簇之间按照接近度(closeness)来组合，而接近度可以基于“接近”的不同含义采用不同的定义。当进一步的组合导致多个原因之一的非期望结果时，上述组合过程结束。例如，当达到预先给定的簇数目时可以停止聚类。二是点分配算法，即按照某个顺序依次考虑每个点，并将它分配到最适合的簇中，点分配算法中最经典的是k均值(k-means)算法。该算法假定环境为欧式空间，且最终簇的数目已知。本文基于k-means算法，结合中心群跟踪算法，将密集的群内目标分成若干个聚类小群，通过对小群运动状态的估计实现对大群整体的跟踪。具体算法步骤如下：

1) 针对群中心的一步预测建立跟踪波门

设X(k|k-1)为k时刻群状态的一步预测值，定义落入其确认波门内的量测必须满足以下条件，

(10)

(11)

RG=BRmB′

(12)

式(12)中，B为量测坐标系到跟踪坐标系中的转换矩阵，Rm是量测坐标系下的群量测的误差协方差矩阵。从满足上述判决条件的点迹中，选择归一化距离D2最小的量测作为一个群t的种子量测(Seed Measurement)。

2) 选择聚类中心

假设群内聚类数目为T，定义群内第t个聚类中心(Cluster Centroid)在k时刻的状态向量为：

(13)

考虑到聚类中心将参与小群几何中心的计算，因此最好选择群内的目标点，这样可以避免引入新的点迹，影响群内目标的分布。此外，想要选出极有可能不在同一簇的点，一种简单的方法是选择彼此距离尽量远的点迹，即“最远”原则。基于此，聚类中心的选取按照以下步骤进行：

①选择种子量测作为第1个聚类中心；

②计算剩余点到种子量测的距离，从中选择最大距离对应的点作为第2个聚类中心；

③分别计算剩余点到前两个聚类中心的距离，两个距离中的较小值作为该点到前两个聚类中心的“得分”，选择“得分”最高对应的点作为第3个聚类中心；

④以此类推，完成聚类中心的初始化。

3) 形成小群

计算群内量测与聚类中心的距离，将量测归于最近的聚类中心，形成t个小群。计算各小群的几何中心、分布矩阵及权重，

(14)

(15)

(16)

k时刻群t所占的权重γk,t可用下式表示，

(17)

4) 航迹维持

群目标在运动过程中可能存在整体机动(加速、减速或转弯等运动)或分离、合并的情形。以遂行轰炸任务为例，飞机以编队形式到达任务区域，之后编队分离，对不同位置的目标进行轰炸，任务完成后以编队形式返航。文献[6]中利用速度的一步预测值对聚类中心进行外推，然而当飞机编队运动状态发生变化时，外推法得到的聚类中心不能准确反映群中目标的分布，从而使聚类效果受到影响。因此，本文根据每一时刻筛选的量测实时地选取聚类中心。将大群通过聚类分为T个小群后，需要与上一时刻进行数据互联以维持航迹。本文基于最近邻算法的思想，通过下式计算k时刻第j个聚类中心的真实值与各聚类中心的一步预测的归一化距离，选择最小归一化距离所对应的值与k-1时刻进行互联，完成航迹的维持。

(18)

算法的流程图如图1所示。

图1 算法流程图Fig. 1 Algorithm flow chart

3 仿真实验

相比文献[6]，本文提出算法做出两点改进，第一，采用多特征信息融合的方法进行量测的筛选；第二，采用实时选取聚类中心的方法代替了外推法。本节通过Monte Carlo仿真实验对上述两点改进的有效性分别进行验证。实验结果的评价指标采用跟踪估计的均方根误差(RMSE)，定义为：

(19)

3.1 仿真条件

跟踪由8个目标组成的群目标，各目标的间距在150～300 m之间，目标在x-y平面内运动，模拟实际飞机编队飞行。检测概率Pd=0.98，门概率PG=0.999 7，采样间隔为1 s，仿真运动时间为60 s，Monte Carlo仿真次数为50次。在滤波过程中产生随机的杂波，杂波的空间位置服从高斯分布，个数服从泊松分布，初始杂波密度λ=4×10-6/m2。目标初始状态数据如表1，表2所示。本文选取目标载频与运动状态作为特征信息进行融合，具体数据如表3所示，将大群划分为4个聚类小群，即T=4。

在群分离场景中，t=1～34 s，群整体做匀速直线运动；t=35 s时，群发生分离，分群1中有4个目标，做左转弯运动，分群2中剩余4个目标继续做匀速直线运动。

表1 群分离场景目标初始状态数据

表2 群合并场景目标初始状态数据

表3 目标的辐射特征数据

在群合并场景中，t=1～34 s，分群1做左转弯运动，t=35～60 s，做匀速直线运动；分群2一直做匀速直线运动。当t=35 s时，群发生合并。

3.2 仿真结果及分析

1) 仿真实验1

从仿真步数中任选时刻k，观察本文算法各步骤对接收量测处理的效果，以验证算法的有效性，具体如图2所示。

图2 算法效果图Fig.2 Performance of the proposed algorithm

由图2可以看出，首先，多特征信息融合的方法较好地完成了对量测的筛选；其次，采用k-means聚类的方法，设置初始聚类数目为4，并以种子量测作为第1个聚类中心，依次完成聚类中心的选取，而后根据各点间距离，将大群分成4个小群，计算各小群权值，得出各小群的中心。下一时刻，重复上述步骤，并与k时刻进行航迹关联，以此类推，通过估计4个聚类小群的运动状态，完成对大群态势的检测。

2) 仿真实验2

验证多特征信息融合数据关联的准确性。场景为杂波背景下匀速运动的群目标，将文献[6]中算法改进为实时选取聚类中心，仅验证信息融合对算法的优化效果。

图3(a)为本文算法对群目标的跟踪效果图。由图3(b)可以看出，相比于文献[6]中基于聚类的CGT算法，本文提出算法通过融合目标多个特征的信息，能够更好地对杂波进行筛选，提高了对群中心的估计精度。

图3 多特征信息融合算法性能图Fig.3 Performance of multi-characteristic information fusion algorithm

3) 仿真实验3

验证本文算法对群机动的检测能力。图4、图5分别为运动场景及跟踪效果模拟。图6为群分离前后传统算法、文献[6]算法与本文算法对群中心的估计误差对比。

图4 群机动的真实运动轨迹及杂波分布图Fig.4 Motion trajectory of group maneuvering and clutter map

图5 群机动跟踪效果图Fig.5 Performance of tracking group target maneuvering

图6 群分离跟踪误差Fig.6 RMSE of tracking group target splitting

由图5可以看出，通过群内聚类的方式可以较好地检测出群的分离与合并。特别的，在群合并的跟踪中，起始时刻相当于多群的跟踪问题，按照本文提出算法，第一个聚类中心的初始化选择有效量测的几何中心，由于与真实量测距离较远，小群中仅有一个点(聚类中心)，即形成了起始时刻的孤立点。但在下一个循环中，以种子量测作为第一个聚类中心，通过聚类以及航迹互联，较好地实现了对两个分群的跟踪，在群合并之后跟踪效果较好。由此说明本文提出算法对群分离和合并都具有较好的跟踪效果，证明了算法的普适性。

通过比较可以看出，三种算法中本文算法精度最高。特别的，由图6(a)可以看出，文献[6]采取聚类的方法，相比于传统算法，提高了杂波背景下群中心的估计精度；但是由于速度的估计存在误差，随着算法的循环，采用速度估计值对聚类中心进行外推会使得误差积累，聚类中心将无法准确反映群内目标的分布，因此分离前文献[6]中算法的估计误差逐渐增大。从图6(b)和(c)中可看出，当群分离之后，此时大群中心的速度与两分群的实际速度相差较大，仍然利用其进行外推，将导致跟踪发散甚至丢失目标，因此，文献[6]的算法不具有检测群机动的能力；而传统算法只对大群中心进行估计，估计结果可能更接近其中一个分群，即对一个分群估计误差较小，对另一分群估计误差较大，所以传统算法同样无法检测群的机动。

4) 仿真实验4

比较文献[6]中算法与本文算法的实时性。改变杂波密度，跟踪群目标机动，两种算法的耗时对比如图7所示。

图7 群分离算法耗时对比图Fig.7 Comparison of calculate time of tracking group target splitting

从图7中可以看出，本文采用实时选取聚类中心的方法，相比文献[6]中的外推法运算量有所增加。通过计算，本文算法平均单次Monte Carlo仿真耗时增加了4%，即本文算法在不影响跟踪实时性的前提下，减小了对群目标的跟踪误差，并实现了群机动的检测，相比于文献[6]中算法性能有所提升。

4 结论

本文提出了基于模糊聚类的群分离与合并跟踪算法。该算法首先通过结合目标的运动状态信息及电磁辐射信息，计算候选回波与真实目标的关联度，对量测进行筛选；其次，基于k-means聚类将群目标分为若干个小群，并结合中心群跟踪算法，选取种子量测作为第一个聚类中心，根据“最远”原则，依次完成各聚类中心的初始化，在每一个算法循环中实时选取聚类中心，采用最近邻方法以维持航迹。仿真结果表明，本文算法提高了对群目标的跟踪精度，并且能够有效检测群的分离与机动，具备工程实用性。