volume | PIER Journals

Abstract

We introduce and discuss a parallel SAR backprojection algorithm using a Non-Uniform FFT (NUFFT) routine implemented on a GPU in CUDA language. The details of a convenient GPU implementation of the NUFFT-based SAR backprojection algorithm, amenable to further generalizations to a multi-GPU architecture, are also given. The performance of the approach is analyzed in terms of accuracy and computational speed by comparisons to a ``standard", parallel version of the backprojection algorithm exploiting FFT+interpolation instead of the NUFFT. Different interpolators have been considered for the latter processing scheme. The NUFFT-based backprojection has proven significantly more accurate than all the compared approach, with a computing time of the same order. An analysis of the computational burden of all the different steps involved in both the considered approaches (i.e., standard and NUFFT backprojections) has been also reported. Experimental results against the Air Force Research Laboratory (AFRL) airborne data delivered under the ``challenge problem for SAR-based Ground Moving Target Identification (GMTI) in urban environments" and collected over circular flight paths are also shown.

1. Bamler, R., "A comparison of range-doppler and wavenumber domain SAR focusing algorithms," IEEE Trans. on Geosci. Remote Sens., Vol. 30, No. 4, 706-713, Jul. 1992.
doi:10.1109/36.158864

2. Horham, L. A. and L. J. Moore, "SAR image formation toolbox for MATLAB," Proc. of SPIE 7699, 769906, 2010, doi:10.1117/12.855375.

3. Desai, M. D. and W. K. Jenkins, "Convolution backprojection image reconstruction for spotlight mode synthetic aperture radar," IEEE Trans. on Image Proc., Vol. 1, No. 4, 505-517, Oct. 1992.
doi:10.1109/83.199920

4. Choi, H., D. C. Munson, and Jr., "Direct-Fourier reconstruction in tomography and synthetic aperture radar," Int. J. Imaging Syst. Tech., Vol. 9, No. 1, 1-13, 1998.
doi:10.1002/(SICI)1098-1098(1998)9:1<1::AID-IMA1>3.0.CO;2-E

5. Yegulalp, A. F., "Fast backprojection algorithm for synthetic aperture radar," Proc. of the IEEE Radar Conf., 60-65, Waltham, MA, Apr. 20-22, 1999.

6. Basu, S. and Y. Bresler, "O(N²log₂N) filtered backprojection reconstruction algorithm for tomography," IEEE Trans. on Image Proc., Vol. 9, No. 10, 1760-1773, Oct. 2000.
doi:10.1109/83.869187

7. Ulander, L. M. H., H. Hellsten, and G. Stenström, "Synthetic aperture radar processing using fast factorized back-projection," IEEE Trans. on Aerosp. Electron. Syst., Vol. 39, No. 3, 760-776, Jul. 2003.
doi:10.1109/TAES.2003.1238734

8. Fessler, J. A. and B. P. Sutton, "Nonuniform Fast Fourier Transforms using min-max interpolation," IEEE Trans. on Signal Proc., Vol. 51, No. 2, 560-574, Feb. 2003.
doi:10.1109/TSP.2002.807005

9. Fourmont, K., "Non-equispaced fast Fourier transforms with applications to tomography," J. Fourier Anal. Appl., Vol. 9, No. 5, 431-450, Sept. 2003.
doi:10.1007/s00041-003-0021-1

10. Capozzoli, A., C. Curcio, A. Di Vico, and A. Liseno, "NUFFT-& GPU-based fast imaging of vegetation," IEICE Trans. on Commun., Vol. E94-B, No. 7, 2092-2103, Jul. 2011.
doi:10.1587/transcom.E94.B.2092

11. Capozzoli, A., C. Curcio, and A. Liseno, "GPU-based ω-k processing by 1D Non-Uniform FFTs," Progress In Electromagnetic Research M, Vol. 23, 279-298, 2012.
doi:10.2528/PIERM11083003

12. Franceschetti, G. and G. Schirinzi, "A SAR processor based on two-dimensional FFT codes," IEEE Trans. on Aerosp. Electron. Syst., Vol. 26, No. 2, 356-366, Mar. 1990.
doi:10.1109/7.53462

13. Cafforio, C., C. Prati, and F. Rocca, "SAR data focusing using seismic migration techniques," IEEE Trans. on Aerosp. Electron. Syst., Vol. 27, No. 2, 194-207, Mar. 1991.
doi:10.1109/7.78293

14. Franceschetti, G., R. Lanari, V. Pascazio, and G. Schirinzi, "WASAR: A wide-angle SAR processor," IEE Proceedings F Radar and Signal Processing, Vol. 139, No. 2, 107-114, Apr. 1992.
doi:10.1049/ip-f-2.1992.0014

15. Franceschetti, G., A. Mazzeo, N. Mazzocca, V. Pascazio, and G. Schirinzi, "An e±cient SAR parallel processor," IEEE Trans. on Aerosp. Electron. Syst., Vol. 27, No. 2, 343-353, Mar. 1991.
doi:10.1109/7.78308

