1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
DFI
===
This all is based on Fourier slice theorem: 1D FFT of projection taken at
some angle equals the central radial slice at the same angle of the 2D FFT
of the original object.
The center of rotation is considered to be in the center of axis. Then we
padding both ends with zeroes (the background color have to be zero). And
exchanging left and right halves.
- For DFT, we assume that signal is cyclic and we sample values from 0
to N. But we actually have them from -N/2 to N/2 (because the center of
rotation is in the center of axis). Therefore, we need to move first half
of array after second half.
The main problem is interpolation in Fourier space.
FFT properties
--------------
- Operation on real data gives Hermetian (self-adjoint) matrix in Fourier space.
A Hermitian matrix (or self-adjoint matrix) is a square matrix with complex
entries that is equal to its own conjugate transpose (A*). That is, the element
in the i-th row and j-th column is equal to the complex conjugate of the element
in the j-th row and i-th column (i.e. with sign of imaginary part changed).
- cuFFT have implemented Cooley-Tukey algorith for radixes 2,3,5,7. The best
performance still with large powers of two, but we should check balance
between large padding and usage of sub-optimal radixes. Accroding to cuFFT
documentation, the cuFFT performance is constrained by following restrictions
in the order of decreasing importance:
* Restrict the size along each dimension to use fewer distinct prime factors.
* Radix2 part should be multiple of 256
* Restrict the x dimension of single-precision transforms to be strictly a
power of two either between 2 and 8192 for Fermi-class GPUs or between 2
and 2048 for earlier architectures.
* Use Native compatibility mode for in-place complex-to-real or
real-to-complex transforms.
- 2D FFT is series of independent 1D FFT transforms on rows and columns
|