Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 1213
Kernel: Python 3 (Ubuntu Linux)

Math 157: Intro to Mathematical Software

UC San Diego, Winter 2018

March 15, 2018 : Fast Fourier Transforms

Nancy Juarez-Fuertes

"4-E-AY"

Collaborators: Anastasia Guiano, Megan Chang

This Worksheet:

  1. Overview

  2. Real Life Applications

  3. Common Functions

  4. Examples

  5. Exercises


Fast Fourier Transforms(FFT): Overview

What is FFT?

  • FFT is a discrete Fourier transform algorithm that samples a signal over a period of time and divides it into its frequency components.

  • Fourier analysis converts a dignal from its orginal domain into a frequency domain representation. FFT rapidly computes the transformation by factoring the descrete Fourier matrix into a product of sparse factors.

  • Were first discussed by cooley and Tukey in 1965

  • Gauss had already discussed the critical factorization step as early as 1805

Finding the Recipe!

  • Watch this video

  • Here's a great website that breaks down what the Fourier transform is and how it is used!

  • A Fourier Series is the summation of sine waves. A Fourier series can be used to represent any periodic signal.

  • Given a complex wave, a combination of many sine waves, (A Fourier Series), we can preform a Fourier Trandform to find the ingredients, used to create such a complex wave

  • We take the signal which shows us the power over a period of time, and we are transforming it into individual components which shows us the power of each wavelength, or frequency.

  • The Fourier Transform is a set of complicated equations.

  • The foureir Transform further proves how the Fourier series is a good approximation of a naturally occuring signal.

Real Life Applications

Where is the Fourier Transform used in the real world?

  • sound wave analysis

  • image data analysis

  • digital image processing

  • computer -assisted image processing

  • Edge detection (when you take a picture and you want to outline a person or something and transfer it to another image)

Make sure your kernel is set to "Python 3 (Ubuntu Linux)" before proceeding.

Functions used for FFT in Python:

One dimensional discrete Fourier Transform

Here is an example of fft and ifft

from scipy.fftpack import fft, ifft #Return discrete inverse Fourier transform of real or complex sequence. x = np.array([1.0, 2.0, 1.0, -1.0, 1.5]) y = fft(x) # fft Return discrete Fourier transform of real or complex sequence. y
array([ 4.5 +0.j , 2.08155948-1.65109876j, -1.83155948+1.60822041j, -1.83155948-1.60822041j, 2.08155948+1.65109876j])
yinv = ifft(y) #Return discrete inverse Fourier transform of real or complex sequence. yinv
array([ 1. +0.j, 2. +0.j, 1. +0.j, -1. +0.j, 1.5+0.j])

fftfreq returns sample frequency points.

from scipy.fftpack import fftfreq freq = fftfreq(8, 0.125) freq
array([ 0., 1., 2., 3., -4., -3., -2., -1.])

Here we plot the fast fourier transform of the sum of two sine waves.

from scipy.fftpack import fft # Number of sample points N = 600 # sample spacing T = 1.0 / 800.0 x = np.linspace(0.0, N*T, N) a = np.sin(50.0 * 2.0*np.pi*x) b = 0.5*np.sin(80.0 * 2.0*np.pi*x) y = a+b yf = fft(y) xf = np.linspace(0.0, 1.0/(2.0*T), N//2) import matplotlib.pyplot as plt plt.plot(xf, 2.0/N * np.abs(yf[0:N//2])) plt.grid() plt.show()
Image in a Jupyter notebook

Two dimensional Fourier Transform

The following example demonstrates a 2-dimensional inverse fast fourier transform.
from scipy.fftpack import ifftn import matplotlib.pyplot as plt import matplotlib.cm as cm N = 30 f, ((ax1, ax2, ax3), (ax4, ax5, ax6)) = plt.subplots(2, 3, sharex='col', sharey='row') xf = np.zeros((N,N)) xf[0, 5] = 1 xf[0, N-5] = 1 Z = ifftn(xf) ax1.imshow(xf, cmap=cm.Reds) ax4.imshow(np.real(Z), cmap=cm.gray) xf = np.zeros((N, N)) xf[5, 0] = 1 xf[N-5, 0] = 1 Z = ifftn(xf) ax2.imshow(xf, cmap=cm.Reds) ax5.imshow(np.real(Z), cmap=cm.gray) xf = np.zeros((N, N)) xf[5, 10] = 1 xf[N-5, N-10] = 1 Z = ifftn(xf) ax3.imshow(xf, cmap=cm.Reds) ax6.imshow(np.real(Z), cmap=cm.gray) plt.show()
Image in a Jupyter notebook

2-D Fourier Transforms are used in image processing. They are used to see peaks of spacial frequencies of repeated texture in images such as finger prints!

Digital Image Processing: Making an image blurry using FFT

Here is a "clear" example on how 2-D FFT applictions are applied to images.

