|
Pink 0.9
|
fast Fourier transform More...
fast Fourier transform
Usage: fft in.pgm [dir] out.pgm
Description: Computes the 2 dimensional Fast Fourier Transform of an image.
This program will compute either a forward or inverse FFT, depending on the direction requested with the dir option. A dir value of 0 will result in a forward FFT, and a dir value of 1 will result in an inverse FFT.
The arguments are described as follows:
in.pgm specifies the input image, which must be of data type COMPLEX.
out.pgm output image, which will be an image of data type COMPLEX. If row size or column size of in.pgm is not an integral power of 2, then input data is padded and dimensions of out.pgm may be different from those of in.pgm .
dir (optional) specifies the FFT direction. A dir of 0 (default) will result in a forward FFT, and a dir of 1 will result in an inverse FFT.
This particular implementation of the DFT uses the transform pair defined as follows:
Let there be two complex arrays each with n rows and m columns.
Index them as
f(x,y): 0 <= x <= m - 1, 0 <= y <= n - 1
F(u,v): -m/2 <= u <= m/2 - 1, -n/2 <= v <= n/2 - 1
Then the forward and inverse transforms are related as follows.
Forward:
F(u,v) = {x=0}^{m-1} {y=0}^{n-1} f(x,y) {-2 i (ux/m + vy/n)}
Inverse:
f(x,y) = 1/(mn) {u=-m/2}^{m/2-1} {v=-n/2}^{n/2-1} F(u,v) {2 i (ux/m + vy/n)}
Therefore, the transforms have these properties:
1. f(x,y) = F(0,0)
2. m n |f(x,y)|^2 = |F(u,v)|^2
Types supported: complex 2d
Category: signal
1.7.3