Image Processing Algorithms: Canny Edge Detector
An explanation using the OpenCV C++ Library
The Background
What are edges?
In image processing, edges simply represent sets of points within an image where the image brightness has a high rate of change (more on this later).
Why detect edges?
Edge detection is an important part of image processing as it facilitates the computational identification and separation of images into distinct parts. This has wide ranging applications, from photo editing software like photoshop, to pedestrian awareness software used by autonomous vehicle initiatives like Tesla.
Development of the Canny Edge Detector
The Canny Edge Detector (CED) was developed in 1986 by John F. Canny to detect a wide range of edges in images. CED aims to satisfy three main criteria. First, the detection should accurately reveal as many edges as possible. Second, the distance between the edges that are detected and the actual edges present in the source image must be minimized. Third, an edge should only be detected once within an image.
The Algorithm
CED uses a multistage algorithm to detect edges. The process is as follows:
- Apply a Gaussian Filter
- Compute the image gradient
- Apply non-maximum suppression
- Apply double thresholding
- Apply hysteresis
We’ll revisit each of these in more detail as we walkthrough the example implementation.
The Implementation
OpenCV is an open-source computer vision library written in C++ (also with bindings in Python, Java, and MATLAB, which we won’t be discussing in this post). A comprehensive coverage of the features and capabilities of OpenCV is outside of this post’s scope, so I will briefly go over the relevant parts as they come up.
cv::Mat
Before we get to the meat of the CED, we need to take a look at how we’ll be working with our image data. OpenCV implements a matrix type cv::Mat to load, store, and manipulate image data. Conceptually, the cv::Mat type can be thought of as a two-dimensional array, with each element representing a pixel value. Simply iterate through the array to access or mutate pixel values.
For three-channel images (color images), an array of cv::Mat objects is used, with one matrix per color channel. In other words, a three-dimensional array, with the third dimension representing the red, green, and blue color channels.
However, because we will be doing edge detection, the color values of an image aren’t very relevant, so we’ll be loading all our images in grayscale, as single-channel cv::Mat objects.
Loading an image for CED
String imgName = argv[1];
String imgPath = "../testImages/" + imgName;
Mat src = imread(imgPath, IMREAD_GRAYSCALE);The above code uses cv::imread to load an image into a the Mat object src . The first parameter specifies the image path and the second parameter provides the IMREAD_GRAYSCALE flag, so our image will be loaded in grayscale.
CED, Step 1: Apply Gaussian Filter
A Gaussian filter is used to smooth the source image so as to remove image noise that may cause false-positive edge detection. Gaussian filters work by replacing every pixel in an image with a weighted average of neighbor pixels. The pixels are weighted similar to a normal distribution (hence, the ‘Gaussian’) where farther neighbor pixels have decreasing weights. The number of neighbors to consider within the average is variable, and the smoothness of the image after being filtered is dependent on the size of the region being averaged over.
Mat blurred;
blur(src, blurred, Size(3, 3));For this CED implementation, we will simply use the built in function cv::blur to apply the Gaussian filter. The first parameter is the source Mat object, the second parameter is the destination Mat object, and the third parameter defines the size of the region being averaged over.
CED, Step 2: Compute Image Gradient
First, what is an image gradient? An image gradient is the two-dimensional gradient vector representing the directional change in intensity (brightness) of an image. These intensity values provide the information necessary to determine the positions and polarities of edges.
The image gradient is computed from convolving the source image with a derivative filter to get the first-order partial derivatives, which together, form the (image) gradient vector representation. A potential edge is simply identify by the values with the highest rates of change, so the derived values with the highest magnitude are potential edge candidates.
Mat xComponent, yComponent;
Sobel(blurred, xComponent, CV_64F, 1, 0, 3);
Sobel(blurred, yComponent, CV_64F, 0, 1, 3);We use the cv::Sobel method to compute the x and y gradient vector components. Note, the CV_64F parameter value is simply an output type (in this case, our output will be a Mat object with pixel values represented as 64-bit floats), and the remaining three parameters specify the component to output (x or y) and the kernel size for the Sobel derivative filter (a kernel simply holds a filter, so for our current purposes we can think of them as the same).
CED, Step 3: Non-Maximum Suppression
Non-maximum suppression is an edge thinning technique used to remove extraneous edge candidates. It works by iterating through all pixel values, comparing the current value with the pixel value in the positive and negative gradient directions, and suppressing the current value if it does not have the highest magnitude relative to its neighbors. For our implementation, we will be using a set of discrete gradient directions.
Mat magnitude, angle;
cartToPolar(xComponent, yComponent, magnitude, angle, true);First we use the cv::cartToPolar method to calculate the gradient magnitude and direction.
normalize(magnitude, magnitude, 0, 1, NORM_MINMAX);Then, we normalize the magnitude so as to produce more evenly distributed data.
int neighbor1X, neighbor1Y, neighbor2X, neighbor2Y;
float gradientAngle; for (int x = 0; x < blurred.rows; x++) {
for (int y = 0; y < blurred.cols; y++) {
gradientAngle = angle.at<float>(y, x);
if (abs(gradientAngle) > 180)
gradientAngle = abs(gradientAngle-180);
else
gradientAngle = abs(gradientAngle);
if (gradientAngle <= 22.5) {
neighbor1X = x-1; neighbor1Y = y;
neighbor2X = x+1; neighbor2Y = y;
} else if (22.5 < gradientAngle <= 67.5) {
neighbor1X = x-1; neighbor1Y = y-1;
neighbor2X = x+1; neighbor2Y = y+1;
} else if (67.5 < gradientAngle <= 112.5) {
neighbor1X = x; neighbor1Y = y-1;
neighbor2X = x; neighbor2Y = y+1;
} else if (112.5 < gradientAngle <= 157.5) {
neighbor1X = x-1; neighbor1Y = y+1;
neighbor2X = x+1; neighbor2Y = y-1;
} else if (157.5 < gradientAngle <= 202.5) {
neighbor1X = x-1; neighbor1Y = y;
neighbor2X = x+1; neighbor2Y = y;
} if ((0 <= neighbor1X < blurred.rows)
&& (0 <= neighbor1Y < blurred.cols)) {
if (magnitude.at<float>(y, x) < magnitude.at<float> (neighbor1Y, neighbor1X)) {
magnitude.at<float>(y, x) = 0;
continue;
}
}
if ((0 <= neighbor2X < blurred.rows)
&& (0 <= neighbor2Y < blurred.cols)) {
if (magnitude.at<floa t>(y, x) < magnitude.at<float> (neighbor2Y, neighbor2X)) {
magnitude.at<float>(y, x) = 0;
continue;
}
}
}
}
Now we can apply the non-maximum suppression. It looks like a lot is going on, but in reality, it’s quite simple. Each pixel value is iterated through, the angle is normalized, and then the magnitude of the pixel is compared to its neighbors in the appropriate cardinal or ordinal directions. When necessary, the pixel value is suppressed (set to 0).
CED, Step 4: Apply Double Thresholding
Double thresholding is used to categorize the remaining edge pixels into three categories using a low and high threshold value. If an edge pixel value is greater than the high threshold value, it is categorized as a strong edge pixel, with a high probability of being an edge. If an edge pixel value is less than the high threshold value, but greater than the low threshold value, it is categorized as a weak edge pixel, with some probability of being an edge. If an edge pixel value is less than both the high and low threshold values, it is categorized as having a very low probability of being an edge, and the value is suppressed.
float magMax = 0.2, magMin = 0.1;
Mat strong = Mat::zeros(magnitude.rows, magnitude.cols, CV_32F); Mat weak = Mat::zeros(magnitude.rows, magnitude.cols, CV_32F);
Mat suppress = Mat::zeros(magnitude.rows, magnitude.cols, CV_32F);
float gradientMagnitude; for (int x = 0; x < magnitude.cols; x++) {
for (int y = 0; y < magnitude.rows; y++) {
gradientMagnitude = magnitude.at<float>(x, y);
if (gradientMagnitude > magMax)
strong.at<float>(x, y) = gradientMagnitude;
else if (gradientMagnitude <= magMax && gradientMagnitude > magMin)
weak.at<float>(x, y) = gradientMagnitude;
else
suppress.at<float>(x, y) = gradientMagnitude;
}
}
We accomplish this by defining a set of destination Mat objects to hold the categorized values and then simply iterate through the magnitude Mat and compare the edge pixel values to our defined magMax and magMin values, adding them to their respective Mat object as necessary.
CED, Step 5: Hysteresis
Hysteresis is the final step of the CED algorithm. It determines which of the values in the weak edge category should be included in the final edge detection image. The process simply checks to see if a weak edge pixel is connected (neighbored by) a strong edge pixel. If so, the weak edge is included, otherwise it’s suppressed.
for (int x = 0; x < weak.cols; x++) {
for (int y = 0; y < weak.rows; y++) {
if (weak.at<float>(x, y) != 0) {
if ((strong.at<float>(x+1, y))
|| (strong.at<float>(x-1, y))
|| (strong.at<float>(x, y+1))
|| (strong.at<float>(x, y-1))
|| (strong.at<float>(x-1, y-1))
|| (strong.at<float>(x+1, x-1))
|| (strong.at<float>(x-1, y+1))
|| (strong.at<float>(x+1, y-1)))
strong.at<float>(x, y) = weak.at<float>(x, y);
}
}
}We can implement this by iterating through the Mat object for weak pixel values, and checking if the coordinate value in the strong pixel value Mat object has non-zero neighboring values. If so, we add the weak pixel value back into the strong pixel value Mat object.
And finally, we are left with our final resulting image.
Further Reading
If you would like to learn more about edge detection algorithms, OpenCV, or computer vision, here are some good next-step resources to check out:
