唐江文 鄧云凱 王 宇 李 寧

?

Bulk-FFBP：基于距離向整體處理的快速分解后向投影算法

唐江文*①②鄧云凱①王 宇①李 寧①

①(中國科學(xué)院電子學(xué)研究所 北京 100190)②(中國科學(xué)院大學(xué) 北京 100049)

距離向分塊快速分解后向投影(Block-FFBP)算法通過子孔徑合成降低了傳統(tǒng)BP的算法復(fù)雜度，并且通過距離向分塊，簡(jiǎn)化了繁瑣的極坐標(biāo)與直角坐標(biāo)的轉(zhuǎn)換。然而，距離分塊操作使各塊引入了斜距范圍波動(dòng)，而且插值核長(zhǎng)度余量導(dǎo)致了算法的內(nèi)存效率低下，從而降低了成像效率。該文提出一種基于距離向整體處理的Bulk-FFBP算法，并細(xì)分為基于距離向控制點(diǎn)的Bulk-FFBP以及無控制點(diǎn)的Bulk-FFBP。文中通過仿真對(duì)兩種Bulk-FFBP算法進(jìn)行了誤差分析、成像性能分析以及算法效率分析，并與Block-FFBP算法進(jìn)行對(duì)比，證實(shí)了Bulk-FFBP的優(yōu)越性。

合成孔徑雷達(dá)；后向投影算法；快速BP算法

1 引言

后向投影(Back-Projection, BP)算法是一種精確有效的合成孔徑雷達(dá)(SAR)成像算法[1]，該算法在時(shí)域?qū)崿F(xiàn)聚焦，因而能夠很好地解決很多頻域成像算法遇到的難題，比如距離徙動(dòng)、SAR傳感器的非直線飛行軌跡、方位空變等[2,3]。BP算法復(fù)雜度為(3)，高于一般頻域成像算法的復(fù)雜度(2lg)，這成為限制其廣泛使用的巨大障礙。在使用BP算法進(jìn)行成像時(shí)，一般都需要性能強(qiáng)勁的計(jì)算平 臺(tái)，然而，借助于計(jì)算平臺(tái)并不能改變BP算法(3)計(jì)算復(fù)雜度的事實(shí)。

快速BP算法對(duì)BP算法結(jié)構(gòu)進(jìn)行了改進(jìn)，利用了子孔徑角頻率帶寬有限的性質(zhì)[7]，將全孔徑積分分割成子孔徑積分的組合，以降低計(jì)算復(fù)雜度。其中文獻(xiàn)[8]采用了兩級(jí)算法結(jié)構(gòu)實(shí)現(xiàn)了計(jì)算復(fù)雜度為(2.5)的快速BP算法，文獻(xiàn)[9]采用多級(jí)算法結(jié)構(gòu)實(shí)現(xiàn)了計(jì)算復(fù)雜度為(2lg)的快速BP算法。文獻(xiàn)[10]提出了快速分解BP算法(Fast Factorized Back-Projection, FFBP)，并對(duì)斜距誤差進(jìn)行了分析，另外還提出了在距離向分塊的FFBP算法(Block-FFBP)，簡(jiǎn)化了極坐標(biāo)與直角坐標(biāo)之間繁瑣的轉(zhuǎn)化計(jì)算。文獻(xiàn)[11]提出了一種結(jié)合波數(shù)域頻譜拼接的快速BP算法，但仍在極坐標(biāo)系下進(jìn)行，并且子孔徑成像之后采用了類似極坐標(biāo)格式算法(PFA)的頻域處理，一定程度上喪失了BP不受波前彎曲影響的特點(diǎn)[1]。文獻(xiàn)[12,13]對(duì)FFBP算法進(jìn)行了改進(jìn)，但成像操作仍然是在極坐標(biāo)系下進(jìn)行的。

文獻(xiàn)[10]中指出，Block-FFBP算法缺陷在于增加了算法需要的內(nèi)存空間，這是因?yàn)榉纸膺^程中每一塊對(duì)應(yīng)的斜距范圍不同，需要的存儲(chǔ)空間存在波動(dòng)；另一方面Block-FFBP使用插值核進(jìn)行插值，需要一定余量以保證邊緣點(diǎn)的插值效果。文獻(xiàn)[14]給出了一種優(yōu)化的分塊策略，但并沒有完全消除分塊帶來的問題。本文對(duì)Block-FFBP算法進(jìn)行改進(jìn)和優(yōu)化，提出了一種對(duì)相同方位向的波束進(jìn)行整體處理的Bulk-FFBP算法，降低了額外的內(nèi)存消耗，提升了算法的計(jì)算效率，且更加易于實(shí)現(xiàn)。

接下來的內(nèi)容安排如下，第2節(jié)對(duì)Block-FFBP進(jìn)行介紹，并指出Block-FFBP存在的缺陷；第3節(jié)對(duì)Bulk-FFBP算法進(jìn)行詳細(xì)的描述和分析；第4節(jié)對(duì)Bulk-FFBP算法進(jìn)行仿真驗(yàn)證；最后對(duì)本文進(jìn)行了總結(jié)。

2 Block-FFBP算法

2.1 Block-FFBP算法基本步驟

Block-FFBP算法是在FFBP算法的基礎(chǔ)上，對(duì)距離向進(jìn)行分塊處理。以基數(shù)為2的8孔徑Block-FFBP為例(如圖1)，在SAR飛行軌跡上有8個(gè)孔徑，每個(gè)孔徑對(duì)應(yīng)一個(gè)指向成像場(chǎng)景的波束，第1步如圖1(a)，將相鄰兩個(gè)孔徑進(jìn)行子孔徑合成，同時(shí)在距離向上進(jìn)行分塊，這樣就得到了右側(cè)方位向和距離向2×2的4個(gè)波束，而孔徑減少了一半，變?yōu)?孔徑；第2步分解為圖1(b)右側(cè)的2孔徑，16波束；同理第3步得到圖1(c)右側(cè)的1孔徑，64波束。當(dāng)然，分解的層數(shù)以及選用的基數(shù)可自由選擇，最后通過一步傳統(tǒng)BP算法實(shí)現(xiàn)最終成像。由于經(jīng)過多級(jí)分解，場(chǎng)景尺寸小了，孔徑數(shù)也少了，最終的BP成像計(jì)算量也就大大降低了。

圖1 基數(shù)為2的8孔徑Block-FFBP各級(jí)子孔徑合成示意圖

2.2 Block-FFBP存在的問題

普通的FFBP算法，是通過繁復(fù)的極坐標(biāo)和直角坐標(biāo)轉(zhuǎn)換來確定成像點(diǎn)與新舊孔徑之間斜距的關(guān)系，而Block-FFBP的波束指向中心點(diǎn)是在直角坐標(biāo)系中直接選定的，計(jì)算出中心點(diǎn)到孔徑斜距，也就確定了當(dāng)前塊到孔徑的中心斜距，塊內(nèi)其他點(diǎn)的斜距為中心斜距加減一個(gè)斜距范圍，從而簡(jiǎn)化了計(jì)算。

Block-FFBP也存在一些問題，一方面，新孔徑在合成過程中需要進(jìn)行插值操作，由于距離向分塊，數(shù)據(jù)不斷被截?cái)啵瑹o法通過統(tǒng)一的FFT進(jìn)行插值，只能通過插值核進(jìn)行，而插值核是有一定長(zhǎng)度的，為了保證斜距邊緣點(diǎn)的插值效果，波束數(shù)據(jù)長(zhǎng)度需要有一定的插值余量，隨著分解級(jí)數(shù)增多，插值余量所占的空間比例越來越大，導(dǎo)致內(nèi)存空間需求不斷增長(zhǎng)(如圖2)。另一方面，即使不考慮插值余量所占空間，有效數(shù)據(jù)由前一級(jí)孔徑合成到新一級(jí)孔徑時(shí)，所需要的內(nèi)存空間也并不完全一致，會(huì)產(chǎn)生波動(dòng)。

總之，從算法實(shí)現(xiàn)的角度來看，Block-FFBP需要更多的內(nèi)存空間，并且內(nèi)存空間的動(dòng)態(tài)增長(zhǎng)會(huì)降低算法的計(jì)算效率。

3 Bulk-FFBP算法

3.1 基于距離向控制點(diǎn)的Bulk-FFBP

