Digital Image Processing

Filtering in the Frequency Domain

Christophoros Nikou
cnikou@cs.uoi.gr

University of Ioannina - Department of Computer Science

2 Filtering in the Frequency Domain
Filter: A device or material for suppressing or
minimizing waves or oscillations of certain
frequencies.

Frequency: The number of times that a periodic

function repeats the same sequence of values
during a unit variation of the independent variable.

Webster’s New Collegiate Dictionary

C. Nikou – Digital Image Processing (E12)

3 Contents
In this lecture we will look at image
enhancement in the frequency domain
– Aliasing due to sampling
– The Fourier series & the Fourier transform
• Theory developed at the blackboard
– Image Processing in the frequency domain
• Image smoothing
• Image sharpening
– Fast Fourier Transform

C. Nikou – Digital Image Processing (E12)

4 Jean Baptiste Joseph Fourier
Fourier was born in Auxerre,
France in 1768
– Most famous for his work “La
Théorie Analitique de la
Chaleur” published in 1822
– Translated into English in 1878:
“The Analytic Theory of Heat”
Nobody paid much attention when the work
was first published
One of the most important mathematical
theories in modern engineering
C. Nikou – Digital Image Processing (E12)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)
5 The Big Idea

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
C. Nikou – Digital Image Processing (E12)
Taken from www.tfh-berlin.de/~schwenk/hobby/fourier/Welcome.html
6 The Big Idea (cont…)

Notice how we get closer and closer to the

original function as we add more and more
frequencies

C. Nikou – Digital Image Processing (E12)

7 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 − j 2π ( ux / M +vy / N )

x =0 y =0

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

C. Nikou – Digital Image Processing (E12)

8 The Inverse DFT
It is really important to note that the Fourier
transform is completely reversible
The inverse DFT is given by:
M −1 N −1
1
f ( x, y ) =
MN
∑∑ F (u, v)e
u =0 v =0
j 2π ( ux / M +vy / N )

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

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

The Box Filter
 Images taken from Gonzalez & Woods, Digital Image Processing (2002)
10

C. Nikou – Digital Image Processing (E12)

2D Impulse Train
 11
2D Fourier Transform of Sampled
Signals
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Over-sampled Under-sampled

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

Aliasing
13 Moiré Patterns
Effect of sampling a scene with periodic or nearly
periodic components (e.g. overlapping grids, TV
raster lines and stripped materials).

In image processing the problem arises when

scanning media prints (e.g. magazines,
newspapers).

The problem is more general than sampling

artifacts.

C. Nikou – Digital Image Processing (E12)

14 Moiré Patterns (cont...)
Superimposed grid drawings (not digitized)
produce the effect of new frequencies not existing
in the original components.

C. Nikou – Digital Image Processing (E12)

15 Moiré Patterns (cont...)
In printing industry the problem comes when
scanning photographs from the superposition of:

1) The sampling lattice (usually horizontal and

vertical).
2) Dot patterns on the newspaper image.

C. Nikou – Digital Image Processing (E12)

16 Moiré Patterns (cont...)

C. Nikou – Digital Image Processing (E12)

17 Moiré Patterns (cont...)
The printing
industry uses
halftoning to cope
with the problem.

The dot size is

inversely
proportional to
image intensity.

C. Nikou – Digital Image Processing (E12)

 18 DFT & Images
The DFT of a two dimensional image can be
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

visualised by showing the spectrum of the

image component frequencies

DFT

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

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

DFT

Scanning electron microscope Fourier spectrum of the image

image of an integrated circuit
magnified ~2500 times

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

DFT & Images (cont…)
24 Periodicity of the DFT
The range of
frequencies of the
signal is between
[-M/2, M/2].
The DFT covers
two back-to-back
half periods of the
signal as it covers
[0, M-1].

C. Nikou – Digital Image Processing (E12)

25 Periodicity of the DFT (cont...)
For display and computation purposes it is
convenient to shift the DFT and have a
complete period in [0, M-1].
From DFT properties:
j 2π ( N 0 n / M )
f [n]e ⇔ F (k − N 0 )

Letting N0=M/2: f [n](−1) ⇔ F (k − M / 2)

n

And F(0) is now located at M/2.

