Abstract

In this paper, we discuss two effective methods for computing optical propagations using two-dimensional (2D) discrete Fourier transforms: the matrix triple product (MTP) and the chirp z-transform (CZT) and analyze their performance both in theory and via benchmarks compared to the performance of a traditional padded fast Fourier transform (FFT). We show that, in many regimes of interest for phase-retrieval algorithms, the MTP or CZT is comparable to or better than the FFT in terms of run time while offering more flexible control over the sampling. We propose that for many applications, the CZT makes a robust general purpose alternative to the padded 2D FFT.

© 2018 Optical Society of America

Full Article  |  PDF Article
OSA Recommended Articles
Phase retrieval with unknown sampling factors via the two-dimensional chirp z-transform

Alden S. Jurling and James R. Fienup
J. Opt. Soc. Am. A 31(9) 1904-1911 (2014)

Fast computation of Lyot-style coronagraph propagation

R. Soummer, L. Pueyo, A. Sivaramakrishnan, and R. J. Vanderbei
Opt. Express 15(24) 15935-15951 (2007)

Fast nonparaxial scalar focal field calculations

Matthias Hillenbrand, Armin Hoffmann, Damien P. Kelly, and Stefan Sinzinger
J. Opt. Soc. Am. A 31(6) 1206-1214 (2014)

References

  • View by:
  • |
  • |
  • |

  1. J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput. 19, 297–301 (1965).
    [Crossref]
  2. M. Frigo and S. Johnson, “FFTW: an adaptive software architecture for the FFT,” in IEEE International Conference on Acoustics, Speech and Signal Processing (1998).
  3. M. Frigo and S. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93, 216–231 (2005).
    [Crossref]
  4. J. R. Fienup, “Phase retrieval for undersampled broadband images,” J. Opt. Soc. Am. A 16, 1831–1837 (1999).
    [Crossref]
  5. J. R. Fienup, “Phase retrieval with broadband light,” in Frontiers in Optics 2011/Laser Science XXVII (Optical Society of America, 2011), paper FThD5.
  6. M. D. Bergkoetter and J. R. Fienup, “Phase retrieval with linear chromatic dispersion,” in Imaging and Applied Optics (Optical Society of America, 2016), paper CT4C.5.
  7. M. D. Bergkoetter, “Phase retrieval for chromatic aberrations and wide-field detectors,” Ph.D. dissertation (University of Rochester, 2017).
  8. J. W. Goodman, Introduction to Fourier Optics, 3rd ed. (Roberts, 2005).
  9. R. D. Fiete, “Image quality and λFN/p for remote sensing systems,” Opt. Eng. 38, 1229–1240 (1999).
    [Crossref]
  10. R. Soummer, L. Pueyo, A. Sivaramakrishnan, and R. J. Vanderbei, “Fast computation of Lyot-style coronagraph propagation,” Opt. Express 15, 15935–15951 (2007).
    [Crossref]
  11. M. Guizar-Sicairos, S. T. Thurman, and J. R. Fienup, “Efficient subpixel image registration algorithms,” Opt. Lett. 33, 156–158 (2008).
    [Crossref]
  12. A. J. Stothers, “On the complexity of matrix multiplication,” Ph.D. dissertation (University of Edinburgh, 2010).
  13. N. Brenner, “Fast Fourier transform of externally stored data,” IEEE Trans. Audio Electroacoust. 17, 128–132 (1969).
    [Crossref]
  14. G. Rivard, “Direct fast Fourier transform of bivariate functions,” IEEE Trans. Acoust. Speech Signal Process. 25, 250–252 (1977).
    [Crossref]
  15. M. Andrews and R. E. Boring, “Architectural study of adaptive algorithms for adaptive beam communication antennas,” , 1988.
  16. L. Rabiner, R. Schafer, and C. Rader, “The chirp z-transform algorithm,” IEEE Trans. Audio Electroacoust. 17, 86–92 (1969).
    [Crossref]
  17. L. Bluestein, “A linear filtering approach to the computation of discrete Fourier transform,” IEEE Trans. Audio Electroacoust. 18, 451–455 (1970).
    [Crossref]
  18. D. H. Bailey and P. N. Swarztrauber, “The fractional Fourier transform and applications,” SIAM Rev. 33, 389–404 (1991).
    [Crossref]
  19. K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
    [Crossref]
  20. G. Pretzler, A. Kasper, and K. Witte, “Angular chirp and tilted light pulses in CPA lasers,” Appl. Phys. B 70, 1–9 (2000).
    [Crossref]
  21. H.-M. Heuck, P. Neumayer, T. Kühl, and U. Wittrock, “Chromatic aberration in petawatt-class lasers,” Appl. Phys. B 84, 421–428 (2006).
    [Crossref]
  22. B. E. Kruschwitz, S.-W. Bahk, J. Bromage, M. D. Moore, and D. Irwin, “Accurate target-plane focal-spot characterization in high-energy laser systems using phase retrieval,” Opt. Express 20, 20874–20883 (2012).
    [Crossref]
  23. Nvidia Corporation, “CUDA toolkit documentation,” http://docs.nvidia.com/cuda/cufft/#introduction .

