Fundamentals of Computer Vision
Lecture 6
• Frequency-domain filtering.
• Sampling and Aliasing.
• Gaussian image pyramid.
• Finding boundaries.
• Line fitting.
• Line parameterizations.
• Hough transform.
• Hough circles.
• Some applications
Overview of today’s lecture
Slide credits
Most of these slides were adapted from:
• Kris Kitani (15-463, Fall 2016), Ioannis Gkioulekas (16-385, Spring 2019). Some slides were inspired or taken from:
• Fredo Durand (MIT).
• James Hays (Georgia Tech).
Revisiting blurring
Why does the Gaussian give a nice smooth image, but the square filter give edgy artifacts?
Gaussian filter
Box filter
Gaussian blur
Box blur
More filtering examples
? ?
filters shown in frequency- domain
More filtering examples
low-pass
filters shown band-pass in frequency-
domain
More filtering examples
high-pass
?
More filtering examples
high-pass
More filtering examples
original image low-pass filter
frequency magnitude
?
More filtering examples
original image low-pass filter
frequency magnitude
More filtering examples
original image high-pass filter
frequency magnitude
?
More filtering examples
original image high-pass filter
frequency magnitude
More filtering examples
original image band-pass filter
frequency magnitude
More filtering examples
original image band-pass filter
frequency magnitude
More filtering examples
original image band-pass filter
frequency magnitude
More filtering examples
original image band-pass filter
frequency magnitude
Image Downsampling
Image Scaling
This image is too big to fit on the screen. How can we generate a half-sized version?
Source: S. Seitz
Image sub-sampling
delete even rows, delete even columns
Throw away every other row and column to create a 1/2 size image
– called image sub-sampling
1/4
1/8
Source: S. Seitz
Naïve Image Downsampling
1/2 1/4 (2x zoom) 1/8 (4x zoom)
What is the 1/8 image so pixelated (and do you know what this effect is called)?
Subsampling by a factor of 2
Throw away every other row and column to create a 1/2 size image
Derek Hoiem
Image sub-sampling
Source: F. Durand
Reminder
Images are a discrete, or sampled, representation of a continuous world
Downsample
However: Subsampling is a bad idea unless you have previously blurred/smoothed the image! (because it leads to aliasing!) What is aliasing?!
Very simple example: a sine wave
Sampling
How would you discretize this signal?
Very simple example: a sine wave
Sampling
Very simple example: a sine wave
Sampling
How many samples should I take?
Can I take as many samples as I want?
Very simple example: a sine wave
Sampling
How many samples should I take?
Can I take as few samples as I want?
Undersampling
Very simple example: a sine wave
Unsurprising effect: information is lost.
Undersampling
Very simple example: a sine wave
Fancy term for: Undersampling can disguise a signal as one of a lower frequency
Unsurprising effect: information is lost.
Surprising effect: can confuse the signal with one of lower frequency.
Undersampling
Very simple example: a sine wave
Unsurprising effect: information is lost.
Surprising effect: can confuse the signal with one of lower frequency. Note: we could always confuse the signal with one of higher frequency.
Aliasing
Fancy term for: Undersampling can disguise a signal as one of a lower frequency
Unsurprising effect: information is lost.
Surprising effect: can confuse the signal with one of lower frequency. Note: we could always confuse the signal with one of higher frequency.
Aliasing in textures
Temporal aliasing
Temporal aliasing
Temporal aliasing
Anti-aliasing
How would you deal with aliasing?
Anti-aliasing
How would you deal with aliasing? Approach 1: Oversample the signal
Anti-aliasing in textures
aliasing artifacts
anti-aliasing by oversampling
Anti-aliasing
How would you deal with aliasing? Approach 1: Oversample the signal
Approach 2: Smooth the signal
• Remove some of the detail effects that cause aliasing.
• Lose information, but better than aliasing artifacts.
How would you smooth a signal?
Better image Downsampling
Apply a smoothing filter first, then throw away half the rows and columns
1/2
Gaussian filter delete even rows delete even columns
Gaussian filter delete even rows delete even columns
1/4
1/8
Better image downsampling
1/2 1/4 (2x zoom) 1/8 (4x zoom)
Naïve image downsampling
1/2 1/4 (2x zoom) 1/8 (4x zoom)
Anti-aliasing
Question 1: How much smoothing do I need to do to avoid aliasing? Question 2: How many samples do I need to take to avoid aliasing? Answer to both: Enough to reach the Nyquist limit.
The Nyquist-Shannon sampling theorem
A continuous signal can be perfectly reconstructed from its discrete version using linear interpolation, if sampling occurred with frequency:
This is called the Nyquist frequency
Equivalent reformulation: When downsampling, aliasing does not occur if samples are taken at the Nyquist frequency or higher.
Gaussian Image Pyramid
Form a Multi-Resolution Representation
original
sigma = 1
sigma = 3
sigma = 10
Variable frequency sensitivity
Experiment: Where do you see the stripes?
frequency
contrast
Variable frequency sensitivity
Campbell-Robson contrast sensitivity curve
Our eyes are sensitive to mid-range frequencies
• Early processing in humans filters for various orientations and scales of frequency
• Perceptual cues in the mid frequencies dominate perception
frequency
contrast
Pyramid Representations
Because a large amount of smoothing limits the frequency of features in the image, we do not need to keep all the pixels around!
Strategy: progressively reduce the number of pixels as we smooth more and more.
Leads to a “pyramid” representation if we subsample at each level.
Gaussian Pyramid
• Synthesis: Smooth image with a Gaussian and downsample. Repeat.
• Gaussian is used because it is self-reproducing (enables incremental smoothing).
• Computational cost typically dominated by convolution at the two lowest (highest resolution) levels.
Gaussian pyramid
How does the Nyquist-Shannon theorem relate to the Gaussian pyramid?
Gaussian pyramid
How does the Nyquist-Shannon theorem relate to the Gaussian pyramid?
• Gaussian blurring is low-pass filtering.
• By blurring we try to sufficiently decrease
the Nyquist frequency to avoid aliasing.
Reminder
• Cascaded Gaussians
– Repeated convolution by a smaller Gaussian to simulate effects of a larger one.
• G*(G*f) = (G*G)*f [associativity]
Gaussian Pyramid
Low res
High res
Emphasis: Smaller Images have Lower Resolution
Low resolution
G =(G *gaussian)¯2
Gaussian Pyramid
4 3 blur
G =(G *gaussian)¯2
32
blur
G =(G *gaussian)¯2 21
blur
G =(G *gaussian)¯2 1 0
High resolution
G0 =Image blur
Laplacian image pyramid
At each level, retain the residuals instead of the blurred images themselves.
Can we reconstruct the original image using the pyramid?
Laplacian image pyramid
At each level, retain the residuals instead of the blurred images themselves.
Can we reconstruct the original image using the pyramid?
• Yes we can!
What do we need to store to be able to reconstruct the original image?
Constructing a Laplacian pyramid
It’s a Gaussian pyramid.
Algorithm
repeat:
filter
compute residual
subsample until min resolution
reached
What do we need to construct the original image?
What do we need to construct the original image?
(1) residuals
What do we need to construct the original image?
(2) smallest image
(1) residuals
(2) smallest image
Algorithm
Reconstructing the original image
repeat: upsample
sum with residual
until min resolution reached
(1) residuals
Subsampling away…
f0 –l0 =h0
f1 –l1 =h1
{f0 , f1 , …, fn}
= Gaussian pyramid
{h0 , h1 , …, hn} = Laplacian pyramid
Derek Hoiem
http://sepwww.stanford.edu/~morgan/texturematch/paper_html/node3.html
h2 = f2
L =G -expand(G ) ii i+1
G =L +expand(G ) ii i+1
G0
G L=G nnn
G2 – = L2
G1 – = L1
-=
L0
The Laplacian Pyramid
Gaussian Pyramid Laplacian Pyramid
What are image pyramids used for?
image blending
image compression
multi-scale texture mapping
multi-scale detection
denoising
multi-scale registration
Hough Transform
Now: Fitting
• Wanttoassociateamodelwithobservedfeatures
[Fig from Marszalek & Schmid, 2007] For example, the model could be a line, a circle, or an arbitrary shape.
Kristen Grauman
Fitting: Main idea
• Choose a parametric model to represent a set of features
• Membership criterion is not local
• Can’t tell whether a point belongs to a given model just by looking at that point
• Three main questions:
• What model represents this set of features best?
• Which of several model instances gets which feature?
• How many model instances are there?
• Computational complexity is important
• It is infeasible to examine every possible set of parameters and every possible combination of features
Slide credit: L. Lazebnik
Where are the object boundaries?
Human annotated boundaries
edge detection
Applications
Autonomous Vehicles (lane line detection)
tissue engineering (blood vessel counting)
behavioral genetics (earthworm contours)
Autonomous Vehicles (semantic scene segmentation)
Computational Photography (image inpainting)
Example: Line fitting
• Whyfitlines?
Many objects characterized by presence of straight lines
• Wait, why aren’t we done just by running edge detection? Kristen Grauman
Difficulty of line fitting
• Extra edge points (clutter), multiple models:
– which points go with which line, if any?
• Only some parts of each line detected, and some parts are missing:
– how to find a line that bridges missing evidence?
• Noise in measured edge points, orientations:
– how to detect true underlying parameters?
Kristen Grauman
Voting
• It’snotfeasibletocheckallcombinationsoffeaturesbyfittingamodelto each possible subset.
• Votingisageneraltechniquewhereweletthefeaturesvoteforallmodels that are compatible with it.
• Cyclethroughfeatures,castvotesformodelparameters. • Lookformodelparametersthatreceivealotofvotes.
• Noise&clutterfeatureswillcastvotestoo,buttypicallytheirvotesshould be inconsistent with the majority of “good” features.
Kristen Grauman
Fitting lines: Hough transform
• Given points that belong to a line, what is the line?
• How many lines are there?
• Which points belong to which lines?
• Hough Transform is a voting technique that can be used to answer all of these questions.
Main idea:
1. Record vote for each possible line on which each edge point lies.
2. Look for lines that get many votes.
Kristen Grauman
Slope intercept form
slope y-intercept
Double intercept form
x-intercept y-intercept Derivation:
(Similar slope)
Derivation:
Normal Form
plug into:
Image and Parameter Space
variables
parameters
Image space
Image and Parameter Space
A line in the image corresponds to a point in Hough space
variables
parameters
variables
parameters
a line becomes a point
Image space
Parameter space
Image and Parameter Space
variables
parameters
What would a point in image space become in parameter space?
Image space
Image and Parameter Space
variables
parameters
variables
parameters
a point becomes a line
Image space
Parameter space
Image and Parameter Space
variables
parameters
variables
parameters
two points become
?
Image space
Parameter space
Image and Parameter Space
variables
parameters
variables
parameters
Image space
Parameter space
two points become
?
Image and Parameter Space
variables
parameters
variables
parameters
three points become
?
Image space
Parameter space
Image and Parameter Space
variables
parameters
variables
parameters
three points become
?
Image space
Parameter space
Image and Parameter Space
variables
parameters
variables
parameters
four points become
?
Image space
Parameter space
Image and Parameter Space
variables
parameters
variables
parameters
four points become
?
Image space
Parameter space
How would you find the best fitting line?
Image space Parameter space
Is this method robust to measurement noise? Is this method robust to outliers?
Basic reading:
• Szeliski textbook, Sections 3.4, 3.5
References
Additional reading:
• Burt and Adelson, “The Laplacian Pyramid as a Compact Image Code,” IEEE ToC 1983.
The original Laplacian pyramid paper.
• Hubel and Wiesel, “Receptive fields, binocular interaction and functional architecture in the cat’s
visual cortex,” The Journal of Physiology 1962
A foundational paper describing information processing in the visual system, including the
different types of filtering it performs;; Hubel and Wiesel won the Nobel Prize in Medicine in 1981 for the discoveries described in this paper.