Vol. 23

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

GPU-Based ω-k Tomographic Processing by 1D Non-Uniform FFTs

By Amedeo Capozzoli, Claudio Curcio, and Angelo Liseno
Progress In Electromagnetics Research M, Vol. 23, 279-298, 2012


We present an ω-k approach based on the use of a 1D Non-Uniform FFT (NUFFT) routine, of NER (Non-Equispaced Results) type, programmed on a GPU in CUDA language, amenable to real-time applications. A Matlab main program links, via mex files, a compiled parallel (CUDA) routine implementing the NUFFT. The approach is shown to be an extension of an already developed parallel algorithm based on standard backprojection processing to account also for near-field data. The implementation of the GPU-based, parallel NUFFT routine is detailed and the computational advantages of the developed approach are highlighted against other confronted sequential or parallel (on multi-core CPU) procedures. Furthermore, the benefits of the $\omega$-k, NUFFT-based processing are pointed out by both comparing its accuracy and computational convenience against other interpolators, and by providing numerical results. By comparing the computational performance of the algorithm against a multi-core, Matlab implementation, the speedup has been about 20 for a medium size image. The performance of the approach has been pointed out in the applicative case of vegetation imaging against experimental data of a boxtree (Buxus tree), also under a source of temporal decorrelation (wind).


