Loading [MathJax]/jax/output/CommonHTML/jax.js
Back
Close

How to Detect Circles in Images

[CG]Maxime
15.9K views

Introduction

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.

Edge detection

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)

Where intensity[x, y] is the luminosity of the pixel situated at (x, y).

Edge detection approximation
from PIL import Image, ImageDraw
import numpy as np
from math import sqrt
# Load image:
input_image = Image.open("input.png")
input_pixels = input_image.load()
width, height = input_image.width, input_image.height
# Create output image
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Here's the code using a sobel filter:

Sobel operator
from PIL import Image, ImageDraw
from math import sqrt
# Load image:
input_image = Image.open("input.png")
input_pixels = input_image.load()
# Sobel kernels
kernely = [[-1, 0, 1],
[-2, 0, 2],
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Canny Algorithm

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.

Canny Edge Detector
from math import sqrt, atan2, pi
import numpy as np
def canny_edge_detector(input_image):
input_pixels = input_image.load()
width = input_image.width
height = input_image.height
# Transform the image to grayscale
grayscaled = compute_grayscale(input_pixels, width, height)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Circle Detection using the Circle Hough Transform

As a reminder, the parametric equation of a circle of radius r and center (a,b) is:

{x=a+rcos(t)y=b+rsin(t)witht[0,2π)

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:

Circle Detection
from PIL import Image, ImageDraw
from math import sqrt, pi, cos, sin
from canny import canny_edge_detector
from collections import defaultdict
# Load image:
input_image = Image.open("input.png")
# Output image:
output_image = Image.new("RGB", input_image.size)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants