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

唐江文 鄧云凱 王 宇 李 寧

?

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

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

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

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

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

1 引言

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

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

文獻[10]中指出，Block-FFBP算法缺陷在于增加了算法需要的內存空間，這是因為分解過程中每一塊對應的斜距范圍不同，需要的存儲空間存在波動；另一方面Block-FFBP使用插值核進行插值，需要一定余量以保證邊緣點的插值效果。文獻[14]給出了一種優化的分塊策略，但并沒有完全消除分塊帶來的問題。本文對Block-FFBP算法進行改進和優化，提出了一種對相同方位向的波束進行整體處理的Bulk-FFBP算法，降低了額外的內存消耗，提升了算法的計算效率，且更加易于實現。

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

2 Block-FFBP算法

2.1 Block-FFBP算法基本步驟

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

圖1 基數為2的8孔徑Block-FFBP各級子孔徑合成示意圖

2.2 Block-FFBP存在的問題

普通的FFBP算法，是通過繁復的極坐標和直角坐標轉換來確定成像點與新舊孔徑之間斜距的關系，而Block-FFBP的波束指向中心點是在直角坐標系中直接選定的，計算出中心點到孔徑斜距，也就確定了當前塊到孔徑的中心斜距，塊內其他點的斜距為中心斜距加減一個斜距范圍，從而簡化了計算。

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

總之，從算法實現的角度來看，Block-FFBP需要更多的內存空間，并且內存空間的動態增長會降低算法的計算效率。

3 Bulk-FFBP算法

3.1 基于距離向控制點的Bulk-FFBP

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

圖2 Block-FFBP插值核余量需求空間不斷增長

圖3 Bulk-FFBP對于方位向相同的波束在距離向選擇數量固定的控制點

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

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

(2)

其中，0為SAR信號的載頻。對于一對對應的延遲時間{t,t}，可以設計一組插值函數，表征合成后孔徑的回波延遲到合成前各孔徑A回波延遲的映射關系，即

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

(4)

式(4)就是孔徑1,2到的子孔徑合成公式，可以看出通過插值得到了子孔徑合成的連續表達式，不再存在Block-FFBP中數據截斷的問題，相同方位向的波束回波成為一個整體，所以稱為Bulk- FFBP，如此一來，對回波數據的插值就可以通過整體的FFT升采樣來進行，提高了插值效率。

3.2 無控制點的Bulk-FFBP

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

(6)

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

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

(8)

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

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

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

3.3 誤差分析

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

設l,l,l,l對應的回波延遲時間為t,t,t,t，那么式(10)表示成傳播延遲誤差則為

(11)

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

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

(13)

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

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

圖7 兩種Bulk-FFBP與Block-FFBP相位誤差對比

4 仿真實驗

4.1 點目標性能對比

為了對Bulk-FFBP和Block-FFBP有更加直觀的印象，這里設計了一組X波段星載聚束SAR仿真參數進行點目標性能對比，具體參數如表1所示。

表1 X波段星載聚束SAR仿真參數

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

3種算法的點目標成像結果及距離向和方位向剖面如圖8所示，表2給出了該點目標的具體性能指標，從表中可以看出，在距離向上，兩種Bulk- FFBP算法的峰值旁瓣比PSLR優于Block-FFBP約2.2 dB，積分旁瓣比ISLR優于Block-FFBP約3.7 dB，這是因為Block-FFBP算法由于數據截斷無法使用FFT進行插值，而使用了8點sinc插值，在逐級的sinc插值過程中，振鈴現象被放大[15]，而兩種Bulk-FFBP采用的是FFT升采樣插值；在方位向上，兩種Bulk-FFBP略優于Block-FFBP約0.1 dB。

4.2 算法效率對比

接下來對Block-FFBP以及兩種Bulk-FFBP算法的運算效率進行對比，3種算法都使用單線程運行。為了便于分析，我們對距離壓縮后的數據進行了裁剪，以縮短成像時間，裁剪后方位向為2048個點，距離向為1024點，之后進行基數為4的分解成像處理，成像大小為1024×1024。

表3給出了3種算法的運行時間及相對傳統BP的加速比(倍)，可以看出3種算法的速度相對于傳統BP都有提升，而且隨分解級數的增多，加速比也在增加，兩種Bulk-FFBP算法整體上比Block- FFBP的速度更快，這是因為Block-FFBP距離向分塊內存效率低下，并影響了計算效率。尤其是，在5級分解時，Block-FFBP的加速比相對于4級分解反而降低了，這是因為插值余量所占的空間超過了有效數據本身的空間，導致計算效率嚴重下降。

圖8 Block-FFBP與兩種Bulk-FFBP點目標成像對比

表2 點目標性能對比

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

5 總結

本文針對Block-FFBP算法由于距離向分塊造成的數據截斷及效率瓶頸問題，提出了基于距離向整體處理的Bulk-FFBP算法，在算法的推導過程，又將Bulk-FFBP算法細分為兩種，一種是基于距離向控制點的Bulk-FFBP算法，另一種是無控制點的Bulk-FFBP算法。文中通過誤差分析、成像性能分析以及算法效率分析，證實了這兩種Bulk-FFBP算法相對于Block-FFBP算法的優越性。

[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]. 電子與信息學報, 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] 楊澤民, 孫光才, 吳玉峰, 等. 一種新的基于極坐標格式的快速后向投影算法[J]. 電子與信息學報, 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

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

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

唐江文： 男，1988年生，博士生，研究方向為SAR時域成像算法及大規模并行計算.

鄧云凱： 男，1962年生，研究員，博士生導師，研究方向為星載SAR系統設計、成像及微波遙感理論.

王 宇： 男，1980年生，研究員，博士生導師，研究方向為星載SAR系統設計及信號處理.