Fast Fourier Transform (FFT) in Python

Fast Fourier Transform (FFT) is Discrete Fourier Transform (DFT) algorithm. To perform FFT in Python you need to install several packages/modules/libraries. You can skip this portion if you already have it available. I am a windows user so I will show how to setup your machine for windows environment. This is an effort to provide the easiest and extensive tutorial for image processing beginners in python.

Things you need to download and install are as follows:

1. Install Python 2.7.10 (as for Python 3.4 you will face challenges for other packages) from https://www.python.org/downloads/

2. Install SciPy 0.16.0 superpack for Python 2.7 from http://sourceforge.net/projects/scipy/files/scipy/0.16.0/

3. Install NumPy 1.9.2 superpack for Python 2.7 from http://sourceforge.net/projects/numpy/files/NumPy/1.9.2/

4. Install Six 1.9.0 from https://pypi.python.org/pypi/six

5. Install Matplotlib 1.4.3 for Python 2.7 from http://sourceforge.net/projects/matplotlib/files/matplotlib/matplotlib-1.4.3/windows/

6. Install Dateutil 2.4.2 from https://pypi.python.org/pypi/python-dateutil [Install Six (see step-4) before installing Dateutil]

7. Install PIL 1.1.7 for Python 2.7 from http://www.pythonware.com/products/pil/

8. Install PyParsing 2.0.3 for Python 2.7 from http://sourceforge.net/projects/pyparsing/files/pyparsing/pyparsing-2.0.3/

9. Install OpenCV (Open Source Computer Vision) 3.0.0 from http://sourceforge.net/projects/opencvlibrary/files/opencv-win/3.0.0/

--> Open command prompt (cmd.exe) and type python to check whether python is installed or not, if it shows an unrecognized command then set your python directory (C:\Python27) as PATH environment variable.

--> I am not using pip package manager for python so I have used tar.gz files instead of .whl files and installing it from command line. To install from tarball gzip (.tar.gz) archive first extract the file, go to that directory and run these two following commands:

python setup.py build

python setup.py install

--> After installing opencv-3.0.0.exe go to the directory where it is installed and follow this path:

opencv > build > python > 2.7 > x86 > cv2.pyd

Copy this cv2.pyd file to your python directory (C:\Python27) > Lib > site-packages

Ok, we are done with installation now. If you have any queries you may post it on the comment section below this post. All set? Great! Let's try out a simple application which reads an image and plots it.

Code:

import cv2
import numpy as np
from matplotlib import pyplot as plt

img = cv2.imread('2.png',0)
f = np.fft.fft2(img)
fshift = np.fft.fftshift(f)

magnitude_spectrum = 20*np.log(np.abs(fshift))
plt.subplot(121),plt.imshow(img, cmap = 'gray')
plt.title('Input Image'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(magnitude_spectrum, cmap = 'gray')
plt.title('Magnitude Spectrum'), plt.xticks([]), plt.yticks([])
plt.show()

Explanation:

Here we are reading the image file 2.png with opencv's imread function. It is passed as a 2D-array to numpy's fft2 which is a 2D Fast Fourier Transform of the image which it receives as a signal. We are plotting the input image which is read as raw data in grayscale as fft reads is as grayscale just to visualize the effect. [Please correct me if I am wrong here] Along with that magnitude spectrum is plotted which is obtained through fast fourier transform of the given image.

Output: