Abstract

Gridding based non-uniform fast Fourier transform (NUFFT) has recently been shown as an efficient method of processing non-linearly sampled data from Fourier-domain optical coherence tomography (FD-OCT). This method requires selecting design parameters, such as kernel function type, oversampling ratio and kernel width, to balance between computational complexity and accuracy. The Kaiser-Bessel (KB) and Gaussian kernels have been used independently on the NUFFT algorithm for FD-OCT. This paper compares the reconstruction error and speed for the optimization of these design parameters and justifies particular kernel choice for FD-OCT applications. It is found that for on-the-fly computation of the kernel function, the simpler Gaussian function offers a better accuracy-speed tradeoff. The KB kernel, however, is a better choice in the pre-computed kernel mode of NUFFT, in which the processing speed is no longer dependent on the kernel function type. Finally, the algorithm is used to reconstruct in-vivo images of a human finger at a camera limited 50k A-line/s.

© 2011 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. Z. Hu and A. M. Rollins, “Fourier domain optical coherence tomography with a linear-in-wavenumber spectrometer,” Opt. Lett. 32(24), 3525–3527 (2007).
    [CrossRef] [PubMed]
  2. C. M. Eigenwillig, B. R. Biedermann, G. Palte, and R. Huber, “K-space linear Fourier domain mode locked laser and applications for optical coherence tomography,” Opt. Express 16(12), 8916–8937 (2008).
    [CrossRef] [PubMed]
  3. D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
    [CrossRef]
  4. J. Xi, L. Huo, J. Li, and X. Li, “Generic real-time uniform K-space sampling method for high-speed swept-source optical coherence tomography,” Opt. Express 18(9), 9511–9517 (2010).
    [CrossRef] [PubMed]
  5. G. Liu, J. Zhang, L. Yu, T. Xie, and Z. Chen, “Real-time polarization-sensitive optical coherence tomography data processing with parallel computing,” Appl. Opt. 48(32), 6365–6370 (2009).
    [CrossRef] [PubMed]
  6. M. A. Choma, M. V. Sarunic, C. Yang, and J. A. Izatt, “Sensitivity advantage of swept source and Fourier domain optical coherence tomography,” Opt. Express 11(18), 2183–2189 (2003).
    [CrossRef] [PubMed]
  7. M. Wojtkowski, V. J. Srinivasan, T. H. Ko, J. G. Fujimoto, A. Kowalczyk, and J. S. Duker, “Ultrahigh-resolution, high-speed, Fourier domain optical coherence tomography and methods for dispersion compensation,” Opt. Express 12(11), 2404–2422 (2004).
    [CrossRef] [PubMed]
  8. D. Hillmann, G. Huttmann, and P. Koch, “Using nonequispaced fast Fourier transformation to process optical coherence tomography signals,” Proc. SPIE 7372, 73720R (2009).
    [CrossRef]
  9. K. K. H. Chan and S. Tang, “High-speed spectral domain optical coherence tomography using non-uniform fast Fourier transform,” Biomed. Opt. Express 1(5), 1309–1319 (2010).
    [CrossRef] [PubMed]
  10. K. Zhang and J. U. Kang, “Graphics processing unit accelerated non-uniform fast Fourier transform for ultrahigh-speed, real-time Fourier-domain OCT,” Opt. Express 18(22), 23472–23487 (2010).
    [CrossRef] [PubMed]
  11. S. Vergnole, D. Lévesque, and G. Lamouche, “Experimental validation of an optimized signal processing method to handle non-linearity in swept-source optical coherence tomography,” Opt. Express 18(10), 10446–10461 (2010).
    [CrossRef] [PubMed]
  12. K. Wang, Z. Ding, T. Wu, C. Wang, J. Meng, M. Chen, and L. Xu, “Development of a non-uniform discrete Fourier transform based high speed spectral domain optical coherence tomography system,” Opt. Express 17(14), 12121–12131 (2009).
    [CrossRef] [PubMed]
  13. K. Zhang and J. U. Kang, “Real-time intraoperative 4D full-range FD-OCT based on the dual graphics processing units architecture for microsurgery guidance,” Biomed. Opt. Express 2(4), 764–770 (2011).
    [CrossRef] [PubMed]
  14. A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. 14(6), 1368–1393 (1993).
    [CrossRef]
  15. L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004).
    [CrossRef]
  16. J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, “Selection of a convolution function for Fourier inversion using gridding [computerised tomography application],” IEEE Trans. Med. Imaging 10(3), 473–478 (1991).
    [CrossRef] [PubMed]
  17. P. J. Beatty, D. G. Nishimura, and J. M. Pauly, “Rapid gridding reconstruction with a minimal oversampling ratio,” IEEE Trans. Med. Imaging 24(6), 799–808 (2005).
    [CrossRef] [PubMed]
  18. G. E. Sarty, R. Bennett, and R. W. Cox, “Direct reconstruction of non-Cartesian k-space data using a nonuniform fast Fourier transform,” Magn. Reson. Med. 45(5), 908–915 (2001).
    [CrossRef] [PubMed]
  19. A. J. W. Duijndam and M. A. Schonewille, “Nonuniform fast Fourier transform,” Geophysics 64(2), 539–551 (1999).
    [CrossRef]
  20. J. A. Fessler and B. P. Sutton, “Nonuniform fast Fourier transforms using min-max interpolation,” IEEE Trans. Signal Process. 51(2), 560–574 (2003).
    [CrossRef]
  21. J. D. O’Sullivan, “A fast sinc function gridding algorithm for fourier inversion in computer tomography,” IEEE Trans. Med. Imaging 4(4), 200–207 (1985).
    [CrossRef] [PubMed]
  22. D. Potts, G. Steidl, and M. Tasche, “Fast Fourier transforms for nonequispaced data: a tutorial,” in Modern Sampling Theory: Mathematics and Applications, J. J. Benedetto and P. Ferreira, eds. (Springer, 2001), Chap. 12, 249–274.
  23. M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93(2), 216–231 (2005).
    [CrossRef]
  24. B. Liu, E. Azimi, and M. E. Brezinski, “True logarithmic amplification of frequency clock in SS-OCT for calibration,” Biomed. Opt. Express 2(6), 1769–1777 (2011).
    [CrossRef] [PubMed]
  25. T. E. Ustun, N. V. Iftimia, R. D. Ferguson, and D. X. Hammer, “Real-time processing for Fourier domain optical coherence tomography using a field programmable gate array,” Rev. Sci. Instrum. 79(11), 114301 (2008).
    [CrossRef] [PubMed]
  26. A. W. Schaefer, J. J. Reynolds, D. L. Marks, and S. A. Boppart, “Real-time digital signal processing-based optical coherence tomography and Doppler optical coherence tomography,” IEEE Trans. Biomed. Eng. 51(1), 186–190 (2004).
    [CrossRef] [PubMed]
  27. OpenMP Architecture Review Board, “The OpenMP API specification for parallel programming,” http://www.openmp.org/ .
  28. T. S. Sorensen, T. Schaeffter, K. O. Noe, and M. S. Hansen, “Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware,” IEEE Trans. Med. Imaging 27(4), 538–547 (2008).
    [CrossRef] [PubMed]

2011 (2)

2010 (4)

2009 (3)

2008 (3)

T. E. Ustun, N. V. Iftimia, R. D. Ferguson, and D. X. Hammer, “Real-time processing for Fourier domain optical coherence tomography using a field programmable gate array,” Rev. Sci. Instrum. 79(11), 114301 (2008).
[CrossRef] [PubMed]

T. S. Sorensen, T. Schaeffter, K. O. Noe, and M. S. Hansen, “Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware,” IEEE Trans. Med. Imaging 27(4), 538–547 (2008).
[CrossRef] [PubMed]

C. M. Eigenwillig, B. R. Biedermann, G. Palte, and R. Huber, “K-space linear Fourier domain mode locked laser and applications for optical coherence tomography,” Opt. Express 16(12), 8916–8937 (2008).
[CrossRef] [PubMed]

2007 (2)

Z. Hu and A. M. Rollins, “Fourier domain optical coherence tomography with a linear-in-wavenumber spectrometer,” Opt. Lett. 32(24), 3525–3527 (2007).
[CrossRef] [PubMed]

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

2005 (2)

M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93(2), 216–231 (2005).
[CrossRef]

P. J. Beatty, D. G. Nishimura, and J. M. Pauly, “Rapid gridding reconstruction with a minimal oversampling ratio,” IEEE Trans. Med. Imaging 24(6), 799–808 (2005).
[CrossRef] [PubMed]

2004 (3)

L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004).
[CrossRef]

