Edge detection in an Image

Hi, in this post I will show you what is edge detection and how you can implement it in python.

1.What is edge detection?

Edge detection is an image processing technique for finding the boundaries of objects within images. It works by detecting discontinuities in brightness.

Canny edge detection applied to a photograph. src

Common edge detection algorithms include 

1. Sobel
2. Canny
3. Prewitt
4. Roberts

All these algorithms(except canny) defer in the mask that is applied on the image. Canny is a little more complex and includes few more steps.

2.Types of edges

1. Step Edge: The intensity of the image pixels change abruptly, i.e. the difference in the intensity of adjacent pixels in an image is large.
2. Ramp Edge: The intensity change but smoothly.
3. Line Edge: The intensity abruptly changes and then gets back to original value.
4. Roof Edge: The intensity changes smoothly and then gets back to the original value.

3.Gradient

The magnitude of change of intensity is called the gradient of a pixel. The gradient in 2-D is equivalent to the first derivative. The intensity of the pixels in the image can change in horizontally and vertically. The change in intensity along the horizontal direction is called the horizontal gradient or gx and the change in the vertical direction is called the vertical gradient or gy. 

Note - The coordinate system of the image starts from the top left corner with x increasing as we go towards the right and y increasing as we go down. x and y are also sometimes represented as i and j respectively.

The formula shown below calculates the gradient of a pixel. We need to calculate the gradient at every pixel.

SRC: wiki

df/dy and df/dx are horizontal and the vertical gradients. These are very easy to calculate, what we have to do is basically subtract two or three-pixel values for each horizontal and vertical gradient. How we subtract pixels depends on which edge detection algorithm we are using.

3.1Calculating the gradients

The basic idea of calculating the gradient is the same irrespective of the edge detection algorithm we use. The idea is to do addition/subtraction along the horizontal and vertical axis to calculate the horizontal and vertical gradients.  We do this by taking 3 by 3 window of pixels of the original image at a time and doing computations on them. The value that gets calculated is for the center pixel. We create a new 2D array of the same size as the original image to put in the gradient values we will be calculating. Let's see how to calculate the gradients with Sobels edge operator with an example.

Sobels Edge Operator

This is the Sobels edge operator. What it is telling us is for calculating the horizontal gradient(gx) we need to multiply the Gx in the above image to the corresponding values in a 3x3 window of the original image and then take the sum of all these elements and put at the center pixel. eg 

-1*(1,1) + 0*(1,2) + 1*(1,3) and so on.

Let's take a sample image to make this more clear.

This is a 4*5 image. We start by taking the first 3*3 window:

Calculating the horizontal gradient(gx) for this window:

-1*125 + 0*80 + 1*95 + (-2)*90 + 0*240 + 2*200 + (-1)*10  + 0*250 +1*250 = 430

Now we place this in the new 2D array that we create at the center position of this window which is 2,2( with index starting from 1). 

So now the 2D array of the horizontal gradient will look like:

Now we move the 3x3 window one pixel towards the right. The window would look like:

Similarly, we calculate the horizontal gradient(gx) for this window and put it at the center, which would correspond to 2,3. When we reach the end of the image by sliding this 3x3 window we move the window one pixel down and start from the extreme left of the image again(column 1). we do this till we reach the bottom right of the image.

After we calculate all the horizontal gradients in this manner the array of the horizontal gradients would look like this:

Similarly, we would calculate the vertical gradient using the Gy in Sobels edge operator.

The total magnitude of change at a pixel is given by :

For example, the total magnitude of change at a pixel 2,2 is:

square root( square(value of gx at 2,2) + square( value of gy at 2,2) )  

The direction of change is(gradient angle) :

Note that this is the direction of the change of magnitude and not the direction(angle) of the edge. The edge angle is gradient angle + 90.

4.Steps involved in edge detection

1. Filtering: This is done to remove the noise from the image. It may lead to loss of sharpness and the edged may become blurry. 
2. Gradient calculation - In this, we calculate the gradient of each pixel.
3. Thresholding - In this step we threshold the gradients so that only the gradients that are above certain threshold remain. We do this to remove weak edges and some noise. 
4. Localization

5. Code

 import numpy as np  
 import cv2  
 from matplotlib import pyplot as plt  
   
 #read image  
 image = cv2.imread("coins.png", 0)  
 plt.imshow(image, cmap='gray')  
 plt.show()  
 rows, columns = image.shape  
   
 #initializing empty arrays, We take a array of zeros as the 3x3 edge detector is not defined at the top, bottom ,left and right most rows  
 gx = np.zeros((rows, columns))  
 gy = np.zeros((rows, columns))  
 gradient_magnitude = np.zeros((rows,columns))  
 gradient_direction = np.zeros((rows,columns))  
   
 for i in range(1, rows-1):  
   for j in range(1, columns-1):  
     gx[i][j] = -1*image[i-1][j-1] -2*image[i][j-1] -1*image[i+1][j-1] + 1*image[i-1][j+1] + 2*image[i][j+1] + 1*image[i+1][j+1]  
     gy[i][j] = 1*image[i-1][j-1] + 2*image[i-1][j] + 1*image[i-1][j+1] -1*image[i+1][j-1] -2*image[i+1][j] -1*image[i+1][j+1]  
     gradient_magnitude[i][j] = np.sqrt(np.square(gx[i][j]) + np.square(gy[i][j]))  
     gradient_direction[i][j] = np.arctan(gradient_magnitude[i][j])  
   
 plt.imshow(gradient_magnitude , cmap='gray')  
 plt.show()  

References

1. https://en.wikipedia.org/wiki/Edge_detection
2. https://www.mathworks.com/discovery/edge-detection.html
3. https://en.wikipedia.org/wiki/Image_gradient
4. Machine Vision