[attachment=11921]
1 Introduction
The purpose of edge detection in general is to significantly reduce the amount of data in an
image, while preserving the structural properties to be used for further image processing. Several
algorithms exists, and this worksheet focuses on a particular one developed by John F. Canny
(JFC) in 1986
Even though it is quite old, it has become one of the standard edge detection
methods and it is still used in research
The aim of JFC was to develop an algorithm that is optimal with regards to the following
criteria:
1. Detection: The probability of detecting real edge points should be maximized while the
probability of falsely detecting non-edge points should be minimized. This corresponds to
maximizing the signal-to-noise ratio.
2. Localization: The detected edges should be as close as possible to the real edges.
3. Numb er of responses: One real edge should not result in more than one detected edge
(one can argue that this is implicitly included in the first requirement).
With JFC’s mathematical formulation of these criteria, Canny’s Edge Detector is optimal for
a certain class of edges (known as step edges). A C++ implementation of the algorithm has
been written, and this will be further described in Section
3
. The images used throughout this
worksheet are generated using this implementation.
1.1 Test Image
The image in Figur
is used throughout this worksheet to demonstrate how Canny edge de-
tection works. It depicts a partially assembled pump from Grundfos, and the edge detection is
a step in the process of estimating the pose (position and orientation) of the pump.
The image has been preprocessed as described in the worksheet “Ideas for Solution to the Pose
Estimation Problem”. The preprocessing includes:
• Determining ROI (Region of Interest) that includes only white background besides the
pump, and cropping the image to this region.
• Conversion to gray-scale to limit the computational requirements.
• Histogram-stretching, so that the image uses the entire gray-scale. This step may not be
necessary, but it is included to counter-compensate for automatic light adjustment in the
used web camera.
2 The Canny Edge Detection Algorithm
The algorithm runs in 5 separate steps:
1. Smoothing: Blurring of the image to remove noise.
2. Finding gradients: The edges should be marked where the gradients of the image has
large magnitudes.
3. Non-maximum suppression: Only local maxima should be marked as edges.
4. Double thresholding: Potential edges are determined by thresholding.
5. Edge tracking by hysteresis: Final edges are determined by suppressing all edges that
are not connected to a very certain (strong) edge.
Each step is described in the following subsections.
2.1 Smoothing
It is inevitable that all images taken from a camera will contain some amount of noise. To
prevent that noise is mistaken for edges, noise must be reduced. Therefore the image is first
smoothed by applying a Gaussian filter. The kernel of a Gaussian filter with a standard deviation
of s = 1.4 is shown in Equation (
1
). The e ect of smoothing the test image with this filter is
shown in Figure
2
.
2 4 5 4 2
4 9 12 9 4
B = 1
5 12 15 12 5
(1)
159 •
4 9 12 9 4
2 4 5 4 2
2
2.2 Finding gradients
The Canny algorithm basically finds edges where the grayscale intensity of the image changes
the most. These areas are found by determining gradients of the image. Gradients at each pixel
in the smoothed image are determined by applying what is known as the Sobel-operator. First
step is to approximate the gradient in the x- and y-direction respectively by applying the kernels
shown in Equation (
2
).
-1 0 1
K
=
-2 0 2
GX
-1 0 1
1 2 1
K
=
0 0 0
(2)
GY
-1 -2 -1
The gradient magnitudes (also known as the edge strengths) can then be determined as an
Euclidean distance measure by applying the law of Pythagoras as shown in Equation (
3
). It
is sometimes simplified by applying Manhattan distance measure as shown in Equation (
4
) to
reduce the computational complexity. The Euclidean distance measure has been applied to the
test image. The computed edge strengths are compared to the smoothed image in Figure
3
.
|G| = G
+ G
(3)
2
2
x
y
|G| = |G
| + |G
| (4)
x
y
where:
G
and G
are the gradients in the x- and y-directions respectively.
x
y
It is obvious from Figure
3
, that an image of the gradient magnitudes often indicate the edges
quite clearly. However, the edges are typically broad and thus do not indicate exactly where
the edges are. To make it possible to determine this (see Section
2.3
), the direction of the edges
must be determined and stored as shown in Equation (
5
).
|
y
= arctan |G
|G
| (5)
x
3
(a) Smoothed (b) Gradient magnitudes
Figure 3: The gradient magnitudes in the smoothed image shown in
3b
as well as their directions are
determined by applying e.g. the Sobel-operator.
2.3 Non-maximum suppression
The purpose of this step is to convert the “blurred” edges in the image of the gradient magnitudes
to “sharp” edges. Basically this is done by preserving all local maxima in the gradient image,
and deleting everything else. The algorithm is for each pixel in the gradient image:
1. Round the gradient direction to nearest 45 , corresponding to the use of an 8-connected
neighbourhood.
2. Compare the edge strength of the current pixel with the edge strength of the pixel in the
positive and negative gradient direction. I.e. if the gradient direction is north (theta =
90 ), compare with the pixels to the north and south.
3. If the edge strength of the current pixel is largest; preserve the value of the edge strength.
If not, suppress (i.e. remove) the value.
A simple example of non-maximum suppression is shown in Figure
4
. Almost all pixels have
gradient directions pointing north. They are therefore compared with the pixels above and
below. The pixels that turn out to be maximal in this comparison are marked with white
borders. All other pixels will be suppressed. Figure
3 1
Figure 4: Illustration of non-maximum suppression. The edge strengths are indicated both as colors and
numbers, while the gradient directions are shown as arrows. The resulting edge pixels are marked with
white borders.
4