多目标跟踪下点迹凝聚的实时优化算法

2021-10-15吴春林曹运合

兵器装备工程学报 2021年9期

吴春林，曹运合，王蒙

(1.海军航空大学青岛校区，山东青岛 266041； 2.西安电子科技大学，西安 710071；3.北京机电工程研究所，北京 100074)

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

因此算法的时间复杂度为O(NM)。算法的优化方向主要在优化那2个耗时步骤上。

执行流程如图1所示。

图1 常规方法实现点迹凝聚程序流程框图Fig.1 Flow chart of conventional plots centroid method

算法实现伪代码如下：

Algorithm 1 点迹凝聚算法的常规实现

Input： CFARRes

Output： CentroidRes

1 leftCFARRes=CFARRes;

2whileleftCFARRes is not emptydo

3 maxAmpItem=leftCFARRes[0];

4foritem in leftCFARRes do

5Ifitem.amplitude > maxAmpItem.amplitude then

6 maxAmpItem=item;

7endif

8endfor

9foritem in leftCFARRes do

10ifitem in maxAmpItem’s centroid window then

11 delete item;

12endif

13endfor

14 insert maxAmpItem to CentroidRes;

15endwhile

3 使用预排序优化算法的实现

对基本实现方案进行编程实现，对程序分块计时分析由表1可知，算法执行时间近半耗费在从剩余点迹中获取幅值最大点的操作。可以通过对点迹根据幅值信息进行预排序进行优化。工程上常用的排序算法是快速排序算法，因此我们选择快速排序算法对算法进行优化。

表1 常规实现方案中找幅值最大值时间消耗占比

执行流程如图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;

2i=0;

3whilei

4ifCFARRes[i].visited == 0 then

5 Insert CFARRes[i] to CentroidRes;

6j=i+1;

7whilej

8ifCFARRes[j] in

9 CFARRes[i]’s centroid windowthen

10 CFARRes[j].visited=1;

11endif

12j++;

13endwhile

14endif;

15i++;

16endwhile

相对于常规方案的点迹凝聚算法，本方案的优化点在于优化了寻找剩余点迹中幅值最大点这一操作，凝聚窗内点迹的方法不变。对N个点迹，如果经过算法处理最终凝聚成M个目标，其快速排序的时间复杂度为O(NlogN)，而常规方案中，寻找剩余点迹中幅值最大点的操作的时间复杂度为O(MN)。这里，还可以采用基数排序的方法对待凝聚点迹进行排序，基数排序的理论算法复杂度更优。基于上述可以分析出，当需要凝聚的点数较多时，应该采用预排序的方法对执行时间进行优化。

4 HashMap优化算法实现

在预排序的前提下，还可以进一步优化凝聚窗内点迹的操作。对于每一个目标点，我们在其距离维和多普勒维开一个窗口，判断剩余点迹是否在这个窗内，需要遍历所有的剩余点迹，我们可以预先建立点迹在距离-多普勒矩阵中的位置到其在排序后的点迹数据中的位置的映射，便可以在常数时间内锁定窗内的点是否在点迹数组中。使用HashMap的数据结构可以实现这种映射关系。

使用HashMap这一数据结构的关键点在于键值key的选取、桶的个数的确定和冲突解决方案的选择。假定点迹在距离-多普勒矩阵中的坐标为(x，y)，经过分析和测试，最终选择(x<<16)+y作为键值，使用大于点迹个数的最小素数作为桶的个数，使用拉链法来解决哈希冲突的方案来构造HashMap这一数据结构。该方案能够较为均匀的将点迹分布在各个桶里，保证能在常数时间内确定映射关系。

相对于常规的实现方案，使用HashMap进行优化的点集中在降低凝聚窗内点迹的复杂度上。对于N个点迹，凝聚成M个目标来说，之前的方案中这一操作的时间复杂度为O(MN)，使用HashMap优化后，时间复杂度降低为O(M)，这种优化对性能的提升是巨大的。

算法的程序流程如图3所示。

图3 使用预排序+HashMap优化的程序流程框图Fig.3 Flow chart optimized using pre-sorting+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;

4i=0;

5whilei

6ifCFARRes[i].visited == 0then

7 insert CFARRes[i] to CentroidRes;

8foritem in CFARRes[i]’s centroid windowdo

9ifitem’s position in hashMapthen

10 CFARRes[hashMap(Item’s position)].

visited=1;

11endif

12endfor

13endif

14i++;

15endwhile

5 多线程优化算法的实现

随着摩尔定律的逐渐失效，现代处理器的处理主频已经接近其物理上限了，不能够像之前一样，通过提升处理器主频来提升处理器的性能。多核便成为了现代处理器必然的发展方向。核心数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示意图Fig.4 Diagram of multi-threading scheme 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示意图Fig.5 Diagram of multi-threading scheme 2

方案1中，优点在于每一轮次各线程负责的距离单元数是均匀的，且相对于方案二较少，但会有第二轮次的处理，第二轮次处理的点数较少，但线程调度的开销不小。方案2，只有一个轮次的处理，但每个线程负责的距离单元数要大于方案1，且第一个和最后一个线程的负载相对于其他线程不同，优点在于没有第二轮次的处理。

上述的2个多线程方案中目标在距离维呈现均匀分布时才能取得良好的加速效果。由于实际情况中，目标的分布状况是未知的。为了提高多线程方案的适用性，需要在进行多线程处理前，使用任务预分配方法合理划分每个线程的处理区间。方法的执行步骤和复杂度分析如下所述。

第一步需要维护一个长度等于距离单元个数的计数数组，该数组初始化为零，然后对所有的目标点进行一次遍历，在遍历过程中，记录对应距离单元的目标数。第二步从起始位置遍历计数数组，对计数数组中每个点(对应着不同的距离单元)，累加统计从起始位置到该距离单元的目标数。第三步根据目标的总个数除以划分的线程个数可确定每个线程要处理的目标点个数，再从第二步的计数数组中找到每个线程的合理处理区间，该划分可尽最大可能平均每个线程处理的目标点个数，从而使整体获得良好的平均加速效果。

对于N个目标点，第一步的时间复杂度为O(N)，第二步和第三步实现时可合并处理，对于L个距离单元，其时间复杂度为O(L)。任务预分配方法的整体时间复杂度是线性的，不改变算法的整体时间复杂度。

6 各案执行情况

为了对比各执行方案的执行效率，编程实现所有的方案并在同一环境下进行性能测试。实验环境如表2所示，点迹凝聚算法的参数如表3所示。

表2 实验环境

表3 算法参数

为了保证测试的公平性，在测试时对以下几点做出保证：确保每种方案的代码经过同等级的优化，不刻意从代码实现层面制造性能差异；对于多线程代码，为降低线程建立之类的系统调用对程序性能的影响，预先执行一遍多线程代码，在再次重复执行时对程序进行计时；性能测试结果采用多次测试取平均值的方案。最终的测试结果如表4所示。