16. Ender, J. H. G. and A. R. Brenner, "PAMIR --- A wideband phased array SAR/MTI system," IEE Proc. --- Radar Sonar Navig., Vol. 150, No. 3, 165-172, Jun. 2003.
doi:10.1049/ip-rsn:20030445

17. Hannsen, R. and R. Bamler, "Evaluation of interpolation kernels for SAR interferometry," IEEE Trans. on Geosci. Remote Sens., Vol. 37, No. 1, 318-321, Jan. 1999.
doi:10.1109/36.739168

18. Migliaccio, M. and F. Bruno, "A new interpolation kernel for SAR interferometric registration," IEEE Trans. on Geosci. Remote Sens., Vol. 41, No. 5, 1105-1110, May 2003.
doi:10.1109/TGRS.2003.810672

19. Migliaccio, M., F. Nunziata, F. Bruno, and F. Casu, "Knab sampling window for InSAR data interpolation," IEEE Trans. on Geosci. Remote Lett., Vol. 4, No. 3, 397-400, Jul. 2007.
doi:10.1109/LGRS.2007.895708

20. Capozzoli, A., G. D'Elia, A. Liseno, A. Moreira, and K. P. Papathanassiou, "A novel optimization approach to forest height reconstruction from multi-baseline data," Proc. of the Geosci. Remote Sens. Int. Symp., 5037-5040, Barcelona, Spain, Jul. 23-28, 2007.

21. Capozzoli, A., G. D'Elia, A. Liseno, P. Vinetti, M. Nannini, A. Reigber, R. Scheiber, and V. Severino, "SAR tomography with optimized constellation and its application to forested scenes," Atti della Fondazione G. Ronchi, Vol. LXV, No. 3, 367-375, May-Jun. 2010.

22. Bamler, R. and P. Hartl, "Synthetic aperture radar interferometry," Inverse Probl., Vol. 14, No. 4, R1-R54, Aug. 1998.
doi:10.1088/0266-5611/14/4/001

23. Tao, Y. B., H. Lin, and H. J. Bao, "From CPU to GPU: GPU-based electromagnetic computing (GPUECO)," Progress In Electromagnetic Research, Vol. 81, 1-19, 2008.
doi:10.2528/PIER07121302

24. Dziekonski, A., A. Lamecki, and M. Mrozowski, "A memory efficient and fast sparse matrix vector product on a GPU," Progress In Electromagnetic Research, Vol. 116, 49-63, 2011.

25. Gao, P. C., Y. B. Tao, and H. Lin, "Fast RCS prediction using multiresolution shooting and bouncing ray method on the GPU," Progress In Electromagnetic Research, Vol. 107, 187-202, 2010.
doi:10.2528/PIER10061807

26. Xu, K., Z. Fan, D.-Z. Ding, and R.-S. Chen, "GPU accelerated unconditionally stable Crank-Nicolson FDTD method for the analysis of three-dimensional microwave circuits," Progress In Electromagnetic Research, Vol. 102, 381-395, 2010.
doi:10.2528/PIER10020606

27. Dziekonski, A., P. Sypek, A. Lamecki, and M. Mrozowski, "Finite element matrix generation on a GPU," Progress In Electromagnetic Research, Vol. 128, 249-265, 2012.

28. Demir, V., "Graphics processor unit (GPU) acceleration of finite-difference frequency-domain (FDFD) method," Progress In Electromagnetic Research M, Vol. 23, 29-51, 2012.
doi:10.2528/PIERM11090909

29. Di Bisceglie, M., M. Di Santo, C. Galdi, R. Lanari, and N. Ranaldo, "Synthetic aperture radar processing with GPGPU," IEEE Signal Proc. Mag., Vol. 27, No. 2, 69-78, Sept. 2010.
doi:10.1109/MSP.2009.935383

30. Fasih, A. and T. Hartley, "GPU-accelerated synthetic aperture radar backprojection in CUDA," Proc. of the IEEE Radar Conf., 1408-1413, Washington, DC, May 10-14, 2010.

31. Kusk, A. and J. Dall, "SAR focusing of P-band ice sounding data using back-projection," Proc. of the IEEE Geosci. Remote Sens. Symp., 4071-4074, Honolulu, HI, Jul. 25-30, 2010.

32. Ponce, O., P. Prats, M. Rodriguez-Cassola, R. Scheiber, and A. Reigber, "Processing of circular SAR trajectories with fast factorized back-projection," Proc. of the IEEE Geosci. Remote Sens. Int. Symp., 3692-3695, Vancouver, Canada, Jul. 24-29, 2011.

33. Capozzoli, A., C. Curcio, A. Liseno, and P. Vinetti, "Fast interpolation accelerated on GPU for SAR backprojection," Proc. of the 28th Annual Rev. of Progr. in Appl. Comput. Electromagn., 305-310, Columbus, OH, Apr. 10-14, 2012.

