The Hough Transform

The Hough Transform detects instances of a parametric curve family in an image by converting a detection problem in image space into a voting problem in parameter space. A shape family, such as the set of all lines, is described by a small tuple of parameters — slope and intercept, or radius and center. Every edge pixel $(x, y)$ in the image, if it lies on some instance of that shape, must satisfy the shape's equation for a specific parameter value. Because a single point does not know which instance it belongs to, it instead considers all parameter values consistent with its coordinates and casts a vote for each one. The parameter space is discretized into a grid called the accumulator array or Hough space. Each cell corresponds to one candidate parameter setting (e.g., one specific line or one specific circle). As edge points cast votes, cells corresponding to true shapes accumulate many votes — one from every point that actually lies on that shape — while cells corresponding to spurious combinations receive votes from unrelated, uncoordinated points and stay low. After all points have voted, the algorithm reports local maxima ("peaks") in the accumulator whose vote count exceeds a threshold; each peak is a detected shape instance. The key structural fact that makes this work is a point–curve duality. A point in image space, when substituted into the line equation, traces out a curve in parameter space (all lines through that point). Conversely, a point in parameter space corresponds to one specific line in image space. Collinear points in image space map to curves in parameter space that all intersect at the same point — the parameters of the shared line. Voting is simply an efficient, discretized way of finding that common intersection without solving simultaneous equations symbolically, which would be brittle under noise. This duality generalizes: for circles the parameter space is 3-D $(a, b, r)$; for ellipses it is 5-D; the Generalized Hough Transform extends the idea to arbitrary shapes using a lookup table (the R-table) instead of a closed-form equation.

Step 1 — Choose the parameterization. For lines, the naive form $y = mx + b$ fails because vertical lines have $m = \infty$. The standard fix is the normal (polar) form:

Here $\rho$ is the perpendicular distance from the origin to the line, and $\theta \in [0, \pi)$ is the angle of that perpendicular. Every line has a finite, bounded representation: $\theta$ ranges over a bounded interval and $\rho$ ranges over $[-D, D]$ where $D$ is the image diagonal.

Step 2 — Build the accumulator. Discretize $\theta$ into $K$ bins (e.g., 1° steps, so $K = 180$) and $\rho$ into $M$ bins (e.g., 1-pixel steps across $[-D, D]$). Initialize a 2-D integer array $A[\theta][\rho]$ to zero.

Step 3 — Vote. For every edge pixel $(x, y)$ (typically pre-filtered by a gradient-magnitude threshold), and for every discretized angle $\theta_k$, compute $\rho = x\cos\theta_k + y\sin\theta_k$, round it to the nearest bin, and increment $A[\theta_k][\rho]$. Each edge point traces a sinusoidal curve through $(\theta, \rho)$-space.

Step 4 — Find peaks. After all points vote, scan $A$ for local maxima above a threshold $T$. Optionally apply non-maximum suppression in a neighborhood to avoid reporting near-duplicate lines from the same physical edge (which, because of pixel-level noise, often spreads votes across a few adjacent bins).

