Canny Edge Detection Algorithm From Scratch.

Let’s understand everything about Canny Edge Detection, as well as coding a custom implementation in python.

9 min readJan 31, 2023

Image by Robert Bye on Unsplash [Edited]

Canny is a multi-stage edge detection algorithm that can detect edge like features in images.

But, wait.. why do we need to detect edges in an image?

As a human, our brain has no problem detecting edges in any image, but to automate the task on computers we have to use programs that can do the task.

For example,

Medical Imaging
Finger Print Recognition
In Self-Driving cars
Satellite Imaging

Is canny the only option when it comes to detecting edges?

No, there are quite a few methods, such as,

Sobel Edge Detection
Prewitt Edge Detection
Laplacian Edge Detection

Though there are quite different methods, Canny edge detection is a widely used technique for detecting edges in images.

Algorithm

The algorithm was developed by John F. Canny in 1986 and has since become a standard technique in image processing.

As we said earlier Canny is a multi-stage algorithm, what that means is that it is an algorithm that comprises many other algorithms, The Sobel edge detection that we mentioned above is one such algorithm in Canny.

Steps:-

Gray scale conversion
Noise reduction
Gradient calculation
Non-maximum suppression
Double Thresholding and hysteresis

1. Gray Scale Conversion

Photo by Luca Herrmann on Unsplash [Edited]

Grayscale is just a 2x2 matrix (image with just one channel), so to convert RGB, HSV, or other formats to Grayscale we gotta find somehow to compress those information to just one channel.

The very first idea you might get is taking the average the three channels to get one, it could work theoretically, but that method doesn’t work as expected. The reason is that the human brain reacts differently to RGB. Eyes are most sensitive to green light, less sensitive to red light, and the least sensitive to blue light.

Therefore, the three colors should have different weights when we generate the gray-scale image (taking average of the channels). That brings us to the Weighted Method which is also called the Luminosity Method. The weights are calculated according to their wavelengths, so the improved formula will be like shown below,

Grayscale = 0.2989 * R + 0.5870 * G + 0.1140 * B

NOTE: In HSL format, the channel L(luminosity) is the grayscale image of it.

2. Noise reduction

In this step we have to reduce unnecessary information in the image, ie. noise, we can achieve that by blurring the image.

There are many kernels for blurring,

Gaussian Filter
Box Filter
Mean Filter
Median Filter

Here we are going to be using Gaussian Filter to blur.

Actually, I already made a whole article on that, so I’m not gonna be explaining it in detail, check it out.

Gaussian Blur Operation from scratch in Python

Here We will be discussing about image filters, convolution, etc.. along with the Python code. As well as, learn to use…

medium.com

Basically, the procedure is to perform convolution operation on an image with the gaussian kernel matrix, which results in a blurred image of the corresponding given image.

import cv2

img_blur = cv2.GaussianBlur(src=img_gray, ksize=(5, 5), sigmaX=3)
# custom implementation for GaussianBlur is given in the above mentioned article

3. Gradient Calculation

Before getting into this section, we wanna make it clear, What is an edge? We can say edge is a part where there is a sudden change in the intensity/colour.

So somehow we wanna capture the change of the intensities in the image, since image is a two dimentional matrix, we can look for change in X and Y direction, and combine those two to one final result.

So we are trying to find gradient vectors (𝜕𝐼/𝜕𝑥 & 𝜕𝐼/𝜕𝑦) that points in the direction of the greatest rate of change in the image intensity, Using those two gradients we generate a single total Gradient, if we plot that Gradient we get an image which consists of the edges of the image.

One way to do it is by using a kernel/filter (which is a discrete approximation of the derivative) we do convolution operation on the image for both X and Y direction seperately, so in the resultant matrices the response will be based on whether it’s corresponding region in the image is an edge or not. An edge region has to have a large response and a flat region should have theoretically zero response.

There are many filters out there, but we are going to be using the Sobel Filter.

So, if we do the convolution operation with the Sobel Filter X on the image we will get a matrix that shows the change in colors in the x direction.

Also, convolving the Sobel Filter Y on the image results in a matrix that shows the change in colors in the y direction.

But, how exactly is this happening?
It is fairly simple, just check out the below illustration, as s sample.

Below is the code and results, if we do that on the real image,

import numpy as np
from scipy.signal import correlate2d


Kx = np.array(
    [[-1, 0, 1],
     [-2, 0, 2],
     [-1, 0, 1]], np.float32
)

Ky = np.array(
    [[-1, -2, -1],
     [0, 0, 0],
     [1, 2, 1]], np.float32
)

Gradient_Y = correlate2d(img_blur, Ky)
Gradient_X = correlate2d(img_blur, Kx)

fig = plt.figure()
plt.subplot(121)
plt.imshow(Gradient_Y, cmap='gray')
plt.title('Gradient$_y$')
plt.subplot(122)
plt.imshow(Gradient_X, cmap='gray')
plt.title('Gradient$_x$')

fig.set_figwidth(8)

To find the total change, we make use of the Pythagorean theorem.

Take Base as the X gradient and Altitude as the Y gradient, so the Hypotenuse will result in the total change.

def scale(x):
    '''scale between 0 and 255'''
    return (x - x.min()) / (x.max() - x.min()) * 255\

G = scale(np.hypot(Gradient_X, Gradient_Y))

plt.title('Sobel Edge Detection Result')
plt.imshow(G, cmap='gray')

We will also be storing the angles between the X and Y gradients (theta) in a variable for further uses, it can be calculated as given below,

EPS = np.finfo(float).eps # used to tackle the division by zero error
theta = np.arctan(Gradient_Y / (Gradient_X + EPS))

But, there is a problem with using np.arctan, if you look at the below illustration, you can notice that even though we got the angle correctly when you do things this way, the directionality may gets lost.

so the angle that you found won’t be in the range of an entire circle.

In this way, if we calculate the theta it will be like follows,

Instead of,

NOTE: picturization of the theta is just for visualization, we won’t be using it as an image.

To tackle this problem mathematicians added some conditions in calculating this, so the new method is implemented in numpy as np.arctan2

So in arctan2, instead of giving the ratio between y and x, we give both as such so that the algorithm can adjust to it.

theta = np.arctan2(Gradient_Y, Gradient_X)

So finally, you understood all the details, and found the Edges.

Now we have to ask you the question, “are we finished?”

It depends on what are you planning to do.

The problems that we currently have are,

The Sobel edge detection algorithm also finds the thickness of the edges.
It is not a binary image, but a grayscale image.
And it also has many noises that we can reduce.

To resolve those issues, we are going to be suppressing the thickness using Non-Maximum Algorithm, and thresholding to make it even better.

4. Non-maximum suppression

In this stage, we are going to suppress the thickness of the edges.

The process is that we loop over all the pixels and take two adjacent pixels of the current pixel and compare with them to find whether the intensity of the current pixel is greater than the two adjacent pixels, if so then continue, if not then set the current pixel intensity to 0.

Here we have to put focus on taking the adjacent pixels, we can’t just take some random pixels around the current pixel, but have to be according to the angle(theta),

The idea is that take the pixels which are almost perpendicular to the angle of the main pixel.

for example, if the theta for the current pixel is 25° then take the pixels as shown below, where (i, j) is the current pixel.

Below is another illustration of, the process, the arrow is represented as the angle of the detected edges, our goal is to detect the gray-shaded pixels only.

NOTE: with the image that we’ve been using the plot for NMS result seems to be fully black, the edges are hard to see so i’m not including it here.

5. Double Thresholding and hysteresis

We’ve only yet reduced the width of the edges, we have to make the border colour consistant (using double thresholding) and remove some noises (using hysteresis).

Pixels with a gradient magnitude above the high threshold are considered strong edges and thus we assign pixel value of 255 to it. Pixels with a gradient magnitude below the low threshold are considered non-edges so they gets pixel value of 0, this process is called Double Thresholding.

Pixels with a gradient magnitude between the low and high threshold are considered weak edges. These pixels are only assign pixel value of 255, if they are connected to a strong edge, else assign pixel value of 0 to it, this process is called hysteresis.

The complete code is available in my GitHub repo;

GitHub — rohit-krish/CVFS: Coding computer vision related algorithms from “scratch”.

You can’t perform that action at this time. You signed in with another tab or window. You signed out in another tab or…

github.com

Conclusion

I hope now you have a clear understanding of Canny Edge Detection Algorithm.

Its not a bad practice to code from scratch, it actually halps you understand things far better than just an explanation. But when you work on real-world projects you don’t have to code from scratch, then you can use libraries such as OpenCV for your help.

In Python using OpenCV, you can generate a gaussian blurred image as below,

import cv2

img = cv2.imread(<img_path>)

# to grayscale
imgGray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# guassian blur
imgBlur = cv2.GaussianBlur(imgGray, (13, 13), 0)

# canny edge detection
imgCanny = cv2.Canny(imgBlur, 50, 50)

If this article helps you in any way, i really appreciate if you could support me through BuyMeACoffee, it really motivates me to produce amazing articles for you guys 🥰.