Hough Transform

The Hough transform detects shapes that can be described by a few parameters, such as straight lines and circles, in a set of image points. Each point, usually an edge pixel from an edge detector, votes for every shape that passes through it; the votes are counted in a discretized parameter space, the accumulator, and shapes supported by many points appear as peaks. The method turns a global grouping problem, which points belong to the same line, into a local one, finding maxima in an array. The generalized Hough transform extends the idea to shapes with no formula, described by a table of edge positions relative to a reference point, and the same voting principle reappears as pose clustering in feature matching and as learned voting in modern detectors.

Paul Hough patented the method for tracks in bubble-chamber photographs (filed 1960, issued 1962). The form used in image analysis today, with lines in normal (angle–distance) parameters, goes back to Duda and Hart (1972), and the generalization to arbitrary shapes to Ballard (1981), as Lin et al. (2020) and Han et al. (2020) summarize the history.

Problem

An edge detector reports pixels where intensity changes, not lines or circles. Real edge maps contain gaps where contrast drops, small offsets from noise, extra pixels from texture and clutter, and several shapes at once. A least-squares fit needs to know which pixels belong to which shape, and a single unrelated pixel can pull it away. RANSAC handles outliers by sampling minimal sets and counting support, but finds one model per run and needs the sampling to hit an all-inlier sample. The Hough transform instead lets every point contribute evidence for all the shapes it could belong to, and leaves the decision to the counts: a shape is detected if enough points agree on it, whatever else is in the image and however the supporting points are spread along the shape.

Inputs and Outputs

Input: a set of feature points, in practice the pixels of a binary edge map; optionally, the gradient direction at each point, which some variants use to restrict votes.
Parameters: the shape family and its parameterization, the range and the bin size of each parameter, and a rule for selecting peaks (a vote threshold, a minimum separation between peaks, or a fixed number of peaks).
Output: the accumulator array and the parameter vectors of its selected peaks, such as $(\rho, \theta)$ for each line or $(x_c, y_c, r)$ for each circle, with their vote counts. The standard line transform returns infinite lines, not segments; Han et al. (2020) note this limitation, and the progressive probabilistic variant described below recovers end points.

Intuition

A single point does not determine a line: infinitely many lines pass through it. But the set of lines through the point is itself a curve in the space of line parameters. Two points determine one line, and their two curves cross at that line’s parameters. Many collinear points give many curves that all cross at one place. Discretize the parameter space into cells, let every point add one vote to each cell its curve crosses, and the cell where many curves cross collects a high count.

This is a change of viewpoint from the image to the parameter space: a line in the image becomes a point (a peak), and a point in the image becomes a curve. Hough’s patent describes the same construction for bubble-chamber photographs: each point of a track segment is drawn as a line in a “plane transform”, and the lines of points on a straight segment intersect in a single point, which the patent calls a “knot”. Noise spreads the crossing into a small cloud; clutter adds votes that rarely agree with each other; gaps only remove some of the curves. The peak survives all three as long as enough of the true points remain.

Algorithm

For lines in a binary edge map:

Choose the parameter ranges and bin sizes: angles $\theta$ in $[-90^\circ, 90^\circ)$ with step $\Delta\theta$ , distances $\rho$ from $-D$ to $D$ with step $\Delta\rho$ , where $D$ is the image diagonal.
Create an accumulator $A$ of size $N_\rho \times N_\theta$ , filled with zeros.
For each edge pixel $(x, y)$ and each angle $\theta_j$ : compute $\rho = x\cos\theta_j + y\sin\theta_j$ , round it to the nearest bin $i$ , and add one to $A[i, j]$ .
Find local maxima of $A$ that exceed a threshold, usually with non-maximum suppression over a small neighbourhood so that one line does not yield several adjacent peaks.
Return the $(\rho_i, \theta_j)$ of each selected peak; optionally refit each line by least squares to the pixels near it.

The same steps apply to any shape family: replace the line equation with the shape’s equation and the two-dimensional accumulator with one of as many dimensions as the shape has free parameters.

Mathematical Formulation

Lines

Hough’s patent parameterizes a line by a slope and an intercept, measured within small “framelets” of the picture chosen so that track pieces are nearly straight. In slope–intercept form $y = mx + c$ , a point $(x_0, y_0)$ votes along the line $c = y_0 - m x_0$ in the $(m, c)$ plane. The slope is unbounded: vertical lines have $m = \infty$ , so no finite accumulator covers all lines. The offset–angle form, which Lin et al. (2020) date to Duda and Hart (1972), writes a line by its normal:

\rho = x\cos\theta + y\sin\theta,

where $\theta$ is the angle of the line’s normal to the $x$ axis and $\rho$ is the signed distance of the line from the origin. With $\theta \in [-\pi/2, \pi/2)$ and $|\rho|$ at most the image diagonal, both parameters are bounded and every line has one representation. A point $(x_0, y_0)$ votes along

\rho(\theta) = x_0\cos\theta + y_0\sin\theta = \sqrt{x_0^2 + y_0^2}\,\cos(\theta - \varphi_0), \qquad \varphi_0 = \operatorname{atan2}(y_0, x_0),

a sinusoid in the $(\theta, \rho)$ plane. The sinusoids of collinear points cross at the common line. This article uses scikit-image’s convention: the origin is the top-left pixel, $x$ is the column index (to the right) and $y$ is the row index (downwards). OpenCV’s documentation describes the same $(\rho, \theta)$ with the origin at the top-left corner and $\theta = 0$ for a vertical line, but its HoughLines searches $\theta$ from 0 to $\pi$ by default.

The continuous counterpart of the accumulator is the Radon transform: the integral of the image along every line. Lin et al. (2020) describe the Radon transform as a continuous version of the Hough transform, and point out that a local operation in Hough space, such as a small filter over neighbouring $(\rho, \theta)$ cells, corresponds to a global operation over whole lines in the image.

Circles

A circle $(x - a)^2 + (y - b)^2 = r^2$ has three parameters. A point votes for every centre $(a, b)$ at distance $r$ from it, for each radius $r$ : a circle in each radius slice of a three-dimensional accumulator, so a cone in $(a, b, r)$ . scikit-image’s hough_circle implements this directly: for each requested radius it adds a rasterized circle of that radius around every edge pixel.

The edge’s gradient direction removes most of these votes. On a circle the gradient is normal to the boundary, so the centre lies along the gradient line at distance $r$ :

(a, b) = (x, y) \pm r\,\frac{\nabla I}{\lVert \nabla I \rVert}.

Each point then casts two votes per radius (one per sign, if the circle may be brighter or darker than its surroundings) instead of one per pixel of the circle’s perimeter. OpenCV’s HOUGH_GRADIENT method, which its documentation describes as basically the “21HT” method described by Yuen et al. (1990), goes one step further. Its source computes Sobel gradients and Canny edges, lets each edge pixel step along both gradient directions from the minimum to the maximum radius, and adds the votes to a two-dimensional accumulator of centres only; the radius of each accepted centre is estimated in a second stage from a histogram of the distances of the edge pixels to it. The documentation notes that the function usually finds centres well but may fail to find the correct radii.

Other analytic shapes

An ellipse has five parameters, and a five-dimensional accumulator is large. scikit-image’s hough_ellipse, which its docstring attributes to Xie and Ji (2002), reduces it: it treats each pair of edge pixels as the end points of a candidate major axis, which fixes the centre, the orientation and the semi-major axis, and accumulates only the semi-minor axis (as its square) over all third pixels, in a one-dimensional histogram. The general pattern is that every constraint a point or a pair of points imposes, from the gradient or from geometry, lowers the number of free parameters each vote must cover.

The generalized Hough transform

For a shape with no analytic form, the parameters are the pose of a known template, and the vote is given by a lookup table. Ballard (1981) introduced this generalization, as Han et al. (2020) and Qi et al. (2019) describe it. OpenCV implements it in GeneralizedHoughBallard, which its documentation says detects position only, after Ballard. Its source shows the construction:

Build the R-table from the template. For each template edge pixel $p$ with gradient angle $\phi$ , quantized into one of $K$ bins (360 by default in OpenCV), store the offset $\mathbf{r} = \mathbf{c} - p$ from the pixel to a reference point $\mathbf{c}$ of the template, such as its centre, in the row of that bin.
Vote. For each image edge pixel $q$ with gradient angle in bin $k$ , add one vote at $q + \mathbf{r}$ for every offset $\mathbf{r}$ stored in row $k$ .
Detect. Peaks of the accumulator are positions of the reference point.

In our reading, this is a counterpart of template matching that compares only edge pixels and their orientations: the template is not slid over every position, but each image edge pixel sends its votes directly to the positions it is consistent with.

The gradient angle selects which template points an image point could be, so a pixel on a straight part of the outline votes only with the offsets of the template pixels that share its orientation. Rotation and scale add dimensions: in our reading, each candidate rotation $\alpha$ shifts the orientation index by $\alpha$ and rotates the stored offsets, and each scale $s$ multiplies them, giving a four-dimensional accumulator over position, rotation and scale. OpenCV’s GeneralizedHoughGuil, after Guil et al. (1999) according to its documentation, searches over rotation and scale as well as position: its parameters set the range and step of each.

Parameters

Accumulator resolution ( $\Delta\rho$ , $\Delta\theta$ , the radius step, the R-table’s orientation bins). Coarse cells limit how precisely a peak can locate a shape: the reported parameters are cell centres. Fine cells spread the votes of a noisy shape over several cells, so the peak is lower, may split into several neighbouring maxima, and is easier to confuse with chance agreements among clutter. The example below measures this trade-off. scikit-image’s hough_line defaults to 180 angles over $[-\pi/2, \pi/2)$ and 1-pixel distance bins; the angle step can be changed through its theta argument.
Peak selection. A vote threshold (OpenCV’s threshold; scikit-image’s hough_line_peaks defaults to half the accumulator’s maximum), a minimum separation between peaks in each parameter (scikit-image’s min_distance of 9 cells and min_angle of 10 cells by default), and optionally a maximum number of peaks. The separation must be larger than the spread of a single shape’s votes and smaller than the distance between distinct shapes.
Parameter ranges. Restricting $\theta$ , the radius range or the image region to the shapes that can occur removes votes and false peaks; lane detection restricts the line angle to the slanted directions lanes take on each side of the image.
Edge detection. The transform sees only the points it is given. The edge detector’s smoothing scale and thresholds decide how many clutter pixels vote and whether a shape’s boundary is complete; Han et al. (2020) note that a clean input edge map is critical to Hough-based line detectors.

Complexity

In our reading of the procedure: the line transform costs one vote per edge pixel and angle bin, $O(N N_\theta)$ for $N$ edge pixels, with $O(N_\rho N_\theta)$ memory. All-angle circle voting costs about $O(N \sum_r 2\pi r)$ for the radii searched and needs $O(N_r H W)$ memory; gradient voting reduces the time to $O(N N_r)$ , and OpenCV’s two-dimensional centre accumulator reduces the memory to $O(HW)$ . In general a shape with $d$ parameters at $n$ bins each needs $n^d$ cells and each point votes on a $(d-1)$ -dimensional surface of them, which is why the transform is used for shapes with few parameters, and why constraints from gradients, point pairs or a coarse-to-fine search matter. Han et al. (2020) describe the original transform’s mapping of every image point to all points of the parameter space as many-to-many voting with high computational cost on large images. The voting itself is independent per point, so it parallelizes well.

Implementation

Three examples build each transform by hand in NumPy and SciPy, check the hand-built accumulators against scikit-image where it has the same routine, and measure what the parameters of the method do. They use NumPy 2.3.5, SciPy 1.16.3 and scikit-image 0.25.2, set the BLAS thread count to one, use fixed seeds, and print identical output on repeated runs. The data are synthetic, so the true shape parameters are known exactly.

