Content
This chapter is concerned primarily with helping the reader develop a basic understanding of the Fourier transform and the frequency domain, and how they apply to image enhancement.

Background Introduction to the Fourier Transform and the Frequency Domain DFT Smoothing Frequency-Domain Filters Sharpening Frequency-Domain Filters

4.1 Background
• Any function that periodically repeats itself can be expressed as the sum of sines and/or cosines of different frequencies, each multiplied by a different coefficient (Fourier series). • Even functions that are not periodic (but whose area under the curve is finite) can be expressed as the integral of sines and/or cosines multiplied by a weighting function (Fourier transform). • The advent of digital computation and the “discovery” of fast Fourier Transform (FFT) algorithm in the late 1950s revolutionized the field of signal processing, and allowed for the first time practical processing and meaningful interpretation of a host of signals of exceptional human and industrial importance.

• The frequency domain refers to the plane of the two dimensional discrete Fourier transform of an image. • The purpose of the Fourier transform is to represent a signal as a linear combination of sinusoidal signals of various frequencies.

=
Any function that periodically repeats itself can be expressed as a sum of sines and cosines of different frequencies each multiplied by a different coefficient – a Fourier series

4.2 Introduction to the Fourier Transform and the Frequency Domain
• The one-dimensional Fourier transform and its inverse – Fourier transform (continuous case)
F (u ) = ∫ f ( x)e − j 2πux dx where j = − 1
−∞ ∞

– Inverse Fourier transform: f ( x) = ∫ F (u )e j 2πux du
−∞ ∞

e jθ = cos θ + j sin θ

• The two-dimensional Fourier transform and its inverse – Fourier transform (continuous case)
F (u , v) = ∫
∞ −∞ −∞

∫

∞

f ( x, y )e − j 2π ( ux + vy ) dxdy

– Inverse Fourier transform: f ( x, y ) = ∫
∞ −∞ −∞

∫

∞

F (u, v)e j 2π (ux + vy ) dudv

4.2.1The one-dimensional Fourier transform and its inverse (discrete time case)
– Fourier transform (DFT) 1 M −1 F (u ) = f ( x)e − j 2πux / M for u = 0,1,2,..., M − 1 ∑ M x =0 – Inverse Fourier transform (IDFT)

f ( x) = ∑ F (u )e j 2πux / M u =0

M −1

for x = 0,1,2,..., M − 1

The 1/M multiplier in front of the Fourier transform sometimes is placed in the front of the inverse instead. Other times both equations are multiplied by Unlike continuous case, the discrete Fourier transform and its inverse always exist, only 1/ f(x) is finite duration. if M

jθ • Since e = cos θ + j sin θ and the fact cos(−θ ) = cos θ then discrete Fourier transform can be redefined

1 M −1 F (u ) = ∑ f ( x)[cos 2π ux / M − j sin 2π ux / M ] M x =0 for u = 0,1, 2,..., M − 1

– Frequency (time) domain: the domain (values of u) over which the values of F(u) range; because u determines the frequency of the components of the transform. – Frequency (time) component: each of the M terms of F(u).

• F(u) can be expressed in polar coordinates:
F (u ) = F (u ) e jφ (u ) where F (u ) =  R 2 (u ) + I 2 (u )   
1/2

(magnitude or spectrum)

φ (u ) = tan −1 

 I (u )   (phase angle or phase spectrum)  R (u ) 

– R(u): the real part of F(u) – I(u): the imaginary part of F(u)

• Power spectrum:
P(u ) = F (u ) = R 2 (u ) + I 2 (u )
2

Some One-Dimensional Fourier Transform Examples

Please note the relationship between the value of K and the height of the spectrum and the number of zeros in the frequency domain.

• The transform of a constant function is a DC value only.

• The transform of a delta function is a constant.

• The transform of an infinite train of delta functions spaced by T is an infinite train of delta functions spaced by 1/T.

• The transform of a cosine function is a positive delta at the appropriate positive and negative frequency.

• The transform of a sin function is a negative complex delta function at the appropriate positive frequency and a negative complex delta at the appropriate negative frequency.

• The transform of a square pulse is a sinc function.

The Discrete Fourier Transform (DFT)
The Discrete Fourier Transform of f(x, y), for x = 0, 1, 2…M-1 and y = 0,1,2…N-1, denoted by F(u, v), is given by the equation:
M −1 N −1

F (u , v ) =

∑ ∑ f ( x, y )e x =0 y =0

− j 2 π ( ux / M +vy / N )

for u = 0, 1, 2…M-1 and v = 0, 1, 2…N-1.

4.2.2 The two-dimensional Fourier transform and its inverse (discrete time case)
– Fourier transform (DFT)
1 F (u, v) = MN
M −1 N −1

∑∑ x =0 y =0

f ( x, y )e − j 2π (ux / M + vy / N )

