Anagram Engineering

Webdesign und Softwarelösungen aus Vorarlberg. Ihr Partner für innovative Lösungen rund ums Internet. Full Service Agentur.

Edge detection



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 $ x$ and $ y$ direction, denoted as $ G_x(x,y)$ and $ G_y(x,y)$, 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 $ tau$. 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


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

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


A faster computation of the magnitude is given by


where $ G_x$ and $ G_y$ are the first derivations of the image in x and y direction. $ G_x$ is proportional to variations in the horizontal direction and $ G_y$ 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


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 $ theta$ and the new direction will be $ theta'$ , then $ theta'$ 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 $ arctan$ 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. $ tau _H$ which is the higher threshold and $ tau _L$ which is the lower threshold. If the magnitude of a point is higher or equal to $ tau _H$, it is immediately marked as an edge. Every pixel that is connected to such a pixel and has magnitude higher than $ tau _L$ is also marked as an edge. If you think of following an edge, the search starts at a pixel with a magnitude higher than $ tau _H$ and does not stop until a pixel with a magnitude lower than $ tau _L$ 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, $ cdots$).

The decision which detector to use depends on the problem which is to solve. Every edge detector has its special advantages and disadvantages. In order to find straight lines, the Canny edge detector was appropriate.

Next: Line Extraction
Up: Methods