Edge detection

From Wikipedia, the free encyclopedia

The goal of edge detection is to mark the points in a digital image at which the luminous intensity changes sharply. Sharp changes in image properties usually reflect important events and changes in properties of the world. These include (i) discontinuities in depth, (ii) discontinuities in surface orientation, (iii) changes in material properties and (iv) variations in scene illumination. Edge detection is a research field within image processing and computer vision, in particular within the area of feature extraction.

Edge detection of an image reduces significantly the amount of data and filters out information that may be regarded as less relevant, preserving the important structural properties of an image. There are many methods for edge detection, but most of them can be grouped into two categories, search-based and zero-crossing based. The search-based methods detect edges by looking for maxima and minima in the first derivative of the image, usually local directional maxima of the gradient magnitude. The zero-crossing based methods search for zero crossings in the second derivative of the image in order to find edges, usually the zero-crossings of the Laplacian or the zero-crossings of a non-linear differential expression.

1 Edge properties
2 Simple edge model
3 Detecting an edge
4 Edge detection operators
5 References
6 See also

[edit] Edge properties

Edges may be viewpoint dependent - these are edges that may change as the viewpoint changes, and typically reflect the geometry of the scene, objects occluding one another and so on, or may be viewpoint independent - these generally reflect properties of the viewed objects such as surface markings and surface shape. In two dimensions, and higher, the concept of perspective projection has to be considered.

A typical edge might be (for instance) the border between a block of red color and a block of yellow; in contrast a line can be a small number of pixels of a different color on an otherwise unchanging background. There will be one edge on each side of the line. Edges play quite an important role in many applications of image processing. During recent years, however, substantial (and successful) research has also been made on computer vision methods that do not explicitly rely on edge detection as a pre-processing step.

[edit] Simple edge model

Edges in natural images are usually not ideal step edges. Instead they are normally affected by one or several of the following effects:

focal blur caused by a finite depth-of-field.
penumbral blur caused by shadows created by light sources of non-zero radius.
shading at a smooth object edge.
local specularities or interreflections in the vicinity of object edges.

Although the following model cannot be regarded as perfect, the error function $\operatorname{erf}$ is commonly used for modelling the effects of edge blur in practical applications. Thus, a one-dimensional image $f$ which has exactly one edge placed at $0$ may be modelled as follows:

$f(x) = \frac{I_r - I_l}{2} \left( \operatorname{erf}\left(\frac{x}{\sqrt{2}\sigma}\right) + 1\right) + I_l$

Then, left of the edge the intensity is $I_l = \lim_{x \rightarrow -\infty} f(x)$ , and right of the edge it is $I_r = \lim_{x \rightarrow \infty} f(x)$ ; $σ$ is called the blur scale of the edge. Please note that $f$ can be written as a convolution $f = g σ * u$ where $g σ$ is the gaussian kernel with standard deviation $σ$ , and $u$ is a step function defined as follows:

