In the previous blog, we discuss how the Hough transform can be used to detect lines in an image. Now, in this blog, let’s extend our knowledge of Hough transform to detect circles. This is also known as Hough Circle Transform. So, let’s get started.

We know that a circle can be represented as (x-a)² + (y-b)² = r² where a, b represents the circle center and r is the radius. So, we require 3 parameters (a,b,r) to completely describe the circle.

Recall from the previous blog, a line requires a 2D accumulator array as a line was defined by two parameters (r,θ). So, for a circle, we would require a 3D accumulator array. Now, let’s discuss how to fill this accumulator array.

Let’s take a simple case, where the radius r is known to us. In that case, the 3D accumulator array [a,b,r] will become 2D [a,b]. And each point in the (x, y) space will be equivalent to a circle in the (a, b) space as shown below.

Now, similar to what we did in the Hough line transform, we will first draw the circles in the ab space corresponding to each edge point. Then we will find the point of intersection (actually the local maxima in the accumulator array) which will correspond to the original circle center. Now, let’s understand this with the help of image taken from Wikipedia.

Here, for each white point in the left image, we draw the corresponding circles in the ab space (Assume that the radius is known to us). Then we find the intersection point (local maxima), see the red point in the right image. This will be the original circle center. This 2D accumulator corresponds to one row of the 3D accumulator array.

Here, we assumed that the radius is known to us. In practice, we take different radius values and repeat the above procedure. Corresponding to each r value, we will fill the 3D accumulator array. A simple question, what is the maximum plausible value that the radius can take? Obviously, for images, this can’t be greater than the diagonal length of the image.

Below is the pseudo-code for the Hough Circle Transform.

Algorithm

• Initialize the accumulator (H[a,b,r]) to all zeros
• Find the edge image using any edge detector
• For r= 0 to diagonal image length
  • For each edge pixel (x,y) in the image
    • For Θ = 0 to 360
      • a = x – r*cosΘ
      • b = y – r*sinΘ
      • H[a,b,r] = H[a,b,r] +1
• Find the [a,b,r] value(s), where H[a,b,r] is above a suitable threshold value

Problem

As you might have guessed, the above algorithm is inefficient since it involves dealing with 3D parameter space. Also, we may face a sparsity problem because only a few accumulator cells would be filled. So, to overcome this, OpenCV uses a slightly trickier method known as the Hough gradient method. So, let’s understand how that works.

OpenCV Hough Gradient Method

As is clear from the name, this method takes into account the gradient information. Earlier for each edge point, we were drawing the corresponding circles in the parameter space and thereby incrementing the accumulator cells. But now instead of drawing the full circle, we only increment the accumulator cells in the gradient direction of each edge pixel.

This algorithm consists of 2 steps:

• First, you find all the plausible candidates for the circle centers
• Then for each candidate center, we find the best radius

Let’s understand each step in detail. You can find the OpenCV code here.

First, the edge image is calculated using the Canny edge detector. Then the gradient information is computed using the Sobel operator for each edge pixel. Now, for each edge pixel, we increment the accumulator cells that lie in both directions of the gradient. Then you select all those accumulator cells that are both local maxima and above a certain threshold. All these accumulator cells are plausible candidates for circle centers.

Once you obtained the center candidates, now the task is to find the best radius for each candidate. Obviously, the parameter space is now reduced to 1D. To fill this 1D accumulator array, for each candidate center just calculate its distance from all edge pixels(this is exactly what radius is) and increment the corresponding accumulator cell. The best radius will be the one that is best supported (voted) by the edge pixels. Repeat this for each candidate center. Discard those centers that don’t have enough support and that are close to the previously selected center. This is what the Hough Gradient method does coarsely.

Now, let’s discuss how to perform the Hough Circle transform using OpenCV-Python.

OpenCV

OpenCV provides a built-in cv2.HoughCircles() function that finds circles in a grayscale image using the Hough transform. Below is the syntax

Below are the parameters explained in detail

• image: 8-bit, single-channel, grayscale input image
• method: HOUGH_GRADIENT and HOUGH_GRADIENT_ALT
• dp: The inverse ratio of accumulator resolution and image resolution
• minDist: Minimum distance between the centers of the detected circles. All the candidates below this distance are neglected as explained above
• param1: it is the higher threshold of the two passed to the Canny edge detector (the lower canny threshold is twice smaller)
• param2: it is the accumulator threshold for the circle centers at the detection stage as discussed above.
• minRadius: minimum radius that you expect. If unknown, put zero as default.
• maxRadius: if -ve, only circle centers are returned without radius search. If unknown, put zero as default.

Image Smoothing will help in this, unless the image is already soft. Let’s take an image and see how to implement this.

Steps

• Read an image and blur it to reduce the noise
• Apply the Hough Circle Transform
• Display the detected circles

Play with the parameters in order to understand them better. That’s all for this blog. In the next blog, we will discuss the Probabilistic Hough Transform that is an optimization of the Hough Transform. Hope you enjoy reading.

If you have any doubts/suggestions please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.