How to Detect Circles in Images

100.3K views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

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
output_image = Image.new("RGB", input_image.size)
draw = ImageDraw.Draw(output_image)
# Convert to grayscale
intensity = np.zeros((width, height))
for x in range(width):
    for y in range(height):
        intensity[x, y] = sum(input_pixels[x, y]) / 3
# Compute convolution between intensity and kernels
for x in range(1, input_image.width - 1):
    for y in range(1, input_image.height - 1):
        magx = intensity[x + 1, y] - intensity[x - 1, y]
        magy = intensity[x, y + 1] - intensity[x, y - 1]
        # Draw in black and white the magnitude
        color = int(sqrt(magx**2 + magy**2))
        draw.point((x, y), (color, color, color))
    
output_image.save("edge.png")

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],
           [-1, 0, 1]]
kernelx = [[-1, -2, -1],
           [0, 0, 0],
           [1, 2, 1]]
# Create output image
output_image = Image.new("RGB", input_image.size)
draw = ImageDraw.Draw(output_image)
# Compute convolution between intensity and kernels
for x in range(1, input_image.width - 1):
    for y in range(1, input_image.height - 1):
        magx, magy = 0, 0
        for a in range(3):
            for b in range(3):
                xn = x + a - 1
                yn = y + b - 1
                intensity = sum(input_pixels[xn, yn]) / 3
                magx += intensity * kernelx[a][b]
                magy += intensity * kernely[a][b]
        # Draw in black and white the magnitude
        color = int(sqrt(magx**2 + magy**2))
        draw.point((x, y), (color, color, color))
    
output_image.save("sobel.png")

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)
    # Blur it to remove noise
    blurred = compute_blur(grayscaled, width, height)
    # Compute the gradient
    gradient, direction = compute_gradient(blurred, width, height)
    # Non-maximum suppression
    filter_out_non_maximum(gradient, direction, width, height)
    # Filter out some edges
    keep = filter_strong_edges(gradient, width, height, 20, 25)
    return keep
def compute_grayscale(input_pixels, width, height):
    grayscale = np.empty((width, height))
    for x in range(width):
        for y in range(height):
            pixel = input_pixels[x, y]
            grayscale[x, y] = (pixel[0] + pixel[1] + pixel[2]) / 3
    return grayscale
def compute_blur(input_pixels, width, height):
    # Keep coordinate inside image
    clip = lambda x, l, u: l if x < l else u if x > u else x
    # Gaussian kernel
    kernel = np.array([
        [1 / 256,  4 / 256,  6 / 256,  4 / 256, 1 / 256],
        [4 / 256, 16 / 256, 24 / 256, 16 / 256, 4 / 256],
        [6 / 256, 24 / 256, 36 / 256, 24 / 256, 6 / 256],
        [4 / 256, 16 / 256, 24 / 256, 16 / 256, 4 / 256],
        [1 / 256,  4 / 256,  6 / 256,  4 / 256, 1 / 256]
    ])
    # Middle of the kernel
    offset = len(kernel) // 2

Circle Detection using the Circle Hough Transform

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

{\begin{matrix} x = a + r \cdot c o s (t) \\ y = b + r \cdot s i n (t) \end{matrix} with t \in [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 $r_{m i n}$ and $r_{m a x}$

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)
output_image.paste(input_image)
draw_result = ImageDraw.Draw(output_image)
# Find circles
rmin = 18
rmax = 20
steps = 100
threshold = 0.4
points = []
for r in range(rmin, rmax + 1):
    for t in range(steps):
        points.append((r, int(r * cos(2 * pi * t / steps)), int(r * sin(2 * pi * t / steps))))
acc = defaultdict(int)
for x, y in canny_edge_detector(input_image):
    for r, dx, dy in points:
        a = x - dx
        b = y - dy
        acc[(a, b, r)] += 1
circles = []
for k, v in sorted(acc.items(), key=lambda i: -i[1]):
    x, y, r = k
    if v / steps >= threshold and all((x - xc) ** 2 + (y - yc) ** 2 > rc ** 2 for xc, yc, rc in circles):
        print(v / steps, x, y, r)
        circles.append((x, y, r))
for x, y, r in circles:
    draw_result.ellipse((x-r, y-r, x+r, y+r), outline=(255,0,0,0))
# Save output image
output_image.save("result.png")

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

Introduction

Edge detection

Canny Algorithm

Circle Detection using the Circle Hough Transform

Basic Image Manipulation

How to build a chatbot in less than 50 lines of code

PYTHON: BEGINNER QUIZ (10 Questions)

Simple Python Test