Filters in Image Processing
Introduction & Some revision
David Svoboda
email: svoboda@fi.muni.cz
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno, CZ
September 16, 2019
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 1 / 39
Outline
1 Introduction
Basic information
Structure of a lecture
Bibliography
2 Some Revision
Signal Filtering
Convolution
Vector Spaces
Function analysis
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 2 / 39
1 Introduction
Basic information
Structure of a lecture
Bibliography
2 Some Revision
Signal Filtering
Convolution
Vector Spaces
Function analysis
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 3 / 39
Introduction
Basic information
Lecture + seminar = 2 + 2 hours per week.
Final exam is written & spoken and is focused on your skills rather than knowledge.
Basic knowledge of English and math (calculus, statistics, algebra) is highly recommended.
Digital Image Processing (PV131) is highly recommended.
Seminars take place in PC labs using MATLAB R
The experience from seminars will be useful for completing a small team (two students)
project written in MATLAB R
, C/C++, Java (or the preferred language).
At the end of each lecture you can find a list of questions you should be able to answer if
you want to pass the final exam.
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
-10 -5 0 5 10
sin(2*x)*exp(-x*x/25)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 4 / 39
Introduction
Structure of a lecture
1 Introduction & Some revision
2 Fourier transform, Fast Fourier transform
3 Image resampling, Texture filtering
4 Principal component analysis, Discrete cosine transform
5 Subband coding, Wavelet Transform, Discrete WT
6 Z-transform, recursive filtering
7 Edge detection
8 Image compression
9 Image descriptors (Haralick, SIFT, MPEG-7, . . . )
10 Image restoration
11 Steerable filters
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 5 / 39
Introduction
Bibliography
Gonzalez, R. C., Woods, R. E., Digital image processing / 2nd ed.,
Upper Saddle River: Prentice Hall, 2002, pages 793, ISBN
0201180758
Bracewell, R. N., Fourier transform and its applications / 2nd ed.
New York: McGraw-Hill, pages 474, ISBN 0070070156
J¨ahne, B., Digital image processing / 6th rev. and ext. ed., Berlin:
Springer, 2005, pages 607, ISBN 3540240357
selected papers
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 6 / 39
1 Introduction
Basic information
Structure of a lecture
Bibliography
2 Some Revision
Signal Filtering
Convolution
Vector Spaces
Function analysis
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 7 / 39
Digital Filters in Image Processing
Some examples
Linear mappings (e.g. Fourier or Wavelet transform)
Denoising (e.g. median filtering)
Point based transforms (e.g. thresholding, contrast, brightness)
(Re)sampling (e.g. nearest neighbour, bilinear, Lanczos)
Texture filtering (e.g. anisotropic filtering)
Edge detection (e.g. Sobel, Canny)
Quantization (common in lossy compression techniques)
More . . .
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 8 / 39
Signal Filter
Definition
Filter F is any system having its input/output:
FILTERf h
h = F(f )
f (x) or f (m) . . . input image/function/signal
h(y) or h(n) . . . output image/function/signal
F . . . filter (functor)
x, y . . . continuous signal
m, n . . . discrete sequence
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 9 / 39
Convolution
1D convolution
Discrete: given two 1D signals f (i) and g(i):
(f ∗ g)(i) ≡
k
f (k)g(i − k)
Continuous: given two 1D signals f (x) and g(x):
(f ∗ g)(x) ≡
∞
−∞
f (x )g(x − x )dx
Notice: ’g’ is called a convolution kernel (mask)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 10 / 39
Convolution
An example
1D convolution
x’x x’x
1
1 1
f(x’)
x’ x’
x’
g(x’)
g(−x’) g(x−x’)
1
(f*g)(x)
x
f(x’)g(x−x’)
Try: http://www.jhu.edu/~signals/convolve/index.html
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 11 / 39
Convolution
2D convolution
Discrete: given two 2D signals f (i, j) and g(i, j):
(f ∗ g)(i, j) ≡
k,l
f (k, l)g(i − k, j − l)
Continuous: given two 2D signals f (x, y) and g(x, y):
(f ∗ g)(x, y) ≡ f (x , y )g(x − x , y − y )dx dy
Notice: If not necessary we will focus only on 1D (discrete) convolution.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 12 / 39
Impulse symbol δ
Definition
Infinitely brief and infinitely strong unit-area impulse:
δ(x) = 0 x = 0
and
∞
−∞
δ(x)dx = 1
we call it Dirac delta function or impulse symbol
it is NOT a function
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 13 / 39
Impulse symbol δ
Some properties
Given 1D function f and a ∈ R:
∞
−∞
δ(x)f (x)dx = f (0)
∞
−∞
δ(x − a)f (x)dx = f (a)
δ(x) plot:
x
y
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 14 / 39
Kronecker delta (function)
Kronecker delta function . . . discrete counterpart to Dirac delta impulse.
δi,j =
1 if (i = j)
0 otherwise
or
δ(n) =
1 if (n = 0)
0 otherwise
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 15 / 39
Convolution
With some important functions
Convolution of any function f with:
δ impulse shifts the origin of f to the nonzero response of δ
δ impulses replicate the function f
Gaussian shifts the origin of f to the position of the peak of the
Gaussian and smooths
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 16 / 39
Convolution properties
Commutativity
Given two signals f (i) and g(i):
(f ∗ g)(i) = (g ∗ f )(i)
Proof:
(f ∗ g)(i) =
∞
j=−∞
f (j)g(i − j) =
∞
j=−∞
g(i − j)f (j)
/subst. k = i − j; j = i − k/
=
∞
k=−∞
g(k)f (i − k)
= (g ∗ f )(i)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 17 / 39
Convolution properties
Associativity
Given three signals f (i), g(i), and h(i):
((f ∗ g) ∗ h)(i) = (f ∗ (g ∗ h))(i)
Proof:
((f ∗ g) ∗ h)(i) =
j
(f ∗ g)(j)h(i − j) =
j k
f (k)g(j − k) h(i − j)
=
j k
f (k)g(j − k)h(i − j)
/subst. l = j − k; j = k + l/
=
l k
f (k)g(l)h(i − k − l) =
k
f (k)
l
g(l)h(i − k − l)
=
k
f (k) [(g ∗ h)(i − k)] = (f ∗ (g ∗ h))(i)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 18 / 39
Convolution properties
Separable kernels in 2D
2D kernel g(i, j) is called separable if there exist two 1D vectors grow , gcol
such that:
g = grow ∗ gT
col
Convolution with 2D separable kernel = two consecutive convolutions with
1D kernels:
(f ∗ g)(i, j) = (f ∗ (grow ∗ gcol ))(i, j)
/associativity/
= ((f ∗ grow ) ∗ gcol )(i, j)
Notice: 2D kernel is separable if the rank of its matrix is equal to 1.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 19 / 39
Convolution properties
Separable kernels in 2D
Examples
Gaussian: 