Block-FFBP的缺陷在于，分塊操作導(dǎo)致內(nèi)存需求會(huì)增長(zhǎng)。這里給出一種Bulk-FFBP算法，主要思想是不在距離向上進(jìn)行分塊，而是選取一些固定的控制點(diǎn)，來確立成像點(diǎn)到新舊孔徑斜距之間的關(guān)系。

圖2 Block-FFBP插值核余量需求空間不斷增長(zhǎng)

圖3 Bulk-FFBP對(duì)于方位向相同的波束在距離向選擇數(shù)量固定的控制點(diǎn)

圖4給出了局部放大圖，B(x,,)是成像平面內(nèi)的一個(gè)波束控制點(diǎn)，設(shè)斜距1B的長(zhǎng)度為1i，斜距2B的長(zhǎng)度為2i，孔徑合成后AB的長(zhǎng)度為l，則B到3個(gè)孔徑的回波延遲分別為

其中，c為光速。設(shè)孔徑1的距離壓縮回波為1()，孔徑2的距離壓縮回波為2()，孔徑的距離壓縮回波為()，那么子孔徑合成的過程可表示為

(2)

其中，0為SAR信號(hào)的載頻。對(duì)于一對(duì)對(duì)應(yīng)的延遲時(shí)間{t,t}，可以設(shè)計(jì)一組插值函數(shù)，表征合成后孔徑的回波延遲到合成前各孔徑A回波延遲的映射關(guān)系，即

把插值函數(shù)代入式(2)就可以得到

(4)

式(4)就是孔徑1,2到的子孔徑合成公式，可以看出通過插值得到了子孔徑合成的連續(xù)表達(dá)式，不再存在Block-FFBP中數(shù)據(jù)截?cái)嗟膯栴}，相同方位向的波束回波成為一個(gè)整體，所以稱為Bulk- FFBP，如此一來，對(duì)回波數(shù)據(jù)的插值就可以通過整體的FFT升采樣來進(jìn)行，提高了插值效率。

3.2 無控制點(diǎn)的Bulk-FFBP

在前面的基礎(chǔ)上，我們對(duì)l和l(=1,2)的展開形式進(jìn)行分析，有

(6)

將式(1)代入式(6)可得

如果將離散的{t,t}替換為連續(xù)的{t,}，則有

(8)

這樣就直接得到了當(dāng)前孔徑回波延遲和下一級(jí)孔徑回波延遲之間的關(guān)系，式(4)也就可以寫為

這樣就把回波延遲的表示方式由基于控制點(diǎn)的插值轉(zhuǎn)換為具體的解析表達(dá)式，減少了計(jì)算量。如果沒有水平直線飛行的前提條件，那么也可以從式(5)推出更嚴(yán)格的形式，形式較繁復(fù)，在此不再展開。以上展示的是基數(shù)為2的孔徑合成，其實(shí)也可以擴(kuò)展到其他整數(shù)基數(shù)上。同樣，無控制點(diǎn)Bulk- FFBP也可以使用FFT升采樣進(jìn)行高效的插值計(jì)算。圖5給出了兩種Bulk-FFBP的算法流程圖，可以看出兩種算法的區(qū)別是，控制點(diǎn)Bulk-FFBP的斜距來自基于控制點(diǎn)的擬合，而無控制點(diǎn)Bulk-FFBP的斜距來自直接計(jì)算。

圖5 兩種Bulk-FFBP的算法流程圖

3.3 誤差分析

接下來，我們對(duì)Bulk-FFBP的斜距誤差以及Block-FFBP的斜距誤差進(jìn)行對(duì)比。Block-FFBP的斜距誤差來源于，成像點(diǎn)到新舊孔徑的回波延遲并不一致，對(duì)于Block-FFBP來說只有場(chǎng)景塊中心點(diǎn)到新舊回波延遲可以保證一致，其他成像點(diǎn)都存在誤差。圖6示意了Block-FFBP某塊場(chǎng)景，圖中當(dāng)前孔徑為，上一級(jí)某孔徑為A，場(chǎng)景塊中心點(diǎn)為，塊中任意點(diǎn)，斜距,,AB,AC的長(zhǎng)度分別表示為l,l,l,l,點(diǎn)由于位于場(chǎng)景中心，不存在斜距誤差，而對(duì)于點(diǎn)，它相對(duì)上一級(jí)孔徑A的斜距為l，而通過當(dāng)前孔徑映射到上一級(jí)孔徑A的斜距為，因此點(diǎn)的斜距誤差為

