This article follows the playground Basic Image Manipulation which shows how to do some basic image manipulations (rotation, grayscale, blur, edge detection, etc.) without using any advanced library.
The purpose of this new article is show a basic algorithm to detect circles in an image for educational purpose. The code provided isn't optimized and some improvements are possible. I recommend using a library such as OpenCV if you need to do feature extractions in a real project.
The source codes are written in Python with the libraries PIL and Numpy. However, no advanced features are used and it should be trivial to reimplement the algorithm in any other language.
The examples can be executed directly in your browser.
In order to detect the circles, or any other geometric shape, we first need to detect the edges of the objects present in the image.
The edges in an image are the points for which there is a sharp change of color. For instance, the edge of a red ball on a white background is a circle. In order to identify the edges of an image, a common approach is to compute the image gradient.
Since an image is composed of a set of discrete values, the derivative functions must be approximated. The most common way to approximate the image gradient is to convolve an image with a kernel, such as the Sobel operator or Prewitt operator. For an introduction to image convolution, check this playground.
The simplest way to approximate the gradient image is to compute, for each point:
magx = intensity[x + 1, y] - intensity[x - 1, y] magy = intensity[x, y + 1] - intensity[x, y - 1] mag = sqrt(magx ** 2 + magy ** 2)
intensity[x, y] is the luminosity of the pixel situated at
Here's the code using a sobel filter:
Unfortunately, the gradient image is too noisy to be used directly. The Canny edge detector is a multi-stage algorithm that will clean the image and only keep the strongest edges.
The Canny edge detector successively apply the following operations:
- Gaussian filter
- Compute image gradient
- Non-maximum suppression
- Edge tracking
The gaussian filter aims at smoothing the image to remove some noise. And, as just shown, the image gradient will identify the edges. The objective of the next two steps is to remove some edges to only keep those which are the most relevant.
When computing the gradient image, we also compute the direction of the gradient
atan2(magy, magx). Using this, we only keep the pixels that are the maximum among their neighbors in the direction of the gradient. This will thin the edges.
The next step consist of applying two threshold: the pixels with a gradient magnitude lower that
low are removed, those greater than
high are marked as strong edges, and those between are marked weak edges. Then, we iterate over the weak edges and mark as strong those which are next to a strong edge. This will allow us to improve the edge continuity.
Circle Detection using the Circle Hough Transform
As a reminder, the parametric equation of a circle of radius r and center (a,b) is:
The set of all the possible circles is defined by all the possible values for a, b and r. And for each circle, the pixels that belong to the circle can be found by iterating over some possible values of t. To reduce the amount of circles to take into consideration, we will only consider values for r between rmin and rmax
Using the edges given by the Canny edge detector and for each possible circle, we count the number of edges that are part of each circle. However, instead of iterating over all the pixels of all circles, it is faster to iterate over the coordinates of each strong edge (x,y) and compute the coordinates of the center of all the circles that pass by that point. This is done using the equation above by setting r and t. For each of these circles, we increment a counter (a,b,r).
In order to select which circles are good enough, we use two criteria: a threshold (here, at least 40% of the pixels of a circle must be detected) and we exclude circles that are too close of each other (here, once a circle has been selected, we reject all the circles whose center is inside that circle).
Here's the complete code: