Next: Line Extraction
Up: Methods
Previous: Calibration

Edge detection

The next step is to transform the images into a representation in which only edge segments remain. Edges are declared as significant changes in the signal level, thus can be searched with the help of convolution masks which approximate the first or second derivation of the image. If the mask measures the first derivation of the image in and direction, denoted as and , an edge point is found if the magnitude
$m = sqrt{G_x(x,y)^2 + G_y(x,y)^2}$ of the convolution at the measured point is above a threshold . Also the direction
$varrho = arctan(frac{G_y(x,y)}{G_x(x,y)})$ of the edge can be computed. A zero-crossing represents an edge in a mask which calculates the second derivation. The direction of the edge is stored in the values on the right and left side of the zero-crossing. Some popular convolution masks are:

Sobel

The Sobel operator approximates the first derivation of the image. The operator mask of the Sobel operator is defined as

$displaystyle S_x = begin{pmatrix}-1 & 0 & 1 cr -2 & 0 & 2 cr -1 & 0 & 1 en... ...uad S_y = begin{pmatrix}1 & 2 & 1 cr 0 & 0 & 0 cr -1 & -2 & -1 end{pmatrix}$

(3.6)

Prewitt

The Prewitt is similar to the Sobel operator, its operation mask is defined as

$displaystyle P_x = begin{pmatrix}-1 & 0 & 1 cr -1 & 0 & 1cr -1 & 0 & 1 end... ...uad P_y = begin{pmatrix}1 & 1 & 1 cr 0 & 0 & 0 cr -1 & -1 & -1 end{pmatrix}$

(3.7)

Zero Crossing

The core of the zero crossing operator is the LoG Filter (Laplacian of Gaussian). It is defined as

$displaystyle Log(x,y) = frac{-1}{pisigma^4}[1-frac{x^2+y^2}{2sigma^2}]e^-frac{x^2+y^2}{2sigma^2}$

(3.8)

and is shown in Figure 3.6

**Figure 3.6:**
LoG Filter

The LoG operator calculates the second derivation of an image, as a result in an area with no change in intensity values the response of the LoG operator will be zero. However, if there is a change in intensity the response will be positive on the darker side, zero in between (on the edge itself) and negative on the lighter side. Thus the direction of the edge is encoded in the resulting grayscale map after convolving with the LoG operator. The LoG operator is isotropic, so the quality does not depend on the attitude of the edge in relation to the image.

Canny

The Canny edge detector can be roughly divided into six steps:

Step 1

During the first stage of the Canny algorithm, noise has to be filtered out. This is done by convolving the image with a Gaussian filter mask. The size of the mask is proportional to the sensitivity and indirectly proportional to the localization
achieved by the detector.

Step 2

The strength of the edges is found by convolving the images with the Sobel operator (defined in Equation 3.6.), which performs a 2-D spatial gradient measurement on the image. The magnitude of the gradient can be found using the equation

$displaystyle M = sqrt{G_x^2 + G_y^2 }$

(3.9)

A faster computation of the magnitude is given by

(3.10)

where and are the first derivations of the image in x and y direction. is proportional to variations in the horizontal direction and to variations in the vertical direction. If both derivates are combined, as it is in Equation 3.10 all directions are taken into consideration.

Step3

The direction of the edge can be computed as

$displaystyle theta = begin{cases}arctan(frac{G_y}{G_x}) & text{if $G_x n... ... & $G_x =0 $} 90^{circ} & text{if $G_y ne 0$ & $G_x = 0$} end{cases}$

(3.11)

Step 4

The direction has to be classified into five sectors. This process is similar to dividing a semicircle into five regions. Lets say the result of Equation 3.11 is

and the new direction will be

, then

can be computed as:

$displaystyle theta' = begin{cases}0^{circ} & text{if $thetageq 0$ & $... ...$} 135^{circ} & text{if $theta > 112.5$ & $theta < 157.5$} end{cases}$

(3.12)

According to [HB93], it could be better to calculate the discrete tangent directly, without the indirection of first computing the and then classifying into five regions.

Step 5

After the edge directions are known, nonmaximum suppression is applied which traces along the edges and deletes every edge point (set it to 0) which is not considered to be an edge.

Step 6

Finally, hysteresis is used to eliminate the breaking up of an edge due to variations of the operator. Therefore two thresholds are defined.

which is the higher threshold and

which is the lower threshold. If the magnitude of a point is higher or equal to

, it is immediately marked as an edge. Every pixel that is connected to such a pixel and has magnitude higher than

is also marked as an edge. If you think of following an edge, the search starts at a pixel with a magnitude higher than

and does not stop until a pixel with a magnitude lower than

is reached.

The output of the Canny edge operator is an edge image with a low error rate, good localization and only one response to a single edge. Figure 3.7 shows the results of the Canny edge detector with two different thresholds. With a low threshold many artifacts remain whereas with a high threshold important information could be lost. The choice which thresholds to use depends on the demands of the continuative process as well as the environment conditions (natural light, artificial light, contrast, ).