2012 (1)

2008 (1)

2007 (1)

2006 (1)

H.-M. Heuck, P. Neumayer, T. Kühl, and U. Wittrock, “Chromatic aberration in petawatt-class lasers,” Appl. Phys. B 84, 421–428 (2006).
[Crossref]

2005 (1)

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

2004 (1)

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

2000 (1)

G. Pretzler, A. Kasper, and K. Witte, “Angular chirp and tilted light pulses in CPA lasers,” Appl. Phys. B 70, 1–9 (2000).
[Crossref]

1999 (2)

J. R. Fienup, “Phase retrieval for undersampled broadband images,” J. Opt. Soc. Am. A 16, 1831–1837 (1999).
[Crossref]

R. D. Fiete, “Image quality and λFN/p for remote sensing systems,” Opt. Eng. 38, 1229–1240 (1999).
[Crossref]

1991 (1)

D. H. Bailey and P. N. Swarztrauber, “The fractional Fourier transform and applications,” SIAM Rev. 33, 389–404 (1991).
[Crossref]

1977 (1)

G. Rivard, “Direct fast Fourier transform of bivariate functions,” IEEE Trans. Acoust. Speech Signal Process. 25, 250–252 (1977).
[Crossref]

1970 (1)

L. Bluestein, “A linear filtering approach to the computation of discrete Fourier transform,” IEEE Trans. Audio Electroacoust. 18, 451–455 (1970).
[Crossref]

1969 (2)

L. Rabiner, R. Schafer, and C. Rader, “The chirp z-transform algorithm,” IEEE Trans. Audio Electroacoust. 17, 86–92 (1969).
[Crossref]

N. Brenner, “Fast Fourier transform of externally stored data,” IEEE Trans. Audio Electroacoust. 17, 128–132 (1969).
[Crossref]

1965 (1)

J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[Crossref]

Andrews, M.

M. Andrews and R. E. Boring, “Architectural study of adaptive algorithms for adaptive beam communication antennas,” , 1988.

Bahk, S.-W.

Bailey, D. H.

D. H. Bailey and P. N. Swarztrauber, “The fractional Fourier transform and applications,” SIAM Rev. 33, 389–404 (1991).
[Crossref]

Bergkoetter, M. D.

M. D. Bergkoetter and J. R. Fienup, “Phase retrieval with linear chromatic dispersion,” in Imaging and Applied Optics (Optical Society of America, 2016), paper CT4C.5.

M. D. Bergkoetter, “Phase retrieval for chromatic aberrations and wide-field detectors,” Ph.D. dissertation (University of Rochester, 2017).

Bluestein, L.

L. Bluestein, “A linear filtering approach to the computation of discrete Fourier transform,” IEEE Trans. Audio Electroacoust. 18, 451–455 (1970).
[Crossref]

Boring, R. E.

M. Andrews and R. E. Boring, “Architectural study of adaptive algorithms for adaptive beam communication antennas,” , 1988.

Brenner, N.

N. Brenner, “Fast Fourier transform of externally stored data,” IEEE Trans. Audio Electroacoust. 17, 128–132 (1969).
[Crossref]

Bromage, J.

Cooley, J. W.

J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[Crossref]

Csatari, M.

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

Fienup, J. R.

M. Guizar-Sicairos, S. T. Thurman, and J. R. Fienup, “Efficient subpixel image registration algorithms,” Opt. Lett. 33, 156–158 (2008).
[Crossref]

