基于MapReduce的合成孔徑雷達(dá)后向投影快速成像方法

李長(zhǎng)樹(shù)， 廖可非,2*， 歐陽(yáng)繕,2， 蔣俊正,2， 杜 毅

(1.桂林電子科技大學(xué)信息與通信學(xué)院，桂林 541004；2.衛(wèi)星導(dǎo)航定位與位置服務(wù)國(guó)家地方聯(lián)合工程研究中心(桂林電子科技大學(xué))，桂林 541004)

合成孔徑雷達(dá)(synthetic aperture radar，SAR)是一種全天時(shí)、全天候、信息量豐富的遙感成像技術(shù)[1]。該技術(shù)已經(jīng)在目標(biāo)偵察、軍事打擊、資源勘測(cè)、災(zāi)害監(jiān)測(cè)和環(huán)境監(jiān)測(cè)等軍用與民用領(lǐng)域得到了廣泛的應(yīng)用[2-3]。隨著SAR成像場(chǎng)景的復(fù)雜化和應(yīng)用的深化[4]，非線(xiàn)性運(yùn)動(dòng)軌跡下大場(chǎng)景高分辨率高精度快速成像成為了SAR研究的熱點(diǎn)[5-6]。SAR在非線(xiàn)性運(yùn)動(dòng)軌跡下完成大場(chǎng)景高分辨率高精度成像最為合適的算法就是后向投影(back projection，BP)算法。相比于頻域成像算法，BP算法不存在近似計(jì)算，適合應(yīng)用于非線(xiàn)性運(yùn)動(dòng)軌跡下SAR的大場(chǎng)景高分辨率高精度成像[5]。但是，由于BP算法需要每個(gè)脈沖內(nèi)的回波數(shù)據(jù)對(duì)成像場(chǎng)景網(wǎng)格點(diǎn)進(jìn)行遍歷計(jì)算，因此算法計(jì)算量大，成像時(shí)延長(zhǎng)，限制了其在實(shí)際中的進(jìn)一步應(yīng)用。

為了實(shí)現(xiàn)數(shù)據(jù)的快速處理，中外學(xué)者提出了基于圖形處理器(graphics processing unit，GPU)的數(shù)據(jù)處理方法，借助GPU強(qiáng)大的并行處理能力和大量的算術(shù)邏輯計(jì)算單元，加速數(shù)據(jù)處理過(guò)程。文獻(xiàn)[7]提出了基于GPU的遙感圖像海陸分割并行化處理方法，采用GPU的并行化計(jì)算框架，將遙感圖像海陸分割的計(jì)算過(guò)程并行化，有效提高了海陸分割的處理速度。在SAR的BP成像上，文獻(xiàn)[5]提出了基于GPU的非線(xiàn)性運(yùn)動(dòng)補(bǔ)償SAR圖像流BP成像方法，通過(guò)圖像流處理與并行化計(jì)算的方式，使得該方法的成像時(shí)間滿(mǎn)足了許多SAR成像應(yīng)用的需求。文獻(xiàn)[8]提出了基于GPU的并行化BP成像算法及其兩種優(yōu)化方法，一是利用紋理存儲(chǔ)器進(jìn)行快速插值，二是利用共享存儲(chǔ)器提高訪(fǎng)存速度，優(yōu)化了并行化BP算法的成像過(guò)程。文獻(xiàn)[9]提出了一種針對(duì)BP成像的GPU優(yōu)化方案，采用多流異步執(zhí)行技術(shù)優(yōu)化脈沖壓縮，通過(guò)反投影計(jì)算結(jié)構(gòu)優(yōu)化和混合精度編程方法，提高了BP成像的計(jì)算速度?？梢?jiàn)，基于GPU加速的BP成像方法在成像速度上獲得了較大的提升。但是，使用GPU加速的BP成像方法也存在以下兩個(gè)不足：第一是現(xiàn)有GPU顯存不足，較難一次性完成大場(chǎng)景高分辨率成像[10]；最重要的是，基于GPU的處理平臺(tái)的計(jì)算能力擴(kuò)展性不足，組建超級(jí)計(jì)算機(jī)的成本十分昂貴。

近年來(lái)，隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，分布式計(jì)算在需要巨大計(jì)算能力的場(chǎng)景中得到了實(shí)踐和應(yīng)用。文獻(xiàn)[11]提出了基于MapReduce的雷達(dá)信號(hào)快速識(shí)別方法，將K近鄰算法在MapReduce編程模型中分布式并行化實(shí)現(xiàn)，能夠有效用于海量雷達(dá)信號(hào)數(shù)據(jù)的快速識(shí)別。文獻(xiàn)[12]提出了基于MapReduce的模糊局部信息C-均值算法，在Map階段進(jìn)行隸屬度的更新計(jì)算,在Reduce階段更新聚類(lèi)中心，多次MapReduce計(jì)算實(shí)現(xiàn)算法迭代，能夠有效用于大尺寸的SAR圖像變化檢測(cè)。文獻(xiàn)[13]提出了基于云計(jì)算的SAR原始數(shù)據(jù)仿真方法，該方法采用MapReduce分布式計(jì)算編程模型加速仿真的計(jì)算，有效提高了SAR原始數(shù)據(jù)的仿真速度。為了實(shí)現(xiàn)SAR大場(chǎng)景快速成像，本文結(jié)合分布式計(jì)算技術(shù)提出了一種MapReduce-后向投影(MapReduce-back projection，MR-BP)方法。MR-BP方法根據(jù)BP算法對(duì)每個(gè)脈沖內(nèi)的數(shù)據(jù)進(jìn)行獨(dú)立處理的特性，結(jié)合MapReduce分布式計(jì)算編程模型的分布式并行化計(jì)算能力，將數(shù)據(jù)劃分成若干個(gè)數(shù)據(jù)塊，讓不同的計(jì)算執(zhí)行單元并行處理劃分后的數(shù)據(jù)塊，最后將各個(gè)數(shù)據(jù)塊的計(jì)算結(jié)果聚合起來(lái)，完成BP快速成像。該方法的優(yōu)點(diǎn)是滿(mǎn)足海量數(shù)據(jù)的交互需求、一次性完成大場(chǎng)景高分辨率高精度快速成像、計(jì)算平臺(tái)的計(jì)算能力具備良好的擴(kuò)展性。

首先給出BP算法的流程與并行化分析、MapReduce分布式計(jì)算編程模型的計(jì)算過(guò)程；然后闡述BP算法與MapReduce的結(jié)合過(guò)程，給出MR-BP方法計(jì)算流程和詳細(xì)步驟；最后通過(guò)實(shí)驗(yàn)驗(yàn)證MR-BP方法的成像準(zhǔn)確性，分析該方法輸入數(shù)據(jù)分塊數(shù)對(duì)計(jì)算效率的影響和該方法對(duì)BP成像的加速性能。

1 算法原理

1.1 BP算法

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

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

在BP算法中，每個(gè)脈沖內(nèi)的數(shù)據(jù)處理是獨(dú)立的，均是對(duì)成像場(chǎng)景網(wǎng)格點(diǎn)遍歷計(jì)算，得到單個(gè)脈沖的成像數(shù)據(jù)，最后將所有脈沖的成像數(shù)據(jù)相參累加得到成像結(jié)果。因此，BP算法能夠以單個(gè)脈沖的成像作為單元，進(jìn)行并行化計(jì)算來(lái)縮減計(jì)算時(shí)間[14]。

圖2 MapReduce計(jì)算流程框圖Fig.2 MapReduce calculation flow diagram

1.2 MapReduce分布式計(jì)算編程模型

MapReduce是依托于Hadoop分布式計(jì)算平臺(tái)的大規(guī)模分布式數(shù)據(jù)并行計(jì)算編程模型，它結(jié)合Hadoop的分布式文件系統(tǒng)(Hadoop distributed file system，HDFS)和資源調(diào)度模塊(yetanother resource negotiator，YARN)可以快速完成海量數(shù)據(jù)的并行化處理。MapReduce的計(jì)算流程主要分成Map階段和Reduce階段，計(jì)算流程框圖如圖2所示[13]，數(shù)據(jù)傳輸以鍵值對(duì)(鍵值對(duì)，是一種數(shù)據(jù)組織形式，記為，key表示存儲(chǔ)內(nèi)容的編號(hào)，value表示存儲(chǔ)的內(nèi)容)的形式實(shí)現(xiàn)，詳細(xì)實(shí)現(xiàn)方案參見(jiàn)文獻(xiàn)[15]。

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

2 MR-BP方法的實(shí)現(xiàn)

MR-BP方法是分布式并行化計(jì)算與BP算法的結(jié)合應(yīng)用，其思想是對(duì)BP算法的方位向成像計(jì)算進(jìn)行劃分并實(shí)現(xiàn)分布式并行化計(jì)算，快速完成大場(chǎng)景高分辨BP成像。根據(jù)MapReduce分布式并行化計(jì)算流程與BP算法原理，將MR-BP方法分為預(yù)處理階段、Map階段和Reduce階段，流程框圖如圖3所示。

