Selection of convolution kernel in non-uniform fast Fourier transform for Fourier domain optical coherence tomography

Kenny K.H. Chan; Shuo Tang

doi:10.1364/OE.19.026891

Selection of convolution kernel in non-uniform fast Fourier transform for Fourier domain optical coherence tomography

Kenny K.H. Chan and Shuo Tang

Optics Express
Vol. 19,
Issue 27,
pp. 26891-26904
(2011)
•https://doi.org/10.1364/OE.19.026891

Get Citation
Copy Citation Text
Kenny K.H. Chan and Shuo Tang, "Selection of convolution kernel in non-uniform fast Fourier transform for Fourier domain optical coherence tomography," Opt. Express 19, 26891-26904 (2011)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Get PDF (3524 KB)
Set citation alerts
Save article

Related Topics
Table of Contents Category
- Medical Optics and Biotechnology
Optics & Photonics Topics
?

The topics in this list come from the OSA Optics and Photonics Topics applied to this article.
Previously assigned OCIS codes
- Discrete optical signal processing (070.2025)
- Image reconstruction techniques (110.3010)
- Optical coherence tomography (170.4500)

About this Article
History
- Original Manuscript: October 14, 2011
- Revised Manuscript: December 3, 2011
- Manuscript Accepted: December 5, 2011
- Published: December 16, 2011
Virtual Issues
Virtual Journal for Biomedical Optics Vol. 7, Iss. 2

Accessible

Open Access

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.

Full Article | PDF Article

OSA Recommended Articles

GPU-accelerated non-uniform fast Fourier transform-based compressive sensing spectral domain optical coherence tomography

Daguang Xu, Yong Huang, and Jin U. Kang
Opt. Express 22(12) 14871-14884 (2014)

High-speed spectral domain optical coherence tomography using non-uniform fast Fourier transform

Kenny K. H. Chan and Shuo Tang
Biomed. Opt. Express 1(5) 1309-1319 (2010)

Graphics processing unit accelerated non-uniform fast Fourier transform for ultrahigh-speed, real-time Fourier-domain OCT

Kang Zhang and Jin U. Kang
Opt. Express 18(22) 23472-23487 (2010)

References

View by:
Article Order
|
Year
|
Author
|
Publication

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]
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]
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]
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]
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]
D. Hillmann, G. Huttmann, and P. Koch, “Using nonequispaced fast Fourier transformation to process optical coherence tomography signals,” Proc. SPIE 7372, 73720R (2009).
[Crossref]
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]
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]
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. 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]
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]
A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. 14(6), 1368–1393 (1993).
[Crossref]
L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004).
[Crossref]
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]
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]
A. J. W. Duijndam and M. A. Schonewille, “Nonuniform fast Fourier transform,” Geophysics 64(2), 539–551 (1999).
[Crossref]
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]
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]
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.
M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93(2), 216–231 (2005).
[Crossref]
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]
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]
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]
OpenMP Architecture Review Board, “The OpenMP API specification for parallel programming,” http://www.openmp.org/ .
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]

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

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)

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]

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]

2005 (2)

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]

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

2004 (3)

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]

L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004).
[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]

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.

Azimi, E.

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]

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.

Biedermann, B. R.

Boppart, S. A.

Brezinski, M. E.

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]

Chan, K. K. H.

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]

Chen, M.

Chen, Y.

Chen, Z.

Choma, M. A.

Connolly, J.

Cox, R. W.

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.

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.

Greengard, L.

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

Hammer, D. X.

Hansen, M. S.

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.

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]

Huber, R.

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.

Izatt, J. A.

Jackson, J. I.

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.

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]

Liu, G.

Macovski, A.

Marks, D. L.

Meng, J.

Meyer, C. H.

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]

Noe, K. O.

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.

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.

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]

Sarty, G. E.

Sarunic, M. V.

Schaefer, A. W.

Schaeffter, T.

Schmitt, J.

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.

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.

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]

Ustun, T. E.

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)

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]

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]

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)

IEEE Trans. Med. Imaging (4)

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]

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]

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)

Nat. Photonics (1)

Opt. Express (7)

Opt. Lett. (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]

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)

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)

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

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.

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.

Click here to see a list of articles that cite this paper

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.

Download Full Size | PPT Slide | PDF

Fig. 2

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

Download Full Size | PPT Slide | PDF

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.

Download Full Size | PPT Slide | PDF

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.

Download Full Size | PPT Slide | PDF

Fig. 5

Relative L₂ 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.

Download Full Size | PPT Slide | PDF

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.

Download Full Size | PPT Slide | PDF

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 L₂ 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.

Download Full Size | PPT Slide | PDF

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.

Download Full Size | PPT Slide | PDF

Tables (2)

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

View Table | View all tables in this article

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

View Table | View all tables in this article

Equations (19)

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

f_{N D F T} (z_{m}) = \frac{1}{N} \sum_{n = 0}^{N - 1} F (k_{n}) \exp (- i \frac{2 π}{Δ K} m (k_{n} - k_{o})), m = 0, \dots, N - 1

F_{r} (k_{l}) = \sum_{n = 0}^{N - 1} F (k_{n}) C (k_{l} - k_{n}), l = 0, \dots, N_{r} - 1

f_{r} (z_{m}) \approx \frac{1}{N_{r}} \sum_{l = 0}^{N_{r} - 1} F_{r} (k_{l}) e^{- i 2 π \frac{m l}{N_{r}}}, m = 0, 1, \dots, N_{r} - 1

f_{N U F F T} (z_{m}) = \frac{f {}_{r}{(z_{m})}}{c (z_{m})}

