The Discrete Fourier Transform (DFT) for a 1D signal of length N is defined as
where both f(x) and F(u) are periodic with the same period N.
Suppose the image, f(x,y) (2D signal), has dimensions 128x128
f(x,y) = 1 for x <= 64 and 0 elsewhere
The DFT generates a complex image, with real and imaginary parts. In practice we compute the DFT of real functions (images). Another way of looking at the DFT is to see its Magnitude and Phase spectrums. The magnitude spectrum is an even function, i.e. M(u) = M(-u). The phase spectrum is an odd function, i.e. - P(u) = P(-u ). Both spectrums are periodic with periods N and M, where N is the size of the image's width and M is the height. In general we operate on square images, thus, N = M. Also, in general the spectrums are displayed with the DC component, i.e. its (0,0) at the center.
The magnitude spectrum of our image f(x,y) is
Magnitude spectrum of f(x,y)
The image, f(x,y), has a constant value in any vertical line. It is expected to have magnitude spectrum values different than zero only in the middle line, i.e. F(0,v) != 0.
Extracting a 1D profile of the DFT, horizontal line 64, and plotting it yields
1D profile of magnitude spectrum
1D profile of phase spectrum
Is there a connection between the 1D DFT and a N-dimensional DFT? Analytically, we can compute the DFT of the 1D signal of length 128 with the equation
Printing the pixel values of the DFT we get a list of the real and imaginary numbers
... real imaginary 61 ( 2.385244779e-17, 0.1059114784) 62 ( 0.0078125, -0) 63 ( 1.880985883e-17, 0.3182459772) 64 ( 0.5078125, 0) 65 ( 1.301042607e-17, -0.3182459772) 66 ( 0.0078125, -0) 67 ( 1.908195824e-17, -0.1059114784) 68 ( 0.0078125, -0) ...Recall, position 64 gives F(0) = 65/128, F(1)= 0-j0.31 = conjugate of F(-1), which are properties of the Fourier transform.
... Magnitude Phase 61 0.1059114784 1.570796371 62 0.0078125 -0 63 0.3182459772 1.570796371 64 0.5078125 0 65 0.3182459772 -1.570796371 66 0.0078125 -0 67 0.1059114784 -1.570796371 68 0.0078125 -0 ...
It is possible to show that the 1D inverse DFT of a real function can be determined from the following formula
This equation states that we can reconstruct the original signal as a sum of primitive cosine functions. Selecting only the two strongest cosines yields
f(x) ~= 0.507 + 0.636 cos(period 128, phase:-90) + 0.211 cos( period:128/3, phase:-90) + ...
We can extrapolate the above equation to images and visualize the operation taking place.
0.507+0.636 +0.211 =
The horizontal profile of the reconstructed image is
If we use all cosine waveforms from F(1) to F(63) in the reconstruction process we get back the original image. Therefore, the spectrum gives a recipe on how to combine all possible cosine primitives with period 128 (min) to 2 (max) in order to obtain the original image.
From each point of the magnitude spectrum and the correspondent phase spectrum, we can derive the cosine parameters below
Given the following spectrum
We note that there are only two points which are symmetrical. Recall that the center is the DC value. If we print the contents of the DFT
# Size: Width = 128, Height = 128, Depth = 1, Time = 1, Elements = 1 coord real imaginary ... 44 49 ( 1.416520691e-19, 0.5) ... 84 79 (-2.228730213e-18, -0.5) ...
Converting those points to Magnitude and Phase and relating to DC [(0,0)] which is at the center of the image, i.e. point (64,64) we get
F(20,15) is the complex conjugate of F(-20,-15), and
the Magnitude and Phase of point F(20,15) is = 0.5 ; -1.57 (-90 degrees)
Clearly, we have only one cosine function with parameters shown below
The DFT then gives us which cosine components are necessary to reconstruct the image. It provides all the different frequency components. Points near the center of the magnitude spectrum refer to smooth cosine waveforms with a long period, and points far from the center refer to high frequency components.