Recently I have been reading up on frequency domain image processing. I am still just beginning to understand how it works. Over the last few weeks I have been trying to understand the ** Fourier Transform **. Although the gist of **Fourier Series** is easy to understand from its formula, that of the **Fourier Transform** isn’t (to me at least). This blog post describes the Fourier Transform as I understood it, along with some helpful diagrams. I am using NumPy and matplotlib for plotting. As a reference for all the equations mentioned in this post, I am using Digital Image Processing (3rd Edition).

## The Fourier Series

I haven’t done any digging into its theory, but the formula for Fourier Series is pretty straight forward. Given has a period of

where

for

To simplify this, we can replace . now becomes.

Using Euler’s Formula

We can say that, is now exactly equal to an infinite sum of certain sines and cosines. The Wikipedia Page has some pretty nice visualizations of the concept.

## The Discrete Fourier Transform

This is what took me a while to understand. The discrete fourier transform, is derived from the Fourier Transform. Given a discrete function whose samples have been collected, we have.

for

As you can see, the function of is **transformed** into the function of .

We can get back by the inverse Fourier Transform

for

Although the relationship of and is mathematically proven, the underlying meaning was not immediately apparent to me. What puzzled me was, why is computed at all, and how can it tell us anything about . The way I looked at it to understand it better is as follows.

Let

Using Euler’s formula we have

From the above equation, it is clear why the Fourier Transform is important. The function , has given us coefficients to express as a sum of sines and cosines. I will try to demonstrate this with some code. I wrote a small helper function to help me input curves. The following function taken an image of a curve drawn in black on white and saves it into a `.npy`

file. You will need the scikit-image library to use this.

from skimage import io, color, util from matplotlib import pyplot as plt pylab.rcParams['figure.figsize'] = (8.0, 8.0) def img2curve(imgfile, arrayfile): """ Converts an image of a curve into numpy array and saves it""" img = io.imread(imgfile) img = color.rgb2gray(img) img = util.img_as_ubyte(img) array = np.zeros((img.shape[1], )) for r in range(img.shape[0]): for c in range(img.shape[1]): if img[r, c] < 128: array[c] = img.shape[0] - r np.save(arrayfile, array) def show_curve(array): """ Plots real and imaginary parts of an array """ ax = plt.subplot(111) ax.set_xlim(0, len(array)) ax.set_ylim(-10, len(array)) plt.plot(np.real(array), color='blue') plt.plot(np.imag(array), color='red')

### Original Image

img = io.imread("curve.png") io.imshow(img)

### Derived Curve

img2curve("curve.png", "curve.npy") curve = np.load("curve.npy") show_curve(curve)

If you’d like to, you can download the original image and the curve.npy file.

### Computing the DFT

We will compute the discrete fourier transform using NumPy’s `np.fft.fft`

method and observe the first 5 terms.

curve_fft = np.fft.fft(curve) print curve_fft[:5]

`curve_fft`

is our function as described above. Applying the inverse transform to `curve_fft`

should give us back `curve`

exactly. But let’s see what happens by considering an element in at a time. First we take only and apply the inverse transform by using `np.fft.ifft`

.

### Contribution of F(0)

tmp = curve_fft.copy() tmp[1:] = 0 array = np.fft.ifft(tmp) show_curve(array)

As you can see, it is a real constant shown in blue.

### Contribution of F(1)

tmp = curve_fft.copy() tmp[2:] = 0 tmp[0:1] = 0 array = np.fft.ifft(tmp) show_curve(array)

### Contribution of F(2)

tmp = curve_fft.copy() tmp[3:] = 0 tmp[0:2] = 0 array = np.fft.ifft(tmp) show_curve(array)

### Contribution of F(0), F(1) and F(2)

tmp = curve_fft.copy() tmp[3:] = 0 array = np.fft.ifft(tmp) show_curve(array)

As you can see the resultant curve is trying to match the original curve. The imaginary part in red, will eventually get zeroed out when all the terms of are considered.

## Fourier Transform in action

The code snippet below generates successive images of contribution of each term in . In `nth`

still, the blue and red lines show the real and imaginary part of the curve so far, and the dotted lines show the contribution of .

import numpy as np from matplotlib import pyplot as plt curve = np.load("curve.npy") curve_fft = np.fft.fft(curve) result = np.zeros_like(curve, dtype=np.complex) for i in range(curve_fft.shape[0]): tmp = np.zeros_like(curve, dtype=np.complex) tmp[i] = curve_fft[i] tmp_curve = np.fft.ifft(tmp) result += tmp_curve fig = plt.figure() ax = plt.subplot(111) ax.set_xlim(0, len(curve)) ax.set_ylim(-10, len(curve)) plt.plot(np.real(result), color='blue') plt.plot(np.imag(result), color='red') plt.title("Adding F(%d)" % i) plt.plot(np.real(tmp_curve), 'r--', color='blue') plt.plot(np.imag(tmp_curve), 'r--', color='red') fig.savefig('out/' + str(i) + ".png")

I ran the command

avconv -f image2 -r 1 -i %d.png -r 20 fft.mp4

to generate the final video.

As I understand DFT more, I’ll keep posting. Till then, thanks for reading.