# 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 ? –  Zeta.Investigator 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

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 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. –  Rudy the Reindeer Aug 28 '12 at 9:43
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. –  Rudy the Reindeer Aug 28 '12 at 12:33
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is. –  nbubis Aug 3 '13 at 5:20
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here. –  Ron Gordon Aug 3 '13 at 7:23

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.

-

In layman's terms:

This comes from a paper Fourier wrote on modelling heat diffusion. The idea being that one could approximate any continuous function by adding up lots of sin an cos functions. The more terms you can use, the more accurate you can make the result.

ie:

$f(x) = a_0\cos\frac{\pi y}{2}+a_1\cos 3\frac{\pi y}{2}+a_2\cos5\frac{\pi y}{2}+\cdots + b_0\sin\frac{\pi y}{2}+b_1\sin 3\frac{\pi y}{2}+b_2\sin5\frac{\pi y}{2}+\cdots$

In order to find the coefficients (the a's) to do this, the following trick was used:

$a_n = \frac{1}{\pi}\int_{-\pi}^\pi f(x) \cos(nx)\, dx$

The same would be similarly done for sine functions.

$b_n = \frac{1}{\pi}\int_{-\pi}^\pi f(x) \sin(nx)\, dx$

These are known as the Fourier sine and cosine transforms.

Euler's formula $e^{i\theta} = cos(\theta) + i sin(\theta)$ shows an relationship between exponential functions and cos and sin. This is why you seen an exponential (e) in the Fourier transform instead of cos and sin. This is merely the Fourier cosine and Fourier Sine transforms being combined into one transform.

This is where $\hat{f}(\xi) = \int_{-\infty}^{\infty} f(x)\ e^{- 2\pi i x \xi}\,dx$ comes from.

Now in image processing we are typically working with 2 dimensional images. So the Fourier transform has been done twice on both dimensions.

$F(u,v)=\int \int_{-\infty}^{\infty} f(x,y) e^{-j2\pi(ux+vy)} dx dy$

Since images actually come in discrete pixels rather than continuous (like analogue vs digital) functions. (Images are "digital"). This function has been discretised.

Which is why you see the summation instead of the integrals.

-

The discrete Fourier transform (which is a function from $\mathbb C^N$ to $\mathbb C^N$) simply changes basis, to a special basis known as the discrete Fourier basis.

And what's so special about this basis? It's a basis of eigenvectors for the shift operator $S$, which maps $\begin{bmatrix} x_0 & x_1 & x_2 &\ldots & x_{N-1} \end{bmatrix}^T$ to $\begin{bmatrix} x_{N-1} & x_0 & x_1& \ldots & x_{N-2} \end{bmatrix}^T$.

Each basis vector is constructed by taking an $N$th root of unity $\omega$ and forming the vector $v = \begin{bmatrix} 1 & \omega & \omega^2 & \ldots & \omega^{N-1} \end{bmatrix}^T$. It's easy to check that $v$ is an eigenvector of $S$: \begin{align*} S(v) &= \begin{bmatrix} \omega^{N-1} & 1 & \omega & \ldots & \omega^{N-2} \end{bmatrix}^T \\ &= \omega^{-1} v. \end{align*} We have one discrete Fourier basis vector for each $N$th root of unity.

Because $S$ is unitary (it clearly preserves norms), we have that $S$ is normal, so there is an orthonormal basis of eigenvectors for $S$. This explains why the discrete Fourier basis (once normalized) is orthonormal and why the discrete Fourier transform preserves norms.

Any convolution operator on $\mathbb C^N$ can be expressed as a linear combination of powers of $S$. This explains why the discrete Fourier basis diagonalizes any convolution operator on $\mathbb C^N$.

The 2D discrete Fourier transform is analogous. We have two shift operators on $\mathbb C^{M \times N}$, $S_1$ (which shifts each row to the right) and $S_2$ (which shifts each column down). $S_1$ and $S_2$ are normal operators and they commute, so there is an orthonormal basis of eigenvectors that simultaneously diagonalizes $S_1$ and $S_2$. This gives us the 2D discrete Fourier basis.

-