設(shè)l,l,l,l對(duì)應(yīng)的回波延遲時(shí)間為t,t,t,t，那么式(10)表示成傳播延遲誤差則為

(11)

對(duì)于Bulk-FFBP，假設(shè)使用式(4)控制點(diǎn)的方法，為距離向控制點(diǎn)之一，結(jié)合式(3)，點(diǎn)的回波延遲誤差可以表示為

同樣，如果使用式(9)無控制點(diǎn)方法，結(jié)合式(8)，式(9)，點(diǎn)的回波延遲誤差為

(13)

下面通過數(shù)值的方法對(duì)block(),bulk1()和bulk2()進(jìn)行分析對(duì)比。參照?qǐng)D6，設(shè)置情景為水平直線飛行的機(jī)載SAR，高度為8000 m，下視角為, C波段，載頻為5.4 GHz，設(shè)置不同的斜視角分別為，孔徑和A之間的間隔|AA|分別為1 m, 10 m, 100 m, 1000 m，選取的矩形場(chǎng)景大小以1()引起的相位誤差不超過為準(zhǔn)，即，然后繪制出場(chǎng)景內(nèi)500×500點(diǎn)中相位誤差1(),2()和3()各自的最大值，結(jié)果如圖7所示，圖中相對(duì)進(jìn)行了歸一化，其中控制點(diǎn)Bulk-FFBP算法中的使用的是3次樣條插值。圖中被虛線分隔開的區(qū)域?qū)?yīng)不同的斜視角，同一區(qū)域內(nèi)不同的點(diǎn)對(duì)應(yīng)不同的孔徑間隔，孔徑間隔順序?yàn)? m, 10 m, 100 m, 1000 m，可以看出在孔徑間隔小斜視角度小的情況下，Bulk-FFBP與Block-FFBP相差不大，而當(dāng)孔徑間隔增大或者斜視角度增大時(shí)，Bulk-FFBP的相位誤差就逐漸小于Block-FFBP，因此從誤差分析的角度來看，Bulk- FFBP是優(yōu)于Block-FFBP的。

圖6 Block-FFBP與Bulk-FFBP誤差分析模型

圖7 兩種Bulk-FFBP與Block-FFBP相位誤差對(duì)比

4 仿真實(shí)驗(yàn)

4.1 點(diǎn)目標(biāo)性能對(duì)比

為了對(duì)Bulk-FFBP和Block-FFBP有更加直觀的印象，這里設(shè)計(jì)了一組X波段星載聚束SAR仿真參數(shù)進(jìn)行點(diǎn)目標(biāo)性能對(duì)比，具體參數(shù)如表1所示。

表1 X波段星載聚束SAR仿真參數(shù)

場(chǎng)景中心設(shè)置了點(diǎn)目標(biāo)，仿真得到的回波尺寸為方位向20000點(diǎn)，距離向24000點(diǎn)，然后分別使用Block-FFBP、控制點(diǎn)Bulk-FFBP、無控制點(diǎn)Bulk-FFBP對(duì)回波進(jìn)行基數(shù)分別為4, 4, 5, 5的4級(jí)分解成像處理，其中控制點(diǎn)Bulk-FFBP在距離向均勻等距設(shè)置30個(gè)控制點(diǎn)，采用3次樣條插值。成像大小為12000×12000，場(chǎng)景尺寸為2 km× 2 km。

3種算法的點(diǎn)目標(biāo)成像結(jié)果及距離向和方位向剖面如圖8所示，表2給出了該點(diǎn)目標(biāo)的具體性能指標(biāo)，從表中可以看出，在距離向上，兩種Bulk- FFBP算法的峰值旁瓣比PSLR優(yōu)于Block-FFBP約2.2 dB，積分旁瓣比ISLR優(yōu)于Block-FFBP約3.7 dB，這是因?yàn)锽lock-FFBP算法由于數(shù)據(jù)截?cái)酂o法使用FFT進(jìn)行插值，而使用了8點(diǎn)sinc插值，在逐級(jí)的sinc插值過程中，振鈴現(xiàn)象被放大[15]，而兩種Bulk-FFBP采用的是FFT升采樣插值；在方位向上，兩種Bulk-FFBP略優(yōu)于Block-FFBP約0.1 dB。

