Edge Detection Methods in Digital Image Processing

Abstract

The current work focuses on the study of different edge detection techniques and analysis of there relative performances. The recent advance of image processing has motivated on the various edge detection techniques. There are many ways to perform the edge detection. However the majority of different methods may be categorized into two groups, i.e. Gradient based and Laplacian based. Also we introduce stochastic gradient method which gives the better result in the presence of noise. The effectiveness of the stochastic process is demonstrated experimentally.

Key words: Edges, Salt and paper noise, stochastic process

Introduction

Edge detection [5] is a process that detects the presence and location of edges constituted by sharp changes in color, intensity (or brightness) of an image. Since, it can be proven that the discontinuities in image brightness are likely corresponding to discontinuities in depth, discontinuities in surface orientation, changes in material properties and variations in scene illumination. In the ideal case, the result of applying an edge detector to an image may lead to a set of connected curves that indicate the boundaries of objects, the boundaries of surface markings as well curves that correspond to discontinuities in surface orientation [1, 2]. However, it is not always possible to obtain such ideal edges from real life images of moderate complexity. Edges extracted from non-trivial images are often hampered by fragmentation (i.e. edge curves are not connected), missing edge segments, as well as false edges (i.e. not corresponding to interesting phenomena in the image), which all lead to complicating the subsequent task of image interpreting [3].

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

A grey scale image can be represented by two-dimensional values of pixel in which each pixel represents the intensity. In image processing, the digitization process can be done by sampling and quantization of continuous data. The sampling process samples the intensity of the continuous-tone image, such as a monochrome, color or multi-spectrum image, at specific locations on a discrete grid. The grid defines the sampling resolution. The quantization process converts the continuous or analog values of intensity brightness into discrete data, which corresponds to the digital brightness value of each sample, ranging from black, through the gray, to white. A digitized sample is referred to as a picture element, or pixel. The digital image contains a fixed number of rows and columns of pixels. Pixels are like little tiles holding quantized values that represents the brightness at the points of the image. Pixels are parameterized by position, intensity and time. Typically, the pixels are stored in computer memory as a raster image or raster map, a two-dimensional array of small integers. Image is stored in numerical form which can be manipulated by a computer. A numerical image is divided into a matrix of pixels (picture elements).

Digital image processing allows one to enhance image features of interest while attenuating detail irrelevant to a given application, and then extract useful information about the scene from the enhanced image. Images are produced by a variety of physical devices, including still and video cameras, x-ray devices, electron microscopes, radar, and ultrasound, and used for a variety of purposes, including entertainment, medical, business (e.g. Documents), industrial, military, civil (e.g. traffic), security, and scientific. The goal in each case is for an observer, human or machine, to extract useful information about the scene being imaged.

Organization of the paper

The paper is organized as follows:

In Section – 2 we briefly discuss the different types of edge detection methods and also discuss the criteria for edge detection. In Section – 3 we also consider Stochastic Gradient operator by which we can give the better result in noisy environment. Some experimental results are shown in Section – 4 along with few remarks. In Section – 5 some conclusions are drawn.

2. Motivation behind Edge Detection:

The main objective of edge detecting process is to extract the accurate edge line with good orientation without changing the properties of the image. The brightness and contrast of an image is discreet function, mentioned in [7]. They are corresponds to:

1. Depth Discontinuities
2. Surface orientation Discontinuities
3. Changes in material properties
4. Variations in scene brightness

In general, a group of connected curves which denotes the boundary of the image surface. If the boundary detection step is successfully completed, then the subsequent task of interpreting pixel values contents in the original image may therefore be substantially simplified. But, it is not always possible to get exact edges from the real life images. Edges extracted from non-trivial images are often hampered by fragmentation i.e. the edge curves are not connected, missing edge segments, false edges etc., which complicate the subsequent task of interpreting the image data.

2.1 Edge Detection

Edge is a part of an image that contains significant variation. The edges provide important visual information since they correspond to major physical, photometrical or geometrical variations in scene object. Physical edges are produced by variation in the reflectance, illumination, orientation, and depth of scene surfaces. Since image intensity is often proportional to scene radiance, physical edges are represented by changes in the intensity function of an image [6] Therefore, it should be mandatory to find out the occurrence in perpendicular to an edge.

2.2 Different Types of Edges

The common types of edges, mentioned in [7] are following .

