CSE 483: Computer Vision

Hough Transform

Prof. Mahmoud Khalil

Spring 2022
1
Text Book

 Digital Image Processing, Third edition, Rafael C.

Gonzalez and Richard E. Woods, Pearson
Education, Inc. 2008.

 Section: 10.2.7

2
Fitting
• Want to associate a model with observed features

[Fig from Marszalek & Schmid, 2007]

For example, the model could be a line, a circle, or an arbitrary shape.

3
 Why lines? Because they are usually good features to
detect objects. Why not use the way we did earlier
Example: Line fitting with kernels? Because it was too noisy and unreliable.
It in fact only fits for being a pre-processing step.
• Why fit lines?
Many objects characterized by presence of straight lines

• Wait, why aren’t we done just by running edge detection?

4
 Example of a
false-positive
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?

5
Hough Transform is a voting technique.

Voting
• It’s not feasible to check all combinations of features by
fitting a model to each possible subset.

• Voting is a general technique where we let the features

vote for all models that are compatible with it.
• Cycle through features, cast votes for model parameters.
• Look for model parameters that receive a lot of votes.

• Noise & clutter features will cast votes too, but typically
their votes should be inconsistent with the majority of
“good” features.

6
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.

7
Finding lines in an image: Hough space
y b

b0

x m0 m
image space Hough (parameter) space

Connection between image (x,y) and Hough (m,b)

spaces
• A line in the image corresponds to a point in Hough space
• To go from image space to Hough space:
• given a set of points (x,y), find all (m,b) such that y = mx + b
i.e., for all the points you have in the image, find the lines that
Slide credit: Steve Seitz these points may make and take note of that in the parameter 8

space using the slope and y-intercept as the "note".

 Finding lines in an image: Hough space
y b
y0

x0 x m
image space Hough (parameter) space

• What does a point (x0, y0) in the image space map to?

– Answer: the solutions of b = -x0m + y0

– this is a line in Hough space
To answer this question, you need to answer the question from the prev.
slide: "What lines may go through the point?"; Well, a crap ton of them. 9
Slide credit: Steve Seitz
Any line that can pass through it will make it to the hough space. Usually, a line y=mx+c has a constant m-c pair
that can fit an infinite number of x-y pairs. However, here you have only one specific x-y pair, and you actually
want to know the m-c pairs that fit it. It is the opposite equation then! y=mx+c but x-y is the constant now,
hence, an infinite number of m-c pairs can fit it!
Notice how this algorithm is parallelizable! Each point is studied independent of others!

Finding lines in an image: Hough space

y b
(x1, y1)
y0
(x0, y0)

b = –x1m + y1
x0 x m
image space Hough (parameter) space

What are the line parameters for the line that

contains both (x0, y0) and (x1, y1)?
• It is the intersection of the lines b = –x0m + y0 and
b = –x1m + y1
So, now, for every point in the image space, we find the corresponding line that represents all possible m-c pairs that may create a line
that includes said point. Since this means that each point will make such line of possibilities, then the intersection of these lines means
10
that the m-c pair at that intersection can actually fit both of these points. i.e., it is a line on which both lie! Let's do this for all points...
Finding lines in an image: Hough algorithm
y b

x m
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.
The size of the bins determines how much approximation in the fitted line 11
will be tolerated. Smaller = less tolerance, more accurate line detection.
Another hyper-parameter is the threshold number of votes to accept a line
Shown below is one possible line that the given point could be passing through.
Below I go through deriving how to represent that line in polar coordinates eqn.

The parameter space would be

Polar representation for lines better if it was bounded within

known regions. The slope and y-
intercept can take on any values,
additionally the slope could even
Issues with usual (m,b) parameter space: can take on infinite values, reach infinity for vertical lines.
undefined for vertical lines. Not good.

Image columns
𝑥 cos 𝜃 𝑦 sin 𝜃 𝑑
𝑥
[0,0]
𝜃 𝑑 : perpendicular distance from line to origin
𝜃 : angle the perpendicular makes with the x-axis
Image rows

𝑑 Let's start with y = mx + c representing the line through which the

𝑦 point passes AND NOT line between it and the origin, where:
p
This is the better point representation. m = slope = dy/dx for any two points on the line. Let's choose the
The 'd' is still bad, but the 'θ' is a major points (0, c) and p. The coordinates of point p are (dcosθ, dsinθ).
improvement because it is limited to Therefore the slope is ( c – dsinθ ) / ( 0 – dcosθ ).
180 degrees. We no longer have a
slope that may shoot off to infinity! But what is c? It is the y-intercept... To get it, focus on the shaded
We now only have the 'd' to kinda be triangle. It is the hypotenuse. In that case, d = csinθ, so; c = d/sinθ.
worried about, but it scales nicely with
the size of the input image anyway. Then y = mx + c can be rewritten as:
y = ( ( d/sinθ – dsinθ ) / ( – dcosθ ) ) x + d/sinθ
y . sinθ = ( ( d – dsin2θ ) / ( – dcosθ ) ) x + d
y . sinθ = ( d( 1 – sin2θ ) / ( – dcosθ ) ) 12
x+d
Point in image space  sinusoid segment in Hough space And knowing that 1 – sin2θ = cos2θ...
y . sinθ = – cosθ . x + d
Thus: y . sinθ + x . cosθ = d
 In image a you have 5
points, 4 at each corner
and one at the center (3)

In image b you see what each point becomes: means max

Line 1 makes sense because all lines that can pass

through point 1 have zero rho (d) and any angle
from -90 to 90 can work. (yes that's theta's range)

The line connecting point 4 makes an angle zero

with the x-axis (yes the x-axis in this example is
vertical AAAAAAAAA) and that is why it has max
rho at 0 theta. Line 2 is similar but at +90 degrees
(because it makes +90 degrees with x-axis).

Another thing to note about point 4 is that it has

y=0 and x=+ve, so in the general equation... ysinθ
+ xcosθ = d, we'll only have xcosθ = d. That is why
the curve looks like a cosine. And also, that is why
d is positive all the way, because θ goes from -90
to 90, which means xcosθ = 0 ... +max ... 0.

As for line 2 it has x=0, y=+ve, so should be

ysinθ=d, and indeed in negative theta it is
negative rho, i.e., it goes -max, -ve, 0, +ve, +max.

Lines 3 and 5 achieve their max rhos at +45

degrees because they make a +45 angle w/ x-axis.
Hough transform algorithm
Using the polar parameterization: H: accumulator array (votes)
𝑥 cos 𝜃 𝑦 sin 𝜃 𝑑

d
Basic Hough transform algorithm
1. Initialize H[d, ]=0
2. for each edge point I[x,y] in the image
for  = [min to max ] // some quantization 
𝑑 𝑥 cos 𝜃 𝑦 sin 𝜃
H[d, ] += 1
3. Find the value(s) of (d, ) where H[d, ] is maximum
4. The detected line in the image is given by
𝑑 𝑥 cos 𝜃 𝑦 sin 𝜃

Time complexity (in terms of number of votes per pt)?

Source: Steve Seitz 14
Original image Canny edges

Vote space and top peaks

15
Kristen Grauman
Showing longest segments found
16
Kristen Grauman
Impact of noise on Hough

y d

x 

Image edge coordinates Votes

space

What difficulty does this present for an implementation? 17

Impact of noise on Hough
Even if some points
align, if they are sparse,
then they probably don't
actually make a line irl...
We'd need to do some
post-processing to do
checks like that, for
example measure the
length from first and last
point in the line after
detection, etc...
Image space Votes
edge coordinates

Here, everything appears to be “noise”, or random edge points, but we

still see peaks in the vote space.
18
Extensions
Extension 1: Use the image gradient
1. same
2. for each edge point I[x,y] in the image
 = gradient at (x,y)
