基于坐标映射距离差分的快速群分割算法

2016-08-15王海鹏

系统工程与电子技术 2016年8期

关键词：分群图解法视场

王　聪, 王海鹏, 何　友

(1. 海军航空工程学院信息融合技术研究所, 山东烟台 264001;2.飞行器测控与通信教育部重点实验室, 重庆 400044)

基于坐标映射距离差分的快速群分割算法

王聪1,2, 王海鹏1, 何友1

(1. 海军航空工程学院信息融合技术研究所, 山东烟台 264001;2.飞行器测控与通信教育部重点实验室, 重庆 400044)

群分割技术作为群目标跟踪技术的首要环节,其处理结果直接影响后续整个数据处理过程的效果。在深入研究目前已有的群分割技术的基础上,提出了一种基于坐标映射距离差分的快速群分割算法。首先将量测集的二维信息分解为两组坐标映射距离的一维信息,进而分别进行排序和分群处理,从而减小了算法的时间复杂度,最后将分别获得的两组预备群进行取交关联,得到最终的分割群。通过与3种传统算法在时间复杂度上的理论分析与比较,该方法在大视场回波稀疏条件下具有显著的效率优势。经过多场景的仿真分析表明,该算法的处理效能显著高于传统算法,且对复杂动态场景具有较好的鲁棒性。

群分割技术; 群目标跟踪; 坐标映射; 距离差分; 时间复杂度

0　引　言

随着飞行器技术水平的不断提高,低空飞行的飞机编队、多发齐射的低空飞行导弹成为现代战争越来越普遍使用的常规化战术。在杂波环境下,对该类运动方式相似、空间距离相近的目标进行精确跟踪成为当前目标跟踪领域的一个新的热门问题——群目标跟踪技术[1-4]。该技术可主要分为3部分:群的起始、群航迹的维持、群的撤销。其中,如何准确的起始一个群,是群目标跟踪首先需要解决的问题。

在群目标的起始技术中,又分为群的分割与互联两个技术环节。其中群分割技术作为后续算法的数据基础,是整个航迹跟踪过程需要最先解决的问题。本文主要针对群分割技术进行了研究。

在现有的研究中,文献[5-6]提出了一种最直观的基于回波之间距离的分群方法。该方法从群定义的角度出发,实现根据量测点距离进行划分,并且遍历所有量测点间的距离,因此该方法虽然处理结果比较稳定可靠,但计算复杂度太大,不适合工程应用。文献[7-9]对上述距离分割法进行了一定的改进,提出了基于循环阈值的分割方法。该方法根据已划分量测进行外推,一定程度上减少了不必要的距离计算,因此可取得与基于目标距离方法相同的分割效果,并在一定程度上降低了计算复杂度。文献[10]基于图论的思想,将整个探测区域进行分割以能够一次性确定多个群。该方法虽然直观方便,但对于不同杂波条件以及选取的单位小区域面积不恰当时,会造成额外的计算量以及出现多个虚假群。

本文在借鉴上述算法的基础上,并结合工程实际情况,提出了基于坐标映射距离差分的群分割方法。该方法可对观测点进行有效的群分割,并显著降低了计算复杂度,特别在雷达视场较大且回波稀疏等常见战场情况下效果明显,可有效缩短处理时间,能适应工程应用要求。

1　问题提出

在进行群的分割之前,首要要对群进行定义。理论上,群被定义[11]为满足以下3个条件的多目标:

(1)运动方向一致;

(2)速度基本相同;

(3)群中各目标之间的空间距离远小于各群之间的距离。

根据上述对群的定义,假设Z(k)为传感器在k时刻获得的所有量测集,且

(1)

式中,mk为k时刻的量测个数。

(2)

若

(3)

则量测zi(k)与zj(k)属于同一个群。这里d0为群内目标的稠密程度值,其取值取决于传感器系统的群目标目的。

传统的基于空间距离的分割方法直接遍历计算k时刻量测集Z(k)中任意两个点的空间距离d[zi(k),zj(k)],最终可分为m个群,记为{U1,U2,…,Um}。

2　本文算法

2.1坐标映射距离

图1　坐标映射距离示意图

2.2群分割方法

在获得了所有量测点的坐标轴映射距离后,这里对两个轴分别进行分群。以x轴为例,首先将所有量测点的x轴映射距离升序排列,即