4.2 算法效率對(duì)比

接下來對(duì)Block-FFBP以及兩種Bulk-FFBP算法的運(yùn)算效率進(jìn)行對(duì)比，3種算法都使用單線程運(yùn)行。為了便于分析，我們對(duì)距離壓縮后的數(shù)據(jù)進(jìn)行了裁剪，以縮短成像時(shí)間，裁剪后方位向?yàn)?048個(gè)點(diǎn)，距離向?yàn)?024點(diǎn)，之后進(jìn)行基數(shù)為4的分解成像處理，成像大小為1024×1024。

表3給出了3種算法的運(yùn)行時(shí)間及相對(duì)傳統(tǒng)BP的加速比(倍)，可以看出3種算法的速度相對(duì)于傳統(tǒng)BP都有提升，而且隨分解級(jí)數(shù)的增多，加速比也在增加，兩種Bulk-FFBP算法整體上比Block- FFBP的速度更快，這是因?yàn)锽lock-FFBP距離向分塊內(nèi)存效率低下，并影響了計(jì)算效率。尤其是，在5級(jí)分解時(shí)，Block-FFBP的加速比相對(duì)于4級(jí)分解反而降低了，這是因?yàn)椴逯涤嗔克嫉目臻g超過了有效數(shù)據(jù)本身的空間，導(dǎo)致計(jì)算效率嚴(yán)重下降。

圖8 Block-FFBP與兩種Bulk-FFBP點(diǎn)目標(biāo)成像對(duì)比

表2 點(diǎn)目標(biāo)性能對(duì)比

表3 不同分解級(jí)數(shù)成像用時(shí)(s)及加速比(倍)

5 總結(jié)

本文針對(duì)Block-FFBP算法由于距離向分塊造成的數(shù)據(jù)截?cái)嗉靶势款i問題，提出了基于距離向整體處理的Bulk-FFBP算法，在算法的推導(dǎo)過程，又將Bulk-FFBP算法細(xì)分為兩種，一種是基于距離向控制點(diǎn)的Bulk-FFBP算法，另一種是無控制點(diǎn)的Bulk-FFBP算法。文中通過誤差分析、成像性能分析以及算法效率分析，證實(shí)了這兩種Bulk-FFBP算法相對(duì)于Block-FFBP算法的優(yōu)越性。

[1] DESAI M D and JENKINS W K. Convolution backprojection image reconstruction for spotlight mode synthetic aperture radar[J]., 1992, 1(4): 505-517. doi: 10.1109/83.199920.

[2] SOUMEKH M. Synthetic Aperture Radar Signal Processing with MATLAB Algorithms[M]. New York, Wiley, 1999: 212-215.

[3] MENG D, HU D, and DING C. Precise focusing of airborne SAR data with wide apertures large trajectory deviations: a chirp modulated back-projection approach[J]., 2015, 53(5): 2510-2519. doi: 10.1109/TGRS.2014.2361134.

[4] CAPOZZOLI A, CURCIO C, and LISENO A. Fast GPU- based interpolation for SAR backprojection[J]., 2013, 133: 259-283.

[5] FREY O, WERNER C L, and WEGMULLER U. GPU- based parallelized time-domain back-projection processing for Agile SAR platforms[C]. IEEE International Geoscience and Remote Sensing Symposium (IGARSS). Quebec City, Canada, 2014: 1132-1135.

[6] PRITSKER D. Efficient global back-projection on an FPGA[C]. IEEE Radar Conference. Arlington, VA, USA, 2015: 0204-0209.

[7] BASU S and BRESLER Y.(2log2) filtered backprojection reconstruction algorithm for tomography[J]., 2000, 9(10): 1760-1773. doi: 10.1109/83.869187.

[8] YEGULALP A F. Fast backprojection algorithm for synthetic aperture radar[C]. Proceedings of 1999 IEEE Radar Conference, Waltham, MA, USA, 1999: 60-65.

