CPSC 425: Computer Vision

Lecture 5: Image Filtering (final)

( unless otherwise stated slides are taken or adopted from Bob Woodham, Jim Little and Fred Tung )
Menu for Today
Topics:
—Linear Filtering recap — Non-linear Filters:
—Efficient convolution, Fourier aside Median, ReLU, Bilateral Filter

Readings:
— Today’s Lecture: Szeliski 3.3-3.4, Forsyth & Ponce (2nd ed.) 4.4

Reminders:
— Assignment 1: Image Filtering and Hybrid Images due Sep 24th

2
Recap

3
Linear Filter Example z z0
2 3
x  0
image
I(X, Y )
4 5 x
output
I (X, Y )
I(X, Y ) F (X, YP) = y !
y
F (X, Y ) n⇥n z
filter
n⇥n m⇥m
m⇥m m=5 0 0 x
x =f
m=5 z

height
k
X k
X
0
I (X, Y ) = FF(I,
(i, J)I(X
j) + i, Y + j)
j= k i= k
output filter image (signal)

4 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Linear Filters: Correlation vs. Convolution

Definition: Correlation
k
X k
X
0
I (X, Y ) = k
X X F
k (i, j)I(X + i, Y + j)
0
I (X, Y )j=
= k i= k F (i, j)I(X + i, Y + j)
Xk Xk
Definition: Convolution
0
j= k i= k
I (X, Y ) = k
X X F
k (i, j)I(X i, Y j)
0
I (X, Y )j== k i= k F (i, j)I(X i, Y j)
k
Xj= X k
Filter k i= k
0
(rotated by 180) I (X, Y ) = k
X X F
k ( i, j)I(X + i, Y + j)
0
a b I c(X, Y )j=
=
1 k2 i=3 k F ( i, j)I(X + i, Y= + j)
9a + 8b + 7c
d e f 4 j=
5 6k i= k + 6d + 5e + 4f
+ 3g + 2h + 1i
g h i 7 8 9
Filter Image Output
5
Point Spread Function

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 9 8 7 0 0 0 0
0 0 1 0 0 0 0 0 0 6 5 4 0 0 0 0
1 2 3
0 0 0 0 0 0 0
0 0
0
0 0 0 0 0 0
⇤ 4 5 6 = 0
0
3
0
2
0
1
0
0
9
0
8
0
7
0
0
7 8 9
0 0 0 0 0 1 0 0 0 0 0 0 6 5 4 0
0 0 0 0 0 0 0 0 0 0 0 0 3 2 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

6
Linear Systems: Characterization Theorem

Any linear, shift invariant operation can be expressed as convolution

7
Low-pass Filtering = “Smoothing”

Box Filter Pillbox Filter Gaussian Filter

1 4 6 4 1
1 1 1 4 16 24 16 4
1 1
1 1 1 == 6 24 36 24 6−
9 256
1 1 1 4 16 24 16 4
1 4 6 4 1
All of these filters are Low-pass Filters
Low-pass filter: Low pass filter filters out all of the high frequency content
of the image, only low frequencies remain
8
Gaussian Blur
Gaussian Blur
Gaussian kernels are often used for smoothing and resizing images
• Gaussian kernel
12.2

1D 2D

1D 2D

⇤ =

9
Example 6: Smoothing with a Gaussian

With =1: 0.059 0.097 0.059

0.097 0.159 0.097

0.059 0.097 0.059

Better version of the Gaussian filter:

— sums to 1 (normalized)
— captures ±2

A good guideline for the Gaussian filter is to capture ±3 , for = 1 => 7x7 filter

10
Gaussian Blur

2D Gaussian filter can be thought of as an outer product or convolution of

row and column filters

11
Separable Filtering

2D Gaussian blur by horizontal/vertical blur

horizontal vertical

vertical
12 horizontal
Example: Separable Gaussian Filter

1 1 4 6 4 1
4 4 16 24 16 4
1 1 1
1 4 6 4 1 ⌦ 6 = 6 24 36 24 6
16 16 256
4 4 16 24 16 4
1 1 4 6 4 1

13
Efficient Implementation: Separability I(X, Y )
Naive implementation of 2D Gaussian: F (X, Y )
I(X, Y ) n⇥n
I(X, Y )
At each pixel,
F (X, Y ) , there are m ⇥ m multiplications
F (X, Y ) I(X, Y )
n⇥n m=5
There are n ⇥ n pixels inF (X, Y )
m⇥m m⇥m n⇥n
Total: m = 5 2 2
mm⇥=n5 multiplications
m⇥m
m=5
Separable 2D Gaussian:
I(X, Y ) I(X, Y )
At each pixel,
F (X, Y ) , there are F2m(X, Y )multiplications
I(X, Y )
n⇥n
There are n ⇥ n pixels inF (X, Y )
m⇥m m⇥m n⇥n
Total: m = 5 2mm⇥ =n5 multiplications
2
m⇥m
m=5
Separable Filtering
Several useful filters can be applied as independent row and column operations
116 Computer Vision: Algorithms and Applications (September 3, 2010 draft)