(4)

进而将该序列进行差分运算(后项减前项),即获得一个表示相邻两点之间距离的序列

(5)

(6)

根据群的定义,通常情况下由于各个群之间距离较远,但在某些情况下,各个群之间的距离相对较近,会出现单独一个坐标轴分群出现错误的情况,如图2所示。此时,需要对两组预备群进行取交关联:

(7)

通过将所有预备群进行关联,可以将各个群Uk的空间范围确定在一个矩形区域内,由于各群之间距离远大于群内目标之间距离,因此确定的群具有唯一性。

2.3算法流程

综上所述,基于坐标映射距离差分的快速群分割算法的总体流程如图3所示。从图3中可以看出,该算法结构简单易行,易于工程实现。

图2　群分割示意图

图3　算法流程图

2.4时间复杂度分析

时间复杂度[12-16]是衡量一个算法性能优劣的重要指标。在理论上,算法运行所耗费的时间并不能计算出来,必须上机测试,但仍可通过理论分析执行算法所需要的计算工作量,来比较衡量各个算法。因此本节将距离分割法、循环阈值法、图解法与本文提出的基于坐标映射距离差分的群分割算法进行理论分析与比较,为后续仿真提供理论依据。这里,假设在单传感器条件下,某时刻回波个数为n。

距离分割法的计算量主要集中在遍历所有回波点两两之间的距离,因此T1(n)=Ο(n2)。

图解法的计算量不仅取决于传感器探测范围内的回波个数,还与探测区域被分割成的个数l2有关。该方法第一步将回波划归小区域时,时间复杂度为Ο(nl),第二步更新小区域比重时,复杂度为Ο(l2),则T3=Ο(nl)+Ο(l2)。由此可以看出,当l≫n时,T3≈Ο(l2);当l与n相当量级时,T3≈Ο(n2)。因此,当l≫n时,即视场内的雷达回波较为稀疏条件下,该算法的时间复杂度由视场分割数l2决定。

通过对上述4种算法的时间复杂度的理论分析,可得如表1所示时间复杂度对比图。从表1可以看出,在最好情况下,循环阈值法的时间复杂度最低;最差情况下,当l≫n时,图解法的时间复杂度最高;平均条件下,本文算法的时间复杂度最低,理论上效率最高。

表1　算法时间复杂度对比

3　仿真验证与分析

为了全面展示算法性能,本节模拟了两种战场常见的雷达量测场景与一种模拟工程应用的复杂场景:小视场环境、大视场稀疏回波环境[20]、群分裂与群合并情景下的分群。由于群分割技术主要侧重算法耗时与正确分群率(完全准确的将属于一个群的量测点标记为一个群),因此仿真结果采用这两个指标做衡量标准。

场景 1常见的小视场环境仿真参数如表2所示。

表2　场景1仿真参数

在上述仿真情况下,由于有杂波存在,即在雷达扫描区域内有单个点的存在,该类点既有可能是单个目标的航迹点,也有可能是随机杂波,但在本文仿真中,只划分“群目标”与“非群目标”,因此在数据处理过程中将该类点标记为“非群目标”,以备后续点航关联使用。仿真场景如图4所示(杂波为随机的)。

仿真实验结果如表3所示。

通过表3可以看出,在处理的正确率上,本文算法跟经典距离分割法及循环阈值法处理水平相当,显著高于图解法。在算法效率上,本文算法的处理耗时显著低于其他3种算法,与经典的距离分割法相比,处理效率几乎要高出一个量级;与循环阈值法及图解法相比,耗时减少一半。通过在这两项指标上的仿真实验结果可以看出,本文提出的算法与目前常用的算法相比,可以获得相似或者更高的处理准确率,且处理耗时更短,具有更高效的处理效率。

图4　场景1示意图

算法耗时/s正确分群率/%距离分割法10.625100循环阈值法5.326100图解法3.01294.5本文算法2.41499.5

场景 2大视场稀疏回波环境仿真参数如表4所示。

表4　场景2仿真参数

在该场景中,视场范围较大,回波总数较为稀疏,符合许多传感器真实应用条件下的探测态势。仿真场景如图5所示。图中3个小图为3个目标群的放大示意图。

仿真结果如表5所示。

