Abstract

The use of the discrete Fourier transform has decreased since the introduction of the fast Fourier transform (fFT), which is a numerically efficient computing process. This paper presents the iterative local Fourier transform (ilFT), a set of new processing algorithms that iteratively apply the discrete Fourier transform within a local and optimal frequency domain. The new technique achieves 210 times higher frequency resolution than the fFT within a comparable computation time. The method’s superb computing efficiency, high resolution, spectrum zoom-in capability, and overall performance are evaluated and compared to other advanced high-resolution Fourier transform techniques, such as the fFT combined with several fitting methods. The effectiveness of the ilFT is demonstrated through the data analysis of a set of Talbot self-images (1280 × 1024 pixels) obtained with an experimental setup using grating in a diverging beam produced by a coherent point source.

© 2016 Optical Society of America

Full Article  |  PDF Article
OSA Recommended Articles
Fast and noninterpolating method for subpixel displacement analysis of digital speckle images using phase shifts of spatial frequency spectra

Helin Lu, Chaohong Huang, Cheng Wang, Xiaozhong Wang, Hongyan Fu, and Ziyi Chen
Appl. Opt. 53(13) 2806-2814 (2014)

Nonuniform fast Fourier transform method for numerical diffraction simulation on tilted planes

Yu Xiao, Xiahui Tang, Yingxiong Qin, Hao Peng, Wei Wang, and Lijing Zhong
J. Opt. Soc. Am. A 33(10) 2027-2033 (2016)