e (z_{m}) = | f_{N U F F T} (z_{m}) - f_{N D F T} (z_{m}) |

= | \frac{1}{c (z_{m})} \sum_{i = - \infty}^{\infty} [f_{N D F T} (z_{m + i N_{r}}) c (z_{m + i N_{r}})] - f_{N D F T} (z_{m}) |

= | \frac{1}{c (z_{m})} \sum_{i \neq 0} f_{N D F T} (z_{m + i N_{r}}) c (z_{m + i N_{r}}) |

e_{2} = \frac{{({\sum_{m} | f_{N U F F T} (z_{m}) - f_{N D F T} (z_{m}) |}^{2})}^{\frac{1}{2}}}{{(\sum_{m} {| f_{N D F T} (z_{m}) |}^{2})}^{\frac{1}{2}}}

e_{a b s} = \frac{1}{N} \sum_{m} | 20 \log_{10} [f_{N U F F T} (z_{m})] - 20 \log_{10} [f_{N D F T} (z_{m})] |

C (κ) = e^{\frac{- κ^{2}}{4 τ}}

C (κ) = \frac{1}{W} I_{o} {β {[1 - {(2 κ / W)}^{2}]}^{\frac{1}{2}}}

C (κ) = α + (1 - α) \cos (\frac{2 π}{W} κ)

C (κ) = α + β \cos (\frac{2 π}{W} κ) + (1 - α - β) \cos (\frac{4 π}{W} κ)

κ = | \frac{k_{n} - k_{l}}{δ k} | \leq \frac{W}{2}, δ k = \frac{k_{\max} - k_{\min}}{N_{r}}

τ = \frac{W}{2 N^{2}} \frac{π}{R (R - 0.5)}

β = π {[\frac{W^{2}}{R^{2}} {(R - \frac{1}{2})}^{2} - 0.8]}^{\frac{1}{2}}

c (z_{m}) = {(2 τ)}^{\frac{1}{2}} \exp (- z_{m}^{2} τ), m = 0, \dots, \frac{N}{2} - 1

c (z_{m}) = \frac{\sin ({[{(m π W / N_{r})}^{2} - β^{2}]}^{\frac{1}{2}})}{{[{(m π W / N_{r})}^{2} - β^{2}]}^{\frac{1}{2}}}

O [p W N + R N \log_{2} (R N) + N]

Kernel Width	Two term cosine	Three term cosine
Kernel Width	α	α	β
2	0.5273	0.4149	0.4990
3	0.5076	0.3954	0.4977
4		0.3850	0.5000
5		0.3823	0.5000

Kernel function	Pre-computed mode (R=2, W=3)		On-the-fly mode (R=2, W=3)		On-the-fly mode (R=2, W=5)
Kernel function	Processing time	A-scan rate	Processing time	A-scan rate	Processing time	A-scan rate
Gaussian	10.51	95.14k	18.01	55.52k	23.77	40.27k
Kaiser-Bessel			39.72	25.17k	59.42	16.83k
Two term cos			20.01	49.96k	24.95	40.08k
Three term cos			25.56	39.13k	36.15	27.66k
NDFT	1470	0.6803k	-	-	-	-

Kernel Width	Two term cosine	Three term cosine
Kernel Width	α	α	β
2	0.5273	0.4149	0.4990
3	0.5076	0.3954	0.4977
4		0.3850	0.5000
5		0.3823	0.5000

Kernel function	Pre-computed mode (R=2, W=3)		On-the-fly mode (R=2, W=3)		On-the-fly mode (R=2, W=5)
Kernel function	Processing time	A-scan rate	Processing time	A-scan rate	Processing time	A-scan rate
Gaussian	10.51	95.14k	18.01	55.52k	23.77	40.27k
Kaiser-Bessel			39.72	25.17k	59.42	16.83k
Two term cos			20.01	49.96k	24.95	40.08k
Three term cos			25.56	39.13k	36.15	27.66k
NDFT	1470	0.6803k	-	-	-	-

Abstract

References

2011 (2)

2010 (4)

2009 (3)

2008 (3)

2007 (2)

2005 (2)

2004 (3)

2003 (2)

2001 (1)

1999 (1)

1993 (1)

1991 (1)

1985 (1)

Adler, D. C.

Azimi, E.

Beatty, P. J.

Bennett, R.

Biedermann, B. R.

Boppart, S. A.

Brezinski, M. E.

Chan, K. K. H.

Chen, M.

Chen, Y.

Chen, Z.

Choma, M. A.

Connolly, J.

Cox, R. W.

Ding, Z.

Duijndam, A. J. W.

Duker, J. S.

Dutt, A.

Eigenwillig, C. M.

Ferguson, R. D.

Fessler, J. A.

Frigo, M.

Fujimoto, J. G.

Greengard, L.

Hammer, D. X.

Hansen, M. S.

Hillmann, D.

Hu, Z.

Huber, R.

Huo, L.

Huttmann, G.

Iftimia, N. V.

Izatt, J. A.

Jackson, J. I.

Johnson, S. G.

Kang, J. U.

Ko, T. H.

Koch, P.

Kowalczyk, A.

Lamouche, G.

Lee, J.

Lévesque, D.

Li, J.

Li, X.

Liu, B.

Liu, G.

Macovski, A.

Marks, D. L.

Meng, J.

Meyer, C. H.

Nishimura, D. G.

Noe, K. O.

O’Sullivan, J. D.

Palte, G.

Pauly, J. M.

Reynolds, J. J.

Rokhlin, V.

Rollins, A. M.

Sarty, G. E.

Sarunic, M. V.

Schaefer, A. W.

Schaeffter, T.

Schmitt, J.

Schonewille, M. A.

Sorensen, T. S.