The mathematics behind Fourier Transform for Image Processing

I am following http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm . I understand the application of Fourier Transform behind Image Processing, but right now, I am curious about the mathematics behind it, and it is giving me a bit of a hard time.

For example:

In this formula, where do all these equations come from? Could somebody please elaborate the mathematics behind the scene in layman's term?

-
Did you check en.wikipedia.org/wiki/Discrete_Fourier_transform ? – PooyaM Aug 28 '12 at 9:08
Yes, I did, but my head spins even further. – Karl Aug 28 '12 at 9:24
An interesting explanation, to be sure... but I think I prefer to think about it in terms of orthogonal bases in inner product spaces. – Zhen Lin Aug 28 '12 at 9:40

I have given a similar explanation of Fourier series here and here.

The Fourier series of a function $f : \mathbb R / \mathbb Z \to \mathbb C$ is a sum $\sum_{k = -\infty}^\infty \hat{f}(e^{2 \pi i k x}) e^{2 \pi i k x}$. Here, $e^{2 \pi i k x} = \chi_k (x)$ denotes the $k$-th character of the topological group $\mathbb R / \mathbb Z$ and $\hat{f} : \widehat{\mathbb R / \mathbb Z} \to \mathbb C$ denotes the Fourier transform of $f$.

The setting is: You have a topological group $G$, then you consider a space of functions $G \to \mathbb C$ on it, say for example $L^2(G)$. This is a Hilbert space and comes with an inner product $\langle \cdot , \cdot \rangle$ which lets you define orthogonality of functions in the space, and characters in particular. Those characters form an orthonormal basis for your functions which means that you can approximate every function in $L^2(G)$ as $\| f - \sum_{k = -N}^N \hat{f}(\chi_k) \chi_k (x) \|_2 \xrightarrow{N \to \infty} 0$.

-
 I don't think it's possible to explain it using less definitions. – Matt N. Aug 28 '12 at 9:43 Note that you need $G$ to be Abelian and compact. But I don't want to perplex you with words that you don't know so ignore this for know and study the details later. – Matt N. Aug 28 '12 at 9:46 That's not much of a layman's term, is it? – Karl Aug 28 '12 at 12:24 @Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this. – Matt N. Aug 28 '12 at 12:33

In my opinion it is quite okay to understand Fourier transform as orthogonal basis matrices to evaluate the certain frequencies for a given image. However I have the following link which will be helpful for you to further understand:

http://sharp.bu.edu/~slehar/fourier/fourier.html#harmonics

Good luck.

-

I think the easiest way of understanding the math, Is understanding what it means. It's also easier to start in 1D and only then move on to higher dimensions.

To see what the sum you mentioned is, try inserting a wave with constant frequency. You see that the summation only gives a peak at the "correct" frequency. If you have a super-position of waves, the sum will give you a number of peaks each corresponding to a different part of the super-position.

Thus, the sum gives you the spectrum of frequencies in the wave or image.

-