Circle Hough Transform

hardPROHough TransformsHoughCV: Feature Detection and Matching

Implement the Hough transform for circle detection, a technique used in computer vision to identify circular shapes in images. The goal is to detect circles of varying radii in an image by transforming the image into a parameter space where circles are represented as peaks.

The Hough transform is a feature extraction technique that uses a voting system to detect shapes, such as lines, circles, and ellipses, in an image. For circle detection, the parameter space is 3D, represented as $(a, b, r)$ , where $(a, b)$ is the center of the circle and $r$ is the radius. The equation of a circle is given by $(x-a)^2 + (y-b)^2 = r^2$ .

For each edge pixel $(x, y)$ ,
For each possible radius $r$ ,
Vote for all centers $(a, b)$ on the circle,
Find peaks in the accumulator space.

(x-a)^2 + (y-b)^2 = r^2

This technique is widely used in object detection and recognition applications.

Output

Return a list of (a, b, r, votes) tuples, where $a$ is the centre's column ( $x$ ) and $b$ its row ( $y$ ), for every $(a, b, r)$ with at least threshold votes. Sort them by vote count, highest first, and return at most the 10 strongest.

Example

Input

edges = binary image with circle edges
r_min = 10, r_max = 50
threshold = 100

Output

[(center_x, center_y, radius, vote_count), ...]

Reasoning

Inputs: edges is an $H \times W$ binary image (1 marks an edge), r_min and r_max bound the radii tried (inclusive), and threshold is the minimum vote count; results look like [(center_x, center_y, radius, vote_count), ...].
Take a $100 \times 100$ image whose 146 edge pixels trace a radius-20 circle around $(50, 50)$ , with radii 15 to 25 and threshold 30.
Edge pixel $(x, y)$ fits any centre with $(x-a)^2 + (y-b)^2 = r^2$ , a ring of radius $r$ around it; each cell $(a, b, r)$ on that ring gains a vote.
At $r = 20$ the rings cross near the true centre, but they only touch whole pixels, so not all meet in one cell: the peak is $(49, 49, 20)$ with 36 votes (one pixel off, as positions round down).
Neighbour $(50, 49, 20)$ gets 18 and radii 19 or 21 reach at most 15, all under 30, leaving only $(49, 49, 20, 36)$ .
Notice: at threshold = 100 this circle would not be found, and an image with no edges gives an empty list.

Constraints

edges: Binary edge image (H, W)
r_min, r_max: Range of radii to detect
threshold: Minimum votes to detect circle
Return: List of (a, b, r, votes) detected circles

Learn this in

Feature Detection and MatchingCV Study Plan

More from CV: Feature Detection and Matching

Canny Edge Detection Pipelinehard Hamming Distance Matcherhard Simple BRIEF Descriptormedium Point to Hough Spaceeasy Edge Non-Maximum Suppressionmedium

Concept primerPREVIEW

Background Knowledge

The Hough transform is a voting-based method for detecting parameterized shapes (like lines, circles) in images. Instead of trying to directly fit a shape in image space, each edge pixel votes in a parameter space for all shapes that could pass through it. Peaks in this parameter space correspond to likely shapes.

For circles, each circle is defined by its center $(a, b)$ and radius $r$ , so the parameter space is 3D: $(a, b, r)$ . The circle equation in image coordinates is:

(x - a)^2 + (y - b)^2 = r^2

Given an edge pixel $(x, y)$ and a radius $r$ , all possible centers $(a, b)$ lie on a circle around $(x, y)$ . Voting over all such possibilities builds an accumulator where strong peaks indicate circles.

To reduce computation, we can use the image gradient at each edge pixel. The gradient direction is (approximately) normal to the edge and points toward or away from the circle center. So instead of voting for all possible centers around the edge point, we only vote along the gradient direction, drastically cutting down the 3D search.

Algorithm/Approach

General approach for circle Hough transform:

Preprocess the image to get edge pixels and optionally gradient direction (e.g., via Canny).
Define a 3D accumulator over $(a, b, r)$ where:
$a, b$ are center coordinates in image space.
$r$ ranges over allowed radii.
For each edge pixel and each candidate radius:
Compute possible center(s) and increment the corresponding accumulator cell.
After voting, find peaks in the accumulator (local maxima with enough votes).
Convert peaks back to circles in image space.

The “optimization with gradient” modifies the vote: for each edge pixel and radius, you infer the center position from the gradient direction, so each pair $(x, y, r)$ typically votes for 1–2 centers instead of a full circle.

Step-by-Step Strategy

Here is a practical implementation strategy (language-agnostic, but suitable for typical CV coding problems):

1) Preprocessing

Convert to grayscale (if needed).
Apply Gaussian blur (optional, to reduce noise).
Run an edge detector (e.g., Canny) to get:
A binary edge map edges[y][x].
Gradient direction theta[y][x] (can get from Sobel or from Canny internals).

2) Define parameter ranges

Let:
H, W be image height and width.
r_min, r_max be the min and max radius you care about.
Number of radii: R = r_max - r_min + 1.
Allocate a 3D accumulator, e.g.:

acc = np.zeros((H, W, R), dtype=np.int32)

3) Voting without gradient (baseline)

Conceptually:

for y in range(H):
 for x in range(W):
 if not edges[y, x]:
 continue
 for r_index, r in enumerate(radii): # radii = [r_min,..., r_max]
 # For all possible centers on circle around (x, y):
 for angle in range(0, 360, angle_step):
 a = x - r * cos(angle)
 b = y - r * sin(angle)
 if 0 <= a < W and 0 <= b < H:
 acc[int(b), int(a), r_index] += 1

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results