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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Prof. Amedeo Capozzoli

Dr. Claudio Curcio

Dr. Angelo Liseno