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

Optics Express, Vol. 19, Issue 27, pp. 26891-26904 (2011)

http://dx.doi.org/10.1364/OE.19.026891

Acrobat PDF (3524 KB)

### 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

## 1. Introduction

*k*domain is Fourier transformed to axial depth

*z*domain in the reconstruction. The Fourier transform (FT) can be achieved by the computationally efficient fast Fourier transform (FFT) algorithm if the spectral data is uniformly sampled. Unfortunately, this is not the case for most FD-OCT systems. One type of FD-OCT, spectral domain OCT (SD-OCT) is typically designed to capture the spectral components linearly in wavelength λ with a spectrometer. The inverse relationship between wavenumber and wavelength,

*k*. The second type, swept source OCT (SS-OCT), time-encodes wavenumber by rapidly tuning a narrowband source through a broad optical bandwidth non-linearly, which also requires a resampling. The image reconstruction algorithm however is interchangeable between the two kinds of FD-OCT.

*k*sampling. Hardware approaches such as linear-in-wavenumber spectrometer for SD-OCT [1

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]

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]

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]

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]

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]

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]

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]

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]

## 2. The NUFFT processing method

### 2.1 Gridding based NUFFT

*z*domain is obtained by a Fourier transform of the interference fringes sampled in the

*k*domain. However, most systems acquire spectra non-uniformly sampled in wavenumber. In such cases, the axial reflectivity can be directly calculated by using NDFT [12

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]

*f*) is the axial reflectivity at the axial depth location

_{NDFT}(z_{m}*z*,

_{m}*F(k*) is the interference signal sampled at non-uniform

_{n}*k*spacing,

*k*is the wavenumber of the first sample,

_{o}*ΔK*is the wavenumber range, and

*N*is the number of sample points. The NDFT computation has a complexity of

*O(N*. Therefore, it is often desirable to resample the data and use FFT with a complexity

^{2})*O(Nlog*for faster processing speed. This requires that the intensity values to be resampled to points evenly spaced in

_{2}N)*k*. Traditionally linear interpolation [5

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]

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]

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]

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]

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]

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]

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]

- 1) Convolve the non-uniformly sampled
*k*domain data with a kernel function. - 2) Resample the result onto evenly spaced locations on an oversampled grid.
- 3) Compute the Fourier transform using an FFT on the oversampled data.
- 4) Apply a deconvolution in the
*z*domain by a division of the FT of the kernel function (also known as apodization correction or deapodization).

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]

*C(k*) with

*F(k)*gives the intermediate function

*F*on the oversampled grid that can be defined in discrete form as,where

_{r}(k)*N*is the number of points on a grid with oversampling ratio

_{r}=RN*R*. Note that Eq. (2) completes both convolution and resampling steps of the NUFFT algorithm. Figure 1 illustrates the convolution and resampling process. The kernel width

*W*defines the number of grid points adjacent to the original data point that the kernel is evaluated. The kernel width will be further examined in section 2.3.

*N*points.

_{r}*f*has been calculated, the actual profile

_{r}(z_{m})*f(z*can be determined by a deconvolution in

_{m})*k*space or alternatively with a simple division by the Fourier transform of

*C(k)*in z space,where

*c(z*is the Fourier transform of the kernel function

_{m})*C(k).*The resulting vector

*f(z*will have

_{m})*N*points, which is larger than the original

_{r}*N*points input because of the oversampling. This vector is truncated to

*N/2*points to remove extra points due to oversampling that contain artifacts [9

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]

### 2.2 Sources of error in NUFFT

_{r}introduces identical copies of the spectrum in the Fourier domain at every

