基于数据流聚类的多目标跟踪算法
马天力, 王新民, 曹宇燕, 黄誉, 穆凌霞    
西北工业大学, 自动化学院, 陕西 西安 710072
摘要: 针对传统多目标跟踪算法在航迹初始阶段易受杂波干扰,提出一种交互多模型核预估数据流聚类的多目标跟踪算法(CE_DMTT)。对数据流进行在线聚类,并运用交互式多模型预估类核位置,缩小聚类搜索范围,同时引入Renyi熵,对聚类进行自适应提取,获取潜在航迹。然后基于潜在航迹运用多假设跟踪算法实现实时跟踪。仿真结果表明,该算法有效减少计算复杂度,提高系统实时性。
关键词: 多目标     交互多模型     Renyi熵     数据流聚类     多假设跟踪    

大数据时代中,数据流应用在线财政管理、通讯、环境监控、卫星传感等领域[1, 2]。数据流挖掘是数据流应用的关键技术之一,即从大量数据中提取隐含信息,用于对未来状态做出预测以及为下一步操作提供帮助。

多目标跟踪问题是一个从大量数据信号中对目标信息挖掘的过程。研究人员提出了许多有效的方法。如最近邻(nearest neighbor,NN),概率数据关联(probabilistic data association,PDA),联合概率数据关联(joint probabilistic data association,JPDA),多假设跟踪(multiple hypothesis tracking,MHT)[3, 4, 5],这些算法都是通过对量测分配,将多目标问题转化为并行的单目标跟踪处理问题,但是其处理过程的核心及关键是数据关联,当目标数较多且存在大量虚警时,关联则会带来组合爆炸、计算量呈指数型增长等问题。He等提出的FCM-JPDA算法[6](FJPDA)克服传统JPDA计算量大的缺点,但需在航迹起始阶段提前对目标数量进行设定,不利于工程实践。

本文提出一种交互多模型核预估数据流聚类的多目标跟踪算法(CE-DMTT)。在航迹起始阶段对数据流进行聚类,并运用交互多模型对类核位置进行预估,缩小搜索范围,通过判断各类内信息熵自适应输出聚类,提取预航迹,对预航迹运用多假设算法实现对多目标的追踪。仿真结果说明本文算法能够有效减少计算量、提高实时性。

1 模型描述

设机载雷达跟踪s个目标,t时刻的量测集合为Zt,第i个目标运动特性的状态方程为:

式中: 为目标i的状态向量。Zi,t=[xi,t,yi,t,vi,t]T为测量向量,过程噪声w1,i,t与量测噪声w2,i,t分别为相互独立的高斯白噪声向量。FH分别为系统状态转移矩阵与量测矩阵。

在跟踪过程中,假设区域内杂波分布模型固定。杂波数量Nc服从参数为λ的泊松分布,杂波位置服从均匀分布。

式中:ctt时刻的杂波数。

2 交互多模型核预估数据流聚类算法 2.1 自适应Denstream聚类航迹起始算法

Denstream聚类算法[7, 8, 9]是一种在未知聚类数目的情况下可对任意形状数据进行分类的密度聚类算法。微簇密度是点在邻域内权重随时间指数衰减的结果,时间衰减函数如下所示:

式中:λ为时间衰减因子,λ>0。

定义1 (微簇)表示为(w,c,r)。其中w为微簇权重,c为微簇中心,r为微簇半径。根据各个时刻采样数据pT1,pT2,pT3,…,pTn计算w,c,r如下:

式中,Ddist(pij,c)为点pij与微簇中心c的欧氏距离,μ为微簇权重门限,ε为核微簇密度门限。

由于数据流的性质不断改变,已形成微簇以及离群微簇的结构随时间在发生变化,新簇可能出现,离群微簇也可能形成新簇。Denstream聚类算法提出2种新结构,潜在微簇与离群微簇。

定义2 (潜在(离线)微簇)表示为(wp,CF1,CF2)。 为潜在微簇权重,其中wp>βμβ 用于判断一个微簇是潜在微簇还是离群微簇。 为采样数据权重的线性加权和。 为采样数据的平方加权和。潜在微簇中心为 ,核半径为r=

因雷达采样信息是多维数据,在Denstream聚类的过程中类距离Ddist(pij,c)采用一种扩展权重的多维欧式距离(SWED)[10]。公式如下:

本文通过Renyi熵判别聚类是否输出,其中点迹聚类划分愈合理,数据属于某一类越确定,目标信息所聚类的Renyi熵[11, 12]越小。当类内Renyi熵达到门限κ,聚类输出,否则继续聚类。数据集C的Renyi熵计算如下:

式中:h为窗宽或平滑系数,Nk为类C内点数量。

算法1 自适应Denstream聚类航迹起始算法

输入:数据集DSt

输出:聚类cp

For(t时刻数据集DSt中点p)

      计算点p合并入潜在微簇cp,离去微簇co的核半径rp

      ifrp<ε

        合并p进入cp

Elseif ro<ε

          合并p进入co

          if ωp>βμ

            将co转变为cp

          End

Else

      创造一个新的co

          End

End

For(每一个cp)

      计算类内信息熵V

      if V>κ

          输出聚类cp

      End

End

2.2 交互多模型核预估算法

Denstream聚类算法需对全局搜索,计算量较大。本文运用交互式多模型[13, 14, 15]对所得潜在聚类的核位置进行预估,缩小聚类搜索范围,减少系统运行时间。交互式模型核预估算法实质是由前一时刻每个模型的核输出加权组合作为各个模型的当前输入,多个模型并行估计聚类核位置,最后得到组合状态估计,交互模型分别采用常加速模型 与协同转弯模型 。两模型交互式核估计器主要由以下4个步骤组成:

1)模型交互输入;

k时刻模型j的初始条件可通过交互k-1时刻的各个模型滤波得到,即

式中: 表示模型的交互概率,上式中协方差为下式所示:

2)双模型并行滤波;

依据卡尔曼滤波的步骤,通过步骤1)求出模型初始条件 ,Pj0(k-1),可计算出第j个模型的状态估计 和协方差阵Pj(k),即可求出模型似然函数:

式中,vj(k),Sj(k)为模型j的滤波残差与相应的协方差;式vj(k)=Z(k)-Hj(k)j(k);Sj(k)=Hj(k)Pj(k)Hj(k)′+R(k)

3)模型概率更新;

式中,σ为归一化系数,可以通过下式计算:

4)状态估计与协方差组合

k+1时刻滤波器对核状态预测以及k时刻滤波器对核状态的最终估计以及其协方差阵可通过(11)~(13)式计算:

算法2 CEDenstream航迹起始算法

if (cp数量>0)且(t>2)

    For(每一个cp)

    运用交互多模型预估ci,t的位置,计算第i个环形波门范围,找到数据集DSi,t,运用算法1

End

Else

        取全集DSall

End

if (t>2)且(cot时刻无合并点)

    Delete co

End

3 多假设跟踪算法

多假设跟踪算法[17, 18]中量测值来源于目标,虚假目标等多种情况,构造假设树并利用贝叶斯后验概率的传递性,分别对各个假设分支进行概率计算,删除概率较小航迹,实现多目标中数据关联。

根据量测以及各个航迹之间的关系生成关联矩阵如下所示:

式中:ωji为二进制变量,ωjt=1表示量测j,(j=1,2,…,mk)落入目标i,(i=0,1,2,…T)的确认波门内。通过关联矩阵产生假设矩阵并分别计算概率。 根据概率的大小运用N-scan剪枝[17]合并处理。

4 基于CE-Denstream多目标跟踪算法

基于交互式多模型核预估数据流聚类的多目标跟踪算法主要步骤如下所示:

1)程序初始化:设定CE-Denstream数据流聚类算法参数(β,μ,κ),令第1帧的所有m个点p01,p02,p03,…,p0m为离群微簇,其离群微簇中心为c01,c02,c03,…,c0m

2)接收数据:接收t时刻的数据集DSt并根据预估出的核位置获得当前聚类的范围。

3)CE-Denstream聚类:运用数据流聚类算法将DSt中的数据pT1,pT2,pT3,…,pTnt-1时刻的微簇集合Ψt-1中的微簇进行合并,得到t时刻的微簇集Ψt,并运用交互多模型算法预估核位置。

4)计算类内信息熵:计算微簇集Ψt中潜在核微簇cp1,cp2,cp3,…,cpk的类内信息熵Vp1,Vp2,Vp3,…,Vpk,若Vpi≤κ则令聚类结果输出,并按时标提取潜在航迹集Ψi。(若Vpi,转到2)。

5)多假设跟踪算法:运用多假设算法对Ψi中的航迹进行跟踪,MHT算法选取3帧剪枝的方式进行删除航迹,并在每一时刻运用扩展卡尔曼滤波算法进行滤波。

6)输出结果:当接收到航迹输出信号后,选取概率和最大的航迹输出。

5 仿真实验 5.1 聚类质量评价

为了对数据流聚类品质进行评估[8, 9]。通过所得微簇的平均品质来进行判别,计算判别式表示如下:

式中:K为聚类数目,|Cdi|为类i中具有该簇最主要类标号的数据点的数目,|Ci|为类i中包含的所有数据点的个数。运用同一数据集对CE-Denstream聚类算法和Denstream聚类算法在不同杂波密度下的聚类效果进行仿真。为了使结果更准确,算法各执行5次并计算平均聚类纯度作为结果值,仿真结果如图 1所示:

图 1 不同杂波密度下聚类纯度比较

图 1中,低杂波密度时,CE-Denstream聚类算法的聚类效果与Denstream聚类算法基本相同,在杂波密度较高时,CE-Denstream聚类算法聚类纯度明显高于Denstream聚类算法。在不同杂波密度下,CE-Denstream聚类算法纯度均保持90%以上。说明本文聚类算法优越性。2种聚类算法平均单步相对运行时间在不同杂波密度下的比较如表 1所示。

表 1 不同杂波密度下的运行时间比较
杂波密度 运行时间
CE -Denstream Denstream
λ=5 1 0.931
λ=10 1.052 1.085
λ=15 1.091 1.773
λ=20 1.101 1.936

表 1中,以CE-Denstream聚类算法在杂波密度为5时刻的单步运行时间作为基准1,随杂波密度增大,算法运行有效时间不断增加。

结果显示,Denstream聚类算法的单步运行时长在高密度时明显大于CE_Denstream聚类算法的单步运行时长。

5.2 CE-DMTT算法实验

为了验证本文所提多目标跟踪算法的有效性,仿真环境设置如下:

设杂波服从泊松分布,λ为10;测距误差为100 m,雷达扫描概率为0.97;扫描周期为1 s;假设在二维平面内有2个匀速直线运动的目标交叉飞行;目标T1的起始位置/m为(1 000,9 000),速度/(m·s-1)(300,-200);目标T2的起始位置/m为(1 000,1 000),速度/(m·s-1)为(200,300);采样时间为35 s。CE-Denstream参数β为0.2,μ为20,κ为0.5。目标运动轨迹如图 2所示。

图 2 目标运动的轨迹图

CE-DMTT平均单步相对运行时间在不同杂波密度下的运行时间比较如表 2所示。

表 2 不同杂波密度下的运行时间比较
杂波密度 运行时间
FJPDA CE -DMTT
λ=5 1.351 1
λ=10 1.377 1.038
λ=15 1.460 1.174

表 2给出的是相对时间,令CE-DMTT算法在λ为5情况下下运行时间标准化,设为单位“1”。

表 2中,随杂波密度不断增加,2种算法的单步运行时间也随之增加。同一杂波密度时,CE-DMTT下相比于FJPDA在目标跟踪的过程中仿真速度有明显提高。

根据本文仿真设定条件选取λ为10对程序进行100次蒙特卡罗实验,仿真将FJPDA与CE-DMTT进行比对,图 3为2种算法对于目标1和目标2在 xy方向上的均方根误差比。

图 3 FJPDA与CE-DMTT在x,y方向上的均方根误差图

图 3中可知,在相同杂波密度的情况下CE-DMTT在跟踪精度上高于FJPDA。

6 结 论

针对传统算法在多目标跟踪的初始阶段计算量大,耗时,易受杂波影响,无法满足工程应用中实时性等问题,提出一种改进的多目标跟踪算法。在跟踪起始阶段对雷达获得的数据流进行聚类,并对类核位置进行预估,缩小搜索范围,通过计算各类内信息熵,提取可输出聚类,获得潜在航迹,运用多假设算法对潜在航迹进行多目标追踪。仿真结果表明本算法在有效提高跟踪目标精度的同时,可以大大减少计算量、提高实时性。算法具有很好的工程应用价值。