Accumulator resolution for lines

The first example draws one straight line, $x\cos\theta + y\sin\theta = \rho$ with $\theta = 37.3^\circ$ and $\rho = 51.7$ px, across a 128 × 128 image. It samples 120 points uniformly along the visible segment, moves each across the line by Gaussian noise of standard deviation $\sigma$ (0, 0.5, 1 or 2 px), and rounds them to pixels; 200 pixels placed uniformly at random add clutter. The accumulator is built for five grids, from 4° by 4 px to 0.25° by 0.25 px. Three measures are averaged over seeds 0 to 9: the line error, the larger distance of the true segment’s two end points from the line of the accumulator’s global maximum; the split count, the number of separate groups of local maxima within 5° and 5 px of the true line that reach at least half the global maximum (1 means a single peak); and the peak height divided by the number of distinct line pixels. Before the experiment, the code checks that the hand-built accumulator equals scikit-image’s hough_line on the same angles. It runs in about a second.

import os
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["OPENBLAS_NUM_THREADS"] = "1"
os.environ["MKL_NUM_THREADS"] = "1"
import numpy as np
from scipy import ndimage as ndi
from skimage.transform import hough_line

H = W = 128
TH0, RHO0 = np.deg2rad(37.3), 51.7          # true line: x cos(th) + y sin(th) = rho
NORMAL = np.array([np.cos(TH0), np.sin(TH0)])
DIRECTION = np.array([-np.sin(TH0), np.cos(TH0)])
D = int(np.ceil(np.hypot(H, W)))            # largest |rho| in the image

# Visible segment of the true line: t range where rho*n + t*d lies in the image.
t = np.linspace(-200, 200, 40001)
pts = RHO0 * NORMAL + t[:, None] * DIRECTION
inside = (pts[:, 0] >= 0) & (pts[:, 0] <= W - 1) & (pts[:, 1] >= 0) & (pts[:, 1] <= H - 1)
T0, T1 = t[inside].min(), t[inside].max()
ENDS = RHO0 * NORMAL + np.array([T0, T1])[:, None] * DIRECTION


def edge_image(rng, sigma, n_line=120, n_clutter=200):
    """Edge pixels of the line, jittered across it by sigma px, plus clutter."""
    tt = rng.uniform(T0, T1, n_line)
    p = RHO0 * NORMAL + tt[:, None] * DIRECTION + rng.normal(0, sigma, n_line)[:, None] * NORMAL
    x, y = np.rint(p[:, 0]).astype(int), np.rint(p[:, 1]).astype(int)
    keep = (x >= 0) & (x < W) & (y >= 0) & (y < H)
    img = np.zeros((H, W), bool)
    img[y[keep], x[keep]] = True
    n_on_line = img.sum()
    img[rng.integers(0, H, n_clutter), rng.integers(0, W, n_clutter)] = True
    return img, n_on_line


def accumulate(img, dtheta_deg, drho):
    """Hand-built (rho, theta) accumulator; theta in [-90, 90) deg, rho cells centred on k*drho."""
    thetas = np.deg2rad(np.arange(-90, 90, dtheta_deg))
    rhos = np.arange(-np.ceil(D / drho), np.ceil(D / drho) + 1) * drho
    y, x = np.nonzero(img)
    r = x[:, None] * np.cos(thetas) + y[:, None] * np.sin(thetas)
    ri = np.floor(r / drho + 0.5).astype(int) + (len(rhos) - 1) // 2
    acc = np.zeros((len(rhos), len(thetas)), np.int64)
    np.add.at(acc, (ri, np.broadcast_to(np.arange(len(thetas)), ri.shape)), 1)
    return acc, thetas, rhos


def line_error(theta, rho):
    """Largest distance from the true segment's two end points to the detected line."""
    n = np.array([np.cos(theta), np.sin(theta)])
    return np.abs(ENDS @ n - rho).max()


def analyse(acc, thetas, rhos):
    i, j = np.unravel_index(np.argmax(acc), acc.shape)
    err = line_error(thetas[j], rhos[i])
    # Peak splitting: separate local maxima of at least half the peak, near the true line.
    peaks = (acc == ndi.maximum_filter(acc, size=3, mode="constant")) & (acc >= 0.5 * acc.max())
    near = (np.abs(thetas - TH0)[None, :] <= np.deg2rad(5)) & (np.abs(rhos - RHO0)[:, None] <= 5)
    n_split = ndi.label(peaks & near, structure=np.ones((3, 3)))[1]
    return err, n_split, acc.max()


# Library check: the hand accumulator equals scikit-image's hough_line at 1 deg, 1 px.
img, _ = edge_image(np.random.default_rng(0), 1.0)
acc, thetas, _ = accumulate(img, 1.0, 1.0)
ref, _, _ = hough_line(img, theta=thetas)
print("hand accumulator == skimage hough_line:", np.array_equal(acc, ref))

SEEDS = range(10)
RES = [(4, 4), (2, 2), (1, 1), (0.5, 0.5), (0.25, 0.25)]
print(f"{'sigma':>5} {'dtheta, drho':>13} {'err mean':>9} {'err max':>8} "
      f"{'split mean':>10} {'split max':>9} {'peak/line px':>12}")
for sigma in [0.0, 0.5, 1.0, 2.0]:
    rows = {res: [] for res in RES}
    for seed in SEEDS:
        img, n_line = edge_image(np.random.default_rng(seed), sigma)
        for res in RES:
            err, n_split, peak = analyse(*accumulate(img, *res))
            rows[res].append((err, n_split, peak / n_line))
    for res in RES:
        a = np.array(rows[res])
        print(f"{sigma:5.1f} {f'{res[0]} deg, {res[1]} px':>13} {a[:, 0].mean():9.2f} {a[:, 0].max():8.2f} "
              f"{a[:, 1].mean():10.1f} {a[:, 1].max():9.0f} {a[:, 2].mean():12.2f}")

hand accumulator == skimage hough_line: True
sigma  dtheta, drho  err mean  err max split mean split max peak/line px
  0.0   4 deg, 4 px      0.78     0.78        1.0         1         1.06
  0.0   2 deg, 2 px      0.78     0.78        1.0         1         0.97
  0.0   1 deg, 1 px      0.73     0.78        1.0         1         0.67
  0.0 0.5 deg, 0.5 px      0.41     0.44        1.0         1         0.51
  0.0 0.25 deg, 0.25 px      0.24     0.61        2.7         5         0.29
  0.5   4 deg, 4 px      0.78     0.78        1.0         1         1.04
  0.5   2 deg, 2 px      0.78     0.78        1.0         1         0.84
  0.5   1 deg, 1 px      0.72     0.78        1.0         1         0.53
  0.5 0.5 deg, 0.5 px      0.54     1.25        2.2         5         0.33
  0.5 0.25 deg, 0.25 px      0.49     1.08       13.6        22         0.19
  1.0   4 deg, 4 px      0.78     0.78        1.0         1         0.96
  1.0   2 deg, 2 px      0.78     0.78        1.0         1         0.63
  1.0   1 deg, 1 px      0.92     1.58        2.3         3         0.36
  1.0 0.5 deg, 0.5 px      0.78     1.28        9.9        16         0.22
  1.0 0.25 deg, 0.25 px      0.71     1.05       38.3        70         0.14
  2.0   4 deg, 4 px      0.78     0.78        1.0         1         0.70
  2.0   2 deg, 2 px      1.49     2.84        1.2         2         0.39
  2.0   1 deg, 1 px      1.71     2.58        4.7         8         0.25
  2.0 0.5 deg, 0.5 px      1.64     3.08       22.1        31         0.15
  2.0 0.25 deg, 0.25 px      5.07    11.29       64.5        92         0.10

The hand-built accumulator matches hough_line exactly, including its rounding of $\rho$ to the nearest cell.

Finer grids buy precision only while the votes still land in one cell. Without noise, the error falls from 0.78 px with 4° cells to 0.41 px with 0.5° cells, and every grid down to 0.5° gives a single peak. At 0.25° the rounding of the points to pixels, by up to half a pixel in each coordinate, already spreads the votes over several 0.25 px cells: the mean error is lowest, but the peak splits into 2.7 groups on average and holds only 29% of the line’s pixels. With noise the spread grows: at $\sigma = 2$ px the 0.25° grid splits the line into 64.5 groups on average, its best cell gathers 10% of the line pixels, and the global maximum lands up to 11 px from the line, in our reading because cells that happen to align clutter pixels with a few line pixels now compete with the fragmented true peak. The peak height falls from coarse to fine grids at every noise level, and the coarsest grid never splits; the hypothesis planned for these three observations (with more than 1.5 groups on average for the finest grid at $\sigma = 2$ px) held.

Two hypotheses planned before the run did not hold. The plan expected the noise-free error to decrease monotonically from the 4° grid to the 0.5° grid; this hypothesis failed: the 4° and 2° grids tie at 0.78 px. It also expected the lowest error at $\sigma = 2$ px to come from an intermediate grid (1° or 0.5°); this hypothesis failed: at $\sigma = 2$ px the coarsest grid has the lowest mean error, 0.78 px, against 1.49 to 5.07 px for the finer grids. The coarse grid’s error is 0.78 px in every seed at every noise level, and the code’s construction explains why. The true line, $\theta = 37.3^\circ$ and $\rho = 51.7$ px, lies 0.7° from the 4° grid’s cell centre at 38° and 0.3 px from its cell centre at 52 px, so the line of that cell runs close to the true one over the whole visible segment: evaluating $x\cos 38^\circ + y\sin 38^\circ - 52$ at the segment’s end points, $(65, 0)$ on the top edge and $(0, 85.3)$ on the left edge, gives distances of about 0.78 px and 0.53 px, so the printed 0.78 px is the error of that one cell. In our reading, noise up to $\sigma = 2$ px never moves the peak out of a cell this large. The 2° grid has cell centres at the same 38° and 52 px, hence the tie. A coarse cell does not always fit so well. The line crosses the image’s top edge at $x = \rho/\cos\theta \approx 65$ px and its left edge at $y = \rho/\sin\theta \approx 85$ px, so the visible segment is about 107 px long; if the true line lay near a cell boundary, the cell’s line could be off by half a cell in each parameter, 2° in angle and 2 px in distance. Changing $\theta$ with $\rho$ fixed turns the line about the foot of its normal, here $(41.1, 31.3)$ , which is 68 px from the farther end, so a 2° turn moves that end by $68 \sin 2^\circ \approx 2.4$ px, and a 2 px change of $\rho$ adds up to 2 px more: up to about 4 px. The example used one fixed line, so its comparison of grids at a given noise level depends on where that line falls relative to each grid, which was not varied.

Gradient voting for circles

The second example renders three bright antialiased disks with known centres and radii 12, 19 and 27 px on a 160 × 160 image, first alone (one clean scene) and then with clutter: eight random one-pixel segments, two filled boxes and Gaussian noise, with seeds 0 to 9. Edges come from scikit-image’s Canny detector ( $\sigma = 1.5$ ) and gradients from Sobel filters on the Gaussian-smoothed image. Two transforms search radii 8 to 32: all-angle voting, where each edge pixel votes on a full rasterized circle for each radius, and gradient voting, where it votes only at distance $r$ along its gradient, in both directions. Both fill the same three-dimensional accumulator, which is divided by each radius’s perimeter length so that peaks are comparable across radii. Peaks are local maxima of the accumulator, merged when their centres lie within 5 px; the three strongest are matched to the true circles. A circle counts as found when its centre is within 2 px and its radius within 2 px; a false peak is a merged peak at least half as high as the weakest true circle’s peak that matches no circle. The code first checks the all-angle accumulator against scikit-image’s hough_circle. It runs in about three seconds.

