Circle Hough Transform

1. 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:

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.

2. 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.

3. 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