A. W. Schaefer, J. J. Reynolds, D. L. Marks, and S. A. Boppart, “Real-time digital signal processing-based optical coherence tomography and Doppler optical coherence tomography,” IEEE Trans. Biomed. Eng. 51(1), 186–190 (2004).
[CrossRef] [PubMed]

M. Wojtkowski, V. J. Srinivasan, T. H. Ko, J. G. Fujimoto, A. Kowalczyk, and J. S. Duker, “Ultrahigh-resolution, high-speed, Fourier domain optical coherence tomography and methods for dispersion compensation,” Opt. Express 12(11), 2404–2422 (2004).
[CrossRef] [PubMed]

2003 (2)

M. A. Choma, M. V. Sarunic, C. Yang, and J. A. Izatt, “Sensitivity advantage of swept source and Fourier domain optical coherence tomography,” Opt. Express 11(18), 2183–2189 (2003).
[CrossRef] [PubMed]

J. A. Fessler and B. P. Sutton, “Nonuniform fast Fourier transforms using min-max interpolation,” IEEE Trans. Signal Process. 51(2), 560–574 (2003).
[CrossRef]

2001 (1)

G. E. Sarty, R. Bennett, and R. W. Cox, “Direct reconstruction of non-Cartesian k-space data using a nonuniform fast Fourier transform,” Magn. Reson. Med. 45(5), 908–915 (2001).
[CrossRef] [PubMed]

1999 (1)

A. J. W. Duijndam and M. A. Schonewille, “Nonuniform fast Fourier transform,” Geophysics 64(2), 539–551 (1999).
[CrossRef]

1993 (1)

A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. 14(6), 1368–1393 (1993).
[CrossRef]

1991 (1)

J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, “Selection of a convolution function for Fourier inversion using gridding [computerised tomography application],” IEEE Trans. Med. Imaging 10(3), 473–478 (1991).
[CrossRef] [PubMed]

1985 (1)

J. D. O’Sullivan, “A fast sinc function gridding algorithm for fourier inversion in computer tomography,” IEEE Trans. Med. Imaging 4(4), 200–207 (1985).
[CrossRef] [PubMed]

Adler, D. C.

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

Azimi, E.

Beatty, P. J.

P. J. Beatty, D. G. Nishimura, and J. M. Pauly, “Rapid gridding reconstruction with a minimal oversampling ratio,” IEEE Trans. Med. Imaging 24(6), 799–808 (2005).
[CrossRef] [PubMed]

Bennett, R.

G. E. Sarty, R. Bennett, and R. W. Cox, “Direct reconstruction of non-Cartesian k-space data using a nonuniform fast Fourier transform,” Magn. Reson. Med. 45(5), 908–915 (2001).
[CrossRef] [PubMed]

Biedermann, B. R.

Boppart, S. A.

A. W. Schaefer, J. J. Reynolds, D. L. Marks, and S. A. Boppart, “Real-time digital signal processing-based optical coherence tomography and Doppler optical coherence tomography,” IEEE Trans. Biomed. Eng. 51(1), 186–190 (2004).
[CrossRef] [PubMed]

Brezinski, M. E.

Chan, K. K. H.

Chen, M.

Chen, Y.

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

Chen, Z.

Choma, M. A.

Connolly, J.

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

Cox, R. W.

G. E. Sarty, R. Bennett, and R. W. Cox, “Direct reconstruction of non-Cartesian k-space data using a nonuniform fast Fourier transform,” Magn. Reson. Med. 45(5), 908–915 (2001).
[CrossRef] [PubMed]

Ding, Z.

Duijndam, A. J. W.

A. J. W. Duijndam and M. A. Schonewille, “Nonuniform fast Fourier transform,” Geophysics 64(2), 539–551 (1999).
[CrossRef]

Duker, J. S.

Dutt, A.

A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. 14(6), 1368–1393 (1993).
[CrossRef]

Eigenwillig, C. M.

Ferguson, R. D.

T. E. Ustun, N. V. Iftimia, R. D. Ferguson, and D. X. Hammer, “Real-time processing for Fourier domain optical coherence tomography using a field programmable gate array,” Rev. Sci. Instrum. 79(11), 114301 (2008).
[CrossRef] [PubMed]

Fessler, J. A.

J. A. Fessler and B. P. Sutton, “Nonuniform fast Fourier transforms using min-max interpolation,” IEEE Trans. Signal Process. 51(2), 560–574 (2003).
[CrossRef]

Frigo, M.