A Sharp Step, as shown in Figure 1(a), is an idealization of an edge. We know that an image is always band limited, so this type of graph never occurs. A Gradual Step, as shown in Figure 1(b), is very similar to a Sharp Step, but it has been smoothed out. But the change in intensity is not as quick or sharp. A Roof, as show in Figure 1(c), is different than the first two edges. The derivative of this edge is discontinuous. A Roof can have a variety of sharpness, widths, and spatial extents. The Trough, also shown in Figure 1(d), is the inverse of a roof.

There are many methods for edge detection, but most of them can be grouped into two categories, search-based and zero-crossing based mentioned in [8]. The search-based methods detect edges by first computing a measure of edge strength, usually a first-order derivative expression such as the gradient magnitude, and then searching for local directional maxima of the gradient magnitude using a computed estimate of the local orientation of the edge, usually the gradient direction. The zero-crossing based methods search for zero crossings in a second-order derivative expression computed from the image in order to find edges, usually the zero-crossings of the Laplacian or the zero-crossings of a non-linear differential expression. As a pre-processing step to edge detection, a smoothing stage, typically Gaussian smoothing, is almost always applied.

The main objective [9] of edge detection in image processing is to reduce data storage while at same time retaining its topological properties, to reduce transmission time and to facilitate the extraction of morphological outlines from the digitized image.

2.3 Criteria for Edge Detection

There are large numbers of edge detection operators available, each designed to be sensitive to certain [7] types of edges. The Quality of edge detection can be measured from several criteria objectively. Some criteria are proposed in terms of mathematical measurement, some of them are based on application and implementation requirements. In all five cases a quantitative evaluation of performance requires use of images where the true edges are known. The criterions are Good detection, Noise sensitivity, Good localization, Orientation sensitivity, Speed and efficiency. Criteria of edge detection will helps to evaluate the performance of edge detectors. Correspondingly, different techniques have been developed to find edges based upon the above criteria, which can be classified into linear and non linear techniques.

2.4 Procedure for Edge detection

Edges characterized object boundaries. It is also useful for segmentation, registration, and identification of objects in images which are mentioned in[1]. Edge points can be considered as pixels of abrupt gray-scale change. Therefore we can say that, it is reasonable to define edge points in binary images as black pixels with at least one white nearest neighbor, that is, pixel locations(m,n) such that u(m,n)=0 and g(m,n)=1, where

g(m,n) [u(m,n) u(m±1,n)] OR [u(m,n) u(m,n ± 1)]

Figure 4: Gradient of f(x,y) along r direction

Where denotes the logical exclusive-OR operation. For a continues image f(x,y), its derivatives can be assumed a local maximum in the direction of the edge. Therefore, one edge detection technique is to measure the gradient of f along r in a direction θ, i.e.

∂f/∂r = ∂f/∂x * ∂x/∂r + ∂f/∂y * ∂y/∂r = fx cosθ + fysinθ

2.5. Various Techniques for Edge Detection

There are many ways to perform edge detection. Various edge detection algorithms have been developed in the process of finding the perfect edge detector. However, the most may be grouped into two categories, gradient and Laplacian. The gradient method detects the edges by looking for the maximum and minimum in the first derivative of the image. The Laplacian method searches for zero crossings in the second derivative of the image to find edges.

2.6 Gradient-based method

The first derivative assumes a local maximum at an edge. For a gradient image f(x, y), at location (x, y), where x and y are the row and column coordinates respectively, typically consider the two directional derivatives, mentioned in [2, 12]. The two functions that can be expressed in terms of the directional derivatives are the gradient magnitude and the gradient orientation.

The gradient magnitude is defined by

g(x,y) (∆x2 + ∆y2)1/2

∆z = f(x+n,y) – f(x-n,y) and ∆y = f(x,y+n) – f(x,y-n)

Where n is a small integer usually unity.

This quantity gives the maximum rate of increase of f(x, y) per unit distance in the gradient orientation of g(x, y). The gradient orientation is also an important quantity. The gradient orientation is given by

Θ(x,y) atan (∆y/∆x)

Here the angle is measured with respect to the x-axis. The direction of the edge at (x, y) is perpendicular to the direction of the gradient vector at that point. The other method of calculating the gradient is given by estimating the finite difference.

2.6.1 Robert Edge Detector

The calculation of the gradient magnitude of an image is obtained by the partial derivatives Gx and Gy at every pixel location. The simplest way to implement the first order partial derivative is by using the Roberts cross gradient operator, mentioned in [12].

Therefore

Gx= f (i, j) – f (i+1, j+1)

