volume | PIER Journals

Abstract

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

1. Stolt, R., "Migration by Fourier transform techniques," Geophys., Vol. 43, No. 1, 49-76, 1978.
doi:10.1190/1.1440826

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.
doi:10.1109/7.78293

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.
doi:10.1049/ip-rsn:20045087

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.
doi:10.1109/LGRS.2008.2011924

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.
doi:10.2528/PIERB10061304

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.
doi:10.2529/PIERS090907050824

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.
doi:10.1109/TGRS.2006.870412

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.
doi:10.1109/36.158864

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.
doi:10.1109/36.298008

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.
doi:10.1109/36.739168

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.
doi:10.1007/s00041-003-0021-1

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

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.
doi:10.1109/LAWP.2010.2069550

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.
doi:10.2528/PIER10021005

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.
doi:10.1109/MSP.2009.935383

20. Sharma, G. and J. Martin, "MATLABR^?: A language for parallel computing," Int. J. Parallel Prog., Vol. 37, No. 1, 3-36, 2009.
doi:10.1007/s10766-008-0082-5

21. Rosario-Torres, S. and M. Velez-Reyes, "Speeding up the MATLAB^TM 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.
doi:10.1163/156939310793675772

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.
doi:10.1587/transcom.E94.B.2092

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.
doi:10.1109/TMI.2007.909834

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

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.
doi:10.1364/OE.18.023472

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.
doi:10.1109/36.158864

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.
doi:10.1109/TMTT.1986.1133496

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.
doi:10.1109/36.469496

41., CUDA cuFFT Library, Aug. 2010.
doi:10.1109/36.469496

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

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.
doi:10.1023/A:1019011716367

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.
doi:10.1016/j.jcp.2010.09.011

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.
doi:10.2528/PIER08092204

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.
doi:10.1109/7.144566

Prof. Amedeo Capozzoli

Dr. Claudio Curcio

Dr. Angelo Liseno