M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93(2), 216–231 (2005).
[CrossRef]

Fujimoto, J. G.

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

M. Wojtkowski, V. J. Srinivasan, T. H. Ko, J. G. Fujimoto, A. Kowalczyk, and J. S. Duker, “Ultrahigh-resolution, high-speed, Fourier domain optical coherence tomography and methods for dispersion compensation,” Opt. Express 12(11), 2404–2422 (2004).
[CrossRef] [PubMed]

Greengard, L.

L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004).
[CrossRef]

Hammer, D. X.

T. E. Ustun, N. V. Iftimia, R. D. Ferguson, and D. X. Hammer, “Real-time processing for Fourier domain optical coherence tomography using a field programmable gate array,” Rev. Sci. Instrum. 79(11), 114301 (2008).
[CrossRef] [PubMed]

Hansen, M. S.

T. S. Sorensen, T. Schaeffter, K. O. Noe, and M. S. Hansen, “Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware,” IEEE Trans. Med. Imaging 27(4), 538–547 (2008).
[CrossRef] [PubMed]

Hillmann, D.

D. Hillmann, G. Huttmann, and P. Koch, “Using nonequispaced fast Fourier transformation to process optical coherence tomography signals,” Proc. SPIE 7372, 73720R (2009).
[CrossRef]

Hu, Z.

Huber, R.

C. M. Eigenwillig, B. R. Biedermann, G. Palte, and R. Huber, “K-space linear Fourier domain mode locked laser and applications for optical coherence tomography,” Opt. Express 16(12), 8916–8937 (2008).
[CrossRef] [PubMed]

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

Huo, L.

Huttmann, G.

D. Hillmann, G. Huttmann, and P. Koch, “Using nonequispaced fast Fourier transformation to process optical coherence tomography signals,” Proc. SPIE 7372, 73720R (2009).
[CrossRef]

Iftimia, N. V.

T. E. Ustun, N. V. Iftimia, R. D. Ferguson, and D. X. Hammer, “Real-time processing for Fourier domain optical coherence tomography using a field programmable gate array,” Rev. Sci. Instrum. 79(11), 114301 (2008).
[CrossRef] [PubMed]

Izatt, J. A.

Jackson, J. I.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, “Selection of a convolution function for Fourier inversion using gridding [computerised tomography application],” IEEE Trans. Med. Imaging 10(3), 473–478 (1991).
[CrossRef] [PubMed]

Johnson, S. G.

M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93(2), 216–231 (2005).
[CrossRef]

Kang, J. U.

Ko, T. H.

Koch, P.

D. Hillmann, G. Huttmann, and P. Koch, “Using nonequispaced fast Fourier transformation to process optical coherence tomography signals,” Proc. SPIE 7372, 73720R (2009).
[CrossRef]

Kowalczyk, A.

Lamouche, G.

Lee, J.

L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004).
[CrossRef]

Lévesque, D.

Li, J.

Li, X.

Liu, B.

Liu, G.

Macovski, A.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, “Selection of a convolution function for Fourier inversion using gridding [computerised tomography application],” IEEE Trans. Med. Imaging 10(3), 473–478 (1991).
[CrossRef] [PubMed]

Marks, D. L.

A. W. Schaefer, J. J. Reynolds, D. L. Marks, and S. A. Boppart, “Real-time digital signal processing-based optical coherence tomography and Doppler optical coherence tomography,” IEEE Trans. Biomed. Eng. 51(1), 186–190 (2004).
[CrossRef] [PubMed]

Meng, J.

Meyer, C. H.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, “Selection of a convolution function for Fourier inversion using gridding [computerised tomography application],” IEEE Trans. Med. Imaging 10(3), 473–478 (1991).
[CrossRef] [PubMed]

Nishimura, D. G.

P. J. Beatty, D. G. Nishimura, and J. M. Pauly, “Rapid gridding reconstruction with a minimal oversampling ratio,” IEEE Trans. Med. Imaging 24(6), 799–808 (2005).
[CrossRef] [PubMed]

J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, “Selection of a convolution function for Fourier inversion using gridding [computerised tomography application],” IEEE Trans. Med. Imaging 10(3), 473–478 (1991).
[CrossRef] [PubMed]

Noe, K. O.

T. S. Sorensen, T. Schaeffter, K. O. Noe, and M. S. Hansen, “Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware,” IEEE Trans. Med. Imaging 27(4), 538–547 (2008).
[CrossRef] [PubMed]