1 4 6 4 1
1 1 ··· 1
1 1 ··· 1
1 2 1 4 16 24 16 4 1 0 1 1 2 1
1
K2 .. .. ..
1
16 2 4 2 1
256 6 24 36 24 6 1
8 2 0 2 1
4 2 4 2
. . 1 .
1 2 1 4 16 24 16 4 1 0 1 1 2 1
1 1 ··· 1
1 4 6 4 1

1
K 1 1 ··· 1 1
4 1 2 1 1
16 1 4 6 4 1 1
2 1 0 1 1
2 1 2 1

(a) box, K = 5 (b) bilinear (c) “Gaussian” (d) Sobel (e) corner

Figure 3.14 Separable linear filters: For each image (a)–(e), we show the 2D filter kernel
(top), the corresponding horizontal 1D kernel (middle), and the filtered image (bottom). The
filtered Sobel and corner images are signed, scaled up by 2⇥ and 4⇥, respectively, and added
Low-pass Filtering = “Smoothing”

Box Filter Pillbox Filter Gaussian Filter

1 4 6 4 1
1 1 1 4 16 24 16 4
1 1
1 1 1 == 6 24 36 24 6−
9 256
1 1 1 4 16 24 16 4
1 4 6 4 1

Not a separable filter!

16
Advanced Convolution Topics

• Multiple filters
• Fourier transforms

17
 Linear Filters: Properties
⌦Let ⌦ k denote
k F1 convolution.
F1F2 F2 F LetFI(X,I(X, Y ) be
Y )a digital image
(F1 +(FF1 2+)⌦ ) ⌦ I(X,
F2I(X, 1 ⌦ I(X,
Y ) =Y F) 1=⌦FI(X, 2 ⌦ I(X,
Y ) +YF)2+⌦FI(X, Y) Y)
)(kF ) ⌦ I(X,
⌦ I(X, Y⌦)⌦=YkF)kLet
(kFSuperposition: =
⌦F ⌦
(kI(X,(kI(X,
Y )) Y
= )) =
k(F k(F
⌦ I(X,⌦ I(X,
Y )) Y ))
FF1 1andFF 2 2 be digital
FF I(X,filters
I(X,YY) )
(F1 1++FF
(F 2 )2 )⌦⌦
⌦I(X,
I(X, kYY) )==
FF1F1 1⌦⌦I(X,
FI(X,
2 YY) F
)++FF2 2⌦⌦I(X,
I(X,I(X,
Y )YY) )
(kF) )⌦⌦I(X,
(kF (FI(X,
1+YYF) )2=)=⌦ ⌦⌦(kI(X,
FFI(X, (kI(X,
Y ) =YY F))1))= k(F⌦
⌦=I(X,
k(F Y⌦I(X,
) I(X,
+ FY 2Y))))I(X, Y )
⌦
(kF ) ⌦ I(X, Y ) = F ⌦ (kI(X, Y )) = k(F ⌦ I(X, Y ))
FScaling:
1 F2 Let F be⌦digital
I(X,k Yfilter
) Fand1 ⌦let F2 k be F aFscalar
1 F2 Y ) F
I(X, I(X, Y )
⌦ I(X, Y ) = F1 ⌦ I(X,
(F1 + YF )+ 2) F ⌦ (F
⌦2 I(X,I(X,
1Y+) Y=
F)2F) 1⌦⌦I(X,
I(X,YY) )=+FF1 2⌦⌦I(X,
I(X,YY) )+ F2 ⌦ I(X, Y )
X, Y ) = F ⌦ (kI(X,(kF Y ))) = k(F ⌦
⌦ I(X, Y I(X,
= F)Y⌦
)(kF ))I(X,
⌦ (kI(X, Y )Y=))F=⌦k(F (kI(X,
⌦ I(X,Y ))Y=))k(F ⌦ I(X, Y ))

Shift Invariance: Output is local (i.e., no dependence on absolute position)

An operation is linear if it satisfies both superposition and scaling

 Linear Filters: Additional Properties
⌦Let ⌦ k denote
k F1 convolution.
F1F2 F2 F LetFI(X,I(X, Y )a digital image. Let F and G be
Y ) be
+(FF1 2+
(F1 digital ⌦ ) ⌦ I(X,
F2I(X,
) filters 1 ⌦ I(X,
Y ) =Y F) 1=⌦FI(X, 2 ⌦ I(X,
Y ) +YF)2+⌦FI(X, Y) Y)
(kF )(kF ) ⌦ I(X,
⌦ I(X, Y ) =Y F) =
⌦F ⌦ (kI(X,
(kI(X, Y ))
Y )) = = k(F
k(F ⌦ I(X,
⌦ I(X, Y )) Y ))
— Convolution is associative. That is,
G ⌦ (F ⌦ I(X, Y )) = (G ⌦ F ) ⌦ I(X, Y )
symmetric.
— Convolution is(G That is,
⌦ F ) ⌦ I(X, Y ) = (F ⌦ G) ⌦ I(X, Y )
(G⌦⌦F
(G F))⌦⌦(G
(G )⌦⌦F
I(X,
FI(X, Y)))⌦
YI(X,==I(X,
Y(G
(G⌦⌦
)=YF
(G )⌦⌦(G
)F)= )⌦⌦F
I(X,
FI(X, Y)))⌦ I(X,
YI(X, Y) Y)

F2Convolving
F I(X, Y ) with filter F and then convolving the result with filter G can
) =be
F1achieved
⌦ I(X, Y in
)+single
⌦F2 ⌦ k step,
I(X,Fnamely
1 ) F2 convolving
Y F I(X, Y ) with filter G ⌦ F = F ⌦ G
F ⌦ (kI(X, Y ))(F + F⌦
=1k(F 2 ) I(X,
⌦ I(X,Y ))Y ) = F1 ⌦ I(X, Y ) + F2 ⌦ I(X, Y )
Note:(kF
Correlation,
) ⌦ I(X, Yin)general, is not associative.
= F ⌦ (kI(X, (thinkYof))subtraction)
Y )) = k(F ⌦ I(X,
 I(x, y) I(x, y) ⇤ g(x, y)
Symmetricity Example (zero-padding)
A conv B = B conv A
0 0
A
A corr
conv B
B == B B corr
conv AA
0 0
A corr B = B corr A
conv(A, B) = conv(B, A)
0 0
conv(A,B)
corr(A, B) == corr(B
conv(B,, A
A))
corr(A, B) 6= corr(B, A)
0 0
corr(A, B) = corr(B , A )
0
A (x, y) = A( x, y)

For code/explanation in class see [Link]

 Linear Filters: Additional Properties
⌦Let ⌦ k denote
k F1 convolution.
F1F2 F2 F LetFI(X,I(X, Y )a digital image. Let F and G be
Y ) be
+(FF1 2+
(F1 digital ⌦ ) ⌦ I(X,
F2I(X,
) filters 1 ⌦ I(X,
Y ) =Y F) 1=⌦FI(X, 2 ⌦ I(X,
Y ) +YF)2+⌦FI(X, Y) Y)
(kF )(kF ) ⌦ I(X,
⌦ I(X, Y ) =Y F) =
⌦F ⌦ (kI(X,
(kI(X, Y ))
Y )) = = k(F
k(F ⌦ I(X,
⌦ I(X, Y )) Y ))
— Convolution is associative. That is,
G ⌦ (F ⌦ I(X, Y )) = (G ⌦ F ) ⌦ I(X, Y )
symmetric.
— Convolution is(G That is,
⌦ F ) ⌦ I(X, Y ) = (F ⌦ G) ⌦ I(X, Y )
(G⌦⌦F
(G F))⌦⌦(G
(G )⌦⌦F
I(X,
FI(X, Y)))⌦
YI(X,==I(X,
Y(G
(G⌦⌦
)=YF
(G )⌦⌦(G
)F)= )⌦⌦F
I(X,
FI(X, Y)))⌦ I(X,
YI(X, Y) Y)

F2Convolving
F I(X, Y ) with filter F and then convolving the result with filter G can
) =be
F1achieved
⌦ I(X, Y in
)+single
⌦F2 ⌦ k step,
I(X,Fnamely
1 ) F2 convolving
Y F I(X, Y ) with filter G ⌦ F = F ⌦ G
F ⌦ (kI(X, Y ))(F + F⌦
=1k(F 2 ) I(X,
⌦ I(X,Y ))Y ) = F1 ⌦ I(X, Y ) + F2 ⌦ I(X, Y )
Note:(kF
Correlation,
) ⌦ I(X, Yin)general, is not associative.
= F ⌦ (kI(X, (thinkYof))subtraction)
Y )) = k(F ⌦ I(X,
Example: Two Box Filters
filter = boxfilter(3)
signal.correlate2d(filter, filter,′ full′)

3x3 Box 3x3 Box

Example: Two Box Filters
Note, in this case you have to pad
Treat one filter as padded “image” maximally until two filters no longer overlap

0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 1 1 1 0 0 1 1 1
1 11 1
0 0 1 1 1 0 0 ⌦ 1 1 1 =
9 99 81
0 0 1 1 1 0 0 1 1 1
0 0 0 0 0 0 0
3x3 Box
0 0 0 0 0 0 0
3x3 Box Output
Example: Two Box Filters

Treat one filter as padded “image”

0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2
0 0 1 1 1 0 0 1 1 1
1 11 1
0 0 1 1 1 0 0 ⌦ 1 1 1 =
9 99 81
0 0 1 1 1 0 0 1 1 1
0 0 0 0 0 0 0
3x3 Box
0 0 0 0 0 0 0
3x3 Box Output
Example: Two Box Filters

Treat one filter as padded “image”

0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2 3
0 0 1 1 1 0 0 1 1 1
1 11 1
0 0 1 1 1 0 0 ⌦ 1 1 1 =
9 99 81
0 0 1 1 1 0 0 1 1 1
0 0 0 0 0 0 0
3x3 Box
0 0 0 0 0 0 0
3x3 Box Output
Example: Two Box Filters

Treat one filter as padded “image”

0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2 3 2 1
0 0 1 1 1 0 0 1 1 1 2 4 6
1 11 1
0 0 1 1 1 0 0 ⌦ 1 1 1 =
9 99 81
0 0 1 1 1 0 0 1 1 1
0 0 0 0 0 0 0
3x3 Box
0 0 0 0 0 0 0
3x3 Box Output
Example: Two Box Filters

Treat one filter as padded “image”

0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2 3 2 1
0 0 1 1 1 0 0 1 1 1 2 4 6 4 2
1 11 1
0 0 1 1 1 0 0 ⌦ 1 1 1 = 3 6 9 6 3
9 99 81
0 0 1 1 1 0 0 1 1 1 2 4 6 4 2
0 0 0 0 0 0 0 1 2 3 2 1
3x3 Box
0 0 0 0 0 0 0
3x3 Box Output
Example: Two Box Filters

Treat one filter as padded “image”

0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2 3 2 1
0 0 1 1 1 0 0 1 1 1 2 4 6 4 2
1 11 1
0 0 1 1 1 0 0 ⌦ 1 1 1 = 3 6 9 6 3
9 99 81
0 0 1 1 1 0 0 1 1 1 2 4 6 4 2
0 0 0 0 0 0 0 1 2 3 2 1
3x3 Box
0 0 0 0 0 0 0
3x3 Box Output
Example: Two Box Filters
filter = boxfilter(3)
temp = signal.correlate2d(filter, filter,′ full′)
signal.correlate2d(filter, temp,′ full′)

3x3 Box 3x3 Box 3x3 Box

5.1
Example: Two Box Filters
filter = boxfilter(3)
temp = signal.correlate2d(filter, filter,′ full′)
signal.correlate2d(filter, temp,′ full′)

3x3 Box 3x3 Box 3x3 Box

5.1
Example: Separable Gaussian Filter

1 1 4 6 4 1
4 4 16 24 16 4
1 1 1
1 4 6 4 1 ⌦ 6 = 6 24 36 24 6
16 16 256
4 4 16 24 16 4
1 1 4 6 4 1
Example: Separable Gaussian Filter

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 4
1 1 1
1 4 6 4 1 ⌦ 6 =
16 16 256
0 0 0 0 0 4
0 0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
Example: Separable Gaussian Filter

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 1 1 4 6 4 1
0 0 0 0 0 4 4 16
1 1 1
1 4 6 4 1 ⌦ 6 =
16 16 256
0 0 0 0 0 4
0 0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
Example: Separable Gaussian Filter

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 1 1 4 6 4 1
0 0 0 0 0 4 4 16 24 16 4
1 1 1
1 4 6 4 1 ⌦ 6 = 6 24 36 24 6
16 16 256
0 0 0 0 0 4 4 16 24 16 4
0 0 0 0 0 1 1 4 6 4 1
0 0 0 0 0
0 0 0 0 0
Example: Separable Gaussian Filter

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 1 1 4 6 4 1
0 0 0 0 0 4 4 16 24 16 4
1 1 1
1 4 6 4 1 ⌦ 6 = 6 24 36 24 6
16 16 256
0 0 0 0 0 4 4 16 24 16 4
0 0 0 0 0 1 1 4 6 4 1
0 0 0 0 0
0 0 0 0 0
 have size:
sha1_base64="qw89m2zjKtu52PaePZJvpyNWqtc=">AAACR3iclVDLSgMxFM3UV62vqks3QREqYpkpom6EghvFTQVrC506ZNJMG5rMDMkdoQz9Fn/GjVt3/oCLblwo4tL0sdDqxgMhh3PuITfHjwXXYNvPVmZmdm5+IbuYW1peWV3Lr2/c6ChRlFVpJCJV94lmgoesChwEq8eKEekLVvO7Z0O/dseU5lF4Db2YNSVphzzglICRvPytK1gABSw9B+9jVyfSS7unpf7tJS5Ir4sPsLOHXcXbHTA3cMk0/kfEy+/YRXsE/Js4E7JTrtRf7ucGuxUv/+S2IppIFgIVROuGY8fQTIkCTgXr59xEs5jQLmmzhqEhMQs101EPfbxrlBYOImVOCHikfk+kRGrdk76ZlAQ6etobin95jQSCk2bKwzgBFtLxQ0EiMER4WCpuccUoiJ4hhCpudsW0QxShYKrPmRKc6S//JjelonNUPLwybVygMbJoC22jAnLQMSqjc1RBVUTRAxqgN/RuPVqv1of1OR7NWJPMJvqBjPUFyaWwOQ==</latexit>
<latexit
m1 +
sha1_base64="9tlGDXwciwOBPKDWXvTitJ7m4xQ=">AAAB/3icbVDLSgMxFL1TX7W+RgU3boJFaBHLjIi6LLjRXQX7gHYomTTThmYyQ5IRyljQX3HjQhG3/oY7/8ZM24VWDwTOPede7s3xY86UdpwvK7ewuLS8kl8trK1vbG7Z2zsNFSWS0DqJeCRbPlaUM0HrmmlOW7GkOPQ5bfrDy8xv3lGpWCRu9SimXoj7ggWMYG2krr1XEkfhsVtGHc1CqtCs7NpFp+JMgP4Sd0aK1fIDZKh17c9OLyJJSIUmHCvVdp1YeymWmhFOx4VOomiMyRD3adtQgc0yL53cP0aHRumhIJLmCY0m6s+JFIdKjULfdIZYD9S8l4n/ee1EBxdeykScaCrIdFGQcKQjlIWBekxSovnIEEwkM7ciMsASE20iK5gQ3Pkv/yWNk4p7Vjm9MWlcwxR52IcDKIEL51CFK6hBHQjcwxO8wKv1aD1bb9b7tDVnzWZ24Resj2+HdpSk</latexit>
<latexit
K
X

k=2
(mk
(n + m
Pre-Convolving Filters

1)
!
⇥
1) ⇥ (n + m

m1 +
K
1)

k=2
(mk
1)
!
Convolving two filters of size m ⇥ m and n ⇥ n results in filter of size:

More broadly for a set of K filters of sizes mk ⇥ mk the resulting filter will
Gaussian: An Additional Property

Let ⌦ denote
k convolution.
F1 F2 LetF G G I(X,
(x) and
⌦Y
(x) )
⌦
G G (x) (x)
= be
=
G p
pGbe
2 +two
22 1D
(x)
2 (x)Gaussians
1 1 2 2 + 2
1 12
(F1 + F2 ) ⌦ I(X, Y ) = F1 ⌦ I(X, Y ) + F2 ⌦ I(X, Y )
(kF ) ⌦ I(X, Y ) = F ⌦ (kI(X, Y )) = k(F ⌦ I(X, Y ))
G 1 (x) ⌦ G 2 (x) = G p 2+ 2 (x)
1 2

Convolution of two Gaussians is another Gaussian

Special case: Convolving with G (x) twice is equivalent to G p

2 (x)
 What follows is for fun
(you will NOT be tested on this)

38
 Convolution using Fourier Transforms [ Szeliski 3.4 ]

Convolution Theorem:
0
Let i (x, y) = f (x, y) ⌦ i(x, y)

then0 0I (w 0
0 x , wy ) = F(wx , wy ) I(wx , wy )
i (x,
i (x,
y)
i (x,
y)
== y)
f (x,
f=
(x,
y) ⌦⌦
f (x,
y) ⌦y)i(x,
i(x,
y)i(x, y) y)
0
whereI 0 0
I(w(w 0
xI, xw(w
, yw)xy,=,=
)w F(w
y )F(w,xw, yw)xy,,I(w
=xF(w )and
wI(w
y )x I(w
,xw, yw)xy,)wy ) are Fourier transforms of i (x, y),= f (
0
,(x,
y) =y) f=(x,
f (x, and
y) ⌦
y)i(x, y) y)
⌦ i(x, 0
I (wx , wy ) = F
y ) F(w
wwxy, )w= = F(w
x , w
x ,
y )
w I(w
y ) I(w
At the expense of two
x , w
x ,
y )
wyFourier
) transforms and one inverse Fourier transform,
convolution can be reduced to (complex) multiplication

