Integral and Discrete Transforms 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 12, 2022
David Svoboda (CBIA@FI) Image Transforms autumn 2022 1 / 37
Outline
1 Introduction
Course rules
Course itinerary
Recommended reading
2 Some revision
Image transforms
Convolution
Impulse symbol
Complex numbers
Vector spaces
David Svoboda (CBIA@FI) Image Transforms autumn 2022 2 / 37
Introduction
Course rules
12 lectures & seminars
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 Python.
The experience from seminars will be useful for completing a small project
written in Python, MATLAB®, 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.
David Svoboda (CBIA@FI) Image Transforms autumn 2022 4 / 37
Introduction
Course itinerary
1 Introduction & Revision
2 Fourier Transform, Spherical Harmonics, Hilbert Transform
3 Principle Component Analysis (PCA), Discrete Cosine Transform (DCT)
4 Singular Value Decomposition (SVD), Independent Component Analysis (ICA)
5 Image Resampling, Texture filtering
6 Z-transform
7 Wavelet Transform
8 Lifting Scheme
9 Recursive Filtering, Steerable Filters
10 Image Restoration
11 Image Compression Methods
12 Image Compression Standards
David Svoboda (CBIA@FI) Image Transforms autumn 2022 5 / 37
Introduction
Recommended reading
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) Image Transforms autumn 2022 6 / 37
Image transforms
Definition
Image transform T is a function that converts the image from one vector
space to another (or the same) vector space.
h = T (f )
f (x) or f (m) . . . input image/signal
h(y) or h(n) . . . output image/signal
T . . . transform
x, y . . . positions in continuous signal
m, n . . . indices addressing the positions in discrete sequences/vectors
David Svoboda (CBIA@FI) Image Transforms autumn 2022 8 / 37
Convolution
Definition
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) Image Transforms autumn 2022 9 / 37
Convolution
Example
1D discrete convolution
31 0
31 0x0 x1x2
input signal kernel
1 1 0 1 0 1 0 2
0 12
flip
output signal
5
Σ
2
David Svoboda (CBIA@FI) Image Transforms autumn 2022 10 / 37
Convolution
Definition
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) Image Transforms autumn 2022 11 / 37
Convolution
Example
2D discrete convolution
23 7
2 1 5
3 03 3
1
11
1 00
00
23 7
2 1 5
3 03
x3
x1
x1x1
x1 x0x0
x0x0
1
14 0
13
2 1
7
0 2
4
1
64
2 2 6
4
50
input image kernel output image
15
Σ
flip
David Svoboda (CBIA@FI) Image Transforms autumn 2022 12 / 37
Convolution
Basic properties
Commutativity:
f ∗ g = g ∗ f
Distributivity:
f ∗ (g + h) = f ∗ g + f ∗ h
Associativity:
(f ∗ g) ∗ h = f ∗ (g ∗ h)
Convolution theorem:
FT(f ) · FT(g) = FT(f ∗ g)
FT(f ) ∗ FT(g) = FT(f · g)
Separability:
2D kernel g is separable ⇔ rank(g) = 1
Notice: Expression ’FT()’ stands for Fourier transform.
David Svoboda (CBIA@FI) Image Transforms autumn 2022 13 / 37
Convolution
Complexity in 2D
Conditions
input image f : M×M → {0, . . . , 2bitdepth}
convolution kernel g : N×N → ⟨0; 1⟩
Standard/Naive 2D discrete convolution
Time: O(M2
N2
)
Space: none required
Usability: Very slow.
2D discrete convolution with separable kernel
Time: O(M2
N)
Space O(M2
)
Usability: Not all PSFs are separable.
Convolution theorem
Time: O((M + N)2
log(M + N))
Space: O((M + N)2
)
Usability: Huge memory requirements.
David Svoboda (CBIA@FI) Image Transforms autumn 2022 14 / 37
Convolution
Memory optimization stategies / Parallelization
”Overlap & Save” scheme
input image output image
discard overlaps
*
overlap
overlap
David Svoboda (CBIA@FI) Image Transforms autumn 2022 15 / 37
Convolution
Memory optimization stategies / Parallelization
”Overlap & Add” scheme
input image output image
do not crop the result
+
+ +
*
David Svoboda (CBIA@FI) Image Transforms autumn 2022 16 / 37
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) Image Transforms autumn 2022 17 / 37
Impulse symbol δ
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) Image Transforms autumn 2022 18 / 37
Impulse symbol δ
Properties
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) Image Transforms autumn 2022 19 / 37
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) Image Transforms autumn 2022 20 / 37
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) Image Transforms autumn 2022 21 / 37
Complex numbers
Be aware of the difference!
φ – phase (of complex number)
I
φ = π
4
R
|z|
I
R
φ = 3π
4
|z|
φ – phase shift (of a function)
David Svoboda (CBIA@FI) Image Transforms autumn 2022 22 / 37
Vectors
Basic properties
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) Image Transforms autumn 2022 23 / 37
Vectors
Basic properties
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) Image Transforms autumn 2022 24 / 37
Vectors
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) Image Transforms autumn 2022 25 / 37
Vectors
Projection to a new 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) Image Transforms autumn 2022 26 / 37
Vectors
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) Image Transforms autumn 2022 27 / 37
Vectors
Example (cont’d)
Each orthonormal basis forms a square matrix:
A =
u1
u2
=
−0.7 −0.7
0.7 −0.7
The projection is therefore realized using matrix multiplication:
v⟨u1,u2⟩ = Av⟨e1,e2⟩
Notice: Transform from one basis onto another one is a linear mapping.
David Svoboda (CBIA@FI) Image Transforms autumn 2022 28 / 37
Vectors
Projection to a new basis
Properties of transform matrices:
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.
The following two sentences express the same:
The vector v is projected into the basis ⟨u1, u2, . . . , un⟩.
The vector v is decomposed into a linear combination of basis vectors
u1, u2, . . . , un
David Svoboda (CBIA@FI) Image Transforms autumn 2022 29 / 37
Decomposition in higher dimensions
Let’s increase the dimensionality: 2-D → 3-D → . . . → N-D
Let V ⊆ KN be a N-dimensional vector space (K = R or C), then the
following terms express the same:
a vector v ∈ V
example: v = (4, 2, 3, 6, −1, 5)
a point p ∈ V
example: p = [4, 2, 3, 6, −1, 5]
a discrete 1D function f , where |f | = N
example: f = {(0, 4), (1, 2), (2, 3), (3, 6), (4, −1), (5, 5)}
Notice: The addition of points/vectors equals to addition of functions.
The same for other well known operations like subtraction, multiplication
by scalar, or linear combination.
David Svoboda (CBIA@FI) Image Transforms autumn 2022 30 / 37
Decomposition in higher dimensions
Example
The discrete function below can be understood as a vector/point in
100-dimensional vector space:
Notice: In higher dimensions, we use rather the concept of functions.
David Svoboda (CBIA@FI) Image Transforms autumn 2022 31 / 37
Decomposition in higher dimensions
Example
The discrete function below can be decomposed into a linear combination
of some simple (well known) functions:
⇒
Notice: Each discrete function can be decomposed in this manner.
David Svoboda (CBIA@FI) Image Transforms autumn 2022 32 / 37
Decomposition in higher dimensions
Another example
A step function (red color) 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) Image Transforms autumn 2022 33 / 37
Decomposition in higher dimensions
Let be a discrete 1D function f of N samples:
f can be uniquely expressed as a linear combination of basis functions
φ1, φ2, . . . , φN:
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 as:
∀k = {1, . . . , N} : ak = f · φk
i.e. using the projection (inner/dot product)
Notice: f · φk = m f (m)φk(m)
David Svoboda (CBIA@FI) Image Transforms autumn 2022 34 / 37
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) Image Transforms autumn 2022 35 / 37
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) Image Transforms autumn 2022 36 / 37
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) Image Transforms autumn 2022 37 / 37