O’Sullivan, J. D.

J. D. O’Sullivan, “A fast sinc function gridding algorithm for fourier inversion in computer tomography,” IEEE Trans. Med. Imaging 4(4), 200–207 (1985).
[CrossRef] [PubMed]

Palte, G.

Pauly, J. M.

P. J. Beatty, D. G. Nishimura, and J. M. Pauly, “Rapid gridding reconstruction with a minimal oversampling ratio,” IEEE Trans. Med. Imaging 24(6), 799–808 (2005).
[CrossRef] [PubMed]

Reynolds, J. J.

A. W. Schaefer, J. J. Reynolds, D. L. Marks, and S. A. Boppart, “Real-time digital signal processing-based optical coherence tomography and Doppler optical coherence tomography,” IEEE Trans. Biomed. Eng. 51(1), 186–190 (2004).
[CrossRef] [PubMed]

Rokhlin, V.

A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. 14(6), 1368–1393 (1993).
[CrossRef]

Rollins, A. M.

Sarty, G. E.

G. E. Sarty, R. Bennett, and R. W. Cox, “Direct reconstruction of non-Cartesian k-space data using a nonuniform fast Fourier transform,” Magn. Reson. Med. 45(5), 908–915 (2001).
[CrossRef] [PubMed]

Sarunic, M. V.

Schaefer, A. W.

A. W. Schaefer, J. J. Reynolds, D. L. Marks, and S. A. Boppart, “Real-time digital signal processing-based optical coherence tomography and Doppler optical coherence tomography,” IEEE Trans. Biomed. Eng. 51(1), 186–190 (2004).
[CrossRef] [PubMed]

Schaeffter, T.

T. S. Sorensen, T. Schaeffter, K. O. Noe, and M. S. Hansen, “Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware,” IEEE Trans. Med. Imaging 27(4), 538–547 (2008).
[CrossRef] [PubMed]

Schmitt, J.

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

Schonewille, M. A.

A. J. W. Duijndam and M. A. Schonewille, “Nonuniform fast Fourier transform,” Geophysics 64(2), 539–551 (1999).
[CrossRef]

Sorensen, T. S.

T. S. Sorensen, T. Schaeffter, K. O. Noe, and M. S. Hansen, “Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware,” IEEE Trans. Med. Imaging 27(4), 538–547 (2008).
[CrossRef] [PubMed]

Srinivasan, V. J.

Sutton, B. P.

J. A. Fessler and B. P. Sutton, “Nonuniform fast Fourier transforms using min-max interpolation,” IEEE Trans. Signal Process. 51(2), 560–574 (2003).
[CrossRef]

Tang, S.

Ustun, T. E.

T. E. Ustun, N. V. Iftimia, R. D. Ferguson, and D. X. Hammer, “Real-time processing for Fourier domain optical coherence tomography using a field programmable gate array,” Rev. Sci. Instrum. 79(11), 114301 (2008).
[CrossRef] [PubMed]

Vergnole, S.

Wang, C.

Wang, K.

Wojtkowski, M.

Wu, T.

Xi, J.

Xie, T.

Xu, L.

Yang, C.

Yu, L.

Zhang, J.

Zhang, K.

Appl. Opt. (1)

Biomed. Opt. Express (3)

Geophysics (1)

A. J. W. Duijndam and M. A. Schonewille, “Nonuniform fast Fourier transform,” Geophysics 64(2), 539–551 (1999).
[CrossRef]

IEEE Trans. Biomed. Eng. (1)

A. W. Schaefer, J. J. Reynolds, D. L. Marks, and S. A. Boppart, “Real-time digital signal processing-based optical coherence tomography and Doppler optical coherence tomography,” IEEE Trans. Biomed. Eng. 51(1), 186–190 (2004).
[CrossRef] [PubMed]

IEEE Trans. Med. Imaging (4)

J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, “Selection of a convolution function for Fourier inversion using gridding [computerised tomography application],” IEEE Trans. Med. Imaging 10(3), 473–478 (1991).
[CrossRef] [PubMed]

P. J. Beatty, D. G. Nishimura, and J. M. Pauly, “Rapid gridding reconstruction with a minimal oversampling ratio,” IEEE Trans. Med. Imaging 24(6), 799–808 (2005).
[CrossRef] [PubMed]