1 2 1
2 4 2
1 2 1

 =


1
2
1

 ∗ 1 2 1
Sobel: 

1 2 1
0 0 0
−1 −2 −1

 =


1
0
−1

 ∗ 1 2 1
There are also separable functions. An example of such function is 2D
Dirac impulse: δ(x, y) = δ(x)δ(y)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 20 / 39
Convolution properties
Linearity & Position invariance
If convolution kernel ’g’ is fixed (which might be valid for optical systems,
for example) then we can write:
f ∗ g = Og (f )
The operator Og is:
linear – given the images f1, f2, and any α, β ∈ R, it holds:
Og (αf1 + βf2) = αOg (f1) + βOg (f2)
position invariant – if h(x) = Og (f (x)) then also
∀y : h(x − y) = Og [f (x − y)]
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 21 / 39
Convolution properties
Convolution theorem
F (f ∗ g) = F(f ) · F(g)
F (f · g) = F(f ) ∗ F(g)
where
F . . . Fourier transform
“·” . . . point-wise multiplication
“∗” . . . convolution
f , g . . . images
Notice: Proof is coming soon.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 22 / 39
Convolution properties
Why is it good to know/understand them?
Commutativity
convolutions can be reordered in random sequence
images becomes convolution kernels, and vice versa
Associativity
parenthesis can be moved without affecting the result
choosing the simpler way of evaluation – different position of
parenthesis may change the complexity
Kernel separability
convolution with 2D kernels . . . O(n2)
convolution with 1D kernels . . . O(n)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 23 / 39
Complex numbers
Any z ∈ C can be written in one
of the following ways:
z = x + iy
z = |z| (cos ϕ + i sin ϕ)
z = |z|eiϕ
where x, y ∈ R and i2 = −1 is a
constant, |z| is a magnitude and
ϕ is a phase of z
Properties:
conjugate complex number:
z = x − iy
x
z = x + iy
z = x − iy
I
R
y
−y
ϕ
ϕ
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 24 / 39
Vector composition
Let be given a Euclidean (K = R) or unitary (K = C) vector space
V ⊆ Kn and three vectors u, v, w ∈ V:
Vector addition: z = u + v + w ∈ V
v
w
z
u
Linear combination of vectors: z = 1
2u + 3v − 2w ∈ V
v
w
u
z
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 25 / 39
Vector decomposition
Let be given Euclidean space V = u1, u2, . . . , un , then each v ∈ V can
be written as:
v = a1u1 + a2u2 + · · · + anun
where
(u1, u2, . . . , un) is the basis of V
∀i = {1, . . . , n} : ai ∈ K
vector (a1, a2, . . . , an) is unique.
Notes:
two vectors u, v ∈ V are orthogonal, if u · v = 0
(’·’ stands to inner product)
basis (u1, u2, . . . , un) is orthonormal, if ∀i, j = 1, . . . , n : ui · uj = δi,j
(δi,j stands for Kronecker delta)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 26 / 39
Vector decomposition
Example
Given Cartesian coordinate system e1, e2, e3 and a vector
v = (3.4, −2, 7), we can write:
v = 3.4e1 − 2e2 + 7e3
where
e1 = (1, 0, 0)
e2 = (0, 1, 0)
e3 = (0, 0, 1)
Question: How to find the (linear combination) coefficients when we do
not project the vector v onto standard basis?
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 27 / 39
Vector decomposition
Conversion to another basis
Given a vector v ∈ V and “any” basis (u1, u2, . . . , un) in V, we can write:
v = a1u1 + a2u2 + · · · + anun
where
∀i = {1, . . . , n} : ai =
v · ui
ui · ui
If the basis is orthonormal, it is sufficient to write: ai = v · ui
Notice: Inner product v · w is a projection v onto w. The result is a
number.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 28 / 39
Vector decomposition
Example
standard basis: e1, e2 = (1, 0), (0, 1)
v e1,e2
= (−1, 3)
another basis: u1, u2 = (−0.7, −0.7), (0.7, −0.7) (0.7
.
=
√
2
2 )
a1 =
(−1, 3) · (−0.7, −0.7)
(−0.7, −0.7) · (−0.7, −0.7)
.
= −1.42
a2 =
(−1, 3) · (0.7, −0.7)
(0.7, −0.7) · (0.7, −0.7)
.
= −2.86
v u1,u2
= (−1.42, −2.86)
v
e1
e2
u1 u2
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 29 / 39
Vector decomposition
Matrix notation
Each orthonormal basis can form a square matrix A:
A =
u1
u2
=
−0.7 −0.7
0.7 −0.7
The projection is realized using matrix multiplication:
v u1,u2
= Av e1,e2
Notice: Transform (mapping) from one basis onto another one is realized
using matrix multiplication ⇒ linear mapping.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 30 / 39
Vector decomposition
matrix notation
Properties of transform matrix A
A is unitary matrix, i.e. A−1 = A
T
.
If y = Ax is forward transform, then x = A−1y = A
T
y is inverse
transform.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 31 / 39
Let us do the same with functions
(n-dimensional vectors)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 32 / 39
Function decomposition
An example
How can we decompose the following function?
-2
0
2
4
6
8
10
12
14
0 2 4 6 8 10
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 33 / 39
Function decomposition
An example
We can express it as the following linear combination:
-2
0
2
4
6
8
10
12
14
0 2 4 6 8 10
f1
f2
f3
f4
f5 = 2f1 - 2f2 + 0.4f3 - f4
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 34 / 39
Function decomposition
Another example
A step function is defined as an infinite sum of sine waves:
fz(m) =
z
n=0
sin {(2n + 1)m}
2n + 1
f3(m) f10(m)
f20(m) f35(m)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 35 / 39
Function decomposition in 1D
Let be a discrete 1D function f of N samples:
f is a point in some N-dim vector space V ⊆ KN (K = R or C)
f can be expressed as a linear combination of basis functions:
f (m) =
N
k=1
akϕk(m)
where ak ∈ K and (ϕ1, ϕ2, . . . , ϕN) form the orthonormal basis
The coefficients of linear combination are found in the common way:
∀k = {1, . . . , N} : ak = f · ϕk
i.e. using the projection (inner product)
Notice: f · ϕk = m f (m)ϕk(m)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 36 / 39
Basis functions
An example of sine & cosine waves sampled with N = 16
Common request:
the basis is orthonormal, i.e. ϕk · ϕl = δk,l
the basis functions for N = 16 are:
ϕk(m) =
1
√
N
e
−2πimk
N =
1
√
N
cos
2πmk
N
− i sin
2πmk
N
0 10
−1
0
1
freq=0
0 10
−1
0
1
freq=1
0 10
−1
0
1
freq=2
0 10
−1
0
1
freq=3
0 10
−1
0
1
freq=4
0 10
−1
0
1
freq=5
0 10
−1
0
1
freq=6
0 10
−1
0
1
freq=7
0 10
−1
0
1
freq=8
0 10
−1
0
1
freq=9
0 10
−1
0
1
freq=10
0 10
−1
0
1
freq=11
0 10
−1
0
1
freq=12
0 10
−1
0
1
freq=13
0 10
−1
0
1
freq=14
0 10
−1
0
1
freq=15
0 5 10 15
−1
0
1
freq=0
0 5 10 15
−1
0
1
freq=1
0 5 10 15
−1
0
1
freq=2
0 5 10 15
−1
0
1
freq=3
0 5 10 15
−1
0
1
freq=4
0 5 10 15
−1
0
1
freq=5
0 5 10 15
−1
0
1
freq=6
0 5 10 15
−1
0
1
freq=7
0 5 10 15
−1
0
1
freq=8
0 5 10 15
−1
0
1
freq=9
0 5 10 15
−1
0
1
freq=10
0 5 10 15
−1
0
1
freq=11
0 5 10 15
−1
0
1
freq=12
0 5 10 15
−1
0
1
freq=13
0 5 10 15
−1
0
1
freq=14
0 5 10 15
−1
0
1
freq=15
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 37 / 39
Bibliography
Gonzalez, R. C., Woods, R. E., Digital image processing / 2nd ed.,
Upper Saddle River: Prentice Hall, 2002, pages 793, ISBN
0201180758
Bracewell, R. N., Fourier transform and its applications / 2nd ed.
New York: McGraw-Hill, pages 474, ISBN 0070070156
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 38 / 39
You should know the answers . . .
What happens if we convolve a function f with Gaussian located
outside the origin?
What is the result when convolving a function f with several δ
impulses?
Under which conditions is the convolution kernel separable?
What is the basis and vector space generated by the given basis?
What are the orthogonal vectors?
What is the orthonormal basis?
How can we simply convert a vector from one basis to another basis?
What is the unitary/orthogonal matrix?
What is the difference between basis vector and basis function?
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 39 / 39