[CV] 5. Canny Edge Detector with Image Gradients

Published in

jun-devpBlog

7 min readNov 18, 2020

Previous articles deal with about the definiton of filter, what is the filtering and how is it related to correlation and convolution, how to compute gradients in an image. I explained them, beacuse they are necessary components to reach today’s topic: Edge Detection.

1. What is Edge Detection?

Edge detection is an image processing method to find all boundaries of objects such that distinct one from others within an image. More specifically, it refers to a technique that maps an image from 2D array (pixels) to another 2D array containing a set of curves or line segments or contours.

Figure 1. Example of the edge detection given an image, from [1]

There are three criteria that an ideal edge detector should meet.

Good detection: Detector should minimizes the chance of producing false positives (detecting wrong edge: when the detector says there is edge but actually there isn’t) and false negatives (missing real edge: when the detector says there is no edge but actually there is)
Good localization: the detected edges should be as close as possible to the ture edges.
Single response: a detector should output a single detected edge point for a true edge point.

All standards above are well illustrated in the following image.

Figure 2. detected edges with poor edge detector given true edge, from [1, 7]

Now we know what is edge detection and criteria it needs to satisfy. But how does an edge detector find edges within image?

The main idea is to look for strong gradients!

2. Gradients → Edges

As mentioned before, Image gradients are very strong cue for detecting edges within image. This is because pixels belonging to one object are likely to have similar pixel intensities, resulting low gradient magnitudes among those pixels. Boundaries between objects, On the other hands, often have sharp transition in pixel intensities and this results high gradient magnitudes, and the boundaries correspond to edges we want to find. Therefore, by finding pixels within image whose gradient magnitude has a high value, we can locate edges with high probability.

2.1 Summary of General Edge Detection Steps

(1) Smoothing the image to suppress noise

As we’ve seen in the chapter 3, without suppressing the noise, we cannot obtain image gradients valid for edge detection.

(2) Edge enhancement: Image gradient computation with filter for contrast (e.g. Gradient filter)

(3) Edge localization: Find where edges are

Determine which local maxima (meaning the pixels showing the highest gradient magnitude, locally) are actual edges.
Thresholding to remove pixels with not sufficiently strong gradients from consideration.

Note that the standard deviation σ of Gaussian Filter has a huge influence while detecting edges. This is because the Gaussian filter performs smoothing and changes the image structure in accordance with σ, while suppressing noise within image.

**Figure 3. Edge detection results after applying Gaussian filters with 𝝈 = 1 and 𝝈 = 3, from [1, 2]**

Fig 3 shows two results of detected edges from an Panda image after applying Gaussian smoothing with 𝝈 = 1 and 𝝈 = 3, respectively.

One observation is that when larger value of 𝝈 (3 in above) is applied, the only large-scale edges are detected, whereas finer features, edges in detail are detected when 𝝈 = 1.

Why the filter with 𝝈 = 1 keeps finer detail, compared to a filter with 𝝈 = 3?

The answer is, due to the ‘Duality’ between spatial and frequency domain. Recall that we apply Gaussian filtering by convolution, which removes components whose frequency is higher than certain value. This certain value is determined by the standard deviation 𝝈 of Gaussian filter. But then one might asks, Gaussian Filter with 𝝈 = 1 has smaller width than the one with 𝝈 = 3, and therefore 𝝈 = 1 should remove all frequencies higher than 1 and loose finer features in image.

Unfortunately, this is not the case. According to the Duality, what is localized in spatial domain is more distributed in frequency domain and vice versa, as illustrated below.

**Figure 4. Illustration of the Duality between spatial and frequency domain with an example of Gaussian, from [1]**

Gaussian filter with 𝝈 = 1 in spatial domain has larger width in frequency domain than a Gaussian filter with 𝝈 = 3, and therefore it preserve larger frequency components after convolution (Filtering) operation than Gaussian filtering with 𝝈 = 3.

Thus, finer edges survive after Gaussian filtering with smaller 𝝈, and therefore, they are detected by Edge Detector as is shown in the center panel of Fig 3.