J. D. O’Sullivan, “A fast sinc function gridding algorithm for fourier inversion in computer tomography,” IEEE Trans. Med. Imaging 4(4), 200–207 (1985).
[CrossRef] [PubMed]

T. S. Sorensen, T. Schaeffter, K. O. Noe, and M. S. Hansen, “Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware,” IEEE Trans. Med. Imaging 27(4), 538–547 (2008).
[CrossRef] [PubMed]

IEEE Trans. Signal Process. (1)

J. A. Fessler and B. P. Sutton, “Nonuniform fast Fourier transforms using min-max interpolation,” IEEE Trans. Signal Process. 51(2), 560–574 (2003).
[CrossRef]

Magn. Reson. Med. (1)

G. E. Sarty, R. Bennett, and R. W. Cox, “Direct reconstruction of non-Cartesian k-space data using a nonuniform fast Fourier transform,” Magn. Reson. Med. 45(5), 908–915 (2001).
[CrossRef] [PubMed]

Nat. Photonics (1)

D. C. Adler, Y. Chen, R. Huber, J. Schmitt, J. Connolly, and J. G. Fujimoto, “Three-dimensional endomicroscopy using optical coherence tomography,” Nat. Photonics 1(12), 709–716 (2007).
[CrossRef]

Opt. Express (7)

M. A. Choma, M. V. Sarunic, C. Yang, and J. A. Izatt, “Sensitivity advantage of swept source and Fourier domain optical coherence tomography,” Opt. Express 11(18), 2183–2189 (2003).
[CrossRef] [PubMed]

M. Wojtkowski, V. J. Srinivasan, T. H. Ko, J. G. Fujimoto, A. Kowalczyk, and J. S. Duker, “Ultrahigh-resolution, high-speed, Fourier domain optical coherence tomography and methods for dispersion compensation,” Opt. Express 12(11), 2404–2422 (2004).
[CrossRef] [PubMed]

C. M. Eigenwillig, B. R. Biedermann, G. Palte, and R. Huber, “K-space linear Fourier domain mode locked laser and applications for optical coherence tomography,” Opt. Express 16(12), 8916–8937 (2008).
[CrossRef] [PubMed]

K. Wang, Z. Ding, T. Wu, C. Wang, J. Meng, M. Chen, and L. Xu, “Development of a non-uniform discrete Fourier transform based high speed spectral domain optical coherence tomography system,” Opt. Express 17(14), 12121–12131 (2009).
[CrossRef] [PubMed]

J. Xi, L. Huo, J. Li, and X. Li, “Generic real-time uniform K-space sampling method for high-speed swept-source optical coherence tomography,” Opt. Express 18(9), 9511–9517 (2010).
[CrossRef] [PubMed]

S. Vergnole, D. Lévesque, and G. Lamouche, “Experimental validation of an optimized signal processing method to handle non-linearity in swept-source optical coherence tomography,” Opt. Express 18(10), 10446–10461 (2010).
[CrossRef] [PubMed]

K. Zhang and J. U. Kang, “Graphics processing unit accelerated non-uniform fast Fourier transform for ultrahigh-speed, real-time Fourier-domain OCT,” Opt. Express 18(22), 23472–23487 (2010).
[CrossRef] [PubMed]

Opt. Lett. (1)

Proc. IEEE (1)

M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93(2), 216–231 (2005).
[CrossRef]

Proc. SPIE (1)

D. Hillmann, G. Huttmann, and P. Koch, “Using nonequispaced fast Fourier transformation to process optical coherence tomography signals,” Proc. SPIE 7372, 73720R (2009).
[CrossRef]

Rev. Sci. Instrum. (1)

T. E. Ustun, N. V. Iftimia, R. D. Ferguson, and D. X. Hammer, “Real-time processing for Fourier domain optical coherence tomography using a field programmable gate array,” Rev. Sci. Instrum. 79(11), 114301 (2008).
[CrossRef] [PubMed]

SIAM J. Sci. Comput. (1)

A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. 14(6), 1368–1393 (1993).
[CrossRef]

SIAM Rev. (1)

L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004).
[CrossRef]

Other (2)

D. Potts, G. Steidl, and M. Tasche, “Fast Fourier transforms for nonequispaced data: a tutorial,” in Modern Sampling Theory: Mathematics and Applications, J. J. Benedetto and P. Ferreira, eds. (Springer, 2001), Chap. 12, 249–274.

OpenMP Architecture Review Board, “The OpenMP API specification for parallel programming,” http://www.openmp.org/ .

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (8)

