Basics of Circle Detection
A circle can be described by the following equation:
To detect circles, we can fix point (x, y). Now we need to find 3 parameters: a, b and r. So the problem is in the 3D search space. To find possible circles, the algorithm uses a three-dimensional matrix called the Accumulator Matrix to store the potential values of a, b, and r. The value of a (center x coordinate) can range from 1 to rows, b (center y coordinate) can range from 1 to columns, and r can range from 1 to maxRadius = ,
Below are the steps of the algorithm.
- Accumulator matrix initialization: Dimension row matrix initialization * cols * maxRadius with zeros.
- Image preprocessing: Apply to the image blur, grayscale and edge detector. This is done to make the circles look like darkened edges of the image.
- Loop through points: select point in the image.
- Fixing r and looping through a and b: use a double nested loop to find the value of r by varying a and b in the given ranges.
ma th. sqrt ((xi
accum_matrix [a] [b] [r]
- Voting: Select the points in the battery matrix with the maximum value. These are strengths that indicate the existence of a circle with parameters a, b and r. This gives us the space of the circles.
- Finding circles: Finally, using the above circles as candidates, vote according to the image. The maximum circle of voted in the accumulator matrix gives us a circle.
HoughCircles function in OpenCV has the following parameters, which can be changed according to the image.
Detection Method: OpenCV has an advanced implementation, HOUGH_GRADIENT, which uses gradient of the edges instead of filling up the entire 3D accumulator matrix, thereby speeding up the process.
dp: This is the ratio of the resolution of original image to the accumulator matrix.
minDist: This parameter controls the minimum distance between detected circles.
Param1: Canny edge detection requires two parameters - minVal and maxVal. Param1 is the higher threshold of the two. The second one is set as Param1 / 2.
Param2: This is the accumulator threshold for the candidate detected circles. By increasing this threshold value, we can ensure that only the best circles, corresponding to larger accumulator values, are returned.
minRadius: Minimum circle radius.
maxRadius: Maximum circle radius.
Below is the code for finding circles using OpenCV in the image above.