在场景2的条件下,应用图解法对整个视场环境进行划分显然比较浪费资源,因为该方法的虚拟网格中大部分的位置都是空闲的,但却需要遍历这些网格。如表5所示,图解法的运行时间远远高于其他3种算法,这说明在该场景条件下,不适宜应用图解法进行分群处理。比较本文算法与另外两种经典分群算法,三者的分群正确率相同,而本文算法的处理时间显著低于其他二者,这说明本文在该场景下的整体效率显著优于传统算法。

图5　场景2示意图

算法耗时/s正确分群率/%距离分割法8.45999.5循环阈值法3.86499.5图解法28.47197.5本文算法1.96399.0

纵观两个场景的仿真结果,距离分割法与循环阈值法的处理正确率较为稳定,这主要也源于其算法思路是对群定义的直接实现,但算法的耗时取决于当前时刻的传感器回波个数,不适用于多目标及多杂波情况。图解法在小视场条件的表现较优,耗时较短,但在大视场条件的耗时显著增大,因此其应用条件较苛刻,不适合实际应用需求。本文提出的算法在两种仿真条件下的分群正确率较稳定,且耗时均为最小,在大视场稀疏回波条件下的效果尤为突出。因此,本文提出的算法可应用于所有真实战场环境,对后续的群跟踪数据处理环节提供更准确高效的分群结果。

另外,本文仿真的大视场与小视场环境并不是绝对的,二者在某些情况下是可以互相转化的。如当场景2中的传感器由于某些原因导致回波数增多,达到n与l相当量级时,既转化为了场景1。在工程应用中需要分群算法能够在场景多变的条件下也具有较好的适应性与兼容性。而本文提出的算法在这两种场景中均表现优异,可适应复杂多变的实际应用场景,多场景兼容性优异,因此具有宽广的工程应用前景。

场景 3群分裂与合并情景下的环境仿真:设在雷达视场x～[-1.6e4-0.4e4]、y～[0.6e42.2e4]内存在两个匀速直线运动的编队,其中群1存在5个成员、群2存在2个成员。群1中的2个成员机动运动逐渐与群1分离,随后慢慢合并到群2中。各个目标的初始运动状态如表6所示,表中G1-1表群1的第一个目标,以此类推。其中G12-1则表示开始在群1中,后来在群2中的目标。G12-1与G12-2这两个目标的加速度为[5 m/s2-10 m/s2]。杂波的生成为在矩形雷达视场的内,每个时刻产生均匀分布的20个杂波。

雷达位于坐标原点(0,0),测向误差σθ=0.2°、测距误差σρ=20 m。

表6　场景3目标初始运动参数

在该场景中,既存在群的分离,也存在群的合并,同时还存在一定密度的杂波,因此场景较为复杂,前60个时刻的量测点,分布如图6所示。群1从图中的右下至左上运动,群2从中部顶端运动至左下。显然,群1中的两个目标脱离了群1,经过机动拐弯后合并到群2中。

图6　场景3量测分布图

在群的分裂与合并时,为了后续处理过程(例如互联、滤波等)具有良好的数据保障,要求分群算法对目标的量测具有较高的划分准确性,即当群发生分裂时,能较早的将成员划分为不同的群。图7为在群分裂与合并相关时刻的目标量测分布图,为了清晰显示目标量测,这里已删去杂波。如图7(a)所示,在13时刻,群1已分为两个群,但这两群之间仍处于分群的临界距离,因此,判断群分裂的时刻越靠近13时刻,越有利于后续的态势处理。同理,如图7(b)所示,在48时刻时,两群已合并为一个群,因此,在此时刻左右需要更准确的分群能力。因此,为了对比算法对动态运动场景的鲁棒性,这里通过对准确分群的判决时刻,来对比各算法的表现。

通过1 000次蒙特卡罗仿真,各算法在12～17时刻对群分裂的判决次数曲线如图8所示;在45～50时刻对群合并的判决次数如图9所示。群分裂与合并的平均判决时刻如表7所示。

图7　场景3群分裂与合并时刻量测放大图

图8　群分裂判决时刻分布曲线图

图9　群合并判决时刻分布曲线图

