Fourier Transform

Motivation

• seperate smooth regions from details
• detect discrete repeated patterns
• remove periodic noise
• accelerate large-kernel filtering
• ease of identifying and modifying images via frequecy for some images

Spatial Frequency

• it identifies how fast intensity changes
• low frequency: slow intensity variation
• high frequency: rapid intensity variation
• Spatial frequency is commonly measured in cycles per unit distance or cycles per image

Different frequency's representation in Images

Low frequency: illumination, background, large shapes
High frequency: edges, texture, fine details, noise

Fourier Transform

$$F(x,y)=\sum weightedsinusoids$$

Basis Fourier Pattern

• previously we learnt that any spatial image can be built using single bright pixel impulse
• that was called Spatial Impulse Basis, $\delta (x,y)$
• now we learn that the same spatial image can also be built by a Fourier Pattern
• which is a full-screen 2D sinusoidal wave of stripes that spans across the entire image frame
• this is called Basis Fourier Pattern, $b_{u,v}(x,y)$ ,which is just a different basis function

flowchart LR

A[Types of Basis Functions] --> B(1. Spatial Impulse Basis)
A[Types of Basis Functions] --> C(2. Basis Fourier Pattern)

• Basis Functions are the fundamental representation of a 2D spatial image

$$b_{u,v}=\exp (j2\pi (ux+vy))=cos(2\pi (ux+vy))+jsin(2\pi (ux+vy))$$

The above equation represents a Basis Fourier Pattern:

• $u$ controls horizontal variation
• $v$ controls vertical variation
• amplitude controls strength
• phase controls alignments

Fourier Transform and Inverse Fourier Transform

Fourier Transform:

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

Inverse Fourier Transform:

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

where:

• $f(x,y)$: spatial image
• $F(u,v)$: frequency representation
• $(u,v)$: spatial frequencies

Name / Pattern	Spatial Domain $f(x,y)$	Frequency Domain $F(u,v)$
Impulse	$\delta (x,y)$	$1$
Gaussian	$A\sqrt{2\pi }\sigma e^{-2{\pi }^2{\sigma }^2(x^2+y^2)}$	$A{e}^{-(u^2+v^2)/2{\sigma }^2}$
Rectangle	$\text{rect}[a,b]$	$ab\frac{\sin (\pi ua)}{(\pi ua)}\frac{\sin (\pi vb)}{(\pi vb)}{e}^{-j\pi (ua+vb)}$
Cosine	$\cos (2\pi u_{0}x+2\pi v_{0}y)$	$\frac{1}{2}[\delta (u+u_0,v+v_0)+\delta (u-u_0,v-v_0)]$
Sine	$\sin (2\pi u_{0}x+2\pi v_{0}y)$	$j\frac{1}{2}[\delta (u+u_0,v+v_0)-\delta (u-u_0,v-v_0)]$

Magnitude and Phase

$$F(u,v)=|F(u,v)|\exp [j\phi (u,v)]$$

Polar to Rectangular Conversions

Real Part ($R$):

$$R=|F|\cos \phi$$

Imaginary Part ($I$):

$$I=|F|\sin \phi$$

Magnitude Spectrum ($|F|$):

$$|F|=\sqrt{R^2+I^2}$$

Phase Spectrum ($\phi$):

$$\phi ={\tan }^{-1}\left(\frac{I}{R}\right)$$

Log Magnitude

• we need to use log magnitude since the dynamic range is too large to display using basic magnitude

My Own Understanding of Frequency Domain from an Image in Spatial Domain

Basically we have an image in spatial domain. It has size $M\times N$.

Looking at the formula: $b_{u,v}(x,y)$, this is the fourier basis pattern which is used for the fourier transform of the image from spatial domain to frequency domain.

Now, we have 2 ways to use this formula.

1. First is by subbing in a fixed spatial point $(x_0,y_0)$. When we substitute a fixed spatial point, we will get $b_{u,v}(x_0,y_0)$ which gives us every possible basis patterns at that particular point $(x_0,y_0)$.
2. Next, we can also sub in a fixed frequency point $(u_0,y_0)$. This gives us 1 specific fourier basis pattern.

Note how we will get a total of $MN$ number of basis patterns/complex 2-dimensional sinusoid. Its complex because:

$b_{u,v}=\exp (j2\pi (ux+vy))=cos(2\pi (ux+vy))+jsin(2\pi (ux+vy))$

It contains the cosine pattern as its real part and a sine pattern as its imaginary part. Each unique frequency coordinate $(u,v)$ gives a sinusoid with a specific frequency and orientation.