Gradient based methods

An edge point can be regarded as a point in an image where a discontinuity (in gradient) occurs across some line. A discontinuity may be classified as one of three types (see Fig 21):

 

Fig. 21 The C Compilation Model

A Gradient Discontinuity

-- where the gradient of the pixel values changes across a line. This type of discontinuity can be classed as

• roof edges
  
• ramp edges
  
• convex edges
  
• concave edges

by noting the sign of the component of the gradient perpendicular to the edge on either side of the edge.

Ramp edges have the same signs in the gradient components on either side of the discontinuity, while roof edges have opposite signs in the gradient components.

A Jump or Step Discontinuity

-- where pixel values themselves change suddenly across some line.

A Bar Discontinuity

-- where pixel values rapidly increase then decrease again (or vice versa) across some line.

For example, if the pixel values are depth values,

• jump discontinuities occur where one object occludes another (or another part of itself).
  
• Gradient discontinuities usually occur between adjacent faces of the same object.

If the pixel values are intensities,

• a bar discontinuity would represent cases like a thin black line on a white piece of paper.
  
• Step edges may separate different objects, or may occur where a shadow falls across an object.

The gradient is a vector, whose components measure how rapidly pixel values are changing with distance in the x and y directions.

Thus, the components of the gradient may be found using the following approximation:

where and measure distance along the x and y directions respectively.

In (discrete) images we can consider and in terms of numbers of pixels between two points. Thus, when (pixel spacing) and we are at the point whose pixel coordinates are (i,j) we have
 

In order to detect the presence of a gradient discontinuity we must calculate the change in gradient at (i,j). We can do this by finding the following gradient magnitude measure,

and the gradient direction, , given by

Implementation:

The difference operators in Eqn. 44 correspond to convolving the image with the two masks in Fig. 22.

This is easy to compute:

• The top left-hand corner of the appropriate mask is superimposed over each pixel of the image in turn,
  
• A value is calculated for or by using the mask coefficients in a weighted sum of the value of pixel (i,j) and its neighbours.
  
• These masks are referred to as convolution masks or sometimes convolution kernels.

 

Fig. 22 Edge operator convolution masks

Instead of finding approximate gradient components along the x and y directions we can also approximate gradient components along directions at and to the axes respectively. In this case the following equations are used:
 

This form of operator is known as the Roberts edge operator and was one of the first operators used to detect edges in images. The corresponding convolution masks are given by:  

Fig. 23 The C Compilation Model

Many edge detectors have been designed using convolution mask techniques, often using mask sizes or even larger.

An advantage of using a larger mask size is that errors due to the effects of noise are reduced by local averaging within the neighbourhood of the mask.

An advantage of using a mask of odd size is that the operators are centred and can therefore provide an estimate that is biased towards a centre pixel (i,j).

One important edge operator of this type is the Sobel edge operator. The Sobel edge operator masks are given in Fig 24.  

Fig. 24 Sobel edge operator convolution masks