基于MapReduce的合成孔径雷达后向投影快速成像方法

李长树， 廖可非,2*， 欧阳缮,2， 蒋俊正,2， 杜 毅

(1.桂林电子科技大学信息与通信学院，桂林 541004；2.卫星导航定位与位置服务国家地方联合工程研究中心(桂林电子科技大学)，桂林 541004)

合成孔径雷达(synthetic aperture radar，SAR)是一种全天时、全天候、信息量丰富的遥感成像技术[1]。该技术已经在目标侦察、军事打击、资源勘测、灾害监测和环境监测等军用与民用领域得到了广泛的应用[2-3]。随着SAR成像场景的复杂化和应用的深化[4]，非线性运动轨迹下大场景高分辨率高精度快速成像成为了SAR研究的热点[5-6]。SAR在非线性运动轨迹下完成大场景高分辨率高精度成像最为合适的算法就是后向投影(back projection，BP)算法。相比于频域成像算法，BP算法不存在近似计算，适合应用于非线性运动轨迹下SAR的大场景高分辨率高精度成像[5]。但是，由于BP算法需要每个脉冲内的回波数据对成像场景网格点进行遍历计算，因此算法计算量大，成像时延长，限制了其在实际中的进一步应用。

为了实现数据的快速处理，中外学者提出了基于图形处理器(graphics processing unit，GPU)的数据处理方法，借助GPU强大的并行处理能力和大量的算术逻辑计算单元，加速数据处理过程。文献[7]提出了基于GPU的遥感图像海陆分割并行化处理方法，采用GPU的并行化计算框架，将遥感图像海陆分割的计算过程并行化，有效提高了海陆分割的处理速度。在SAR的BP成像上，文献[5]提出了基于GPU的非线性运动补偿SAR图像流BP成像方法，通过图像流处理与并行化计算的方式，使得该方法的成像时间满足了许多SAR成像应用的需求。文献[8]提出了基于GPU的并行化BP成像算法及其两种优化方法，一是利用纹理存储器进行快速插值，二是利用共享存储器提高访存速度，优化了并行化BP算法的成像过程。文献[9]提出了一种针对BP成像的GPU优化方案，采用多流异步执行技术优化脉冲压缩，通过反投影计算结构优化和混合精度编程方法，提高了BP成像的计算速度。可见，基于GPU加速的BP成像方法在成像速度上获得了较大的提升。但是，使用GPU加速的BP成像方法也存在以下两个不足：第一是现有GPU显存不足，较难一次性完成大场景高分辨率成像[10]；最重要的是，基于GPU的处理平台的计算能力扩展性不足，组建超级计算机的成本十分昂贵。

近年来，随着计算机技术和网络技术的飞速发展，分布式计算在需要巨大计算能力的场景中得到了实践和应用。文献[11]提出了基于MapReduce的雷达信号快速识别方法，将K近邻算法在MapReduce编程模型中分布式并行化实现，能够有效用于海量雷达信号数据的快速识别。文献[12]提出了基于MapReduce的模糊局部信息C-均值算法，在Map阶段进行隶属度的更新计算,在Reduce阶段更新聚类中心，多次MapReduce计算实现算法迭代，能够有效用于大尺寸的SAR图像变化检测。文献[13]提出了基于云计算的SAR原始数据仿真方法，该方法采用MapReduce分布式计算编程模型加速仿真的计算，有效提高了SAR原始数据的仿真速度。为了实现SAR大场景快速成像，本文结合分布式计算技术提出了一种MapReduce-后向投影(MapReduce-back projection，MR-BP)方法。MR-BP方法根据BP算法对每个脉冲内的数据进行独立处理的特性，结合MapReduce分布式计算编程模型的分布式并行化计算能力，将数据划分成若干个数据块，让不同的计算执行单元并行处理划分后的数据块，最后将各个数据块的计算结果聚合起来，完成BP快速成像。该方法的优点是满足海量数据的交互需求、一次性完成大场景高分辨率高精度快速成像、计算平台的计算能力具备良好的扩展性。

首先给出BP算法的流程与并行化分析、MapReduce分布式计算编程模型的计算过程；然后阐述BP算法与MapReduce的结合过程，给出MR-BP方法计算流程和详细步骤；最后通过实验验证MR-BP方法的成像准确性，分析该方法输入数据分块数对计算效率的影响和该方法对BP成像的加速性能。

1 算法原理

1.1 BP算法

BP算法的成像流程图如图1所示。

图1 BP算法的成像流程图Fig.1 BP algorithm imaging flow chart

在BP算法中，每个脉冲内的数据处理是独立的，均是对成像场景网格点遍历计算，得到单个脉冲的成像数据，最后将所有脉冲的成像数据相参累加得到成像结果。因此，BP算法能够以单个脉冲的成像作为单元，进行并行化计算来缩减计算时间[14]。

图2 MapReduce计算流程框图Fig.2 MapReduce calculation flow diagram

1.2 MapReduce分布式计算编程模型

MapReduce是依托于Hadoop分布式计算平台的大规模分布式数据并行计算编程模型，它结合Hadoop的分布式文件系统(Hadoop distributed file system，HDFS)和资源调度模块(yetanother resource negotiator，YARN)可以快速完成海量数据的并行化处理。MapReduce的计算流程主要分成Map阶段和Reduce阶段，计算流程框图如图2所示[13]，数据传输以键值对(键值对，是一种数据组织形式，记为，key表示存储内容的编号，value表示存储的内容)的形式实现，详细实现方案参见文献[15]。

图3 MR-BP方法流程框图Fig.3 MR-BP method flow diagram

2 MR-BP方法的实现

MR-BP方法是分布式并行化计算与BP算法的结合应用，其思想是对BP算法的方位向成像计算进行划分并实现分布式并行化计算，快速完成大场景高分辨BP成像。根据MapReduce分布式并行化计算流程与BP算法原理，将MR-BP方法分为预处理阶段、Map阶段和Reduce阶段，流程框图如图3所示。

2.1 预处理阶段

MR-BP方法的预处理阶段完成目标回波数据的距离压缩和划分成像场景网格之后，由于BP算法计算回波时延需要得到该脉冲内天线阵元的位置信息，因此在距离向成像数据分块之前，对每个脉冲内的数据添加其对应天线阵元的位置信息，为实现数据块的并行处理做准备。预处理阶段详细的步骤如下。

(1)对目标回波数据采用传统雷达距离压缩算法进行距离向成像，得到距离像矩阵。

(2)对成像场景建立三维直角坐标系，划分网格。

(3)在距离像矩阵的右边添加一列，记录每个脉冲的数据所对应天线阵元的位置信息，形成第二距离像矩阵。

(4)将第二距离像矩阵上传到HDFS。

2.2 Map阶段

MR-BP方法的Map阶段实现方位向成像任务的划分和分布式并行化计算。在任务的划分上，MapReduce为每个数据块对应生成一个Map任务，为了最大化加速BP成像过程，经过距离压缩后，每个脉冲内的数据对应一个Map任务并行对成像场景网格点遍历计算是理想的并行化方案。但是，由于MapReduce每个Map任务对应一个进程，进程的开启存在必要的时间开销和后续数据聚合耗时，每个脉冲对应一个进程反而会降低计算效率。因此，将多个脉冲内的数据划分成一个数据块，一个数据块对应一个进程，该进程串行处理每个脉冲内的数据，多个数据块对应多个进程并行执行是一个切合实际的并行化方案。在数据并行处理的过程中，需要防止一些Map任务计算量较大，导致计算时间较长，拖慢整个MapReduce程序的运行。因此，对输入数据的分块需要均衡每个Map任务的计算量，避免发生数据倾斜。

此外，在MR-BP方法中，每个Map任务对三维场景遍历之后产生大量的键值对数据，这部分键值对的value是成像场景水平面的二维成像矩阵，key是垂直方向的坐标值，若将这部分键值对数据都复制到Reduce阶段统一进行相参累加，则会导致消耗较多的磁盘资源和网络资源，Reduce阶段的串行计算量也较大。因此，在不影响方法成像结果的前提下，在Mapper函数与Reducer函数之间设置一个Combiner函数，用于将相同key值对应的value进行相参累加，聚合部分键值对，减少落入磁盘的数据量，降低数据复制时的网络负担，减少Reduce阶段的串行计算量，有效缩减MR-BP方法的计算时间。

Map阶段详细的步骤如下。

(1)将第二距离像矩阵按行均分(若存在余数，余数部分可另作1块)，共分成K块。

(2)每个任务的Mapper函数根据经典BP算法逐一处理每个脉冲内的数据，对三维直角坐标系内的场景网格点进行遍历计算。每个脉冲内的数据处理结果以的形式输出，key为z轴的坐标值，value为xOy平面的二维成像矩阵。

(3)Reduce阶段的任务数根据Map阶段输出的数据量设定，现在假设Reduce阶段的任务数为2。所以，每个Map任务将Mapper函数输出的数据根据键值对的key值划分成2个分区，保证相同key值的键值对在同一个分区内，运行Combiner函数将相同key值对应的value进行相参累加。

2.3 Reduce阶段

MR-BP方法的Reduce阶段完成每个Map任务计算结果的复制、合并和相参累加,并把成像数据输出到HDFS。详细的步骤如下。

(1)Reduce任务复制对应分区的成像过程数据。

(2)每个Reduce任务合并数据文件。

(3)合并后的数据文件输入到Reducer函数，Reducer函数将key相同的value进行相参累加。

(4)相参累加的结果作为value、key保持不变，以的形式写到HDFS,完成三维成像数据的计算。

3 实验结果与分析

为了验证本文方法的有效性，实验使用4台相同配置的物理计算机搭建Hadoop分布式计算平台(下文也称之为集群)，包含4个计算节点，其中一个计算节点同时作为主节点(主节点是指负责管理数据存储地址和资源调度的计算机)，具体硬件信息和软件版本如表1所示。单机计算平台是集群中的单台物理计算机。实验所用数据来源于Feko电磁仿真软件的三维成像雷达回波仿真，因此成像场景只是单一的汽车模型。成像的大小为50×50×20 pixel。

表1 实验环境配置Table 1 Experimental environment configuration

3.1 成像准确性分析

MR-BP方法是针对BP算法在大场景高分辨率成像时数据处理速度的优化，在数值计算上与单机计算的BP成像方法相同。对于MR-BP方法成像的准确性验证，实验结果表明相对于单机计算的BP成像方法的成像结果，MR-BP方法的成像结果在每个像素点的数值误差均小于10-10%。实验成像场景中的汽车模型如图4(a)所示，单机计算的BP成像方法成像结果如图4(b)所示，MR-BP方法成像结果如图4(c)所示。可见，对于MR-BP方法与单机计算的BP成像方法，两者的成像质量相当。

图4 成像场景图与实验成像图Fig.4 The imaging scene image and experimental imaging images

3.2 输入数据分块数对计算效率的影响

在MR-BP方法方位向成像中，一个输入数据分块对应启动一个Map任务。若输入数据分块数过小，会导致Map任务启动过少，集群资源利用率过低，计算时间较长；若输入数据分块数过多，启动的Map任务也较多，虽然保证了集群资源的利用率，但是过多的Map任务会带来巨大的任务启动开销和数据存储与传输的耗时，也会使得计算时间较长。为了验证上述的理论分析，实验测试了在不同输入数据分块数下MR-BP方法方位向成像的计算时间，多次实验取均值的结果如图5所示。可见，输入数据的分块数需要根据集群计算资源和处理输入数据的计算量确定，分块数过小或者过大，都会降低MR-BP方法方位向成像的计算效率。本实验环境下输入数据的较优分块数为36。

图5 不同的输入数据分块数对MR-BP方法方位向成像计算时间的影响Fig.5 Influence of different input data block numbers for computational time of MR-BP method azimath imaging

3.3 加速性能分析

在MR-BP方法方位向成像的输入数据分块数为36时，计算节点数量不同的集群分别进行多次实验，取均值的结果如图6所示。

图6 单机计算的BP方位向成像方法与MR-BP方法方位向成像的计算时间对比Fig.6 Comparison of calculation time between BP azimuth imaging method calculated by a single machine and azimuth imaging of MR-BP method

当计算节点数为1时，MR-BP方法方位向成像在Hadoop分布式计算平台中执行，由于存在多进程启动和等待磁盘读写的耗时，相对于单机计算的BP方位向成像方法，MR-BP方法方位向成像的计算时间稍长。但是，随着集群计算节点的增加，MR-BP方法方位向成像的计算时间逐渐减少，当计算节点数为4时，单机计算的BP方位向成像方法的计算时间是MR-BP方法方位向成像的3.7倍，可见，MR-BP方法具备加速BP成像的能力。

4 结论

针对BP算法在大场景下高分辨率成像的时延较长，采用GPU加速的计算平台显存和扩展性不足的问题，基于MapReduce的分布式并行化计算能力，结合BP算法对数据处理的流程，提出了一种基于MapReduce的合成孔径雷达后向投影快速成像方法。该方法对BP成像的加速能力在实验中得到了验证，其依托的Hadoop分布式计算平台，具备海量数据交互与大批量数据处理的能力，计算平台可横向扩展计算节点以提高平台的计算能力，扩展性充足，且成本较低，有效解决基于GPU加速的BP成像方法存在的不足。