基于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成像方法存在的不足。