for u = 0,1,2,..., M − 1, v = 0,1,2,..., N − 1

– Inverse Fourier transform (IDFT) f ( x, y ) = ∑∑ F (u , v)e j 2π ( ux / M + vy / N ) u =0 v =0 M −1 N −1

for x = 0,1,2,..., M − 1, y = 0,1,2,..., N − 1
• u, v : the transform or frequency variables • x, y : the spatial or image variables

• We define the Fourier spectrum, phase anble, and power spectrum of the two-dimensional Fourier transform as follows:
F (u, v) = R (u, v) + I (u, v)
−1

[

2

2

]

1 2

( spectrum)

 I (u , v)  φ (u, v) = tan   (phase angle)  R(u , v)  P (u,v) = F (u , v) = R 2 (u , v) + I 2 (u, v) (power spectrum)
2

– R(u,v): the real part of F(u,v) – I(u,v): the imaginary part of F(u,v)

• Some properties of Fourier transform:
ℑ f ( x, y )(−1) 1 F (0,0) = MN

[

x+ y

]

M N = F (u − , v − ) (shift) 2 2 (average)

M −1 N −1 x =0 y =0

∑∑ f ( x, y)

F (u, v) = F * (−u ,−v) F (u , v) = F (−u ,−v)

(conujgate symmetric) (symmetric)

Steps and some example of two-dimensional DFT The 2D DFT F(u,v) can be obtained by 1. taking the 1D DFT of every row of image f(x,y), F(u,y), 2. taking the 1D DFT of every column of F(u,y)

(a) f(x,y)
Convention of coordination:

(b) F(u,y) y or v x or u

(c) F(u,v)

DFT & Images
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

The DFT of a two dimensional image can be visualised by showing the spectrum of the images component frequencies

DFT

The Inverse DFT
It is really important to note that the Fourier transform is completely reversible The inverse DFT is given by:

1 f ( x, y ) = MN

M −1 N −1 u =0 v =0

∑ ∑ F (u , v ) e

j 2 π ( ux / M +vy / N

for x = 0, 1, 2…M-1 and y = 0, 1, 2…N-1

The DFT and Image Processing
To filter an image in the frequency domain:
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

1. Compute F(u,v) the DFT of the image 2. Multiply F(u,v) by a filter function H(u,v) 3. Compute the inverse DFT of the resul
Including multiplication the input/output image by (-1)x+y.

Some Basic Frequency Domain Filters
Low Pass Filter

High Pass Filter

Shape of three dimensional spectrum

The Property of Two-Dimensional DFT Expansion

A DFT

B

DFT

Expanding the original image by a factor of n (n=2), filling the empty new values with zeros, results in the same DFT.

Two-Dimensional DFT with Different Functions

Sine wave

Its DFT

Rectangle

Its DFT

Some Basic Filters and Their Functions
• Multiply all values of F(u,v) by the filter function (notch filter):  0 if (u , v) = ( M / 2, N / 2) H (u , v) =  otherwise. 1 – All this filter would do is set F(0,0) to zero (force the average value of an image to zero) and leave all other frequency components of the Fourier transform untouched and make prominent edges stand out

Some Basic Filters and Their Functions

Low frequency filters: eliminate the gray-level detail and keep the general gray-level appearance. (blurring the image) Low frequency filters: have less gray-level variations in smooth areas and emphasized transitional (e.g., edge and noise) gray-level detail. (sharpening images)

4.2.4 Correspondence between Filtering in the Spatial and Frequency Domain
• Convolution theorem:
– The discrete convolution of two functions f(x,y) and h(x,y) of size M × N is defined as

1 M −1 N −1 f ( x, y ) ∗ h ( x , y ) = ∑0 ∑ f (m, n)h( x − m, y − n) MN m = n =0 1 M −1 N −1 = ∑0 ∑ h(m, n) f ( x − m, y − n) MN m = n =0 The process of implementation: 1) Flipping one function about the origin; 2) Shifting that function with respect to the other by changing the values of (x, y); 3) Computing a sum of products over all values of m and n, for each displacement.

–Let F(u,v) and H(u,v) denote the Fourier transforms of f(x,y) and h(x,y), then Eq. (4.2-31) f ( x, y ) ∗ h( x, y ) ⇔ F (u , v) H (u , v)

f ( x, y)h( x, y) ⇔ F (u, v) ∗ H (u, v)

Eq. (4.232)

• an impulse function of strength A, located at coordinates (x0,y0): Aδ ( x − x0 , y − y0 ) and is defined by : M −1 N −1 ∑∑ s( x, y) Aδ ( x − x0 , y − y0 ) = As( x0 , y0 ) x =0 y =0
M −1 N −1 x =0 y =0

∑∑ s( x, y)δ ( x, y) = s(0,0)