Gy= f (i+1, j) – f (i,j+1)

The above partial derivatives can be implemented by approximating them to two 2×2 masks. The Roberts operator masks are:

These filters have been the shortest support, thus the position of the edges is more accurate, but the problem with the short support of the filters is its vulnerability to noise. It also produces very weak response to genuine edges unless they are very sharp.

2.6.2 Prewitt Edge detector

The Prewitt edge detector [2, 12] is a much better operator than Roberts’s operator. This operator having a 3 x 3 masks deals better with the effect of noise. An approach using the masks of size 3 x 3 is given below, the arrangement of pixels about the pixels [i, j].

The partial derivatives of the Prewitt operator are calculated as

Gx = (a6 +ca5+ a5) – (a4+ca1+ a2)

Gy = ( a2 +ca3+ a4) – (a0+ca7+ a6)

The constant c implies the emphasis given to pixels closer to the centre of the mask. Gx and Gy are the approximation at [i, j].

Setting c= 1, the Prewitt operator is obtained. Therefore the Prewitt masks are as follows

Gx Gy

These masks have longer support. They differentiate in one direction and average in the other direction, so the edge detector is less vulnerable to noise.

2.6.3 Sobel Edge Detector

The Sobel operator [2, 12] is the most known among the classical methods. The Sobel edge detector applies 2D spatial gradient convolution operation on an image. It uses the convolution masks shown in to compute the gradient in two directions (i.e. row and column orientations), and then works out the pixels’gradient through g=|gr+gc|. Finally, the gradient magnitude is threshold. The Sobel edge detector is very much similar to the Prewitt edge detector. The difference between the both is that the weight of the centre coefficient is 2 in the Sobel operator. The partial derivatives of the Sobel operator are calculated as

Gx = (a6 +2a5+ a4) – (a4+2a1+ a2)

Gy = ( a2 +2a3+ a4) – (a4+2a7+ a6)

Therefore the Sobel masks are:

Although the Prewitt masks are easier to implement than Sobel masks.

2.6.4. 4-neibougher operator

Instead of calculating edge strength at the point (r-½,c-½), it is desired to calculate it at the point (r,c),mentioned in [2, 12]. To take care of this, 3X3 mask are used as against 2X2 mask in Roberts operator. Then

d1 = g5 – g1 and d2 = g7 – g3

The corresponding masks are given by

2.6.5. Compass operator

Compass operators [11, 12] measure gradients in a selected number of directions shown in figure. An anti-clockwise circular shift of the eight boundary elements of these masks gives a 450 rotation of the gradient direction.

Let gk(m,n) denote the compass gradient in the direction θk = π/2 + kπ/4, k=0,…,.,7. The gradient at location (m,n) is defined as

Which can be threshold to obtain the edge map as before Only four of the preceding eight compass gradients are linearly independent. Therefore, it is possible to define four 3X3 arrays that are mutually orthogonal and span the space of these compass gradients. Compass gradients with higher angular resolution can be designed by increasing the size of the mask.

2.6.6 The Canny Edge Detector

The Canny operator, mentioned in [2, 12] is one of the most widely used edge finding algorithms. Canny proposed a method that was widely considered to be the standard edge detection algorithm in the industry. In regard to regularization explained in image smoothing, Canny saw the edge detection as an optimization problem. He considered three criteria desired for any edge detector: good detection, good localization, and only one response to a single edge. Then he developed the optimal filter by maximizing the product of two expressions corresponding to two former criteria (i.e. good detection and localization) while keeping the expression corresponding to uniqueness of the response constant and equal to a pre-defined value. The solution (i.e. optimal filter) was a rather complex exponential function, which by variations it could be well approximated by first derivative of the Gaussian function. This implies the Gaussian function as the smoothing operator followed by the first derivative operator. Canny showed that for a 1D step edge the derived optimal filter can be approximated by the first derivative of a Gaussian function with variance s as follow:

The Canny approach to edge detection is optimal for step edges corrupted by white Gaussian noise. This edge detector is assumed to be output of a filter that both reduces the noise and locates the edges. Its ‘optimality’ is related to the following performance criteria:

Good detection: Both the probability of missing real edge points and incorrectly marking non-existent edge points must be minimal.

Good localization: The distance between the actual and detected location of the edge should be minimal.

Minimal response: This criteria state that multiple responses to a single edge and ‘false’ edges due to noise must be eliminated.