从图8中可以看出,本文算法与距离分割法和循环阈值法的曲线相近,具有相近的处理能力,均显著高于图解法。且主要判决时刻集中在13与14时刻,较接近真实条件。从图9中可以看出,4种算法的判决时刻主要集中在47与48时刻,但本文算法在48时刻的判决次数高于其他算法。从表7可以看出,无论在群分裂还是合并的情况,本文算法在平均判决时刻均更接近13与48时刻,因此,本文算法在动态场景下的算法效能最高。

表7　群分裂与合并的平均判决时刻

造成上述结果的原因是:图解法的算法思路决定了其对量测点精细距离判断的模糊性,因此在需要精细判决的条件下表现最差。而本文算法与距离分割法和循环阈值法均基于点与点之间的距离进行分割,因此较为精确。本文算法思路将二维信息转化为两个一维信息分别处理,因此对量测点之间的距离更敏感。从该场景仿真结果可以看出,本文算法在动态复杂条件(群的分裂与合并)下,表现出了比3种经典算法更准确更稳定的分群效能,对动态场景具有较好的鲁棒性。

4　结　论

本文所提出的基于坐标映射距离差分的快速群分割算法在理论上减小了算法的时间复杂度,改进传统算法在实时性上的不足。并通过3个常见战场环境进行仿真验证。该算法能够在保证分群正确率的同时有效缩减运行时间,提高算法整体效能。在动态场景群的分裂与合并条件下仍保持较高的分群准确率,对各种场景均具有较好的鲁棒性。该算法结构简单,时效性显著,鲁棒性好,可在工程实践中广泛应用。本文下一步工作是基于算法容错性继续对本文的分群算法进行研究,从而为算法的优化奠定基础。

[1] Jian L, Li X R. Tracking of maneuvering non-ellipsoidal extended object or target group using random matrix[J].IEEETrans.onSignalProcessing, 2014, 62(9):2450-2463.

[2] Feldmann M, Franken D, Koch W. Tracking of extended objects and group targets using random matrices[J].IEEETrans.onSignalProcessing, 2011, 59(4):1409-1420.

[3] Hyondong O, Seungkeun K, Hyo S S, et al. Coordinated standoff tracking of moving target groups using multiple UAVs[J].IEEETrans.onAerospaceandElectronicSystems,2015,51(2):1501-1514.

[4] Ziho K, Landry S J. An eye movement analysis algorithm for a multielement target tracking task: maximum transition-based agglomerative hierarchical clustering[J].IEEETrans.onHuman-MachineSystems, 2015, 45(1):13-24.

[5] Bar S Y. Extension of the probabilistic data association filter in multi-target tracking[C]∥Proc.ofthe5thSymposiumonNonlinearEstatimation, 1974: 16-21.

[6] Geng W D. Summarizing of group-target tracking[C]∥Proc.ofthe10thChinaRadarConference,2008:367-371.(耿文东.编队目标跟踪综述[C]∥第十届全国雷达学术年会,2008:367-371.)

[7] Wang H P, Xiong W, He Y, et al. Gray refined track initiation algorithm for centralized multi-sensor group targets[J].SystemsEngineeringandElectronics,2012,34(11):2249-2255.(王海鹏,熊伟,何友,等.集中式多传感器群目标灰色精细航迹起始算法[J].系统工程与电子技术,2012,34(11):2249-2255.)

[8] He Y, Wang H P, Xiong W,et al.Gray refined track initiation algorithm of group targets based on relative position vector[J].ActaAeronauticaetAstronauticaSinica,2012,33(10):1850-1863.(何友,王海鹏,熊伟,等.基于相对位置矢量的群目标灰色精细航迹起始算法[J].航空学报,2012,33(10):1850-1863.)

[9] Xing F Y, Xiong W, Wang H P. A formation target track initiation algorithm based on clustering and hough transform[J].JournalofNavalAeronauticalandAstronauticalUniversity, 2010, 25(6):624-629.(邢凤勇,熊伟,王海鹏.基于聚类和Hough变换的多编队航迹起始算法[J].海军航空工程学院学报,2010,25(6):624-629.)

[10] He Y, Xiu J J, Zhang J W.Radardataprocessingwithapplications[M]. 2nd ed. Beijing: Publishing House of Electronics Industry Press, 2011:170-178.(何友,修建娟,张晶炜.雷达数据处理及应用[M].2版.北京:电子工业出版社,2011:170-178.)