The shifting property of impulse function

where δ ( x, y ) : a unit impulse located at the origin • The Fourier transform of a unit impulse at the origin (Eq4.2-35) : 1 M −1 N −1 1 δ ( x, y )e − j 2π (ux / M +vy / N ) = F (u , v) = ∑∑ MN x =0 y =0 MN

• Let f ( x, y ) = δ ( x, y ) , then the convolution (Eq. (4.2-36))
1 M −1 N −1 f ( x, y ) ∗ h ( x, y ) = ∑∑ δ (m, n)h( x − m, y − n) MN m =0 n =0 1 = h ( x, y ) MN

• Combine Eqs. (4.2-35) (4.2-36) with Eq. (4.2-31), we obtain: f ( x, y ) ∗ h( x, y ) ⇔ F (u, v) H (u , v) δ ( x, y ) ∗ h( x, y ) ⇔ ℑ[δ ( x, y )]H (u, v) 1 1 h ( x, y ) H (u, v) MN MN h( x, y ) ⇔ H (u , v)

That is to say, the response of impulse input is the transfer function of filter.

The distinction and links between spatial and frequency filtering
If the size of spatial and frequency filters is same, then the computation burden in spatial domain is larger than in frequency domain; However, whenever possible, it makes more sense to filter in the spatial domain using small filter masks. Filtering in frequency is more intuitive. We can specify filters in the frequency, take their inverse transform, and the use the resulting filter in spatial domain as a guide for constructing smaller spatial filter masks. Fourier transform and its inverse are linear process, so the following discussion is limited to linear processes.

There is two reasons that filters based on Gaussian functions are of particular importance: 1) their shapes are easily specified; 2) both the forward and inverse Fourier transforms of a Gaussian are real Gaussian function.

• Let H(u) denote a frequency domain, Gaussian filter function given the equation

H (u ) = Ae where σ : the standard deviation of the Gaussian curve. • The corresponding filter in the spatial domain is

− u 2 / 2σ 2

h( x) = 2π σAe

−2π 2σ 2 x 2

H (u ) = Ae

2 − u 2 / 2σ1

− Be

2 − u 2 / 2σ 2

, ( A ≥ B, σ 1 ≥ σ 2 )

The corresponding filter in the spatial domain is

h( x) = 2πσ 1 Ae

2 −2π 2σ1 x 2

− 2πσ 2 Be

2 −2π 2σ 2 x 2

We can note that the value of this types of filter has both negative and positive values. Once the values turn negative, they never turn positive again. Filtering in frequency domain is usually used for the guides to design the filter masks in the spatial domain.

Some important properties of Gaussian filters funtions • One very useful property of the Gaussian function is that both it and its Fourier transform are real valued; there are no complex values associated with them. • In addition, the values are always positive. So, if we convolve an image with a Gaussian function, there will never be any negative output values to deal with. • There is also an important relationship between the widths of a Gaussian function and its Fourier transform. If we make the width of the function smaller, the width of the Fourier transform gets larger. This is controlled by the variance parameter σ2 in the equations. • These properties make the Gaussian filter very useful for lowpass filtering an image. The amount of blur is controlled by σ2. It can be implemented in either the spatial or frequency domain. • Other filters besides lowpass can also be implemented by using two different sized Gaussian functions.

4.2 Smoothing Frequency-Domain Filters
• The basic model for filtering in the frequency domain G (u , v) = H (u, v) F (u , v) where F(u,v): the Fourier transform of the image to be smoothed H(u,v): a filter transfer function • Smoothing is fundamentally a lowpass operation in the frequency domain. • There are several standard forms of lowpass filters (LPF).
– Ideal lowpass filter – Butterworth lowpass filter – Gaussian lowpass filter

Smoothing Frequency Domain Filters
Smoothing is achieved in the frequency domain by dropping out the high frequency components The basic model for filtering is: G(u,v) = H(u,v)F(u,v) where F(u,v) is the Fourier transform of the image being filtered and H(u,v) is the filter transform function Low pass filters – only pass the low frequencies, drop the high ones

Ideal Low Pass Filter
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Simply cut off all high frequency components that are a specified distance D0 from the origin of the transform

changing the distance changes the behaviour of the filter

Ideal Low Pass Filter (cont…)
The transfer function for the ideal low pass filter can be given as:

1 if D(u , v) ≤ D0 H (u , v) =  0 if D(u , v) > D0 where D(u,v) is given as:

D(u, v) = [(u − M / 2) 2 + (v − N / 2) 2 ]1/ 2

Ideal Lowpass Filters (ILPFs) • The simplest lowpass filter is a filter that “cuts off” all high-frequency components of the Fourier transform that are at a distance greater than a specified distance D0 from the origin of the transform. • The transfer function of an ideal lowpass filter 1 if D(u , v) ≤ D0 H (u, v) =  0 if D (u, v) > D0 where D(u,v) : the distance from point (u,v) to the center of ther frequency rectangle (M/2, N/2)

