COMPUTER VISION
Le Thanh Ha, Ph.D
Assoc. Prof. at University of Engineering and Technology,
Vietnam National University
[email protected];
[email protected]; 0983 692 592
Linear filtering
Motivation: Noise reduction
• Given a camera and a still scene, how can
you reduce noise?
Take lots of images and average them!
What’s the next best thing?
Source: S. Seitz
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 a 3x3 moving average?
1 1 1
1 1 1
1 1 1
“box filter”
Source: D. Lowe
Defining convolution
• Let f be the image and g be the kernel. The output of
convolving f with g is denoted f * g.
( f g )[m, n] = f [m − k , n − l ] g[k , l ]
k ,l
• Convention: kernel is “flipped”
• MATLAB: conv2 vs. filter2 (also imfilter) Source: F. Durand
Key properties
• Linearity: 𝑓𝑖𝑙𝑡𝑒𝑟(𝑓1 + 𝑓2) = 𝑓𝑖𝑙𝑡𝑒𝑟(𝑓1) + 𝑓𝑖𝑙𝑡𝑒𝑟(𝑓2)
• Shift invariance: same behavior regardless of pixel location:
𝑓𝑖𝑙𝑡𝑒𝑟(𝑠ℎ𝑖𝑓𝑡(𝑓)) = 𝑠ℎ𝑖𝑓𝑡(𝑓𝑖𝑙𝑡𝑒𝑟(𝑓))
• Theoretical result: any linear shift-invariant operator can be
represented as a convolution
Properties in more detail
• Commutative: 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎
– Conceptually no difference between filter and signal
• Associative: 𝑎 ∗ (𝑏 ∗ 𝑐) = (𝑎 ∗ 𝑏) ∗ 𝑐
– Often apply several filters one after another: (((𝑎 ∗ 𝑏1) ∗ 𝑏2) ∗ 𝑏3)
– This is equivalent to applying one filter: 𝑎 ∗ (𝑏1 ∗ 𝑏2 ∗ 𝑏3)
• Distributes over addition: 𝑎 ∗ (𝑏 + 𝑐) = (𝑎 ∗ 𝑏) + (𝑎 ∗ 𝑐)
• Scalars factor out: 𝑘𝑎 ∗ 𝑏 = 𝑎 ∗ 𝑘𝑏 = 𝑘(𝑎 ∗ 𝑏)
• Identity: unit impulse 𝑒 = [… , 0, 0, 1, 0, 0, … ], 𝑎 ∗ 𝑒 = 𝑎
Annoying details
• What is the size of the output?
• MATLAB: filter2(g, f, shape)
– shape = ‘full’: output size is sum of sizes of f and g
– shape = ‘same’: output size is same as f
– shape = ‘valid’: output size is difference of sizes of f and g
g g g g
g g
f f f
g g
g g
g g
Annoying details
• What about near the edge?
– the filter window falls off the edge of the
image
– need to extrapolate
– methods:
• clip filter (black)
• wrap around
• copy edge
• reflect across edge
Source: S. Marschner
Annoying details
• What about near the edge?
– the filter window falls off the edge of the image
– need to extrapolate
– methods (MATLAB):
• clip filter (black): imfilter(f, g, 0)
• wrap around: imfilter(f, g, ‘circular’)
• copy edge: imfilter(f, g, ‘replicate’)
• reflect across edge: imfilter(f, g, ‘symmetric’)
Source: S. Marschner
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
Original Filtered
(no change)
Source: D. Lowe
Practice with linear filters
?
0 0 0
0 0 1
0 0 0
Original
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 1 1 1
0 0 0 1 1 1
Original Sharpening filter
- Accentuates differences
with local average
Source: D. Lowe
Sharpening
Source: D. Lowe
Smoothing with box filter revisited
• Smoothing with an average actually doesn’t compare at all well with a defocused
lens
• Most obvious difference is that a single point of light viewed in a defocused lens
looks like a fuzzy blob; but the averaging process would give a little square
Source: D. Forsyth
Smoothing with box filter revisited
• Smoothing with an average actually doesn’t compare at all well with a defocused
lens
• Most obvious difference is that a single point of light viewed in a defocused lens
looks like a fuzzy blob; but the averaging process would give a little square
• Better idea: to eliminate edge effects, weight contribution of neighborhood pixels
according to their closeness to the center, like so:
“fuzzy blob”
Gaussian Kernel
0.003 0.013 0.022 0.013 0.003
0.013 0.059 0.097 0.059 0.013
0.022 0.097 0.159 0.097 0.022
0.013 0.059 0.097 0.059 0.013
0.003 0.013 0.022 0.013 0.003
5 x 5, = 1
• Constant factor at front makes volume sum to 1 (can be ignored, as
we should re-normalize weights to sum to 1 in any case)
Source: C. Rasmussen
Choosing kernel width
• Gaussian filters have infinite support, but discrete filters use
finite kernels
Source: K. Grauman
Choosing kernel width
• Rule of thumb: set filter half-width to about
3σ
Example: Smoothing with a Gaussian
Mean vs. Gaussian filtering
Gaussian filters
• Remove “high-frequency” components from the image (low-
pass filter)
• Convolution with self is another Gaussian
– So can smooth with small-width kernel, repeat, and get same result
as larger-width kernel would have
– Convolving two times with Gaussian kernel of width σ is same as
convolving once with kernel of width σ√2
• Separable kernel
– Factors into product of two 1D Gaussians
Source: K. Grauman
Separability of the Gaussian filter
Source: D. Lowe
Separability example
2D convolution
(center location only)
The filter factors
into a product of 1D
filters:
Perform convolution
along rows: * =
Followed by convolution =
along the remaining column: *
Source: K. Grauman
Separability
• Why is separability useful in practice?
Noise
• Salt and pepper noise:
contains random
occurrences of black and
white pixels
• Impulse noise: contains
random occurrences of
white pixels
• Gaussian noise: variations in
intensity drawn from a
Gaussian normal distribution
Source: S. Seitz
Gaussian noise
• Mathematical model: sum of
many independent factors
• Good for small standard
deviations
• Assumption: independent,
zero-mean noise
Source: M. Hebert
Reducing Gaussian noise
Smoothing with larger standard deviations suppresses noise,
but also blurs the image
Reducing salt-and-pepper noise
3x3 5x5 7x7
• What’s wrong with the results?
Alternative idea: Median filtering
• A median filter operates over a
window by selecting the median
intensity in the window
• Is median filtering linear?
Source: K. Grauman
Median filter
• What advantage does
median filtering have over
Gaussian filtering?
– Robustness to outliers
Source: K. Grauman
Median filter
Salt-and-pepper noise Median filtered
Source: M. Hebert
Median vs. Gaussian filtering
3x3 5x5 7x7
Gaussian
Median
Sharpening revisited
• What does blurring take away?
– =
original smoothed (5x5) detail
Let’s add it back:
+α =
original detail sharpened
Unsharp mask filter
f + ( f − f g ) = (1 + ) f − f g = f ((1 + )e − g )
image blurred unit impulse
image (identity)
unit impulse
Gaussian Laplacian of Gaussian
