Name

fftip - calculate forward or inverse in-place Fourier transform of an 1-2-3D image

Usage

fftip(image)

Input

image

input image is replaced, depending on its format, by its forward or inverse Fourier transform, if real, the forward Fourier transform is calculated, if Fourier, the inverse Fourier transform is calculated.

Description

• If input image is real and it was not extended for Fourier transform, 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.

• If input image is Fourier, the padding of the x dimension n will not be removed. This feature is handy if a series of Fourier/real operations is intended and it significantly speeds up the processing. However, as of now, most real space commands will not work properly on extended images. In order to remove the extension, use function image.postift_depad_corner_inplace().

• 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.