𝑑 𝑥 cos 𝜃 𝑦 sin 𝜃
H[d, ] += 1 Instead of trying a variety
3. same of θs only use the one θ
4. same in the gradient direction
(Reduces degrees of freedom)

19
Hough transform for circles
• Circle: center (a,b) and radius r
𝑥 𝑎 𝑦 𝑏 𝑟
• For a fixed radius r, unknown gradient direction Each point becomes a circle

Intersection:
most votes for
center occur
here.

Image space Hough space

22
 In summary, any model that has an
equation can be hough-transformed
with the same idea.

Hough transform for circles

• Circle: center (a,b) and radius r
𝑥 𝑎 𝑦 𝑏 𝑟
• For an unknown radius r, unknown gradient direction

b
a
Image space Hough space

Kristen Grauman
24
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).

27
Example: detecting circles with Hough
Combined detections
Original Edges Votes: Quarter

Coin finding sample images from: Vivek Kwatra

28
Example: iris detection

Gradient+threshold Hough space Max detections

(fixed radius)

• Hemerson Pistori and Eduardo Rocha Costa http://rsbweb.nih.gov/ij/plugins/hough‐circles.html

29
Example: iris detection

• An Iris Detection Method Using the Hough Transform and Its Evaluation for Facial and
Eye Movement, by Hideki Kashima, Hitoshi Hongo, Kunihito Kato, Kazuhiko Yamamoto,
ACCV 2002.
30
Hough transform: pros and cons
Pros
• All points are processed independently, so can cope with
occlusion, gaps
• Some robustness to noise: noise points unlikely to
contribute consistently to any single bin
• Can detect multiple instances of a model in a single pass

Cons
• Complexity of search time increases exponentially with
the number of model parameters aka dimensions
• Non-target shapes can produce spurious peaks in
parameter space
• Quantization: can be tricky to pick a good grid size

31
 Let's say we have the two points in some random model, blue
and green, and we characterize their positions w.r.t. the
arbitrarily chosen ref. point via displacement vectors to it such
that for new images, we apply the displacement vectors to all
points in these images and if the ends of their displacement

Generalized Hough Transform vectors meet (or are close enough to each other), its correct!

• What if we want to detect arbitrary shapes?

Intuition:

Displacement
x
vectors xx

Ref. point x
x
Model image Novel image Vote space

Now suppose those colors encode gradient directions…

32
 The three dots highlighted in yellow below are for the case where
there is a repeating gradient (think a st. line part in the image), in
which case that one gradient would have multiple displacement
vectors associated to it. When we're doing hough voting, upon
seeing that gradient place all these vectors on the image anyway.
Generalized Hough Transform Yeah they may get some false positives that way, but they
guarantee we don't get false negatives, which are more critical.

• Define a model shape by its boundary points and

a reference point. When there's no equation to properly model it

Offline procedure:
a
At each boundary point,
x

θ θ
compute displacement
p1 p2
vector: r = a – pi.
Model shape
Store these vectors in a
θ …
table indexed by
θ … gradient orientation θ.
…

33
[Dana H. Ballard, Generalizing the Hough Transform to Detect Arbitrary Shapes, 1980]

This table is the substitute of the equation.

This table represents the shape.
Generalized Hough Transform
Detection procedure:
x
For each edge point:
θ xx
•Use its gradient orientation θ
xx
to index into stored table θ θ
p1
θ
•Use retrieved r vectors to vote θ

for reference point

Novel image
translation-invariant, but,
rotation- and scale- variant
θ …

θ …
…

34
Assuming translation is the only transformation here, i.e., orientation and scale are fixed.
Summary
• Fitting problems require finding any supporting evidence for a
model, even within clutter and missing features.
• associate features with an explicit model

• Voting approaches, such as the Hough transform, make it

possible to find likely model parameters without searching all
combinations of features.
• Hough transform approach for lines, circles, …, arbitrary shapes defined
by a set of boundary points, recognition from patches.

Hough for lines is invariant to translation, rotation, and

scaling, for lines and circles (when detecting circles of
unknown radius).

37