2.1 預(yù)處理階段

MR-BP方法的預(yù)處理階段完成目標(biāo)回波數(shù)據(jù)的距離壓縮和劃分成像場(chǎng)景網(wǎng)格之后，由于BP算法計(jì)算回波時(shí)延需要得到該脈沖內(nèi)天線(xiàn)陣元的位置信息，因此在距離向成像數(shù)據(jù)分塊之前，對(duì)每個(gè)脈沖內(nèi)的數(shù)據(jù)添加其對(duì)應(yīng)天線(xiàn)陣元的位置信息，為實(shí)現(xiàn)數(shù)據(jù)塊的并行處理做準(zhǔn)備。預(yù)處理階段詳細(xì)的步驟如下。

(1)對(duì)目標(biāo)回波數(shù)據(jù)采用傳統(tǒng)雷達(dá)距離壓縮算法進(jìn)行距離向成像，得到距離像矩陣。

(2)對(duì)成像場(chǎng)景建立三維直角坐標(biāo)系，劃分網(wǎng)格。

(3)在距離像矩陣的右邊添加一列，記錄每個(gè)脈沖的數(shù)據(jù)所對(duì)應(yīng)天線(xiàn)陣元的位置信息，形成第二距離像矩陣。

(4)將第二距離像矩陣上傳到HDFS。

2.2 Map階段

MR-BP方法的Map階段實(shí)現(xiàn)方位向成像任務(wù)的劃分和分布式并行化計(jì)算。在任務(wù)的劃分上，MapReduce為每個(gè)數(shù)據(jù)塊對(duì)應(yīng)生成一個(gè)Map任務(wù)，為了最大化加速BP成像過(guò)程，經(jīng)過(guò)距離壓縮后，每個(gè)脈沖內(nèi)的數(shù)據(jù)對(duì)應(yīng)一個(gè)Map任務(wù)并行對(duì)成像場(chǎng)景網(wǎng)格點(diǎn)遍歷計(jì)算是理想的并行化方案。但是，由于MapReduce每個(gè)Map任務(wù)對(duì)應(yīng)一個(gè)進(jìn)程，進(jìn)程的開(kāi)啟存在必要的時(shí)間開(kāi)銷(xiāo)和后續(xù)數(shù)據(jù)聚合耗時(shí)，每個(gè)脈沖對(duì)應(yīng)一個(gè)進(jìn)程反而會(huì)降低計(jì)算效率。因此，將多個(gè)脈沖內(nèi)的數(shù)據(jù)劃分成一個(gè)數(shù)據(jù)塊，一個(gè)數(shù)據(jù)塊對(duì)應(yīng)一個(gè)進(jìn)程，該進(jìn)程串行處理每個(gè)脈沖內(nèi)的數(shù)據(jù)，多個(gè)數(shù)據(jù)塊對(duì)應(yīng)多個(gè)進(jìn)程并行執(zhí)行是一個(gè)切合實(shí)際的并行化方案。在數(shù)據(jù)并行處理的過(guò)程中，需要防止一些Map任務(wù)計(jì)算量較大，導(dǎo)致計(jì)算時(shí)間較長(zhǎng)，拖慢整個(gè)MapReduce程序的運(yùn)行。因此，對(duì)輸入數(shù)據(jù)的分塊需要均衡每個(gè)Map任務(wù)的計(jì)算量，避免發(fā)生數(shù)據(jù)傾斜。

此外，在MR-BP方法中，每個(gè)Map任務(wù)對(duì)三維場(chǎng)景遍歷之后產(chǎn)生大量的鍵值對(duì)數(shù)據(jù)，這部分鍵值對(duì)的value是成像場(chǎng)景水平面的二維成像矩陣，key是垂直方向的坐標(biāo)值，若將這部分鍵值對(duì)數(shù)據(jù)都復(fù)制到Reduce階段統(tǒng)一進(jìn)行相參累加，則會(huì)導(dǎo)致消耗較多的磁盤(pán)資源和網(wǎng)絡(luò)資源，Reduce階段的串行計(jì)算量也較大。因此，在不影響方法成像結(jié)果的前提下，在Mapper函數(shù)與Reducer函數(shù)之間設(shè)置一個(gè)Combiner函數(shù)，用于將相同key值對(duì)應(yīng)的value進(jìn)行相參累加，聚合部分鍵值對(duì)，減少落入磁盤(pán)的數(shù)據(jù)量，降低數(shù)據(jù)復(fù)制時(shí)的網(wǎng)絡(luò)負(fù)擔(dān)，減少Reduce階段的串行計(jì)算量，有效縮減MR-BP方法的計(jì)算時(shí)間。

