Memoire Online - Implementation of edge detection for a digital image

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.

Many edge-detection operators are based upon the 1^st 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.

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

The magnitude of the first derivative can be used to detect the presence of an edge at a point in an image.

Some other edge-detection operators are based upon the 2nd derivative of the intensity. This is essentially the rate of change in intensity gradient.

Here, we can alternatively search for zero-crossings in the second derivative of the image gradient.

-2

The signs of the 2^nd derivative can be used to determine whether an edge pixel lies on the dark or light side of an edge.[17]

Once we have calculated our derivative, the next stage is to apply a threshold, to determine where the result suggests an edge to be present. It is useful to be able to separate out the regions of the image corresponding to the objects in which we are interested, from the region of the image that correspond to background. Threshold often provides n easy and convenient way to perform this segmentation.

Thresholding is the simplest method of image segmentation on the basis of deferent intensities in the foreground and background regions of an image. Individual pixels in image are marked as «object» if their value is greater than some threshold value.(assuming an object to be bright than the background) and as» background «pixels if their values is less than threshold value. The key parameter in thresholding is the choice of a threshold.

Several different methods for choosing a threshold exist. But a common used compromiser method is thresholding with hysteresis. This method uses multiple thresholds to find edges. We begin by using the upper threshold to fid the start point. 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 low threshold.

2.4.4 EDGE DETECTION ALGORITHMS.

An edge, by definition, is that drastic change in value from one spot to the next either in an image or in one's own eyes. In the digital world, an edge is a set of connected pixels that lie on the boundary between two regions. Ideally, a digital edge would have one pixel colored a certain value and one of its neighboring pixels colored noticeably different. Since the contrast between the pixels is drastic, we label it an edge. Unfortunately, when dealing with digital pictures, most edges are blurred. This leads to edges having a gradual change of pixels levels from one object to the next thus causing the edge to be less defined and harder to distinguish. In this instance, one would have to devise an intuitive way to distinguish gray level transitions.

Edge detection is the process of determining where the boundaries of objects fall within an image. There are several algorithms that exist to date that are able detect edges. Roberts Cross was the first technique used and is thus the fasted and simplest to implement. Lastly, there is the Canny edge detection algorithm. This uses several steps to detect edges in an image. However, this algorithm can be slow at times due to its higher degree of complexity.

The Roberts Cross algorithm performs a two dimensional spatial gradient convolution on the image. The main idea is to bring out the horizontal and vertical edges individually and then to put them together for the resulting edge detection.

We have two typical Roberts Cross kernels .
+100-1	0+1-10

The two Roberts Cross kernels, shown above in Figure 1, are designed with the intention of bringing out the diagonal edges within the image. The Gx image will enunciate diagonals that run from the top-left to the bottom-right where as the Gy image will bring out edges that run top-right to bottom-left. The two individual images Gx and Gy are combined using the approximation equation

Roberts Cross is not quite as effective as the Sobel technique. It does bring out edges, but when compared the same image only using the Sobel algorithm, the amount of edges detected is poor. The Sobel approach seems to work the best.

In general, kernels are designed so that it consists of an odd number of rows and columns. This helps to define a distinct center in each kernel. Sampling pixels on each side of the center pixel leads to a better convolution image. This yields a better edge detection image produced in the outcome. The Sobel algorithm takes this account into effect when selecting its kernels.

estimate is vector sum of a pair of orthogonal vectors . Each orthogonal vector is a directional derivative estimate multiplied by a unit vector specifying the derivative's direction. The vector sum of these simple gradient estimates amounts to a vector sum of the 8 directional derivative vectors.

Sobel which is a popular edge detection method is considered in this work. There exists a function, edge.m which is in the image toolbox. In the edge function, the Sobel method uses the derivative approximation to find edges. Therefore, it returns edges at those points where the gradient of the considered image is maximum. The horizontal and vertical gradient matrices whose dimensions are 3×3 for the Sobel method has been generally used in the edge detection operations. In this work, a function is developed to find edges using the matrices whose dimensions are 5×5 in matlab.

