Hough Transform: Line Detection¶
Parametric Models¶
A parametric model defines a class of instances, each specified by a particular setting of parameters (e.g., a line by slope and intercept, a circle by center and radius).
Key considerations when fitting parametric models:
Parameterization choice matters — even for lines, the representation affects robustness.
Extended support — membership in a model depends on examining many points collectively, not individual edges alone.
Combinatorial cost — exhaustively checking every possible model is infeasible; efficient search strategies are required.
Challenges of Line Fitting¶
Given an edge image, finding lines is non-trivial because:
Many edge points are clutter unrelated to any line.
Lines are only partially detected with gaps in edge responses.
Detected edges are noisy — pixels deviate from the true line position.
Voting and the Hough Transform¶
Voting lets data decide which models are present:
Each feature (edge point) casts votes for all model parameters consistent with it.
Accumulate votes across all features.
Parameters receiving many votes correspond to detected models.
Voting is robust because noise and clutter points cast inconsistent votes that scatter across parameter space, while true features reinforce a common peak. Partial occlusion is tolerated since remaining visible points still accumulate sufficient votes.
The Hough transform applies this voting principle to find lines (and other shapes). Each edge point votes for all compatible lines; peaks in the vote accumulator identify detected lines.
Hough Space (m-b Parameterization)¶
For the line equation \(y = mx + b\):
A line in image space \(y = m_0 x + b_0\) maps to a point \((m_0, b_0)\) in Hough space.
A point \((x_0, y_0)\) in image space maps to a line \(b = -x_0 m + y_0\) in Hough space.
Two image-space points \((x_0, y_0)\) and \((x_1, y_1)\) produce two lines in Hough space; their intersection gives the \((m, b)\) of the line through both points.
The m-b parameterization fails for vertical lines (\(m = \infty\)), motivating a polar representation.
Polar Representation¶
A line is defined by:
\(d\) — perpendicular distance from the origin to the line.
\(\theta\) — angle of the perpendicular with the x-axis.
The constraint for any point \((x, y)\) on the line:
A point in image space traces a sinusoid in \((d, \theta)\) Hough space (rather than a line as in m-b space).
Range conventions: if \(d\) can be positive or negative, \(\theta \in [0, \pi)\) suffices. If \(d \geq 0\), then \(\theta \in [0, 2\pi)\).
Hough Transform Algorithm¶
Using polar parameterization with an accumulator array \(H[d, \theta]\):
Initialize \(H\) to zero.
For each edge point \((x, y)\):
For each \(\theta\) (e.g., \(0^\circ\) to \(179^\circ\) in \(1^\circ\) steps):
Compute \(d = x \cos\theta + y \sin\theta\)
Increment \(H[\text{bin}(d),\; \theta]\)
Find peaks in \(H\) — each peak \((d^*, \theta^*)\) defines a detected line.
Complexity¶
Space: \(O(k^n)\) where \(k\) = bins per dimension, \(n\) = number of parameters. For lines (\(n=2\)), this is \(k^2\).
Time (voting): Linear in the number of edge points — each point votes in constant time per \(\theta\) bin. Far cheaper than combinatorial approaches (e.g., \(\binom{q}{3}\) for circles with \(q\) edge points).
Examples¶
Noise-free points on a line: sinusoids in Hough space intersect at a sharp peak.
Square: four peaks in the accumulator, one per side.
Complex scenes: many overlapping sinusoids; the brightest peak corresponds to the longest/most-supported line.
MATLAB Demo Summary¶
Workflow: load image → convert to grayscale → detect edges (Canny) → apply hough() → find peaks with houghpeaks() → extract segments with houghlines().
Key parameters for tuning:
Threshold in
houghpeaks: minimum accumulator value to accept a peak (e.g.,0.6 * max(H)). Higher values suppress weak/false lines.Neighborhood size: suppression region in \((\rho, \theta)\) space around each peak; prevents detecting near-duplicate lines.
FillGap in
houghlines: maximum pixel gap to merge collinear segments (e.g., 50 px).MinLength: minimum segment length to report (e.g., 100 px).
Line Segments vs. Infinite Lines¶
The Hough transform finds infinite lines (parameters \(d, \theta\)). To recover line segments, either:
Trace along the infinite line and check for nearby edge points.
Record which points voted for each bin; retrieve the voter list for a winning bin.
Noise and Robustness¶
Small noise broadens peaks — fine bins may miss the true peak. Mitigation: smooth the accumulator array, then refine with finer bins in the neighborhood of coarse peaks (hierarchical approach).
Pure noise (no real structure) can produce accidental peaks. Without prior knowledge of how many lines exist, distinguishing real peaks from spurious ones requires thresholding or statistical tests.
Extensions¶
Gradient-Based Voting¶
Instead of iterating over all \(\theta\), use the edge gradient direction at each point to select a single \(\theta\) (or a narrow range). This dramatically reduces voting time and can eliminate one parameter dimension.
Other Extensions¶
Weighted votes: stronger edges contribute more votes.
Hierarchical binning: coarse bins first to find approximate peaks, then fine bins locally for precise parameters.
Other shapes: circles, ellipses, or arbitrary templates via generalized Hough transform.