NFFT Logo 3.0 API Reference
Main Page | Modules | Data Structures | Directories | File List | Data Fields | Globals

polar_fft_test
[Polar FFT]


Functions

int polar_grid (int T, int R, double *x, double *w)
 Generates the points $x_{t,j}$ with weights $w_{t,j}$ for the polar grid with $T$ angles and $R$ offsets.
int polar_dft (fftw_complex *f_hat, int NN, fftw_complex *f, int T, int R, int m)
 discrete polar FFT
int polar_fft (fftw_complex *f_hat, int NN, fftw_complex *f, int T, int R, int m)
 NFFT-based polar FFT.
int inverse_polar_fft (fftw_complex *f, int T, int R, fftw_complex *f_hat, int NN, int max_i, int m)
 inverse NFFT-based polar FFT
int main (int argc, char **argv)
 test program for various parameters

Function Documentation

int polar_grid (  int  T,
int  R,
double *  x,
double *  w
) 
 

Generates the points $x_{t,j}$ with weights $w_{t,j}$ for the polar grid with $T$ angles and $R$ offsets.

The nodes of the polar grid lie on concentric circles around the origin. They are given for $(j,t)^{\top}\in I_R\times I_T$ by a signed radius $r_j := \frac{j}{R} \in [-\frac{1}{2},\frac{1}{2})$ and an angle $\theta_t := \frac{\pi t}{T} \in [-\frac{\pi}{2},\frac{\pi}{2})$ as

\[ x_{t,j} := r_j\left(\cos\theta_t, \sin\theta_t\right)^{\top}\,. \]

The total number of nodes is $M=TR$ , whereas the origin is included multiple times.

Weights are introduced to compensate for local sampling density variations. For every point in the sampling set, we associate a small surrounding area. In case of the polar grid, we choose small ring segments. The area of such a ring segment around $x_{t,j}$ ($j \ne 0$ ) is

\[ w_{t,j} = \frac{\pi}{2TR^2}\left(\left(|j|+\frac{1}{2}\right)^2- \left(|j|-\frac{1}{2}\right)^2\right) = \frac{\pi |j| }{TR^2}\, . \]

The area of the small circle of radius $\frac{1}{2R}$ around the origin is $\frac{\pi}{4R^2}$ . Divided by the multiplicity of the origin in the sampling set, we get $w_{t,0} := \frac{\pi}{4TR^2}$ . Thus, the sum of all weights is $\frac{\pi}{4}(1+\frac{1}{R^2})$ and we divide by this value for normalization.

return the number of knots

Definition at line 51 of file polar_fft_test.c.

References PI.

Referenced by inverse_polar_fft(), main(), polar_dft(), and polar_fft().

int polar_dft (  fftw_complex *  f_hat,
int  NN,
fftw_complex *  f,
int  T,
int  R,
int  m
) 
 

discrete polar FFT

< index for nodes and frequencies

< plan for the nfft-2D

< knots and associated weights

< number of knots

< oversampling factor sigma=2

< oversampling factor sigma=2

init two dimensional NFFT plan

init nodes from polar grid

init Fourier coefficients from given image

NDFT-2D

copy result

finalise the plans and free the variables

Definition at line 73 of file polar_fft_test.c.

References nfft_plan::f, nfft_plan::f_hat, FFT_OUT_OF_PLACE, FFTW_INIT, nfft_plan::M_total, MALLOC_F, MALLOC_F_HAT, MALLOC_X, nfft_plan::N_total, ndft_trafo(), nfft_finalize(), nfft_init_guru(), polar_grid(), PRE_PHI_HUT, PRE_PSI, and nfft_plan::x.

Referenced by main().

int polar_fft (  fftw_complex *  f_hat,
int  NN,
fftw_complex *  f,
int  T,
int  R,
int  m
) 
 

NFFT-based polar FFT.

< index for nodes and freqencies

< plan for the nfft-2D

< knots and associated weights

< number of knots

< oversampling factor sigma=2

< oversampling factor sigma=2

init two dimensional NFFT plan

init nodes from polar grid

precompute psi, the entries of the matrix B

init Fourier coefficients from given image

NFFT-2D

copy result

finalise the plans and free the variables

Definition at line 127 of file polar_fft_test.c.

References nfft_plan::f, nfft_plan::f_hat, FFT_OUT_OF_PLACE, FFTW_INIT, nfft_plan::M_total, MALLOC_F, MALLOC_F_HAT, MALLOC_X, nfft_plan::N_total, nfft_finalize(), nfft_plan::nfft_flags, nfft_init_guru(), nfft_precompute_full_psi(), nfft_precompute_lin_psi(), nfft_precompute_psi(), nfft_trafo(), polar_grid(), PRE_FULL_PSI, PRE_LIN_PSI, PRE_PHI_HUT, PRE_PSI, and nfft_plan::x.

Referenced by main().

int inverse_polar_fft (  fftw_complex *  f,
int  T,
int  R,
fftw_complex *  f_hat,
int  NN,
int  max_i,
int  m
) 
 

inverse NFFT-based polar FFT

< index for nodes and freqencies

< plan for the nfft-2D

< plan for the inverse nfft

< knots and associated weights

< index for iterations

< number of knots

< oversampling factor sigma=2

< oversampling factor sigma=2

init two dimensional NFFT plan

init two dimensional infft plan

init nodes, given samples and weights

precompute psi, the entries of the matrix B

initialise damping factors

initialise some guess f_hat_0

solve the system

copy result

finalise the plans and free the variables

Definition at line 191 of file polar_fft_test.c.

References CGNR, infft_plan::f_hat_iter, FFT_OUT_OF_PLACE, FFTW_INIT, infft_plan::flags, infft_before_loop(), infft_finalize(), infft_init_advanced(), infft_loop_one_step(), nfft_plan::M_total, MALLOC_F, MALLOC_F_HAT, MALLOC_X, infft_plan::mv, nfft_plan::N, nfft_plan::N_total, nfft_finalize(), nfft_plan::nfft_flags, nfft_init_guru(), nfft_precompute_full_psi(), nfft_precompute_lin_psi(), nfft_precompute_psi(), infft_plan::p_hat_iter, polar_grid(), PRE_FULL_PSI, PRE_LIN_PSI, PRE_PHI_HUT, PRE_PSI, PRECOMPUTE_DAMP, PRECOMPUTE_WEIGHT, infft_plan::w, infft_plan::w_hat, nfft_plan::x, and infft_plan::y.

Referenced by main().

int main (  int  argc,
char **  argv
) 
 

test program for various parameters

< mpolar FFT size NxN

< number of directions/offsets

< number of knots of mpolar grid

< knots and associated weights

< number of iterations

generate knots of mpolar grid

load data

direct polar FFT

Test of the polar FFT with different m

fast polar FFT

compute error of fast polar FFT

Test of the inverse polar FFT for different m in dependece of the iteration number

inverse polar FFT

compute maximum relative error

free the variables

Definition at line 286 of file polar_fft_test.c.

References inverse_polar_fft(), nfft_error_l_infty_complex(), polar_dft(), polar_fft(), and polar_grid().

Generated on 1 Nov 2006 by Doxygen 1.4.4