基于DBSCAN聚类的群目标分离与合并跟踪算法

李学文，何 山，吴盘龙

（南京理工大学 自动化学院，南京 210094）

在目标跟踪领域将聚集在一起且具有相似行为模式的多个目标称为编队目标或群目标［1］，如蜂群无人机。在跟踪上述类型的目标时，可能存在一个雷达波束内有多个目标的情况，从而导致无法分辨出每一个个体目标［2］。而群目标跟踪的优点就是节约雷达资源，在某些情况下，不需要单独跟踪每个目标，因此需要较少的雷达处理和跟踪数据［3］。群中心通常是群目标跟踪过程中要跟踪和测量的对象。

由于群目标在运动过程中难免会出现群成员的分离行为、多群目标的合并行为及群目标的消失和新群目标的出现行为［4］，这些行为会引起群目标跟踪精度不稳定、数据关联错误。因此，实时检测群目标的状态变化，并对变化行为及时做出准确的措施是保证跟踪稳定的关键。蔡庆宇等［5］将群目标等效回波统计中心用于滤波器的更新，将每时刻的量测与统计中心进行关联来判断群目标成员合并与分离。耿文东等［6］通过把每时刻的量测与群目标成员进行一一关联，保留落入关联门中的量测，通过门限约束下量测的两两逐一判别来确定是否是群目标成员，该方法造成了数据关联的不确定性。Feldmann等［7］提出了一种基于随机矩阵的群分离检测方法，将群目标的扩展形状拟合为椭圆，以一个对称正定随机矩阵表示，然后利用贝叶斯滤波方法估计椭圆的中心状态和形状，并利用椭圆偏心率作为检测分离的依据，但该方法不适用于跟踪模型为非线性的情况。Qi等［8］提出了一种非椭球扩展目标跟踪（NETT）滤波器的群目标运动估计方法，估计每个子对象的运动学、扩展和测量速率状态以及子对象的数量，以保证每次分离运动同时产生多个分裂单元，且不需要分别假设分裂分量，但算法相对较为复杂。

为解决群目标分离与合并跟踪过程中数据关联不准确以及检测的鲁棒性等问题，本文提出了一种基于DBSCAN聚类的检测算法，旨在有效地判断出群目标的分离与合并，适用于多种跟踪模型。

1 DBSCAN算法

在实际作战环境下，敌军目标数量未知，无法确定群目标个数。相比于K-mean聚类［9］需要事先设置群的个数，DBSACN是一种密度聚类算法，不用初始设置群个数，只需设置搜索半径ε和最少可达目标数Nmin，针对空间目标可变的情况易于处理；同时，算法对于噪声点的识别也能减少由杂波带来的影响［10］。该算法首先从量测集中随机选取一个量测，并将其分配给集群1，然后计算该量测的ε距离内有多少个量测，如果该数量大于或等于Nmin，则将其视为核心点，将所有这些邻域内的量测集中到集群1；然后，再检查集群1中的每个成员，并找到它们各自的ε邻域内的点。如果集群1的某个成员的ε邻域内有大于或等于Nmin的量测，它将通过将这些量测放入群中来扩展集群1，直到没有更多的量测放入其中；接着，从不属于任何集群的数据集中再选取另一个点，并将其放入集群2，以此类推，直到所有量测都属于某个群或被标记为杂波。

DBSCAN算法对ε和Nmin的值非常敏感，因此，如何选择ε和Nmin的值非常重要。这些值的微小变化会显著改变DBSCAN算法产生的结果。如果选择的ε值较小，则大部分数据将会丢失，但是，ε值过高时，多个集群将会合并，并且大多数目标将聚类到同一集群中。因此，根据群目标跟踪思想，ε的值可以根据量测传感器分辨率来选择，Nmin可以根据群目标的概念来确定。

2 群目标模型

群目标跟踪一般利用质心表示群目标，群成员的运动方向和速度大小与质心保持一致，然后估计下一周期扫描的质心位置，计算估计质心和量测质心之间的误差，最后自适应调整状态矩阵的参数，使估计误差最小化。假设环境中第t个群目标需要跟踪，当群目标由其质心表示时，其系统的动态方程如下：

其中，Zt（k+1）为群中心量测信息；Wt（k+1）为量测噪声；H为量测矩阵，假设速度、加速度与噪声无关。

其中，α为滤波增益系数为初始点迹分布参数。

3 群目标跟踪门