Fig. 1
Fig. 1

Illustration of the resampling of data with Gaussian kernel into equally spaced grid with a width of 6 [9]. The circles are the original unevenly sampled data and the vertical dashed lines are the new uniform grid. A Gaussian function is convolved with each original data point, spreading its power over a few adjacent grid points as shown by the crosses. The new evenly sampled data value is the summation of the values of all the crosses on each grid line.

Fig. 2
Fig. 2

The overview of the NUFFT algorithm in the spectral domain (k space) and the spatial domain (z space) (color online).

Fig. 3
Fig. 3

The effect on the kernel response by changing the kernel width W (left) and oversampling ratio R (right) of the Kasier-Bessel kernel function.

Fig. 4
Fig. 4

(left) Plot of kernel functions with R = 2, W = 3 and (right) Fourier transform of the kernel function a) Gaussian b) Kaiser-Bessel c) Two term cosine d) Three term cosine.

Fig. 5
Fig. 5

Relative L2 error with varying oversampling ratio and kernel width for different kernel functions. a) Gaussian, b) Kaiser-Bessel, c) Two term cosine, d) Three term cosine.

Fig. 6
Fig. 6

Average absolute error with varying oversampling ratio and kernel width for different kernel functions. a) Gaussian, b) Kaiser-Bessel, c) Two term cosine, d) Three term cosine.

Fig. 7
Fig. 7

Computation time–error curves of the NUFFT (R = 2) in pre-computed mode (a, c) and in on-the-fly mode (b, d) for kernel width W = 2, 3, 4, 5, 6. The top row shows the L2 error and the bottom row shows the average absolute error. Increasing the kernel width increases the processing time as expected. The arrow points to the most efficient kernel function: Kaiser-Bessel for the pre-computed mode and the Gaussian for the on-the-fly mode.

Fig. 8
Fig. 8

Images of the palmar surface of a finger reconstructed using NUFFT with different kernel functions and their differences from NDFT reconstructed image. From top to bottom the rows are Gaussian, Kaiser-Bessel, two term cosine, and three term cosine, respectively. The field of view is 2.5 mm wide by 1.7 mm deep. The scale bars are in dB.

Tables (2)

Tables Icon

Table 1 The parameters for cosine functions with an oversampling ratio of 2

Tables Icon

Table 2 NUFFT computation time (μs) for a 1024 pixels A-line and A-scan rate (lines/s)

Equations (19)

Equations on this page are rendered with MathJax. Learn more.

f NDFT ( z m )= 1 N n=0 N1 F( k n ) exp( i 2π ΔK m( k n k o ) ), m=0,,N1
F r ( k l )= n=0 N1 F( k n ) C( k l k n ) , l=0,, N r 1
f r ( z m ) 1 N r l=0 N r 1 F r ( k l ) e i2π ml N r , m=0,1,, N r 1
f NUFFT ( z m )= f ( z m ) r c( z m )
e( z m )=| f NUFFT ( z m ) f NDFT ( z m ) |
=| 1 c( z m ) i= [ f NDFT ( z m+i N r )c( z m+i N r ) ] f NDFT ( z m ) |
=| 1 c( z m ) i0 f NDFT ( z m+i N r )c( z m+i N r ) |
e 2 = ( m | f NUFFT ( z m ) f NDFT ( z m ) | 2 ) 1 2 ( m | f NDFT ( z m ) | 2 ) 1 2
e abs = 1 N m | 20 log 10 [ f NUFFT ( z m ) ]20 log 10 [ f NDFT ( z m ) ] |
C( κ )= e κ 2 4τ
C( κ )= 1 W I o { β [ 1 ( 2κ/W ) 2 ] 1 2 }
C( κ )=α+( 1α )cos( 2π W κ )
C( κ )=α+βcos( 2π W κ )+( 1αβ )cos( 4π W κ )
κ=| k n k l δk | W 2 , δk= k max k min N r
τ= W 2 N 2 π R(R-0.5)
β=π [ W 2 R 2 ( R 1 2 ) 2 0.8 ] 1 2
c( z m )= ( 2τ ) 1 2 exp( z m 2 τ ), m=0,, N 2 1
c( z m )= sin( [ ( mπW/ N r ) 2 β 2 ] 1 2 ) [ ( mπW/ N r ) 2 β 2 ] 1 2
O[ pWN+RN log 2 ( RN )+N ]

Metrics