基于观测数据聚类划分的扩展目标跟踪算法*

章 涛 来 燃 吴仁彪

(1. 中国民航大学天津市智能信号与图像处理重点实验室，天津，300300； 2. 天津大学电子信息工程学院，天津，300072)

基于观测数据聚类划分的扩展目标跟踪算法*

章 涛1，2来 燃1吴仁彪1

(1. 中国民航大学天津市智能信号与图像处理重点实验室，天津，300300； 2. 天津大学电子信息工程学院，天津，300072)

针对高斯混合假设概率密度滤波扩展目标跟踪算法中的观测集合划分问题，本文分析了距离门限划分方法存在的问题，提出了一种利用聚类方法进行观测数据集合划分的方法。该方法利用极大似然方法获得目标数的估计值，以此作为聚类数利用K-means聚类对观测数据集合进行聚类划分，并利用椭球门限对观测数据进行处理以降低杂波观测对聚类划分的影响。实验结果表明，该方法能够获得正确的划分观测集合，计算复杂度较距离门限划分方法有较大降低，同时在多目标跟踪效果方面优于观测数据距离门限划分的假设概率密度滤波扩展目标跟踪算法。

多目标跟踪; 扩展目标跟踪；概率假设密度滤波；观测集合划分；K-means聚类

引 言

多目标跟踪在多传感器数据融合领域既是重要的理论问题又是重要的应用问题。目前的多目标跟踪方法可以分为传统的基于数据关联的方法[1-3]和基于随机有限集理论[4](Random finite set，RFS)的非关联方法。概率假设密度(Probability hypothesis density，PHD)滤波方法[5～7]是非关联多目标跟踪方法的代表。无论是传统的基于数据关联的多目标跟踪方法,还是基于随机有限集理论的方法，绝大多数方法都需要满足这样一个假设：每一个观测都来自于一个可以被看作质点的目标。然而由于传感器分辨率、目标存在多个反射点以及传感器与目标相对位置关系等原因，这一假设并不一定能成立,从而出现了单个目标同时产生多个观测形成的扩展目标问题，如图1所示。

图1 扩展目标示意图Fig.1 Sketch map of extended target

在随机有限集框架下，2003年Mahler提出传递后验概率密度的一阶统计矩的PHD滤波器[5]。2006年 Vo提出了线性高斯条件下PHD滤波器的近似形式GM-PHD (Gaussian mixture PHD)滤波器[8]。2009年Mahler 提出了利用假设概率密度滤波算法解决扩展目标的跟踪问题，并给出了相关算法理论框架，即ET-PHD(Extended target PHD)算法[9]。2012年，Granstrom提出了基于ET-PHD框架线性条件下的高斯混合模型实现方法，即ET-GM-PHD滤波算法[10]。在Mahler 提出的ET-PHD扩展目标跟踪算法理论框架中，需要将观测数据(包括目标及杂波)划分为多种可能的集合，然后利用所有可能集合划分进行目标状态更新计算，这种方法对于目标数和杂波较多的情况几乎是无法计算的[10]。Granstrom针对这个问题提出了一种利用距离门限实现观测数据集合划分的方法[10]。但距离门限范围的设置依赖于实验数据，导致算法性能与观测距离门限范围参数选取情况密切相关，跟踪估计性能很不稳定。

本文提出了一种利用K-means聚类进行观测数据集合划分的方法。该方法利用极大似然方法获得目标数的估计值，以此作为聚类数并利用K-means对观测数据集合进行划分，并利用椭球门限对观测数据进行处理以降低杂波观测对聚类划分的影响。实验结果表明，该方法能够获得正确的观测集合划分，计算复杂度较距离门限划分方法有较大降低，同时在多目标跟踪效果方面优于距离门限划分的假设概率密度滤波扩展目标跟踪算法。

1 概率假设密度滤波扩展目标跟踪

1.1 目标跟踪模型

(1)

(2)

在传统的目标跟踪问题中，一般假设每一个观测都来自于一个可以被看作质点的目标，但对于扩展目标，这一假设将不再成立，一个目标会产生多个观测，Mahler在其提出的ET-PHD滤波框架中将每一个目标产生的扩展观测数假设为Poisson分布。

1.2 扩展目标观测集合划分

在ET-PHD滤波扩展目标跟踪框架中，观测集合划分方法是将观测任意组合构成多个观测集合划分可能，并利用观测集合的所有集合划分可能对扩展目标的状态进行更新，当观测数较大时计算量过大，对于目标数较多和杂波较多的情况几乎是无法实现的。

(3)

式中：Rk为观测噪声协方差矩阵。该距离服从χ2分布，因此可以通过设置概率Pg获得在该概率下合理的观测集合划分距离阈值。文献[10]通过实验方法，总结出阈值取值满足Pg∈(0.3,0.8)时可较好地兼顾正确集合划分和算法计算复杂度,但由于这种阈值范围的选取依赖于实验数据所总结的经验，导致跟踪估计性能对于不同数据很不稳定。

1.3ET-GM-PHD滤波器

(4)

(5)

假设每个目标都满足式(1)线性动态模型，每个传感器观测满足式(2)线性观测模型，目标的存活概率与检测概率状态独立，目标的强度函数可以表示为高斯混合形式，则针对扩展目标的ET-GM-PHD算法的递推公式可以分为预测步和更新步两个步骤，其中预测步与传统点目标GM-PHD方法相同，即预测步为

(6)

更新步为

(7)

(8)

其中

(9)

(10)

(11)

(12)

其中

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

式中：观测zk属于观测子集W，集合的势为|W|；每个周期观测中杂波观测数服从Poisson分布，其均值为λk，一般情况下假设杂波观测数均值为常数，即λk=λ；ck(zk)为观测空间中杂波的分布函数，假设其服从均匀分布，即ck(zk)=1/V，V为观测空间；HW，RW分别表示扩维后的观测矩阵及观测噪声协方差矩阵；blkdiag (·)表示块对角矩阵计算；δ|W|,1为克罗内克(Kronecker delta)函数；p'表示观测集合划分的每一种可能；W′表示每一个观测集合划分可能中的观测子集；ωp表示当前观测划分可能的权重。

2 观测数据聚类划分

2.1 目标数估计

每一个周期获得的观测包括目标的扩展观测和杂波观测，每个目标的扩展观测数服从γ为均值的Posson分布，杂波观测数服从λ为均值的Poisson分布。由于多个独立Poisson分布的和仍然服从Poisson分布，因此每一个周期获得的观测服从均值为γNX,k+λ的Poisson分布，即

(25)

式中：NX,k表示k时刻的目标数，Mk表示k时刻的观测数。

每个目标的扩展观测数均值γ已知，杂波观测数均值λ已知，对于k时刻获得的Mk个观测可通过极大似然估计方法获得目标数NX,k的估计值，即

(26)

2.2 观测数据K-means聚类划分

由于每一个周期获得的观测中不仅包括目标观测还包括杂波观测，但是杂波均匀分布在观测空间中，离散分布的杂波观测会严重影响聚类划分的效果。如图2(a)所示，由于杂波存在影响了K-means的相似度计算，使得A，B两目标的观测被划分到同一观测子集中。为了解决这个问题，本文首先利用椭球门限对进行更新计算的观测数据进行门限处理，以减少观测数据中的杂波成分，从而改善了观测数据集合划分效果。如图2(b)所示，对观测数据进行椭球门限处理后，部分杂波被剔除掉，K-means聚类能够正确划分观测子集。

(a) 消除杂波前划分 (b) 消除杂波后划分(a) Partitioning before clutter removal (b) Partitioning after clutter removal图2 杂波对聚类划分影响的示意图Fig.2 Influence of clutter measurements on partitioning

在k时刻预测步计算后，残差向量可以表示为

(27)

残差协方差矩阵可以表示为

(28)

式中：Hk为测量矩阵；Pk(j)为第j个预测协方差矩阵；Rk为观测噪声矩阵。

利用椭球门限[11]判别对观测数据进行门限处理，以减少观测数据中的杂波成分，即有

(29)

当观测空间的维数为2时，椭球门限阈值表示为

(30)

式中：Pg为目标观测落入椭球门限的概率。

2.3 算法流程

本文提出的基于观测数据聚类划分的扩展目标递归跟踪算法流程归纳如下。

(1) 已知k-1时刻的目标强度函数υk-1(x)；

(2) 利用式(6)预测目标强度函数得到υk|k-1(x);

(6)对目标强度函数υk|k(x)的高斯项进行裁剪合,具体方法详见参考文献[12]。

3 仿真试验

图3 目标运动轨迹及观测值Fig．3 True trajectories and measurements

验证本文算法的实验场景为一个[-100,100]×[-100,100]的监视区域，4个目标匀速直线运动(如图3所示)。传感器采样周期为1 s，仿真获得40个采样周期数据，目标状态用向量[x,x',y,y']T表示，其中(x,y)表示目标的位置，(x',y')表示目标的速度，观测获得目标的二维位置信息(即nz=2)，目标运动方程及观测方程满足线性高斯模型，目标存活概率设置为Ps=0.99，检测概率设置为PD=0.9，杂波服从Poisson分布，强度设置为λ=10，杂波位置均匀分布在观测空间中。每个目标扩展观测数服从γ=5的Poisson分布。新生目标的概率假设密度函数为

(31)

图4 本文方法的状态估计结果Fig．4 Estimates of proposed algorithm图5 观测划分数比较Fig．5 Comparison of partition number

图6 目标数估计结果比较Fig．6 Comparison of target number estimation图7 OSPA距离比较Fig．7 Comparison of OSPA distance

4 结束语

