1 引言
点迹凝聚作为雷达信号处理过程中重要的一环，帮助雷达在大量杂波干扰下准确的获取目标的距离、速度、方位角等信息，为后续的目标跟踪等算法提供有力的支撑。
在脉冲多普勒体制的雷达系统中，为了提高采样信号的质量，一般雷达系统的采样频率会大于奈奎斯特采样频率。这样会导致对同一个目标点有多个检测点，恒虚警处理后，还是会留下多余的点迹，所以需要使用点迹凝聚算法对其进行处理，保留最能反应目标参数的点，而筛除掉其他虚假的目标点[1-3]。
在需要凝聚的点数较少的情况下，常规的做法可以满足实时性的需求。但针对现在的多目标，群目标跟踪，由于目标个数的增加，恒虚警处理之后会产生大量的待凝聚点迹。当需要凝聚的点迹数量剧增时，常规的实现方案[4]就不能满足实时性的需求了。为了能提升大数据量下点迹凝聚算法的实时性，有很多针对于特定平台下的实现优化[5-9]，点迹凝聚算法的实现还可以通过优化数据结构的使用和充分发掘并行性进行优化。本文中在常规的点迹凝聚算法的实现方案[10-15]基础上，通过预排序、HashMap优化和多线程优化来降低算法的执行时间。在待凝聚点数较大时，最优方案相对于常规的实现方案在点迹数量为有着显著的加速效果。
2 常规点迹凝聚算法实现方案
点迹凝聚算法在工程上的常规实现方案是以恒虚警处理后目标回波的幅度值大小作为判断依据，根据点迹在距离-多普雷矩阵中的位置确定凝聚处理的窗大小，进行凝聚处理。
假设有N个待凝聚的点迹，最终凝聚出来M个有效目标，算法主要的时间消耗在了2个步骤上：
1) 从剩余目标中找幅值最大点；
2) 遍历所有剩余点确定是否在凝聚窗内。
这2个操作都需要进行M次循环，每次循环需要操作的点迹个数为当前轮次的剩余点迹个数，设每次循环排除的点迹个数分别为n1，n2，n3，…，nM，操作每个点迹的时间为t，那么总的时间消耗为
Ttotal=(2N+2(N-n1)+2(N-n2-n1)+…+
2(N-nm-…-n2-n1))*t=
(2NM-[n1+(n2+n1)+…+
(nm+…+n2+n1)])*t
NMt<Ttotal<2NMt
因此算法的时间复杂度为O(NM)。算法的优化方向主要在优化那2个耗时步骤上。
执行流程如图1所示。
图1 常规方法实现点迹凝聚程序流程框图
Fig.1 Flow chart of conventional plots centroid method
算法实现伪代码如下：
Algorithm 1 点迹凝聚算法的常规实现
Input： CFARRes
Output： CentroidRes
1 leftCFARRes=CFARRes;
2 while leftCFARRes is not empty do
3 maxAmpItem=leftCFARRes[0];
4 for item in leftCFARRes do
5 If item.amplitude > maxAmpItem.amplitude then
6 maxAmpItem=item;
7 end if
8 end for
9 for item in leftCFARRes do
10 if item in maxAmpItem’s centroid window then
11 delete item;
12 end if
13 end for
14 insert maxAmpItem to CentroidRes;
15 end while
3 使用预排序优化算法的实现
对基本实现方案进行编程实现，对程序分块计时分析由表1可知，算法执行时间近半耗费在从剩余点迹中获取幅值最大点的操作。可以通过对点迹根据幅值信息进行预排序进行优化。工程上常用的排序算法是快速排序算法，因此我们选择快速排序算法对算法进行优化。
表1 常规实现方案中找幅值最大值时间消耗占比
Table 1 The time proportion of finding the maximum amplitude
in the conventional implementation plan
待处理目标点数1005002 50012 500找幅值最大值耗时占比/%41484849
执行流程如图2所示。
图2 使用预排序优化的程序流程框图
Fig.2 Flow chart of using pre-sort optimization
算法实现伪代码如下：
Algorithm 2 使用预排序优化点迹凝聚算法的实现
Input： CFARRes
Output： CentroidRes
1 sort CFARRes with quick sort algorithm by amplitude;
2 i=0;
3 while i 4 if CFARRes[i].visited == 0 then 5 Insert CFARRes[i] to CentroidRes; 6 j=i+1; 7 while j 8 if CFARRes[j] in 9 CFARRes[i]’s centroid window then 10 CFARRes[j].visited=1; 11 end if 12 j++; 13 end while 14 end if; 15 i++; 16 end while 相对于常规方案的点迹凝聚算法，本方案的优化点在于优化了寻找剩余点迹中幅值最大点这一操作，凝聚窗内点迹的方法不变。对N个点迹，如果经过算法处理最终凝聚成M个目标，其快速排序的时间复杂度为O(NlogN)，而常规方案中，寻找剩余点迹中幅值最大点的操作的时间复杂度为O(MN)。这里，还可以采用基数排序的方法对待凝聚点迹进行排序，基数排序的理论算法复杂度更优。基于上述可以分析出，当需要凝聚的点数较多时，应该采用预排序的方法对执行时间进行优化。 在预排序的前提下，还可以进一步优化凝聚窗内点迹的操作。对于每一个目标点，我们在其距离维和多普勒维开一个窗口，判断剩余点迹是否在这个窗内，需要遍历所有的剩余点迹，我们可以预先建立点迹在距离-多普勒矩阵中的位置到其在排序后的点迹数据中的位置的映射，便可以在常数时间内锁定窗内的点是否在点迹数组中。使用HashMap的数据结构可以实现这种映射关系。 使用HashMap这一数据结构的关键点在于键值key的选取、桶的个数的确定和冲突解决方案的选择。假定点迹在距离-多普勒矩阵中的坐标为(x，y)，经过分析和测试，最终选择(x<<16)+y作为键值，使用大于点迹个数的最小素数作为桶的个数，使用拉链法来解决哈希冲突的方案来构造HashMap这一数据结构。该方案能够较为均匀的将点迹分布在各个桶里，保证能在常数时间内确定映射关系。 相对于常规的实现方案，使用HashMap进行优化的点集中在降低凝聚窗内点迹的复杂度上。对于N个点迹，凝聚成M个目标来说，之前的方案中这一操作的时间复杂度为O(MN)，使用HashMap优化后，时间复杂度降低为O(M)，这种优化对性能的提升是巨大的。 算法的程序流程如图3所示。 图3 使用预排序+HashMap优化的程序流程框图 算法实现伪代码如下： Algorithm 3 使用预排序+HashMap优化点迹凝聚算法的实现 Input： CFARRes Output： CentroidRes 1 sort CFARRes with quick sort algorithm by amplitude; 2 initial hashMap by build map relationship 3 from target position to its index in CFARRes; 4 i=0; 5 while i 6 if CFARRes[i].visited == 0 then 7 insert CFARRes[i] to CentroidRes; 8 for item in CFARRes[i]’s centroid window do 9 if item’s position in hashMap then 10 CFARRes[hashMap(Item’s position)]. visited=1; 11 end if 12 end for 13 end if 14 i++; 15 end while 随着摩尔定律的逐渐失效，现代处理器的处理主频已经接近其物理上限了，不能够像之前一样，通过提升处理器主频来提升处理器的性能。多核便成为了现代处理器必然的发展方向。核心数32个的商用桌面级CPU已经很常见，TI的c66x系列DSP的最高核心数也达到了8个。为了使算法能够利用多核处理器的优势，需要充分的发掘算法执行中的并行性，使用多线程的优化方案是建立在预排序和HashMap优化的基础上。本文给出2种多线程的优化方法。这2个方案都是建立在需要凝聚的点迹在距离-多普勒矩阵中的分布是呈现多点聚簇的样式，对于在大范围内连续的点迹是不适用的。 方案1：假设处理器有N个核心，则开辟N个线程。N个线程根据点迹的距离单元来划分各自负责的区域，各线程之间的处理没有重叠。各线程进行第一轮点迹凝聚之后，再开辟N-1个线程，每个线程负责的区域为第一轮线程间的邻接部分。距离维的长度为设置的距离维的窗的大小。 举例说明，距离-多普勒矩阵的大小为24*8，距离维窗大小为4，线程数为4。在第一轮次的处理中，线程1负责的距离单元为[1，6]，线程2负责的距离单元为[7，12]，线程3负责的距离单元为[13，18]，线程4负责的距离单元为[19，24]。将第一轮此凝聚出的点，选择出距离单元在[5，8]∪[11，14]∪[17，20]的点迹，继续进行第二轮次的凝聚，第二轮次的线程数为3，线程1负责的距离单元为[5，8]，线程2负责的距离单元为[11，14]，线程3负责的距离单元为[17，20]。第二轮凝聚结束，即得到了最终的凝聚结果。示意图如图4。 图4 多线程方案1示意图 方案2：假设处理器有N个核心，则开辟N个线程。N个线程根据点迹的距离单元来划分各自负责的区域，各线程之间的处理有一定的重叠。重叠区域的大小大于等于设定的距离维窗大小，对每个线程凝聚出的点迹进行筛选，每个线程只负责输出重叠区域中靠近自己处理的非重叠部分的半边。 在点迹凝聚的处理中，线程1负责的距离单元为[1，8] 的点迹，线程2负责的距离单元为[5，14] 的点迹，线程3负责的距离单元为[11，20] 的点迹，线程4负责的距离单元为[17，24] 的点迹。在点迹的输出过程中，线程1负责输出距离单元为[1，6] 的点迹，线程2负责输出距离单元为[7，12] 的点迹，线程3负责输出距离单元为[13，18] 的点迹，线程4负责输出距离单元为[19，24] 的点迹。示意图如图5。 图5 多线程方案2示意图 方案1中，优点在于每一轮次各线程负责的距离单元数是均匀的，且相对于方案二较少，但会有第二轮次的处理，第二轮次处理的点数较少，但线程调度的开销不小。方案2，只有一个轮次的处理，但每个线程负责的距离单元数要大于方案1，且第一个和最后一个线程的负载相对于其他线程不同，优点在于没有第二轮次的处理。 上述的2个多线程方案中目标在距离维呈现均匀分布时才能取得良好的加速效果。由于实际情况中，目标的分布状况是未知的。为了提高多线程方案的适用性，需要在进行多线程处理前，使用任务预分配方法合理划分每个线程的处理区间。方法的执行步骤和复杂度分析如下所述。 第一步需要维护一个长度等于距离单元个数的计数数组，该数组初始化为零，然后对所有的目标点进行一次遍历，在遍历过程中，记录对应距离单元的目标数。第二步从起始位置遍历计数数组，对计数数组中每个点(对应着不同的距离单元)，累加统计从起始位置到该距离单元的目标数。第三步根据目标的总个数除以划分的线程个数可确定每个线程要处理的目标点个数，再从第二步的计数数组中找到每个线程的合理处理区间，该划分可尽最大可能平均每个线程处理的目标点个数，从而使整体获得良好的平均加速效果。 对于N个目标点，第一步的时间复杂度为O(N)，第二步和第三步实现时可合并处理，对于L个距离单元，其时间复杂度为O(L)。任务预分配方法的整体时间复杂度是线性的，不改变算法的整体时间复杂度。 为了对比各执行方案的执行效率，编程实现所有的方案并在同一环境下进行性能测试。实验环境如表2所示，点迹凝聚算法的参数如表3所示。 表2 实验环境 Table 2 Experimental environment 参数条目指标操作系统win10集成开发环境Visual Studio 2017编译器MSVC 2017编译环境Release,x64版本优化等级-O2处理器AMD Ryzen 7 4800H编程语言C++ 表3 算法参数 Table 3 Algorithm parameters 参数条目指标距离维单元数16 384多普勒维单元数256距离维窗大小11多普勒维窗大小7多线程方案开辟线程数4 为了保证测试的公平性，在测试时对以下几点做出保证：确保每种方案的代码经过同等级的优化，不刻意从代码实现层面制造性能差异；对于多线程代码，为降低线程建立之类的系统调用对程序性能的影响，预先执行一遍多线程代码，在再次重复执行时对程序进行计时；性能测试结果采用多次测试取平均值的方案。最终的测试结果如表4所示。 表4 各方案执行性能 Table 4 Performance comparison of different schemes 待凝聚点个数1003009002 7008 10024 30072 900218 700常规方案/ms0.10.82182532 51020 486142 457预排序优化/ms0.10.413312994 13844 659预排序+HashMap优化/ms0.511392778352多线程方案1/ms35568122491多线程方案2/ms23448112393 1) 在需要处理的待凝聚点数较少的情况下，常规的实现方案的性能和优化的方案差别很小，由于优化带来的额外的开销，常规的方案甚至略有优势。 2) 随着待凝聚点数的增加，常规方案的执行时间大幅增加，使用预排序+HashMap优化的方案能够大幅降低算法的执行时间，具有很大的优势。 3) 多线程代码相对于单线程代码，在待凝聚点数较少时，由于线程调度之类的开销的存在，使得执行时间比单线程还长。但随着数据规模的增加，多线程方案相对于单线程的执行时间比近似于1：线程数，有着明显的加速效果。 4) 多线程的优化方案相对于单线程的方案，在数据规模较大时，加速比接近线程数目，可充分利用现代处理器的多核特性。优化措施和多线程处理，能够使得点迹凝聚算法在大数据量下仍能满足雷达信号处理实时性的需求，对今后的工程实现有着巨大的意义。 [1] 王建声.目标积累检测与点迹凝聚技术研究[D].西安：西安电子科技大学，2017. Wang J S.Study on accumulate detect of target and the technology of dots-cohesion[D].Xi’an：Xidian University，2017. [2] 田焕.米波雷达点迹凝聚处理与实现[D].西安：西安电子科技大学，2014. Tian H.Meter-band Radar Plots Centroid Processing and Its Implementation[D].Xi’an：Xidian University，2014. [3] Li Y Y，Guo L M，Huang X S.Research and application of multi-target tracking based on GM-PHD Filter[J].Optics and Photonics Journal，2020，10(6)：125-133. [4] 彭中硕.基于多核处理器的火控雷达信号处理方法与实现[D].西安：西安电子科技大学，2018. Peng Z S.Method and Implement of Fire Control Radar Signal Processing Based on Multicore Processor[D].Xi’an：Xidian University，2018. [5] 李娜，刘志英.基于BW100的二维点迹凝聚算法研究[J].电子科学技术，2016，3(02)：159-161，165. Li N，Liu Z Y.Study on accumulate detect of target and the tech-nology of dots-cohesion[J].Electronic Science & Technology，2016，3(02)：159-161，165. [6] 马晓晨.基于PowerPC的雷达点迹凝聚方法研究[D].西安：西安电子科技大学，2015. Ma X C.A Plot Clotting Approach of Radar Based on PowerPC[D].Xi’an：Xidian University，2015. [7] 夏栋，夏奎，张伟，等.GPU加速下脉冲压缩雷达的点迹凝聚[J].火力与指挥控制，2013，38(03)：81-85. Xia D，Xia K，Zhang W，et al.Acceleration of pulse compression radar’s plots’ agglomerating on GPU[J].Fire control & command control，2013，38(03)：81-85. [8] 熊毅，张承志.VxWorks平台下的米波雷达点迹凝聚方法研究[J].雷达科学与技术，2009，7(06)：443-446，451. Xiong Y，Zhang C Z.A Plot Clotting Approach of Meter Wave Radar Based on VxWorks[J].Radar Science and Technology，，2009，7(06)：443-446，451. [9] 杨海英，蔡文彬，秦赟，等.点迹凝聚在FPGA上的实现[J].雷达与对抗，2012，32(03)：59-62. Yang H Y，Cai W B，Qin Y，et al.Realization of plots centroid on FPGA[J].Radar & Ecm，2012，32(03)：59-62. [10] 周喃.一种基于三坐标雷达的点迹凝聚方法[J].雷达与对抗，2013，33(04)：46-50. Zhou N.Algorithm of Plots-Centroid Based on three coordinates Radar[J].Radar & Ecm，2013，33(04)：46-50. [11] 杨文琳，方志宏，阮信畅，等.雷达点迹凝聚处理技术及其数据分析[J].信号处理，2001，17(2)：130-138. Yang W L，Fang Z H，Ruan X C，et al.Processing technology and data analysis of radar plots centroid[J].Signal Processing，2001，17(2)：130-138. [12] Liu H B，Li J B，Zhang P Y.A new algorithm of plots centroid for radar target[C]//2016 9th International Congress on Image and Signal Processing，Bio Medical Engineering and Informatics.IEEE，2016. [13] 戴麒麟.雷达数据处理算法及实现技术研究[D].成都：电子科技大学，2018. Dai Q L.Research on Radar Data Processing Algorithm and Implementation Technique[D].Chengdu：University of Electronic Science and Technology of China，2018. [14] 于祥龙.目标检测和点迹处理技术仿真和实现[D].西安：西安电子科技大学，2017. Yu X L.Simulation and Implementation of Target Detection and Plot Processing Technology[D].Xi’an：Xidian University，2017. [15] 罗元，肖航，欧俊雄.基于深度学习的目标跟踪技术的研究综述[J].半导体光电，2020，41(06)：757-767. Luo Y，Xiao H，Ou J X.A review of target tracking techniques based on deep learning[J].Semiconductor Optoelectronics，2020，41(06)：757-767.4 HashMap优化算法实现
Fig.3 Flow chart optimized using pre-sorting+HashMap
5 多线程优化算法的实现
Fig.4 Diagram of multi-threading scheme 1
Fig.5 Diagram of multi-threading scheme 26 各案执行情况
7 结论