J. R. Fienup, “Phase retrieval for undersampled broadband images,” J. Opt. Soc. Am. A 16, 1831–1837 (1999).
[Crossref]

J. R. Fienup, “Phase retrieval with broadband light,” in Frontiers in Optics 2011/Laser Science XXVII (Optical Society of America, 2011), paper FThD5.

M. D. Bergkoetter and J. R. Fienup, “Phase retrieval with linear chromatic dispersion,” in Imaging and Applied Optics (Optical Society of America, 2016), paper CT4C.5.

Fiete, R. D.

R. D. Fiete, “Image quality and λFN/p for remote sensing systems,” Opt. Eng. 38, 1229–1240 (1999).
[Crossref]

Frigo, M.

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

M. Frigo and S. Johnson, “FFTW: an adaptive software architecture for the FFT,” in IEEE International Conference on Acoustics, Speech and Signal Processing (1998).

Goodman, J. W.

J. W. Goodman, Introduction to Fourier Optics, 3rd ed. (Roberts, 2005).

Guizar-Sicairos, M.

Heiner, Z.

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

Heuck, H.-M.

H.-M. Heuck, P. Neumayer, T. Kühl, and U. Wittrock, “Chromatic aberration in petawatt-class lasers,” Appl. Phys. B 84, 421–428 (2006).
[Crossref]

Irwin, D.

Johnson, S.

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

M. Frigo and S. Johnson, “FFTW: an adaptive software architecture for the FFT,” in IEEE International Conference on Acoustics, Speech and Signal Processing (1998).

Kasper, A.

G. Pretzler, A. Kasper, and K. Witte, “Angular chirp and tilted light pulses in CPA lasers,” Appl. Phys. B 70, 1–9 (2000).
[Crossref]

Klebniczki, J.

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

Kovacs, A.

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

Kruschwitz, B. E.

Kühl, T.

H.-M. Heuck, P. Neumayer, T. Kühl, and U. Wittrock, “Chromatic aberration in petawatt-class lasers,” Appl. Phys. B 84, 421–428 (2006).
[Crossref]

Kurdi, G.

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

Moore, M. D.

Neumayer, P.

H.-M. Heuck, P. Neumayer, T. Kühl, and U. Wittrock, “Chromatic aberration in petawatt-class lasers,” Appl. Phys. B 84, 421–428 (2006).
[Crossref]

Osvay, K.

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

Pretzler, G.

G. Pretzler, A. Kasper, and K. Witte, “Angular chirp and tilted light pulses in CPA lasers,” Appl. Phys. B 70, 1–9 (2000).
[Crossref]

Pueyo, L.

Rabiner, L.

L. Rabiner, R. Schafer, and C. Rader, “The chirp z-transform algorithm,” IEEE Trans. Audio Electroacoust. 17, 86–92 (1969).
[Crossref]

Rader, C.

L. Rabiner, R. Schafer, and C. Rader, “The chirp z-transform algorithm,” IEEE Trans. Audio Electroacoust. 17, 86–92 (1969).
[Crossref]

Rivard, G.

G. Rivard, “Direct fast Fourier transform of bivariate functions,” IEEE Trans. Acoust. Speech Signal Process. 25, 250–252 (1977).
[Crossref]

Schafer, R.

L. Rabiner, R. Schafer, and C. Rader, “The chirp z-transform algorithm,” IEEE Trans. Audio Electroacoust. 17, 86–92 (1969).
[Crossref]

Sivaramakrishnan, A.

Soummer, R.

Stothers, A. J.

A. J. Stothers, “On the complexity of matrix multiplication,” Ph.D. dissertation (University of Edinburgh, 2010).

Swarztrauber, P. N.

D. H. Bailey and P. N. Swarztrauber, “The fractional Fourier transform and applications,” SIAM Rev. 33, 389–404 (1991).
[Crossref]

Thurman, S. T.

Tukey, J. W.

J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[Crossref]

Vanderbei, R. J.

Witte, K.

G. Pretzler, A. Kasper, and K. Witte, “Angular chirp and tilted light pulses in CPA lasers,” Appl. Phys. B 70, 1–9 (2000).
[Crossref]

Wittrock, U.

H.-M. Heuck, P. Neumayer, T. Kühl, and U. Wittrock, “Chromatic aberration in petawatt-class lasers,” Appl. Phys. B 84, 421–428 (2006).
[Crossref]

