Edge Detection

download notebookDownload this example as a Mathematica notebook.


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 [Graphics:Images/index_gr_1.gif], where x and y are the row and column coordinates respectively, we typically consider the two directional derivatives [Graphics:Images/index_gr_2.gif] and [Graphics:Images/index_gr_3.gif]. Of particular interest in edge detection are two functions that can be expressed in terms of these directional derivatives: the gradient magnitude and the gradient orientation. The gradient magnitude is defined as

[Graphics:Images/index_gr_4.gif],

and the gradient orientation is given by

[Graphics:Images/index_gr_5.gif].

Local maxima of the gradient magnitude identify edges in [Graphics:Images/index_gr_6.gif]. 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 [Graphics:Images/index_gr_7.gif]. The differential operator used in these so-called zero-crossing edge detectors is the Laplacian

[Graphics:Images/index_gr_8.gif].

This loads the package.

[Graphics:Images/index_gr_9.gif]

The following demonstration illustrates the principles of edge detection. We model a one-dimensional edge with a simple smooth function, for example, [Graphics:Images/index_gr_10.gif]. As the parameter alpha increases, the slope of the edge gets steeper. Here we use [Graphics:Images/index_gr_11.gif].

[Graphics:Images/index_gr_12.gif]

[Graphics:Images/index_gr_13.gif]

This evaluates and plots the first and second derivatives of our "edge" function.

[Graphics:Images/index_gr_14.gif]

[Graphics:Images/index_gr_15.gif]

As expected, the result shows that maxima of the 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 [Graphics:Images/index_gr_16.gif] and [Graphics:Images/index_gr_17.gif]. Formally these are linear-phase FIR filters. A convolution of the image with [Graphics:Images/index_gr_20.gif] and [Graphics:Images/index_gr_21.gif] gives two directional derivative images [Graphics:Images/index_gr_22.gif] and [Graphics:Images/index_gr_23.gif] respectively. The gradient image is traditionally calculated as [Graphics:Images/index_gr_24.gif], or alternatively using [Graphics:Images/index_gr_25.gif] [1]. A pixel location is declared an edge location if the value of nabla (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 [Graphics:Images/index_gr_26.gif] .

Edge Operators

[Graphics:Images/index_gr_27.gif] [Graphics:Images/index_gr_28.gif]
[Graphics:Images/index_gr_29.gif] [Graphics:Images/index_gr_30.gif]
[Graphics:Images/index_gr_31.gif] [Graphics:Images/index_gr_32.gif]

Option of EdgeMagnitude

The method of computing the gradient magnitude is user selectable with option GradientType.

[Graphics:Images/edge_gr_34.gif] [Graphics:Images/edge_gr_35.gif]  
[Graphics:Images/edge_gr_37.gif] [Graphics:Images/edge_gr_38.gif] [Graphics:Images/edge_gr_39.gif]


Gradient Edge Operators

A number of commonly used gradient operators are available.

[Graphics:Images/index_gr_39.gif] [Graphics:Images/index_gr_40.gif]
[Graphics:Images/index_gr_41.gif] [Graphics:Images/index_gr_42.gif]
[Graphics:Images/index_gr_43.gif] [Graphics:Images/index_gr_44.gif]
[Graphics:Images/index_gr_45.gif] [Graphics:Images/index_gr_46.gif]

Here are two common gradient edge operators.

[Graphics:Images/index_gr_47.gif]
[Graphics:Images/index_gr_48.gif]
[Graphics:Images/index_gr_49.gif]
[Graphics:Images/index_gr_50.gif]

Note that each of the Sobel edge masks is a combination of a digital differentiator in one of the spatial directions and a smoothing operator in the other.

Here we read one of the example images and consider a subregion of the image.

[Graphics:Images/index_gr_51.gif]

We compute the gradient magnitude and edge direction using the Sobel mask.

[Graphics:Images/index_gr_52.gif]
[Graphics:Images/index_gr_53.gif]

[Graphics:Images/index_gr_54.gif]

To recover the edges, the gradient image must be segmented using a global or local (i.e., adaptive) threshold operator. 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 percent of the largest gradient values are selected as edge points. This is easily done based on an investigation of the cumulative histogram.

[Graphics:Images/index_gr_55.gif]
[Graphics:Images/index_gr_56.gif]

[Graphics:Images/index_gr_57.gif]

The threshold can now be estimated visually or even calculated from the cumulative histogram by setting a threshold at the 80 percent level.

[Graphics:Images/index_gr_58.gif]
[Graphics:Images/index_gr_59.gif]

We display the edge maps for three selected threshold values.

[Graphics:Images/index_gr_60.gif]

[Graphics:Images/index_gr_61.gif]

Based on visual inspection of the edge maps, it seems reasonable to accept the threshold value of t.

A zero-crossing edge operator was originally proposed by Marr and Hildreth [2]. 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 that 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).


Smoothing and Differentiating Filters

[Graphics:Images/edge_gr_64.gif] [Graphics:Images/edge_gr_65.gif]
[Graphics:Images/edge_gr_66.gif] [Graphics:Images/edge_gr_67.gif]
[Graphics:Images/edge_gr_68.gif] [Graphics:Images/edge_gr_69.gif]
[Graphics:Images/edge_gr_70.gif] [Graphics:Images/edge_gr_71.gif]

LaplacianFilter returns a number of common FIR filter approximations to the Laplacian operator. The default argument value ([Graphics:Images/index_gr_70.gif]) returns the minimum-variance discrete Laplacian subject to the conditions that pixel noise is uncorrelated and has uniform variance [3]. The Laplacian is the lowest-order isotropic (i.e., orientation-independent) operator.

[Graphics:Images/index_gr_71.gif]
[Graphics:Images/index_gr_72.gif]

This computes the Laplacian of the example image.

[Graphics:Images/index_gr_73.gif]

This shows the original and filtered images.

[Graphics:Images/index_gr_74.gif]

[Graphics:Images/index_gr_75.gif]

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.

[Graphics:Images/index_gr_76.gif]
[Graphics:Images/index_gr_77.gif]

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 step by constructing a compound operator. LoGFilter is a compound operator whose values are samples of the Laplacian of the bivariate Gaussian function with variance [Graphics:Images/index_gr_78.gif].

[Graphics:Images/index_gr_79.gif]
[Graphics:Images/index_gr_80.gif]

Here we set [Graphics:Images/index_gr_81.gif] and plot both the resulting function as a surface and the functions profile for [Graphics:Images/index_gr_82.gif].

[Graphics:Images/index_gr_83.gif]

[Graphics:Images/index_gr_84.gif]

Here we filter the example image using LoGFilter.

[Graphics:Images/index_gr_85.gif]

Shown below are the results of convolving the example image with a Laplacian-of-Gaussian filter followed by zero-crossing detection. The latter is implemented with the function ZeroCrossing.

[Graphics:Images/index_gr_86.gif]

[Graphics:Images/index_gr_87.gif]


Bibliography

[1] Gonzalez, R. C., and Woods, R. E. Digital Image Processing (Reading, MA: Addison-Wesley, 1992).

[2] Marr, D., and Hildreth, E. "Theory of Edge Detection," Proceedings of the Royal Society London 207 (1980) 187-217.

[3] Haralick, R. M., and Shapiro, L. G. Computer and Robot Vision, vol.1 (Reading, MA: Addison-Wesley, 1992).