参考文献
[1] Amini A, Wah T Y, Saboohi H. On Density-Based Data Streams Clustering Algorithms: A Survey[J]. Journal of Computer Science and Technology, 2014, 29(1): 116-141
Click to display the text
[2] Khan K, Rehman S U, Aziz K, et al. DBSCAN: Past, Present and Future[C]//5th International Conference on Applications of Rigital Information and Web Technologies, 2014: 232-238
Click to display the text
[3] Kirubarajan T, Barshalom Y. Probabilistic Data Association Techniques for Target Tracking in Clutter[J]. Proceedings of the IEEE, 2004, 92(3): 536-557
Click to display the text
[4] Musicki D, Evans R. Joint integrated Probabilistic Data Association: JIPDA[J]. IEEE Trans on Aerospace and Electronic Systems, 2004, 40(3): 1093-1099
Click to display the text
[5] Blackrnan S, House A. Design and Analysis of Modern Tracking Systems[M]. Boston, MA: Artech House, 1999
[6] He J Y, Yan Y J, Meng Q. Multiple Arrays Multiple Targets Data Fusion and Tracking Based on TDOA Measurement Using FCM-JPDA Algorithm[C]//2002 6th International Conference on Signal Processing, 2002: 1612-1616
Click to display the text
[7] Ntoutsi I, Zimek A, Palpanas T, et al. Density-Based Projected Clustering over High Dimensional Data Streams[C]//12th SIAM International Conference on Data Mining, 2012: 987-998
Click to display the text
[8] Cao F, Ester M, Qian W, et al. Density-Based Clustering over an Evolving Data Stream with Noise[C]//6th SIAM International Conference on Data Mining, 2006: 326-337
Click to display the text
[9] Ruiz C, Menasalvas E, and Spiliopoulou M. C-Denstream: Using Domain Knowledge on a Data Stream[C]//Discovery Science. Springer Berlin Heidelberg, 2009: 287-301
Click to display the text
[10] Deza M M, Deza E. Encyclopedia of Distances[M]. Springer, Berlin Heidelberg, 2009
[11] Lenzi E K, Mendes R S, da Silva L R. Statistical Mechanics Based on Renyi Entropy[J]. Physica A: Statistical Mechanics and Its Applications, 2000, 280(3): 337-345
Click to display the text
[12] Crutchfield J P, Young K. Inferring Statistical Complexity[J]. Physical Review Letters, 1989, 63(2): 105
Click to display the text
[13] Fu X, Jia Y, Du J, et al. New Interacting Multiple Model Algorithms for the Tracking of the Manoeuvring Target[J]. IET Control Theory & Applications, 2010, 4(10): 2184-2194
Click to display the text
[14] Foo P H, Ng G W. Combining the Interacting Multiple Model Method with Particle Filters for Manoeuvring Target Tracking[J]. IET Radar, Sonar & Navigation, 2011, 5(3): 234-255
Click to display the text
[15] Johnston L A, Krishnamurthy V. An Improvement to the Interacting Multiple Model (IMM) Algorithm[J]. IEEE Trans on Signal Processing, 2001, 49(12): 2909-2923
Click to display the text
[16] Blackman S S. Multiple Hypothesis Tracking for Multiple Targets Tracking[J]. Aerospace and Electronic Systems Magazine of IEEE, 2004, 19(1): 5-18
Click to display the text
[17] Muthumanikandan P, Vasuhi S, Vaidehi V. Multiple Maneuvering Target Tracking Using MHT and Nonlinear Non-Gaussian Kalman Filter[C]//International Conference on Signal Prosessing Communications and Netuorkiy, 2008: 52-56
An Algorithm of Multi-Target Tracking Based on Clustering Data Stream
Ma Tianli, Wang Xinmin, Cao Yuyan, Huang Yu, Mu Lingxia     
Department of Automatic Control, Northwestern Polytechnical University, Xi'an 710072, China
Abstract: In order to deal with the clutter problem in the initial stage of traditional multi-target tracking,a data stream clustering mulitiple target algorithm based on Interactive Multi-Model core estimation(CE_DMTT) is proposed.Through estimating core position based on the Interactive Multi-Model to reduce the searching range of the cluster,the datastream is online clustering。In order to obtain potential track, the Renyi Entropy is introduced to adaptivly extract the cluster.Based on the obtained potential track, we use Multiple Hypotheses Tracking algorithm to implement real-time tracking.Simulation results and their analysis show preliminarily that the proposed algorithm can effectively reduce the computational complexity and improve System Real-time Performance.
Key words: clustering algorithms     computational complexity     computer simulation     matrix algebra     covariance matrix     Gaussian noise(eletronic)     efficiency     entropy     estimation     mean square error     Monte Carlo methods     radar clutter     real time control     target tracking     vectors     data stream clustering     Interactive Multi-Model     Multiple Hypothesis Tracking,multi-target     Renyi entropy    
西北工业大学主办。
0

文章信息

马天力, 王新民, 曹宇燕, 黄誉, 穆凌霞
Ma Tianli, Wang Xinmin, Cao Yuyan, Huang Yu, Mu Lingxia
基于数据流聚类的多目标跟踪算法
An Algorithm of Multi-Target Tracking Based on Clustering Data Stream
西北工业大学学报, 2015, 33(3): 506-511
Journal of Northwestern Polytechnical University, 2015, 33(3): 506-511.

文章历史

收稿日期: 2014-11-04

相关文章

工作空间