基于CODHD聚类划分的多扩展目标跟踪算法

苗 露，李鸿艳，冯新喜

空军工程大学 信息与导航学院，西安 710077

1 引言

多目标跟踪是利用传感器量测对目标数目和状态进行估计的过程，主要受到杂波、漏检和虚警的影响[1]。传统目标跟踪所利用的是点目标模型，假设在每一观测时刻每个目标至多产生一个量测。随着传感器分辨率的提高，这种假设不再适用，探测单个目标时会得到多个量测值，即可以得到更多的目标运动和形态信息[2]，这种目标跟踪称之为扩展目标跟踪。

Mahler根据随机有限集（RFS）理论[3]，推导出概率假设密度（Probability Hypothesis Density，PHD）滤波器的递推方程，避免了传统目标跟踪所利用的复杂数据关联过程，但存在集值积分无法求解的难题。随后，Mahler利用RFS的一阶统计矩对多目标的后验概率密度进行近似替代，提出了一阶统计矩近似的PHD滤波器，并于2009年将PHD滤波器用于扩展目标跟踪，即ET-PHD（Extended Target PHD）滤波器。假定目标运动模型满足线性高斯条件下，文献[4]给出了高斯混合PHD（Gaussian Mixture PHD，GM-PHD）滤波器的实现，文献[5]给出了扩展目标高斯混合PHD（ET-GM-PHD）滤波器的实现。文献[6]利用核密度估计方法对经过剪枝、合并后的PHD密度分布函数进行状态估计，将峰值点作为状态估计值，使目标估计结果更加精确。针对目标漏检时致使有用信息丢失和目标相近造成滤波性能下降，文献[7]对PHD滤波器的预测、更新方程加以修正，有效改善了目标跟踪性能。

根据Mahler的推导[8]，无论是ET-PHD滤波器、GMET-PHD滤波器还是GM-ET-CPHD滤波器，提高滤波器性能就需要对量测集进行快速准确的划分，这在理论上是需要考虑所有可能的划分。而实际中随着目标数和杂波量测增多，量测划分数将急剧增加，将引起计算灾难，这对扩展目标跟踪系统而言，实时性的要求难以满足[9]。关于量测集划分问题已经提出了多种解决办法，Granstrom等[5]提出了距离划分、距离辅助划分，Li等[10]提出了K-means聚类划分，以上方法均是利用距离进行划分，在量测密度差别较大时效果不佳。Zhang等[11]提出了基于快速模糊自适应共振理论（Adaptive Resonance Theory，ART）的划分方法，能进行稳定快速的量测集划分，但在多杂波环境下对多个扩展目标进行跟踪，算法易出现“饱和”问题而产生额外错误划分。文献[12]提出CODHD算法，该算法基于凝聚性层次划分，对簇合并计算过程和聚类有效性指标进行优化，得到最优聚类结果。本文基于该方法进行量测集划分，先通过自适应椭球门限进行量测预处理使无效杂波有效去除，再利用CODHD得到最优聚类结果，利用FCM运算得到量测划分子集。

2 ET-GM-PHD滤波器

Mahler在ET-PHD滤波框架下将扩展目标用空间分布模型来描述，假设扩展目标满足线性高斯运动模型，传感器观测满足线性模型，目标存活概率和检测概率相互独立，多扩展目标的预测强度函数就可以通过高斯混合的形式来表示[13]。

假设在k时刻，扩展目标的状态集表示为Xk=，量测集表示为和分别表示k时刻的第i个扩展目标的状态和量测，Nx,k和Nz,k分别表示k时刻的扩展目标数和量测数。根据RFS理论，目标的状态方程为：

其中，i=1,2,…,Nx,k，Fk表示状态转移矩阵，表示协方差为的零均值高斯白噪声。

目标的量测方程为：

其中，Hk表示观测矩阵，表示协方差为的零均值高斯白噪声。

在k时刻，预测PHD的GM可表示为：

量测更新PHD强度可通过预测PHD强度和伪似然函数相乘得到，即：

其中，量测伪似然函数为：

式中，λk=βFA,kVs为杂波量测个数的期望，ck(zk)=1/VS为观测空间中杂波的空间分布，p∠Zk为对Zk的P划分，W为某一划分中的各非空集合，ωP和dw分别为P和W的权重。

