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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 . Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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