Hough Transform

Stop hunting lines in the image and let every edge pixel vote for the lines that could pass through it. The busiest ballot boxes are the real lines.

Three pixels (0,2) (1,1) (2,0) vote rho 1.414 at theta 45 degrees: three sinusoids cross once, casting 3 votes for one line

Why Does This Exist?

Edge maps hand you disconnected pixels, and fitting lines through them directly breaks on the first gap, speck, or crossing. Hough (1962) inverted the problem: instead of grouping pixels into lines, each pixel votes for all compatible lines in a parameter space, and lines emerge as vote peaks that survive gaps and clutter. Lane finding, document borders, and industrial metrology still run on this vote.

Clean edges are the prerequisite, via edge filtering. This page covers the polar parametrization, the accumulator, and resolution tuning. Applied line segments get their own page (Hough lines), and round shapes get Hough circles.

Think of It Like This

An election among witnesses

Three witnesses glimpse a getaway car from different corners. Each lists every route consistent with what they saw: hundreds of possibilities per witness. Tallies accumulate, and one route appears on all three lists while every decoy appears once. The winner is not the cleverest testimony but the most corroborated.

It stops holding when ballots cost money. Every extra angle and radius bin multiplies the count, the same way the accumulator's memory and time explode with fine resolution. Democracy works, but the ballot printing bill is real.

How It Actually Works

Why slope-intercept fails first

The schoolbook line $y = mx + b$ cannot represent vertical lines (infinite $m$ ) and stretches the parameter space unevenly. The polar form fixes both: $\rho = x \cos\theta + y \sin\theta$ , where $\theta$ is the line's normal angle and $\rho$ its distance from the origin. Every line, vertical included, is one finite $(\rho, \theta)$ point.

Voting in the accumulator

Fix an edge pixel and sweep $\theta$ through $180°$ : each angle gives one $\rho$ , tracing a sinusoid of votes in parameter space. Repeat for every edge pixel into a 2D histogram, the accumulator. Pixels sharing a real line have sinusoids crossing at that line's $(\rho, \theta)$ , so true lines become bright peaks while noise spreads thin.

Verify with three pixels $(0,2)$ , $(1,1)$ , $(2,0)$ on the line $y = -x + 2$ . At $\theta = 45°$ , $\cos\theta = \sin\theta \approx 0.7071$ , and $\rho = (x + y) \times 0.7071 = 2 \times 0.7071 \approx 1.414$ for all three. Three sinusoids, one crossing, peak $(45°, 1.41)$ with $3$ votes.

Resolution and threshold

Bin sizes set the deal: $\rho$ resolution near $1$ pixel and $\theta$ near $1°$ suit most images. Finer bins split one line's votes across neighbours so nothing peaks; coarser bins merge distinct lines into one. The vote threshold then filters peaks: it must sit below the faintest true line's pixel count and above the clutter's accidental crossings.

Code

The three fixture pixels voting at $45$ degrees:

1import math2
3pixels = [(0, 2), (1, 1), (2, 0)]4theta = math.radians(45)5rhos = [x * math.cos(theta) + y * math.sin(theta) for x, y in pixels]6print(f"rhos {[round(r, 3) for r in rhos]}, votes at 1.414: {sum(abs(r - 1.414) < 0.001 for r in rhos)}")7# -> rhos [1.414, 1.414, 1.414], votes at 1.414: 3

All three sinusoids cross at $\rho = 1.414$ , casting $3$ votes for one line.

Watch Out For

Voting on raw grayscale instead of edges

Symptom: the accumulator glows everywhere and every returned line is fiction, because thousands of textured pixels vote for thousands of accidental crossings. The transform assumes sparse edge input. Run Canny first, view the edge map, and only vote when a human can see the lines in the edges.

Splitting votes with over-fine resolution

Symptom: a strong obvious line returns nothing while a coarse rerun finds it instantly. Bins narrower than the edge localization error scatter one line's votes across neighbours so no cell crosses threshold. Start at $1$ pixel and $1$ degree, and coarsen before lowering the threshold.

The Quick Version

Hough turns line finding into voting: each edge pixel votes for every line through it in $(\rho, \theta)$ space.
The polar form $\rho = x \cos\theta + y \sin\theta$ represents every line, vertical ones included.
True lines are accumulator peaks where many sinusoids cross; noise spreads its votes thin.
Bin resolution near $1$ pixel and $1°$ balances split votes against merged lines.
It tolerates gaps and clutter but needs clean edges first, or every peak is fiction.