Computer Science Department, Colorado School of Mines
Learning Objectives
By the end of this lecture, you should be able to:
Explain how image points vote in Hough space and how peaks identify line and circle models.
Interpret the polar representation of a line and explain how gradient directions help locate circle centers.
Use OpenCV to detect lines and circles, and explain how bin sizes, thresholds, and search ranges affect detection.
What Is the Hough Transform?
Hough Transform
The Hough transform is a generic framework for detecting a parametric model by a voting process. In computer vision, Hough Transform is commonly used to detect lines, circles, and other parametric shapes in images from imperfect edge detections.
A parametric model describes a shape using a small set of numbers.
A line can be described by its slope and intercept.
A circle can be described by its center and radius.
Image points vote for models that could explain their locations.
Models receiving strong support become detection candidates.
From Edge Pixels to Lines
Canny finds edge pixels at local intensity changes. It does not assign them to a shared line model.
Hough groups supporting pixels into line models, including pixels separated by gaps.
The yellow lines show four distinct candidates after excluding near-horizontal lines. Hough detects straight structures; it does not know which ones are lane boundaries.
Gaps Do Not Necessarily Prevent Detection
Separated fragments can support the same line even when part of it is hidden.
The detected line extends through the gap; this is a model prediction, not an observed edge.
Detection still requires enough supporting evidence. Heavy clutter or too little visible structure can prevent a reliable result.
The Same Idea Can Detect Circles
A circle is a parametric model with center \((a,b)\) and radius \(r\):
\[
(x-a)^2 + (y-b)^2 = r^2
\]
Boundary evidence supports candidate circle centers and radii.
Representing a Line with Two Numbers
A line can be written as
\[
y = mx + b,
\]
where \(m\) is its slope and \(b\) is its \(y\)-intercept.
Lines A and B have the same slope but different intercepts.
Lines B and C have the same intercepts but different slopes.
A Line Becomes a Point
In image space, a line has the equation \(y = mx + b\).
In parameter space, a point specifies an entire line \((m,b)\).
Parallel lines share the same \(m\) coordinate but have different \(b\) coordinates.
Lines with the same intercept share the same \(b\) coordinate but can have different \(m\) coordinates.
Estimating a Line from an Edge Point
Given a point \((x,y)\) on an image edge that we want to estimate its line parameters:
The image gradient \((I_x,I_y)\) is perpendicular to the edge.
We can estimate its line parameters as: \[
m=-\frac{I_x}{I_y},
\qquad
b=y-mx.
\]
Each edge point now supplies an estimated line \((m,b)\) that we can count.
Note that near-vertical edges have \(I_y \approx 0\) and require a different representation, which we will address later.
Binning the Line Parameters
The parameters \(m\) and \(b\) are continuous. Divide their ranges into a grid of bins.
Voting in the Hough Space
Initialize every bin to zero.
Estimate \((m,b)\) at an edge point.
Add one to the bin containing that estimate.
Repeat for the other edge points.
Nearby estimates can fall into the same bin.
A bin’s value counts points that support a line model, not the number of separate physical lines.
Each bin spans \(\Delta m=0.2\) and \(\Delta b=100\) pixels in this example.
One Edge Point, One Vote
The marked point and its gradient give one estimated line.
That estimate falls into one parameter-space bin.
We increment that bin by one.
More Points Add Votes
Points along the same straight edge tend to produce similar slopes and intercepts.
Their votes accumulate in the same bin or nearby bins.
Noise, corners, and other edges spread votes across additional bins.
A large count indicates strong support for a line with that bin’s parameters.
Peaks Identify Line Candidates
Strong, separated peaks identify candidate lines supported by many edge points.
Nearby bins may describe the same line, so we can suppress neighboring peaks.
A high bin count measures support; it does not guarantee a correct detection.
Do We Need a Slope at Every Edge Point?
So far, each point must provide a unique line estimate:
\[
m=-\frac{I_x}{I_y},
\qquad
b=y-mx.
\]
This requires a reliable gradient estimate.
Noise and corners can make direction uncertain.
Can the point vote without first choosing one slope and intercept?
Hough’s key idea: Instead of choosing one line from the gradient, let the point vote for all lines that could pass through it.
Which Lines Pass Through One Point?
For image point \(p = (2,3)\), any line through it must satisfy
\[
3=2m+b
\qquad\Longrightarrow\qquad
b=3-2m.
\]
Choosing a slope \(m\), gives an intercept \(b\).
Each possible image line contributes one parameter point. As we add more possibilities, those parameter points trace a line in Hough space.
dp=1.2: center-accumulator cells span approximately 1.2 image pixels.
minDist=170: minimum separation between detected centers; reduces duplicate detections.
param1=120: upper internal Canny threshold; the lower threshold is set to half of this value as 60.
param2=45: voting threshold for accepting circle candidates. Lower values admit weaker candidates and more false detections.
minRadius, maxRadius: search radii from 85 to 115 pixels in the image.
Each result contains \((a,b,r)\): center coordinates and radius.
Key Takeaways
The Hough transform works through voting in parameter space. Separated edge points can support the same model despite gaps or partial occlusion.
Polar line parameters \((r,\theta)\) handle all line orientations. Collinear image points produce sinusoids that meet at the line’s parameters.
Circles are described by their center and radius \((a,b,r)\). Gradient directions constrain candidate centers and reduce the search.
Detection Depends on the Search Parameters
Noise spreads votes across nearby bins. Bin sizes, thresholds, and parameter ranges affect which models are detected and whether nearby models remain distinguishable.