3. Canny Edge Detector

Among many approaches for detecting edges, Canny edge detector is a very widely and commonly used edge detector in many computer vision tasks.

Canny edge detector also works in a way described in 2.1, but little more elaborated.

Step 1. Filter an image with the derivative of Gaussian and find magnitude and orientation of gradient

Figure 5. Extracted Gradient information (magnitude) of an image

In order to compute the image gradients for each pixel, x-derivative of Gaussian and y-derivative of Gaussian filters are used. Then the magnitude and orientation maps are built based on computed derivatives with respect to x and y for each pixel, as follows.

**Figure 6. Computation of Magnitude and Orientation based on x and y derivatives, from [1.3]**

Step 2. Apply Non-Maximum Suppression (NMS)

By filtering with Gaussian, we obtain image gradients, reducing the influence of noise within image. However, this introduces a drawback that the edges in image are no longer single-pixel, but become a thick region due to the smoothing effect.

According to the criterion: Single response, it needs to be fixed to output a single-pixel curve (or line segment), not a region (multiple-pixels).

In order to do so, a technique, which is called Non-Maximum Suppression, is applied. It is to keep only the local maxima pixel and to discard non-maxima pixels in an edge region, resulting thiner, and ideally single-pixel, edges.

The process for NMS is as follows.

Given the current pixel, find two neighboring pixels in the same direction as the computed orientation of current pixel.
Compare the magnitudes from three (current and two neighboring pixels)
If the magnitude of current pixel is the maximum, keep its magnitude. Otherwise discard the pixel from the edge detection process.
Repeat the above stages for each pixel

By completing the NMS for each pixel in image, the detected edge regions get thinner. Figure 7 is the illustration of NMS given one pixel q.

**Figure 7. Illustration of NMS, from [1, 4]**

Step 3. Hysteresis Thresholding

The last step of NMS is Hysteresis Thresholding. As edges can be seen as boundaries between objects within image, there is often a sharp transition in pixel intensities neighboring an edge, and therefore such pixels have high magnitude value. Similarly, we can interpret this observation as a pixel with high magnitude is likely to be an edge that we want to detect.

Therefore, many detectors are built with thresholding in order to remove non-probable pixels. It applies to Canny edge detector as well. One difference is that while others use a single threshold, Canny edge detector use two thresholds: high and low, and this is called Hysteresis thresholding.

Before getting into Hysteresis thresholding, Let’s take a look what could happen when single-value thresholding. Think of a case when a certain threshold theta is given. Any edge whose magnitude (|grad|) is lower than theta will be discarded, and this indicates the lost of edge in image.

Equation 1. Thresholding for each pixel p given threshold theta

Here is an example. If the chosen theta is higher than the lowest magnitude of true edges, we loose them. In the following image, we lost some edges in woman’s chin due to the thresholding.

In order to reduce such lost, Hysteresis thresholding uses a high and low thresholds. The main idea of Hysteresis thresholding is

Use the high threshold to find “strong edges”, which is sure to be considered as an edge, to start edge chain
Use the low threshold to find “weak edges”, which connect empty segment between “strong edges”

Let’s take a look at how Hysteresis thresholding works with an example.

**Figure 8. Hysteresis thresholding with example with 2 thetaL maxVal and minVal**

Firstly, any detected edges, after NMS, whose magnitude is smaller than minVal (low threshold) will be discarded. In Fig 8, not every pixel of the edge surpasses the maxVal and therefore, edge curve A will partially survive after thresholding with maxVal. In order to compensate this loss, Hysteresis thresholding uses the minVal. As long as such lost segment (noted as C) has still higher magnitude than minVal, then it is also considered as a edge to get a full edge curve of A.

Note that this approach only save edge such that (1) magnitude is higher than minVal, and (2) the edge should be connected to one of STRONG EDGES. In Fig 8, the edge B has also a magnitude above minVal, but it is not connected to Strong-edge A and therefore discarded.

After Hysteresis Thresholding, we obtain the edge-detection map with less true-edge lost as following image (focus on her chin!).