Fourier transform

Created	@April 23, 2022
Tags	Basic Concepts

Q11: What’s a Fourier transform?

Answer: A Fourier transform is a generic method to decompose generic functions into a superposition of symmetric functions. Or as this more intuitive tutorial puts it, given a smoothie, it’s how we find the recipe. The Fourier transform finds the set of cycle speeds, amplitudes, and phases to match any time signal. A Fourier transform converts a signal from time to frequency domain—it’s a very common way to extract features from audio signals or other time series such as sensor data.

Fourier Transform Overview

The Fourier Transform is a mathematical transform used in physics and engineering to decompose a function of time (a signal) into the frequencies that make it up. This is analogous to finding the musical notes that, when played together, produce a complex sound. The Fourier Transform is fundamental in signal processing, image analysis, and many areas of applied mathematics. It transforms a time-domain signal into its constituent frequencies, providing a frequency-domain representation.

Mathematical Definition

The continuous Fourier Transform $F(\omega)$ of a continuous, integrable function $f(t)$, where $t$ represents time and $\omega$ represents angular frequency, is defined as:

$F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-j\omega t} dt$

Here, $e^{-j\omega t}$ is the complex exponential, where $j$ is the imaginary unit. The inverse Fourier Transform, which reconstructs $f(t)$ from $F(\omega)$, is given by:

$f(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega) e^{j\omega t} d\omega$

Discrete Fourier Transform (DFT)

In practice, especially in computer applications, we often work with sampled signals, leading to the Discrete Fourier Transform (DFT). The DFT converts a finite sequence of equally-spaced samples of a function into a sequence of coefficients of a finite combination of complex sinusoids, ordered by their frequencies:

$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j(2\pi/N)kn}$

where:

$N$ is the number of samples,

$x[n]$ is the $n$-th sample of the input (time domain),

$X[k]$ is the output (frequency domain),

$k$ is the index of the frequency component (ranging from 0 to $N-1$).

Applications

Signal Processing: Filtering, signal analysis, and signal reconstruction.

Image Processing: Image filtering, compression, and feature extraction.

Data Analysis: Spectral analysis and finding periodicities in data.

Telecommunications: Modulation and demodulation techniques.

Python Example Using NumPy

Here's how to compute the DFT of a simple signal using NumPy, a fundamental package for scientific computing with Python:

import numpy as np
import matplotlib.pyplot as plt

# Create a sample signal
t = np.linspace(0, 1, 400, endpoint=False)
signal = np.sin(2 * np.pi * 5 * t) + np.sin(2 * np.pi * 10 * t)

# Compute the DFT
signal_dft = np.fft.fft(signal)

# Compute the frequencies
freq = np.fft.fftfreq(t.shape[-1])

# Plot the magnitude of the DFT
plt.figure(figsize=(12, 5))
plt.plot(freq, np.abs(signal_dft))
plt.title('Magnitude of the DFT')
plt.xlabel('Frequency (Hz)')
plt.ylabel('Magnitude')
plt.grid(True)
plt.show()

This example creates a signal composed of two sine waves (5 Hz and 10 Hz), computes its DFT to transform it into the frequency domain, and plots the magnitude of the DFT. The plot reveals peaks at frequencies 5 Hz and 10 Hz, corresponding to the frequencies of the sine waves in the original signal.

Applying the Fourier Transform directly in Computer Vision (CV) and Natural Language Processing (NLP) tasks might seem unconventional at first glance, as these fields often use specialized techniques suited to their data types (images for CV and text for NLP). However, the Fourier Transform can play a role in preprocessing or feature extraction in both domains. Let's explore how it can be applied:

Computer Vision (CV) Example: Image Filtering

In computer vision, the Fourier Transform is used for image filtering, compression, and analysis. An image can be transformed from the spatial domain to the frequency domain. High frequencies in an image are associated with edges and fine details, whereas low frequencies correspond to smooth regions.

Example: Removing Noise from an Image

Suppose we have an image contaminated with high-frequency noise (like salt-and-pepper noise). We can apply the Fourier Transform to filter out this noise.

Transform the Image: Apply the Fourier Transform to the image to convert it from the spatial domain to the frequency domain.

Filter High Frequencies: Create a low-pass filter to remove high frequencies associated with noise.

Inverse Transform: Apply the inverse Fourier Transform to convert the image back to the spatial domain.

import numpy as np
import matplotlib.pyplot as plt
from scipy.fft import fft2, ifft2, fftshift, ifftshift
from skimage import data, img_as_float
from skimage.color import rgb2gray

# Load an example image
image = img_as_float(rgb2gray(data.astronaut()))

# Apply Fourier Transform
f_transform = fft2(image)
f_shifted = fftshift(f_transform)
magnitude_spectrum = 20*np.log(np.abs(f_shifted))

# Display the original image and its frequency domain representation
plt.figure(figsize=(12, 6))
plt.subplot(121), plt.imshow(image, cmap='gray'), plt.title('Original Image')
plt.subplot(122), plt.imshow(magnitude_spectrum, cmap='gray'), plt.title('Magnitude Spectrum')
plt.show()

# Apply a simple low-pass filter (e.g., a circular mask in the center)
rows, cols = image.shape
crow, ccol = rows//2, cols//2
mask = np.zeros((rows, cols), np.uint8)
r = 30  # radius of the mask
center = [crow, ccol]
x, y = np.ogrid[:rows, :cols]
mask_area = (x - center[0])**2 + (y - center[1])**2 <= r*r
mask[mask_area] = 1

# Apply mask and inverse FFT
f_shifted_masked = f_shifted * mask
f_ishifted = ifftshift(f_shifted_masked)
img_filtered = ifft2(f_ishifted)
img_filtered = np.abs(img_filtered)

# Display the filtered image
plt.figure(figsize=(6, 6))
plt.imshow(img_filtered, cmap='gray'), plt.title('Filtered Image')
plt.show()

This code loads an example grayscale image, applies the Fourier Transform to move it into the frequency domain, applies a low-pass filter to remove high-frequency noise, and then uses the inverse Fourier Transform to return the image to the spatial domain, displaying the filtered image.

Natural Language Processing (NLP) Example: Signal Processing for Speech

In NLP, the Fourier Transform is less directly applicable to text data but plays a crucial role in speech processing, a subfield of NLP. It can be used to analyze the frequency components of speech signals, which is useful for feature extraction, noise reduction, and speech recognition.

Example: Frequency Analysis of a Speech Signal

Capture a Speech Signal: Record a short speech sample or load a pre-recorded speech signal.

Apply Fourier Transform: Analyze the frequency components of the speech signal.

Visualize Frequencies: Plot the magnitude spectrum to identify dominant frequencies.

This example demonstrates the process conceptually as the actual recording and loading of speech data require specific libraries (like librosa for audio processing in Python) and are beyond the scope of this explanation.

The Fourier Transform's utility in CV and NLP highlights its versatility across different data types, offering valuable insights and processing capabilities that can enhance model performance and data understanding.