Vol. 133

Front:[PDF file] Back:[PDF file]
Latest Volume
All Volumes
All Issues

Fast GPU-Based Interpolation for SAR Backprojection

By Amedeo Capozzoli, Claudio Curcio, and Angelo Liseno
Progress In Electromagnetics Research, Vol. 133, 259-283, 2013


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.


Amedeo Capozzoli, Claudio Curcio, and Angelo Liseno, "Fast GPU-Based Interpolation for SAR Backprojection," Progress In Electromagnetics Research, Vol. 133, 259-283, 2013.


    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.

    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.

    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.

    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(N2log2N) filtered backprojection reconstruction algorithm for tomography," IEEE Trans. on Image Proc., Vol. 9, No. 10, 1760-1773, Oct. 2000.

    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.

    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.

    9. Fourmont, K., "Non-equispaced fast Fourier transforms with applications to tomography," J. Fourier Anal. Appl., Vol. 9, No. 5, 431-450, Sept. 2003.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

    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.

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

    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.

    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.

    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.

    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.

    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.