$u(x) := \left\{ \begin{matrix} I_l, & \mathrm{if} \; x \leq 0\\ I_r, & \mathrm{otherwise} \end{matrix} \right.$

[edit] Detecting an edge

Taking an edge to be a change in intensity taking place over a number of pixels, edge detection algorithms generally compute a derivative of this intensity change. To simplify matters, we can consider the detection of an edge in one dimension. In this instance, our data can be a single line of pixel intensities. For instance, we can intuitively say that there should be an edge between the 4th and 5th pixels in the following 1-dimensional data:

152

148

149

To firmly state a specific threshold on how large the intensity change between two neighbouring pixels must be for us to say that there should be an edge between these pixels is, however, not always an easy problem. Indeed, this is one of the reasons why edge detection may be a non-trivial problem unless the objects in the scene are particularly simple and the illumination conditions can be well controlled.

[edit] Computing the 1st derivative

Many edge-detection operators are based upon the 1st derivative of the intensity - this gives us the intensity gradient of the original data. Using this information we can search an image for peaks in the intensity gradient.

If I(x) represents the intensity of pixel x, and I′(x) represents the first derivative (intensity gradient) at pixel x, we therefore find that:

$I'(x)=-1/2\cdot I(x-1) + 0 \cdot I(x) + 1/2 \cdot I(x+1).\,$

For higher performance image processing, the 1st derivative can therefore be calculated (in 1D) by convolving the original data with a mask:

−1/2

+1/2

[edit] Computing the 2nd derivative

Some other edge-detection operators are based upon the 2nd derivative of the intensity. This is essentially the rate of change in intensity gradient. In the ideal continuous case, detection of zero-crossings in the second derivative captures local maxima in the gradient. Peak detection in the second derivative, on the other hand, is a method for line detection, provided that the image operators are expressed at a proper scale. As noted above, a line is a double edge, hence we will see an intensity gradient on one side of the line, followed immediately by the opposite gradient on the opposite site. Therefore we can expect to see a very high change in intensity gradient where a line is present in the image. To find lines, we can alternatively search for zero-crossings in the second derivative of the image gradient.

If I(x) represents the intensity at point x, and I"(x) is the second derivative at point x:

$I''(x) = 1\cdot I(x-1) - 2 \cdot I(x) + 1 \cdot I(x+1).\,$

Again most algorithms use a convolution mask to quickly process the image data:

−2

[edit] Thresholding

Once we have calculated our derivative, the next stage is to apply a threshold, to determine where the result suggest an edge to be present. The lower the threshold, the more lines will be detected, and the results become increasingly susceptible to noise, and also to picking out irrelevant features from the image. Conversely a high threshold may miss subtle lines, or segmented lines.

A commonly used compromise is thresholding with hysteresis. This method uses multiple thresholds to find edges. We begin by using the upper threshold to find the start of a line. Once we have a start point, we trace the edge's path through the image pixel by pixel, marking an edge whenever we are above the lower threshold. We stop marking our edge only when the value falls below our lower threshold. This approach makes the assumption that edges are likely to be in continuous lines, and allows us to follow a faint section of an edge we have previously seen, without meaning that every noisy pixel in the image is marked down as an edge.

[edit] Edge detection operators

1st order: Roberts Cross, Prewitt, Sobel, Canny
2nd Order: Marr-Hildreth, zero-crossings of the second-order derivative in the gradient direction.

Currently, the Canny operator (or variations of this operator) is most commonly used edge detection method. A large number of edge detection operators have been published but so far none has shown significant advantages over the Canny-type operators in general situations. In his original work, Canny studied the problem of designing an optimal pre-smoothing filter for edge detection, and then showed that this filter could be well approximated by a first-order Gaussian derivative kernel. Canny also introduced the notion of non-maximum suppression, which means that edges are defined as points where the gradient magnitude assumes a maximum in the gradient direction.

On a discrete grid, the non-maximum suppression stage can be implemented by estimating the gradient direction using first-order derivatives, then rounding off the gradient direction to multiples of 45 degrees, and finally comparing the values of the gradient magnitude in the estimated gradient direction. A more refined approach to obtain edges with sub-pixel accuracy is by using the following differential approach of detecting zero-crossings of the second-order directional derivative in the gradient direction (Lindeberg 1998)

$L_x^2 \, L_{xx} + 2 \, L_x \, L_y \, L_{xy} + L_y^2 \, L_{yy} = 0,$

that satisfy a sign-condition on the third-order directional derivative in the same direction (for more details, please see the relations between edge detection and ridge detection in the article on ridge detection)

$L_x^3 \, L_{xxx} + 3 \, L_x^2 \, L_y \, L_{xxy} + 3 \, L_x \, L_y^2 \, L_{xyy} + L_y^3 \, L_{yyy} < 0$

where $L x$ , $L y$ ... $L y y y$ denote partial derivatives computed from a scale-space representation $L$ obtained by smoothing the original image with a Gaussian kernel. In this way, the edges will be automatically obtained as continuous curves with subpixel accuracy. Hysteresis thresholding can also be applied to these differential and subpixel edge segments.