跟踪门是多目标跟踪中筛选量测的常用方法［11-12］，主要是以前一时刻的目标预测值为中心，覆盖一定的范围，落入该范围内的量测即为有效量测，可以实现已知目标预测值与当前时刻量测的相互匹配。多目标跟踪门的大小由量测的噪声方差来确定。假设已知多目标跟踪对象有M个，在k时刻雷达探测到N个量测，量测维度为I=3，第t个目标的状态预测值为，预测协方差为，第j个量测值为和在第i个分量上分别为。若与的残差满足以下条件：

群目标跟踪的量测一般是等效量测或群中心量测，而群目标等效量测可以由落入群目标跟踪门内的所有目标量测来确定。因此，群目标跟踪门的中心可以是前一时刻群中心的预测值，跟踪门大小则由等效量测的方差确定。当群目标跟踪门内的量测数量变化波动较大时，意味着群目标可能发生分离，需要群目标数据关联和分群检测来验证。

由于在任意时刻雷达的探测结果都无法确定有多少真实量测和虚假量测，因此可以根据群目标的定义假设群目标跟踪门内至少存在两个真实量测，并且这些量测服从零均值高斯分布。

假设在k时刻某一群目标跟踪门内存在M个真实量测，则等效量测为：

由于实际情况下存在虚假量测，因此可以假设在群目标跟踪门内M个量测中存在N个虚假量测，第n个虚假量测为，其中，wnk是跟踪门内的高斯白噪声。因此，式（6）可以转化为：

根据周宏仁等［13］中等效噪声的计算方法，当m=2时，等效量测方差为：

则可得到：

群目标跟踪门为：

4 群目标分离与合并检测方法

在实际战争环境中，敌军空袭目标必然具备集群策略和编队飞行的特点，当接近我方阵地时，会表现出机动特性，将一个大群目标转变为多个小群目标分开行动，或者将多个小群目标合并为一个大群目标集中火力开始进攻。因此，群目标分离与合并检测问题是多群目标跟踪中的重要环节，针对群目标的分离、合并、消失和出现，结合群目标跟踪门和DBSCAN算法进行实时检测。

为了提高计算效率，可以基于目标状态的预测群中心设置关联门，一般采用椭圆关联门来剔除与群目标无关的等效量测［14］。根据群目标的状态先验信息获取相应的预测群中心和预测协方差，根据获取的预测群中心和预测协方差，可设置相应的关联门，当等效量测信息满足式（12），可认为该等效量测与群目标t相关，即：

4.1 群分离

当预测群中心t与多个等效量测关联且群目标t跟踪门中的有效量测数量超出预测数量范围时，则认为群目标可能发生群分离行为，群分离过程示意图如图1所示。

图1 群分离示意图

假设在k时刻群目标t跟踪门中的有效量测数量为Nt（k），k+1时刻的有效量测数量为Nt（k+1）。由式（4）可知，k+1时刻的预测量测数量为：

若k+1时刻预测量测数量与当前时刻的跟踪门中量测数量之间的差值绝对值大于等于群分离检测阈值x，即：

则需要进一步考虑关联门中的DBSCAN算法得到的等效量测。假设在k时刻通过聚类得到的两个群目标中成员量测数量为Ng1(k)和Ng2(k)，若连续两个时刻聚类群成员数量与预测量测数量满足以下条件，即：

则认为第g1个和第g2个聚类群是由群目标t的成员分离形成的。将分离后的多个小群重新初始化，利用小群中的量测更新对应的群目标跟踪门大小，并更新Ng1(0)和Ng1(0)，即：

4.2 群合并

当多个群目标的跟踪门位于这些群目标关联门的交叉区域时，则认为群目标可能发生群合并行为，需要在接下来的连续多个时刻利用DBSCAN算法进一步确定。群合并示意图如图2所示。假设连续多个时刻群目标t1和群目标t2的跟踪门位于两者的关联门交叉区域中，则将交叉区域内的量测用于DBSCAN算法中。

图2 群合并示意图

假设该连续多个时刻中的某一时刻聚类结果得到的等效量测为G，第g个聚类群成员数量为Ng(k+1)。若当前时刻第g个聚类群成员数量与群目标t1和群目标t1的预测量测数量三者满足以下条件，即：

则认为群目标t1和群目标t2合并为一个大群，将合并后的大群状态重新初始化，利用大群中的量测更新对应的群目标跟踪门大小，并更新Ng(0)，即：

4.3 群消失

当预测群中心t不与任何等效量测关联时，则认为群目标可能发生消失行为。先利用预测值直接进行更新滤波器，若下一周期仍是如此，则舍弃该预测群中心。

4.4 新群出现

在每个时刻，通过DBSCAN算法对群目标关联门外的量测进行聚类，当聚类获得的等效量测不与任何预测群中心关联时，则认为有新的群目标可能出现。通过连续几个周期对无关联的等效量测建立航迹起始，若建立成功，则进行接下来的跟踪和滤波；若建立失败，则认为该量测为杂波。