import numpy as np from scipy import fftpack import matplotlib.pyplot as plt
img = plt.imread('lion.png') plt.figure() plt.imshow(img)
<matplotlib.image.AxesImage at 0x7ffa5ccbe940>
Image in a Jupyter notebook
# First a 1-D Gaussian t = np.linspace(-10, 10, 30) bump = np.exp(-0.1*t**2) bump /= np.trapz(bump) # normalize the integral to 1 # make a 2-D kernel out of it kernel = bump[:, np.newaxis] * bump[np.newaxis, :]

Padded fourier transform, with the same shape as the image We use :func:scipy.signal.fftpack.fft2 to have a 2D FFT

kernel_ft = fftpack.fft2(kernel, shape=img.shape[:2], axes=(0, 1)) img_ft = fftpack.fft2(img, axes=(0, 1)) img2_ft = kernel_ft[:, :, np.newaxis] * img_ft # the 'newaxis' is to match to color direction img2 = fftpack.ifft2(img2_ft, axes=(0, 1)).real img2 = np.clip(img2, 0, 1) # clip values to range # plot plt.figure() plt.imshow(img2)
<matplotlib.image.AxesImage at 0x7ffa5c438f98>
Image in a Jupyter notebook

Examples using wav files

Downloaded wav files from here. More websites available to get wav files here

Think about a mechanic who takes a sound sample of an engine and then relies on a machine to analyze that sample, looking for potential engine problems. The diagnostic can find some problems and visual inspection can find others, but sometimes the sound of an engine reveals issues that you can’t find in any other way.

import matplotlib.pyplot as plt from scipy.io import wavfile as wav from scipy.fftpack import fft import numpy as np

What does this do? What are the blue lines at the bottom?

rate, data = wav.read('whistle.wav') fft_out = fft(data) %matplotlib inline plt.plot(data, np.abs(fft_out)) #plt.axis([0,250,0,50000]) plt.show()
Image in a Jupyter notebook

This code reads a .wav file and solves the Fourier transform! The output displays the strongest detected frequencies over time. The blue lines at the bottom are the extra noise of the signal.

Note: I found that testing this with .wav files larger than 24 kb caused a bit of trouble when reading the file.

rate, data = wav.read('Movie-06.wav') fft_out = fft(data) %matplotlib inline plt.plot(data, np.abs(fft_out)) plt.show()
/usr/local/lib/python3.5/dist-packages/scipy/io/wavfile.py:273: WavFileWarning: Chunk (non-data) not understood, skipping it. WavFileWarning)
Image in a Jupyter notebook

Exercises

1. Plot the following FFT where y=sin(2Ď€t)y = sin(2 {\pi} t), the sampling rate is 150 and the frequuency signal is 5.
2a. Find and download a .wav file and add it to this folder.
2b. Plot the fft of your own sound
2c. What does your plot show you? How large was your wav file? When is this technique used in real wolrd applications?

Solutions:

#Solution 1 from numpy import fft import numpy as np import matplotlib.pyplot as plt n = 1000 # Number of data points dx = 5.0 # Sampling period (in meters) x = dx*np.arange(0,n) # x coordinates w1 = 100.0 # wavelength (meters) w2 = 20.0 # wavelength (meters) fx = np.sin(2*np.pi*x/w1) + 2*np.cos(2*np.pi*x/w2) # signal Fk = fft.fft(fx)/n # Fourier coefficients (divided by n) nu = fft.fftfreq(n,dx) # Natural frequencies Fk = fft.fftshift(Fk) # Shift zero freq to center nu = fft.fftshift(nu) # Shift zero freq to center f, ax = plt.subplots(3,1,sharex=True) ax[0].plot(nu, np.real(Fk)) # Plot Cosine terms ax[0].set_ylabel(r'$Re[F_k]$', size = 'x-large') ax[1].plot(nu, np.imag(Fk)) # Plot Sine terms ax[1].set_ylabel(r'$Im[F_k]$', size = 'x-large') ax[2].plot(nu, np.absolute(Fk)**2) # Plot spectral power ax[2].set_ylabel(r'$\vert F_k \vert ^2$', size = 'x-large') ax[2].set_xlabel(r'$\widetilde{\nu}$', size = 'x-large') plt.show()
Image in a Jupyter notebook
#solution 2 #2a. downloaded bowling.wav #2b. import matplotlib.pyplot as plt from scipy.io import wavfile as wav from scipy.fftpack import fft import numpy as np rate, data = wav.read('bowling.wav') fft_out = fft(data) %matplotlib inline plt.plot(data, np.abs(fft_out)) plt.show() #2c #The plot displays the most prominent frequency in the file. This application of fft is used in sound editing and audio engineerine. One can pinpoint the highest frequency and cancel out the whitenoise. The white noise can be extracted to create a smaller file, such as an MP3.
Image in a Jupyter notebook