Edge Detection

The new topic that we will see is closer to what we call "image processing" compared to what we already saw. Indeed, we will talk about the edge detection. It's the name used to describe a set of mathematical methods which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities. It exists many edge detection filters and I will present the most famous ones which always provide interesting results. Basically, the method used to apply these filters just consists in using certain convolution matrices (sometimes two at the same time for just one filter). I already explained the particularities of the convolution matrices and how to apply them on an image in this post. But let's reuse this previous understandable example :

On the left of the multiplication operator, there is the image matrix representation of the Green channel and on the right, there is a convolution matrix (also named kernel) with dimensions 3x3 and which is entirely filled with the value 0 except in one index containing the value 1. The result, where the value 42 circled in red appears, represents the new value that replaces the initial value 50 circled in red in the image matrix representation after applying the convolution matrice as follows :

new value = 40*0 + 42*1 + 46*0 + 46*0 + 50*0 + 55*0 + 52*0 + 56*0 + 58*0 = 42.

So we calculate the sum of products of the current pixel component and its 8 neighbors by the corresponding values, location based, in the convolution matrix (as a pixel has 3 channels : Red, Green and Blue, there are 3 sums to calculate). Note that in some cases, the new value must be divided by what we call a normalization factor as you will see. Now we can definitely start this new tutorial...

Prewitt filter :

The Prewitt operator is based on convolving the image with a small, separable, and integer valued filter in horizontal and vertical directions and is therefore relatively inexpensive in terms of computations. It was developed by Judith M. S. Prewitt. The convolution matrices' dimensions are 3x3 and have a normalization factor equal to 3 (like the Sobel filter). They must be filled with these following values :

Horizontal kernel

-1	-1	-1
0	0	0
1	1	1

Vertical kernel

-1	0	1
-1	0	1
-1	0	1

Sobel filter :

As you can see, the main difference with the Sobel filter is just the values of the convolution matrices. It was developped by Irwin Sobel who presented the idea of an "Isotropic 3x3 Image Gradient Operator" at a talk at the Stanford Artificial Intelligence Project (SAIL) in 1968.

Horizontal kernel

-1	0	1
-2	0	2
-1	0	1

Vertical kernel

-1	-2	-1
0	0	0
1	2	1

Roberts filter :

The Roberts filter was one of the first edge detectors and was initially proposed by Lawrence Roberts.

Normalization factor : 1 (like the Laplacian filter)

Horizontal kernel

0	0	0
0	-1	0
0	0	1

Vertical kernel

0	0	0
0	0	1
0	-1	0

Kirsch filter :

The Kirsch operator is a non-linear edge detector that finds the maximum edge strength in a few predetermined directions. It is named after the computer scientist Russell A. Kirsch.

Normalization factor : 15

Horizontal kernel

-3	-3	-3
-3	0	-3
5	5	5

Vertical kernel

-3	-3	5
-3	0	5
-3	-3	5

Laplacian filter :

The Laplacian of an image highlights regions of rapid intensity change and is therefore often used for edge detection (see zero crossing edge detectors). The Laplacian is often applied to an image that has first been smoothed with something approximating a Gaussian smoothing filter in order to reduce its sensitivity to noise (see my post on the blurring filters).

Horizontal kernel

0	-1	0
-1	4	-1
0	-1	0

Vertical kernel

-1	-1	-1
-1	8	-1
-1	-1	-1

The get_prewitt, get_sobel, get_roberts, get_kirsch and get_laplacian functions return 2 convolution matrices as they are respectively defined above. To see how they look like, look at the following get_high_pass function. Note that abs is the absolute value function (details).

High-pass filter :

  ⇒ 

The high-pass filter can be used to make an image appear sharper. This filter emphasizes fine details in the image – exactly the opposite of the low-pass filter. Unfortunately, while low-pass filtering smooths out noise, high-pass filtering does just the opposite: it amplifies noise. You can get away with this if the original image is not too noisy; otherwise the noise will overwhelm the image. High-pass filtering can also cause small, faint details to be greatly exaggerated. An over-processed image will look grainy and unnatural, and point sources will have dark donuts around them. So while high-pass filtering can often improve an image by sharpening detail, overdoing it can actually degrade the image quality significantly. To try this filter, you just have to apply a single convolution matrix (as I explained just before) with dimensions 3x3 and which must be filled with these values :

0	-1	0
-1	5	-1
0	-1	0

MDIF filter :

The last filter, which probably generate the best result, is the MDIF filter. Here again you will have to use two convolution matrices for an horizontal and then a vertical edge detection. These convolution matrices have the same dimensions : 5x5. And finally, the normalization factor is 12 and the convolution matrices must be filled with these values :

Horizontal kernel

0	-1	-1	-1	0
-1	-2	-3	-2	-1
0	0	0	0	0
1	2	3	2	1
0	1	1	1	0

Vertical kernel

0	-1	0	1	0
-1	-2	0	2	1
-1	-3	0	3	1
-1	-2	0	2	1
0	-1	0	1	0

The get_mdif function returns 2 convolution matrices as they are respectively defined above.

To finish, here is a last trick you can use to detect edges (without kernels) and at the same time, get the impression that your image is now a grey or white etching in relief like these 2 illustrations :

 

You must convert your image in grey level with the method of your choice (here are the methods we already saw). And as the grey level verifies Red=Green=Blue in each (Red,Green,Blue) pixel, let's assume that p0 is the Red or Green or Blue pixel component of the current pixel during the browsing of your image matrix representation and that p1, p2, p3, p4, p5, p6, p7, p8 are the 8 pixel components which surround p0 and of the same pixel channel. If you want to apply a grey etching for example, just replace the current pixel by (new value, new value, new value) where
new value = 8*p0 - p1 - p2 - p3 - p4 - p5 - p6 - p7 - p8 and then
new value = new value + 128 and finally new value = 255 - new value.

For the white etching this time, the two last steps are now : new value = fix_rgb(new value) and finally, new value = 255 - new value where fix_rgb is a function that checks if new value is correctly between 0 and 255 like all RGB pixel components values. That's all!