Fundamentals of Computer Vision
Lecture 7
• Hough transform.
• Hough circles.
• Some applications
• Why detect corners?
• Visualizing quadratics.
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).
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
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?
Finding lines in an image: Hough algorithm
yb
xm
image space Hough (parameter) space
How can we use this to find the most likely parameters (m,b) for the most prominent line in the image space?
• Let each edge point in image space vote for a set of possible parameters in Hough space
• Accumulate votes in discrete set of bins; parameters with the most votes indicate line in image space.
Slide credit: Kristen Grauman
Better Parameterization
Use normal form:
Given points find Hough Space Sinusoid
0≤ 𝛉≤П -ρ ≤ ρ ≤ ρ
(Finite Accumulator Array Size)
Image Space
? Hough Space
Image and parameter space
variables parameters
parameters
variables
a point becomes?
Image space Parameter space
Image and parameter space
variables parameters
parameters
variables
a point becomes a wave
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes?
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes a point
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes?
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes a point
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes a point
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes a point
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes a point
Image space Parameter space
Image and parameter space
variables
parameters
a line becomes a point
Image space Parameter space
Image and parameter space
variables
parameters
Wait …why is rho negative?
a line becomes a point
Image space Parameter space
Image and parameter space
variables
parameters
same line through the point
a line becomes a point
Image space Parameter space
There are two ways to write the same line:
Positive rho version:
Negative rho version:
Recall:
Image and parameter space
variables
parameters
two points become
?
Image space Parameter space
Image and parameter space
variables
parameters
three points become
?
Image space
Parameter space
Image and parameter space
variables
parameters
four points become
?
Image space
Parameter space
Implementation
1.Initialize accumulator H to all zeros
2.For each edge point (x,y) in the image
For θ =0to180or q =[qmin to qmax] //somequantization
ρ =xcos θ +ysin θ //maybenegative
H(θ, ρ)=H(θ, ρ)+1 end
end
3.Find the value(s) of (θ, ρ) where H(θ, ρ) is a local maximum
4.The detected line in the image is given by ρ =xcos θ +ysin θ
NOTE: Watch your coordinates. Image origin is top left!
Image space Votes
Basic shapes
(in parameter space)
can you guess the shape?
Basic shapes (in parameter space)
line
Basic shapes (in parameter space)
line rectangle
Basic shapes (in parameter space)
line rectangle circle
Basic Shapes
Showing longest segments found
Kristen Grauman
More complex image
In practice, measurements are noisy…
Image space Votes
Too much noise …
Image space Votes
Extensions
Extension 1: Use the image gradient
1. same
2. for each edge point I[x,y] in the image
q = gradient at (x,y)
d = xcosq - ysinq
H[d, q] += 1
3. same
4. same
(Reduces degrees of freedom)
Extension 2
• give more votes for stronger edges
Extension 3
• change the sampling of (d, q) to give more/less resolution
Extension 4
• The same procedure can be used with circles, squares, or any other shape
Slide credit: Kristen Grauman
Extensions
Extension 1: Use the image gradient 1. same
2. for each edge point I[x,y] in the image
compute unique (d, q) based on image gradient at (x,y)
H[d, q] += 1 3. same
4. same
(Reduces degrees of freedom)
Extension 2
• give more votes for stronger edges (use magnitude of gradient)
Extension 3
• change the sampling of (d, q) to give more/less resolution
Extension 4
• The same procedure can be used with circles, squares, or any other shape…
Source: Steve Seitz
Hough Transform for circles
• Circle: center (a,b) and radius r
(x -a)2 +(y -b)2 =r2 ii
Equation of circle?
Equation of set of circles that all pass through a point?
• Forafixedradiusr
b
Image space
Hough space
a
Adapted by Devi Parikh from: Kristen Grauman
Hough Transform for circles
• Circle: center (a,b) and radius r
(x -a)2 +(y -b)2 =r2 ii
• Forafixedradiusr
Intersection: most votes for center occur here.
Image space
Hough space
Kristen Grauman
Hough Transform for circles
• Circle: center (a,b) and radius r
(x -a)2 +(y -b)2 =r2 ii
• Foranunknownradiusr
r
?
b
Image space
a
Hough space
Kristen Grauman
Hough Transform for circles
• Circle: center (a,b) and radius r
(x -a)2 +(y -b)2 =r2 ii
• Foranunknownradiusr
r
b
Image space
a
Hough space
Kristen Grauman
Hough Transform for circles
• Recall:
• Circle: center (a,b) and radius r
x_i=a+rcos(theta) y_i = b – r sin(theta)
(xi -a)2 +(yi -b)2 =r2
x
θ
Image space Adapted by Devi Parikh from Kristen Grauman
Hough space
Hough Transform for circles
For every edge pixel (x,y) :
For each possible radius value r:
For each possible gradient direction θ: // or use estimated gradient at (x,y)
a = x – r cos(θ) // column b=y+rsin(θ) //row H[a,b,r] += 1
end end
• Check out online demo : http://www.markschulze.net/java/hough/
Kristen Grauman
Example: detecting circles with Hough
Original
Edges
Votes: Penny
Note: a different Hough transform (with separate accumulators) was used for each circle radius (quarters vs. penny).
Slide credit: Kristen Grauman
Example: detecting circles with Hough
Combined detections
Edges
Votes: Quarter
Slide credit: Kristen Grauman
Coin finding sample images from: Vivek Kwatra
Hough Transform: pros and cons
Pros
• Allpointsareprocessedindependently,socancopewith occlusion, gaps
• Somerobustnesstonoise:noisepointsunlikelytocontribute consistently to any single bin
• Candetectmultipleinstancesofamodelinasinglepass
Cons
• Complexityofsearchtimeincreasesexponentiallywiththe number of model parameters
• Non-targetshapescanproducespuriouspeaksinparameter space
• Quantization:canbetrickytopickagoodgridsize
Kristen Grauman