A thing or two about the Fourier Transform

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 f has a period of T

f(t) = \sum\limits_{n=-\infty}^\infty c_{n} e^{i\frac{2 \pi n}{T}}

where

c_n = \frac{1}{T} \int\limits_{\frac{-T}{2}}^{\frac{T}{2}} f(t)e^{-i\frac{2 \pi n}{T}}

for
n = 0,\pm 1, \pm2, .....

To simplify this, we can replace \omega=\frac{2\pi}{T} . f now becomes.

f(t) = \sum\limits_{n=-\infty}^\infty  c_n e^{i \omega n}

Using Euler’s Formula

f(t) = \sum\limits_{n=-\infty}^\infty  c_n (cos(n \omega t) + i. sin(n \omega t))

We can say that, f 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 f whose M samples have been collected, we have.

F(u) = \sum\limits_{x=0}^{M-1} f(x)e^{-i\frac{2\pi u x}{M}}

for

u = 0, 1, 2, ..., M -1

As you can see, the function f of x is transformed into the function F of u .
We can get f back by the inverse Fourier Transform

f(x) = \frac{1}{M} \sum\limits_{u=0}^{M-1} F(u)e^{i\frac{2\pi u x}{M}}
for
x = 0, 1, 2, ... , M -1

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

Let
\omega = \frac{2\pi}{M}

f(x) = \frac{1}{M} \sum\limits_{u=0}^{M-1} F(u)e^{i\omega u x}

Using Euler’s formula we have

f(x) = \frac{1}{M}[{F(0).(cos(0) + i.sin(0)) + F(1).(cos(1\omega x) + i.sin(1\omega x)) + F(2).(cos(2\omega x) + i.sin(2\omega x)) + ...} ]

From the above equation, it is clear why the Fourier Transform is important. The function F , has given us coefficients to express f 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)

image

Derived Curve

img2curve("curve.png", "curve.npy")
curve = np.load("curve.npy")
show_curve(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 F 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 F at a time. First we take only F(0) and apply the inverse transform by using np.fft.ifft.

Contribution of F(0)

t_0(x) = \frac{1}{M}[F(0).(cos(0) + i.sin(0))]

tmp = curve_fft.copy()
tmp[1:] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F0

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

Contribution of F(1)

t_1(x) = \frac{1}{M}[F(1).(cos(1\omega x) + i.sin(1\omega x))]

tmp = curve_fft.copy()
tmp[2:] = 0
tmp[0:1] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F1

Contribution of F(2)

t_2(x) = \frac{1}{M}[F(2).(cos(2\omega x) + i.sin(2\omega x))]

tmp = curve_fft.copy()
tmp[3:] = 0
tmp[0:2] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F2

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

t_0(x) + t_1(x) + t_2(x)

tmp = curve_fft.copy()
tmp[3:] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F123

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 F are considered.

Fourier Transform in action

The code snippet below generates successive images of contribution of each term in F . 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 F(n) .

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.

Ultra Quick GUIs with wxFormBuilder/Python

I’ve been a fan of wxFormBuilder for a a long time. It allows programmers like me to develop highly polished GUIs for Real World Applications or quick, temporary GUIs just to get the job done. To follow the below steps won’t take more than 15 minutes. The Goal is to build a usable calculator using wxPython and wxFoemBuilder

Things you’ll need

Python
wxPython
wxFormBuilder

Any versions will do as long as they are inter compatible. I used Python 2.7.3 (32-bit), wxPython 2.8.12.1 (msw-unicode) and wxFormBuilder 3.2.3-beta (unicode)

Install all the above in thee order mentioned and we should be good to go.

Enter wxFormBuilder

Start wxFormBuilder and you’ll be greeted with New Project with a blank grey area in the center. Go to the Object Properties Window on the right and change name,file and set code generation to Python

1

From the Forms tab Choose Frame
3

Choose The Recently Added Frame from the object Tree and change name to MainFrame
4

Add a wxBoxSizer from Layout tab , make sure that orient is wxVERTICAL from the Object Properties

5

From the Common tab add TexCtrl and 2 Buttons.

6

Select each of these 3 elements and enable Expand and Stretch

7

Select the TextCtrl and change the name to text

8

Choose any button and rename it to solveButton and change the label to Solve

9

In the Events Tab change the OnButtonClick value to solveFunc. This will be the function called when the button is clicked.
10

Similarly rename the other Button to clearButton and change OnButtonCick to clearFunc

Your window should be looking similar to this by now.

11

Save The Project and hit F8 to generate code. You should end up with a file called gui.py in the directory you saved in. This file holds the code for generating the graphics.

Almost There

The final bit is writing the python code. Create a new python file in the same directory, and copy this code into it

Read the comments for explanation.

#importing wx files
import wx

#import the newly created GUI file
import gui

#importing * : to enable writing sin(13) instead of math.sin(13)
from math import *

#inherit from the MainFrame created in wxFowmBuilder and create CalcFrame
class CalcFrame(gui.MainFrame):
    #constructor
    def __init__(self,parent):
        #initialize parent class
        gui.MainFrame.__init__(self,parent)

    #what to when 'Solve' is clicked
    #wx calls this function with and 'event' object
    def solveFunc(self,event):
        try:
            #evaluate the string in 'text' and put the answer back
            ans = eval(self.text.GetValue())
            self.text.SetValue (str(ans))
        except Exception:
            print 'error'
    #put a blank string in text when 'Clear' is clicked
    def clearFunc(self,event):
        self.text.SetValue(str(''))

#mandatory in wx, create an app, False stands for not deteriction stdin/stdout
#refer manual for details
app = wx.App(False)

#create an object of CalcFrame
frame = CalcFrame(None)
#show the frame
frame.Show(True)
#start the applications
app.MainLoop()


The File contains less than 20 Lines of functional code.
All hail Python !!

If you are using IDLE on windows you can run this by clicking on Run Module and on Linux you can use python file.py where file.py is the file with the above contents. ( Thanks No more commandline )

Usage

Insert any valid mathematical expression in the Text Box and get the result
12

13