Map階段詳細(xì)的步驟如下。

(1)將第二距離像矩陣按行均分(若存在余數(shù)，余數(shù)部分可另作1塊)，共分成K塊。

(2)每個(gè)任務(wù)的Mapper函數(shù)根據(jù)經(jīng)典BP算法逐一處理每個(gè)脈沖內(nèi)的數(shù)據(jù)，對(duì)三維直角坐標(biāo)系內(nèi)的場(chǎng)景網(wǎng)格點(diǎn)進(jìn)行遍歷計(jì)算。每個(gè)脈沖內(nèi)的數(shù)據(jù)處理結(jié)果以的形式輸出，key為z軸的坐標(biāo)值，value為xOy平面的二維成像矩陣。

(3)Reduce階段的任務(wù)數(shù)根據(jù)Map階段輸出的數(shù)據(jù)量設(shè)定，現(xiàn)在假設(shè)Reduce階段的任務(wù)數(shù)為2。所以，每個(gè)Map任務(wù)將Mapper函數(shù)輸出的數(shù)據(jù)根據(jù)鍵值對(duì)的key值劃分成2個(gè)分區(qū)，保證相同key值的鍵值對(duì)在同一個(gè)分區(qū)內(nèi)，運(yùn)行Combiner函數(shù)將相同key值對(duì)應(yīng)的value進(jìn)行相參累加。

2.3 Reduce階段

MR-BP方法的Reduce階段完成每個(gè)Map任務(wù)計(jì)算結(jié)果的復(fù)制、合并和相參累加,并把成像數(shù)據(jù)輸出到HDFS。詳細(xì)的步驟如下。

(1)Reduce任務(wù)復(fù)制對(duì)應(yīng)分區(qū)的成像過(guò)程數(shù)據(jù)。

(2)每個(gè)Reduce任務(wù)合并數(shù)據(jù)文件。

(3)合并后的數(shù)據(jù)文件輸入到Reducer函數(shù)，Reducer函數(shù)將key相同的value進(jìn)行相參累加。

(4)相參累加的結(jié)果作為value、key保持不變，以的形式寫(xiě)到HDFS,完成三維成像數(shù)據(jù)的計(jì)算。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文方法的有效性，實(shí)驗(yàn)使用4臺(tái)相同配置的物理計(jì)算機(jī)搭建Hadoop分布式計(jì)算平臺(tái)(下文也稱(chēng)之為集群)，包含4個(gè)計(jì)算節(jié)點(diǎn)，其中一個(gè)計(jì)算節(jié)點(diǎn)同時(shí)作為主節(jié)點(diǎn)(主節(jié)點(diǎn)是指負(fù)責(zé)管理數(shù)據(jù)存儲(chǔ)地址和資源調(diào)度的計(jì)算機(jī))，具體硬件信息和軟件版本如表1所示。單機(jī)計(jì)算平臺(tái)是集群中的單臺(tái)物理計(jì)算機(jī)。實(shí)驗(yàn)所用數(shù)據(jù)來(lái)源于Feko電磁仿真軟件的三維成像雷達(dá)回波仿真，因此成像場(chǎng)景只是單一的汽車(chē)模型。成像的大小為50×50×20 pixel。

表1 實(shí)驗(yàn)環(huán)境配置Table 1 Experimental environment configuration

3.1 成像準(zhǔn)確性分析

MR-BP方法是針對(duì)BP算法在大場(chǎng)景高分辨率成像時(shí)數(shù)據(jù)處理速度的優(yōu)化，在數(shù)值計(jì)算上與單機(jī)計(jì)算的BP成像方法相同。對(duì)于MR-BP方法成像的準(zhǔn)確性驗(yàn)證，實(shí)驗(yàn)結(jié)果表明相對(duì)于單機(jī)計(jì)算的BP成像方法的成像結(jié)果，MR-BP方法的成像結(jié)果在每個(gè)像素點(diǎn)的數(shù)值誤差均小于10-10%。實(shí)驗(yàn)成像場(chǎng)景中的汽車(chē)模型如圖4(a)所示，單機(jī)計(jì)算的BP成像方法成像結(jié)果如圖4(b)所示，MR-BP方法成像結(jié)果如圖4(c)所示?？梢?jiàn)，對(duì)于MR-BP方法與單機(jī)計(jì)算的BP成像方法，兩者的成像質(zhì)量相當(dāng)。

圖4 成像場(chǎng)景圖與實(shí)驗(yàn)成像圖Fig.4 The imaging scene image and experimental imaging images