Step 5 — Recover the shapes. Each surviving peak $(\theta^*, \rho^*)$ is converted back to a line equation and, optionally, its finite extent is recovered by re-examining which edge pixels actually voted for that bin and taking their convex extent along the line. For circles, the equation $(x-a)^2 + (y-b)^2 = r^2$ has three unknowns. If the radius is known or restricted to a small range, the accumulator is 3-D over $(a, b, r)$. A major efficiency gain uses the gradient direction at each edge pixel: since the gradient at a point on a circle points radially, each edge point only needs to vote along the line through $(x, y)$ in the gradient direction, for each candidate radius, rather than over all possible centers — this collapses the vote from a full circle of candidate centers to a single ray, drastically cutting redundant votes. ``` function HOUGH_LINES(edge_points, theta_bins, rho_bins, image_diag, threshold):

# edge_points: list of (x, y) coordinates of edge pixels

# theta_bins: number of angle samples over [0, pi)

# rho_bins: number of distance samples over [-image_diag, image_diag] A = new integer array of size [theta_bins][rho_bins], all zeros theta_step = pi / theta_bins rho_step = (2 * image_diag) / rho_bins

# precompute cos/sin tables once -- avoids re-evaluating trig NK times for k in 0 .. theta_bins - 1: cos_table[k] = cos(k theta_step) sin_table[k] = sin(k theta_step) for (x, y) in edge_points: for k in 0 .. theta_bins - 1: rho = x cos_table[k] + y sin_table[k] r_idx = round((rho + image_diag) / rho_step) # shift into [0, rho_bins) if 0 <= r_idx < rho_bins: A[k][r_idx] += 1 peaks = empty list for k in 0 .. theta_bins - 1: for r in 0 .. rho_bins - 1: if A[k][r] >= threshold and IS_LOCAL_MAX(A, k, r, window=5): theta = k theta_step rho = -image_diag + r * rho_step peaks.append( (theta, rho, A[k][r]) ) sort peaks by vote count descending return peaks

function IS_LOCAL_MAX(A, k, r, window): for dk in -window..window: for dr in -window..window: if (dk, dr) != (0, 0) and A[wrap(k+dk)][clip(r+dr)] > A[k][r]: return false return true ``` ``` function HOUGH_CIRCLES(edge_points, gradients, radii_range, a_bins, b_bins):

# gradients[i] is the gradient direction (unit vector) at edge_points[i] A = new integer array of size [a_bins][b_bins][len(radii_range)], all zeros for i in 0 .. len(edge_points) - 1: (x, y) = edge_points[i] (gx, gy) = gradients[i] # unit gradient direction for r in radii_range:

# candidate center lies along the gradient ray, distance r away,

# in EITHER direction (dark-on-light or light-on-dark boundary) for sign in (+1, -1): a = x - sign r gx b = y - sign r gy if in_bounds(a, b): A[bin(a)][bin(b)][index(r)] += 1 return TOP_PEAKS(A, threshold) ```

Time complexity — lines. For $N$ edge points and $K$ angular samples, the voting loop performs $O(N \cdot K)$ work, since each point casts exactly one vote per angle bin. With $K$ typically a small constant (90–360), this is effectively $O(N)$ in practice, though it should honestly be stated as $O(NK)$. Peak-finding scans the accumulator, which has $O(K \cdot M)$ cells ($M$ = number of $\rho$ bins), so total time is

Since $N$ (edge pixels) usually dominates $KM$ (a few hundred by a few hundred accumulator cells) in images of interest, the transform scales linearly with the amount of edge evidence — a major advantage over combinatorial line-fitting (checking all $\binom{N}{2}$ point pairs, $O(N^2)$, and then verifying which other points are collinear with each pair, pushing worst-case cost to $O(N^3)$).

Time complexity — circles. With a fixed radius, the accumulator is 2-D and cost is $O(NR)$ where $R$ is the number of candidate radii tried (or $O(N)$ per fixed radius using the gradient-direction speedup, since each point votes along one ray instead of an entire circle of candidate centers). Without the gradient trick, a full 3-D brute-force circle Hough (voting for every possible center on the circle of radius $r$ around each edge point, for every candidate $r$) costs $O(N \cdot R \cdot C)$ where $C$ is the number of angular samples used to trace out each candidate circle of centers — this is why the gradient-direction restriction (Step 5 above) is the standard practical implementation.

Space complexity. The accumulator requires $O(KM)$ for lines and $O(A_{bins} \cdot B_{bins} \cdot R_{bins})$ for circles — the latter can become large enough (millions of cells) that coarse quantization or a hierarchical/multi-resolution accumulator is used in practice.

Correctness argument. The core invariant is: a cell in the accumulator receives one vote from point $(x,y)$ if and only if $(x,y)$ lies exactly on the shape instance that cell represents (up to quantization). This follows directly from substituting the discretized parameter values into the shape equation during voting — voting is literally evaluating "does this point satisfy this parameterized equation" and incrementing on success. Consequently, if a true line $L^*$ passes through $n$ edge points, the accumulator cell for $L^*$ receives exactly $n$ votes (modulo quantization spreading votes into 1–2 adjacent bins), while any other cell receives votes only from points that happen to be collinear with respect to a different, spurious line — an event whose expected count under a reasonably scattered noise/background distribution is much lower than $n$ for images with a real, well-supported line. This is why peak height serves as reliable evidence: it directly counts corroborating observations, and the corroboration is invariant to the order in which points appear, to gaps in the line (missing points do not create false votes elsewhere), and to a bounded amount of coordinate noise (which merely spreads the vote of a true point across a small neighborhood of bins rather than eliminating it).