C. Nikou – Digital Image Processing (E12)
26 Periodicity of the DFT (cont...)
In two dimensions:
m+n
f [m, n](−1) ⇔ F (k − M / 2, l − N / 2)
And F(0,0) is now located at (M/2, N/2).

C. Nikou – Digital Image Processing (E12)

27 Periodicity of the DFT (cont...)

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

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

Although the images differ by a simple geometric

transformation no intuitive information may be
extracted from their phases regarding their relation.
C. Nikou – Digital Image Processing (E12)
 Images taken from Gonzalez & Woods, Digital Image Processing (2002)
31

C. Nikou – Digital Image Processing (E12)

DFT & Images (cont…)
 32 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 result

C. Nikou – Digital Image Processing (E12)

 33
Images taken from Gonzalez & Woods, Digital Image Processing (2002)
The importance of zero padding

C. Nikou – Digital Image Processing (E12)

 34
The importance of zero padding
(cont...)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

C. Nikou – Digital Image Processing (E12)

 35
The importance of zero padding
(cont...)
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

C. Nikou – Digital Image Processing (E12)

 36 Some Basic Frequency Domain Filters

Low Pass Filter

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

High Pass Filter

C. Nikou – Digital Image Processing (E12)
 37
Images taken from Gonzalez & Woods, Digital Image Processing (2002)
Some Basic Frequency Domain Filters

C. Nikou – Digital Image Processing (E12)

 38
Images taken from Gonzalez & Woods, Digital Image Processing (2002)
Some Basic Frequency Domain Filters

C. Nikou – Digital Image Processing (E12)

39 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.

C. Nikou – Digital Image Processing (E12)

 40 Ideal Low Pass Filter
Simply cut off all high frequency components
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

that are a specified distance D0 from the

origin of the transform

changing the distance changes the behaviour

of the filter C. Nikou – Digital Image Processing (E12)
41 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) + (v − N / 2) ]
2 2 1/ 2

C. Nikou – Digital Image Processing (E12)

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

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

C. Nikou – Digital Image Processing (E12)

 43 Ideal Lowpass Filters (cont...)
ILPF in the spatial domain is a sinc function
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

that has to be truncated and produces

ringing effects.
The main lobe is responsible for blurring and
the side lobes are responsible for ringing.

C. Nikou – Digital Image Processing (E12)

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

Result of filtering
Original with ideal low
image pass filter of
radius 5

Result of filtering Result of filtering

with ideal low with ideal low
pass filter of pass filter of
radius 15 radius 30

Result of filtering Result of filtering

with ideal low with ideal low
pass filter of pass filter of
radius 80 radius 230

C. Nikou – Digital Image Processing (E12)

 45 Butterworth Lowpass Filters
The transfer function of a Butterworth
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

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

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

 47 Butterworth Lowpass Filter (cont…)
Less ringing than ILPF
due to smoother
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

Result of filtering
transition
Original with Butterworth
image filter of order 2 and
cutoff radius 5

Result of filtering Result of filtering

with Butterworth with Butterworth
filter of order 2 and filter of order 2 and
cutoff radius 15 cutoff radius 30

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

C. Nikou – Digital Image Processing (E12)

 48 Gaussian Lowpass Filters
The transfer function of a Gaussian lowpass
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

filter is defined as:

− D ( u ,v ) / 2 D0
2 2
H (u , v) = e

C. Nikou – Digital Image Processing (E12)

 49 Gaussian Lowpass Filters (cont…)
Less ringing than
BLPF but also less
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

smoothing Result of filtering

Original with Gaussian
image filter with cutoff
radius 5

Result of filtering Result of filtering

with Gaussian with Gaussian
filter with cutoff filter with cutoff
radius 15 radius 30

Result of Result of filtering

filtering with with Gaussian
Gaussian filter filter with cutoff
with cutoff radius 230
radius 85

C. Nikou – Digital Image Processing (E12)

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

Result of
Result of filtering
filtering with
with ideal low
Butterworth filter
pass filter of
of order 2 and
radius 15
cutoff radius 15

Result of filtering
with Gaussian
filter with cutoff
radius 15

C. Nikou – Digital Image Processing (E12)

 51 Lowpass Filtering Examples
A low pass Gaussian filter is used to
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

connect broken text

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

 53 Lowpass Filtering Examples (cont…)
Different lowpass Gaussian filters used to
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