References

  • View by:
  • |
  • |
  • |

  1. L. M. Sanchez-Brea, F. J. Torcal-Milla, J. M. Herrera-Fernandez, T. Morlanes, and E. Bernabeu, “Self-imaging technique for beam collimation,” Opt. Lett. 39(19), 5764–5767 (2014).
    [Crossref] [PubMed]
  2. K. Patorski, M. Trusiak, and K. Pokorski, “Diffraction grating three-beam interferometry without self-imaging regime contrast modulations,” Opt. Lett. 40(6), 1089–1092 (2015).
    [Crossref] [PubMed]
  3. K. Patorski, K. Pokorski, and M. Trusiak, “Circular-linear grating Talbot interferometry with moiré Fresnel imaging for beam collimation,” Opt. Lett. 39(2), 291–294 (2014).
    [Crossref] [PubMed]
  4. S. De Nicola, P. Ferraro, G. Coppola, A. Finizio, G. Pierattini, and S. Grilli, “Talbot self-image effect in digital holography and its application to spectrometry,” Opt. Lett. 29(1), 104–106 (2004).
    [Crossref] [PubMed]
  5. F. Pfeiffer, T. Weitkamp, O. Bunk, and C. David, “Phase retrieval and differential phase-contrast imaging with low-brilliance X-ray sources,” Nat. Phys. 2(4), 258–261 (2006).
    [Crossref]
  6. J. Luo, J. Bai, J. Zhang, C. Hou, K. Wang, and X. Hou, “Long focal-length measurement using divergent beam and two gratings of different periods,” Opt. Express 22(23), 27921–27931 (2014).
    [Crossref] [PubMed]
  7. C. van Loan, Computational Frameworks for the Fast Fourier Transform (SIAM, 1992).
  8. G. Bachmann, L. Narici, and E. Beckenstein, Fourier and wavelet analysis (Springer Science & Business Media, 2012).
  9. M. Frigo and S. G. Johnson, “FFTW: An adaptive software architecture for the FFT,” Acoustics, Speech and Signal Processing, 1998. Proceedings of the 1998 IEEE International Conference on Seattle, WA, (CSREA, 1998), pp. 1381–1384 vol.3.
    [Crossref]
  10. A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data,” SIAM J. Sci. Comput. 14(6), 1368–1393 (1993).
    [Crossref]
  11. J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16(10), 1059–1072 (1997).
    [Crossref]
  12. J. Dongarra and F. Sullivan, “Guest Editors Introduction to the top 10 algorithms,” Comput. Sci. Eng. 2(1), 22–23 (2000).
    [Crossref]
  13. J. S. Walker, Fast Fourier transforms (CRC, 1996), Vol. 24.
  14. D. G. Voelz, Computational Fourier Optics: A MATLAB® Tutorial (SPIE, 2011).
  15. M. Donadio, Digital Signal Processing Articles, “How to interpolate the peak location of a DFT or FFT if the frequency of interest is between bins.” (1999) http://dspguru.com/dsp/howtos/how-to-interpolate-fft-peak .
  16. J. P. Berrut and L. N. Trefethen, “Barycentric Lagrange interpolation,” SIAM Rev. 46(3), 501–517 (2004).
    [Crossref]
  17. J. P. Berrut, R. Baltensperger, and H. D. Mittelmann, “Recent developments in barycentric rational interpolation.” Trends and applications in constructive approximation (Birkhäuser Basel, 2005) 27–51.
  18. Ta-Hsin Li and Kai-Sheng Song, “Estimation of the parameters of sinusoidal signals in non-Gaussian noise,” IEEE Transactions on Signal Processing. (IEEE, 57(1), 62–72 (2009).
    [Crossref]
  19. J. Gai, F. Chan, Y. T. Chan, H. J. Du, and F. A. Dilkes, “Frequency Estimation of Uncooperative Coherent Pulse Radars,” in Proceedings of IEEE Conference on Military Communications (IEEE, 1988), pp. 1–7.
  20. J. Capon, “High-resolution frequency-wavenumber spectrum analysis,” in Proceedings of IEEE (IEEE, 1969), 57, pp. 1408–1418.
  21. Wikipedia, “Discrete Fourier transform,” https://en.wikipedia.org/wiki/Discrete_Fourier_transform .
  22. Y. Nakano and K. Murata, “Talbot interferometry for measuring the focal length of a lens,” Appl. Opt. 24(19), 3162–3166 (1985).
    [Crossref] [PubMed]
  23. A. Montaux-Lambert, P. Mercère, and J. Primot, “Interferogram conditioning for improved Fourier analysis and application to X-ray phase imaging by grating interferometry,” Opt. Express 23(22), 28479–28490 (2015).
    [Crossref] [PubMed]

2015 (2)

2014 (3)

2009 (1)

Ta-Hsin Li and Kai-Sheng Song, “Estimation of the parameters of sinusoidal signals in non-Gaussian noise,” IEEE Transactions on Signal Processing. (IEEE, 57(1), 62–72 (2009).
[Crossref]

2006 (1)

F. Pfeiffer, T. Weitkamp, O. Bunk, and C. David, “Phase retrieval and differential phase-contrast imaging with low-brilliance X-ray sources,” Nat. Phys. 2(4), 258–261 (2006).
[Crossref]

2004 (2)

2000 (1)

J. Dongarra and F. Sullivan, “Guest Editors Introduction to the top 10 algorithms,” Comput. Sci. Eng. 2(1), 22–23 (2000).
[Crossref]

1997 (1)

J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16(10), 1059–1072 (1997).
[Crossref]

1993 (1)

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

1985 (1)

Bai, J.

Bernabeu, E.

Berrut, J. P.

J. P. Berrut and L. N. Trefethen, “Barycentric Lagrange interpolation,” SIAM Rev. 46(3), 501–517 (2004).
[Crossref]

Bunk, O.

F. Pfeiffer, T. Weitkamp, O. Bunk, and C. David, “Phase retrieval and differential phase-contrast imaging with low-brilliance X-ray sources,” Nat. Phys. 2(4), 258–261 (2006).
[Crossref]

Chan, F.

J. Gai, F. Chan, Y. T. Chan, H. J. Du, and F. A. Dilkes, “Frequency Estimation of Uncooperative Coherent Pulse Radars,” in Proceedings of IEEE Conference on Military Communications (IEEE, 1988), pp. 1–7.

Chan, Y. T.

J. Gai, F. Chan, Y. T. Chan, H. J. Du, and F. A. Dilkes, “Frequency Estimation of Uncooperative Coherent Pulse Radars,” in Proceedings of IEEE Conference on Military Communications (IEEE, 1988), pp. 1–7.

Coppola, G.

David, C.

F. Pfeiffer, T. Weitkamp, O. Bunk, and C. David, “Phase retrieval and differential phase-contrast imaging with low-brilliance X-ray sources,” Nat. Phys. 2(4), 258–261 (2006).
[Crossref]

De Nicola, S.

Dilkes, F. A.

J. Gai, F. Chan, Y. T. Chan, H. J. Du, and F. A. Dilkes, “Frequency Estimation of Uncooperative Coherent Pulse Radars,” in Proceedings of IEEE Conference on Military Communications (IEEE, 1988), pp. 1–7.

Dongarra, J.

J. Dongarra and F. Sullivan, “Guest Editors Introduction to the top 10 algorithms,” Comput. Sci. Eng. 2(1), 22–23 (2000).
[Crossref]

Du, H. J.

J. Gai, F. Chan, Y. T. Chan, H. J. Du, and F. A. Dilkes, “Frequency Estimation of Uncooperative Coherent Pulse Radars,” in Proceedings of IEEE Conference on Military Communications (IEEE, 1988), pp. 1–7.

Dutt, A.

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

Ferraro, P.

Finizio, A.

Gai, J.

J. Gai, F. Chan, Y. T. Chan, H. J. Du, and F. A. Dilkes, “Frequency Estimation of Uncooperative Coherent Pulse Radars,” in Proceedings of IEEE Conference on Military Communications (IEEE, 1988), pp. 1–7.

Grilli, S.

Herrera-Fernandez, J. M.

Hou, C.

Hou, X.

Kai-Sheng Song,

Ta-Hsin Li and Kai-Sheng Song, “Estimation of the parameters of sinusoidal signals in non-Gaussian noise,” IEEE Transactions on Signal Processing. (IEEE, 57(1), 62–72 (2009).
[Crossref]

Luo, J.

Mercère, P.

Montaux-Lambert, A.

Morlanes, T.

Murata, K.

Nakano, Y.

Patorski, K.

Pfeiffer, F.

F. Pfeiffer, T. Weitkamp, O. Bunk, and C. David, “Phase retrieval and differential phase-contrast imaging with low-brilliance X-ray sources,” Nat. Phys. 2(4), 258–261 (2006).
[Crossref]

Phillips, J. R.

J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16(10), 1059–1072 (1997).
[Crossref]

Pierattini, G.

Pokorski, K.

Primot, J.

Rokhlin, V.

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

Sanchez-Brea, L. M.

Sullivan, F.

J. Dongarra and F. Sullivan, “Guest Editors Introduction to the top 10 algorithms,” Comput. Sci. Eng. 2(1), 22–23 (2000).
[Crossref]

Ta-Hsin Li,

Ta-Hsin Li and Kai-Sheng Song, “Estimation of the parameters of sinusoidal signals in non-Gaussian noise,” IEEE Transactions on Signal Processing. (IEEE, 57(1), 62–72 (2009).
[Crossref]

Torcal-Milla, F. J.

Trefethen, L. N.

J. P. Berrut and L. N. Trefethen, “Barycentric Lagrange interpolation,” SIAM Rev. 46(3), 501–517 (2004).
[Crossref]

Trusiak, M.

Wang, K.

Weitkamp, T.

F. Pfeiffer, T. Weitkamp, O. Bunk, and C. David, “Phase retrieval and differential phase-contrast imaging with low-brilliance X-ray sources,” Nat. Phys. 2(4), 258–261 (2006).
[Crossref]

White, J. K.

J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16(10), 1059–1072 (1997).
[Crossref]

Zhang, J.

Appl. Opt. (1)

Comput. Sci. Eng. (1)

J. Dongarra and F. Sullivan, “Guest Editors Introduction to the top 10 algorithms,” Comput. Sci. Eng. 2(1), 22–23 (2000).
[Crossref]

IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. (1)

J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16(10), 1059–1072 (1997).
[Crossref]

IEEE Transactions on Signal Processing. (IEEE, (1)

Ta-Hsin Li and Kai-Sheng Song, “Estimation of the parameters of sinusoidal signals in non-Gaussian noise,” IEEE Transactions on Signal Processing. (IEEE, 57(1), 62–72 (2009).
[Crossref]

Nat. Phys. (1)

F. Pfeiffer, T. Weitkamp, O. Bunk, and C. David, “Phase retrieval and differential phase-contrast imaging with low-brilliance X-ray sources,” Nat. Phys. 2(4), 258–261 (2006).
[Crossref]

Opt. Express (2)

Opt. Lett. (4)

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)

J. P. Berrut and L. N. Trefethen, “Barycentric Lagrange interpolation,” SIAM Rev. 46(3), 501–517 (2004).
[Crossref]

Other (10)

J. P. Berrut, R. Baltensperger, and H. D. Mittelmann, “Recent developments in barycentric rational interpolation.” Trends and applications in constructive approximation (Birkhäuser Basel, 2005) 27–51.

J. S. Walker, Fast Fourier transforms (CRC, 1996), Vol. 24.

D. G. Voelz, Computational Fourier Optics: A MATLAB® Tutorial (SPIE, 2011).

M. Donadio, Digital Signal Processing Articles, “How to interpolate the peak location of a DFT or FFT if the frequency of interest is between bins.” (1999) http://dspguru.com/dsp/howtos/how-to-interpolate-fft-peak .

C. van Loan, Computational Frameworks for the Fast Fourier Transform (SIAM, 1992).

G. Bachmann, L. Narici, and E. Beckenstein, Fourier and wavelet analysis (Springer Science & Business Media, 2012).

M. Frigo and S. G. Johnson, “FFTW: An adaptive software architecture for the FFT,” Acoustics, Speech and Signal Processing, 1998. Proceedings of the 1998 IEEE International Conference on Seattle, WA, (CSREA, 1998), pp. 1381–1384 vol.3.
[Crossref]

J. Gai, F. Chan, Y. T. Chan, H. J. Du, and F. A. Dilkes, “Frequency Estimation of Uncooperative Coherent Pulse Radars,” in Proceedings of IEEE Conference on Military Communications (IEEE, 1988), pp. 1–7.

J. Capon, “High-resolution frequency-wavenumber spectrum analysis,” in Proceedings of IEEE (IEEE, 1969), 57, pp. 1408–1418.

Wikipedia, “Discrete Fourier transform,” https://en.wikipedia.org/wiki/Discrete_Fourier_transform .

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 (9)

Fig. 1
Fig. 1 Schematic flow chart showing the iterative spectrum zoom-in algorithm implemented in the ilFT method.
Fig. 2
Fig. 2 Conceptual diagram depicting spectral value recycling during ilFT iterations.
Fig. 3
Fig. 3 Numerical case-study simulations comparing different Fourier analysis methods.
Fig. 4
Fig. 4 Log-log plot comparing the computing efficiency between zero-padding fFT and ilFT.
Fig. 5
Fig. 5 Input frequency vs. evaluated frequency plot (with < ~0.1 s processing time limit). The zero-padding fFT failed to trace the varying input frequency but the fitting fFT and the ilFT showed a good correlation between the input and evaluated values.
Fig. 6
Fig. 6 Zero-padding fFT result showing the overall spectrum of the input data (a) and the zoom-in (red-box) spectrum comparing the ilFT and fitting fFT near the region of interest (b).
Fig. 7
Fig. 7 (a) Talbot self-image experiment setup, (b) schematic layout (PH: pinhole, Sz: translation length), and (c) measured Talbot self-image.
Fig. 8
Fig. 8 Partial section of the frequency spectrum calculated by (a) the standard MATLAB fFT and (b) by ilFT for the Talbot self-image shown in Fig. 7(c). fx and fy represents the spatial frequency in x and y axis, respectively.
Fig. 9
Fig. 9 Magnified period p’ of the measured Talbot self-images as a function of pinhole-to-grating distance, denoted by the micrometer reading Sz. The red squares represent the fFT result and the black squares the ilFT result. The black solid line corresponds to the expected theoretical model.

Equations (5)

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

G( f x , f y )= Δ 2 i,j=1 N g( x i , y j ) e j2π( f x x i + f y y j ) ,
x i =iΔ and y j =jΔ.
p'=p( 1 d z ),
z= z 0 + S z ,
| Δp' |=p ' 2 Δf.

Metrics