Tradeoffs to be honest about. Bin resolution trades accuracy against discretization: too coarse a grid merges distinct nearby lines into one peak (or blurs $\rho, \theta$ estimates); too fine a grid spreads a true line's votes across many adjacent cells, weakening peak height and risking it falling below threshold — a phenomenon sometimes mitigated with Gaussian-smoothed accumulators before peak detection. The transform also does not exploit continuity or ordering along the curve, only feature membership, so it can hallucinate lines from coincidentally aligned but visually unrelated points in cluttered scenes (false positives grow with clutter density). Extending to shapes with more parameters (ellipses have 5) suffers a curse-of-dimensionality-like accumulator blow-up, which is exactly the pressure that motivates randomized sampling approaches like RANSAC Robust Estimation for higher-parameter models.

Consider four edge points intended to lie on the line $y = x + 1$ (so points like $(1,2)$, $(2,3)$, $(3,4)$), plus one noise point $(5,1)$ that does not lie on that line. Use 6 angle bins spanning $\theta \in \{0°, 30°, 60°, 90°, 120°, 150°\}$, computing $\rho = x\cos\theta + y\sin\theta$ and rounding to the nearest integer.

Rounding each $\rho$ to the nearest integer bin and tallying votes per $(\theta, \rho)$ cell:

• At $\theta = 60°$: $(1,2) \to \rho \approx 2$, $(2,3) \to \rho \approx 4$, $(3,4) \to \rho \approx 5$ — no agreement here, these spread out.
• At $\theta = 120°$: $(1,2) \to \rho \approx 1$, $(2,3) \to \rho \approx 2$, $(3,4) \to \rho \approx 2$ — partial agreement (2 votes at $\rho=2$).
• Checking the true angle more carefully: the line $y = x+1$ has slope 1, so its perpendicular angle is $\theta = 135°$ (not one of our coarse bins), and true $\rho = 1/\sqrt2 \approx 0.707$. With only 30°-resolution bins, this line's votes spread between the 120° and 150° columns rather than stacking cleanly — illustrating the discretization tradeoff described above.

Refining to 5° resolution near $\theta = 135°$ would show all three collinear points' curves crossing almost exactly at $(\theta, \rho) = (135°, 0.71)$, producing a clean peak with 3 votes, while $(5,1)$'s sinusoidal curve passes nowhere near that cell — its votes land in unrelated bins across the table, never stacking with the other three. This is the expected behavior: finer angular resolution near the true parameter recovers a sharp peak, while a noise point's votes disperse rather than concentrate. The peak-finding step, run on the fine-resolution accumulator, would report $(\theta^*, \rho^*) \approx (135°, 0.71)$ with vote count 3, correctly identifying the line and correctly excluding the noise point — without ever explicitly testing "are these three points collinear" as a combinatorial check.

The transform's ancestor was devised for particle-physics photograph analysis, where physicists needed to automatically trace particle trajectories (which are lines or arcs) through cluttered bubble-chamber images — the same "many candidate curves through noisy points" problem that appears in computer vision.

Lane-line detection in early and current advanced-driver-assistance systems (ADAS) uses Hough line detection on edge-filtered camera frames to find lane boundaries in real time, often as a preprocessing stage before more sophisticated tracking. Document scanning and deskewing pipelines use the Hough line transform to find the dominant page-boundary angle and rotate scanned images to be axis-aligned. Industrial inspection systems use the circle Hough transform to count and measure circular objects — bottle caps, drilled holes, pills — on assembly lines. Iris and pupil localization in biometric and medical imaging historically relied on circular Hough fitting to find the pupil boundary before deep-learning segmentation became dominant. Barcode and QR-code preprocessing pipelines sometimes use Hough line detection to find the dominant orientation of a tilted code before rectification. OpenCV's `HoughLines`, `HoughLinesP` (probabilistic variant), and `HoughCircles` remain some of the most widely used functions in the library, taught as a canonical bridge between Edge Detection and higher-level shape reasoning, and forming the conceptual stepping stone to sampling-based fitting methods like RANSAC Robust Estimation that scale better to models with many parameters or heavy outlier contamination.

Ask the tutor: How would the accumulator and voting rule change if I wanted to detect ellipses instead of circles?