import os
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["OPENBLAS_NUM_THREADS"] = "1"
os.environ["MKL_NUM_THREADS"] = "1"
import numpy as np
from scipy import ndimage as ndi
from skimage.draw import circle_perimeter, line, polygon
from skimage.feature import canny
from skimage.transform import hough_circle

H = W = 160
CIRCLES = [(40.3, 45.6, 12), (110.7, 50.2, 19), (95.4, 112.8, 27)]   # (x, y, r) of bright disks
RADII = np.arange(8, 33)
PERIM = np.array([len(circle_perimeter(0, 0, r)[0]) for r in RADII])


def render(rng, clutter):
    """Antialiased bright disks (4x4 supersampling), optional segments, boxes and noise."""
    s = 4
    yy, xx = (np.mgrid[0:H * s, 0:W * s] + 0.5) / s - 0.5
    hi = np.zeros((H * s, W * s))
    for cx, cy, r in CIRCLES:
        hi[(xx - cx) ** 2 + (yy - cy) ** 2 < r ** 2] = 1.0
    img = hi.reshape(H, s, W, s).mean(axis=(1, 3))
    if clutter:
        for _ in range(8):                       # thin straight segments
            r0, c0, r1, c1 = rng.integers(0, H, 4)
            rr, cc = line(r0, c0, r1, c1)
            img[rr, cc] = 0.6
        for _ in range(2):                       # filled boxes
            r0, c0 = rng.integers(0, H - 25, 2)
            h, w = rng.integers(10, 26, 2)
            rr, cc = polygon([r0, r0, r0 + h, r0 + h], [c0, c0 + w, c0 + w, c0])
            img[rr, cc] = 0.8
        img = img + rng.normal(0, 0.05, img.shape)
    return img


def edges_and_gradient(img):
    edges = canny(img, sigma=1.5, low_threshold=0.05, high_threshold=0.15)
    g = ndi.gaussian_filter(img, 1.5)
    gx, gy = ndi.sobel(g, axis=1), ndi.sobel(g, axis=0)
    return edges, gx, gy


def vote_all_angles(edges):
    """Each edge pixel votes for every centre at distance r, for each radius (3D accumulator)."""
    acc = np.zeros((len(RADII), H, W))
    y, x = np.nonzero(edges)
    n_votes = 0
    for i, r in enumerate(RADII):
        dr, dc = circle_perimeter(0, 0, r)
        rr, cc = y[:, None] + dr, x[:, None] + dc
        ok = (rr >= 0) & (rr < H) & (cc >= 0) & (cc < W)
        np.add.at(acc[i], (rr[ok], cc[ok]), 1)
        n_votes += ok.sum()
    return acc, n_votes


def vote_gradient(edges, gx, gy):
    """Each edge pixel votes only at distance r along +/- its gradient direction."""
    acc = np.zeros((len(RADII), H, W))
    y, x = np.nonzero(edges)
    mag = np.hypot(gx[y, x], gy[y, x])
    ok0 = mag > 0
    y, x, ux, uy = y[ok0], x[ok0], gx[y, x][ok0] / mag[ok0], gy[y, x][ok0] / mag[ok0]
    n_votes = 0
    for i, r in enumerate(RADII):
        for sgn in (1, -1):
            rr = np.rint(y + sgn * r * uy).astype(int)
            cc = np.rint(x + sgn * r * ux).astype(int)
            ok = (rr >= 0) & (rr < H) & (cc >= 0) & (cc < W)
            np.add.at(acc[i], (rr[ok], cc[ok]), 1)
            n_votes += ok.sum()
    return acc, n_votes


def peaks(acc):
    """Local maxima of the perimeter-normalized accumulator, greedily merged within 5 px."""
    a = acc / PERIM[:, None, None]
    cand = np.argwhere((a == ndi.maximum_filter(a, size=(5, 7, 7), mode="constant")) & (a > 0))
    cand = cand[np.argsort(-a[tuple(cand.T)], kind="stable")]
    kept = []
    for k, cy, cx in cand:
        if all((cx - q[0]) ** 2 + (cy - q[1]) ** 2 > 25 for q in kept):
            kept.append((cx, cy, RADII[k], a[k, cy, cx]))
    return np.array(kept)


def score(kept):
    """Match the three strongest peaks to the true circles; count false peaks."""
    top = kept[:3]
    c_err, r_err, true_vals = [], [], []
    for cx, cy, r in CIRCLES:
        d = np.hypot(top[:, 0] - cx, top[:, 1] - cy)
        j = np.argmin(d)
        c_err.append(d[j]); r_err.append(abs(top[j, 2] - r))
    for cx, cy, r in CIRCLES:                    # strongest peak at each true circle
        m = (np.hypot(kept[:, 0] - cx, kept[:, 1] - cy) <= 3) & (np.abs(kept[:, 2] - r) <= 2)
        true_vals.append(kept[m, 3].max() if m.any() else 0.0)
    is_true = np.zeros(len(kept), bool)
    for cx, cy, r in CIRCLES:
        is_true |= (np.hypot(kept[:, 0] - cx, kept[:, 1] - cy) <= 3) & (np.abs(kept[:, 2] - r) <= 2)
    n_false = int(((kept[:, 3] >= 0.5 * min(true_vals)) & ~is_true).sum()) if min(true_vals) > 0 else -1
    found = int(sum((ce <= 2) and (re <= 2) for ce, re in zip(c_err, r_err)))
    return found, max(c_err), max(r_err), n_false


# Library check: all-angle voting equals scikit-image's hough_circle (unnormalized).
edges, gx, gy = edges_and_gradient(render(np.random.default_rng(0), True))
print("all-angle accumulator == skimage hough_circle:",
      np.array_equal(vote_all_angles(edges)[0], hough_circle(edges, RADII, normalize=False)))

