Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 46 ยท Features and Matching

Hough Transform for Lines and Circles

Detect lines and circles by voting: build the (rho, theta) accumulator from scratch, find peaks, extend the idea to circles, and learn where it breaks.

An edge detector hands you a cloud of edge pixels. It does not tell you that 80 of them belong to one straight road marking, or that 145 of them form a ring. Fitting a line by least squares fails when most pixels belong to other things, and trying every possible line is far too slow. The Hough transform solves this with an idea that feels backwards at first: instead of asking "which pixels lie on this line?", let every pixel vote for all the lines that could pass through it. The line that collects the most votes is the real one.

This lesson builds the transform from scratch with NumPy, first for lines and then for circles. It starts from the edge pixels you get from edge detection and uses boolean masks and array indexing heavily.

Why slope and intercept do not work

The textbook line y = m*x + c breaks for vertical lines (infinite slope) and spreads votes unevenly. The Hough transform uses the normal form instead. Every line is described by two numbers:

  • theta: the angle of the line's normal (the perpendicular direction), from 0 to 180 degrees.
  • rho: the signed distance from the origin to the line along that normal.

A point (x, y) lies on the line (rho, theta) exactly when

TEXT
rho = x * cos(theta) + y * sin(theta)

For a fixed point, this equation gives one rho for every theta: a smooth sine-shaped curve in the (theta, rho) plane. That curve is the set of all lines through the point. The origin is the image corner, so rho can be negative.

flowchart LR
    P["edge pixel (x, y)"] --> C["one curve in (theta, rho) space<br/>= all lines through the pixel"]
    C --> V["add 1 to every accumulator cell on the curve"]
    V --> K["cells with many votes<br/>= lines supported by many pixels"]

Each pixel votes for a whole curve of lines; real lines are where curves pile up.

Python From points to curves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two points define one line, so their two curves intersect in exactly one place: here theta = 135 degrees and rho = 0, which is the line y = x through the origin (its normal points at 135 degrees). With hundreds of points on a line, hundreds of curves pass through the same spot.

The accumulator

In code, the plane of (rho, theta) becomes a 2D integer array called the accumulator. Its rows are quantized rho values and its columns are angles (we use one-degree steps). For each edge pixel you compute rho for all angles at once and add one to the matching cell in each column. The rho range is -D..D where D is the image diagonal, so an offset of D makes the array index non-negative.

The scene below has a diagonal line, a horizontal line at row 50, and 40 random stray pixels. After voting, we look for the largest cell, record it, blank out its neighbourhood (otherwise the next maximum is just a neighbour of the first), and repeat.

Python Voting for lines from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two peaks are the two lines. The diagonal has rho = 0 and theta = 135 and collects 80 votes (one per pixel of the line). The horizontal line sits at row 50: its normal points straight down, so theta = 90 degrees and rho = 50, with 70 votes. The 40 random pixels each vote too, but their curves cross each other almost nowhere, so noise only produces a low, scattered floor of 1s and 2s. The accumulator image shows the two lines as bright spots where many sine curves meet.

A few practical points follow from this:

  • Resolution matters. Bins that are too fine split one line's votes over neighbouring cells and the peak weakens; bins that are too coarse merge different lines. A 1-pixel rho step and 1-degree theta step suit small images.
  • Fewer, better edges help. Run the transform on thinned edges (the output of Canny), not on a blurry gradient image. Votes can also be weighted by gradient strength.
  • Use the gradient direction. If every edge pixel already knows its gradient angle, it only needs to vote for theta near that angle, which cuts the work by a large factor and removes spurious peaks.
  • A line is not a segment. The accumulator tells you that an infinite line exists, not where it starts and ends. To get segments, go back to the edge pixels near that line and look for runs of them. The probabilistic Hough transform in libraries does this.

Circles

For a circle with centre (a, b) and radius r, every point on it satisfies (x - a)^2 + (y - b)^2 = r^2. That is three parameters, so the accumulator is a 3D array. The voting rule flips the viewpoint again: an edge pixel lies at distance r from the centre, so for a fixed radius it votes for all centres on a circle of radius r around itself. If the pixel is really on a circle of radius r, one of those voted centres is the true centre, and all the pixels on that circle will agree on it.

flowchart TB
    E["edge pixel"] --> R1["for each radius r in the search range"]
    R1 --> V["vote for all centres at distance r"]
    V --> A["3D accumulator (radius, row, column)"]
    A --> M["maximum = best circle"]

Circle detection adds a radius axis, so the cost grows with the radius range.

Python Finding a circle among noise

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

np.add.at is the right tool for the vote: when several votes land on the same cell inside one call, plain acc[idx] += 1 would count them only once, while np.add.at adds every one. The centre map for the best radius (right panel) is dark except for one bright dot, which is the centre.

Limits of the Hough transform

  • Cost. Lines cost (number of edge pixels) times (number of angles). Circles multiply that by the number of radii, and general shapes with more parameters quickly become impractical. Ellipses already have five parameters.
  • Memory and bin choice. The accumulator size follows the parameter ranges and quantization; peaks smear if the bins do not match the real precision.
  • Peak picking. You must decide how many votes make a "real" shape and suppress neighbours, otherwise one line gives dozens of near-duplicate answers.
  • Coincidences. Many unrelated edge pixels can happen to align. A busy photo yields plenty of weak, false lines.
  • Dependence on edges. If the edge map is broken or very noisy, the votes are missing or buried. Good preprocessing (blur and Canny) matters more than the voting code.

Despite these limits, the idea of letting each observation vote in a parameter space is everywhere: in generalized Hough transforms for arbitrary shapes, in vote-based object detectors, and in the RANSAC consensus idea from the previous lesson.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the Hough transform describe lines with (rho, theta) rather than slope and intercept?

    Vertical lines have infinite slope. The normal form (rho, theta) has bounded ranges and represents every direction uniformly.
  2. 2. In the (theta, rho) plane, what does one edge pixel become?

    rho = xcos(theta) + ysin(theta) gives one rho per theta, which is a sinusoid. Every point on that curve is a line through the pixel.
  3. 3. Why do we blank out the neighbourhood of a peak before looking for the next one?

    A line's votes spread slightly over adjacent bins. Without suppression, the next maximum would be a neighbour of the first, not a new line.
  4. 4. How many parameters does a circle-detecting Hough accumulator need when the radius is unknown?

    Centre row, centre column and radius give three parameters, so the accumulator is a 3D array.
  5. 5. Which statement about the line Hough transform is true?

    The accumulator only encodes (rho, theta). Locating where along the line the pixels actually are is a separate step.

Summary

  • The Hough transform detects shapes by voting: every edge pixel adds a vote to each parameter cell of the shapes that could contain it.
  • Lines use the normal form rho = x*cos(theta) + y*sin(theta); a pixel becomes a sine curve and real lines appear as accumulator peaks.
  • Pick the maximum, suppress its neighbourhood, and repeat to get several lines.
  • Circles need a 3D accumulator (radius, row, column); each pixel votes for centres at distance r, and np.add.at counts repeated votes correctly.
  • Costs grow quickly with the number of shape parameters, results depend on bin sizes and on clean edge maps, and lines found are infinite, not segments.

Next, move from detecting shapes to counting and measuring regions with Connected Components and Labeling.