Filters in Image Processing
Fourier transform in two dimensions & (Re)sampling
David Svoboda
email: svoboda@fi.muni.cz
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno, CZ
September 26, 2019
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 1 / 57
Outline
1 Fourier transform (2D)
Discrete
Continuous
Theorems & Properties
2 Sampling
Nyquist-Shannon theorem
Aliasing
Reconstruction
3 Resampling in 1D
Design of an ideal resampling filter
4 Resampling in 2D
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 2 / 57
1 Fourier transform (2D)
Discrete
Continuous
Theorems & Properties
2 Sampling
Nyquist-Shannon theorem
Aliasing
Reconstruction
3 Resampling in 1D
Design of an ideal resampling filter
4 Resampling in 2D
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 3 / 57
2D Fourier Transform (discrete)
Definition
Given 2D discrete function f of (M, N) samples and two bases
(ϕk, k = {0, . . . , M − 1}) and (ϕl , l = {0, . . . , N − 1}), let us define:
forward 2D discrete Fourier transform:
F(k, l) ≡
1
√
MN
M−1
m=0
N−1
n=0
f (m, n)e−2πi(mk
M
+nl
N )
inverse 2D discrete Fourier transform:
f (m, n) ≡
1
√
MN
M−1
k=0
N−1
l=0
F(k, l)e2πi(mk
M
+nl
N )
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 4 / 57
2D Fourier Transform
Separability
The evaluation of 2D-(D)FT can be decomposed into two simpler tasks:
F(k, l) =
1
√
MN
M−1
m=0
N−1
n=0
f (m, n)e−2πi(mk
M
+nl
N )
=
1
√
N
N−1
n=0
1
√
M
M−1
m=0
f (m, n)e−2πimk
M e−2πinl
N
=
1
√
N
N−1
n=0
F(k, n)e−2πinl
N
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 5 / 57
Question
Let us have an image with dimensions M × N (M and N are powers of 2).
As we want to apply discrete cosine transform (Fourier transform) to
implement JPEG compression, we would like to know the efficiency of this
process.
What is the complexity:
when doing straightforward (naive) evaluation of DFT?
when we utilize separability of FT and FFT?
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 6 / 57
2D Fourier Transform (continuous)
Definition
Given 2D integrable function f and two bases (ϕωx , ωx ∈ R) and
(φωy , ωy ∈ R), let us define:
forward 2D continuous Fourier transform
F(ωx , ωy ) ≡
∞
−∞
∞
−∞
f (x, y)e−2πi(xωx +yωy )
dxdy
inverse 2D continuous Fourier transform
f (x, y) ≡
∞
−∞
∞
−∞
F(ωx , ωy )e2πi(xωx +yωy )
dωx dωy
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 7 / 57
2D Discrete Fourier Transform Properties
All the properties from 1D DFT are valid:
scaling
shift
repetition
convolution theorem
There are some more properties:
separability
rotation
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 8 / 57
2D DFT
Scaling
−2
0
2 −2
0
2
0.2
0.4
0.6
0.8
1
y
Gaussian
x
f(x,y)
−2
0
2 −2
0
2
1
2
3
4
5
6
ωy
FT of Gaussian
ωx
F(ωx
,ωy
)
x
y
Gaussian
−2 0 2
−3
−2
−1
0
1
2
3
ωx
ωy
FT of Gaussian
−2 0 2
−3
−2
−1
0
1
2
3
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 9 / 57
2D DFT
Scaling
−1
0
1 −1
−0.5
0
0.5
10
0.2
0.4
0.6
0.8
1
y
Gaussian
x
f(x,y)
−1
0
1 −1
−0.5
0
0.5
10
0.1
0.2
0.3
0.4
ωy
FT of Gaussian
ωx
F(ωx
,ωy
)
x
y
Gaussian
−1 −0.5 0 0.5 1
−1
−0.5
0
0.5
1
ωx
ωy
FT of Gaussian
−1 −0.5 0 0.5 1
−1
−0.5
0
0.5
1
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 10 / 57
2D DFT
Scaling
−2
0
2 −2
−1
0
1
2
0.2
0.4
0.6
0.8
1
y
Gaussian
x
f(x,y)
−2
0
2 −2
−1
0
1
2
0.2
0.4
0.6
0.8
1
1.2
1.4
ωy
FT of Gaussian
ωx
F(ωx
,ωy
)
x
y
Gaussian
−2 −1 0 1 2
−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
ωx
ωy
FT of Gaussian
−2 −1 0 1 2
−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 11 / 57
2D DFT
Scaling
−5
0
5−5
0
50
0.2
0.4
0.6
0.8
1
y
Π function
x
f(x,y)
−5
0
5−5
0
50
1
2
3
x 10
−28
ωy
Sinc
ωx
F(ωx
,ωy
)
x
y
Π
−5 0 5
−5
0
5
ωx
ωy
Sinc
−5 0 5
−5
0
5
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 12 / 57
2D DFT
Scaling
−4
−2
0
2
−4
−2
0
2
0
0.2
0.4
0.6
0.8
1
y
Π function
x
f(x,y)
−4
−2
0
2
−4
−2
0
2
−0.05
0
0.05
0.1
0.15
0.2
ωy
Sinc
ωx
F(ωx
,ωy
)
x
y
Π
−4 −2 0 2
−4
−3
−2
−1
0
1
2
3
ωx
ωy
Sinc
−4 −2 0 2
−4
−3
−2
−1
0
1
2
3
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 13 / 57
2D DFT
Repetition
f(x,y)=x+y
5 10 15
5
10
15
Fourier Transform (amplitude)
5 10 15
5
10
15
f(x,y) stretched by factor 2
5 10 15
5
10
15
Fourier Transform (amplitude)
5 10 15
5
10
15
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 14 / 57
2D DFT
Convolution theorem
Input image "I" Convolution kernel "G" I * G
log(|FT(I)|) log(|FT(G)|) log(|FT(I)FT(G)|)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 15 / 57
2D DFT
Rotation
Input image "I" |FT(I)|
rotated I |FT(rotated I)|
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 16 / 57
2D DFT
Rotation
Let us introduce the polar coordinates:
x = r cos φ
y = r sin φ
ωx = R cos ψ
ωy = R sin ψ
Then
f (x, y) → f (r, φ)
F(ωx , ωy ) → F(R, ψ)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 17 / 57
2D DFT
Rotation
It is now clear to see that:
f (r, φ + φ0) ⊃ F(R, ψ + φ0)
Conclusion: Rotating f (x, y) by an angle φ0 rotates F(ωx , ωy ) by the
same angle, and vice versa.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 18 / 57
1 Fourier transform (2D)
Discrete
Continuous
Theorems & Properties
2 Sampling
Nyquist-Shannon theorem
Aliasing
Reconstruction
3 Resampling in 1D
Design of an ideal resampling filter
4 Resampling in 2D
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 19 / 57
Comb function
In 1D space
III(x) =
∞
n=−∞
δ(x − n)
x
Notice: “III” is pronouced as shah (Cyrilic character).
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 20 / 57
Comb function
Some properties
III(−x) = III(x)
III(x + n) = III(x)
III(x − 1
2) = III(x + 1
2)
III(x) = 0 x = n
III(ax) = 1
|a| δ(x − n
a )
III(x
τ ) ⊃ τIII(τω)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 21 / 57
Comb function
In 2D space
2
III(x, y) =
∞
m=−∞
∞
n=−∞
δ(x − m, y − n)
x
y
z
Separability of delta function implies:
2
III(x, y) = III(x)III(y)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 22 / 57
Sampling
Sampling = the process of converting a continuous signal into a discrete
sequence.
In 1D:
III(x)f (x) =
∞
n=−∞
f (n)δ(x − n)
In 2D:
2
III(x, y)f (x, y) =
m n
f (m, n)δ(x − m, y − n)
Question: What happens in frequency (Fourier) domain?
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 23 / 57
Sampling
Comparison of image and Fourier domain
Image/Time domain:
multiplication of the function f and III
sampling
Fourier domain:
convolution of the function FT(f ) and FT(III)
convolution with Dirac impulses causes replication of FT(f )
scaling property is also valid for III function
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 24 / 57
Sampling
x
f(x)
u
x u
III(x/t) t III(tu)
F(u)
1/t
max frequency
Notice: The comb function density must be high enough to guarantee
proper sampling
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 25 / 57
Sampling
III(x/t)f(x)
x
x u
u
u
t III(tu)*F(u)
x
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 26 / 57
Nyquist-Shannon theorem
Exact reconstruction of a continuous signal from its samples is possible if
the signal is bandlimited and the sampling frequency is greater than twice
the signal maximal frequency
Harry Nyquist (1889 – 1976) & Claude Elwood Shannon (1916 – 2001)
Question: How to use N-S theorem, if the original signal is unlimited?
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 27 / 57
Sampling
Common problems – aliasing
The cause of aliasing:
when Nyquist-Shannon condition is broken, i.e.
sampling frequency is not high enough or
(time alias – wagon wheel effect)
the signal in not bandlimited
(PC games – far horizon)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 28 / 57
Sampling
Common problems – aliasing
An example
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 29 / 57
Sampling
Common problems – aliasing
An example
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 30 / 57
Sampling
Common problems – aliasing
How to eliminate aliasing?
sampling at higher frequency
does it help if the signal is not band limited?
expensive for memory and time
OR
prefiltering
before sampling the input signal is “prefiltered” by lowpass filter
prefilter sampling
continuouscontinuous discrete
bandlimited
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 31 / 57
Sampling
Common problems – aliasing
Some lowpass filters
Gaussian filter
fσ(x) =
1
σ
√
2π
e− x2
2σ2
Sinc filter
f (x) =
sin(x)
x
B-spline filter
b1(x) =
1 |x| ≤ 1/2
0 |x| > 1/2
bn(x) = b1(x) ∗ b1(x) ∗ · · · ∗ b1(x) n-times
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 32 / 57
Reconstruction
Inverse process to sampling
The purpose: reconstruction of the original continuous signal from the
sampled sequence.
Reconstruction ≡ convolution with a low-pass filter.
Common reconstruction filters:
box (nearest neighbour)
tent (linear interpolation)
cubic B-spline (cubic polynomial interpolation)
Gaussian
sinc function
Lanczos (windowed sinc function)
Notice: The unit area under the curve.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 33 / 57
Reconstruction
Lanczos filter
−4 −3 −2 −1 0 1 2 3 4
−0.2
0
0.2
0.4
0.6
0.8
1
1.2
Lanczos3
lanczos3(x) =
sin πx
πx
sin π x
3
π x
3
|x| < 3
0 |x| ≥ 3
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 34 / 57
Reconstruction
Examples of reconstruction
Box filter
↔
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 35 / 57
Reconstruction
Examples of reconstruction
Tent filter
↔
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 36 / 57
Reconstruction
Examples of reconstruction
Cubic B-spline filter
↔
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 37 / 57
1 Fourier transform (2D)
Discrete
Continuous
Theorems & Properties
2 Sampling
Nyquist-Shannon theorem
Aliasing
Reconstruction
3 Resampling in 1D
Design of an ideal resampling filter
4 Resampling in 2D
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 38 / 57
Resampling in 1D
Let us design a 1D resampling filter
The filter should be easy to implement and fast for computation.
The filter should solve the alias problem.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 39 / 57
Resampling in 1D
Design of the resampling filter
1 reconstruct the continuous signal from the discrete one
2 warp the domain of the continuous signal
3 prefilter the warped, continuous signal
4 sample this signal to produce the discrete output signal
m
f(m)
reconstruct
u
warp
reconstructed inputdiscrete input
h(u)
prefilter
warped input
h’(x)
x
continuous output
x
sample
g(n)h’’(x)
discrete output
n
f (m) . . . discrete input signal
r(u) . . . reconstruction filter
h(u) = (f ∗ r)(u) = k f (k)r(u − k) . . . reconstructed input signal
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 40 / 57
Resampling in 1D
Design of the resampling filter
1 reconstruct the continuous signal from the discrete one
2 warp the domain of the continuous signal
3 prefilter the warped, continuous signal
4 sample this signal to produce the discrete output signal
m
f(m)
reconstruct
u
warp
reconstructed inputdiscrete input
h(u)
prefilter
warped input
h’(x)
x
continuous output
x
sample
g(n)h’’(x)
discrete output
n
h (x) = h(u) = h(γ−1(x)) . . . warped signal
x = γ(u) . . . mapping from one coordinate system to another one
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 40 / 57
Resampling in 1D
Design of the resampling filter
1 reconstruct the continuous signal from the discrete one
2 warp the domain of the continuous signal
3 prefilter the warped, continuous signal
4 sample this signal to produce the discrete output signal
m
f(m)
reconstruct
u
warp
reconstructed inputdiscrete input
h(u)
prefilter
warped input
h’(x)
x
continuous output
x
sample
g(n)h’’(x)
discrete output
n
h (x) = (h ∗ p)(x) = h (t)p(x − t)dt . . . prefiltered signal
p(x) . . . (lowpass) prefilter
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 40 / 57
Resampling in 1D
Design of the resampling filter
1 reconstruct the continuous signal from the discrete one
2 warp the domain of the continuous signal
3 prefilter the warped, continuous signal
4 sample this signal to produce the discrete output signal
m
f(m)
reconstruct
u
warp
reconstructed inputdiscrete input
h(u)
prefilter
warped input
h’(x)
x
continuous output
x
sample
g(n)h’’(x)
discrete output
n
g(n) = h (x)III(x) . . . discrete output signal
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 40 / 57
Resampling in 1D
Important (implementation) notes
During the resampling process we actually never construct a
continuous signal h(u), h (x) or h (x).
We pick up the individual positions in the resampled image g(n) and
look for their corresponding positions and their neighbourhood in the
original image f (m).
As the computation is inverted, we never use γ function.
We use only γ−1.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 41 / 57
Resampling in 1D
Derivation of an ideal resampling filter
Computation of one sample point
g(n) = h (n) = h (t)p(n − t)dt
= h(γ−1
(t))p(n − t)dt
= p(n − t)
k
f (k)r(γ−1
(t) − k)dt =
k
f (k)ρ(n, k)
where
ρ(n, k) = p(n − t)r(γ−1
(t) − k)dt
ρ(n, k) is called a resampling filter.
If γ is affine, we can derive: ρ(n, k) = p(γ−1(n) − k) ∗ r(γ−1(n) − k).
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 42 / 57
Resampling in 1D
Practical problems
If the mapping γ is not affine, the filter ρ(m, k) is space variant.
Solution (postfiltering/supersampling)
1 Reconstruct the continuous signal from the discrete input signal.
2 Warp the domain of the input signal.
3 Sample the warped signal at very high resolution to avoid alias.
4 Postfilter the signal to produce a lower resolution output signal.
Notice: The convolution is employed in the very end of this algorithm, i.e.
it is discrete and space invariant.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 43 / 57
Resampling in 1D
Practical problems
If the mapping γ is not affine, the filter ρ(m, k) is space variant.
Solution (postfiltering/supersampling)
1 Reconstruct the continuous signal from the discrete input signal.
2 Warp the domain of the input signal.
3 Sample the warped signal at very high resolution to avoid alias.
4 Postfilter the signal to produce a lower resolution output signal.
Notice: The convolution is employed in the very end of this algorithm, i.e.
it is discrete and space invariant.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 43 / 57
1 Fourier transform (2D)
Discrete
Continuous
Theorems & Properties
2 Sampling
Nyquist-Shannon theorem
Aliasing
Reconstruction
3 Resampling in 1D
Design of an ideal resampling filter
4 Resampling in 2D
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 44 / 57
Resampling in 2D
Task
Design a 2D resampling filter
Obey the rules that are valid for 1D resampling filter.
The filter maps texels from texture space to screen space.
The filter might be anisotropic.
The filter should work fast.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 45 / 57
Resampling in 2D
γ-mapping
Basic properties of γ-mapping
γ converts coordinates from screen space to texture space.
γ is projective (neither linear nor affine).
Circular neighbourhood of one pixel (in screen space) is transformed
into ellipse (in texture space).
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 46 / 57
Resampling in 2D
γ-mapping
Approximation of γ-mapping
Let us approximate γ in the neighbourhood of u0 as the locally-affine
mapping:
γ(u) = u0 + Ju0 (u − u0)
where Ju0 is Jacobian and u = (u, v) is 2D vector in texture space.
Construction of ellipse in texture space
The major and minor axis determining the ellipse shape correspond to
partial derivatives of γ in the position u0, i.e. the rows of matrix Ju0 :
Ju0 =
∂u
∂x
∂u
∂y
∂v
∂x
∂v
∂y
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 47 / 57
Resampling in 2D
γ-mapping
Construction of ellipse in texture space (continued)
v
2
0u =(u ,v )0 0
u
Au + Buv + Cv = F2
F
A =
∂v
∂x
2
+
∂v
∂y
2
B = −2
∂u
∂x
∂v
∂x
+
∂u
∂y
∂v
∂y
C =
∂u
∂x
2
+
∂u
∂y
2
F =
∂u
∂x
∂v
∂y
−
∂u
∂y
∂v
∂x
2
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 48 / 57
Resampling in 2D
γ-mapping
Image Pyramids (MIP map)
Size of ellipse determines level of detail in MIP map pyramid that
should be fetched from the memory.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 49 / 57
Resampling in 2D
Computation in texture space
Collecting pixels from texture space:
1 Create the Gaussian with the elliptical support.
2 Attach the Gaussian to the texture image loaded from the MIP map
pyramid.
3 Sum up the image pixels by using the Gaussian weights.
0
0
100
10
0
200
20
10
300
30 20
400
40 30
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 50 / 57
Resampling in 2D
Elliptical Weighted Average (EWA)
Implementation Notes
For each image pixel (x,y) from screen space:
1 Find corresponding point (u,v) in texture space.
2 Define the local affine transform γ.
3 Compute Jacobian J of this mapping.
4 Delineate the ellipse in texture space.
5 Using the ellipse size choose the appropriate MIP map level.
6 Build the Gaussian over the ellipse.
7 Evaluate direct convolution of MIP map image with Gaussian.
8 Store the result (one value) in the screen pixel (x,y).
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 51 / 57
Resampling in 2D
EWA – Properties
EWA fullfills the requirements applied to optimal resampling filter
g(n) =
k
f (k)ρ(n, k)
where
ρ(n, k) = p(γ−1
(n) − k) ∗ r(γ−1
(n) − k)
γ is locally affine: prefilter p and reconstruction filter r are Gaussians.
Their convolution is again Gaussian.
γ is locally affine: p and r have elliptical support. The product of
their convolution has also elliptical support, as the ellipses are closed
under affine transforms.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 52 / 57
Resampling in 2D
EWA – Technical Notes
The quality of filtering corresponds to the resampling filter support
Anisotropic filtering 1× . . . 8 texels (pixels from texture space)
Anisotropic filtering 2× . . . 16 texels
Anisotropic filtering 4× . . . 32 texels
Anisotropic filtering 8× . . . 64 texels
Anisotropic filtering 16× . . . 128 texels
Higher the quality ⇒ higher the computational cost (GPU usage)
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 53 / 57
Resampling in 2D
EWA – An Example
Texture filtering with naive MIP map (on the left) and anisotropic filtering
with so called EWA based method (on the right)
source: wikipedia.org
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 54 / 57
Resampling in 2D
EWA – An Example
Texture filtering with naive MIP map
source: shinvision.com
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 55 / 57
Resampling in 2D
EWA – An Example
Texture filtering with so called EWA based method
source: shinvision.com
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 55 / 57
Bibliography
1 Bracewell, R. N., Fourier transform and its applications / 2nd ed. New York:
McGraw-Hill, p 474. ISBN 0070070156
2 Paul Heckbert, Fundamentals of Texture Mapping and Image Warping,
Master’s thesis, UCB/CSD 89/516, CS Division, U.C. Berkeley, June 1989,
86 pp
3 Turkowski, K. Filters for common resampling tasks. In Graphics Gems, A. S.
Glassner, Ed. Academic Press Professional, San Diego, CA, 147-165, 1990
4 McCormack, J., Perry, R.N., Farkas, K.I.; Jouppi, N.P. ”Feline: Fast
Elliptical Lines for Anisotropic Texture Mapping”, ACM SIGGRAPH, pp
243-250, August 1999
5 Pharr, M., Humphreys, G. Physically Based Rendering: From Theory to
Implementation. Morgan Kaufmann Publishers Inc., San Francisco, CA,
USA, 2004
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 56 / 57
You should know the answers . . .
Show that the 2D DFT is separable transform.
Derive the complexity of 2D discrete FFT.
Explain the reciprocity of wide and narrow shapes in time and
frequency domain, respectively.
Derive (dot not formulate) the Nyquist-Shannon theorem for 2D
image data.
Show an example of the aliasing effect.
What is a prefilter?
What is the difference between a screen space and texture space?
Give an example of γ warping function both for 1D and 2D case.
What is the difference between projective and affine mappings?
Describe individual steps of EWA filter.
David Svoboda (CBIA@FI) Filters in Image Processing autumn 2019 57 / 57