本文提出了一种基于观测数据聚类划分的扩展目标跟踪算法，该方法首先利用椭球门限对观测数据进行处理以降低杂波观测对聚类划分的影响，然后利用极大似然方法获得目标数估计，并以此作为聚类数利用K-means对观测数据进行划分。实验结果表明，该方法在正确划分观测集合的基础上，计算复杂度有较大降低，同时在多目标跟踪效果方面优于观测数据距离门限划分的假设概率密度滤波扩展目标跟踪算法。

[1]Bar-ShalomY,LiXR.Multitarget-multisensortracking:Principlesandtechniques[M].Storrs,CT:YBSPublishing, 1995.

[2]Bar-ShalomY,FortmannTE.Trackinganddataassociation[M].SanDiego,CA:AcademicPress, 1988, 1-6.

[3] 李鹏飞, 黄建军, 黄敬雄,等. 一种模糊Kalman滤波机动目标跟踪的新算法 [J]. 数据采集与处理, 2009, (4):483-486.

LiPengfei,HuangJianjun,HuangJingxiong,etal.FuzzyKalmanfilterformaneuveringtargettracking[J].JournalofDataAcquisitionandProcessing, 2009, (4):483-486.

[4]MahlerR.Randomsets:Unificationandcomputationforinformationfusion—Aretrospectiveassessment[C] // 7thInternationalConferenceonInformationFusion.Stockholm,Sweden:IEEEComputerSocietyPress, 2004:1-20.

[5]MahlerR.Multi-targetBayesfilteringviafirst-ordermulti-targetmoments[J].IEEETransactionsonAerospaceandElectronicSystems, 2003, 39(4):1152-1178.

[6] 章涛, 吴仁彪. 自适应门限GM-CPHD多目标跟踪算法[J]. 数据采集与处理, 2014, 29(4):549-554.

ZhangTao,WuRenbiao.AdaptivegatingGM-CPHDformultitargettracking[J].JournalofDataAcquisitionandProcessing, 2014, 29(4):549-554.

[7] 连峰, 韩崇昭, 刘伟峰, 等. 高斯混合扩展目标概率假设密度滤波器的收敛性分析[J].自动化学报, 2012, 38(8):1343-1352.

LianFeng,HanChongzhao,LiuWeifeng,etal.ConvergenceanalysisoftheGaussianmixtureextended-targetprobabilityhypothesisdensityfilter[J].ActaAutomaticaSinica, 2012, 38(8):1343-1352.

[8]VoBN,MaWK.TheGaussianmixtureprobabilityhypothesisdensityfilter[J].IEEETransactionsonSignalProcessing, 2006, 54(11): 4091-4104.

[9]MahlerR.PHDFilterfornonstandardtargets,I:Extendedtargets[C] // 12thInternationalConferenceonInformationFusion.Seattle,WA,USA:IEEEComputerSocietyPress, 2009: 915-921.

[10]GranstromK,OrguneU.ExendedtargettrackingusingaGaussian-mixturePHDfilter[J].IEEETransactionsonAerospaceandElectronicSystems, 2012, 48(4): 3268-3286.

[11]BlackmanSS,PopoliR.Designandanalysisofmoderntrackingsystems[M].Norwood,MA:ArtechHouse, 1999.

[12]RisticB,VoBN,ClarkD,etal.Ametricforperformanceevaluationofmulti-targettrackingalgorithms[J].IEEETransactionsonSignalProcessing, 2011, 59( 7 ): 3452-3457.

[13]GranströmK,OrgunerU.ImplementationoftheGIW-PHDfilter[M].Stockholm,Sweden:LinköpingUniversityElectronicPress, 2013.

Extended Target Tracking with Clustering of Measurement Partitioning

Zhang Tao1，2， Lai Ran1，Wu Renbiao1

(1. Tianjin Key Laboratory for Advanced Signal Processing, Civil Aviation University of China, Tianjin, 300300, China;2. School of Electronic Information Engineering, Tianjin University, Tianjin, 300072,China)

A novel K-means algorithm of measurement partitioning is proposed to overcome the problem of distance partitioning algorithm in Gaussian mixture probability hypothesis density filter for extended target tracking. The number of the targets is estimated by maximum-likelihood estimator and then the estimates of the target number are used as the cluster number of K-means. An elliptical gate is introduced to remove the clutter measurements for depressing the influence of clusters. Simulation results show that the proposed algorithm reduces the computational complexity obviously, and obtains an improved performance.

multiple-target tracking; extended target tracking; GM-PHD filter; measurement partitioning; K-means clustering

国家自然科学基金(61471365，61231017，61571442)资助项目；中国民航大学中央高校基金(3122015D003)资助项目。

2014-05-09；

2016-10-14

TP391

A

章涛(1980-)，男，博士，研究方向：目标跟踪、雷达信号处理，E-mail:t-zhang@cauc.edu.cn。

来 燃(1990-)，男，硕士研究生，研究方向：多目标跟踪，E-mail:rlai@cauc.edu.cn。

吴仁彪(1966-)，男，博士，教授，研究方向：自适应信号处理和阵列信号处理在雷达、通信和导航中的应用，E-mail:rbwu@cauc.edu.cn。