remove blemishes in a photograph

C. Nikou – Digital Image Processing (E12)

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

C. Nikou – Digital Image Processing (E12)

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

Original Gaussian
image lowpass filter

Spectrum of Processed
original image image

C. Nikou – Digital Image Processing (E12)

56 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)

C. Nikou – Digital Image Processing (E12)

 57 Ideal High Pass Filters
The ideal high pass filter is given as:
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

⎧0 if D(u , v) ≤ D0
H (u, v) = ⎨
⎩1 if D(u , v) > D0
where D0 is the cut off distance as before

C. Nikou – Digital Image Processing (E12)

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

Results of ideal Results of ideal Results of ideal

high pass filtering high pass filtering high pass filtering
with D0 = 15 with D0 = 30
C. Nikou – Digital Image
with D0 = 80
Processing (E12)
 59 Butterworth High Pass Filters
The Butterworth high pass filter is given as:
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

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

where n is the order and D0 is the cut off

distance as before

C. Nikou – Digital Image Processing (E12)

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

Results of Results of
Butterworth Butterworth
high pass high pass
filtering of filtering of
order 2 with order 2 with
D0 = 15 D0 = 80

Results of Butterworth high pass

filtering of order 2 with D0 = 30
C. Nikou – Digital Image Processing (E12)
 61 Gaussian High Pass Filters
The Gaussian high pass filter is given as:
Images taken from Gonzalez & Woods, Digital Image Processing (2002)

− D 2 ( u ,v ) / 2 D0 2
H (u , v) = 1 − e
where D0 is the cut off distance as before

C. Nikou – Digital Image Processing (E12)

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

Results of Results of
Gaussian Gaussian
high pass high pass
filtering with filtering with
D0 = 15 D0 = 80

Results of Gaussian high

pass filtering with D0 = 30
C. Nikou – Digital Image Processing (E12)
 63
Images taken from Gonzalez & Woods, Digital Image Processing (2002)
Highpass Filter Comparison

Results of ideal Results of Butterworth Results of Gaussian

high pass filtering high pass filtering of high pass filtering with
with D0 = 15 C. Nikouorder 2 Image
– Digital with DProcessing
0 = 15 (E12) D0 = 15
 Images taken from Gonzalez & Woods, Digital Image Processing (2002)
64
High frequency
emphasis result Original image

C. Nikou – Digital Image Processing (E12)

equalisation Highpass filtering result

After histogram
Highpass Filtering Example
 Images taken from Gonzalez & Woods, Digital Image Processing (2002)
65
Inverse DFT of Laplacian in the
Laplacian in the frequency domain
frequency domain (not centered)

C. Nikou – Digital Image Processing (E12)

(not centered)
domain
in the frequency
2-D image of Laplacian
to spatial filter
of the image on
Zoomed section
Laplacian In The Frequency Domain

the left compared

66 Frequency Domain Laplacian Example

Original Laplacian
image filtered
image

Laplacian
Enhanced
image
image
scaled

C. Nikou – Digital Image Processing (E12)

67 Band-Pass Filters

C. Nikou – Digital Image Processing (E12)

68 Band-Pass Filters (cont...)

C. Nikou – Digital Image Processing (E12)

69 Band-Pass Filters (cont...)

C. Nikou – Digital Image Processing (E12)

70 Fast Fourier Transform
The reason that Fourier based techniques
have become so popular is the development
of the Fast Fourier Transform (FFT)
algorithm
Allows the Fourier transform to be carried
out in a reasonable amount of time
Reduces the amount of time required to
perform a Fourier transform by a factor of
100 – 600 times!

C. Nikou – Digital Image Processing (E12)

71
Frequency Domain Filtering & Spatial
Domain Filtering
Similar jobs can be done in the spatial and
frequency domains
Filtering in the spatial domain can be easier
to understand
Filtering in the frequency domain can be
much faster – especially for large images

C. Nikou – Digital Image Processing (E12)

72 Summary
In this lecture we examined image
enhancement in the frequency domain
– Aliasing due to sampling
– The Fourier series & the Fourier transform
– Image Processing in the frequency domain
• Image smoothing
• Image sharpening
Next time we will begin to examine image
restoration using the spatial and frequency
based techniques we have been looking at
C. Nikou – Digital Image Processing (E12)