34. Capozzoli, A., C. Curcio, A. Liseno, and P. V. Testa, "NUFFT-based SAR backprojection on multiple GPUs," Proc. of the Tyrrhenian Workshop on Advances in Radar and Remote Sensing, Napoli, Italy, Sept. 12-14, 2012.

35. Kirk, D. B. and W.-M. W. Hwu, Programming Massively Parallel Processors, Burlington, Morgan Kaufmann, MA, 2010.

36. Blom, M. and P. Follo, "VHF SAR image formation implemented on a GPU," Proc. of the IEEE Int. Symp. on Geosci. Remote Sens., 3352-3356, Seoul, South Korea, Jul. 25-29, 2005.

37. Jackson, J. I., C. H. Meyer, D. G. Nishimura, and A. Macovski, "Selection of a convolution function for Fourier inversion using gridding," IEEE Trans. on Med. Imag., Vol. 10, No. 3, 473-478, Sept. 1991.
doi:10.1109/42.97598

38. Scarborough, S. M., C. H. Casteel, Jr., L. R. Gorham, M. J. Minardi, U. K. Majumder, M. G. Judge, E. Zelnio, and M. Bryant, "A challenge problem for SAR-based GMTI in urban environments," Proc. of SPIE 7337, 73370G, 2009, doi:10.1117/12.823461.

39. Hein, A., Processing of SAR Data: Fundamentals, Signal Processing, Interferometry, Springer-Verlag, Berlin, Heidelberg, 2004.

40. D'Elia, G., G. Leone, R. Pierri, and G. Schirinzi, "Traveling sampling of scattered fields," Proc. of the IEEE Antennas Propag. Int. Symp., 531-534.

41. Knab, J. J., "Interpolation of band-limited functions using the approximate prolate series," IEEE Trans. on Inf. Theory, Vol. 25, No. 6, 717-719, Nov. 1979.
doi:10.1109/TIT.1979.1056115

42. Knab, J. J., "The sampling window," IEEE Trans. on Inf. Theory, Vol. IT-29, No. 1, 157-159, Jan. 1983.
doi:10.1109/TIT.1983.1056603

43. Li, A., "Algorithms for the implementation of Stolt interpolation is SAR processing ," Proc. of the IEEE Geosci. Remote Sens. Symp., 360-362, Houston, TX, May 26-29, 1992.

44. Keys, R. G., "Cubic convolution interpolation for digital image processing," IEEE Trans. on Acoust. Speech Signal Proc., Vol. 29, No. 6, 1153-1160, Dec. 1981.
doi:10.1109/TASSP.1981.1163711

45. Sanders, J. and E. Kandrot, CUDA by Example, Addison-Wesley, Ann Arbor, MI, 2011.

46. CUDA CUFFT Library, Feb. 2011.

47. Nukada, A. and S. Matsuoka, "Auto-tuning 3-D FFT library for CUDA GPUs," Proc. of Conf. on High Performance Computing Networking, Storage and Anal., Portland, OR, Nov. 14-20, 2009.

48. Ruijters, D., B. M. ter Haar Romeny, and P. Suetens, "Efficient GPU-based texture interpolation using uniform B-splines," J. Graphics, GPU, Game Tools, Vol. 13, No. 4, 61-69, Jan. 2008.
doi:10.1080/2151237X.2008.10129269

49. http://www.cs.virginia.edu/» mwb7w/cuda support/memory m-anagement overhead.html.

50. http://www.cs.virginia.edu/»mwb7w/cuda support/memory transfer overhead.html .

51. Tarjan, D., K. Skadron, and P. Micikevicius, "The art of performance tuning for CUDA and manycore architectures," Birds-of-a-feather session at SC'09, 2009.

52. Capozzoli, A., C. Curcio, G. D'Elia, A. Liseno, and P. Vinetti, "Fast CPU/GPU pattern evaluation of irregular arrays," Appl. Comput. Electromagn. Soc. J., Vol. 25, No. 4, 355-372, Apr. 2010.

53. CUDA Toolkit 4.0, CUBLAS Library, Apr. 2011, Oct. 2004.

54. Rigling, B. D. and R. L. Moses, "Polar format algorithm for bistatic SAR," IEEE Trans. on Aerosp. Electron. Syst., Vol. 40, No. 4, 1147-1159.
doi:10.1109/TAES.2004.1386870

55. Selva, J. and J. M. Lopez-Sanchez, "Efficient interpolation of SAR images for coregistration in SAR interferometry," IEEE Geosci. Remote Sens. Lett., Vol. 4, No. 3, 411-415, Jul. 2007.
doi:10.1109/LGRS.2007.895961

56. Austin, C. D., E. Ertin, and R. L. Moses, "Sparse multipass 3D SAR imaging: Applications to the GOTCHA data set," Proc. of SPIE Algorithms for Synthetic Aperture Radar Imagery XVI, Vol. 7337, Orlando, FL, Apr. 16-17, 2009.

Prof. Amedeo Capozzoli

Dr. Claudio Curcio

Dr. Angelo Liseno