# Discrete Fourier transform

As long as images in computers are discrete, there is no reason to compute a continuous Fourier transform. Therefore, we will implement a discrete Fourier transform (DFT). DFT is sampled Fourier transform, and so it does not contain all frequencies in the image, but only a set of sampled frequencies. We will prove that the set of the sampled frequencies is enough to fully describe special domain of the image in this exercise.

For image of size N,M, DFT is given:

To compute the basis it is required to use Euler formula, and the output given contains imaginary and real part. The spectrum amplitude is then the amplitude given by the size of the vector of complex number, and phase can be computed as arctan of the imaginary and real part.

Application notes:

• Since result contains real and imaginary part, feel free to use 2 separate images (or arrays) to store the data.
• Be careful about the data types you are using.

Same process can then be applied for inverse discrete Fourier transform  (IDFT):

Don’t forget that the elements in F matrix are complex, and so is the basis. This will result into the multiplication of two complex numbers. For application just take the real part of the multiplication.

Magnitude of DFT

LV code for FFT using NI-Vision

Data Value
Source https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
Code