Lecture 2: Image filtering
• PS1 due next Tuesday
• Updated office hours next week, due to
holiday. New times will be on Piazza.
• Questions?
Recall last week…
Extra
edges
Missing
edges
Input image Edges
In this lecture
What other transformations can we do?
Filtering
g[n, m] f[n, m]
Our goal: remove unwanted
sources of variation, and keep the
information relevant for whatever
task we need to solve.
Source: Torralba, Freeman, Isola
Linear filtering
Very general! For a filter, H, to be linear, it has to satisfy:
H(a[m, n] + b[m, n]) + H(a[m, n]) + H(b[m, n])
+ b[m, n]) + H(a[m, n]) + H(b[m, n])
H(Ca[m, n]) = CH(a[m, n])
H(Ca[m, n]) = CH(a[m, n])
<latexit sha1_base64="bwjokjlr5CKTUP0e+sMmFK8tILY=">AAACMXicbZDLSgMxFIYz9VbrbdSlm2ARWpQyo4JuhGI3XVawF+gMJZOmbWiSGZKMUIa+khvfRNx0oYhbX8K0nYpWDwS+8/85JOcPIkaVdpyJlVlZXVvfyG7mtrZ3dvfs/YOGCmOJSR2HLJStACnCqCB1TTUjrUgSxANGmsGwMvWbD0QqGop7PYqIz1Ff0B7FSBupY1erBdTmZ8KHpzCYQdHQXISLJkgbz8tVCxX47d3AymK82LHzTsmZFfwLbgp5kFatYz973RDHnAiNGVKq7TqR9hMkNcWMjHNerEiE8BD1SdugQJwoP5ltPIYnRunCXijNERrO1J8TCeJKjXhgbnKkB2rZm4r/ee1Y9679hIoo1kTg+UO9mEEdwml8sEslwZqNDCAsqfkrxAMkEdYm5JwJwV1e+S80zkvuRcm5u8yXb9M4suAIHIMCcMEVKIMqqIE6wOARvIBX8GY9WRPr3fqYX81Y6cwh+FXW5xflFqLC</latexit>
Source: Torralba, Freeman, Isola
Linear filtering
A linear filter in its most general form can be written as (for a 1D signal of length N):
In matrix form:
Source: Torralba, Freeman, Isola
Why handle each spatial position differently?
Want translation invariance!
Photo by Fredo Durand, slide by Torralba, Freeman, Isola
Image denoising
Photo by Fredo Durand
Moving average
• Let’s replace each pixel with a weighted
average of its neighborhood
• The weights are called the filter kernel
• What are the weights for the average of a
3x3 neighborhood?
1 1 1
1 1 1
1 1 1
“box filter”
Source: D. Lowe
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 ?
0 90 90 90 90 0 0
0 90 90 90 90 0 0
0 90 0 90 90 0 0
0 90 90 90 90 0 0
0 0 0 0 0 0 0
Input Output
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 40
0 90 90 90 90 0 0
0 90 90 90 90 0 0
0 90 0 90 90 0 0
0 90 90 90 90 0 0
0 0 0 0 0 0 0
Input Output
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 40 ?
0 90 90 90 90 0 0
0 90 90 90 90 0 0
0 90 0 90 90 0 0
0 90 90 90 90 0 0
0 0 0 0 0 0 0
Input Output
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 40 60
0 90 90 90 90 0 0
0 90 90 90 90 0 0
0 90 0 90 90 0 0
0 90 90 90 90 0 0
0 0 0 0 0 0 0
Input Output
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 40 60
0 90 90 90 90 0 0
0 90 90 90 90 0 0
0 90 0 90 90 0 0 ?
0 90 90 90 90 0 0
0 0 0 0 0 0 0
Input Output
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 40 60
0 90 90 90 90 0 0
0 90 90 90 90 0 0
0 90 0 90 90 0 0 80
0 90 90 90 90 0 0
0 0 0 0 0 0 0
Input Output
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 40 60 60 40 20
0 90 90 90 90 0 0 60 90 60 40 20
0 90 90 90 90 0 0 50 80 80 60 30
0 90 0 90 90 0 0 50 80 80 60 30
0 90 90 90 90 0 0 30 50 50 40 20
0 0 0 0 0 0 0
Input Output
Moving average
Filter kernel
0 0 0 0 0 0 0
0 90 90 90 90 0 0 40 60 60 40 20
0 90 90 90 90 0 0 60 90 60 40 20
0 90 90 90 90 0 0 50 80 80 60 30
0 90 0 90 90 0 0 ? 50 80 80 60 30
0 90 90 90 90 0 0 30 50 50 40 20
0 0 0 0 0 0 0
Input Output
Handling boundaries
Source: Torralba, Freeman, Isola
Handling boundaries
Zero padding
11x11 box
Source: Torralba, Freeman, Isola
Handling boundaries
Input
Output
Error
Source: Torralba, Freeman, Isola
Moving average
Filter kernel
0 0 0 0 0 0 0 0
0 90
0 90 90 90 90
0 0 0 40 60 60 40 20
0 90
0 90 90 90 90
0 0 0 60 90 60 40 20
0 90
0 90 90 90 90
0 0 0 50 80 80 60 30
0 90
0 90
0 90
0 90 90
0 0 0 30 50 80 80 60 30
0 90
0 90 90 90 90
0 0 0 30 50 50 40 20
0 0 0 0 0 0 0 0
Input Output
Convolution
• Let h be the image and g be the kernel. The output of
convolving h with g is:
Convention: h
kernel is “flipped”
Source: F. Durand
Properties of the convolution
Commutative
Associative
Distributive with respect to the sum
Why flip the kernel?
Indexes go backward!
Cross correlation
No flipping!
• Sometimes called just correlation
• Neither associative nor commutative
• In the literature, people often just call both “convolution”
• Filters often symmetric, so won’t matter
Convolutional neural networks
• Neural network with specialized connectivity structure
• Mostly just convolutions!
(LeCun et al. 1989)
Source: Torralba, Freeman, Isola
Filtering examples
Practice with linear filters
0 0 0
0 1 0 ?
0 0 0
Original
Source: D. Lowe
Practice with linear filters
0 0 0
0 1 0
0 0 0
“Impulse”
Original Filtered
(no change)
Source: D. Lowe
Practice with linear filters
0 0 0
0 0 1 ?
0 0 0
Original
“Translated
Impulse”
Source: D. Lowe
Practice with linear filters
0 0 0
0 0 1
0 0 0
Original Shifted left
By 1 pixel
Source: D. Lowe
Practice with linear filters
1 1 1
1 1 1 ?
1 1 1
Original
Source: D. Lowe
Practice with linear filters
1 1 1
1 1 1
1 1 1
Original Blur (with a
box filter)
Source: D. Lowe
Practice with linear filters
0 0 0 1 1 1
0 2 0
0 0 0
- 1 1 1
1 1 1
?
(Note that filter sums to 1)
Original
Source: D. Lowe
Practice with linear filters
0 0 0 1 1 1
0 2 0
0 0 0
- 1 1 1
1 1 1
Original Sharpening filter
- Accentuates differences with
local average
Source: D. Lowe
Sharpening
Source: D. Lowe
Practice with linear filters
?
Original
Can you do this?
Rectangular filter
⊗ =
h[m,n]
€
f[m,n]
g[m,n]
Source: Torralba, Freeman, Isola
Rectangular filter
⊗ =
h[m,n]
€
f[m,n]
g[m,n]
Source: Torralba, Freeman, Isola
“Naturally” occurring filters
Input image Motion blur
Source: Torralba, Freeman, Isola
“Naturally” occurring filters
Input image Convolution weights Convolution output
Source: Torralba, Freeman, Isola
Camera shake
(from Fergus et al, 2007)
Source: Torralba, Freeman, Isola
Blur occurs in many natural situations
Source: Torralba, Freeman, Isola
Smoothing with box filter revisited
• What’s wrong with this picture?
• What’s the solution?
Source: D. Forsyth
Smoothing with box filter revisited
• What’s wrong with this picture?
• What’s the solution?
• To eliminate edge effects, weight contribution of
neighborhood pixels according to their closeness to the
center
“fuzzy blob” Source: S. Lazebnik
Gaussian kernel
σ = 2 with 30 x 30 σ = 5 with 30 x 30
kernel kernel
• Constant factor in front makes kernel sum to 1 (can
also omit it and just divide by sum of filter weights).
Source: K. Grauman
Gaussian vs. box filtering
Source: S. Lazebnik
Gaussian standard deviation
49
σ=2 σ=4 σ=8
Source: Torralba, Freeman, Isola
Gaussian filters
• Convolution with self is another Gaussian
• Can smooth with small-σ kernel, repeat, get same result as
larger-σ
• Convolving two times with Gaussian kernel with std. dev. σ
is same as convolving once with kernel with std. dev. σ 2
I blur(blur(I)) blur(blur(blur(I))) blur(blur(blur(blur(I))))
Source: K. Grauman
Gaussian filters
• It’s a separable kernel
• Blur with 1D Gaussian in one direction, then the other.
• Faster to compute. O(n) time for an n*n kernel instead of O(n )
2
• Learn more about this in Problem Set 1!
I blurx(I) blury(blurx(I))
Edges: recall last lecture…
Image gradient:
Approximation image derivative:
I(x,y)
Edge strength
Edge orientation:
Edge normal:
Slide credit: Antonio Torralba
Discrete derivatives
Source: Torralba, Freeman, Isola
[-1 1]
[-1, 1] =
h[m,n]
f[m,n]
g[m,n]
Source: Torralba, Freeman, Isola
[-1 1] T
[-1, 1]T =
h[m,n]
f[m,n]
g[m,n]
Source: Torralba, Freeman, Isola
Can we recover the image?
Source: Torralba, Freeman, Isola
Reconstruction from 2D derivatives
In 2D, we have multiple derivatives (along n and m)
= [-1 1]
c
c
[-1 1]T
c
and we compute the pseudo-inverse of the full matrix.
Source: Torralba, Freeman, Isola
Reconstruction from 2D derivatives
[1 -1]
[1 -1]T
Source: Torralba, Freeman, Isola
Editing the edge image
[1 -1]
[1 -1]T
Source: Torralba, Freeman, Isola
Thresholding edges
Source: Torralba, Freeman, Isola
Issues with derivative filters
[1 -1]
• Sensitive to edges at small spatial scales
• Also sensitive to noise
• You'll see this in Problem Set 1
Why is this happening?
Noisy input image
Where is the edge?
Source: S. Seitz
Solution: smooth first
f
f*h
To find edges, look for peaks in
Source: S. Seitz
Derivative of Gaussian filter
Gaussian Derivative of Gaussian (x)
Source: N. Snavely
Derivative of Gaussian filter
x-direction y-direction
Source: N. Snavely
Derivatives of Gaussians: Scale
σ=2 σ=4 σ=8
Source: Torralba, Freeman, Isola
Picks up larger-scale edges
Source: Torralba, Freeman, Isola
Computing a directional derivative
(From multivariable calculus)
Directional derivative is a linear
=? combination of partial derivatives
+ = Source: N. Snavely
Derivative of Gaussian filter
x-direction y-direction
+ =
Source: N. Snavely
The Sobel operator
• Common approximation to derivative of Gaussian
• Where does this come from?
Source: N. Snavely
An approximation to the Gaussian
• Apply filter to itself repeatedly.
• Converges to Gaussian, due to Central Limit Theorem
b1 = [1 1]
b2 = [1 1] [1 1] = [1 2 1]
b3 = [1 1] [1 1] [1 1] = [1 3 3 1]
Source: Torralba, Freeman, Isola
Binomial filter
72
Sobel operator: example
Source: N. Snavely / Wikipedia
Next class: frequency