18.11.1.2 Algorithms (2D FFT)

Because of the separability of 2D DFT, we can rewrite its definition as:

F(u,v) = \frac{1}{{MN}}\sum_{x = 0}^{M-1} {\sum_{y = 0}^{N-1} {f(x,y)} } e^{ - i2\pi(ux/M + vy/N)} = \frac{1}{M}\sum_{x = 0}^{M - 1} {e^{ - i2\pi xu/M} } (\frac{1}{N}\sum_{y = 0}^{N - 1} {f(x,y)e^{ - i2\pi yv/N} })

This shows that a 2D FFT can be broken down into a series of 1D Fourier transforms. To compute a 2D FFT, 1D Fourier transform is applied to each individual row of the input matrix and then to each column.

Origin uses the FFTW library for its Fast Fourier Transform code.

English | Deutsch | 日本語