Amedeo Capozzoli, Claudio Curcio, and Angelo Liseno, "GPU-Based ω-k Tomographic Processing by 1D Non-Uniform FFTs ," Progress In Electromagnetics Research M, Vol. 23, 279-298, 2012.


    1. Stolt, R., "Migration by Fourier transform techniques," Geophys., Vol. 43, No. 1, 49-76, 1978.

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

    3. Reigber, A., A. Alivizatos, A. Potsis, and A. Moreira, "Extended wavenumber-domain synthetic aperture radar focusing with integrated motion compensation," IEE Proc. - Radar Sonar Navig., Vol. 153, No. 3, 301-310, Jun. 2006.

    4. Shin, H.-S. and J.-T. Lim, "Omega-k algorithm for airborne forward-looking bistatic spotlight SAR imaging," IEEE Trans. Geosci. on Remote Sens. Lett., Vol. 6, No. 2, 312-316, Apr. 2009.

    5. Hamasaki, T., L. Ferro-Famil, E. Pottier, and M. Sato, "Applications of polarimetric interferometric ground-based SAR (GB-SAR) system to environment monitoring and disaster prevention," Proc. of the Europ. Radar Conf., 29-32, Paris, France, Oct. 6-7, 2005.

    6. Sun, B., J. Chen, C.-S. Li, and Y.-Q. Zhou, "FA-ScanSAR: Full aperture scanning pulse by pulse for the nearspace slow-moving platform borne SAR," Progress In Electromagnetics Research B, Vol. 25, 23-37, 2010.

    7. Chen, H., R. Wu, J. Liu, and Z. Han, "GPR migration imaging algorithm based on NUFFT," PIERS Online, Vol. 6, No. 1, 16-20, 2010.

    8. Song, J., Q. H. Liu, P. Torrione, and L. Collins, "Two-dimensional and three-dimensional NUFFT migration method for landmine detection using ground-penetrating radar," IEEE Trans. on Geosci. Remote Sens., Vol. 44, No. 6, 1462-1469, 2006.

    9. 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.

    10. Raney, R. K., H. Runge, R. Bamler, I. G. Cumming, and F. H. Wong, "Precision SAR processing using chirp scaling," IEEE Trans. on Geosci. Remote Sens., Vol. 32, No. 4, 786-799, Jul. 1994.

    11. Hanssen, 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.

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

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

    14. Greengard, L. and J.-Y. Lee, "Accelerating the nonuniform fast Fourier transform," SIAM Review, Vol. 46, No. 3, 443-454, 2004.

    15. Subiza, B., E. Gimeno-Nieves, J. M. Lopez-Sanchez, and J. Fortuny-Guasch, "An approach to SAR imaging by means of non-uniform FFT's," Proc. of the IEEE Geosci. Remote Sens. Int. Symp., 4089-4091, Toulouse, France, Jul. 21-25, 2003.

    16. Li, S., H. Sun, B. Zhu, and R. Liu, "Two-dimensional NUFFT-based algorithm for fast near-field imaging," IEEE Antennas Wireless Prop. Lett., Vol. 9, 814-817, 2010.

    17. Huang, Y., Y. Liu, Q. H. Liu, and J. Zhang, "Improved 3-D GPR detection by NUFFT combined with MPD method," Progress In Electromagnetics Research, Vol. 103, 185-199, 2010.

    18. Callison, R. J., "Spotlight Synthetic Aperture Radar (SAR) system and method for generating a SAR map in real-time using a modified polar format algorithm,", US Patent, No. 7,511,656 B2, Mar. 31, 2009.

    19. 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, Mar. 2010.

    20. Sharma, G. and J. Martin, "MATLABR?: A language for parallel computing," Int. J. Parallel Prog., Vol. 37, No. 1, 3-36, 2009.

    21. Rosario-Torres, S. and M. Velez-Reyes, "Speeding up the MATLABTM hyperspectral image analysis toolbox using GPUs and the Jacket toolbox," Proc. of the Hyperspectral Image and Signal Proc. Workshop: Evolution in Remote Sens., 1-4, Grenoble, France, Aug. 26-28, 2009.

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

    23. Jiang, W.-Q., M. Zhang, and Y. Wang, "CUDA-based radiative transfer method with application to the EM scattering from a two-layer canopy model," Journal of Electromagnetic Waves and Applications, Vol. 24, No. 17-18, 2509-2521, 2010.

    24. Jiang, W.-Q., M. Zhang, H. Chen, and Y.-G. Lu, "CUDA implementation in the EM scattering of a three-layer canopy," Progress In Electromagnetics Research, Vol. 116, 457-473, 2011.

    25. Pryor, G., B. Lucey, P. Yalamanchili, C. McClanahan, and J. Malcolm, "High-level GPU computing with jacket: For MATLAB and C/C++," Proc. of the SPIE Vol. 8060 Modeling and Simulation for Defense Systems and Applications VI, Orlando, FL, USA, Apr. 26-27, 2011.

    26. Zhou, Y., "Microwave imaging based on wideband range profiles," Progress In Electromagnetics Research Letters, Vol. 19, 57-65, 2010.

    27. 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.

    28. Zhang, Y., J. Liu, E. Kultursay, M. Kandemir, N. Pitsianis, and X. Sun, "Scalable parallelization strategies to accelerate NuFFT data translation on multicores," Proc. of the Int. Euro-Par Conf., Part II, 125-136, Ischia, Italy, Aug. 31-Sep. 3, 2010.

    29. Gregerson, A., "Implementing fast MRI gridding on GPUs via CUDA," NVIDIA Tech. Rep. on Med. Imag. Using CUDA, 2008.

    30. Sorensen, T. S., T. Schaeffter, K. Ostergaard Noe, and M. Schacht Hansen, "Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware," IEEE Trans. Med. Imag., Vol. 27, No. 4, 538-547, Apr. 2008.

    31. Jacob, M., "Optimized least-square nonuniform fast Fourier transform," IEEE Trans. Signal Proc., Vol. 57, No. 6, 2165-2177, Jun. 2009.

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

    33. Zhang, K. and J. U. Kang, "Graphics processing unit accelerated non-uniform fast Fourier transform for ultrahigh-speed, real-time Fourier-domain OCT," Optics Express, Vol. 18, No. 22, 23472-23487, Oct. 2010.

    34. Kestur, S., S. Park, K. M. Irick, and V. Narayanan, "Accelerating the nonuniform fast fourier transform using FPGAs," Proc. of the IEEE Annual Int. Symp. on Field-Programmable Custom Comput. Machines, 19-26, Charlotte, NC, May 2-4, 2010.

    35. Fatica, M. and W.-K. Jeong, "Accelerating Matlab with CUDA," Proc. of the High Performance Embedded Comput. Workshop, Lexington, MA, Sep. 18-20, 2007.

    36. Capozzoli, A., C. Curcio, A. Liseno, M. Migliorelli, and G. Toso, "Accelarating phase-only reflectarray antenna synthesis by GPUs," Proc. of the Int. Rev. of Progr. in Appl. Comput. Electromagn., Williamsburg, VI, Mar. 27-31, 2011, CD ROM..

    37. 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.

    38. Chommeloux, L., C. Pichot, and J.-C. Bolomey, "Electromagnetic modeling for microwave imaging of cylindrical buried inho- mogeneities," IEEE Trans. Microw. Theory Tech., Vol. 34, No. 10, 1064-1076, Oct. 1986.

    39. Rabiner, L. R., R. W. Schafer, and C. M. Rader, "The chirp z-transform algorithm and its application," Bell Syst. Tech. J., Vol. 48, No. 5, 1249-1292, May-Jun. 1969.

    40. Lanari, R., "A new method for the compensation of the SAR range cell migration based on the chirp z-transform," IEEE Trans. on Geosci. Remote Sens., Vol. 33, No. 5, 1296-1299, Sep. 1995.

    41., , CUDA cuFFT Library, Aug. 2010.

    42., , http://www.mathworks.com/matlabcentral/newsreader/view-thread/261866..

    43. Kepner, J., M. Gokhale, R. Minnich, A. Marks, and J. DeGood, "Interfacing interpreted and compiled languages to support applications on a massively parallel network of workstations (MP- NOW)," Cluster Computing, Vol. 3, No. 1, 35-44, 2000.

    44. Huang, B., J. Mielikainen, H. Oh, and H.-L. A. Huang, "Development of a GPU-based high-performance radiative transfer model for the Infrared Atmospheric Sounding Interferometer (IASI)," J. Comput. Phys., Vol. 230, No. 6, 2207-2221, Mar. 2011.

    45. Lim, K.-S. and V. C. Koo, "Design and construction of wideband VNA ground-based radar system with real and synthetic aperture measurement capabilities," Progress In Electromagnetics Research, Vol. 86, 259-275, 2008.

    46. Narayanan, R. M., D. W. Doerr, and D. C. Rundquist, "Temporal decorrelation of x-band backscatter from wind- influenced vegetation," IEEE Trans. Aerosp. Electron. Syst., Vol. 28, No. 2, 404-412, Apr. 1992.