Name

fft - calculate forward or inverse Fourier transform of an 1-2-3D image

Usage

output = fft(image,[npad])

Input

image

input image, if real, the forward Fourier transform is calculated, if Fourier, the inverse Fourier transform is calculated. Input image is not modified by this command.

npad

optional integer argument that specifies how many time the input image will be padded with zeroes before Fourier transform is computed. Default is npad=1, meaning no additional padding is performed (only extension of the x dimension, see Description). npad = 3 means the real image will be padded with zeros to three times the original size and, in addition, its x dimension will be extended.

Output

output

the forward or inverse Fourier transform of the input image. The dimensions of the output image differ from that of the input image, i.e., if the input was real, the output image will have the x dimension extended. If the input was Fourier (and padded), the output image will have the size of the original real image (without padding). For details, see Description.

Description

• If input image is real, the x dimension n will be extended to accomodate full half of the Fourier transform.

  • for n even, the x dimension of the output image is n+2

  • for n odd, the x dimension of the output image is n+1

• Thus, the x dimension of the output image is n + 2 - mod(n,2)

• The Fourier image will have following attributes set: is_complex = True, is_fftodd = True if the input real image had odd x dimension, False, if x was even, fftpad = True, npad =1 (for some techniques, npad may be larger, for examples npad=4 means that the real input image was padded with zeroes to four time the original image size before Fourier transform was calculated)

• Dimensions y and z remain the same.

• The organization of the Fourier transform coefficients is somewhat complicated.

• 1D

  • n - even

• array element:

`   0     1     2      3       4      5    ...       n-2      n-1         n   n+1`

• Fourier coefficient:

`Re(0)  0.0  Re(1) Im(1)  Re(2) Im(2)            Re(n/2-1) Im(n/2-1)  Re(n/2) 0.0`

• n - odd
  • array element:

`   0     1     2      3       4      5    ...       n-2      n-1         n   n+1`

• Fourier coefficient:

`Re(0)  0.0  Re(1) Im(1)  Re(2) Im(2)            Re(n/2-1) Im(n/2-1)  Re(n/2) Im(n/2)`

• by `0.0` we denoted coefficients that are zero by the definition.

• 2D

  • x dimension n - even

  • y dimension m - even

  • array element:

`   0,0     1,0     2,0      3 ,0      4,0      5,0    ...       n-2,0      n-1,0         n,0   n+1,0`

`Re(0,0)  0.0     Re(1,0) Im(1,0)  Re(2,0) Im(2,0)   ...   Re(n/2-1,0) Im(n/2-1,0)  Re(n/2,0) 0.0` `Re(0,1) Im(0,1)  Re(1,1) Im(1,1)  Re(2,1) Im(2,1)   ...   Re(n/2-1,1) Im(n/2-1,1)  Re(n/2,1) Im(n/2,1)` `...` `Re(0,m/2) Im(0,m/2)  Re(1,m/2) Im(1,m/2)  Re(2,m/2) Im(2,m/2)   ...   Re(n/2-1,m/2) Im(n/2-1,m/2)  Re(n/2,m/2) Im(n/2,m/2)` `Re(0,-m/2+1) Im(0,-m/2+1)  Re(1,-m/2+1) Im(1,-m/2+1)  Re(2,-m/2+1) Im(2,-m/2+1)   ...   Re(n/2-1,-m/2+1) Im(n/2-1,-m/2+1)  Re(n/2,-m/2+1) Im(n/2,-m/2+1)` `...` `Re(0,-1) Im(0,-1)  Re(1,-1) Im(1,-1)  Re(2,-1) Im(2,-1)   ...   Re(n/2-1,-1) Im(n/2-1,-1)  Re(n/2,-1) Im(n/2,-1)`

• x dimension n - odd

• y dimension m - odd

`Re(0,0)  0.0     Re(1,0) Im(1,0)  Re(2,0) Im(2,0)   ...   Re(n/2-1,0) Im(n/2-1,0)  Re(n/2,0) Im(n/2,0)` `Re(0,1) Im(0,1)  Re(1,1) Im(1,1)  Re(2,1) Im(2,1)   ...   Re(n/2-1,1) Im(n/2-1,1)  Re(n/2,1) Im(n/2,1)` `...` `Re(0,m/2) Im(0,m/2)  Re(1,m/2) Im(1,m/2)  Re(2,m/2) Im(2,m/2)   ...   Re(n/2-1,m/2) Im(n/2-1,m/2)  Re(n/2,m/2) Im(n/2,m/2)` `Re(0,-m/2) Im(0,-m/2)  Re(1,-m/2) Im(1,-m/2)  Re(2,-m/2) Im(2,-m/2)   ...   Re(n/2-1,-m/2) Im(n/2-1,-m/2)  Re(n/2,-m/2) Im(n/2,-m/2)` `...` `Re(0,-1) Im(0,-1)  Re(1,-1) Im(1,-1)  Re(2,-1) Im(2,-1)   ...   Re(n/2-1,-1) Im(n/2-1,-1)  Re(n/2,-1) Im(n/2,-1)`

• Other combinations of odd/even dimensions can be easily deduced from the above.

• 3D - z dimension is organized the same way as y dimension

• For examples of C code that addresses Fourier elements by frequency see sparx/fourierfilter.cpp

Method

• The exact method of Fourier transform depends on which of the FFTs were linked during compliation of SPARX/EMAN2 system. Generally, it is recommended to use FFTW3. The system also contains native code, which is significantly slower than most of the libraries.

Reference

The references for particular algorithms depend on the FFT library used. The original FFT was reinvented by Cooley Tukey in 1965 after the original algorithm by Gauss. http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm

Author / Maintainer

Grant Tang/ Pawel A. Penczek.

Keywords

category 1

TRANSFORMS

category 2

FOURIER

Files

fundamentals.py

See also

fftip

Maturity

stable

works for most people, has been tested; test cases/examples available.

Bugs

None. It is perfect.