Overview
Edge detection is a process that involves mathematical methods to find points in an image where the brightness of pixel intensities clearly changes or we can say that it is an image processing technique for finding the boundaries of objects within images. It works by detecting discontinuities in brightness. In the industry, the most commonly used edge detection algorithms are Sobel, Canny, Prewitt and Roberts methods.
How it Works
The first thing we are going to do is find the gradient of the grayscale image, allowing us to find edge-like regions in the x and y direction. The gradient is a multi-variable generalization of the derivative. While a derivative can be defined on functions of a single variable, for functions of several variables, the gradient takes its place. Also, the gradient is a vector-valued function, as opposed to a derivative, which is scalar-valued. Like the derivative, the gradient represents the slope of the tangent of the graph of the function. More precisely, the gradient points in the direction of the greatest rate of increase of the function, and its magnitude is the slope of the graph in that direction.
In computer vision, transitioning from black-to-white (0 to 255) is considered a positive slope, whereas a transition from white-to-black (255 to 0) is a negative slope.
Edge detection is used to detect outlines of an object and boundaries between objects (that tend to produce sudden changes in the image intensity) and the background in the image. Image differentiation enhances edges and other discontinuities (such as noise) and de-emphasizes areas with slowly varying gray-level values. Sharpening filters are based on first-and second order derivatives. Comparing the response between the first- and second-order derivatives, the following are the conclusions :
- First-order derivatives generally produce thicker edges in an image
- Second-order derivatives have stronger response to fine detail, such as thin lines and isolated points
- First-order derivatives generally have a stronger response to a gray-level step
- Second-order derivatives produce a double response at step changes in gray level
We will now look at the implementation of Canny Edge Detection using Python and OpenCV but if you are a beginner in the world of computer vision, it will be good to understand the basics at Python for Computer Vision with OpenCV.
Edge Detection
Edge detection is nothing but a filtering process. There are so many types of filters like Sobel, Roberts, Prewitt and Canny filters available, these filters are based on the first-order derivative. The Laplacian of Gaussian is based on the Second-order derivative. The type of filter to be used depends on the application and the efficiency too depends on various factors like type of filter and the value of threshold, etc. Some other filters include Morphological Gradient & Laplacian.
Canny Edge Detection
Canny edge detection uses linear filtering with a Gaussian kernel to smooth noise and then computes the edge strength and direction for each pixel in the smoothed image. Candidate edge pixels are identified as the pixels that survive a thinning process called non-maximal suppression. In this process, the edge strength of each candidate edge pixel is set to zero if its edge strength is not larger than the edge strength of the two adjacent pixels in the gradient direction. Thresholding is then done on the thinned edge magnitude image using hysteresis. In hysteresis, two edge strength thresholds are used. All candidate edge pixels below the lower threshold are labeled as non-edges and all pixels above the low threshold that can be connected to any pixel above the high threshold through a chain of edge pixels are labeled as edge pixels.
The Canny edge detector requires the user to input three parameters. The first is sigma, the standard deviation of the Gaussian filter specified in pixels. The second parameter low is the low threshold which is specified as a fraction of a computed high threshold. The third parameter high is the high threshold to use in the hysteresis and is specified as a percentage point in the distribution of gradient magnitude values for the candidate edge pixels.
Code for Implementation for Canny Edge
import cv2
import numpy as np
cap = cv2.VideoCapture(0)
while(1):
ret, frame = cap.read()
hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
lower_red = np.array([30,150,50])
upper_red = np.array([255,255,180])
mask = cv2.inRange(hsv, lower_red, upper_red)
res = cv2.bitwise_and(frame,frame, mask= mask)
cv2.imshow('Original',frame)
edges = cv2.Canny(frame,100,200)
cv2.imshow('Edges',edges)
k = cv2.waitKey(5) & 0xFF
if k == 27:
break
cap.release()
cv2.destroyAllWindows()
Calculation of Derivative of An Image
The derivative of a matrix is calculated by an operator called the Laplacian. In order to calculate a Laplacian, you will need to calculate first two derivatives, called derivatives of Sobel, each of which takes into account the gradient variations in a certain direction: one horizontal and the other vertical.
- Horizontal Sobel derivative (Sobel x): It is obtained through the convolution of the image with a matrix called kernel which has always odd size. The kernel with size 3 is the simplest case.
- Vertical Sobel derivative (Sobel y): It is obtained through the convolution of the image with a matrix called kernel which has always odd size. The kernel with size 3 is the simplest case.
- Convolution is calculated by the following method: Image represents the original image matrix and filter is the kernel matrix
Factor = 11 – 2- 2- 2- 2- 2 = 3
Offset = 0 Weighted Sum = 124*0 + 19*(-2) + 110*(-2) + 53*11 + 44*(-2) + 19*0 + 60*(-2) + 100*0 = 117
O[4,2] = (117/3) + 0 = 39
So in the end to get the Laplacian (approximation) we will need to combine the two previous results (Sobelx and Sobely) and store it in laplacian.
Parameters
- cv2.Sobel(): The function cv2.Sobel(frame,cv2.CV_64F,1,0,ksize=5) can be written as: cv2.Sobel(original_image, ddepth, xorder, yorder, kernelsize) where the first parameter is the original image, the second parameter is the depth of the destination image. When ddepth=-1/CV_64F, the destination image will have the same depth as the source. The third parameter is the order of the derivative x. The fourth parameter is the order of the derivative y. While calculating Sobelx we will set xorder as 1 and yorder as 0 whereas while calculating Sobely, the case will be reversed. The last parameter is the size of the extended Sobel kernel; it must be 1, 3, 5, or 7.
- cv2.Laplacian: In the function cv2.Laplacian(frame, cv2.CV_64F) the first parameter is the original image and the second parameter is the depth of the destination image.When depth=-1/CV_64F, the destination image will have the same depth as the source
Steps to perform Canny Edge Detection
Filter out any noise. The Gaussian filter is used for this purpose. An example of a Gaussian kernel of size =5 that might be used is shown below:
Find the intensity gradient of the image. For this, we follow a procedure analogous to Sobel:
Apply a pair of convolution masks (in X and Y directions):
Find the gradient strength and direction with:
The direction is rounded to one of four possible angles (namely 0, 45, 90 or 135)
Non-maximum suppression is applied. This removes pixels that are not considered to be part of an edge. Hence, only thin lines (candidate edges) will remain.
Hysteresis: The final step. Canny does use two thresholds (upper and lower):
If a pixel gradient is higher than the upper threshold, the pixel is accepted as an edge
If a pixel gradient value is below the lower threshold, then it is rejected.
If the pixel gradient is between the two thresholds, then it will be accepted only if it is connected to a pixel that is above the upper threshold.Canny recommended a upper:lower ratio between 2:1 and 3:1.
Canny Edge Detector Algorithm Stages
Noise Reduction
Since edge detection is susceptible to noise in the image, first step is to remove the noise in the image with a 5×5 Gaussian filter. It is important to understand that the selection of the size of the Gaussian kernel will affect the performance of the detector. The larger the size is, the lower the detector’s sensitivity to noise. Additionally, the localization error to detect the edge will slightly increase with the increase of the Gaussian filter kernel size. A 5×5 is a good size for most cases, but this will also vary depending on specific situations.
Finding Intensity Gradient of the Image
An edge in an image may point in a variety of directions, so the Canny algorithm uses four filters to detect horizontal, vertical and diagonal edges in the blurred image. Smoothened image is then filtered with a Sobel kernel in both horizontal and vertical direction to get first derivative in horizontal direction and vertical direction. From these two images, we can find edge gradient and direction for each pixel. Gradient direction is always perpendicular to edges. It is rounded to one of four angles representing vertical, horizontal and two diagonal directions.
Non-maximum Suppression
Non-maximum suppression is applied to find “the largest” edge. After applying gradient calculation, the edge extracted from the gradient value is still quite blurred. With respect to criterion 3 listed above, there should only be one accurate response to the edge. Thus non-maximum suppression can help to suppress all the gradient values (by setting them to 0) except the local maxima, which indicate locations with the sharpest change of intensity value. After getting gradient magnitude and direction, a full scan of image is done to remove any unwanted pixels which may not constitute the edge. For this, at every pixel, pixel is checked if it is a local maximum in its neighborhood in the direction of gradient.
Hysteresis Thresholding
This stage decides which are all edges are really edges and which are not. For this, we need two threshold values, minVal and maxVal. Any edges with intensity gradient more than maxVal are sure to be edges and those below minVal are sure to be non-edges, so discarded. Those who lie between these two thresholds are classified edges or non-edges based on their connectivity. If they are connected to “sure-edge” pixels, they are considered to be part of edges. Otherwise, they are also discarded
This stage also removes small pixels noises on the assumption that edges are long lines.So what we finally get is strong edges in the image.
OpenCV Canny Function
OpenCV puts all the above in single function, cv2.Canny(). Syntax of the function is:
edges = cv2.Canny(img,100,200, aperture_size =3, L2gradient = True )
- First argument is our input image
- Second and third arguments are our minVal and maxVal respectively
- Third argument is aperture_size. It is the size of Sobel kernel used for find image gradients. By default it is 3
- Last argument is L2gradient which specifies the equation for finding gradient magnitude