print(f"{'scene':>9} {'method':>9} {'edge px':>7} {'votes':>8} {'found':>5} "
      f"{'centre err':>10} {'radius err':>10} {'false peaks':>11}")
conditions = [("clean", [0], False), ("clutter", range(10), True)]
for name, seeds, clutter in conditions:
    res = {"all": [], "gradient": []}
    for seed in seeds:
        edges, gx, gy = edges_and_gradient(render(np.random.default_rng(seed), clutter))
        for method, (acc, nv) in [("all", vote_all_angles(edges)),
                                  ("gradient", vote_gradient(edges, gx, gy))]:
            res[method].append((edges.sum(), nv) + score(peaks(acc)))
    for method in res:
        a = np.array(res[method], float)
        print(f"{name:>9} {method:>9} {a[:, 0].mean():7.0f} {a[:, 1].mean():8.0f} "
              f"{a[:, 2].mean():5.1f} {a[:, 3].max():10.2f} {a[:, 4].max():10.0f} "
              f"{a[:, 5].mean():5.1f} (max {a[:, 5].max():.0f})")

all-angle accumulator == skimage hough_circle: True
    scene    method edge px    votes found centre err radius err false peaks
    clean       all     418  1226872   3.0       0.50          0   0.0 (max 0)
    clean  gradient     418    20508   3.0       0.50          0   0.0 (max 0)
  clutter       all    1699  4643745   3.0       0.50          0  20.5 (max 30)
  clutter  gradient    1699    78083   3.0       0.92          1   0.0 (max 0)

Both transforms find all three circles in the clean scene and in every cluttered scene, with centres within a pixel and radii exact or one off. The difference is in the votes and in what else they produce. Gradient voting casts about 60 times fewer votes (78 thousand against 4.64 million in clutter), as the construction implies: for each of the 25 radii an edge pixel casts two gradient votes, against one vote per pixel of a rasterized circle whose perimeter grows from roughly 50 to 200 pixels over the radii searched. All-angle voting also produces on average 20.5 false peaks per cluttered scene that are at least half as strong as a true circle, against none for gradient voting. The hypotheses planned for this example (all three circles found in every cluttered scene, fewer false peaks with gradient voting, and a ratio of votes near 59.5) held. In our reading, every edge pixel of the segments and boxes spreads all-angle votes over whole circles, and these overlap by chance into maxima, while gradient voting sends a straight edge’s votes along parallel lines that rarely meet at one centre. The all-angle transform’s largest centre error, 0.50 px, is the distance from the first circle’s centre (40.3, 45.6) to the nearest pixel (40, 46); gradient voting’s is 0.92 px, in our reading because its votes follow estimated gradient directions and scatter slightly around the centre.

An R-table under occlusion

The third example builds a generalized Hough R-table for an asymmetric eight-sided polygon in a 60 × 60 template, with the template’s centre as the reference point and 90 orientation bins of 4°. The 188 template edge pixels fill 26 of the bins, since the outline has few distinct directions. The shape is placed in a 200 × 200 scene with three distractors (a disk, a rectangle and a triangle at random positions below it), and a rectangle of background colour hides the left part of the shape, covering 0, 25, 50 or 75% of the template’s edge pixels by their $x$ coordinate. Each condition is run without noise and with Gaussian noise of 0.05, with seeds 0 to 9. The code reports the visible fraction of the outline, the largest location error of the global maximum, the number of seeds in which the shape is found within 2 px, the votes at the true position divided by the number of template edge pixels, and the smallest margin: the votes at the true position divided by the highest count more than 5 px away. It runs in about three seconds.

import os
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["OPENBLAS_NUM_THREADS"] = "1"
os.environ["MKL_NUM_THREADS"] = "1"
import numpy as np
from scipy import ndimage as ndi
from skimage.draw import polygon
from skimage.feature import canny

S = 4                                    # supersampling for antialiased rendering
SHAPE = np.array([(10, 10), (50, 10), (50, 22), (28, 22), (28, 35),
                  (42, 35), (42, 50), (10, 50)], float)      # (x, y) in a 60 x 60 template
REF = np.array([30, 30])                 # reference point (x, y) in template coordinates
K = 90                                   # orientation bins of the R-table (4 degrees each)
H = W = 200


def draw(img, verts, value):
    """Fill a polygon on the supersampled canvas (vertex coordinates in pixels)."""
    rr, cc = polygon((verts[:, 1] + 0.5) * S - 0.5, (verts[:, 0] + 0.5) * S - 0.5, img.shape)
    img[rr, cc] = value


def downsample(hi):
    h, w = hi.shape[0] // S, hi.shape[1] // S
    return hi.reshape(h, S, w, S).mean(axis=(1, 3))


def edges_and_orientation(img):
    e = canny(img, sigma=1.0, low_threshold=0.05, high_threshold=0.15)
    g = ndi.gaussian_filter(img, 1.0)
    phi = np.arctan2(ndi.sobel(g, axis=0), ndi.sobel(g, axis=1))
    k = np.floor((phi % (2 * np.pi)) / (2 * np.pi / K)).astype(int) % K
    return e, k


# R-table: for each gradient-orientation bin, the offsets from edge pixel to reference point.
hi = np.zeros((60 * S, 60 * S))
draw(hi, SHAPE, 1.0)
t_edges, t_bins = edges_and_orientation(downsample(hi))
ty, tx = np.nonzero(t_edges)
R_TABLE = [[] for _ in range(K)]
for x, y in zip(tx, ty):
    R_TABLE[t_bins[y, x]].append((REF[0] - x, REF[1] - y))
R_TABLE = [np.array(v, int).reshape(-1, 2) for v in R_TABLE]
N_T = len(tx)


