DFT: A Pulse Example

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)  
...

...  
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  
...

• Building a visual program (workspace) in cantata
• Execute the visual program fourier-square.wk

Interpreting the DFT

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

1. Amplitude: it is twice the magnitude value
2. Period: given by the distance from the center: N/distance
3. Phase: given by the phase value
4. Direction: given by the angle of the line connecting the point to the center of the spectrum

Example

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

1. Amplitude: 1.0
2. Phase: -90 (so it is a sinusoid)
3. Period: 128/25 = 5 pixels
4. Direction: arctan(15/20) = -36.8 degrees

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.