3.2 輸入數(shù)據(jù)分塊數(shù)對(duì)計(jì)算效率的影響

在MR-BP方法方位向成像中，一個(gè)輸入數(shù)據(jù)分塊對(duì)應(yīng)啟動(dòng)一個(gè)Map任務(wù)。若輸入數(shù)據(jù)分塊數(shù)過(guò)小，會(huì)導(dǎo)致Map任務(wù)啟動(dòng)過(guò)少，集群資源利用率過(guò)低，計(jì)算時(shí)間較長(zhǎng)；若輸入數(shù)據(jù)分塊數(shù)過(guò)多，啟動(dòng)的Map任務(wù)也較多，雖然保證了集群資源的利用率，但是過(guò)多的Map任務(wù)會(huì)帶來(lái)巨大的任務(wù)啟動(dòng)開(kāi)銷(xiāo)和數(shù)據(jù)存儲(chǔ)與傳輸?shù)暮臅r(shí)，也會(huì)使得計(jì)算時(shí)間較長(zhǎng)。為了驗(yàn)證上述的理論分析，實(shí)驗(yàn)測(cè)試了在不同輸入數(shù)據(jù)分塊數(shù)下MR-BP方法方位向成像的計(jì)算時(shí)間，多次實(shí)驗(yàn)取均值的結(jié)果如圖5所示?？梢?jiàn)，輸入數(shù)據(jù)的分塊數(shù)需要根據(jù)集群計(jì)算資源和處理輸入數(shù)據(jù)的計(jì)算量確定，分塊數(shù)過(guò)小或者過(guò)大，都會(huì)降低MR-BP方法方位向成像的計(jì)算效率。本實(shí)驗(yàn)環(huán)境下輸入數(shù)據(jù)的較優(yōu)分塊數(shù)為36。

圖5 不同的輸入數(shù)據(jù)分塊數(shù)對(duì)MR-BP方法方位向成像計(jì)算時(shí)間的影響Fig.5 Influence of different input data block numbers for computational time of MR-BP method azimath imaging

3.3 加速性能分析

在MR-BP方法方位向成像的輸入數(shù)據(jù)分塊數(shù)為36時(shí)，計(jì)算節(jié)點(diǎn)數(shù)量不同的集群分別進(jìn)行多次實(shí)驗(yàn)，取均值的結(jié)果如圖6所示。

圖6 單機(jī)計(jì)算的BP方位向成像方法與MR-BP方法方位向成像的計(jì)算時(shí)間對(duì)比Fig.6 Comparison of calculation time between BP azimuth imaging method calculated by a single machine and azimuth imaging of MR-BP method

當(dāng)計(jì)算節(jié)點(diǎn)數(shù)為1時(shí)，MR-BP方法方位向成像在Hadoop分布式計(jì)算平臺(tái)中執(zhí)行，由于存在多進(jìn)程啟動(dòng)和等待磁盤(pán)讀寫(xiě)的耗時(shí)，相對(duì)于單機(jī)計(jì)算的BP方位向成像方法，MR-BP方法方位向成像的計(jì)算時(shí)間稍長(zhǎng)。但是，隨著集群計(jì)算節(jié)點(diǎn)的增加，MR-BP方法方位向成像的計(jì)算時(shí)間逐漸減少，當(dāng)計(jì)算節(jié)點(diǎn)數(shù)為4時(shí)，單機(jī)計(jì)算的BP方位向成像方法的計(jì)算時(shí)間是MR-BP方法方位向成像的3.7倍，可見(jiàn)，MR-BP方法具備加速BP成像的能力。

4 結(jié)論

針對(duì)BP算法在大場(chǎng)景下高分辨率成像的時(shí)延較長(zhǎng)，采用GPU加速的計(jì)算平臺(tái)顯存和擴(kuò)展性不足的問(wèn)題，基于MapReduce的分布式并行化計(jì)算能力，結(jié)合BP算法對(duì)數(shù)據(jù)處理的流程，提出了一種基于MapReduce的合成孔徑雷達(dá)后向投影快速成像方法。該方法對(duì)BP成像的加速能力在實(shí)驗(yàn)中得到了驗(yàn)證，其依托的Hadoop分布式計(jì)算平臺(tái)，具備海量數(shù)據(jù)交互與大批量數(shù)據(jù)處理的能力，計(jì)算平臺(tái)可橫向擴(kuò)展計(jì)算節(jié)點(diǎn)以提高平臺(tái)的計(jì)算能力，擴(kuò)展性充足，且成本較低，有效解決基于GPU加速的BP成像方法存在的不足。