OpenCV #010 Circle Detection Using Hough Transform

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
  2. Detecting Circles with Hough
  3. Hough Transform for Circles
  4. Code

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.

Circle in the image space
Circle in the image space

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.

Circle in the image space on the left and circle in the Hough space on the right
Circle in the image space on the left and circle in the Hough space on the right

 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.

Mapping the Image-space into a 2D Hough space
Mapping the Image-space into a 2D Hough 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.

  Mapping the Image space into a  2D Hough space
Mapping the Image space into a 2D Hough space

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.

coins

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.

decting edges then circles on image

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.

Mapping multiple circles from the image space into a 3d hough space
Mapping the Image space into a 3D Hough space

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.

Mapping multiple circles from the image space into a 3d hough space

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.

mapping circles using gradient direction

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.

mapping circles using gradient direction
Using the gradient direction

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;
}Code language: PHP (php)
detecting circle on a tic tac toe game hough transform

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;
}
Code language: PHP (php)
detecting circle on a tic tac toe game hough transform

Another interesting example of circle detection:

detecting a circle on a speed limit sign hough transform

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.

More resources on the topic:

 

Leave a Reply

Your email address will not be published. Required fields are marked *