5 仿真验证

为验证算法的性能和有效性，分别对本文提出的基于DBSCAN的群目标分离与合并跟踪算法、蔡庆宇等［5］的算法以及耿文东等［6］的算法就群目标分离与合并进行比较与分析。实验结果的评价指标采用跟踪估计的均方根误差（RMSE），即：

式中，n为蒙特卡洛仿真次数；为群目标中心估计值；Xi为群目标中心真实值。

假设雷达的采样周期为T=0.05 s，测距误差为ψd，测向误差为ψα。杂波环境设置方式为：杂波的空间位置服从高斯分布，在空间内每时刻随机产生γ个杂波。在本次仿真环境中γ=6，ψd=10 m，ψα=0.05°，n=50。

假设初始时刻在雷达探测范围内存在具有10个成员的群目标，假设第i个群目标的成员初始分布在半径为ri的球体内服从均匀分布。群目标在东北天坐标系下的东北位置平面的飞行态势示意图如图3所示。群目标分离场景中，目标在0～15 s内做匀速飞行运动，在t=15 s时，群目标发生分离，其中5个目标在东北天坐标系下产生了北方向的加速度，均变为35 m/s2。群目标合并场景中，群目标2具有北向加速度，均为20 m/s2，合并后加速度变为0。群目标的初始位置、速度及加速度信息如表1和表2所示。

图3 群目标在东北天坐标系下的飞行态势及杂波分布图

表1 群分离场景目标初始信息

表2 群合并场景目标初始信息

在仿真过程中，任选某一时刻的量测点迹进行观察DBSCAN算法的效果，以验证算法的有效性，如图4所示。

图4 DBSCAN聚类算法效果图

由图5可以看出，通过DBSCAN算法实时检测群目标状态，可以及时判断出群目标的分离与合并。在初始时刻，已知的群目标数量为0，所以需要通过对初始连续几个时刻进行聚类，并根据聚类中心建立航迹起始，从而判断出真实的群目标中心及个数，才能对其进行有效跟踪。在跟踪过程中，实时观察群数量的变化情况，当群目标发生分离或合并行为时，采用本文方法进行修正跟踪算法。为验证本文算法对群目标分离与合并的检测和跟踪能力，对3种跟踪算法进行分析和比较。

图5 群目标分离与合并跟踪效果

图7 分离后群目标1的估计误差

由图6～图8可以看出，本文算法相比于其他两种算法，跟踪精度较高。在群目标分离前的跟踪精度，3种算法相差无几，但在群目标分离后，耿文东等［6］的算法是根据雷达获取量测和群质心的距离、高低角和俯仰角，通过每个量测与群质心的距离差值和角度差值是否超过设定门限来判定群目标是否发生分离，而这样造成分离出去的成员逐渐增加，形成的新群初始跟踪误差会很大；通过采用最近邻数据关联算法来判断该量测是否是群成员，造成了错误关联的增加，后期收敛较慢；蔡庆宇等［5］的算法是通过PDA算法计算群统计中心，根据量测与群统计中心的间距是否超过设定门限来判断群目标，这样同样会造成新群的初始跟踪误差会很大，但收敛后的跟踪误差比耿文东等［6］算法相对较小；本文算法通过聚类算法可以避免离群过程中多个目标连续离开群目标的现象，直接对分离过程结束后的新群进行跟踪，保证了新群的初始跟踪误差较小。

图6 群目标分离前估计误差

图8 分离后群目标2的估计误差

由于群目标在完成分离的过程中需要一定的时间，能够较早地判断出群目标处于分离阶段也是算法的关键问题。判断群目标的分离时刻往往取决于算法的参数大小，蔡庆宇等［5］通过计算量测与群质心的距离和夹角是否达到距离分离门限和角度分离门限来判断群目标的分离时刻；耿文东等［6］通过计算量测与群等效中心是否相关联来判断群目标的分离时刻；而本文算法通过调整DBSCAN算法的搜索半径即可判断群目标的分离时刻。

6 总结

本文在研究群目标的分离与合并问题上，提出了一种基于DBSCAN聚类的群目标分离与合并跟踪算法。首先在群目标模型中引入了群成员数量预测函数，然后根据群目标跟踪门中的有效量测数量变化情况和群目标关联门交叉区域中的等效量测数量变化情况，并结合DBSCAN算法对关联门中量测的聚类结果，进一步检测群目标的分离与合并等行为，保证了群分离与合并检测的实时性以及数据关联的准确性。通过仿真表明，此算法能够有效减小群中心跟踪误差，提高了分离与合并前后的整体精度，具有重要的实际意义。