Circle Hough Transform

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.

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:

For each edge pixel and each radius:

Draw a circle of that radius in accumulator
Centers with many votes are detected circles

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

Example:

Constraints:

Test Results