Return to Computer Vision Notebooks

Bi-dimensional Discrete Fourier Transform



Overview and implementation of bi-dimensional discrete space Fourier transform.

$O(n²)$ >> The running time will be quite long

1. Discrete space Fourier transform


Transforming from spatial to frequency domain using Discrete Fourier Transform, defined by:

$$ \large X(\omega_1,\omega_2)=\sum_{n_1=0}^{N_1-1}\sum_{n_2=0}^{N_2-1}x(n_1,n_2)e^{-j2\pi\left(\frac{\omega_1 n_1}{N_1}+\frac{\omega_2 n_2}{N_2}\right)} $$

2. Inverse discrete space Fourier transform


Transforming from frequency to spatial domain using Inverse Discrete Fourier Transform, defined by:

$$ \large x(n_1,n_2)=\frac{1}{N_1 N_2}\sum_{k_1=0}^{N_1-1}\sum_{k_2=0}^{N_2-1}X(k_1,k_2)e^{j2\pi\left(\frac{n_1 k_1}{N_1}+\frac{n_2 k_2}{N_2}\right)} $$

3. Spatial Frequency Filtering


Gaussian filtering, defined by the multiplication in frequency domain between the filter $H$ and the spectrum $X$.

$$ \large G(u,v)=H(u,v)X(u,v) $$

where:

$$ \large H(u,v)=\frac{1}{2\pi \sigma^2}e^{-\frac{u^2+v^2}{2\sigma^2}} $$

Iterative reconstruction visualization


Demonstration of the iterative reconstruction of a multi-channel image from its fourier spectrum.