Understanding Circle Detection in Image Processing: Mathematical Background and Implementation with OpenCV Hough Transform and Hough Gradient Method
For people who are interested in robotics, detecting simple shapes using a webcam is a must-have skill. In this step-by-step tutorial we are going to learn how to detect circles with OpenCV using the Hough gradient method. So let get started :D !
Photo by Cottonbro on Pexels
In Image processing field, it's important to understand the mathematical background of circles detection. In a nutshell, there are 2 cases. First case consists about having unknown coordinates of the circle center (a, b) with already fixed Radius R. Second case, is where we have a, b and r as unknown parameters.
The First Case:
We can use the Hough Transform which is basically a method to detect straight lines, but it can as well be used to detect circles or ellipses even with some noise and messing points in the processed image. It’s effective enough since we need only 2D accumulator matrix. We will talk more later about the accumulator, and it’s function.
The approach that we are going to take can be done in 3 simple steps :
Step 1: Edge Detection and Thresholding:
We will use a standard edge detection techniques like Canny edge detector to determine the image edges. Good edging and vigilant selection of threshold values will considerably improve the detection accuracy and reduce the Error.
Step 2: Implementing the Accumulator and Counting:
The accumulator matrix will have only 2 dimensions, since the Radius is known. One for the x coordinate of the circle center and one for it’s y coordinate. If you are still a bit confused about the 2D accumulator, you should consider it as a new 2D space where we are going to draw new circle after being extracted from the old space (I mean here the processed image). During the algorithm execution, plenty of circles will be detected and drawn and there will be a peak value in the center of the real circle. In other words, those circles will all meet in the center of the real circle that we want to detect.
Step 3: Finding the Maxima in the 2D Accumulator Matrix:
After finishing the iteration of the algorithm, we only need to find where is that maxima located (peak value) to get the characteristics of the circumference. Finally, we can draw it.
The Second Case :
Solving a problem with 3 unknown parameters a, b and r will force us to use a 3D Accumulator matrix where the 3rd dimension presents the values of the radius r. If we apply the same approach of the Hough transform, we will end up having conic forms. The triplet (a, b, R) will correspond to the accumulation cell where the biggest number of cone surfaces intersect, which will make the search process ineffective in a certain way.
Lucky, OpenCV has optimized the Hough Transform to detect circles in more efficient way. It’s a new method called The Hough gradient method, which works based on the gradient information of edges. In other terms, we are going to do a Space reduction by removing the problematic 3rd parameter (radius).
How does the Hough Gradient Method work ?
While running loops to scan the image, if a pixel is detected, the Hough gradient algorithm will try to find other pixels in the neighborhood. For each 2 pixels, we need to find the perpendicular line passing through the middle point of the slope connecting the 2 pixels. This perpendicular line presents the increment in the accumulator. After finishing the iteration, we will have an accumulator with a peak in the center of the real circumference.
I suppose that we are now fine with the theoretical part, and it is time for the implementation part using C++ and the OpenCV Library.
Programming Part :
To detect circle we have to use the OpenCV function called HoughCircles() which takes 9 parameters:
- The grayscale image on which the circle detection is to be implemented.
- A vector that stores sets of 3 values: x_c, y_c and r for each detected circle.
- Gradient function ( HOUGH_GRADIENT). We define here the detection method. Currently, there is only 1 gradient method in OpenCV
- a value which presents the resolution of the accumulator
- Minimum distance between the centers of the detected circles.
- Parameter 1: Upper threshold for the internal Canny edge detector.
- Parameter 2: Threshold for circle center detection.
- Minimum Radius of the circle that we want to detect.
- Maximum Radius of the circle that we want to detect.
HoughCircles (img, circles, HOUGH_GRADIENT, 1, img.rows/16, 100, 30, 5, 30 );