OpenCV #010 Circle Detection Using Hough Transform
Highlights: In this post we will learn about analysing a given image to find circles detected in that image.
Tutorial Overview:
1. Intro
In the previous post, we saw how we can detect and find lines on images using Hough Transform. Now let’s move to something just a little bit more complicated, circles.
Let’s start with the equation of a circle:
$$ ( x_{i}-a )^{2}+( y_{i}-b )^{2}= r^{2} $$
Here \(a \) and \(b \) are the center, and \(r \) is the radius. For now we’re going to assume the radius is known. And we’re also not going to use any gradient information just yet. We’re just going to find the location of the points.
So we have a circle and we don’t actually know where the circle is. But we’ve detected three points on that circle, the blue dots. Since there are typically three unknowns, \(a \), \(b \), and \(r \), but if we know the radius, Hough space is just \(a \) and \(b \), the center locations and the \(x \) and \(y \) direction.
So, now let’s consider the first point \(x_{0} , y_{0} \). This point is marked in the picture.
So, that point has to lie on the circle, and we know its radius. One way of thinking about that, is that the circle is going to be some radius \(r \) around that point. And what that does is it votes for a set of points, and that is what this green line represents. This set of points that are \(r \) around this location in the \(a,b \) space.
So, for a single point in the image space, we get a circle of radius \(r \) in the Hough space.
Same thing for the next point. It’s got to be, again, a radius \(r \) around that point. And in Hough space, we’re going to vote along this circle we got.
And again the next point. We collect all the votes from each point in the image, and then, the middle point corresponds to the place where we get the majority of our votes, and that’s what’s drawn on the next picture.
So, it is just like in the previous post where we were voting for lines, except now instead of using the \(sin\), we’re voting in a circle in an \(a,b \) Hough space.
2. Detecting Circles with Hough
Here’s a nice example of the circles detection with Hough. We took a picture of coins on top of a textured background.
Basically we can compute the edges and then we can look for circles. We’re going to use the known radius method. Let’s suppose we start with the radius for a penny.
If we want to find the quarters, we just use a bigger radius, the radius of a quarter, and we vote again.
And these are the combined detections.
3. Hough Transform for Circles
But suppose we don’t know the radius.
Now Hough space has three dimensions, \(a \), \(b \) and \(r \), because we don’t know what the radius is. But suppose we don’t know the radius. So what do we do? Well, let’s think about it this way.
Let’s take a look at what would happen if we have a single point.
If we knew the radius, for instance, the radius was seven, then it would be some circle centered about this point. Similarly, if the radius was for example three, it would be another circle centered about the same point, but smaller. So we can start to see that what we’re getting in here is actually a cone.
Therefore, with unknown radius, each point votes for an entire cone in this 3D space. The surface of the cone and not a filled in cone. And then, the next point votes for another cone and we can sum this all up.
In terms of looking for circles if we try to vote in a big 3D space, it’s not going to work so well. For now, just remember that we have this little problem of growing the size of the voting space.
One of the ways we got rid of the number of votes we had to do was by using the gradient direction. If we had a point and we knew the gradient, there was only one possible line it could be.
Well, we can do the same thing with circles. So now we have an unknown radius, but we have a gradient.
Again, our Hough space is \(a \), \(b \) and \(r \), but this time, the point on the circle here has this gradient. Well, now if we knew the radius, we would just have one possible circle it could be.
But if the radius was half that, then the center would be there on the straight line connecting the center of the circle and that point, or it also could be on the other side. So it’s just this single line of voting that can happen when we have the gradient. In the Hough space, even though it’s a three dimensional Hough space, you would only vote along one line.
So that’s a little bit better, at least it makes the voting easier. We still have this problem when we have this three dimensional Hough space.
In general, even though 3D is only 50% more D than 2D, you will find that voting in 3D is way more than 50% harder than 2D. The number of cells that you have to consider is exponential in the number of dimensions, and that’s a challenge with using the Hough transform.
4. Code
The HoughCircles() function finds circles on grayscale images using a Hough Transform.
The name is the same in both python and c ++, and the parameters it takes are the following:
- image – Grayscale input image
- circles – Output vector of found circles. This vector is encoded as 3-element floating-point vector (x,y,radius). This is only needed in c++
- method – Detection method to use. CV_HOUGH_GRADIENT is currently the only available method
- dp – Inverse ratio of the accumulator resolution to the image resolution
- minDist – Minimum distance between the centers of the detected circles
- param1 – In case of CV_HOUGH_GRADIENT , it is the higher threshold of the two passed to the Canny() edge detector
- param2 – In case of CV_HOUGH_GRADIENT , it is the accumulator threshold for the circle centers at the detection stage
- minRadius – Minimum circle radius
- maxRadius – Maximum circle radius.
Python
C++
#include <opencv2/opencv.hpp>
#include <iostream>
using namespace cv;
using namespace std;
int main()
{
// Loading the actual image
Mat image, gray;
image=imread("50.jpg", IMREAD_COLOR);
cv::imshow("Original image", image);
cv::waitKey();
// Edge cases
if(image.empty()){
cout << "Error loading image" << endl;
return -1;
}
// converting the color image into grayscale
cvtColor(image, gray, COLOR_BGR2GRAY);
// Smoothing the image to get rid of noise, so no false detections
// Here we used a 11x11 filter
medianBlur( gray, gray, 11);
cv::imshow("Blurred_image", gray);
//cv::imwrite("Blurred_image.jpg", gray);
cv::waitKey();
// Store the detected circles in a 3d-vector
vector<Vec3f> circles;
// Apply hough transform
HoughCircles(gray, circles, HOUGH_GRADIENT, 1,
100, // detect circle with different distance
100, 100,
0,200);
// Draw the detected circles
for( size_t i = 0; i < circles.size(); i++ )
{
Point center(cvRound(circles[i][0]), cvRound(circles[i][1]));
int radius = cvRound(circles[i][2]);
// Draw the center point of the circle
circle( image, center, 3, Scalar(0,255,0), -1, 8, 0 );
// Draw the circle shape
circle( image, center, radius, Scalar(0,255,0), 3, 8, 0 );
}
// Displaying the result
cv::imshow("circles", image );
//cv::imwrite("Detected_circles.jpg", image);
cv::waitKey(0);
return 0;
}
As you can see in the previous picture, from a few circles, only one is detected. The reason for this is that these are the concentric circles.
One of the parameters of the HoughCircles() function is the distance between the centers of the circles. This prevents us to easily detect concentric circles. For this, it is necessary to change the minimal or the maximal radius of the circle in the loop, and do more detections of the same image.
Python
C++
#include <opencv2/opencv.hpp>
#include <iostream>
using namespace cv;
using namespace std;
int main()
{
// Loading the actual image
Mat image, gray;
image=imread("50.png", IMREAD_COLOR);
cv::imshow("Original image", image);
cv::waitKey();
// Edge cases
if(image.empty()){
cout << "Error loading image" << endl;
return -1;
}
// converting the color image into grayscale
cvtColor(image, gray, COLOR_BGR2GRAY);
// Smoothing the image to get rid of noise, so no false detections
// Here we used a 11x11 filter
blur( gray, gray, Size(7,7), Point(-1,-1) );
cv::imshow("Blurred_image", gray);
//cv::imwrite("Blurred_image.jpg", gray);
cv::waitKey();
// Store the detected circles in a 3d-vector
vector<Vec3f> circles;
for( int maxR = 0; maxR < 200; maxR = maxR + 10)
{
// Apply hough transform
HoughCircles(gray, circles, HOUGH_GRADIENT, 1,
100, // detect circle with different distance
100, 90,
0,maxR);
// Draw the detected circles
for( size_t i = 0; i < circles.size(); i++ )
{
Point center(cvRound(circles[i][0]), cvRound(circles[i][1]));
int radius = cvRound(circles[i][2]);
// Draw the center point of the circle
circle( image, center, 3, Scalar(0,255,0), -1, 8, 0 );
// Draw the circle shape
circle( image, center, radius, Scalar(0,255,0), 3, 8, 0 );
}
}
// Displaying the result
cv::imshow("circles", image );
//cv::imwrite("Detected_circles.jpg", image);
cv::waitKey(0);
return 0;
}
Another interesting example of circle detection:
Summary
Finally, we have learned how to detect circles on a given image. In the next posts, we will talk more about the Discrete Fourier Transform.