[9] XIAO S, MUNSON J D C, BASU S,. An2logback-projection algorithm for SAR image formation[C]. Thirty-Fourth IEEE Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, 2000, 1: 3-7.

[10] ULANDER L M H, HELLSTEN H, and STENSTROM G. Synthetic-aperture radar processing using fast factorized back-projection[J]., 2003, 39(3): 760-776. doi: 10.1109/TAES. 2003.1238734.

[11] ZHANG L, LI H, QIAO Z,. A fast BP algorithm with wavenumber spectrum fusion for high-resolution spotlight SAR imaging[J]., 2014, 11(9): 1460-1464. doi: 10.1109/LGRS.2013. 2295326.

[12] 左紹山, 楊澤民, 孫光才, 等. 基于幾何校正的聚束SAR快速分級(jí)后向投影算法[J]. 電子與信息學(xué)報(bào), 2015, 37(6): 1389-1394. doi: 10.11999/JEIT141254.

ZUO Shaoshan, YANG Zemin, SUN Guangcai,. Geometric correction based fast factorized back projection algorithm for spotlight SAR imaging[J].&, 2015, 37(6): 1389-1394. doi: 10.11999/JEIT141254.

[13] 楊澤民, 孫光才, 吳玉峰, 等. 一種新的基于極坐標(biāo)格式的快速后向投影算法[J]. 電子與信息學(xué)報(bào), 2014, 36(3): 537-544. doi: 10.3724/SP.J.1146.2013.000613.

YANG Zemin, SUN Guangcai, WU Yufeng,. A new fast back projection algorithm based on polar format algorithm[J].&, 2014, 36(3): 537-544. doi: 10.3724/SP.J.1146.2013.000613.

[14] JIANG X, WANG J, QIAN S,. SAR imaging using fast factorized backprojection based on optimal regional partition [C]. IEEE Radar Conference. Cincinnati, OH, USA, 2014: 0229-0232.

[15] CUMMING I G and WONG F H. Digital Processing of Synthetic Aperture Radar Data: Algorithms and Implementation[M]. London, Artech House, 2005: 52-59.

Bulk-FFBP: Fast Factorized Back-projection Algorithm Based on Range Bulk Processing

TANG Jiangwen①②DENG Yunkai①WANG Robert①LI Ning①

①(,,100190,)②(,100049,)

Block Fast Factorized Back-Projection (Block-FFBP) algorithm adopts a subaperture synthesis approach to reduce the computing complexity of the conventional BP algorithm, and partitions the echo data into blocks in range to avoid the complicated transforms between polar and Cartesian coordinates. However, Block- FFBP results in a range span vibration of the data blocks, and Block-FFBP needs an extra data length associated with the interpolation kernel. That gives rise to the inefficiency of the memory, and furthermore the degradation of the imaging speed. A range Bulk processing based FFBP (Bulk-FFBP) algorithm is proposed in this paper. It is implemented in two ways. One is based on a series of range pivots, and the other one is of no pivots. The outperformance of Bulk-FFBP relative to Block-FFBP is verified through simulations in error analysis, imaging evaluation and computing efficiency test.

Synthetic Aperture Radar (SAR); Back-Projection (BP) algorithm; Fast BP algorithm

TN957.52

A

1009-5896(2017)02-0405-07

10.11999/JEIT160373

2016-04-18；改回日期：2016-06-20；

2016-09-08

唐江文 jiangwen@mail.ustc.edu.cn

中國科學(xué)院“百人計(jì)劃”(61422113)，國家“萬人計(jì)劃”

The “Hundred Talents Program” of the Chinese Academy of Sciences (61422113), The National Ten Thousand Talent Program-Young Top-Notch Talent Program

唐江文： 男，1988年生，博士生，研究方向?yàn)镾AR時(shí)域成像算法及大規(guī)模并行計(jì)算.

鄧云凱： 男，1962年生，研究員，博士生導(dǎo)師，研究方向?yàn)樾禽dSAR系統(tǒng)設(shè)計(jì)、成像及微波遙感理論.

王 宇： 男，1980年生，研究員，博士生導(dǎo)師，研究方向?yàn)樾禽dSAR系統(tǒng)設(shè)計(jì)及信號(hào)處理.