The theory and the praxis
The Discrete Fourier transform is defined as:
It is derived from the continuous version of the Fourier series development:
It is not easy to see from the formulas what they mean.
The story of sines
Where do sines come from? We did saw the circle drawing the sine, but... Most of the math before the 20th century was based or derived from or for physics.
If you bump an object and observe his response, it is very likely that the response or shaking will be very sine like. Because the sine has been observed in nature it is why the sine is called a natural function and the frequency of the sine is called the natural frequency. Looking from the practical point of view, it is very nice that man was able to find such a good mathematical model for that motion, namely the sine.
But most objects do not respond with only one sine frequency. This is where the Fourier transform can be used. Fourier offered a method to detect which frequencies of sines were present in the actual response of the object. His method can extract their frequency, phase and amplitude.
What about if the system does not have a sine function as his natural function? There was a lot of heat burned on that subject in the previous century. The conclusion was the following: It may be so, but with a sum of a sufficiently large number of different sines (the Fourier series) it is possible to approximate any desirable function.
Finding the shapes
The Fourier found a way to model a complicated signal with a sum of sines that have different frequencies, amplitudes and phase. Let us try the same. In computer vision there is a widely accepted approach for finding the shapes on the picture, called Hough transform. The idea is simple. If we search for a straight line, that line has a mathematical form of: y = kx + n. We have two parameters: k and n. Now we form pairs of all possible values of k and n, draw the line and count the number of pixels that support that hypothesis. We save the intermediate results and at the end we apply a threshold to those results keeping only those pairs of parameters k and n that had a sufficiently large support.
If we can search for straight lines, why couldn't we search for sines? The sines have three parameters. The function is
The parameters are: A, f and phi . This approach works well, if we have only one sine that has to be found. If we have to find a function that is actually a sum of sines, the approach has to be modified.
One fundament of Linear algebra is orthogonality. Example:Series 1: 1, 0, 0
Series 2: 0, 1, 0If we multiply those series, value by value and sum the results: 1*0 + 0*1 +0*0 = 0. If the result of a dot product is zero, then the two series are orthogonal. And the operation is called the scalar or dot product. And now the trick number 1: