Image Processing,
Retrieval, and Analysis (I)
Prof. Christian Bauckhage
Outline
Lecture 15
Recap
Non-Linear Filters
Median Filters
Morphological Filters
Bilateral Filters
Gaussian Compositions
Unsharp Masking
Difference of Gaussians
Summary
Recap
mean filter (I)
I given intensity image f , consider the m × n neighborhood
Nxy = f [i, j]
m
of the pixel at (x, y) where x − 2 6 i 6 x + m2 , y − n
2 6j6y+ n
2
I we also write
Nxy = p0 , p1 , . . . , pq−1
where q = mn
Recap
mean filter (II)
I mean filter
1 X 1 X
p0 = pi = pi
mn mn
pi ∈Np i
Recap
mean filter (II)
I mean filter
1 X 1 X
p0 = pi = pi
mn mn
pi ∈Np i
I weighted mean filter
P
i wi pi
p = P
0
i wi
Recap
mean filter (II)
I mean filter
1 X 1 X
p0 = pi = pi
mn mn
pi ∈Np i
I weighted mean filter
P
i wi pi
p = P
0
i wi
note:
the Gaussian filter is a specific weighted mean filter
Recap
mean filter (III)
I using convolutions, mean filtering requires O(mn) per pixel
Recap
mean filter (III)
I using convolutions, mean filtering requires O(mn) per pixel
I using integral images, this can be reduced to O(1)
Recap
mean filter (III)
I using convolutions, mean filtering requires O(mn) per pixel
I using integral images, this can be reduced to O(1)
I if
x+ m n
X Xy+ 2
2
f [i, j] X
x X
y
c[x, y, m, n] = and C[x, y] = c[i, j]
m n mn
i=x− 2 j=y− 2 i=0 j=0
then
h m ni h m n i
c[x, y, m, n] = C x + , y + − C x + ,y − − 1
h 2m 2
ni h2 m
2
n i
− C x − − 1, y + + C x − − 1, y − − 1
2 2 2 2
C β C C α C
c c c c
y y y y
δ γ
x x x x
Recap
integral images
I dynamic programming allows for efficient computation of
integral images, simply consider that
C[x, y] = c[x, y] + C[x, y − 1] + C[x − 1, y] − C[x − 1, y − 1]
x
Recap
integral images
I dynamic programming allows for efficient computation of
integral images, simply consider that
C[x, y] = c[x, y] + C[x, y − 1] + C[x − 1, y] − C[x − 1, y − 1]
y y y y
x x x x
Non-Linear Filters
median filter
given f and Nxy , consider ordered set Rxy = ri ∈ Nxy ri 6 ri+1
I
I the element r q−1 is called the median of Nxy
2
I the operation g[x, y] ← r q−1 yields a median filtered version of f
2
example
image f 3 × 3 median g
Non-Linear Filters
algorithm I: naı̈ve median
for all y = 0 . . . M − 1 I average effort per pixel
for all x = 0 . . . N − 1
sanity check for x and y
Nxy = ∅
O(q log q)
for all j = − m2 . . . m2
for all i = − n2 . .. n2 I rather slow, because if
Nxy = Nxy ∪ f [y + j, x + i]
Rxy = qsort(Nxy ) q = mn
g[y, x] ← r q−1
2
effort becomes large
Non-Linear Filters
observation
I the median is the p(x)
0.5 quantile of a
given distribution
x
P (x)
1
2
med{p(x)} x
Non-Linear Filters
histograms
I histograms H(i) count things
I e.g. the number of occurrences of intensities i in an image
I when normalized, histograms correspond to probability
mass functions
Pi
H(i) C(i) = k=0 H(k)
Non-Linear Filters
algorithm II: Huang, 1979
for all y = 0 . . . M − 1
for all x = 0 . . . N − 1
I sketch
sanity check for x and y
if (x, y) is UL corner
initialize histogram H
else
for all k = − n2 . . . n2 y − +
sub f [y + k, x − 2n − 1] from H
add f [y + k, x + 2n ] to H
P
q = i Hi
s=0
for all i = 0 . . . #colors x
s = s + Hi
if s > q/2
I effort per pixel
median = i
O(n) + 256 ops max
= O(n) + O(1)
= O(n)
Non-Linear Filters
observation
I for disjoint sets A and B, we have
H(A ∪ B) = H(A) + H(B)
⇒ idea: maintain a histogram hx for each column x of f
Non-Linear Filters
algorithm III: Perreault & Hébert, 2007
for all y = 0 . . . M − 1
for all x = 0 . . . N − 1
I sketch
sanity check for x and y
if y is uppermost row −
initialize hx
if (x, y) is UL corner y
initialize H
+
else
sub f [y − m2 − 1, x + n2 ] from hx+ n
2
add f [y + m2 , x + n2 ] to hx+ n
2 x
H = H − hx− n −1 + hx+ n
2 2
s=0
...
y − +
x
Non-Linear Filters
algorithm III: Perreault & Hébert, 2007
I effort per pixel (8-bit gray scale image):
1. 1 addition and 1 subtraction for hx+ n2
2. 256 addition and 256 subtraction for H = H − hx− n2 −1 + hx+ n2
3. max. 256 operations for computing s
⇒ O(1)
Non-Linear Filters
algorithm III: Perreault & Hébert, 2007
I effort per pixel (8-bit gray scale image):
1. 1 addition and 1 subtraction for hx+ n2
2. 256 addition and 256 subtraction for H = H − hx− n2 −1 + hx+ n2
3. max. 256 operations for computing s
⇒ O(1)
I however: large constant factor
Non-Linear Filters
algorithm III: Perreault & Hébert, 2007
I effort per pixel (8-bit gray scale image):
1. 1 addition and 1 subtraction for hx+ n2
2. 256 addition and 256 subtraction for H = H − hx− n2 −1 + hx+ n2
3. max. 256 operations for computing s
⇒ O(1)
I however: large constant factor
I however: neat tricks keep effort low
I multilevel histograms
I addition / subtraction by means of bit shifting
Non-Linear Filters
algorithm III: Perreault & Hébert, 2007
I effort per pixel (8-bit gray scale image):
1. 1 addition and 1 subtraction for hx+ n2
2. 256 addition and 256 subtraction for H = H − hx− n2 −1 + hx+ n2
3. max. 256 operations for computing s
⇒ O(1)
I however: large constant factor
I however: neat tricks keep effort low
I multilevel histograms
I addition / subtraction by means of bit shifting
I implementation available within OpenCV
Non-Linear Filters
morphology (I)
given f [i, j] and ordered set Rxy = ri ∈ Nxy ri 6 ri+1
I
Non-Linear Filters
morphology (I)
given f [i, j] and ordered set Rxy = ri ∈ Nxy ri 6 ri+1
I
I the operation
g[x, y] ← r0
is called erosion
Non-Linear Filters
morphology (I)
given f [i, j] and ordered set Rxy = ri ∈ Nxy ri 6 ri+1
I
I the operation
g[x, y] ← r0
is called erosion
I the operation
g[x, y] ← rq−1
is called dilation
Non-Linear Filters
morphology (II)
I erosion and dilation are useful in binary image processing
I they shrink or expand shapes, for example
image f erosion e(f ) dilation d(f )
Non-Linear Filters
morphology (III)
I shape boundary extraction
shape f boundary f − e(f )
Non-Linear Filters
morphology (IV)
I the operation
d◦e
is called opening
Non-Linear Filters
morphology (IV)
I the operation
d◦e
is called opening
I the operation
e◦d
is called closing
Non-Linear Filters
morphology (V)
I they remove isolated pixels or close holes, for example
image f opening d e(f ) closing e d(f )
Non-Linear Filters
morphology (VI)
I morphological operations are of importance in industrial
computer vision (machine vision) and in medical image
processing
Non-Linear Filters
morphology (VI)
I morphological operations are of importance in industrial
computer vision (machine vision) and in medical image
processing
I they are treated in great detail in
I R. Gonzales and R.E. Woods, Digital Image Processing,
Prentice Hall, 3rd edition, 2007
Non-Linear Filters
bilateral filters (I)
I rather recent interesting idea
I for details, see, for instance
I C. Tomasi and R. Manduchi, Bilateral Filtering for Gray and
Color Images, Proc. ICCV, 1998
I S. Paris, P. Kornprobst, J. Tumblin, and F. Durand, Bilateral
Filtering: Theory and Applications, Computer Graphics and
Vision, 4(1), 2008
Non-Linear Filters
bilateral Filters (II)
I given image f , pixels p at p = (x, y) and q at q = (x 0 , y 0 ),
consider
1 X
Gρ |fp − fq | Gσ kp − qk fq
f̃p =
wp
q∈Np
where wp is a normalizing factor and Gρ and Gσ are
Gaussians with standard deviations ρ and σ
Non-Linear Filters
bilateral Filters (II)
I given image f , pixels p at p = (x, y) and q at q = (x 0 , y 0 ),
consider
1 X
Gρ |fp − fq | Gσ kp − qk fq
f̃p =
wp
q∈Np
where wp is a normalizing factor and Gρ and Gσ are
Gaussians with standard deviations ρ and σ
Non-Linear Filters
bilateral Filters (II)
I given image f , pixels p at p = (x, y) and q at q = (x 0 , y 0 ),
consider
1 X
Gρ |fp − fq | Gσ kp − qk fq
f̃p =
wp
q∈Np
where wp is a normalizing factor and Gρ and Gσ are
Gaussians with standard deviations ρ and σ
Non-Linear Filters
bilateral Filters (III)
ρ 0.05 0.2 0.8
σ
16
Gaussian Compositions
unsharp masking (I)
I given an image f (x, y), compute
Gaussian Compositions
unsharp masking (I)
I given an image f (x, y), compute
1. s(x, y) = Gσ ∗ f (x, y)
Gaussian Compositions
unsharp masking (I)
I given an image f (x, y), compute
1. s(x, y) = Gσ ∗ f (x, y)
2. r(x, y) = f (x, y) − s(x, y)
Gaussian Compositions
unsharp masking (I)
I given an image f (x, y), compute
1. s(x, y) = Gσ ∗ f (x, y)
2. r(x, y) = f (x, y) − s(x, y)
3. f̃ (x, y) = f (x, y) + αr(x, y)
I terminology:
α = 1 ⇔ unsharp masking
α > 1 ⇔ highboost filtering
Gaussian Compositions
unsharp masking (II)
f (x, y) s(x, y) r(x, y) f̃ (x, y)
Gaussian Compositions
difference of Gaussians (I)
I consider two Gaussians
2 2
1 − x2 1 − x2
G1 (x) = √ e 2σ1 and G2 (x) = √ e 2σ2
2πσ1 2πσ2
I their difference is 0.14
σ= 3
0.12 σ= 7
DoG
DoG(x) = G1 (x) − G2 (x) 0.1
0.08
0.06
0.04
0.02
-0.02
-0.04
-20 -10 0 10 20
Gaussian Compositions
difference of Gaussians (II)
original
σ1 = 4.5, σ2 = 9 σ1 = 9, σ2 = 18 σ1 = 18, σ2 = 36
Gaussian Compositions
Laplacians (I)
I for the discrete convolution (not correlation!!!)
of the signal · · · 0-110 · · · with the kernel [-11],
we have
· · · 000-11000 · · · ∗ [-11] = · · · 0001-21000 · · ·
Gaussian Compositions
Laplacians (I)
I for the discrete convolution (not correlation!!!)
of the signal · · · 0-110 · · · with the kernel [-11],
we have
· · · 000-11000 · · · ∗ [-11] = · · · 0001-21000 · · ·
I therefore, if we define
d !
f [x] = [-11] ∗ f [x]
dx
then
d2
f [x] = [-11] ∗ [-11] ∗ f [x] = [1-21] ∗ f [x]
dx2
Gaussian Compositions
Laplacians (II)
I given a continuous 2D function f (x, y), the function
∂2 ∂2
∆ f (x, y) = ∇2 f (x, y) = f (x, y) + f (x, y)
∂x2 ∂y2
is called the Laplacian of f (x, y)
Gaussian Compositions
Laplacians (III)
I for discrete 2D function f [x, y] with
∂2 f
= f [x − 1, y] − 2f [x, y] + f [x + 1, y]
∂x2
∂2 f
= f [x, y − 1] − 2f [x, y] + f [x, y + 1]
∂y2
we find
∇2 f [x, y] =f [x − 1, y] + f [x + 1, y]+
f [x, y − 1] + f [x, y + 1] − 4 f [x, y]
Gaussian Compositions
Laplacians (IV)
I written as a discrete 2D filter kernel, the Laplacian
amounts to
0 1 0
L[x, y] = 1 -4 1
0 1 0
and we have
∇2 f [x, y] = (L ∗ f )[x, y]
Gaussian Compositions
note:
I apparently, there are several possible definitions for
discrete gradient operators . . .
I some of the more common operators are called Sobel,
Canny, Preweitt, or Roberts gradient
I depending on the choice of gradient, the discrete
Laplacian may assume different forms
Gaussian Compositions
Laplacians (V)
I the Laplacian of an image reveals regions of rapidly
changing intensities and is therefore often used in
edge detection
Gaussian Compositions
Laplacians (V)
I the Laplacian of an image reveals regions of rapidly
changing intensities and is therefore often used in
edge detection
I yet, as a second derivative operator, it is sensitive to noise
Gaussian Compositions
Laplacians (V)
I the Laplacian of an image reveals regions of rapidly
changing intensities and is therefore often used in
edge detection
I yet, as a second derivative operator, it is sensitive to noise
I for increased robustness, one often performs Gaussian
smoothing prior to computing the Laplacian, i.e.
f̃ (x, y) = L ∗ G ∗ f (x, y)
Gaussian Compositions
Laplacians (VI)
I when computing L ∗ G ∗ f , it is beneficial to compute the
Laplacian of Gaussian
LoG(x, y) = L ∗ G (x, y)
x2 + y2 − x2 +y22
1
=− 4 1− e 2σ
πσ 2σ2
beforehand and then to compute
LoG ∗ f (x, y)
Gaussian Compositions
Laplacians (VII)
I finally, to further simplify computation, the Laplacian of
Gaussian LoG is commonly approximated by means
of a suitably chosen Difference of Gaussians DoG
Summary
we now know about
I efficient algorithms for median filtering
I morphological operations and possible applications
I bilateral filtering and its properties
I unsharp masking
I DoGs and LoGs
