Fundamentals of Computer Vision
Lecture 3
Overview of today’s lecture
• Image noise
• Linear shift-invariant image filtering.
• Convolution / Correlation
• Edge detection
Slide credits
Most of these slides were adapted directly from:
• Robert Colin (454, Fall 2019), Kris Kitani (15-463, Fall 2016), Ioannis Gkioulekas (16-385, Spring 2019)
Inspiration and some examples also came from:
• Fredo Durand (Digital and Computational Photography, MIT).
• Kayvon Fatahalian (15-769, Fall 2016).
Convolution for 1D continuous signals
Definition of filtering as convolution:
notice the flip
filtered signal filter input signal
Consider the box filter example:
1D continuous box filter
filtering output is a blurred version of g
Definition of filtering as convolution:
filtered image
notice the flip filter input image
Convolution for 2D discrete signals
Convolution for 2D discrete signals
If the filter is non-zero only within
The kernel we saw earlier is the 3×3 matrix representation of
Definition of filtering as convolution:
notice the flip filtered image filter input image
, then
.
Properties of Convolution
• Shift invariant:
• Operator behaves the same everywhere, i.e. the value of the output depends on the pattern in the image neighborhood, not the position of the neighborhood.
• Superposition:
• h*(f1+f2)=(h*f1)+ (h*f2)
Slide credit: Kristen Grauman
Properties of convolution
• Commutative: f*g=g*f
• Associative
(f * g) * h = f * (g * h)
• Distributesoveraddition
f * (g + h) = (f * g) + (f * h)
• Scalarsfactorout
kf * g = f * kg = k(f * g)
• Differentiationrule
• Identity:
unitimpulsee=[…,0,0,1,0,0,…]. f*e=f
Slide credit: Kristen Grauman
Definition of discrete 2D convolution:
notice the flip
Definition of discrete 2D correlation:
notice the lack of a flip
Convolution vs Correlation
• Most of the time won’t matter, because our kernels will be symmetric.
• Will be important when we discuss frequency-domain filtering.
Convolution vs Correlation
• Convolution:
• Flipthefilterinbothdimensions(bottomtotop,righttoleft) • Thenapplycross-correlation
H
F
Slide credit: Kristen Grauman
Notation for convolution operator
Filtering an Impulse Signal
What is the result of filtering the impulse signal (image) F with the arbitrary kernel H?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
?
a
b
c
d
e
f
g
h
i
Slide credit: Kristen Grauman
Filtering an impulse signal
What is the result of filtering the impulse signal (image) F with the arbitrary kernel H?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
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
a
b
c
d
e
f
g
h
i
Slide credit: Kristen Grauman
Filtering an impulse signal
What is the result of filtering the impulse signal (image) F with the arbitrary kernel H?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
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
f
a
b
c
d
e
f
g
h
i
Slide credit: Kristen Grauman
Filtering an impulse signal
What is the result of filtering the impulse signal (image) F with the arbitrary kernel H?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
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
f
e
a
b
c
d
e
f
g
h
i
Slide credit: Kristen Grauman
Filtering an impulse signal
What is the result of filtering the impulse signal (image) F with the arbitrary kernel H?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
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
f
e
d
a
b
c
d
e
f
g
h
i
Slide credit: Kristen Grauman
Filtering an impulse signal
What is the result of filtering the impulse signal (image) F with the arbitrary kernel H?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
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
i
h
g
0
f
e
d
0
c
b
a
a
b
c
d
e
f
g
h
i
Slide credit: Kristen Grauman
Separable filters
A 2D filter is separable if it can be written as the product of a “column” and a “row”.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
example: box filter
=
* column
row
What is the rank of this filter matrix? Why is this important?
Separable filters
A 2D filter is separable if it can be written as the product of a “column” and a “row”.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
example: box filter
=
column
*
row
2D convolution with a separable filter is equivalent to two 1D convolutions (with the “column” and “row” filters).
• Convolve all rows
• Convolve all columns
Separable filters
A 2D filter is separable if it can be written as the product of a “column” and a “row”.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
example: box filter
=
column
*
row
2D convolution with a separable filter is equivalent to two 1D convolutions (with the “column” and “row” filters).
If the image has M x M pixels and the filter kernel has size N x N: • What is the cost of convolution with a non-separable filter?
Separable filters
A 2D filter is separable if it can be written as the product of a “column” and a “row”.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
example: box filter
=
column
*
row
2D convolution with a separable filter is equivalent to two 1D convolutions (with the “column” and “row” filters).
If the image has M x M pixels and the filter kernel has size N x N:
• What is the cost of convolution with a non-separable filter? M2 x N2 • What is the cost of convolution with a separable filter?
Separable filters
A 2D filter is separable if it can be written as the product of a “column” and a “row”.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
example: box filter
=
column
*
row
2D convolution with a separable filter is equivalent to two 1D convolutions (with the “column” and “row” filters).
If the image has M x M pixels and the filter kernel has size N x N:
• What is the cost of convolution with a non-separable filter? M2 x N2
• What is the cost of convolution with a separable filter? 2 x N x M2
Separability
• Wecanfactoritintotwosteps:e.g.,
g
f
Slide credit: Kristen Grauman
f * (g * h) = (f * g) * h
h
Gaussian filter
• What if we want nearest neighboring pixels to have the most influence on the output?
This kernel is an approximation of a 2d Gaussian function:
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
1
2
4
2
1
2
1
• Weight falls off with distance from center pixel
• Theoretically infinite, in practice truncated to some maximum distance
• Any heuristics for selecting where to truncate? usually at 2-3σ
Gaussian filtering example
Gaussian vs box filtering
7×7 Gaussian
original
Which blur do you like better?
7×7 box
• Convolution with self is another Gaussian
Gaussian filter
Source: K. Grauman
*
=
Gaussian filters
• Variance of Gaussian: determines extent of smoothing
Slide credit: Kristen Grauman
σ = 2 with 30 x 30 kernel σ = 5 with 30 x 30 kernel
Gaussian filters
• Size of kernel or mask
• Note, Gaussian function has infinite support, but discrete filters use finite
kernels
Slide credit: Kristen Grauman
σ = 5 with 10 x 10 kernel σ = 5 with 30 x 30 kernel
Matlab
>> kernelsize = 10;
>> sigma = 5;
>> h = fspecial(‘gaussian’, kernelsize, sigma);
>> mesh(h);
>> imagesc(h);
>> outim = imfilter(im, h); % correlation >> imshow(outim);
In MATLAB, conv2 does convolution, filter2 does correlation. imfilter does either if specified, correlation by default (‘conv’, ‘corr’ option)
Slide credit: Kristen Grauman
im
outim
Smoothing with a Gaussian
Parameter σ is the “scale” / “width” / “spread” of the Gaussian kernel, and controls the amount of smoothing.
…
for sigma=1:3:10
h = fspecial(‘gaussian‘, hsize, sigma);
out = imfilter(im, h);
imshow(out);
pause;
end
Slide credit: Kristen Grauman
Predict the outputs using correlation filtering
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
*
=?
*
=?
*[
–
]
0
0
0
0
2
0
0
0
0
1
1
1
1
1
1
1
1
1
=?
Slide credit: Kristen Grauman
Practice with linear filters
0
0
0
0
1
0
0
0
0
?
Slide credit: David Lowe
Original
Practice with linear filters
0
0
0
0
1
0
0
0
0
Slide credit: David Lowe
Original
Filtered
(no change)
Practice with linear filters
0
0
0
0
0
1
0
0
0
?
Slide credit: David Lowe
Original
Practice with linear filters
0
0
0
0
0
1
0
0
0
Slide credit: David Lowe
Original
Shifted left
by 1 pixel with correlation
Practice with linear filters
1
1
1
1
1
1
1
1
1
?
Slide credit: David Lowe
Original
Practice with linear filters
1
1
1
1
1
1
1
1
1
Slide credit: David Lowe
Original
Blur (with a box filter)
Practice with linear filters
[-]? Original
0
0
0
0
2
0
0
0
0
1
1
1
1
1
1
1
1
1
Slide credit: David Lowe
Practice with linear filters
-]
[
0
0
0
0
2
0
0
0
0
1
1
1
1
1
1
1
1
1
Original
• Do nothing for flat areas
• Stress intensity peaks
Sharpening filter:
accentuates differences with local average
Slide credit: David Lowe
Filtering examples: sharpening
Slide credit: Kristen Grauman
Do not overdo it with sharpening
original sharpened oversharpened
• What does blurring take away?
–
=
original
Let’s add it back:
smoothed (5×5)
detail
Sharpening revisited
original
detail
sharpened
+α
=
Source: S. Lazebnik
Sharpen filter
image
blurred image
unit impulse (identity)
scaled impulse
Gaussian
Laplacian of Gaussian
Slide credit: Kristen Grauman
Median filter
• No new pixel values introduced
• Removes spikes: good for impulse, salt & pepper noise
• Non-linear filter
Salt and pepper noise
Median filtered
Median filter
Slide credit: Martial Hebert
Plots of a row of the image
Matlab: output im = medfilt2(im, [h w]);;
Median filter
• Medianfilterisedgepreserving
Slide credit: Kristen Grauman
Edge Detection
Edge detection
• Goal: map image from 2D array of pixels to a set of curves or line segments or contours.
• Why?
Figure from J. Shotton et al., PAMI 2007
• Main idea: look for strong gradients, post-process Slide credit: Kristen Grauman
Images as functions…
• Edges look like steep cliffs
What causes an edge?
Reflectance change: appearance information, texture
Depth discontinuity: object boundary
Change in surface orientation: shape
Cast shadows
Slide credit: Kristen Grauman
Detecting edges
How would you go about detecting edges in an image (i.e., discontinuities in a function)?
ü You take derivatives: derivatives are large at discontinuities.
How do you differentiate a discrete image (or any other discrete signal)? ü You use finite differences.
Edges/gradients and invariance
Slide credit: Kristen Grauman
Image gradient
• Thegradientofanimage:
The gradient points in the direction of most rapid increase in intensity
The edge strength is given by the gradient magnitude:
The gradient direction is given by:
Source: Steve Seitz
Derivatives and Edges
An edge is a place of rapid change in the image intensity function.
intensity function
image (along horizontal scanline) first derivative
Slide credit: Svetlana Lazebnik
edges correspond to extrema of derivative
Finite differences
High-school reminder: definition of a derivative using forward difference
Finite differences
High-school reminder: definition of a derivative using forward difference
Alternative: use central difference
For discrete signals: Remove limit and set h = 2
What convolution kernel does this correspond to?
Finite differences
High-school reminder: definition of a derivative using forward difference
Alternative: use central difference
For discrete signals: Remove limit and set h = 2
1D derivative filter
1
0
-1
Derivative of Gaussian filters
(IÄg)Äh =IÄ(gÄh)
[]
➠
0.0030 0.0133 0.0219 0.0133 0.0030
Ä[1 -1] 0.0030 0.0133 0.0219 0.0133 0.0030
0.0133 0.0596 0.0983 0.0596 0.0133
0.0219 0.0983 0.1621 0.0983 0.0219
0.0133 0.0596 0.0983 0.0596 0.0133
Derivative operator
Slide credit: Kristen Grauman
Derivative of Gaussian filter
x-direction
y-direction
Partial derivatives of an image
¶f (x, y) ¶x
¶f (x, y) ¶y
? or
-1
1
1
-1
-1
1
Slide credit: Kristen Grauman
Which shows changes with respect to x?
The Sobel filter
1
0
-1
2
0
-2
1
0
-1
1
2
1
1
0
-1
Sobel filter
=
What filter is this?
*
1D derivative filter
The Sobel filter
1
0
-1
2
0
-2
1
0
-1
1
2
1
1
0
-1
=
*
1D derivative filter
Sobel filter
In a 2D image, does this filter responses along horizontal or vertical lines?
Blurring
The Sobel filter
1
2
1
1
0
-1
2
0
-2
1
0
-1
1
0
-1
Sobel filter
Blurring
=
*
1D derivative filter
Does this filter return large responses on vertical or horizontal lines?
Horizontal Sober filter:
The Sobel filter
1
0
-1
2
0
-2
1
0
-1
1
2
1
1
0
-1
* What does the vertical Sobel filter look like?
=
Horizontal Sober filter:
The Sobel filter
1
0
-1
2
0
-2
1
0
-1
1
2
1
1
0
-1
Sx
Vertical Sobel filter:
Sy
=
*
1
2
1
0
0
0
-1
-2
-1
1
0
-1
1
2
1
=
*
>> My = fspecial(‘sobel’);
>> outim = imfilter(double(im), Sy); >> imagesc(outim);
>> colormap gray;
im
The Sobel operator
Common approximation of derivative of Gaussian
• ThestandarddefinitionoftheSobeloperatoromitsthe1/8term – doesn’t make a difference for edge detection
– the 1/8 term is needed to get the right gradient magnitude
>> My = fspecial(‘sobel’);
>> outim = imfilter(double(im), Sy); >> imagesc(outim);
>> colormap gray;
-1
0
1
-2
0
2
-1
0
1
1
2
1
0
0
0
-1
-2
-1
im
Sobel filter example
original which Sobel filter? which Sobel filter?
Sobel filter example
original horizontal Sobel filter vertical Sobel filter
original
Sobel filter example
horizontal Sobel filter
vertical Sobel filter
Several derivative filters
Sobel Scharr
1
0
-1
2
0
-2
1
0
-1
1
2
1
0
0
0
-1
-2
-1
3
0
-3
10
0
-10
3
0
-3
3
10
3
0
0
0
-3
-10
-3
1
0
-1
1
0
-1
1
0
-1
1
1
1
0
0
0
-1
-1
-1
0
1
-1
0
1
0
0
-1
Prewitt Roberts
• How are the other filters derived and how do they relate to the Sobel filter? • How would you derive a derivative filter that is larger than 3×3?