39
Fourier Transform (you will NOT be tested on this)
How would you generate this function?

= ? + ?

40 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

= ? + ?

41 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

= ? + ?

42 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

= ? + ?

43 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

≈ ? + ?
square wave

44 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

≈ ? + ?

square wave

45 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

≈ +

square wave

46 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

≈ +

square wave

47 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

≈ +

square wave
How would you
= express this
mathematically?

48 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Fourier Transform (you will NOT be tested on this)
How would you generate this function?

∞
1
= ∑ 2
Ak sin(2πkx)
k=1

infinite sum of sine waves

square wave

49 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)

Low-Pass Filtering in 1D
4.4

50
Fourier Transform (you will NOT be tested on this)

Image from: Numerical Simulation and Fractal Analysis of Mesoscopic Scale Failure in Shale Using Digital Images
Fourier Transform (you will NOT be tested on this)

= + + + +
Fourier Transform (you will NOT be tested on this)
What are “frequencies” in an image? Spatial frequency

f =4 f =5 f =6 f =7 f =8 f =9 f = 10
Fourier Transform (you will NOT be tested on this)
What are “frequencies” in an image? Spatial frequency

f =4 f =5 f =6 f =7 f =8 f =9 f = 10

Amplitude (magnitude) of Fourier transform (phase does not show desirable

correlations with image structure)
Fourier Transform (you will NOT be tested on this)
What are “frequencies” in an image? Spatial frequency

f =4 f =5 f =6 f =7 f =8 f =9 f = 10

Amplitude (magnitude) of Fourier transform (phase does not show desirable

correlations with image structure) Observation: low frequencies close
to the center
Fourier Transform (you will NOT be tested on this)
What are “frequencies” in an image? Spatial frequency
Fourier Transform (you will NOT be tested on this)
What are “frequencies” in an image? Spatial frequency
 F (!x, !y ) x
2D Fourier Transforms: Images
y
x !x
y !y f (x, y)
!x
omegay f (x, y) F (!x, !y )
F (!x, !y ) x
y
x f (x, y) !x
y omegay
f (x, y) F (!x, !y )
!x
F (! , !omega
) x
5.2
x
Image y y Fourier Transform
y
58 !x
 F (!x, !y ) x
2D Fourier Transforms: Images
y
x !x
y !y f (x, y)
!x
omegay f (x, y) F (!x, !y )
F (!x, !y ) x
y
x f (x, y) !x
y omegay
f (x, y) F (!x, !y )
!x
F (! , !omega
) x
5.2
x
Image y y Fourier Transform
y
59 !x
2D Fourier Transforms: Images

60
Aside: You will not be tested on this …

Image
[Link]
61
Aside: You will not be tested on this …

First (lowest) frequency, a.k.a. average

