Image Processing,
Retrieval, and Analysis (I)
Prof. Christian Bauckhage
Outline
Lecture 20
Recap
Warping and Interpolation
Warping
1D Interpolation
2D Interpolation
Artistic Image Effects
Fisheye Effect
Waves Effect
Swirl Effect
Summary
Recap
warp function
I a warp function is a transformation T that alters the geometry of
an image, i.e.
g̃(x) = g̃ T(u) = g(u)
example
y
v
u x
the function g(u) the function g̃(T(u)) = g̃(x)
Warping and Interpolation
forward (PUSH) warps
I iterate over the pixels of the source image
I map their intensities to the corresponding
coordinates in the destination image
T
Warping and Interpolation
forward (PUSH) warps
I iterate over the pixels of the source image
I map their intensities to the corresponding
coordinates in the destination image
problem
I this method leapfrogs coordinates in the destination image
Warping and Interpolation
example
Warping and Interpolation
backward (PULL) warps
I exploit the fact that
u = T −1 (x)
I iterate over the pixels of the new image and read
the corresponding intensity or color values from
the original image
−1
T
Warping and Interpolation
example
Warping and Interpolation
interpolation (of 1D functions)
I given a discrete 1D function f with values f [xi ] at sample points xi
Warping and Interpolation
interpolation (of 1D functions)
I given a discrete 1D function f with values f [xi ] at sample points xi
we are looking for a continuous function f̂ (x) that approximates
values at points x in between consecutive sample points, i.e.
xi 6 x 6 xi+1
150 150
f (x)
100 100 f [xi ]
50 50
0 0
0 2 4 6 8 10 0 2 4 6 8 10
-50 -50
-100 -100
discrete f [xi ] continuous f (x) = sin(2x) · x2
Warping and Interpolation
nearest-neighbor interpolation
I round x to the closest sample point
f̂ (x) = f [xk ], where xk = argmin | x − xj |
xj ∈{xi ,xi+1 }
150
f (x)
100 fˆ(x)
f [xi ]
50
0
0 2 4 6 8 10
-50
-100
nn-interpolation
Warping and Interpolation
linear interpolation
I assume f̂ to be piecewise linear
f [xi+1 ] − f [xi ]
f̂ (x) = f [xi ] + (x − xi ) ·
xi+1 − xi
150
f (x)
100 fˆ(x)
f [xi ]
50
0
0 2 4 6 8 10
-50
-100
linear interpolation
Warping and Interpolation
interpolation using Lagrange polynomials
I approximate f̂ (x) using Lagrange polynomials
X
n X
n Y x − xk
f̂ (x) = f [xi ] Li (x) = f [xi ]
xi − xk
i=0 i=0 k6=i
150
f (x)
100 fˆ(x)
f [xi ]
50
0
0 2 4 6 8 10
-50
-100
Lagrange interpolation
Warping and Interpolation
cubic spline interpolation
I piecewise approximate f̂ (x) using cubic polynomials φi (x)
φ1 (x), if x1 6 x 6 x2
φ2 (x), if x2 6 x 6 x3
f̂ (x) = .
..
φn−1 (x), if xn−1 6 x 6 xn
where
φi (x) = ai (x − xi )3 + bi (x − xi )2 + ci (x − xi ) + di
for i = 1, 2, . . . , n − 1
Warping and Interpolation
cubic spline interpolation
150
f (x)
100 fˆ(x)
f [xi ]
50
0
0 2 4 6 8 10
-50
-100
Warping and Interpolation
cubic spline interpolation
φi+1(x)
φi (x)
φi−1 (x)
xi−1 xi xi+1 xi+2
Warping and Interpolation
cubic spline interpolation
I to determine the coefficients ai , bi , ci , di , consider
φi (x) = ai (x − xi )3 + bi (x − xi )2 + ci (x − xi ) + di
φi0 (x) = 3ai (x − xi )2 + 2bi (x − xi ) + ci
φi00 (x) = 6ai (x − xi ) + 2bi
I smoothness requirements / constraints
f̂ (xi ) = f [xi ] (1)
φi (xi+1 ) = φi+1 (xi+1 ) (2)
φi0 (xi+1 ) = 0
φi+1 (xi+1 ) (3)
φi00 (xi+1 ) = 00
φi+1 (xi+1 ) (4)
Warping and Interpolation
cubic spline interpolation
xi−1 xi xi+1 xi+2 xi−1 xi xi+1 xi+2 xi−1 xi xi+1 xi+2
pathology 1 pathology 2 pathology 3
I (1) and (2) prevent pathology 1
I (3) prevents pathology 2
I (4) enforces solutions smoother than pathology 3
Warping and Interpolation
cubic spline interpolation
I next, we assume (for simplicity) that all sample points are equidistant
xi+1 − xi = h ∀i (5)
I from (1), we have
f [xi ] = f̂ (xi ) = φi (xi ) = ai (xi −xi )3 +bi (xi −xi )2 +ci (xi −xi )+di = di (6)
I together with (2), this provides
φi (xi+1 ) = φi+1 (xi+1 ) = di+1
I using
φi (xi+1 ) = ai (xi+1 − xi )3 + bi (xi+1 − xi )2 + ci (xi+1 − xi ) + di
= φi+1 (xi+1 ) = di+1
we find (by means of (5))
di+1 = ai h3 + bi h2 + ci h + di (7)
Warping and Interpolation
cubic spline interpolation
I in analogy, we have from (3)
φi0 (xi+1 ) = 3ai (xi+1 − xi )2 + 2bi (xi+1 − xi ) + ci
0
= φi+1 (xi+1 ) = ci+1
which is to say that
ci+1 = 3ai h2 + 2bi h + ci (8)
I again in analogy, we have from (4)
φi00 (xi+1 ) = 6ai (xi+1 − xi ) + 2bi
00
= φi+1 (xi+1 ) = 2bi+1
which is to say that
2bi+1 = 6ai h + 2bi (9)
Warping and Interpolation
cubic spline interpolation
I next, we substitute (for readability only)
Mi
Mi = 2bi ⇔ bi = (10)
2
I then, becomes
6ai h = 2bi+1 − 2bi = Mi+1 − Mi
Mi+1 − Mi
⇔ ai = (11)
6h
Warping and Interpolation
cubic spline interpolation
I using (12) and (11), we rewrite (7) and obtain
f [xi+1 ] − f [xi ] Mi+1 + 2Mi
ci = − h
h 6
I all in all, we have so far
Mi+1 − Mi
ai =
6h
Mi
bi =
2
f [xi+1] − f [xi ] Mi+1 + 2Mi
ci = − h
h 6
di = f [xi ]
Warping and Interpolation
cubic spline interpolation
I therefore, if we knew the Mi , we could compute the φi (x) and thus f̂ (x)
I the key to determining the Mi lies in (8)
I inserting all the above expressions into ci+1 = 3ai h2 + 2bi h + ci yields
Mi+1 − Mi 2 Mi f [xi+1 ] − f [x1 ] Mi+1 + 2Mi
3 h +2 h+ − h
6h h h 6
f [xi+2 ] − f [xi+1 ] Mi+2 + 2Mi+1
= − h (12)
h 6
Warping and Interpolation
cubic spline interpolation
I after some straightforward algebra
6
Mi + 4Mi+1 + Mi+2 = f [x i ] − 2f [xi+1 ] + f [x i+2 ]
h2
for i = 1, 2, . . . , n − 2
I in matrix form (assuming M1 = Mn = 0)
4 1 0 ··· 0 0 0 f [x1 ] − 2f [x2 ] + f [x3 ]
M2
1 4 1 ··· 0 0 0 M3 f [x2 ] − 2f [x3 ] + f [x4 ]
···
0 1 4 0 0 0 M4 f [x3 ] − 2f [x4 ] + f [x5 ]
.
.. .. .. .. .. .. .. =
6
..
..
. . . . . . . h2
.
0
0 0 ··· 4 1 0 Mn−3
f [xn−4 ] − 2f [xn−3 ] + f [xn−2 ]
0 0 0 ··· 1 4 1 Mn−2 f [x ] − 2f [x ] + f [x ]
n−3 n−2 n−1
0 0 0 ··· 0 1 4 Mn−1 f [xn−2 ] − 2f [xn−1 ] + f [xn ]
Warping and Interpolation
Question:
I why do we consider cubic interpolation polynomials?
Warping and Interpolation
Question:
I why do we consider cubic interpolation polynomials?
Answer:
I consider, for example, the continuous quadratic function
−x2 , if x < 0
f (x) =
x2 , if x > 0
as well as its first and second derivatives f 0 (x) and f 00 (x),
respectively
Warping and Interpolation
Answer (cont.):
I while the first derivative 8
4
0 −2x, if x < 0
f (x) =
2x, if x > 0 0
-8 -4 0 4 8
is continuous, too, . . . -4
f (x)
f ′ (x)
f ′′ (x)
-8
Warping and Interpolation
Answer (cont.):
I while the first derivative 8
4
0 −2x, if x < 0
f (x) =
2x, if x > 0 0
-8 -4 0 4 8
is continuous, too, . . . -4
f (x)
f ′ (x)
I . . . the second derivative -8
f ′′ (x)
−2, if x < 0
f 00 (x) =
2, if x > 0
has a jump discontinuity at 0
Warping and Interpolation
Answer (cont.):
⇒ for functions composed of quadratic polynomials, we
cannot guarantee that they are twice continuously
differentiable
I yet, continuity of the second derivative is essential for
the smoothness demands we incorporated in our
discussion above
Warping and Interpolation
interpolation of 2D Functions
I given: a discrete, 2D function g that assigns values
g[ui , vi ] to coordinates (ui , vi )
Warping and Interpolation
interpolation of 2D Functions
I given: a discrete, 2D function g that assigns values
g[ui , vi ] to coordinates (ui , vi )
I desired: an approximation ĝ(u, v) of the value at point
(u, v) which is situated in between four sample points
ui 6 u 6 ui+1
∧ vi 6 v 6 vi+1
Warping and Interpolation
nearest-neighbor interpolation
I extension of the known approach to the case of 2D data
ĝ(u, v) = g[uk , vl ]
where
(uk , vl ) = argmin
(u, v) − (ui , vj )
i, j
Warping and Interpolation
bilinear interpolation
I extension of the simple 1D approach to 2D data
I can be broken down into three steps . . .
Warping and Interpolation
bilinear interpolation
I extension of the simple 1D approach to 2D data
I can be broken down into three steps . . .
I first:
Warping and Interpolation
bilinear interpolation
I extension of the simple 1D approach to 2D data
I can be broken down into three steps . . .
I second:
Warping and Interpolation
bilinear interpolation
I extension of the simple 1D approach to 2D data
I can be broken down into three steps . . .
I third:
Warping and Interpolation
bilinear interpolation in digital image processing (I)
I it is impossible to approximate function values at
coordinates (u, v) outside of the domain of g, i.e.
ĝ(u, v) = undef, if u < 0 ∨ u > cmax ∨ v < 0 ∨ v > rmax
Warping and Interpolation
bilinear interpolation in digital image processing (I)
I it is impossible to approximate function values at
coordinates (u, v) outside of the domain of g, i.e.
ĝ(u, v) = undef, if u < 0 ∨ u > cmax ∨ v < 0 ∨ v > rmax
I using the PULL method in image warping, it can
generally not be guaranteed that
u = T −1 (x)
lies inside of the domain of the original image g
Warping and Interpolation
bilinear interpolation in digital image processing (I)
I it is impossible to approximate function values at
coordinates (u, v) outside of the domain of g, i.e.
ĝ(u, v) = undef, if u < 0 ∨ u > cmax ∨ v < 0 ∨ v > rmax
I using the PULL method in image warping, it can
generally not be guaranteed that
u = T −1 (x)
lies inside of the domain of the original image g
I for corresponding coordinates x in the warped image g̃,
we thus cannot compute a suitable intensity or color
Warping and Interpolation
bilinear interpolation in digital image processing (II)
I since the coordinates of sample points are given in terms
of integers, it is sufficient to refer to the sample points just
using their index value; i.e. instead of (ui , vj ) we simply
write (i, j)
Warping and Interpolation
bilinear interpolation in digital image processing (II)
I since the coordinates of sample points are given in terms
of integers, it is sufficient to refer to the sample points just
using their index value; i.e. instead of (ui , vj ) we simply
write (i, j)
I then, however, we have:
ui+1 − ui → i + 1 − i = 1
and
vj+1 − vj → j + 1 − j = 1
respectively
Warping and Interpolation
bilinear interpolation in digital image processing (III)
I since i 6 u 6 i + 1 and j 6 v 6 j + 1 this yields
i = buc, i + 1 = due
as well as
j = bvc, j + 1 = dve
i.e. the coordinates of the pixels which surround u can be
easily determined by means of ceiling or flooring u and v
Warping and Interpolation
bicubic spline interpolation
I for bicubic interpolation, we do not merely consider the
immediate neighbors surrounding coordinate (u, v)
Warping and Interpolation
bicubic spline interpolation
I for bicubic interpolation, we do not merely consider the
immediate neighbors surrounding coordinate (u, v)
I rather, 16 pixels from the 4 × 4 neighborhood of (u, v)
are taken into account
Warping and Interpolation
bicubic spline interpolation
I first, 4 splines are computed along the v-axis
Warping and Interpolation
bicubic spline interpolation
I these allow for computing values at (i − 1, v), (i, v),
(i + 1, v), and (i + 2, v)
Warping and Interpolation
bicubic spline interpolation
I through these another spline is fit . . .
Warping and Interpolation
bicubic spline interpolation
I which finally allows for estimating a value at (u, v)
Warping and Interpolation
comparison of the three methods
I nearest neighbor interpolation
Warping and Interpolation
comparison of the three methods
I bilinear interpolation
Warping and Interpolation
comparison of the three methods
I bicubic spline interpolation
Artistic Image Effects
fisheye / lens effect
I enlarge a part of an image as if it was viewed through a
magnifying glass
example
Artistic Image Effects
approach (1D)
g(u)
g̃(x)
Artistic Image Effects
approach (1D)
g(u)
g̃(x)
Artistic Image Effects
approach (1D)
I we consider a warp functionT to the effect
g̃(x̃) = g T(x)
Artistic Image Effects
approach (1D)
I we consider a warp functionT to the effect
g̃(x̃) = g T(x)
I with x > 0 denoting the distance to the center point
of the (virtual) magnifying glass, we require that
T(x) ' x, if x is large
and
T(x) < x, if x is small
Artistic Image Effects
example
20
1
15 0.8
0.6
10
0.4
5 id(x) 2 /32
T (x) 0.2 1 − e−x
0 0
0 5 10 15 20 0 5 10 15 20
Artistic Image Effects
approach (1D)
I that is
Artistic Image Effects
approach (1D)
I that is
either something has to be added to x which is negative for small
x and which equals 0 for large x
Artistic Image Effects
approach (1D)
I that is
either something has to be added to x which is negative for small
x and which equals 0 for large x
or something has to be multiplied to x which is smaller than 1
for small x and which equals 1 for large x
Artistic Image Effects
approach (1D)
I that is
T(x) = x + δ+ (x)
or
T(x) = x · δ· (x)
Artistic Image Effects
approach (1D)
I for instance, we may choose
x2
δ· (x) = 1 − e− 2σ2
Artistic Image Effects
approach (1D)
I for instance, we may choose
x2
δ· (x) = 1 − e− 2σ2
I interestingly
x2 x2
x · δ· (x) = x · (1 − e− σ2 ) = x − x · e− 2σ2 = x + δ+ (x)
Artistic Image Effects
approach (1D)
I it is also common to define δ+ (x) in a case-based manner
I for instance
+ −x · (1 − σx ) if x 6 σ
δ (x) =
0 otherwise
Artistic Image Effects
approach (2D)
I chose the center µ of the virtual lens
Artistic Image Effects
approach (2D)
I chose the center µ of the virtual lens
I iterate over all pixels in the destination image
Artistic Image Effects
approach (2D)
I chose the center µ of the virtual lens
I iterate over all pixels in the destination image
I compute the polar coordinates of the current pixel
(x, y) → r(µ), ϕ
Artistic Image Effects
approach (2D)
I chose the center µ of the virtual lens
I iterate over all pixels in the destination image
I compute the polar coordinates of the current pixel
(x, y) → r(µ), ϕ
I compute the radial warp
T(r) = r + δ+ (r)
Artistic Image Effects
approach (2D)
I chose the center µ of the virtual lens
I iterate over all pixels in the destination image
I compute the polar coordinates of the current pixel
(x, y) → r(µ), ϕ
I compute the radial warp
T(r) = r + δ+ (r)
I compute the corresponding Euclidean coordinates
T(r), ϕ → (u, v)
in the source image and read intensity or color from there
Artistic Image Effects
on choosing δ+ or δ·
I choice are arbitrary and there are infinitely many ways . . .
Artistic Image Effects
examples of lenses (I)
I different functions δ+ (r, rmax ) on a 400 × 400 image
I in each example, rmax = 150
r r2
original δ+ = −r · 1 − rmax δ+ = −r · 1 − 2
rmax
Artistic Image Effects
examples of lenses (II)
I different functions δ+ (r, rmax ) on a 400 × 400 image
I in each example, rmax = 150
√2 −r2
rmax r2
δ+ = −r · rmax δ+ = −r · tanh r
rmax δ+ = −r · exp − 21 2
rmax
Artistic Image Effects
a way more elegant approach
I pretend to be a physicist and understand T to be
something like a central force
Artistic Image Effects
a way more elegant approach
I pretend to be a physicist and understand T to be
something like a central force
I i.e. consider
T = T(r, x)
where r = µ − x indicates the vector pointing from
the current pixel x towards the center µ of the force
Artistic Image Effects
s more elegant approach
I in this interpretation, we can understand T as a distant
dependent displacement in the direction of the center
of the force
T(r, x) = x + δ+ (µ − x)
Artistic Image Effects
example
I here, we applied
(µ−x)2
g̃(x) = g(x + e− 2σ2 · (µ − x))
where µ = (200, 150) and σ = 150
Artistic Image Effects
waves effect
I transform the image such that it appears as if on the
bottom of a swimming pool whose water is in motion
example
Artistic Image Effects
approach (1D)
I as usual, we are interested in g̃(x̃) = g T(x)
I we choose
T(x) = x + α sin(νx − φ)
where the parameters α, ν, and φ denote
the amplitude
the frequency
the phase
of the wave
Artistic Image Effects
example
I effects of the parameters in T(x) = x + α sin(νx − φ)
id(x) id(x)
10 10
T (x) T1 (x)
T2 (x)
5 5
0 0
0 5 10 0 5 10
T(x) = x + sin(x) different frequencies
Artistic Image Effects
example
I effects of the parameters in T(x) = x + α sin(νx − φ)
id(x) id(x)
10 10
T1 (x) T1 (x)
T2 (x) T2 (x)
5 5
0 0
0 5 10 0 5 10
different amplitudes different phases
Artistic Image Effects
approach (2D)
I again, we follow the idea of a central force
I we choose
r
T(r, x) = x + α sin νkrk − φ ·
krk
= x + ∆(r, α, ν, φ)
Artistic Image Effects
swirl effect
I twist an image about a point µ just as if you would put an
immersion blender into it
example
Artistic Image Effects
swirl effect
I each pixel x of the images is being displaced by a vector ∆
where, for instance
∆⊥r=µ−x
Artistic Image Effects
approach (2D)
I chose the point µ where to insert the virtual blender
Artistic Image Effects
approach (2D)
I chose the point µ where to insert the virtual blender
I iterate over all pixels in the destination image
Artistic Image Effects
approach (2D)
I chose the point µ where to insert the virtual blender
I iterate over all pixels in the destination image
I compute the polar coordinates of the current pixel
r = kµ − xk
µy − y
ϕ = arctan
µx − x
Artistic Image Effects
approach (2D)
I chose the point µ where to insert the virtual blender
I iterate over all pixels in the destination image
I compute the polar coordinates of the current pixel
r = kµ − xk
µy − y
ϕ = arctan
µx − x
I compute the angular warp
T(ϕ, r) = ϕ + δ+ (ϕ, r)
Artistic Image Effects
approach (2D)
I that is compute an angular displacement depending on the
distance r between the current point x and the center µ of
the rotation
Artistic Image Effects
approach (2D)
I that is compute an angular displacement depending on the
distance r between the current point x and the center µ of
the rotation
I the choice of δ+ (ϕ, r) is, again, almost arbitrary
Artistic Image Effects
approach (2D)
I that is compute an angular displacement depending on the
distance r between the current point x and the center µ of
the rotation
I the choice of δ+ (ϕ, r) is, again, almost arbitrary
I determine the corresponding Euclidean coordinates
u = x + r · cos T(ϕ, r) − cos ϕ
v = y + r · sin T(ϕ, r) − sin ϕ
in the source image and read intensity or color from there
Artistic Image Effects
explanation
u
∆
r
x x
r ϕ′ r
ϕ
µ µ
Artistic Image Effects
explanation
I according to figure, we have
u=x+∆ ⇔ ∆=u−x
I on the other hand, we have (using ϕ 0 = T(ϕ, r))
u = µx + r · cos ϕ 0
v = µy + r · sin ϕ 0
x = µx + r · cos ϕ
y = µy + r · sin ϕ
I therefore, it follows that
∆x = u − x = r · (cos ϕ 0 − cos ϕ)
∆y = v − y = r · (sin ϕ 0 − sin ϕ)
which immediately leads to the above equations
Artistic Image Effects
explanation
I this, however, means that we may again understand the
effect to be caused by a central force
T(r, x) = x + ∆(r)
where
cos ϕ(r) + δ+ krk − cos ϕ(r)
∆(r) = krk ·
+
sin ϕ(r) + δ krk − sin ϕ(r)
Summary
we now know about
I interpolation of 2D functions
I artistic image warping
I lens effects
I wave effects
I swirl effects