Each direction of Sobel masks is applied to an image, and then two new images are created. One image shows the vertical response and the other shows the horizontal response. Two images combined into a single image. The purpose is to determine the existence and location of edges in a picture. This two image combination is explained that the square of created masks pixel estimate coincidence each other as coordinate are summed. Thus new image on which edge pixels are located obtained the value which is the squared of the above summation. The value of threshold in this above process is used to detect edge pixels.

An algorithm is developed to find edges using the new matrices and then, a matlab function, which is called as Sobel 5x5.m, is implemented in matlab. This matlab function requires a grayscale intensity image, two-dimensional array. The result which is returned by this function is the final image in which the edge pixels are denoted by white color.

The sobel Edge detection algorithm uses the following two kernels.
+1+2+1000-1-2-1	-10+1-20+2-10+1

The Sobel kernels, as shown in the above figure, are larger than its predecessor, the Roberts Cross, is. This causes the processes to be less susceptible to noise.

As one can see, there are only really two pixels of concern with the Roberts Cross algorithm thus noise can be a rather large issue. The Sobel algorithm deals with six pixels and in doing so takes a better average of the neighboring pixels. This along with slight blurring can eliminate most noise found within normal images.

First the image is run through a Gaussian blur to help get ride of a majority of the noise. Second, an edge detection algorithm is applied such as the Roberts Cross or Sobel techniques. From there the angle and magnitude can be obtained and used to determine which portions of the edges should be suppressed and which should be brought out. Lastly, there are two threshold cutoff points. Any value in the image below the first threshold is dropped to zero. Any value above the second threshold is raised to one. For any pixels whose values fall within the two thresholds, their values are set to zero or one, based on their neighboring pixels and their angle. The Canny algorithm first requires that the image be smoothed with a Gaussian mask, which cuts down significantly on the noise within the image. Then the image is run through the Sobel algorithm, and as discussed before, this process is hardly affected by noise. Lastly, the pixel values are chosen base on the angle of the magnitude of that pixel and its neighboring pixels. When using the canny edge detector there are two threshold levels. The first threshold is used to set all values in the image that fall below it to be set to zero. The second threshold level is used to set all values in the image that fall above it to be set to one. The values in the image that lay within the two threshold values are set to either zero or one based on their angle as specified by that algorithm. Thus, the image created is a binary image. Ideally, the lower threshold should be set relatively low so that a majority of the pixels are valued based on their angles. Then the upper threshold is set to a high value there tends to be a spurring effect that occurs on edges that branch off in a 'Y' shape. Unfortunately, when dealing with clouds or fog, this can be quite frequent and, as a result, there can be many spurs appearing in the result. Thus the value of the high threshold should not be set too had so it can, in a sense, prune the spurs away some.

Canny, which should be the best, might not be implemented correctly and therefore, does not work as it should. Currently it is able to detect edges that are well defined, but for minor edges, the best results are created when using the Sobel option. If the Canny detector worked properly it would be superior to both Sobel and Roberts Cross, the only drawback is that it takes longer to compute.[17]

The Prewitt edge detection is an alternative approach to the differential gradient edge detection. The operation usually output two images, one estimating the local edge gradient magnitude and other ones, estimating the orientation of the image.

The Prewitt operator is similarly to the sobel and some other operators approximating the first derivative, operators approximating the first derivatives are also called Compass operator because of the ability to determine gradient direction.

The gradient is estimated in eight (for 3X3 convolution mask) possible direction and convolution result of greatest magnitude indicate the gradient direction. Larger mask are possible.

The Prewitt Edge detection algorithm uses the following two masks (h_xand h_y).
111000-1-1-1	-101-101-101

Prewitt edge detection produces an image where higher grey-level values indicate the presence of an edge between two objects. The Prewitt edge detector mask is one of the oldest and best understand methods of detecting edges in images. Basically there are two masks, one for detecting image derivative in X and other one for detecting image derivative in Y.

In practice, one usually thresholds the result of Prewitt edge detection in other to produce a discrete set of edge.

Implementation of edge detection for a digital image

2.4.3 DETECTING AN EDGE.

2.4.4 EDGE DETECTION ALGORITHMS.