模糊数据关联算法在多目标跟踪中的应用.pdf

数据关联是多传感器目标跟踪融合系统中至关重要的一部分。基于目标函数的模糊聚类算法通过将聚类分析问题转化成带约束条件的优化问题，求出量测与航迹的隶属度矩阵。通过隶属度矩阵，可以获取量测和目标航迹的关联关系，极大地减少了量测和航迹的关联次数。关键词：数据关联；多目标跟踪；模糊聚类中图分类号：TP301.6文献标识码：AApplication of Fuzzy Data Association Algorithm on Multitarget TrackingCAI Yu-bao,DU Hui-ying,HU Zheng-zheng,MA Liu-yang(The 27th Research Institute of China Electronics TechnologyGroup Corporation,Zhengzhou 450047,China)Abstract:Data association is a main component of tracking in multisensory data fusion systems.The fuzzy clus-tering algorithm that based on the objective function transforms the clustering problem into an optimization withconstrains.Through the solution of the optimization,obtaining the membership matrix of the measurements tothe tracks,which reflect the membership between measurements and tracks.Also,the fuzzy clustering algorithmgreatly reduces the number of correlations.Key words:Data Association,Multitarget Tracking,Fuzzy Clustering1引言数据关联是多目标跟踪算法中至关重要的一部分，它决定了更新目标航迹数据所采用的量测值。数据关联技术在民事和军事应用中得到广泛的研究和应用，比如机器人、模式识别、图形处理等。目标跟踪系统的主要目标是航迹估计和预测。目前，数据关联问题比较简单的求解办法是：SNF（St r o n g e s t Ne i g h b o r Fi l t e r）和 NNF（Ne a r e s t-Neighbor Filter)算法 。在这些算法中，一个量测数据最多用于更新一个指定的目标航迹。SNF和NNF在低噪声和非机动目标运行中能够取得较好的表现，但是随着目标噪声的增加，它们的关联成功率就会急剧降低。在理想的模型假设条件下，MHT（M u l t i p l e H y-pothesis Tracker)算法是多目标跟踪的最优求解算法。但是它的计算复杂性限制了该算法在实际工程中的应用 2 。针对此问题，许多学者提出的算法是通过牺牲最优的表现来达到计算可行性。Bar-shalom 和 Fortman 提出 PDA(Probabilistic DataAssociation）和 JPDA（Jo i n t Pr o b a b i li s t i c D a t a A s s o-ciation)来进行多目标的数据关联 3。JPDA和PDA算法都是通过计算量测-航迹的关联概率来进行目标的关联，另一类次最优的目标关联算法是基于神经网络 4 和模糊逻辑技术 5-7 的关联算法。这些技术能够为多目标关联问题提供近似最优解。神经网络技术的最大缺点是需要大量的数据集和训练。模糊逻辑数据关联的准确性依赖于隶属度函数的选择、输入变量数目、逻辑变量数目及逻辑规则和语句的准确性 8 。并且，模糊逻辑数据关联的实现是非常复杂的，原因在于其需要大量的IF-作者简介：蔡玉宝（19 8 7 一），男，硕士研究生，高级工程师，毕业于郑州大学，研究方向：人工智能。第1期系电光统24THEN规则。模糊聚类算法（Fuzzy Clustering Means）是一种无监督的分类算法 1,9 ，通过目标信息的关联隶属度来确定信息的相关性，可以有效地处理相关判决过程中多源信息的模糊性。模糊聚类算法通过目标函数最小化求解，获取隶属度矩阵，然后通过隶属度矩阵进行量测与航迹的隶属度判断。因此，模糊聚类算法极大地降低了计算复杂性。2卡尔曼滤波概述假设Z,=1zk1,zk.2,zk,1表示传感器在k时刻对n，个目标侦测到的n个合理量测数据。目标的动态量测模型如下：x;(k+1)=F;x;(k)+u,(k)(1)z,(k)=H,(k)x(k)+w;(k)(2)这里，x（k）表示目标i在k时刻的n维状态向量；z.（k)是m维的量测向量;F,是nn维的状态转移矩阵;H,是mn维的量测矩阵;u（k）和w（k)是过程噪声和量测噪声，设它们是互不相关、均值为零,协方差为Q.（k)和R（k)的高斯白噪声在多目标跟踪系统中，系统接收到的量测数据个数通常会大于目标数目。假设由式（2）给定的n，个量测数据，将这些量测数据准确地与n，个目标关联起来是很困难的。在无噪声条件下，每个目标航迹的状态估计和更新可根据卡尔曼滤波算法进行确定。g(k+1lk)=F,e(klk)(3)P,(k+11k)=F,P(k)F)+Q.(k)(4)(k+11h+1)=(k+11k)+K,(k+1)z(k+1)(5)P,(k+1Ik+1)=I-K,(k+1)H,(k+1)P,(k+1Ik)(6)式中,K（k）是卡尔曼滤波增益；z（k+1)是残次。z(h+1)=z,(k+1)-H,(k+1)(k+11k)(7)3模糊C均值聚类针对二值数学理论在表现现实世界中模糊性问题所存在的不足，美国数学家Zadeh于19 6 5年发表Fuzzy Sets论文并建立了模糊数学理论 10 。Ruspinil将Zadeh模糊数学理论引人聚类分析，提出模糊划分的概念,将隶属度u;E0,1改进为u=0,1,隶属度u,可在区间 0,1 上连续取值，从而得到聚类目标函数J（U,V）=Eh.Z-(ua)di,uge0,1。1984年，Bezdek等人在求和公式中引人模糊控制参数，采用q次方加权，得到更一般化的模糊聚类算法J(U,V)=Z-.Z-（u a)d a,1,从而将FCM目标函数推广为无限簇函数集合，同时采用交替优化算法求解和估计聚类算法参数 12 。OFCM算法把聚类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。通过反复修改聚类中心V和分类矩阵U来实现动态的迭代聚类，使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。设待聚类的集合为x=1x1,X2,xn(8)其中每一个对象x,有个特性指标,设为x,=1xi1,x2,(9)现在将对象集x分为c类（2 cn）,设c个聚类中心向量构成的矩阵为V.1V12mV0212202mV=(10)VCcm为了获得一个最佳的模糊分类，可以按照如下聚类准则，从模糊分类空间中优选一个最好的模糊分类。聚类准则：求出适当的模糊分类矩阵U及聚类中心矩阵V，使目标函数J(U,V)=（u t）d(11)达到极小值,其中q可取一个定值。而d表示对象x与第i类聚类中心向量V的距离。一般来说,求解上式给出的目标函数J(U,V)是相当困难的，通常待用迭代运算求出近似解。1977年,J.C.Bezdek证明了当q1,xV时，可以通过FCM算法进行迭代运算，而且运算过程是收敛的。具体步骤如下。类中心矩阵阵U(),逐步迭代,l=1,2，。对于U(),计算聚选定分类数c（2 c n）,取初始模糊分类矩总第18 3期25蔡玉宝，等：模糊数据关联算法在多目标跟踪中的应用（1）求最佳模糊分类矩阵和最佳聚类中心矩阵v()=(v,V,V(12)式中,V()=Zi-(u)*修正模糊分类矩阵U(），取2/(q-1)-1(1+1)ik比较U()和U(I+1),若对取定的精度0,有max iWik(1+1)山ik18(13)则U(1+1)和V即为所求，停止迭代；否则，l=+1回到第一步，重复进行。(2)模糊聚类根据求出满足要求的最佳模糊分类矩阵和最佳聚类中心矩阵之后，利用最佳模糊分类矩阵进行分类。假设求得的最佳模糊分类矩阵为W11W12*W21W22W2nU*(14)二WlW2*u*cnVxEx,在U*的第k列中,如果Wik=maxijc(ui*(15)则将对象归属于第i类，即对象对那一类的隶属度最大，就将它归到那一类。4FCM聚类算法流程根据上述步骤可知，基于目标函数的FCM聚类算法采用参数迭代流程，即首先初始化聚类中心或隶属度划分矩阵，然后利用迭代公式分别对聚类中心及隶属度划分矩阵进行更新，并通过比较前后参数的差异性是否满足迭代条件来决定是否跳出迭代过程。FCM算法的流程图如图1所示。开始初始化隶属度矩阵U计算机聚类中心C创建距离向量dis，计算每一个元素相距聚类中心的距离更新隶属度矩阵UU-U否是否满足停止条件是结束图1FCM聚类算法流程图5试验结果与分析本文针对6 组传感器、2 5批目标的仿真试验场景，其中目标运动模型为匀速直线运动及蛇形机动。(1）软硬件平台试验所需的软件平台和硬件平台要求如下。操作系统：Ubuntu20.04；CPU：i 9-119 0 0 K;内存:6 4 GB。（2）融合准确率在本文搭建的试验场景下，采用FCM聚类算法时，针对匀速直线运动目标，其融合准确率可达到10 0%，对蛇形机动目标，其融合准确率可达到90%以上。采用传统最邻近域算法，针对匀速直线运动目标，其融合准确率可达到9 3%，对蛇形机动目标，当目标重复个数增多时，其融合准确率下降到8 0%以下。试验结果如表1所示。第1期电系光26统表1融合准确率准确率（FCM聚类算法/目标运动模型目标重复个数最邻近域算法）匀速直线运动10100%/95%匀速直线运动15100%/93%蛇形机动1093%/85%蛇形机动1591%/76%(3)融合时间在本文搭建的试验场景下，采用FCM聚类算法时，其多目标融合耗时在0.3s以内。采用传统最邻近域算法,其多目标融合耗时在0.3s以上。试验结果如表2 所示表2融合耗时时间（FCM聚类算法/目标运动模型目标重复个数最邻近域算法）匀速直线运动100.25 s/0.33 s匀速直线运动150.28 s/0.35 s蛇形机动100.27 s/0.38 s蛇形机动150.30 s/0.41 s(4)结果分析本文搭建的试验场景，目标运动模型为匀速直线运动及蛇形机动，并在运动航迹数据中增加高斯噪声模型，尽量还原真实目标运动场景。经对比分析，在进行多目标融合时,FCM聚类算法整体上优于最邻近域算法。6结束语在实际的项目中应用，由于目标属性众多，如位置、速度、距离、航向等信息，如果单纯地使用某一属性，就会容易造成信息属性的缺失导致关联错误。而如果采用多属性关联，传统的算法如最邻近域、概率数据关联算法等，在关联过程中的计算量会很大，影响实际应用的时效性。模糊聚类算法在融合过程中，最后形成一个隶属度矩阵，根据隶属度矩阵对量测和航迹进行关联，极大地降低了计算复杂性。综上所述，基于模糊聚类的数据关联算法在多源目标信息融合的实际工程应用中具有更好的应用效果。参考文献1AZIZ A M,TUMMALA M,CRISTI R.Fuzzy logic datacorrelation approach in multisensor-multitarget trackingsystems J.Signal Processing,1999,76(5):195-209.2AZIZ A M.A new all-neighbor fuzzy association techniquefor multitarget tracking in a clustered environment C/Proceedings of the International Conference on Fuzzy Sys-tems,2009:1767-1772.3BAR-SHALOM Y,FORTMAN T E,Tracking and DataAssociation.NewYork:Academic Press,1988.4CHUNG Y N,CHOU P H,YANG M R.Multiple targettracking with competitive hopfield neural network baseddata association J.IEEE Transactions on Aerospaceand Electronic Systems,2007,43(3):1180-1188.5KUMMERT A.Fuzzy technology implemented in sonarsystems J.IEEE Journal of Oceanic Engineering,1993,18(4):483-490.6NANDAN R,SING H P,BAILEY W H.Fuzzy logic ap-plications to multisensory-multitarget correlation J.IEEE Transactions on Aerospace and Electronic Systems,1997,33(3):752-769.7CHEN Y M,HUANG H C,Fuzzy logic approach to mul-tisensory data association J.Mathematics and Comput-ers in Simulation,2000(52):399-412.8AZIZ A M.Fuzzy Track-to-Track association and track fu-sion approach in distributed multisensor-multitarget multi-ple-attribute environment J.Signal Processing,2007,87(6):1474-1492.9何金国，石青云一种新的聚类分析算法 J.中国图象图像学报，2 0 0 0，5（5）：40 140 5.1OZADEH L.Fuzzy setsJ.Information and Control,1965,8(3):338-353.11BERND F.Some competitive learning methods J.Ar-tificial Intelligence Institute,Dresden University of Tech-nology,1997.12BEZDEK JC,EHRLICH R,FULLW.FCM:the fuzzyC-means clustering algorithm J.Computer&Geo-scienc,1984,10(2-3):191-203.