[Edge detection] Canny edge detector

Process of Canny edge detection algorithm

There are three well differentiated steps:
1.-Apply Gaussian filter to remove noise
2.-Apply non-maximum suppression to remove useless edges
3.-Apply hysteresis to add well connected edges

1.-Apply Gaussian filter

Gaussian filter has been explained separately.

2.-Apply non-maximum suppression

The general idea of this process is that after applying a Gaussian filter to remove the noise, we need a tool to detect edge values such as Sobel filter. The value generated by doing the square root of both partial values squared will be denominated intensity from now on. The edges obtained by doing a Sobel filtering have different intensity, and the goal of non-maximum suppression is to keep the highest intensity edge pixels while removing the others, because usually a edge consist of a thin line of pixels rather than many of them.

When Sobel is used during this process, horizontal and vertical templates are:
[latex]
G_x = \begin{bmatrix}
-1 & 0 & +1 \\
-2 & 0 & +2 \\
-1 & 0 & +1
\end{bmatrix}

\quad \text{and} \quad

G_y = \begin{bmatrix}
+1 & +2 & +1 \\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix}
[/latex]

The reason why I used a slightly different templates than in the Sobel filter entry is explained there.

Have a look to this simple edge where intensities are represented using different colors (the whiter, the higher intensity), and imagine that intensity represents the height of each pixel so that we want to remove all except the one in the top of the ridge. We need to find the highest intensity element, and for this task we can look at the direction of each pixel to go upwards.

Directions can be obtained by the Gx and Gy values used for calculating the intensity, by simply:

[latex]
\theta = \arctan \frac{G_y}{G_x}
[/latex]

The direction is the vector orientation.

Depending on the angle, directions can be vertical, horizontal, diagonal-left, diagonal-right.

Horizontal: 0 to 22.5 & 157.5 to 180 degrees

Vertical: 67.5 to 112.5 degrees

Diagonal-Left: 112.5 to 157.5

Diagonal-Right: 22.5 to 67.5

Now that for each pixel we have an intensity and direction, note that there can only be 2 more pixels surrounding our pixel in that direction, and we need to compare it with this two pixels. So if we have a pixel which has a vertical direction, it will be compared with the pixels above and below it (if no problem is encountered due to the borders). When comparing it, if a higher value is found, our pixel will be set to zero (black). Otherwise its value will be preserved.

Let us say that I have a simple figure like this, to which I applied Sobel filter. Let us focus on a certain region (the right-bottom corner above the red line).

Figure (20×20)

After Sobel

On the first picture I wrote the intensity values whereas on the second one I depicted its orientation. In the last picture we can see which pixels were preserved and which were set to zero.

Intensity

Directions

Result after comparing neighbors

3.-Apply hysteresis

Hysteresis’ process basically aims to threshold the whole image. Nonetheless, it does not use a single threshold, but two instead. We need to understand this as an attempt to extend the threshold giving to the algorithm a higher flexibility. For instance, I may find a pixel which is above the threshold and therefore considered as an edge, but right after it I may find another pixel which is part of the edge but its intensity is slightly below our threshold. That is the reason why the algorithm uses two thresholds.

The algorithm may be as:

Iterate over rows
Iterate over columns
If pixel is above threshold
Make this pixel white
For each surrounding pixel: if it is above the second threshold
Make surrounding pixel white
Else: make surrounding pixel black
Else: make this pixel black