Appl. Phys. B (2)

G. Pretzler, A. Kasper, and K. Witte, “Angular chirp and tilted light pulses in CPA lasers,” Appl. Phys. B 70, 1–9 (2000).
[Crossref]

H.-M. Heuck, P. Neumayer, T. Kühl, and U. Wittrock, “Chromatic aberration in petawatt-class lasers,” Appl. Phys. B 84, 421–428 (2006).
[Crossref]

IEEE J. Sel. Top. Quantum Electron. (1)

K. Osvay, A. Kovacs, Z. Heiner, G. Kurdi, J. Klebniczki, and M. Csatari, “Angular dispersion and temporal change of femtosecond pulses from misaligned pulse compressors,” IEEE J. Sel. Top. Quantum Electron. 10, 213–220 (2004).
[Crossref]

IEEE Trans. Acoust. Speech Signal Process. (1)

G. Rivard, “Direct fast Fourier transform of bivariate functions,” IEEE Trans. Acoust. Speech Signal Process. 25, 250–252 (1977).
[Crossref]

IEEE Trans. Audio Electroacoust. (3)

L. Rabiner, R. Schafer, and C. Rader, “The chirp z-transform algorithm,” IEEE Trans. Audio Electroacoust. 17, 86–92 (1969).
[Crossref]

L. Bluestein, “A linear filtering approach to the computation of discrete Fourier transform,” IEEE Trans. Audio Electroacoust. 18, 451–455 (1970).
[Crossref]

N. Brenner, “Fast Fourier transform of externally stored data,” IEEE Trans. Audio Electroacoust. 17, 128–132 (1969).
[Crossref]

J. Opt. Soc. Am. A (1)

Math. Comput. (1)

J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[Crossref]

Opt. Eng. (1)

R. D. Fiete, “Image quality and λFN/p for remote sensing systems,” Opt. Eng. 38, 1229–1240 (1999).
[Crossref]

Opt. Express (2)

Opt. Lett. (1)

Proc. IEEE (1)

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

SIAM Rev. (1)

D. H. Bailey and P. N. Swarztrauber, “The fractional Fourier transform and applications,” SIAM Rev. 33, 389–404 (1991).
[Crossref]

Other (8)

M. Andrews and R. E. Boring, “Architectural study of adaptive algorithms for adaptive beam communication antennas,” , 1988.

M. Frigo and S. Johnson, “FFTW: an adaptive software architecture for the FFT,” in IEEE International Conference on Acoustics, Speech and Signal Processing (1998).

A. J. Stothers, “On the complexity of matrix multiplication,” Ph.D. dissertation (University of Edinburgh, 2010).

J. R. Fienup, “Phase retrieval with broadband light,” in Frontiers in Optics 2011/Laser Science XXVII (Optical Society of America, 2011), paper FThD5.

M. D. Bergkoetter and J. R. Fienup, “Phase retrieval with linear chromatic dispersion,” in Imaging and Applied Optics (Optical Society of America, 2016), paper CT4C.5.

M. D. Bergkoetter, “Phase retrieval for chromatic aberrations and wide-field detectors,” Ph.D. dissertation (University of Rochester, 2017).

J. W. Goodman, Introduction to Fourier Optics, 3rd ed. (Roberts, 2005).

Nvidia Corporation, “CUDA toolkit documentation,” http://docs.nvidia.com/cuda/cufft/#introduction .

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. Visual depiction of the sizes of the input array g ( M × N ), output array G ( R × S ), and DFT period ( K × L ).
Fig. 2.
Fig. 2. Run time comparison for Q I = Q P = 1 as a function of PSF size R for a monochromatic simulation.
Fig. 3.
Fig. 3. Run time comparison for Q I = Q P = 2 as a function of PSF size R for a monochromatic simulation.
Fig. 4.
Fig. 4. Time versus Q P , for PSF size of 1024 × 1024 pixels. Image size is held fixed and pupil sampling is varied to accommodate the change in Q P .
Fig. 5.
Fig. 5. Timing comparison for a broadband simulation.
Fig. 6.
Fig. 6. Timing comparison for a narrowband polychromatic simulation.
Fig. 7.
Fig. 7. 2D FFT times on the GPU, including highly noncomposite array sizes.
Fig. 8.
Fig. 8. 2D FFT times on the CPU (FFTW), including highly noncomposite array sizes.