D(u, v) = (u − M / 2) + (v − N / 2)

[

2

1 2 2

]

Ideal Low Pass Filter (cont…)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Above we show an image, it’s Fourier spectrum and a series of ideal low pass filters of radius 5, 15, 30, 80 and 230 superimposed on top of it

Ideal Low Pass Filter (cont…)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Original image

Result of filtering with ideal low pass filter of radius 5

Result of filtering with ideal low pass filter of radius 15 Result of filtering with ideal low pass filter of radius 80

Result of filtering with ideal low pass filter of radius 30 Result of filtering with ideal low pass filter of radius 230

cutoff frequency

ILPF is a type of “nonphysical” filters and can’t be realized with electronic components and is not very practical.

The blurring and ringing phenomena can be seen, in which ringing behavior is characteristic of ideal filters.

Another example of ILPF
Figure 4.13 (a) A frequency-domain ILPF of radius 5. (b) Corresponding spatial filter. (c) Five impulses in the spatial domain, simulating the values of five pixels. (d) Convolution of (b) and (c) in the spatial domain.

frequency

f ( x, y ) ∗ h( x, y ) ⇔ F (u, v) H (u, v)

Notation: the radius of center component and the number of circles per unit distance from the origin are inversely proportional to the value of the cutoff frequency. diagonal scan line of (d)

spatial

spatial

spatial

Butterworth Lowpass Filters
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

The transfer function of a Butterworth lowpass filter of order n with cutoff frequency at distance D0 from the origin is defined as: 1 H (u , v) = 1 + [ D(u , v) / D0 ]2 n

Butterworth Lowpass Filter (cont…)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Original image

Result of filtering with Butterworth filter of order 2 and cutoff radius 5 Result of filtering with Butterworth filter of order 2 and cutoff radius 30 Result of filtering with Butterworth filter of order 2 and cutoff radius 230

Result of filtering with Butterworth filter of order 2 and cutoff radius 15 Result of filtering with Butterworth filter of order 2 and cutoff radius 80

Butterworth Lowpass Filters (BLPFs)

n=2 D0=5,15,30,80,and 230

Butterworth Lowpass Filters (BLPFs) Spatial Representation

n=1

n=2

n=5

n=20

Gaussian Lowpass Filters (FLPFs)

H (u , v) = e

2 − D 2 ( u ,v ) / 2 D0

Gaussian Lowpass Filters (FLPFs)

D0=5,15,30,80,and 230

Lowpass Filtering Examples (cont…)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Different lowpass Gaussian filters used to remove blemishes in a photograph

Additional Examples of Lowpass Filtering
Character recognition in machine perception: join the broken character segments with a Gaussian lowpass filter with D0=80.

Sharpening in the Frequency Domain
Edges and fine detail in images are associated with high frequency components High pass filters – only pass the high frequencies, drop the low ones High pass frequencies are precisely the reverse of low pass filters, so: Hhp(u, v) = 1 – Hlp(u, v)

4.4 Sharpening Frequency Domain Filter

H hp (u , v) = 1 − H lp (u , v)
Ideal highpass filter
0 H (u , v) =  1 if D (u , v) ≤ D0 if D (u, v) > D0

Butterworth highpass filter
H (u , v) = 1 2n 1 + [D0 / D(u, v)]

Gaussian highpass filter
H (u , v ) = 1 − e
2 − D 2 ( u ,v ) / 2 D0

Ideal High Pass Filters
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

The ideal high pass filter is given as:

0 if D(u , v) ≤ D0 H (u , v) =  1 if D(u , v) > D0

where D0 is the cut off distance as before

Ideal High Pass Filters (cont…)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Results of ideal high pass filtering with D0 = 15

Results of ideal high pass filtering with D0 = 30

Results of ideal high pass filtering with D0 = 80

Butterworth High Pass Filters
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

The Butterworth high pass filter is given as:

1 H (u , v) = 1 + [ D0 / D(u , v)]2 n where n is the order and D0 is the cut off distance as before

Butterworth High Pass Filters (cont…)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Results of Butterwort h high pass filtering of order 2 with D0 = 15

Results of Butterworth high pass filtering of order 2 with D0 = 30

Results of Butterwort h high pass filtering of order 2 with D0 = 80

Gaussian High Pass Filters
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

The Gaussian high pass filter is given as:

H (u, v) = 1 − e

− D 2 ( u ,v ) / 2 D0 2

where D0 is the cut off distance as before

Gaussian High Pass Filters (cont…)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Results of Gaussian high pass filtering with D0 = 15

Results of Gaussian high pass filtering with D0 = 30

Results of Gaussian high pass filtering with D0 = 80