Hough transform

On this page 7

The Hough transform is a feature extraction technique in computer vision that detects parametric shapes, most often straight lines and circles, by letting every edge pixel vote for all shapes that could pass through it in a parameter space. Shapes that collect many votes appear as peaks in an accumulator array, and those peaks identify the shapes present in the image.

Because the method aggregates evidence from many scattered pixels, it remains robust to gaps, partial occlusion and moderate noise. It typically runs after edge detection and is a classical, non-learned alternative to neural object detection for geometric structures such as lane markings, document borders, pupils and coins.

How the Hough transform votes in parameter space

The core idea is a duality between image space and parameter space. A single point in the image is consistent with infinitely many lines, and those lines form a curve in parameter space. When many edge points lie on the same real line, their curves intersect at one parameter location, which therefore receives many votes.

The standard line detector uses the normal form rho = x cos theta + y sin theta, where rho is the perpendicular distance from the origin and theta is the angle of the normal. This form avoids the infinite slope of vertical lines in the y = mx + b form. Each edge pixel traces a sinusoid in the rho-theta plane, and the accumulator cell where many sinusoids cross gives the line.

The process follows a fixed sequence of steps, summarized in the table below.

StepOperationOutput
1. Edge detectionApply Canny or a gradient operatorBinary edge map
2. Accumulator setupQuantize rho and theta into binsEmpty two-dimensional array
3. VotingFor each edge pixel, increment cells along its sinusoidFilled accumulator
4. Peak detectionFind local maxima above a vote thresholdCandidate lines
5. Suppression and conversionRemove near-duplicate peaks, map back to imageFinal line segments or lines
Steps of the classical line Hough transform

Variants for lines, circles and arbitrary shapes

The Hough transform generalizes to any shape described by a small number of parameters, but the cost grows quickly with that number. A line needs two parameters, a circle needs three (center x, center y and radius), and an ellipse needs five. For this reason, practical systems use gradient direction and randomization to reduce the search.

VariantParametersKey ideaTypical use
Standard Hough transformrho, thetaEvery pixel votes across all anglesDetecting infinite lines
Probabilistic Hough transformrho, thetaVotes from a random pixel subsetFast line segment extraction
Circle Hough transformx, y, radiusGradient direction limits votesCoins, pupils, wheels
Generalized Hough transformPosition, scale, rotationR-table of edge offsetsArbitrary known templates
Randomized Hough transformShape-dependentFit shapes from random point tuplesEllipses and higher-order curves
Main Hough transform variants

The gradient-based circle detector illustrates the main optimization. Instead of voting for every center on a full circle around each pixel, a pixel votes only along its gradient direction, which cuts the number of votes per pixel from hundreds to a handful. The probabilistic variant similarly samples a fraction of edge pixels and stops once a line is confirmed, then returns segments with endpoints.

Key parameters and how they affect detection

Detection quality depends mostly on accumulator resolution and the vote threshold. Bins that are too coarse merge neighboring lines and lower positional accuracy, while bins that are too fine spread votes across several cells so that no peak stands out. The threshold then trades missed shapes against false detections.

ParameterTypical valueEffect when too lowEffect when too high
Rho resolution1 pixelVotes scatter, weak peaksNearby lines merge
Theta resolution1 degree (pi/180)Slow, scattered votesPoor angular accuracy
Vote thresholdScene dependent, often 50-200Many spurious linesShort or faint lines missed
Minimum line lengthScene dependentTexture creates fragmentsReal short segments dropped
Maximum line gapA few pixelsDashed lines break apartUnrelated segments join
Tuning parameters of a line Hough transform

Edge detector settings matter as much as Hough settings. Too many edges, for example from grass or fabric texture, flood the accumulator with noise, while too few edges leave real shapes without enough support. Tuning both stages together is the usual practice.

Hough transform compared with other detection approaches

The Hough transform is a global voting method, which distinguishes it from local fitting and from learned detectors. It handles multiple instances and outliers naturally, but it only finds shapes that a fixed parametric model describes.

MethodStrengthWeaknessBest fit
Hough transformRobust to gaps and outliers, finds many shapesMemory grows with parameter countLines and circles in structured scenes
RANSACLow memory, precise model fittingOne model per run, random iterationsSingle dominant shape, geometric models
Least-squares fittingFast and accurate on clean dataFails with outliersRefining an already isolated shape
Template matchingSimple for fixed appearanceSensitive to scale and rotationKnown objects in controlled views
Neural object detectionLearns complex appearanceNeeds labeled data and computeNatural objects without simple geometry
Hough transform versus alternative methods

Modern pipelines often combine approaches: a Hough transform proposes candidate lines, and least squares refines them. Some deep learning models also embed differentiable Hough voting layers for tasks such as semantic line detection and lane detection.

Limitations and common mistakes

The main limitation is the curse of dimensionality in the accumulator. Memory and computation grow exponentially with the number of parameters, which makes direct use impractical beyond about three parameters without randomization or decomposition.

  • Skipping edge detection quality checks: noisy edge maps produce peaks that do not correspond to real structures.
  • Ignoring peak suppression: one thick line produces several adjacent peaks and therefore duplicate detections.
  • Fixing the threshold across images: vote counts scale with image size and line length, so thresholds rarely transfer.
  • Treating lines as segments: the standard transform returns infinite lines, so segment endpoints need the probabilistic variant or a post-processing step.
  • Expecting curved shapes to appear: slightly curved edges, such as lens-distorted lines, split their votes across many cells.

Correcting lens distortion before detection and normalizing thresholds by image size resolve many of these issues in practice.

In simple terms

Imagine a picture with a faint straight road drawn across it, broken in places. The Hough transform asks every visible dot of the road a question: which straight lines could you belong to? Each dot casts a vote for all of them.

Most possible lines receive only a few votes, but the real road line receives votes from nearly every dot. Counting the votes reveals it. The key takeaway is that the method finds shapes by collecting agreement from many small pieces, so it works even when parts of the shape are missing.

A practical example

A driver assistance system in a delivery van must detect lane markings on a highway at 30 frames per second. Each frame is cropped to the road region, converted to grayscale and passed through a Canny edge detector. A probabilistic Hough transform with a rho step of 1 pixel, a theta step of 1 degree, a minimum segment length of 40 pixels and a maximum gap of 20 pixels extracts line segments.

The system keeps only segments with slopes typical of lane lines and groups them into left and right boundaries, which bridges the gaps in dashed markings without extra logic. On dry roads in daylight the method tracks lanes reliably at a fraction of the compute that a neural detector would need. In heavy rain, however, reflections create false segments, so the engineers add a temporal filter that rejects lines jumping too far between frames, which reduces spurious lane changes substantially.