[Link]
62
Aside: You will not be tested on this …

+ Second frequency
[Link]
63
Aside: You will not be tested on this …

+ Third frequency
[Link]
64
Aside: You will not be tested on this …

+ 50% of frequencies
[Link]
65
Aside: You will not be tested on this …

[Link]
66
2D Fourier Transforms: Kernels

f (x, y)
F (!x, !y )
f (x, y)
x
F (!xy, !y )
!x
x
omegay
y
!x Compress power 0.5
omegay to exaggerate lobes
67 (just for visualization)
Convolution using Fourier Transforms
0
Convolution Theorem: i (x, y) = f (x, y) ⌦ i(x, y)
0
I (wx , wy ) = F(wx , wy ) I(wx , wy )

Convolve
Image

Multiply Inverse FFT

FFT

68
What preceded was for fun
(you will NOT be tested on it)

69
Assignment 1: Low/High Pass Filtering

I(x, y)
Original Low-Pass
I(x, y)Filter I(x, y) ⇤ g(x, y)
High-Pass Filter

I(x, y) I(x, y) ⇤ g(x, y) I(x, y) I(x, y) ⇤ g(x, y)

I(x, y) ⇤ g(x, y) I(x, y) 70 y) ⇤ g(x, y)
I(x,
71 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)
72 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)
73 Slide Credit: Ioannis (Yannis) Gkioulekas (CMU)
Aside: You will not be tested on this …

complex
element-wise
multiplication Low pass filtered image

image FFT (Mag)

High pass filtered image

74
Convolution using Fourier TransformsI(X, Y )
General implementation of convolution: F (X, Y )
I(X, Y ) n⇥n
I(X, Y )
At each pixel,
F (X, Y ) , there are m ⇥ m multiplications
F (X, Y ) I(X, Y )
n⇥n m=5
There are n ⇥ n pixels inF (X, Y )
m⇥m m⇥m n⇥n
Total: m = 5 2 2
mm⇥=n5 multiplications
m⇥m
m=5
Convolution if FFT space:
2
Cost of FFT/IFFT for image: O(n log n)
Cost of FFT/IFFT for filter: O(m log m)
2

Worthwhile if image and kernel are both large

75
Non-linear Filters

We’ve seen that linear filters can perform a variety of image transformations
— shifting
— smoothing
— sharpening

In some applications, better performance can be obtained by using non-linear

filters.

For example, the median filter selects the median value from each pixel’s
neighborhood.

76
Non-linear Filtering
(a) (b) (c)

(a) (b) (c)

gaussian blurred

(a) (b) (c) (d)

(e) (f) (g)

“shot”(e)
noise (f)
Figure 3.18 Median and bilateral filtering: (a) original
medianimage(g) with Gaussian noi
filtered
sian filtered; (c) median filtered; (d) bilaterally filtered; (e) original image with s
Figure 3.18 Median and bilateral filtering: (a) original image with Gaussian
Gaussian filtered; (g) median filtered; (h) bilaterally filtered. Note that the bilateno
sian filtered; (c) median filtered; (d) bilaterally filtered; (e) original image
to remove the shot noise because the noisy pixels are too different from their neiwith
(e) (f)
Gaussian filtered; (g) (h) bilaterally filtered.
(g) median filtered; (h) Note that the bilat
77
to remove the shot noise because the noisy pixels are too different from their ne
Median Filter

Take the median value of the pixels under the filter:

5 13 5 221

4 16 7 34 13

24 54 34 23 4 5 5 7 13 16 24 34 54

23 75 89 123

54 25 67 12

Image Output

78
Median Filter
Effective at reducing certain kinds of noise, such as impulse noise (a.k.a ‘salt and
pepper’ noise or ’shot’ noise)

The median filter forces points with distinct values to be more like their neighbors

Image credit: [Link]

79
 126 Computer Vision: Algorithms and Applications (September 3
Bilateral
(a) Filter (b) (c)

(d) (a)
(e) (b)
(f) (c)
Suppose we want to smooth a noisy step function
A Gaussian
0 Bilateral kernel
filtering performs
(Durand a weighted
and Dorsey 2002) average
c 2002ofACM:
points(a)over a spatial
noisy step
neighbourhood..
(b) domain filter (Gaussian); (c) range filter (similarity to center pixel value); (d)
er; (e)But this step
filtered averages points (f)
edge output; both
3D at the topbetween
distance and bottom
[Link] the step — blurring
Bilateral Filter idea: look at distances in range (value) as well as space x,y
ilateral filtering is quite slow compared to regular
80
separable filtering, a number
Bilateral Filter

An edge-preserving non-linear filter

Like a Gaussian filter:

— The filter weights depend on spatial distance from the center pixel
— Pixels nearby (in space) should have greater influence than pixels far away

Unlike a Gaussian filter:

— The filter weights also depend on range distance from the center pixel
— Pixels with similar brightness value should have greater influence than pixels
with dissimilar brightness value

81
Bilateral Filter
Gaussian filter: weights of neighbor at a spatial offset (x, y) away from the
center pixel I(X, Y ) given by:
1 x2 +y 2
G (x, y) = exp 2 2
2⇡ 2
(with appropriate normalization)
✓ ◆ ✓ ◆
1 x 2 1 y2
= p exp 2 2 p exp 2 2
2⇡ 2⇡

82
Bilateral Filter
Gaussian filter: weights of neighbor at a spatial offset (x, y) away from the
center pixel I(X, Y ) given by:
1 x2 +y 2
G (x, y) = exp 2 2
2⇡ 2
(with appropriate normalization)
✓ ◆ ✓ ◆
1 x 2 1 y 2

Bilateral filter: weights of neighbor at a spatial offset

= p exp 2 2 p exp(x, y)
2 2
away from the center
2⇡
pixel I(X, Y ) given by a product: 2⇡

x2 +y 2 (I(X+x,Y +y) I(X,Y ))2

2 2 2
exp d exp 2 r

(with appropriate normalization)

83
Bilateral Filter
Gaussian filter: weights of neighbor at a spatial offset (x, y) away from the
center pixel I(X, Y ) given by:
1 x2 +y 2
G (x, y) = exp 2 2
2⇡ 2
(with appropriate normalization)
✓ ◆ ✓ ◆
1 x 2 1 y 2

Bilateral filter: weights of neighbor at a spatial offset

= p exp 2 2 p exp(x, y)
2 2
away from the center
2⇡
pixel I(X, Y ) given by a product: 2⇡

domain x2 +y 2 (I(X+x,Y +y) I(X,Y ))2 range

2 2 2
kernel exp d exp 2 r
kernel

(with appropriate normalization)

84
Bilateral Filter Normalised
Domain Kernel
image I(X, Y ) image I(X, Y ) d 1
= 0.45
25
F 0(X,
25 Y ) 255 255
255 F (X, Y ) 1
0.1 0 0.1 1 1
0.08 0.12 0.08
0
n 0⇥ n0 230 255 255 0
n 0⇥ n0 0.9 1 1
0.12 0.20 0.12
0
m ⇥ m
25 25 255 230 255 0
m ⇥ m
0.1 0.1 1 0.9 1
0.08 0.12 0.08
0
m 0
=25
5255 255 255 0
m 0
=0.1
5 1 1 1

85
Bilateral Filter Normalised
Domain Kernel
image I(X, Y ) image I(X, Y ) d 1
= 0.45
25
F 0(X,
25 Y ) 255 255
255 F (X, Y ) 1
0.1 0 0.1 1 1
0.08 0.12 0.08
0
n 0⇥ n0 230 255 255 0
n 0⇥ n0 0.9 1 1
0.12 0.20 0.12
0
m ⇥ m
25 25 255 230 255 0
m ⇥ m
0.1 0.1 1 0.9 1
0.08 0.12 0.08
0
m 0
=25
5255 255 255 0
m 0
=0.1
5 1 1 1

Range Kernel
r = 0.45
0.98 0.98 0.2

1 1 0.1

0.98 1 0.1

(differences based on
centre pixel)
86
Bilateral Filter Normalised
Domain Kernel
image I(X, Y ) image I(X, Y ) d 1
= 0.45
25
F 0(X,
25 Y ) 255 255
255 0.1
F 0(X,0.1 Y1) 1 1
0.08 0.12 0.08
0
n 0⇥ n0 230 255 255 0
n 0⇥ n 0 0.9 1 1
0.12 0.20 0.12
0
m ⇥ m
25 25 255 230 255 0
m ⇥ m
0.1 0.1 1 0.9 1
0.08 0.12 0.08
0
m 0
=25
5255 255 255 0
m 0
=0.1
5 1 1 1

Range Kernel Range * Domain Kernel

r = 0.45
0.98 0.98 0.2 0.08 0.12 0.02
multiply
1 1 0.1 0.12 0.20 0.01

0.98 1 0.1 0.08 0.12 0.01

(differences based on
centre pixel)
87
Bilateral Filter Normalised
Domain Kernel
image I(X, Y ) image I(X, Y ) d 1
= 0.45
25
F 0(X,
25 Y ) 255 255
255 F (X, Y ) 1
0.1 0 0.1 1 1
0.08 0.12 0.08
0
n 0⇥ n0 230 255 255 0
n 0⇥ n0 0.9 1 1
0.12 0.20 0.12
0
m ⇥ m
25 25 255 230 255 0
m ⇥ m
0.1 0.1 1 0.9 1
0.08 0.12 0.08
0
m 0
=25
5255 255 255 0
m 0
=0.1
5 1 1 1

Range Kernel Range * Domain Kernel

r = 0.45
0.98 0.98 0.2 0.08 0.12 0.02 0.11 0.16 0.03
multiply sum to 1
1 1 0.1 0.12 0.20 0.01 0.16 0.26 0.01

0.98 1 0.1 0.08 0.12 0.01 0.11 0.16 0.01

(differences based on
centre pixel)
88
Bilateral Filter Normalised
Domain Kernel
image I(X, Y ) image I(X, Y ) d 1
= 0.45
25
F 0(X,
25 Y ) 255 255
255 0.1
F 0(X,0.1 Y1) 1 1
0.08 0.12 0.08
0
n 0⇥ n0 230 255 255 0
n 0⇥ n 0 0.9 1 1
0.12 0.20 0.12
0
m ⇥ m
25 25 255 230 255 0
m ⇥ m
0.1 0.1 1 0.9 1
0.08 0.12 0.08
0
m 0
=25
5255 255 255 0
m 0
=0.1
5 1 1 1

Range Kernel Range * Domain Kernel

r = 0.45 0.1 0 0.1 1 1 1

0.98 0.98 0.2

multiply
0.08 0.12 0.02 X 0.11 0.16 0.03 0 0 0 0.9 1 1

1 1 0.1 0.12 0.20 0.01 0.16 0.26 0.01 ⇥

0 0.1 0.1 1 0.9
= 0.1 1

0.98 1 0.1 0.08 0.12 0.01 0.11 0.16 0.01 0 0 0.1 1 1 1

(differences based on Bilateral Filter

centre pixel)
89
Bilateral Filter Normalised
Domain Kernel
image I(X, Y ) image I(X, Y ) d 1
= 0.45 0.1 0 0.1 1 1 1
F 0(X,
25 Y ) 255 255 F (X, Y ) 1
25
n 0⇥ n
255 0.1 0 0.1 1
n 0⇥ n
1
X 0.08 0.12 0.08 0 0 0 0.9 1 1
0 0 230 255 255 0 0 0.9 1 1
m ⇥ m m ⇥ m
0.12 0.20 0.12 ⇥0 0.1 0.1 1 = 0.3
0.9
1
0 25 25 255 230 255 0 0.1 0.1 1 0.9 1
0.08 0.12 0.08 0 0 0.1 1 1 1
0
m 0
=25
5255 255 255 0
m 0
=0.1
5 1 1 1

Gaussian Filter (only)

Range Kernel Range * Domain Kernel

r = 0.45 0.1 0 0.1 1 1 1

0.98 0.98 0.2

multiply
0.08 0.12 0.02 X 0.11 0.16 0.03 0 0 0 0.9 1 1

1 1 0.1 0.12 0.20 0.01 0.16 0.26 0.01 ⇥

0 0.1 0.1 1 0.9
= 0.1 1

0.98 1 0.1 0.08 0.12 0.01 0.11 0.16 0.01 0 0 0.1 1 1 1

(differences based on Bilateral Filter

centre pixel)
90
Bilateral Filter

This example:
weights for point
on top of edge

Domain Kernel

Input Bilateral Filter Output

(domain * range)

Range Kernel Influence

Images from: Durand and Dorsey, 2002

91
Bilateral Filter Application: Denoising

Noisy Image Gaussian Filter Bilateral Filter

Slide Credit: Alexander Wong

92
Bilateral Filter Application: Cartooning

Original Image After 5 iterations of Bilateral Filter

Slide Credit: Alexander Wong

93
Bilateral Filter Application: Flash Photography

Non-flash images taken under low light conditions often suffer from excessive
noise and blur

But there are problems with flash images:

— colour is often unnatural
— there may be strong shadows or specularities

Idea: Combine flash and non-flash images to achieve better exposure and
colour balance, and to reduce noise

94
Bilateral Filter Application: Flash Photography
System using ‘joint’ or ‘cross’ bilateral filtering:

‘Joint’ or ‘Cross’ bilateral: Range kernel is computed using a separate

guidance image instead of the input image
Figure Credit: Petschnigg et al., 2004
95
Bilateral Filter: “Modern” take

[Link]
Morphology
128 Computer Vision: Algorithms and Applications (September 3, 2010 draft)

original
(a) dilate
(b) erode
(c) majority
(d) open
(e) close
(f)

Figure 3.21 Binary image morphology: (a) original image; (b) dilation; (c) erosion; (d)
majority; (e) opening; (f) closing. The structuring element for all examples is a 5 ⇥ 5 square.
Threshold function
The effects of majority are a subtle rounding of sharp corners. Opening fails to eliminate the
dot, since it is not wide enough.
in local structuring
element
operation, (
close(.) = 1
erode(dilate(.)) if f t,
etc., see Szeliski 3.3.2
✓(f, t) = (3.41)
0 else,
e.g., converting a scanned grayscale document into a binary image for further processing such
Aside: Linear Filter with ReLU

Result of: Linear Image Filtering After Non-linear ReLU

98
Summary
We covered two three non-linear filters: Median, Bilateral, ReLU

The median filter is a non-linear filter that selects the median in the
neighbourhood

The bilateral filter is a non-linear filter that considers both spatial distance
and range (intensity) distance, and has edge-preserving properties

Speeding-up Convolution can be achieved using separable filters or Fourier

Transforms if the filter and image are both large

Fourier Transforms give us a way to think about image processing

operations in Frequency Space, e.g., low pass filter = removing high
frequency components
99