Fourier Transformation

Fourier Transform in Computer Vision

Digital Notes:

1. Introduction:

The Fourier Transform is a fundamental tool in signal processing and computer vision, used to decompose a signal (like an image) into its constituent frequencies. This allows us to analyze the frequency content of an image, perform filtering operations in the frequency domain, and reconstruct the original image from its frequency components.

2. Derivation (Continuous Case):

The continuous Fourier Transform for a 2D function (like an image) f(x, y) is defined as:

$F(u,v)={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f(x,y)e^{-j2\pi (ux+vy)}dxdy$

where:

• $F(u,v)$ is the Fourier Transform of $f(x,y)$.
• $u$ and $v$ represent frequencies in the x and y directions, respectively.
• $j$ is the imaginary unit ($\sqrt{-1}$).

The inverse Fourier Transform is given by:

$f(x,y)={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }F(u,v)e^{j2\pi (ux+vy)}dudv$

3. Fourier Coefficients:

The values $F(u,v)$ are complex numbers representing the amplitude and phase of each frequency component $(u,v)$. They are called Fourier coefficients.

4. Image Representation as [R][I]:

An image can be represented as a matrix where each element corresponds to a pixel value. After applying the Fourier Transform, we obtain a complex-valued matrix. This can be further decomposed into two matrices: one for the real part ([R]) and one for the imaginary part ([I]) of the Fourier coefficients.

5. Magnitude and Phase Spectrum:

• Magnitude Spectrum: $|F(u,v)|=\sqrt{Re(F(u,v){)}^2+Im(F(u,v){)}^2}$ represents the amplitude of each frequency component. It shows how much of each frequency is present in the image. Bright regions in the magnitude spectrum correspond to strong frequency components.
• Phase Spectrum: $\angle F(u,v)=\arctan \left(\frac{Im(F(u,v))}{Re(F(u,v))}\right)$ represents the phase shift of each frequency component. It carries information about the spatial relationships between different frequencies in the image.

6. Effect of Changes:

• Magnitude Spectrum Changes: Modifying the magnitude spectrum alters the strength of different frequencies. Reducing the magnitude of high frequencies can blur the image (remove noise), while amplifying them can sharpen the image.
• Phase Spectrum Changes: Altering the phase spectrum disrupts the spatial relationships between frequencies, leading to significant distortions in the reconstructed image. Phase information is crucial for preserving image structure.

7. Removing High-Frequency Noise:

High-frequency components often correspond to noise in images. By applying a low-pass filter in the frequency domain (e.g., setting the magnitude of high-frequency components to zero), we can effectively remove noise while preserving the essential image content.

8. Painful Parts of Spectral Domain:

• Computational Cost: Calculating the Fourier Transform can be computationally expensive, especially for large images.
• Handling Complex Numbers: Dealing with complex numbers requires careful implementation and can increase computational complexity.
• Visualization and Interpretation: Visualizing and interpreting the phase spectrum can be challenging.

9. Representing Magnitude and Phase with Euler’s Formula:

Euler’s formula relates complex exponentials to trigonometric functions:

$e^{j\theta }=\cos (\theta )+j\sin (\theta )$

The Fourier coefficients can be expressed using Euler’s formula:

$F(u,v)=|F(u,v)|e^{j\angle F(u,v)}$

Where:

• $|F(u,v)|=\sqrt{a^2+b^2}$ (magnitude)
• $\angle F(u,v)=\arctan (\frac{b}{a})$ (phase)
• $a=Re(F(u,v))$ and $b=Im(F(u,v))$

10. Discrete Fourier Transform (DFT):

For digital images, we use the Discrete Fourier Transform (DFT). The DFT of an N x M image is given by:

$F(u,v)={\sum }_{x=0}^{N-1}{\sum }_{y=0}^{M-1}f(x,y)e^{-j2\pi (\frac{ux}{N}+\frac{vy}{M})}$

The inverse DFT is:

$f(x,y)=\frac{1}{NM}{\sum }_{u=0}^{N-1}{\sum }_{v=0}^{M-1}F(u,v)e^{j2\pi (\frac{ux}{N}+\frac{vy}{M})}$

The DFT is commonly implemented using the Fast Fourier Transform (FFT) algorithm, which significantly reduces the computational complexity.