Legacy Documentation

Digital Image Processing (2000)

This is documentation for an obsolete product.
Current products and services
User's Guide / Image Segmentation /
Previous section-----Next section

7.3 Edge Detection

Edge detection is a problem of fundamental importance in image analysis. In typical images, edges characterize object boundaries and are therefore useful for segmentation, registration, and identification of objects in a scene. In this section, the construction, characteristics, and performance of a number of gradient and zero-crossing edge operators will be presented.
An edge is a jump in intensity. The cross-section of an edge has the shape of a ramp. An ideal edge is a discontinuity (i.e., a ramp with an infinite slope). The first derivative assumes a local maximum at an edge. For a continuous image f(x,y), where x and y are the row and column coordinates, respectively, we typically consider the two directional derivatives x f(x,y) and y f(x,y). Of particular interest in edge detection are two functions that can be expressed in terms of these directional derivatives, the gradient magnitude and orientation. The gradient magnitude is defined as
and the gradient orientation is given by
Local maxima of the gradient magnitude identify edges in f(x,y). When the first derivative achieves a maximum, the second derivative is zero. For this reason, an alternative edge detection strategy is to locate zeros of the second derivatives of f(x,y). The differential operator used in these so-called zero-crossing edge detectors, is the Laplacian
This loads the package.
In[1]:=
The following demonstration illustrates the principles of edge detection. We model a 1D edge with a simple smooth function, for example f(t)=Tanh( t). As the parameter increases, the slope of the edge gets steeper. Here we use = 3.
In[2]:=
Out[2]=Out[2]=
This evaluates and plots the first and second derivatives of our edge function.
In[3]:=
Out[3]=Out[3]=
As expected, the result shows that maxima of first derivative (green) and zero-crossings of the second derivative (blue) locate the center of our model edge. It can also be shown that the zero-crossings are independent of the steepness of the transition, while the gradient magnitude is directly related to the edge slope.
In practice, finite difference approximations of first-order directional derivatives are used. These are represented by a pair of masks, say hx and hy. Formally these are linear phase FIR filters. A convolution of the image with hx and hy gives two directional derivative images gx and gy, respectively. The gradient image is traditionally calculated as , or alternatively using = |gx| + |gy| [Gon92]. A pixel location is declared an edge location, if the value of (at point x, y) exceeds some threshold. The locations of all edge points constitutes an edge map. The selection of a threshold value is an important design decision that depends on a number of factors, such as image brightness, contrast, level of noise, and even edge direction. Typically, the threshold is selected following an analysis of the gradient image histogram. It is sometimes useful to calculate edge direction information. This is given by .
EdgeMagnitude[img, h]returns an edge image resulting from the application of edge filter h to img
EdgeMagnitude[img, {h1, h2, ...}]returns the magnitude of a gradient edge image resulting from the application of two or more directional edge filters h1, h2, ... to img
EdgeOrientation[img, {h1, h2}] returns the orientation of a gradient edge image resulting from the application of two directional edge filters to img

Edge operators.

The method of computing the gradient magnitude is user selectable with option GradientType and postprocessing of the gradient result is available with the option NonMaxSuppress.

Option of EdgeMagnitude.

A number of commonly used gradient operators are available.

Gradient edge operators.

Here are two common gradient edge operators.
In[4]:=
Out[4]=Out[4]=
In[5]:=
Out[5]=Out[5]=
Note that each of the Sobel edge filters is a combination of a digital differentiator in one of the spatial directions and a smoothing filter in the other.
Here we read one of the example images and consider a subregion of the image.
In[6]:=
We compute and display the gradient magnitude and edge direction using the Sobel filter.
In[7]:=
Out[7]=Out[7]=
The Canny [Can86] and the Shen and Castan [She92] edge detectors are possibly the most widely known and used methods for detecting edges. These are classic gradient operators, conceptually easy to understand, effective, and yet simple to implement. Canny proposed the use of the derivative of the Gaussian function as an optimal edge filter, while Shen and Castan using a different optimality criterium proved that the best edge filter should be based on a derivative of the symmetric exponential function. Here are the 1D versions of the two filters.
In[8]:=
Out[8]=Out[8]=
Here are the two gradient images resulting from using the Canny and Shen and Castan filters.
In[9]:=
Out[9]=Out[9]=
As originally proposed by Canny, the gradient calculation may be followed by a thinning process that retains only the locally maximum gradient responses. This is enabled with the option NonMaxSuppress→True.
In[10]:=
Out[10]=Out[10]=
To obtain a binary edge map, the gradient image must be segmented using a global or local (i.e., adaptive) threshold operator. This shows the result of hysteresis thresholding of the thinned gradient images.
In[11]:=
Out[11]=Out[11]=
The choice of a threshold value determines the resulting segmentation and, therefore, the perceived quality of the edge detector. It is useful to consider the cumulative histogram of the gradient image in selecting an appropriate threshold value. Here we calculate the histogram and cumulative histogram of the gradient magnitude image. In a typical approach, the top 10% to 20% of the largest gradient values are selected as edge points. This is easily done based on an investigation of the cumulative histogram.
In[12]:=
In[13]:=
Out[13]=Out[13]=
The threshold can now be estimated visually, or better still calculated from the cumulative histogram by setting a threshold at the 80% level.
In[14]:=
Out[14]=Out[14]=
We display the edge maps for three selected threshold values.
In[15]:=
Out[15]=Out[15]=
Based on visual inspection of the edge maps, it seems reasonable to accept the threshold value at the 80% level.
A zero-crossing edge operator was originally proposed by Marr and Hildreth [Mar80]. They suggested that in order to effectively detect intensity changes (edges), the operator needs to have two characteristics. First, it must be a differential operator, taking either a first or second spatial derivative of the image. Second, it should be capable of being tuned to act at any desired scale, so that large filters can be used to detect blurry shadow edges, and small ones can be used to detect sharply focused fine detail in the image. This led to the so-called Laplacian-of-Gaussian edge operator. This is a compound operator, which combines a smoothing operation, using a Gaussian-shaped linear phase FIR filter, with a differentation operation, using a discrete Laplacian. The edges are identified by the location of zero-crossings (recall that the second derivative changes sign in the vicinity of maxima of the first derivative).

Edge detection filters.

This computes the Laplacian of the example image.
In[16]:=
This shows the original and filtered images.
In[17]:=
Out[17]=Out[17]=
The zero crossings are clearly visible as they occur at the border between bright and dark areas of the Laplacian image. The midtones cover areas of small responses to the Laplacian operator, which corresponds to uniform (flat) brightness areas of the original image.
In[18]:=
Out[18]=Out[18]=
In order to mitigate the increase in pixel noise due to differentiation, the image is filtered with a lowpass filter. This is accomplished by a Gaussian-shaped, linear phase FIR filter. Since convolution is associative and commutative, the two-step sequence can be reduced to one by constructing a compound operator. LaplacianOfGaussianFilter is a compound operator, whose values are samples of the Laplacian of the bivariate Gaussian function with variance 2.
In[19]:=
Out[19]=Out[19]=
The value of the standard deviation is determined from the desired dimensions of the filter according to for each dimension i.
In[20]:=
Out[20]=Out[20]=
Here we filter the example image using LaplacianOfGaussianFilter.
In[21]:=
Here are the results of convolving the example image with a Laplacian-of-Gaussian filter followed by zero-crossings detection. The latter is implemented with the function ZeroCrossing.
In[22]:=
Out[22]=Out[22]=