Tables (2)

Tables Icon

Table 1. Summary of Computational Complexities

Tables Icon

Table 2. Mathematical Symbols

Equations (75)

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

G ( f x , f y ) = g ( x , y ) exp [ 2 π i ( f x x + f y y ) ] d x d y .
G [ r , s ] = m , n M , N g [ m , n ] exp [ 2 π i ( m r Δ x Δ f x + n s Δ y Δ f y ) ] ,
M = D x Δ x , N = D y Δ y .
M = { 0 , , M 1 }
M = { M / 2 , , M / 2 1 } ,
R = C x Δ f x , S = C y Δ f y .
G [ r , s ] = m , n M , N g [ m , n ] exp [ 2 π i ( m r K + n s L ) ] ,
K = 1 Δ x Δ f x , L = 1 Δ y Δ f y .
comb ( ξ , η ) p , q = δ ( ξ p ) δ ( η q ) ,
comb ( ξ , η ) FT comb ( f ξ , f η ) .
g S ( x , y ) = comb ( x Δ x , y Δ y ) g ( x , y ) = m , n M , N g ( m Δ x , n Δ y ) δ ( x m Δ x ) δ ( y n Δ y ) Δ x Δ y ,
G P ( f x , f y ) = G ( f x , f y ) * comb ( f x Δ x , f y Δ y ) Δ x Δ y = p , q = G ( f x p Δ x , f y q Δ y ) ,
G P ( f x + p Δ x , f y + q Δ y ) = G P ( f x , f y ) ,
g P ( x , y ) = g ( x , y ) * comb ( x T x , y T y ) 1 T x T y ,
g P ( x , y ) = g P ( x + T x p ˜ , y + T y q ˜ ) ,
G S ( f x , f y ) = G ( f x , f y ) comb ( f x T x , f y T y ) ,
g SP ( x , y ) = g S ( x , y ) * comb ( x T x , y T y ) 1 T x T y = [ comb ( x Δ x , y Δ y ) g ( x , y ) ] * comb ( x T x , y T y ) 1 T x T y ,
G PS ( f x , f y ) = G P ( f x , f y ) comb ( f x T x , f y T y ) = [ G ( f x , f y ) * comb ( f x Δ x , f y Δ y ) Δ x Δ y ] × comb ( f x T x , f y T y ) ,
G PS ( f x , f y ) = r , s = G P ( f x , f y ) δ ( f x r Δ f x ) δ ( f y s Δ f y ) Δ f x Δ f y ,
G [ r , s ] = G P ( r Δ f x , s Δ f y )
G PS ( f x , f y ) = r , s = G [ r , s ] δ ( f x r Δ f x ) δ ( f y s Δ f y ) Δ f x Δ f y ,
g SP ( x , y ) = m , n = g [ m , n ] δ ( x m Δ x ) δ ( y n Δ y ) Δ x Δ y .
G PS ( f x , f y ) = m , n = g [ m , n ] exp [ 2 π i ( f x m Δ x + f y n Δ y ) ] .
G PS ( f x , f y ) = m , n = { m , n M , N g [ m , n ] × exp [ 2 π i ( f x ( m + K m ) Δ x + f y ( n + L n ) Δ y ) ] } ,
G PS ( f x , f y ) = m , n = exp [ 2 π i ( m f x Δ f x + n f y Δ f y ) ] × m , n M , N g [ m , n ] exp [ 2 π i ( f x m Δ x + f y n Δ y ) ] .
G PS ( f x , f y ) = r , s = δ ( f x r Δ f x ) δ ( f y s Δ f y ) × m , n M , N g [ m , n ] exp [ 2 π i ( m r Δ x Δ f x + n s Δ y Δ f y ) ] .
G [ r , s ] = m , n M , N g [ m , n ] exp [ 2 π i ( m r Δ x Δ f x + n s Δ y Δ f y ) ] ,
Q x P = K M Q y P = L N Q x I = K R Q y I = L S .
M Q x P = R Q x I = K ,
N Q y P = S Q y I = L .
M = Q x I R Q x P ,
t FFT K L log 2 ( K L ) .
t INT M N R S .
G [ r , s ] = m exp ( 2 π i Δ x Δ f x m r ) × [ n g [ m , n ] exp ( 2 π i Δ y Δ f y n s ) ] m s ,
t MTP 1 R M S + M N S = M S ( N + R ) .
Ω x [ r , m ] = exp ( 2 π i Δ x Δ f x m r ) ,
Ω y [ n , s ] = exp ( 2 π i Δ y Δ f y n s ) ,
G = Ω x g Ω y ,
G = Ω x ( g Ω y ) ,
G = ( Ω x g ) Ω y
t MTP 2 R M N + R N S = N R ( M + S ) .
t MTP Q I Q P R 3 ( 1 + Q I Q P ) .
α x Δ f x Δ x = 1 K , α y Δ f y Δ y = 1 L ,
G [ r , s ] = m , n M , N g [ m , n ] exp [ i 2 π ( m r α x + n s α y ) ] .
2 m r = m 2 + r 2 ( r m ) 2 , 2 n s = n 2 + s 2 ( s n ) 2 ,
G [ r , s ] = exp [ i π ( r 2 α x + s 2 α y ) ] × m , n M , N { exp [ i π ( m 2 α x + n 2 α y ) ] × g [ m , n ] exp { i π [ ( r m ) 2 α x + ( s n ) 2 α y ] } } ,
G [ r , s ] = a [ r , s ] m , n M , N b [ m , n ] g [ m , n ] h [ r m , s n ] ,
a [ r , s ] exp [ i π ( r 2 α x + s 2 α y ) ] ,
b [ m , n ] exp [ i π ( m 2 α x + n 2 α y ) ] ,
h [ m , n ] exp [ i π ( m 2 α x + n 2 α y ) ] .
g ^ [ m , n ] { g [ m , n ] , ( 0 m < M ) & ( 0 n < N ) 0 , ( M m < K ) ( N n < L ) ,
b ^ [ m , n ] { b [ m , n ] , ( 0 m < M ) & ( 0 n < N ) 0 , ( M m < K ) ( N n < L ) ,
h ^ x [ m ] { exp [ i π m 2 α x ] , 0 m R 1 arbitrary , R 1 < m < K M + 1 exp [ i π ( m K ) 2 α x ] , K M + 1 m < K ,
h ^ y [ n ] { exp [ i π n 2 α y ] , 0 n S 1 arbitrary , S 1 < n < L N + 1 exp [ i π ( n L ) 2 α y ] , L N + 1 n < L ,
h ^ [ m , n ] = h ^ x [ m ] h ^ y [ n ] .
K M + R 1 ,
L N + S 1.
G = a crop [ ( b ^ g ^ ) * h ^ ] ,
G = a crop [ F 1 { F { b ^ g ^ } H ^ } ] ,
t CZT K L log 2 ( K L ) .
t CZT ( M + R ) ( N + S ) log 2 [ ( M + R ) ( N + S ) ] .
t CZT [ R ( 1 + Q I Q P ) ] 2 log 2 R ( 1 + Q I Q P ) .
I ( u , v ) = w ( λ ) | A ( x , y ; λ ) exp [ i 2 π λ W ( x , y ; λ ) ] × exp [ i 2 π λ f ( u x + v y ) ] d x d y | 2 d λ ,
I [ r , s ] = k w k | m , n A [ m , n ; λ k ] exp { i 2 π λ k W [ m , n ; λ k ] } × exp [ i 2 π λ k f ( m r Δ u Δ x + n s Δ v Δ y ) ] | 2 ,
Δ f x Δ u λ k f , Δ f y Δ v λ k f .
Q x , k P = λ k f D x Δ u , Q y , k P = λ k f D y Δ v .
K k = λ k f Δ x Δ u , L k = λ k f Δ y Δ v .
K Q I R , L Q I S
M Q I R Q x P , N Q I S Q y P ,
K k = λ k λ 0 Q I R , L k = λ k λ 0 Q I S .
t FFT , k ( λ k λ 0 Q I R ) 2 log 2 ( λ k λ 0 Q I R ) ,
Δ K = Δ λ λ 0 K 0 , Δ L = Δ λ λ 0 S 0 .
K 0 , L 0 λ 0 Δ λ .
t FFT , k [ λ k λ 0 max ( Q I R , λ k Δ λ ) ] 2 log 2 [ λ k λ 0 max ( Q I R , λ k Δ λ ) ] .
λ 0 f Δ x Δ u = K 0 .

Metrics