Hough Transform: Circle Detection

Circles with Known Radius

The circle equation is \((x - a)^2 + (y - b)^2 = r^2\), with center \((a, b)\) and radius \(r\).

When \(r\) is known, the Hough space is 2D over \((a, b)\). Each edge point \((x_0, y_0)\) votes for a circle of radius \(r\) centered at \((x_0, y_0)\) in \((a, b)\) space — the locus of all possible centers that would place a circle of radius \(r\) through that point.

Multiple edge points on the same circle produce voting circles that intersect at the true center \((a, b)\).

Example — coin detection: run edge detection, then vote with the radius of a penny to find pennies, and separately with the radius of a quarter to find quarters. Each denomination produces distinct peaks at the correct coin centers.

Circles with Unknown Radius

When \(r\) is unknown, Hough space becomes 3D: \((a, b, r)\).

  • Each edge point votes for a cone in \((a, b, r)\) space — a stack of circles at every candidate radius.

  • Voting in 3D is far more expensive: \(k^3\) bins vs. \(k^2\) for known radius.

Using Gradient to Reduce Voting

If the gradient direction at each edge point is known, the center must lie along the gradient ray. For a given radius, only one candidate center exists (or two, considering both sides of the gradient). This reduces voting from a cone to a single line in \((a, b, r)\) space.

Algorithm

For each edge pixel:

  1. For each candidate radius \(r\):

    • If no gradient info: vote for a circle of radius \(r\) around the point in \((a, b)\) — yields a cone in 3D.

    • If gradient available: compute \((a, b)\) directly from the point, gradient direction, and \(r\) — yields a line in 3D.

  2. Increment \(H[a, b, r]\).

  3. Find peaks in \(H\).

Practical Tips

  • Minimize irrelevant votes — discard weak or unreliable edge points.

  • Choose bin sizes carefully: too large merges distinct shapes; too fine causes noise to split votes across bins.

  • Vote for neighboring bins (smoothing in accumulator space) to handle positional uncertainty.

  • Use gradient/edge direction to reduce degrees of freedom by one.

  • To recover which edge points belong to a detected shape, store voter lists per bin during accumulation.

Pros and Cons

Advantages:

  • Points processed independently — tolerates partial occlusion.

  • Robust to moderate noise (spurious votes scatter).

  • Detects multiple instances in a single pass.

Disadvantages:

  • Complexity is \(O(k^n)\) — exponential in the number of parameters; impractical beyond ~3 parameters.

  • Non-target shapes (e.g., ellipses when searching for circles) can degrade voting.

  • Bin size selection requires experimentation; no universal rule.