def scene(rng, frac, noise):
    """The shape at a fixed place, a background-coloured occluder covering the left part
    of it (the fraction `frac` of template edge pixels), three distractors, noise."""
    off = np.array([70, 60])                     # template origin in the scene
    hi = np.zeros((H * S, W * S))
    draw(hi, SHAPE + off, 1.0)
    x_cut = np.quantile(tx, frac) if frac > 0 else -1
    if frac > 0:                                 # occluder over x < x_cut (template coords)
        x0 = off[0] + x_cut + 0.5
        draw(hi, np.array([(off[0], off[1]), (x0, off[1]), (x0, off[1] + 60), (off[0], off[1] + 60)], float), 0.0)
    # Distractors in the bottom band (y >= 130), away from the shape.
    cx = rng.uniform(20, 60), rng.uniform(85, 115), rng.uniform(140, 180)
    cy = rng.uniform(140, 180, 3)
    t = np.linspace(0, 2 * np.pi, 64, endpoint=False)
    draw(hi, np.c_[cx[0] + 16 * np.cos(t), cy[0] + 16 * np.sin(t)], 1.0)              # disk
    draw(hi, np.array([(cx[1] - 15, cy[1] - 11), (cx[1] + 15, cy[1] - 11),
                       (cx[1] + 15, cy[1] + 11), (cx[1] - 15, cy[1] + 11)]), 1.0)     # rectangle
    a = rng.uniform(0, 2 * np.pi)
    draw(hi, np.c_[cx[2] + 18 * np.cos(a + t[::21][:3]), cy[2] + 18 * np.sin(a + t[::21][:3])], 1.0)
    img = downsample(hi) + rng.normal(0, noise, (H, W))
    visible = (tx > x_cut).mean()
    return img, off + REF, visible


def vote(img):
    e, k = edges_and_orientation(img)
    acc = np.zeros((H, W), np.int64)
    for y, x in zip(*np.nonzero(e)):
        off = R_TABLE[k[y, x]]
        cx, cy = x + off[:, 0], y + off[:, 1]
        ok = (cx >= 0) & (cx < W) & (cy >= 0) & (cy < H)
        np.add.at(acc, (cy[ok], cx[ok]), 1)
    return acc


print(f"template edge pixels: {N_T}, R-table bins used: {sum(len(v) > 0 for v in R_TABLE)} of {K}")
print(f"{'occluded':>8} {'noise':>5} {'visible':>7} {'loc err max':>11} {'found':>5} "
      f"{'peak/N_T':>8} {'margin min':>10}")
for noise in [0.0, 0.05]:
    for frac in [0.0, 0.25, 0.5, 0.75]:
        rows = []
        for seed in range(10):
            img, truth, visible = scene(np.random.default_rng(seed), frac, noise)
            acc = vote(img)
            py, px = np.unravel_index(np.argmax(acc), acc.shape)
            err = np.hypot(px - truth[0], py - truth[1])
            yy, xx = np.mgrid[0:H, 0:W]
            near = np.hypot(xx - truth[0], yy - truth[1]) <= 1.5
            peak = acc[near].max()
            margin = peak / acc[~(np.hypot(xx - truth[0], yy - truth[1]) <= 5)].max()
            rows.append((visible, err, err <= 2, peak / N_T, margin))
        a = np.array(rows, float)
        print(f"{frac:8.2f} {noise:5.2f} {a[:, 0].mean():7.2f} {a[:, 1].max():11.2f} "
              f"{a[:, 2].sum():5.0f} {a[:, 3].mean():8.2f} {a[:, 4].min():10.2f}")

template edge pixels: 188, R-table bins used: 26 of 90
occluded noise visible loc err max found peak/N_T margin min
    0.00  0.00    1.00        0.00    10     1.00       2.94
    0.25  0.00    0.75        0.00    10     0.71       2.08
    0.50  0.00    0.49        0.00    10     0.43       1.72
    0.75  0.00    0.23       83.15     0     0.12       0.49
    0.00  0.05    1.00        0.00    10     0.74       2.29
    0.25  0.05    0.75        0.00    10     0.57       1.78
    0.50  0.05    0.49        0.00    10     0.35       1.78
    0.75  0.05    0.23       88.01     1     0.10       0.45

Without occlusion or noise, the peak at the true reference point equals the number of template edge pixels (ratio 1.00), and even in the worst seed it is 2.9 times higher than any count more than 5 px away. Occlusion removes votes in proportion to the hidden outline: with 75% and 49% of the outline visible, the peak keeps 71% and 43% of the template’s votes, a little less than the visible share, in our reading because the occluder’s straight edge cuts the outline where its pixels would have voted. The location stays exact while half the outline is hidden, in every seed and at both noise levels; the planned hypothesis that, without noise and up to 50% occlusion, the location is exact and the peak stays within 0.1 of the visible fraction held. At 75% occlusion the remaining 23% of the outline gives a peak of 0.12 of the template’s votes, below the counts that pile up elsewhere (margin 0.49 in the worst seed), and the global maximum lies up to 83 px from the shape (88 px with noise); the shape is found in no seed without noise and in one of ten with noise. Noise lowers the peak, from 1.00 to 0.74 without occlusion, in our reading because noisy edges move pixels and their gradient angles into neighbouring cells and bins.

The plan expected the smallest margin to decrease as occlusion grows at both noise levels. It decreased without noise (2.94, 2.08, 1.72, 0.49); with noise this hypothesis failed: the smallest margin is 1.78 at both 25% and 50% occlusion before falling to 0.45. The peak still decreases with occlusion at that noise level (0.57 and 0.35); the smallest margin is set by the highest competing count in the worst seed, which the printed output does not break down.

Properties and Behavior

