Linear Filtering – Part II - Bilkent University Computer Engineering

Linear Filtering – Part II - Bilkent University Computer Engineering

Linear Filtering – Part II
Selim Aksoy
Department of Computer Engineering
Bilkent University
[email protected]
Fourier theory
Jean Baptiste Joseph Fourier had a crazy idea:
Don’t believe it?
Any periodic function can be written as a weighted sum
of sines and cosines of different frequencies (1807).
Neither did Lagrange, Laplace, Poisson, …
But it is true!
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 cosines multiplied by a
weighing function.
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
2
Fourier theory
The Fourier theory
shows how most real
functions can be
represented in terms
of a basis of sinusoids.
The building block:
A sin( ωx + Φ )
Add enough of them
to get any signal you
want.
Adapted from Alexei Efros, CMU
CS 484, Spring 2010
©2010, Selim Aksoy
3
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
4
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
5
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
6
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
7
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
8
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
9
Fourier transform
Adapted from Alexei Efros, CMU
CS 484, Spring 2010
©2010, Selim Aksoy
10
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Gonzales and Woods
11
Fourier transform
Adapted from Gonzales and Woods
CS 484, Spring 2010
©2010, Selim Aksoy
12
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
13
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
14
Fourier transform
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Shapiro and Stockman
15
Fourier transform
Example building patterns
in a satellite image and
their Fourier spectrum.
CS 484, Spring 2010
©2010, Selim Aksoy
16
Convolution theorem
CS 484, Spring 2010
©2010, Selim Aksoy
17
Frequency domain filtering
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Shapiro and Stockman,
and Gonzales and Woods
18
Frequency domain filtering
Since the discrete Fourier transform is periodic, padding is
needed in the implementation to avoid aliasing (see section
4.6 in the Gonzales-Woods book for implementation details).
CS 484, Spring 2010
©2010, Selim Aksoy
19
Frequency domain filtering
f(x,y)
|F(u,v)|
×
h(x,y)
|H(u,v)|
⇓
⇓
g(x,y)
|G(u,v)|
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Alexei Efros, CMU
20
Smoothing frequency domain filters
Adapted from Gonzales and Woods
CS 484, Spring 2010
©2010, Selim Aksoy
21
Smoothing frequency domain filters
CS 484, Spring 2010
©2010, Selim Aksoy
22
Smoothing frequency domain filters
The blurring and ringing caused by the ideal lowpass filter can be explained using the convolution
theorem where the spatial representation of a
filter is given below.
CS 484, Spring 2010
©2010, Selim Aksoy
23
Smoothing frequency domain filters
Adapted from Gonzales and Woods
CS 484, Spring 2010
©2010, Selim Aksoy
24
Smoothing frequency domain filters
CS 484, Spring 2010
©2010, Selim Aksoy
25
Sharpening frequency domain filters
CS 484, Spring 2010
©2010, Selim Aksoy
26
Sharpening frequency domain filters
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Gonzales and Woods
27
Sharpening frequency domain filters
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Gonzales and Woods
28
Sharpening frequency domain filters
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Gonzales and Woods
29
Template matching
Correlation can also be used for matching.
If we want to determine whether an image f
contains a particular object, we let h be that
object (also called a template) and compute the
correlation between f and h.
If there is a match, the correlation will be
maximum at the location where h finds a
correspondence in f.
Preprocessing such as scaling and alignment is
necessary in most practical applications.
CS 484, Spring 2010
©2010, Selim Aksoy
30
Template matching
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Gonzales and Woods
31
Template matching
Face detection using template matching: face templates.
CS 484, Spring 2010
©2010, Selim Aksoy
32
Template matching
Face detection using template matching: detected faces.
CS 484, Spring 2010
©2010, Selim Aksoy
33
Resizing images
How can we generate a
half-sized version of a
large image?
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Steve Seitz, U of Washington
34
Resizing images
1/8
1/4
Throw away every other row and column to create
a 1/2 size image (also called sub-sampling).
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Steve Seitz, U of Washington
35
Resizing images
1/2
CS 484, Spring 2010
1/4 (2x zoom)
1/8 (4x zoom)
Does this look nice?Adapted from Steve Seitz, U of Washington
©2010, Selim Aksoy
36
Resizing images
We cannot shrink an image by simply taking every k’th pixel.
Solution: smooth the image, then sub-sample.
Gaussian 1/8
Gaussian 1/4
Gaussian 1/2
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Steve Seitz, U of Washington
37
Resizing images
Gaussian 1/2
CS 484, Spring 2010
Gaussian 1/4
(2x zoom)
©2010, Selim Aksoy
Gaussian 1/8
(4x zoom)
Adapted from Steve Seitz, U of Washington
38
Sampling and aliasing
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Steve Seitz, U of Washington
39
Sampling and aliasing
Errors appear if we do not sample properly.
Common phenomenon:
High spatial frequency components of the image appear
as low spatial frequency components.
Examples:
Wagon wheels rolling the wrong way in movies.
Checkerboards misrepresented in ray tracing.
Striped shirts look funny on color television.
CS 484, Spring 2010
©2010, Selim Aksoy
40
Gaussian pyramids
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Gonzales and Woods
41
Gaussian pyramids
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Michael Black, Brown University
42
Gaussian pyramids
CS 484, Spring 2010
©2010, Selim Aksoy
Adapted from Michael Black, Brown University
43