The feared Discrete Fourier Transform (aka:DFT)

Why we should care about the Discrete Fourier Transform?

I will start talking about the applications in which DFT is used, as Gonzalez says in his image processing book, besides being the cornerstone in linear filtering, it offers considerable flexibility in the design and implementation of filtering solutions in areas as image compression, image restoration, image enhancement, and many other applications of practical interest. Now, we are ready to cheerfully start studying the DFT in deep. (Yeah, right)  

By definition, the DFT is represented as follows:

Mmmm, and as you easily can see from the equation above, :P, we have:

• X(k) = Is the Discrete Fourier Transform of our signal, is its representation in the frequency domain (what?)

• x(n) = Is our signal in the spatial domain, ie. an audio signal

So, if we see the equation, each sample X(k) will be the sum of the multiplication of all the input signal values by the frequency components of the signal.  Yes, is that e raised to two pi divided by N times minus i times k times n.

Without looking for more troubles with efficiency measurement algorithms, we can see (not so clearly) that while we have more samples in our signal, the amount of multiplications and additions is raised exponentially, that inconvenience was solved with the FFT, but that is something that I will not touch so far.

Here I stop with this little explanation of the DFT, but I will continue with an example of it coded in MATLAB in a later post.

(So far I can’t get to understand this)