Robust to gaps and occlusion. A shape needs only enough supporting points, not a connected boundary. The occlusion example located a shape with half of its outline hidden.
Tolerant of clutter, within limits. Points that do not belong to any shape spread their votes over many cells. They matter when they align by chance, which becomes more likely when each vote covers more cells (all-angle circle voting) or when the true shape’s votes are spread thin (fine grids).
Several shapes at once. Every shape in the image produces its own peak in a single pass, unlike RANSAC, which finds one model per run and removes its inliers before the next.
Deterministic. The standard transform involves no sampling; the probabilistic variants below do.
Quantized output. Results are cell centres; precision below the cell size needs a refit to the supporting points or interpolation of the peak.
Sensitive to its grid. Bin size, peak threshold and peak separation interact with the noise of the edge points, as the line example shows.

Limitations

Dimensionality. Memory and time grow exponentially with the number of parameters, which restricts the plain transform to shapes with two or three parameters or forces decompositions such as gradient voting or point pairs.
Quantization trade-off. No single resolution suits all noise levels: coarse cells limit precision, fine cells split peaks.
Peak detection is heuristic. Thresholds and separations are chosen by hand; nearby or parallel shapes can merge into one peak, and one noisy shape can produce several.
Infinite lines. The line transform does not say where a line starts or ends, or whether it is one segment or several collinear ones; end points need a second pass over the image, as in the progressive probabilistic transform.
Correlated clutter. Texture with a dominant orientation, repeated structure or parallel edges produce real peaks that are not the object of interest. Han et al. (2020) note that classical line detectors often focus on fine, detailed straight edges, so that their results often contain irrelevant lines.
Template rigidity. The generalized transform expects the shape it was built from; deformation, viewpoint change and articulation spread its votes, which led to the learned voting methods below.

Variants

Probabilistic and progressive transforms. Kiryati, Eldar and Bruckstein (1991) accelerated the transform by voting with a random subset of the points, as Han et al. (2020) describe. The progressive probabilistic Hough transform of Matas, Galambos and Kittler (2000), which OpenCV’s HoughLinesP cites (scikit-image’s probabilistic_hough_line cites the same authors’ 1999 CVPR paper on it, with Galambos first), works one random point at a time. In the OpenCV source, each selected point is added to the accumulator; if one of its cells reaches the threshold, the code walks along that cell’s line in both directions through the edge map, allowing gaps up to a maximum length, to find the segment’s end points. The pixels on the walk are removed from the edge map, and for a segment long enough to be reported their votes are also removed from the accumulator, so they do not vote again. Lin et al. (2020) describe it as both faster and more robust to noise. The vanishing points article’s example uses scikit-image’s implementation to find line segments.
Hierarchical and multi-resolution transforms. Princen, Illingworth and Kittler (1990) and Yacoub and Jolion applied the transform to a hierarchy of image patches, and Illingworth and Kittler’s adaptive Hough transform (1987) searched for peaks coarse to fine, as Han et al. (2020) describe. OpenCV’s multi-scale variant of HoughLines refines a coarse accumulator by divisors of the distance and angle resolution.
Kernel-based voting. Fernandes and Oliveira (2008) use an oriented elliptical-Gaussian kernel so that votes go to only a few lines, according to Han et al. (2020).
Gradient-constrained circle transforms. OpenCV’s HOUGH_GRADIENT (above) and its HOUGH_GRADIENT_ALT variant, which its documentation describes as a variation for better accuracy, use the edge direction to cut the votes per point to a line segment of centres.
Generalized Hough with rotation and scale. Guil et al. (1999), implemented in OpenCV’s GeneralizedHoughGuil.
Pose clustering of feature matches. In SIFT recognition, each keypoint match predicts an object’s position, scale and orientation, and matches vote in a coarse Hough transform over pose before a least-squares verification; Lowe preferred this to RANSAC when correct matches are a very small fraction of all matches, as the 2004 paper’s article describes.
Learned voting for detection. Samet et al. (2020) describe the Implicit Shape Model of Leibe et al. as the most influential generalized-Hough detector before deep learning: patches around interest points are matched to a codebook of visual words, each word stores the offsets to object centres seen in training, and matched words vote for centres. Hough forests (Gall and Lempitsky) learned the mapping from patches to votes with random forests, and the max-margin Hough transform (Maji and Malik) learned visual words in a discriminative max-margin framework, as Samet et al. (2020) describe. HoughNet itself is a one-stage, anchor-free detector in which every location votes for object centres through a log-polar “vote field” that lowers the spatial precision of votes from far away. VoteNet (Qi et al., 2019) applies Hough voting to 3D object detection: points sampled from a point cloud regress offsets to object centres, and the votes are clustered and turned into box proposals by learned modules.
Deep Hough transforms for lines. Han et al. (2020) run the line transform on convolutional features instead of a binary edge map: features along each line are summed into a parameter-space feature map, convolutions over neighbouring $(\theta, \rho)$ cells add context, and lines are detected as peaks, with non-maximum suppression reduced to taking the centroids of connected regions. Lin et al. (2020) add a Hough-transform block with its inverse to a line-segment network as a built-in line prior, and report that it improves data efficiency on the Wireframe (ShanghaiTech) and York Urban datasets.

History

Hough’s patent, filed on 25 March 1960 and issued on 18 December 1962, addressed bubble-chamber photographs, each of which, it says, needed several hours of study by a trained observer. It divides the picture into framelets small enough for track pieces to be nearly straight, maps each point to a line in a transform plane, and reads slopes and intercepts from the points where these lines meet; it also describes an electronic apparatus with a television camera for doing so. VoteNet (Qi et al., 2019) dates the introduction of the transform to the late 1950s, and HoughNet’s references cite a 1959 conference paper by Hough on the machine analysis of bubble-chamber pictures. Duda and Hart (1972) brought the transform into image analysis with the angle–distance parameterization of lines, and Ballard (1981) generalized it to arbitrary shapes, as Lin et al. (2020) and Han et al. (2020) summarize. Adaptive, hierarchical and probabilistic variants followed from the late 1980s, and the voting idea moved into recognition through pose clustering and implicit shape models, and later into networks, as described above.