After optimizing the above criteria in a certain fashion, an efficient approximation to the required operator is the first derivative of the two-dimensional Gaussian function G(x, y) applied to the original image. For example, the partial derivative with respect to x is defined as follows:

The first step of the edge detection algorithm is to convolve the image I(x, y) with a two dimensional Gaussian filter and differentiate in the direction of n.

Candidate’s edge pixels are identified as the pixels that survive a thinning process known as no maximal suppression. Any gradient value that is not a local peak should be set to zero. Each pixel in turn, forms the centre of a 3×3 neighborhood. The gradient magnitude is estimated for two locations, one on each side of the pixel in the gradient direction, by interpolation of the surrounding values. If the value of the centre pixel is larger than these of the surrounding pixels, the pixel is considered a maximal point. Otherwise, the pixel value is set to zero. The last step of the algorithm is to threshold the candidate edges in order to keep only the significant ones. Canny suggests hysterics threshold instead of a global threshold values. The high threshold is used to find “seeds” for strong edges. These seeds are grown to as long as an edge as possible, in both directions, until the edge strength falls below the low threshold value.

3. Stochastic Gradients

The above stated edge detection techniques [11] are poorly effective when the image is noisy. Because in above stated edge detection techniques passed the images through a low pass filter. So the noise cannot remove properly. A better alternative is to design a edge extraction masks, which take into an account of the presence in noise in a control manner. The following figure shows the edge model whose transition region is one pixel wide to detect the presence of an edge at location P.

Then calculate the horizontal gradient using formula as

Here, (m,n) and =(m,n) are the optimum forward

and backword estimates of u(m,n) from noisy observation given over some finite region W of left and right half plane respectively. W can be defined as

Forward estimates along the horizontal can be defined as

as follows

Similarly, we can find (m,n) at the point P(m,n). In the same manner we can find the vertical gradient at the point P(m,n).Let it be g2 (m,n) . From g1(m,n) and g2(m,n) we calculated g(m,n) using clockwise circular shift of the eight boundary elements of masks. The mask(g1) is implemented using the following matrix and g2 , g3, g4, g5, g6, g7 and g8 derivative equations are isotropic for rotation increments of 450 respectively.

Therefore, g(m,n) as follows:

3.1 Laplacian based method:

The Laplacian based methods, mentioned in [11] 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.

3.2 Laplacian of Gaussian

Gaussian filters are the most widely used filters in image processing and extremely useful as detectors for edge detection. It is proven that they play a significant role in biological vision particularly in human vision system. Gaussian-based edge detectors are developed based on some physiological observations and important properties of the Gaussian function that enable to perform edge analysis in the scale space.

The principle used in the Laplacian of Gaussian method is, the second derivative of a signal is zero when the magnitude of the derivative is maximum. The Laplacian of a 2-D function f(x, y) is defined as

The two partial derivative approximations for the Laplacian for a 3 x 3 region are given as

∆2f = 4( a8) – ( a1+ a3+ a4+ a7)

∆2f = 8( a8) – (a0+a1+ a2+ a3+ a4+ a5+ a6+ a7)

The masks for implementing these two equations are as follows

The above partial derivative equations are isotropic for rotation increments of 900 and 450, respectively. Edge detection is done by convolving an image with the Laplacian at a given scale and marks the points where the result have zero value, which is called the zero-crossings. These points should be checked to ensure that the gradient magnitude is large.

4 Experimental Results

We experimented with a picture “train” by passing it from many edge detection operators and the outputs are given bellow –

Original Image Sobel Output

4-neighbour output Compass Output

LOG Output Prewitt Output

Robert Output Canny output

Stochastic (noisy image) Sobel (noisy image)

4.1. Performance of Edge Detection Operation

To test the performance [11, 13] of our algorithm, we have applied it to a noisy image in sobel and stochastic operator where n0 be the number of edges pixels declared and n1 be the number of missed or new edges pixels of a noisy image. n0 is fixed for noiseless as well as noisy image, then the edge detection error can be given as follows.

In above stated example, the error for sobel operator used on noisy image with SNR 10dB is 24% whereas it is only 1.5% for stochastic operator.

5. Conclusion:

We have reviewed and summarized the characteristics of different common operators. Each approach has its own advantages and drawbacks in different areas but experimental comparisons on different approaches show which approach is suitable for which image. Although, all operators are roughly equivalent in case of noiseless image, but for practical applications, we conclude that the canny edge detection operator gives the best result in edge detection in a noiseless image. But in case of noisy image, the stochastic gradient is found to be quite effective. There are still possibilities for further scope.