5. Fourier Transform

Every 1D function can be decomposed into a set of sines and cosines.

$$ f(x) =a_0\sin 0x + a_1\sin 1x + a_2\sin 2x + \dots + b_0\cos 0x + b_1\cos 1x + b_2 \cos 2x + \dots $$

If we include complex waves, things are a lot easier to understand.

Recall that from Euler's equation,

$$ e^{ i \theta} = i\sin \theta + \cos \theta. $$

every function can be written as a sum of such functions:

$$ f(x) = a_0e^{i0x} + a_1e^{i1x} + a_2^{i2x} + a_3^{i3x} + \dots $$

The Fourier coefficients of $f$ are ordered in increasing frequency.

Images, which are functions of two variables, can also be decomposed in to periodic functions

$$ f(x,y) = \sum_k \sum_l a_{kl}e^{1(kx + ly)}. $$

Nyquist sampling theorem

A rule of thumb that comes from signal processing is the Nyquist sampling theorem. To avoid aliasing, the frequency of sampling should be greater than twice the greatest frequency of the signal.

The intuition behind this is to sample a sine curve at least twice per cycle to get both peak and trough.

The effect of blurring on frequency

Blurring kills high frequency components by making pixels more like their images. It turns out that blurring with a Gaussian is the best way to remove high frequencies.