在每一观测时刻，每个扩展目标会产生多个量测，而传感器得到的量测由真实目标量测以及杂波量测构成。假设在k时刻，传感器获得量测表示为Zk=则对其进行划分的所有可能结果为：

3 量测集划分

3.1 自适应椭球门限处理

杂波量测离散、均匀分布在观测空间，若杂波和真实目标量测一同进行划分，将产生额外错误划分，最终影响滤波效果。在量测集划分前，可采用椭球门限[14]方法进行量测预处理，在不影响滤波精度的前提下，有效滤除无效杂波来改善跟踪性能。

假设在k时刻，对预测步进行计算后，第i个观测和第j个高斯分量的残差向量表示为：

ε(ji)的协方差矩阵表示为：

通过椭球门限判别对量测进行预处理，满足：

3.2 基于CODHD算法的量测集划分

利用聚类实现扩展目标量测集划分是有效途径，CODHD算法基于凝聚型层次聚类，在簇合并过程中对生成的不同划分进行聚类质量评估得到最优聚类结果。该算法对簇合并过程和聚类评估指标加以优化，使计算复杂度降低并提高聚类有效性。

对去除杂波后的量测集划分过程如下：对量测进行区间扫描生成合理划分；层次式生成不同量测划分，计算各划分中的量测局部密度并将密度最大点作为聚类中心点，得到该中心点和更高密度量测之间的最小距离；将每次得到的聚类质量构造为质量曲线并提取极大值点；通过剪枝[15]原理得到最优聚类结果并进行FCM运算，得到量测划分子集。

聚类质量评估指标Q定义为：

量测局部密度Ni计算过程如下：

（1）将量测标准差作为邻域半径：

（2）在邻域半径所构成区域内计算局部密度：

δi表示最小距离，；对于密度最高点有：。Q表示聚类中心量测密度与最小距离乘积之和的均值，若i为聚类中心，则Ni和（或）δi取较大值的可能性就越大，衡量指标Niδi也就有较大值。

凝聚型层次聚类算法在起始阶段将每个数据看做单独子簇，根据簇合并准则将子簇不断进行合并，最后使所有数据成为一个集合。假设k时刻量测集为Z={z1,z2,…,zn} ∈Rd×n，其中 d 为量测维度，n为量测个数。簇合并过程如下：

（1）初始化 S=S0。

（2）将量测进行属性值大小排序，生成序列Ai，在有限区间内扫描，寻找量测x的第i维相似量测y。

（3）每过程 S 增大 Δ(Δ={Δ1,Δ2,…,Δd})，并在上一扫描区间基础上进行扩张，继续扫描寻找相似量测进行合并：

（4）S增大到所有量测划分到一个集合。

图1表示在不同划分数下得到的聚类质量并构造为质量曲线。

图1 不同划分数目下的聚类质量

FCM通过隶属度决定量测划分，是传统硬划分K-means的改进，对划分归属模糊问题能进行较好处理。将剪枝得到的聚类结果进行FCM操作，可有效改善划分效果，其实现过程如下：

（1）提取质量曲线极值点，进行剪枝操作得到聚类数l和聚类中心集V0=(v1,v2,…,vl)，进行相关参数设置：权重指数 m(m=2)，终止阈值 ε(ε=0.01)，迭代记步器t=0。

（2）计算、更新划分矩阵Ut：

（3）更新聚类中心Vt+1：

量测集划分的典型方法和改进方法有距离阈值法、K-means聚类方法、ART方法等。距离阈值法为保证划分中能包含正确的划分子集，需要选取较大的阈值范围，这造成较多错误划分并使目标状态估计误差增大。K-means算法由于K值难以选取且随机选择初始聚类中心，致使聚类结果不稳定，在量测密度差异较大时难以进行有效划分。ART算法对输入警戒参数β比较敏感，在多扩展目标的多杂波环境下，易造成算法“饱和”问题使权向量无法自适应调整权重以适应训练模式，产生额外错误划分，使跟踪效果下降。

基于CODHD聚类划分算法的量测集划分在层次簇合并过程中对生成的不同划分进行聚类评估，得到最优聚类结果后进行FCM运算得到量测划分子集。由于簇合并过程中簇生成个数只与量测分布结构有关，使其可识别量测密度差异；采用标准差作为邻域半径计算量测局部密度，能够反映量测集的量测真实分布情况[16]；避免对量测数据直接进行反复聚类，自适应生成最佳聚类数和聚类中心后执行FCM运算，有效加快收敛速度。考虑真实扩展目标跟踪场景，在杂波环境下目标个数未知并随时间而不断发生变化，并存在目标紧邻、分裂、量测生成数未知等情形，这都影响到多目标跟踪性能。所提方法根据量测分布情况自适应得到最优聚类结果，因此适合于在杂波和目标量测未知情形下进行快速准确地扩展目标量测集划分，确保目标跟踪的实时性。

3.3 扩展目标跟踪算法流程

基于CODHD算法对量测集划分的扩展目标跟踪算法流程归结如下：

（1）已知k-1时刻的目标强度函数Dk-1(x )，预测得到k时刻的目标强度函数

（2）将新生目标和存活目标的高斯分量作为k时刻的状态预测，进行残差和椭球门限值的计算，对量测集Zk进行门限处理后只保留门限内的有效量测

（3）参数初始化：k=n,Un={z1,z2,…,zn},S=S0，Qn=Q(Un)，将量测根据第i维属性排序生成Ai。

（4）从k=n运行至k=1：

②通过簇合并生成新划分，计算Nx和δx，求得有效性指标Qk；

③生成聚类质量曲线。

（5）提取曲线极值点得到量测划分，并利用剪枝原理获得最优聚类数和聚类中心。

（6）进行FCM运算获得若干量测划分子集，并将其对目标强度函数进行更新。

4 仿真结果及分析

为证明本文方法的有效性和可行性，假定在二维平面，传感器对四个扩展目标进行跟踪，观测区域为[-500,500]m×[-500,500]m，采样周期T=1 s，观测时长为40 s。目标运动和观测方程均满足线性高斯模型，各扩展目标的初始状态以及出生、消失时间见表1。

表1 目标初始状态和运动轨迹

在不考虑目标衍生的条件下，PHD滤波器的新生过程表示为强度是γk的泊松有限集。即：

扩展目标的存活概率Ps,k=0.99，检测概率PD,k=0.95。每一观测时刻，扩展目标的量测生成分别服从均值为10、15、20、30的泊松分布，杂波生成量测服从均值为30的泊松分布，并在观测空间内服从均匀分布。高斯项修剪门限Tp=10-4，最大高斯个数Jmax=200，融合门限U=4，椭球门限参数Pg=0.95。

进行200次蒙特卡洛仿真，将本文方法和距离划分法、ART划分法用于ET-GM-PHD滤波器进行比较。采用最优子模式分配（OSPA）距离[17]（参数设置p=2,c=80）对各算法性能做出评估：

图2给出了扩展目标在杂波环境下的运动轨迹，图3和图4是不同算法得到的目标数估计和OSPA距离对比图。

图2 杂波环境下的目标运动轨迹

由图3和图4可知本文方法有更加准确的目标数估计结果以及更小的OSPA距离。这是由于通过椭球门限进行量测预处理使杂波干扰降低，利用量测分布得到最优聚类结果继续进行FCM运算从而保证聚类划分准确度，而距离划分和ART划分在多杂波环境下进行多扩展目标跟踪均产生了较多错误划分，致使跟踪效果下降。

图3 目标数目估计比较

图4 OSPA距离比较

由图5可知，本文划分方法具有较高的运行效率，这是因为在预处理阶段将杂波进行了有效滤除使后续划分算法的计算复杂度降低，利用CODHD输出最优聚类结果避免了对量测数据直接进行反复聚类并使FCM收敛速度加快。

图5 划分时间比较

5 结束语

针对杂波环境下，概率假设密度滤波器对扩展目标跟踪存在量测集划分难且效率低的问题，提出基于CODHD聚类算法进行划分的方法。先利用椭球门限将量测集中的无效杂波量测进行去除，再通过CODHD聚类划分得到最优聚类结果，进行FCM运算得到量测划分子集。结果表明所提方法可以对量测集进行快速准确的划分，保证在杂波环境下对多扩展目标的实时跟踪。