# Discrete Fourier Transform for beginners

I want to make image processing programs which talk about homomorphic filter. But when I read some articles, I can't get it. Maybe can anyone help it. I very need this. Sorry about my english.

1. I change spatial domain image to frequency domain with discrete Fourier transform. Right? Formula Forward DFT: • What are M and N? Width and height of image?
• and then, the output from forward formula, real and imaginary part? like "a+bj"?
2. When I try to inverse the Fourier transform with the formula: • F(u,v) is the result from forward dft? but it has 2 part real and imaginary? if, F(u,v) = (a+bj) and result euler theorem e^... = cos(x)+j sin(x).

So, F(u,v).e^... = (a+bj).( cos(x)+j sin(x) ) = a.cos(x) + j(a.sin(x) + b.cos(x)) - b.sin(x)

my equation correct ?

• the result of inverse real and imaginary part again? because have "j".
• how can i get my original image? take the real part, just make my image get blurred

1. Yes, m and n are the dimensions of the image. F(u,v) will be a complex-valued (real and imaginary) function of u and v.

2. Yes your equation is correct and F(u,v) is the result of the forward DFT. It is correct that F(u,v) has real and imaginary parts, and the multiplication of that into the complex sinusoid will result in a quantity that also has real and imaginary parts.

So how do you get back a real valued image if each of the numbers in the sum over u and v is complex? The key is that F(u,v) has certain symmetry properties due to f(i,k) being real valued. This symmetry results in the sum over u and v adding up to a real number.

The same thing happens with the one-dimensional DFT. In that case a real valued signal f(t) produces a conjugate symmetric DFT F(u) (F(u) = F*(N-u)). The symmetry is a bit more complicated in 2D, but that is why this works out.

I often see students manipulate the DFT coefficients and accidentally destroy the conjugate symmetry. Then when they take the inverse DFT the result is complex valued when it should have been real valued.

Note that numerical errors will sometimes produce an inverse DFT that has a very small imaginary part, even though the symmetry is correctly preserved. In these cases it is best to just take the real part as your result.

Yes, a discrete Fourier transform (DFT) is often used to transform a spatial domain image to a frequency domain image. Usually this is implemented using a 1-dimensional fast Fourier transform FFT independently applied along each row of the original image to produce an intermediate image, then a 1-dimensional FFT independently applied along each column of the intermediate image to produce the frequency domain image. The FFT and the inverse FFT give exactly the same results as the equations you wrote, but they execute much faster.

Yes, complex multiplication works just as you stated,

F(u,v) . e^(jx) = (a+bj) . (cos x + j sin x) = (a cos x - b sin x) + j( a sin x + b cos x)

Traditionally we re-arrange the frequency domain image so the zero-frequency bin of the frequency domain image is in the middle of that image ("centered format").

Sometimes a person takes a Fourier transform of some image an immediately throws away half the data, taking only the real part or taking only the absolute value. That throws away half the information -- any later attempts to recover the image by taking the inverse Fourier transform of the real part (or the absolute value) only give a big blur.

As Barry Van Veen pointed out, if you preserve both the real and imaginary parts, you find that every real valued image produces a frequency domain image with a certain symmetry in frequency space. (Also, you will find that even though you may start with a black-and-white image with values from 0 to 255, the frequency domain image often has both positive and negative real values, positive and negative imaginary values, and values with amplitudes of many thousand). And as he also pointed out, if you preserve that symmetry when you do your filtering, then when you do the inverse transform, the result should be very close to real valued again -- it's often OK to take just the real part as your result.

Yes, F(u,v) is the result from the forward DFT. Yes, for each integer u and each integer v, F(u,v) is a 2-part number with a real and imaginary part, F(u,v) = (a+bj).

You might find the following links relevant:

As you probably already know, most programmers that need to sort something use a standard off-the-shelf sorting library rather than carefully crafting yet another sort() routine from scratch. Also, most programmers that need to do a DFT use a standard off-the-shelf FFT library.