A Beginners Guide to Computer Vision (Part 2)- Edge Detection
Learn the algorithms behind edge detection and their implementation.
This is the continuation to my previous blog, please go through it before preceding further in this topic.
What is edge detection?
Edge detection means finding the boundary in an image like the one, shown above.
To assess the quality of edge detector we use precision and recall curves.
Ground Truth(GM) in the above image is drawn by the humans and Result of method(RM) is obtained after running the edge detector over the target image. True positive is the intersection area of ground truth and result of method(Edges predicted by the algorithm). Precision is the ratio of true positive and Result of method. Recall is the ratio of true positive and ground truth. Below is the plot of precision-recall curves of different edge detectors in comparison with human. Our aim is to develop an edge detector whose precision-recall curve is above the human mark.
Derivative of an Image
Formula of derivative for continuous functions is something you learned in your high school.
But this formula is for continuous functions, images are discrete!!. So when we consider the neighborhood of pixel in x-direction as shown in above formula. Then Δx will be equal to 1. The numerator in above formula is now just the difference of intensities of pixel of under consideration and pixel in front of it. We call this as forward difference derivative. Below are the masks used for finding the derivative of an image in x-direction.
Backward difference [-1 1]
Forward difference [1 -1]
Central difference [-1 0 1 ]We can find the derivative of an image by convolving the image by the masks above. We generally use 3X3 mask for more accurate results. Below is the code snippet for finding the derivatives of image.
dx = np.array([[-1,0,1],
[-1,0,1],
[-1,0,1]])
dy = np.array([[-1,-1,-1],
[0,0,0],
[1,1,1]])
dx_img = ndimage.convolve(guassian_img, dx)
dy_img = ndimage.convolve(guassian_img, dy)
Prewitt Edge Detector
Any edge detector pipeline starts by filtering. Prewitt edge detector uses mean mask for filtering. After filtering, we will find the derivatives of the image in X and Y directions. After differentiating, we will find the resultant from both derivatives you found before. Then we apply a threshold intensity and convert the image into a binary image.
Sobel Edge Detector
It is almost similar to Prewitt edge detection, the only difference is we use a different mask to filter the image. The mask used is shown in the flowchart below.
Marr Hildreth Edge Detector (Laplacian of Gaussian)
Marr Hildreth edge detector’s inspiration is taken from neuroscience. Marr’s filter is a laplacian filter. Laplacian filters are very sensitive to noise. The Laplacian of an image highlights regions of rapid intensity change and is therefore often used for edge detection. So before applying laplacian we need to filter the image properly using Gaussian filter. Convolution (Correlation) operation is associative, we can convolve the Gaussian smoothing filter with the Laplacian filter first of all, and then convolve this hybrid filter with the image to achieve the required result. The results of this is shown in the image below.
The shape of LoG is like a inverted hat. The above image also shows the 9X9 LoG mask when sigma = 1.4. This mask can be directly convolved over the image to obtain LoG of that image. What we do after obtaining the LoG of an Image?
Above image is the plot of intensity variation along x-axis of an image containing a step edge. Right hand side of this image show the plot of LoG of image. There is a zero crossing in LoG when there is an edge in the image. So, this is an evident proof that we can detect the edge from zero crossings. Below is the code snippet on applying threshold over the zero crossings.
log_img = ndimage.gaussian_laplace(gray_img, 1.4)
threshold =-0.05
log_final = np.zeros(log_img.shape)
w,h = log_img.shape
for x in range(1,w-1):
for y in range(1,h-1):
window = log_img[x-1:x+2,y-1:y+2]
point = log_img[x,y]
wmax = window.max()
wmin = window.min()
if point==0.0 and wmax>0.0 and wmin<0.0:
zeroCross=1
elite point>0.0:
zeroCross= True if wmin<0.0 else False
else:
zeroCross= True if wmin<0.0 else False
if (wmax-wmin)>threshold and zeroCross:
log_final[x,y] = 1plt.imshow(log_final, cmap = plt.get_cmap('gray'))
plt.show()
Quality of an edge
There are three essential qualities using which we can assess the quality of an edge.Robust to noise, localization, and exact responses. Canny Edge Detector is developed keeping in mind about the quality of an edge.
Canny Edge Detector
Canny edge detector also starts with Gaussian filtering. After filtering, image will be differentiated in X and Y directions. After differentiating, Magnitude and gradient matrix will be calculated. A new method called Non maximum suppression(NMS) is introduced in this pipeline to reduce the response and make the response into a single chain.After NMS, We apply a threshold to convert the image into a binary image but we implement it bit differently to make the edge bit localized.
You are already familiar upto the differentiation part, we calculate the gradients with a formula similar to the one shown in the code snippet below.
gradient = np.degrees(np.arctan2(dy_img,dx_img)) Gradient of an edge is perpendicular to it. We consider the gradient “zero” if the gradient line in horizontal. Below is the image that make you to understand this concept very clearly.
Above is the image obtained after plotting the the gradient matrix with Spectral color map.
Before understanding NMS have a look at its implementation
In NMS, we loop through every pixel the image and find it’s type as shown in above figure. Then we compare the pixel under consideration(white) with the other pixels(black) in the patch as shown in above image. If the pixel under consideration is having more intensity then we consider that pixel and suppress the remaining pixels. Now we get an image with single pixel edges.
In Hysteresis Threshold method, we maintain two threshold (low and high).
If the intensity of a pixel is more that high threshold, then we consider that pixel as a part of our image.
If the intensity of a pixel is less that low threshold, then we don’t consider that pixel as a part of our image.
If the intensity of a pixel is between high and low threshold, we look if any of it’s neighboring pixel have intensity more than high threshold. If that comes out to be true than we consider that pixel as part of our image.Below is the image after applying hysteresis threshold
Here is my special video on canny edge detector for understanding it more better.
All the code for implementation is in this link
offfff.. Yeah that’s the end of this blog on edge detection. Stay tuned for more on computer vision.