*N*interval, which leads to aliasing for broadband signal such as those in FD-OCT [19

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

*f*is the exact FT of the interference fringes,

_{NDFT}*N*is the repetition interval for the repeating spectrum and

_{r}*i*is any integer [19

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

*i=0*and the aliasing signal is located at

*i≠0*, and thus the error equation reduces to Eq. (7) [17

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]

**64**(2), 539–551 (1999). [CrossRef]

*c(z*, the FT of the kernel function. Readers should note that the error is also dependent on the amplitude of

_{m})*f*and therefore it is dependent on the wavenumber sampling pattern and the signal acquired [17

_{NDFT}(z_{m})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]

**64**(2), 539–551 (1999). [CrossRef]

_{2}error known also as normalized RMS error is usually used to evaluate the accuracy of the reconstruction [14

**14**(6), 1368–1393 (1993). [CrossRef]

**64**(2), 539–551 (1999). [CrossRef]

_{2}error gives the root mean square error over the full range of the axial scan. It is defined as [14

**14**(6), 1368–1393 (1993). [CrossRef]

**64**(2), 539–551 (1999). [CrossRef]

*N*point axial scan can also be calculated, which is defined as

### 2.3 Kernel width and oversampling rate

*c(z*is dependent on the kernel width

_{m})*W*and the oversampling ratio

*R*. These two parameters are fundamental to all NUFFT implementation regardless of the kernel function used. The kernel width

*W*defines the number of grid points adjacent to the original data point that the kernel is accounted for in the NUFFT evaluation. An infinite kernel width would produce the most accurate result, but the value of

*W*is often set to a small finite value for computational efficiency. The use of a finite

*W*value introduces a truncation error [22] because the tails of the kernel are not used. Limiting the kernel function to a width

*W*is equivalent to multiplying a rectangular function to the kernel function in the

*k*domain. The FT of the rectangular function is a sinc function and it contributes to the side lobes as illustrated in Fig. 3 for positive

*m*. The side lobes within the aliasing regions will combine with the region of interest (ROI) at

*R*determines the number of data points

*N*in sampling the convolution. In the Fourier domain, increasing

_{r}*R*only decreases the amplitudes of the side lobes slightly but allows the main lobe to have a wider width as illustrated in Fig. 3. This decreases the amount of roll-off and increases the signal to noise ratio in the region of interest, where the aliasing signal is considered to be noise in this context. Although the deconvolution or apodization correction can compensate for the roll-off of the original signal, it also amplifies the aliased signal. Therefore it is desirable to minimize the roll-off by increasing the oversampling ratio.

### 2.4 Kernel functions

*C(κ*) is central to the NUFFT algorithm. It is used to interpolate and resample the data points onto the uniform oversampled grid. The shape of the function will affect both the roll-off and side lobe amplitudes, and therefore dictates the amount of reconstruction error. Gaussian [9

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]

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]

**7372**, 73720R (2009). [CrossRef]

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]

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]

- 1) Gaussian [9
**1**(5), 1309–1319 (2010). [CrossRef] [PubMed],13**18**(22), 23472–23487 (2010). [CrossRef] [PubMed]**2**(4), 764–770 (2011). [CrossRef] [PubMed]]**46**(3), 443–454 (2004). [CrossRef] - 2) Kaiser-Bessel [11
**18**(10), 10446–10461 (2010). [CrossRef] [PubMed]]**24**(6), 799–808 (2005). [CrossRef] [PubMed]where I_{o}() is the zeroth-order modified Bessel function of the first kind. - 3) Two term cosine (cos2) [16]
**10**(3), 473–478 (1991). [CrossRef] [PubMed] - 4) Three term cosine (cos3) [16
**10**(3), 473–478 (1991). [CrossRef] [PubMed]

*τ*of the Gaussian kernel is [15

**46**(3), 443–454 (2004). [CrossRef]

**64**(2), 539–551 (1999). [CrossRef]

*β*value of the KB kernel is given as [11

**18**(10), 10446–10461 (2010). [CrossRef] [PubMed]

**24**(6), 799–808 (2005). [CrossRef] [PubMed]

*α, β*of the cosine based functions, but Jackson et al. determined the optimum values for a range of kernel widths as summarized in Table 1 [16

**10**(3), 473–478 (1991). [CrossRef] [PubMed]

*W*was used in this study.

**46**(3), 443–454 (2004). [CrossRef]

**64**(2), 539–551 (1999). [CrossRef]

**18**(10), 10446–10461 (2010). [CrossRef] [PubMed]

**24**(6), 799–808 (2005). [CrossRef] [PubMed]

### 2.5 Computational complexity and memory requirements

**64**(2), 539–551 (1999). [CrossRef]

*R*has a larger effect on the complexity than the kernel width. Therefore it is desirable to use the lowest oversampling ratio together with the appropriate kernel width to achieve the desired accuracy [11

**18**(10), 10446–10461 (2010). [CrossRef] [PubMed]

**24**(6), 799–808 (2005). [CrossRef] [PubMed]

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

*R>1*that will give a power of two sized oversampled array based on the hardware. For most SD-OCT systems using a camera with power of two number of pixels, the optimal oversampling rate would be two. Other OCT systems with non power of two inputs, such as SS-OCT, should use the smallest fractional oversampling ratio that results in a power of two sized oversampled array. As determined by the hardware used in this study, this manuscript will focus on using an input array of 1024 elements with the optimal oversampling ratio of two. Finally, the kernel calculation constant

*p*in Eq. (19) is dependent on the kernel function and the implementation of the calculation.

*a priori,*such as in SD-OCT, the values of

*C(κ)*on the grid can be evaluated before the start of the reconstruction to save computation. For this pre-computed mode, the complexity of NUFFT is not dependent on the kernel function and

*p*is constant for all kernel functions. For sampling patterns that are not known

*a priori*or for high speed SS-OCT system with frequency jitters and low repeatability of frequency scanning [24

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]

*p*varies for the different kernels. The computation of a Bessel function for the KB kernel is considerably larger than the computation of exponentials and cosines. Therefore the efficiency of on-the-fly mode NUFFT is highly dependent on the choice of kernel functions.

*WN*number of constants when the kernel function is pre-computed. With increasing interest in high-resolution images (in terms of number of pixels

*N*), high memory demands for these system might make on-the-fly computation preferable, especially those on embedded systems with limited memory such as field-programmable gate array [25

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]

## 3. Reconstruction error based on simulated data

_{2}error is shown in Fig. 5 and the average absolute error is shown in Fig. 6 .

_{2}error is defined in Eq. (8) as the normalized root mean square error of each A-line. The average absolute error is defined in Eq. (9) and shows the image error in dB scale. Readers should note that dB scale is not sensitive when displaying small errors. Note that increasing the kernel width provides a larger improvement on the accuracy than the oversampling ratio. Compared to other kernels, the KB kernel exhibits the lowest error for

*W*≥3, regardless of the oversampling ratio.

## 4. Experiment

**1**(5), 1309–1319 (2010). [CrossRef] [PubMed]

^{2}pixel size. The maximum line rate of the camera is 53 kHz and the data transfer is handled by a PCI camera link frame grabber (National Instrument) in base configuration with 32MB of onboard memory. The spectrometer was designed to realize a source limited axial resolution of 7 μm and an imaging depth of 1.73 mm.

### 4.1 Experimental reconstruction error and computational speed

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

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

*R*=2,

*W*=3) in the pre-computed mode has a processing time of 10.51 μs for a single A-line. This results in a theoretical reconstruction speed at over 95k A-lines per second. This is two orders of magnitude faster than the NDFT method. The processing speed for on-the-fly mode, however, depends primarily on the kernel functions used. The KB NUFFT (

*R*=2,

*W*=3) has a long computation time of 39.72 μs for one A-line due to the evaluation of the Bessel function. This limits the usefulness of the KB kernel for on-the-fly computation. Conversely, the calculation of the Gaussian function is based on a single exponential evaluation per point, and therefore much less computational expensive than the KB kernel. Although less accurate than the KB kernel at the same width, Gaussian based NUFFT for

*R*=2,

*W*=5 attains an error that is comparable to a KB based NUFFT with

*R*=2,

*W*=3, which makes it a suitable alternative when the kernel function cannot be pre-computed due to system limitations. The Gaussian kernel is often used in multidimensional MRI due to this speed advantage [15

**46**(3), 443–454 (2004). [CrossRef]

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]

### 4.2 Reconstruction error in high-speed in-vivo imaging of a human finger

*R*=2 and kernel width

*W*=3. Due to the high accuracy of NUFFT and the use of log scale display common to FD-OCT images, there are only subtle observable differences in the images in Fig. 8 .

*W*= 5 and the results are shown in Fig. 8. Improvements can be seen with all the kernels. Note that reconstruction with Gaussian NUFFT at

*W*= 5 displays an error that is comparable to the KB NUFFT at

*W*= 3, therefore making the Gaussian kernel a suitable choice when on-the-fly computation is needed.

## 5. Conclusion

*a priori.*In this mode of NUFFT the processing time is based only on the oversampling ratio and the kernel width, but the accuracy depends on an addition parameter – the kernel function. The most efficient processing method would employ the kernel that produces the lowest reconstruction error for a given

*R*and

*W.*This is found to be the Kaiser-Bessel function in this study.

*a priori*or for memory limited systems, the kernel is computed on-the-fly within the NUFFT algorithm. For these types of systems the Gaussian kernel, requiring only simple exponential evaluations, offers better efficiency than the Kaiser-Bessel kernel.

*W*other than the oversampling ratio

*R*has been shown to provide a larger improvement on the accuracy. Meanwhile, reducing the oversampling ratio other than the kernel width can reduce the computation complexity more efficiently. Therefore when speed and accuracy are both equally important, designers should choose the lowest oversampling ratio

*R>1*that will give a power of two sized oversampled array for efficient FFT calculation. The kernel width should then be chosen to achieve the desired reconstruction accuracy.

## Acknowledgments

## References and links

1. | Z. Hu and A. M. Rollins, “Fourier domain optical coherence tomography with a linear-in-wavenumber spectrometer,” Opt. Lett. |

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 |

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 |

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 |

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

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 |

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 |

8. | D. Hillmann, G. Huttmann, and P. Koch, “Using nonequispaced fast Fourier transformation to process optical coherence tomography signals,” Proc. SPIE |

9. | K. K. H. Chan and S. Tang, “High-speed spectral domain optical coherence tomography using non-uniform fast Fourier transform,” Biomed. Opt. Express |

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 |

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 |

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 |

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 |

14. | A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. |

15. | L. Greengard and J. Lee, “Accelerating the nonuniform Fast Fourier Transform,” SIAM Rev. |

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 |

17. | P. J. Beatty, D. G. Nishimura, and J. M. Pauly, “Rapid gridding reconstruction with a minimal oversampling ratio,” IEEE Trans. Med. Imaging |

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

19. | A. J. W. Duijndam and M. A. Schonewille, “Nonuniform fast Fourier transform,” Geophysics |

20. | J. A. Fessler and B. P. Sutton, “Nonuniform fast Fourier transforms using min-max interpolation,” IEEE Trans. Signal Process. |

21. | J. D. O’Sullivan, “A fast sinc function gridding algorithm for fourier inversion in computer tomography,” IEEE Trans. Med. Imaging |

22. | D. Potts, G. Steidl, and M. Tasche, “Fast Fourier transforms for nonequispaced data: a tutorial,” in |

23. | M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE |

24. | B. Liu, E. Azimi, and M. E. Brezinski, “True logarithmic amplification of frequency clock in SS-OCT for calibration,” Biomed. Opt. Express |

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

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

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 |

**OCIS Codes**

(170.4500) Medical optics and biotechnology : Optical coherence tomography

(070.2025) Fourier optics and signal processing : Discrete optical signal processing

(110.3010) Imaging systems : Image reconstruction techniques

**ToC Category:**

Medical Optics and Biotechnology

**History**

Original Manuscript: October 14, 2011

Revised Manuscript: December 3, 2011

Manuscript Accepted: December 5, 2011

Published: December 16, 2011

**Virtual Issues**

Vol. 7, Iss. 2 *Virtual Journal for Biomedical Optics*

**Citation**

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)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-19-27-26891

Sort: Year | Journal | Reset

### References

- 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. Express16(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. Photonics1(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. Express18(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. Express11(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. Express12(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. SPIE7372, 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. Express1(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. Express18(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. Express18(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. Express17(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. Express2(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. Imaging10(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. Imaging24(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,” Geophysics64(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. Imaging4(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. IEEE93(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. Express2(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. Imaging27(4), 538–547 (2008). [CrossRef] [PubMed]

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.