[11] Wang H P. Study of multi-sensor group targets tracking algorithm[D]. Yantai: Naval Aeronautical and Astronautical University, 2012. (王海鹏. 多传感器编队目标跟踪算法研究[D]. 烟台: 海军航空工程学院, 2012.)

[12] Pietro S O, Carsten Witt. Improved time complexity analysis of the simple genetic algorithm[J].TheoreticalComputerScience, 2015, 605(9):21-41.

[13] Jia D, Zhang X. Research on time complexity measure method based on analysis method[J].JournalofLiaoningUniversityofTechnology(NaturalScienceEdition), 2015, 35(4):231-240.(贾丹,张兴.基于分析法的算法时间复杂度的度量方法研究[J].辽宁工业大学学报(自然科学版),2015,35(4):231-240.)

[14] Xia J, Shang P, Wang J, et al. Permutation and weighted-permutation entropy analysis for the complexity of nonlinear time series[J].CommunicationsinNonlinearScienceandNumericalSimulation, 2016, 31(1):60-68.

[15] Hu J, Chen L Y, Zeng L M, et al. Performance testing based on time complexity analysis for embedded[C]∥Proc.oftheInternationalConferenceonEmbeddedSoftwareandSystems, 2008:243-247.

[16] Pakhira M K. A linear time-complexityk-means algorithm using cluster shifting[C]∥Proc.ofthe6thInternationalConferenceonComputationalIntelligenceandCommunicationNetworks, 2014:1047-1051.

[17] Dong F G, Fan H, Yuan D. A novel image median filtering algorithm based on incomplete quick sort algorithm[J].InternationalJournalofDigitalContentTechnologyandItsApplications, 2010, 4(6):244-256.

[18] Wang X. Analysis of the time complexity of quick sort algorithm[C]∥Proc.ofthe4thInternationalConferenceonInformationManagement,InnovationManagementandIndustrialEngineering, 2011:408-410.

[19] Hu F, Wang G Y, Feng L. Fast knowledge reduction algorithms based on quick sort[C]∥Proc.ofthe3thInternationalTechnologyinComputerScience,RoughSetsandKnowledgeTechnology, 2008:72-79.

[20] Zhu F, Zhang Q, Hong W, et al. Sparse imaging method with strip-map random noise radar based on compressive sensing[J].SystemsEngineeringandElectronics, 2012, 34(1):56-63. (朱丰, 张群, 洪文, 等. 基于压缩感知的条带随机噪声雷达稀疏成像方法[J].系统工程与电子技术, 2012, 34(1):56-63.)

Fast algorithm of group segmentation based on coordinates transformations and distance differentiations

WANG Cong1,2, WANG Hai-peng1, HE You1

(1. Naval Aeronautical and Astronautical University, Institute of Information Fusion, Yantai 264001, China;2. Key Lab for Spacecraft TT&C and Communication under the Ministry of Education, Chongqing 400044, China)

As a primary technology of group targets tracking, the result of group segmentation is the key to the outcome of the entire data processing progress. Based on the state-of-art researches, a fast algorithm of group segmentation based on coordinates transformations and distance differentiations is proposed. Firstly, the two-dimension information of acquired sets is decomposed into two one-dimensional information of coordinate distance. Then, the sets are sorted and segmented, which make time complexity reduced. Finally, the final segmentation group is obtained by extracting the intersection of two under-processed groups. Compared to three traditional methods in theory analysis of time complexity, the proposed method is more effective especially under the condition of large field of vision with sparse radar echoes. The simulation results of multi-scences show that, the proposed algorithm is much more efficient than the traditional methods, and has excellent robustness to dynamic scenes.

technology of group segmentation;group targets tracking;coordinates transformations;distance differentiations; time complexity

2016-01-21；

2016-04-28；网络优先出版日期：2016-06-07。

飞行器测控与通信教育部重点实验室开放基金(CTTC-FX201302)资助课题

TP 953

10.3969/j.issn.1001-506X.2016.08.02

王聪(1987-),男,讲师,博士,主要研究方向为群目标跟踪、航迹关联。

E-mail:congnavy@hotmail.com

王海鹏(1985-),男,讲师,博士,主要研究方向为群目标跟踪、航迹关联。

E-mail:armystudent@sohu.com

何友(1956-),男,中国工程院院士,教授,主要研究方向为雷达信号处理、信息融合。

E-mail:heyoumail@sohu.com