Idea Transcript
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
IJCST Vol. 3, Issue 2, April - June 2012
Framework for Efficient Edge Detection Techniques– Comparison Among Robert, Prewitt, Sobel, Robinson, Kirsch and Canny 1
B. Ramesh Naidu, 2P. Lakshman Rao, 3M. S. Prasad Babu, 4K. V. L Bhavani Dept. of CSE, AITAM, Tekkali, Srikakulam, AP, India Dept. of MCA, AITAM, Tekkali, Srikakulam, AP, India 3 Dept. of CS & SE, Andhra University, Visakhapatnam, AP, India 4 Dept. of ECE, AITAM, Tekkali, Srikakulam, AP, India 1
2
Abstract In this paper, we focused on the image processing techniques mainly image enhancement and edge detection. Edges are important features in an image since they represent significant local intensity changes. They provide important clues to separate regions within an object. Edge detection on an image significantly reduces the amount of data and filters out useless information, while preserving the important structural properties in an image. In this paper, we implemented edge detectors like Robert, first derivative, second derivative, Prewitt, Sobel, Robinson, Kirsch and Canny. In this paper the comparative analysis of various Image Edge Detection techniques is presented. The software is developed using Java 6.0.This paper provides various available techniques that are suggested by several authors with its merits and demerits. In this way, we say that, this study will help the researchers to develop better edge detection techniques. Keywords Image Processing, Edge Detection, Image Enhancement, Robert, First Derivative, Second Derivative, Prewitt, Sobel, Robinson, Kirsch and Canny I. Introduction Edge detection refers to the process of identifying and locating sharp discontinuities in an image. The discontinuities are abrupt changes in pixel intensity which characterize boundaries of objects in a scene. Classical methods of edge detection involve convolving the image with an operator, which is constructed to be sensitive to large gradients in the image while returning values of zero in uniform regions. There are an extremely large number of edge detection operators available, each designed to be sensitive to certain types of edges. Variables involved in the selection of an edge detection operator include Edge orientation, Noise environment and Edge structure. The geometry of the operator determines a characteristic direction in which it is most sensitive to edges [1]. Operators can be optimized to look for horizontal, vertical, or diagonal edges. Edge detection is difficult in noisy images, since both the noise and the edges contain high frequency content. Attempts to reduce the noise result in blurred and distorted edges. Operators used on noisy images are typically larger in scope, so they can average enough data to discount localized noisy pixels. This results in less accurate localization of the detected edges. Not all edges involve a step change in intensity [2-3]. Effects such as refraction or poor focus can result in objects with boundaries defined by a gradual change in intensity [4-5]. The operator needs to be chosen to be responsive to such a gradual change in those cases. So, there are problems of false edge detection, missing true edges, edge localization, high computational time and problems due to noise etc. Therefore, the objective is to do the comparison of various edge detection w w w. i j c s t. c o m
techniques and analyze the performance of the various techniques in different conditions. There are many ways to perform edge detection. However, the majority of different methods may be grouped into two categories: A. Gradient based Edge Detection The gradient method detects the edges by looking for the maximum and minimum in the first derivative of the image. B. Laplacian based Edge Detection The Laplacian method searches for zero crossings in the second derivative of the image to find edges. An edge has the onedimensional shape of a ramp and calculating the derivative of the image can highlight its location. II. Image Enhancement Image enhancement is the improvement of digital image quality (wanted e.g. for visual inspection or for machine analysis), without knowledge about the source of degradation. If the source of degradation is known, one calls the process image restoration. Image enhancement improves the quality (clarity) of images for human viewing. Removing blurring and noise, increasing contrast, and revealing details are examples of enhancement operations [6-8]. For example, an image might be taken of an endothelial cell, which might be of low contrast and somewhat blurred. Reducing the noise and blurring and increasing the contrast range could enhance the image. The original image might have areas of very high and very low intensity, which mask details. An adaptive enhancement algorithm reveals these details. Adaptive algorithms adjust their operation based on the image information (pixels) being processed. In this case the mean intensity, contrast, and sharpness (amount of blur removal) could be adjusted based on the pixel-intensity statistics in various areas of the image. Image processing technology is used by planetary scientists to enhance images of Mars, Venus, or other planets. Doctors use this technology to manipulate CAT scans and MRI images. The aim of image enhancement is to improve the interpretability or perception of information in images for human viewers, or to provide `better’ input for other automated image processing techniques [9-10]. A. Edge properties The edges extracted from a two-dimensional image of a threedimensional scene can be classified as either viewpoint dependent or viewpoint independent. A viewpoint independent edge typically reflects inherent properties of the three-dimensional objects, such as surface markings and surface shape. A viewpoint dependent edge may change as the viewpoint changes, and typically reflects the geometry of the scene, such as objects occluding one another. A typical edge might for instance be the border between a block of red color and a block of yellow. In contrast a line can be a small International Journal of Computer Science And Technology
1153
IJCST Vol. 3, Issue 2, April - June 2012
number of pixels of a different color on an otherwise unchanging background. For a line, there may therefore usually be one edge on each side of the line [11]. Edges play quite an important role in many applications of image processing, in particular for machine vision systems that analyze scenes of man-made objects under controlled illumination conditions. During recent years, however, substantial (and successful) research has also been made on computer vision methods that do not explicitly rely on edge detection as a preprocessing step. B. Approaches to Edge Detection There are many methods for edge detection, but most of them can be grouped into two categories, search-based and zero-crossing based. 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 will be described in the section on differential edge detection following below. As a pre-processing step to edge detection, a smoothing stage, typically Gaussian smoothing, is almost always applied [12]. The edge detection methods mainly differ in the types of smoothing filters that are applied and the way the measures of edge strength are computed. As many edge detection methods rely on the computation of image gradients, they also differ in the types of filters used for computing gradient estimates in the x- and y-directions [13-14]. A diagrammatic view of the edge detection process is shown in fig. 1.
Fig. 1: Block Diagram of Edge Detector C. Steps in Edge Detection Edge detection contain three steps namely Filtering, Enhancement and Detection. The overview of the steps in edge detection are as follows. 1. Filtering Images are often corrupted by random variations in intensity values, called noise. Some common types of noise are salt and pepper noise, impulse noise and Gaussian noise. Salt and pepper noise contains random occurrences of both black and white intensity values. However, there is a trade-off between edge strength and noise reduction. More filtering to reduce noise results in a loss of edge strength [15]. 2. Enhancement In order to facilitate the detection of edges, it is essential to determine changes in intensity in the neighborhood of a point. Enhancement emphasizes pixels where there is a significant change in local intensity values and is usually performed by computing the gradient magnitude [16].
1154
International Journal of Computer Science And Technology
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
3. Detection Many points in an image have a nonzero value for the gradient, and not all of these points are edges for a particular application. Therefore, some method should be used to determine which points are edge points. Frequently, thresholding provides the criterion used for detection [17]. III. Edge Detection Methods Several most frequently used edge detection methods are used for comparison. These are • Robert, • Prewitt, • Sobel, • Kirsch, • Robinson and • Canny [27]. The details of methods as follows, A. The Roberts Detection The Roberts Cross operator performs a simple, quick to compute, 2-D spatial gradient measurement on an image. It thus highlights regions of high spatial frequency which often correspond to edges. In its most common usage, the input to the operator is a grayscale image, as is the output. Pixel values at each point in the output represent the estimated absolute magnitude of the spatial gradient of the input image at that point [4].
Fig. 2: Roberts Mask B. The Prewitt Detection The prewitt edge detector is an appropriate way to estimate the magnitude and orientation of an edge. Although differential gradient edge detection needs a rather time consuming calculation to estimate the orientation from the magnitudes in the x and y-directions, the compass edge detection obtains the orientation directly from the kernel with the maximum response. The prewitt operator is limited to 8 possible orientations, however experience shows that most direct orientation estimates are not much more accurate. This gradient based edge detector is estimated in the 3x3 neighbourhood for eight directions. All the eight convolution masks are calculated. One convolution mask is then selected, namely that with the largest module[4].
Fig. 3. Prewitt Mask C. The Sobel Detection The Sobel operator performs spatial gradient measurement on an image and so emphasizes regions of high spatial frequency that correspond to edges. Typically it is used to find the approximate absolute gradient magnitude at each point in an input grayscale w w w. i j c s t. c o m
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
IJCST Vol. 3, Issue 2, April - June 2012
image. In theory at least, the operator consists of a pair of 3x3 convolution kernels as shown in fig. 4. One kernel is simply the other rotated by 900. This is very similar to the Roberts Cross operator [4]. The convolution masks of the Sobel detector are shown in fig 4.
Fig. 4: Sobel Mask D. Kirsch Compass Detection It calculates an approximation of the first derivative of the image data and is used as an edge detector [18]. The filter is based on the following filter masks are shown in fig 5:
Fig. 7: Canny Edge detector convolution kernels IV. Implementation and Interface Fig. 5: Kirsh Mask E. Robinson Detection Calculates an approximation of the first derivative of the image data and is used as an edge detector. In robinson the following four of the originally proposed eight 3x3 filter masks are convolved with the image [19]. The other four masks are obtained by a multiplication by -1. All masks contain only the values 0,1,-1,2,-2 as shown in fig. 6.
Fig. 6: Robinson Mask F. Canny Edge Operator The Canny method finds edges by looking for local maxima of the gradients. The gradient is calculated using the derivative of a Gaussian filter. The method uses two thresholds, to detect strong and weak edges, and includes the weak edges in the output only if they are connected to strong edges [20-21]. This method is therefore less likely than the others to be fooled by noise, and more likely to detect true weak edges as shown in fig. 7.
A. Implementation In this paper, we design the applet using java. This applet contains common edge detection algorithms Roberts Cross Operator, Prewitt Edge Detection Operator, and Sobel Edge Detection Operator and also canny edge detection algorithm. It also utilizes Gaussian Blur, Non-maximum Suppression, and Thresholding techniques. The user can select from a variety of files, and can also enter the path of a local file on the hard drive. The simplest Edge Detection methods rely on finding the first order differences between adjacent pixels. The most obvious way to implement this is to find the x-change and y-change, and consolidate this information (as represented by the Simple algorithm). Robert’s Cross Operator is more successful in that it takes both diagonals to calculate edges. Since edge detection is essentially the same as differentiating a function, the Prewitt Edge Detection Operator takes the gradient vector of a 3x3 area, with areas having a larger gradient vector being defined as “edges”. Sobel Edge Detection Operator is very similar to Prewitt Edge Detection Operator, except that it takes into account the Gaussian distribution to finely define edges. There are other ways to decrease erroneous pixels and enhance the clarity of edges. Gaussian Blur is the first step. This smoothes pixels and decreases the number of erroneous results. Non-Maximum Suppression essentially finds the maximum value of each “line”, and deletes the pixels that are not part of the maximum “line”. This cleans up the image for a clearer edge. Lastly, Thresholding removes the pixels that are less than a certain value. This removes unwanted pixels, softer edges, and erroneous results. The edge detection operators can be represented as a “template”, which simplifies the calculations in the java applet. B. Interface In this paper, we developed an interface as shown in fig. 8. In this interface we easily chose the image what we required and choose the required algorithm, and finally observe the result.
w w w. i j c s t. c o m
International Journal of Computer Science And Technology
1155
IJCST Vol. 3, Issue 2, April - June 2012
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
Fig. 8: Interface V. Experimental Results and Analysis In this section, we compared a variety of existing methods for edge detection. Fig 9 to 14 shows the Robert, Prewitt, Sobel, Robinson, Kirsch and Canny methods respectively with different threshold values (32,64,128). Fig. 9 to 14, shows the results of different edge detection algorithms with threshold values=32,64,128. ALGORITHM
ORIGINAL IMAGE
These results show that the results corresponding to 32 localizes edges very well but detect clutter and noise as edges. The results corresponding to 64 include cleaner results but the edges are not well localized. On the other hand, by combining results from scales 32 to 255, we are able achieve edge detection results that both localize edges precisely and create a cleaner edge detection.
EDGES
TEXTURES
ROBERTS
Threshold=32
Threshold=64
Threshold=128
Fig. 9: Robert Method with Different Thresholds
1156
International Journal of Computer Science And Technology
w w w. i j c s t. c o m
IJCST Vol. 3, Issue 2, April - June 2012
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
ALGORITHM
ORIGINAL IMAGE
EDGES
TEXTURES
Prewitt
Threshold=32
Threshold=64
Fig. 10: Prewitt Method with Different Thresholds ALGORITHM
ORIGINAL IMAGE
Threshold=128
EDGES
TEXTURES
Sobel
Threshold=32
Threshold=64
Fig. 11: Sobel Method with Different Thresholds
w w w. i j c s t. c o m
Threshold=128
International Journal of Computer Science And Technology
1157
IJCST Vol. 3, Issue 2, April - June 2012
ALGORITHM
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
ORIGINAL IMAGE
EDGES
TEXTURES
Robinson Threshold=32
Threshold=64
Fig. 12: Robinson Method with Different Thresholds ALGORITHM
ORIGINAL IMAGE
Threshold=128
EDGES
TEXTURES
Kirsch
Threshold=32
Threshold=64
Fig. 13: Kirsch Method with Different Thresholds
1158
Threshold=128
International Journal of Computer Science And Technology
w w w. i j c s t. c o m
IJCST Vol. 3, Issue 2, April - June 2012
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
ALGORITHM
ORIGINAL IMAGE
EDGES
TEXTURES
Canny
Threshold=32
Threshold=64
Fig. 14: Canny Method with Different Thresholds
Threshold=128
VI. Conclusion and Future Work Since edge detection is the initial step in object recognition, it is important to know the differences between edge detection techniques. In this paper we studied the most commonly used edge detection techniques of Gradient-based and Laplacian based Edge Detection. The software is developed using Java.6.0.This article gave an overview of edge detection algorithms as well as interface as we developed. Edge detection will always be a challenge for researchers. Higher-level edge detection techniques and appropriate programming tools only facilitate the process but do not make it a simple task. In this we say that, this study will help the researchers to develop the better techniques in the field of edge detection. References [1] Pellegrino FA, Vanzella W, Torre V.,"Edge Detection Revisited", IEEE Trans Syst Man Cybernetics Part B Cybernetics 2004; 34(3):1500-18. [2] Rosin Pl, Ioannidis E.,"Evaluation of global image thresholding for change detection", Pattern Recognit Lett 2003; 24: 2345-56. [3] Zhai, L., Dong, S., Ma, H.,"Recent Methods and Applications on Image Edge Detection", In Proceedings of the 2008 international Workshop on Education Technology and Training & 2008 international Workshop on Geoscience and Remote Sensing - Vol. 01 (December 21–22, 2008). ETTANDGRS. IEEE Computer Society, Washington, DC, pp. 332-335, 2008.
w w w. i j c s t. c o m
[4] N. Senthilkumaran, R. Rajesh,“Edge Detection Techniques for Image Segmentation - A Survey”, Proceedings of the International Conference on Managing Next Generation Software Applications (MNGSA-08), 2008, pp. 749-760. [5] E. Argyle,“Techniques for edge detection”, Proc. IEEE, Vol. 59, pp. 285-286, 1971. [6] Acharya and Ray,“Image Processing: Principles and Applications”, Wiley-Interscience, 2005. [7] Ou-yi Zheng, Ji-lai Rao; Lei Wu(2010),“Edge detection methods in digital image processing”, ICCSE, pp. 471 – 473. [8] R, Raskar; Tan, K-H; Feris, R.; Yu, J.; Turk, M.,“Nonphotorealistic Camera:Depth Edge Detection and Stylized Rendering Using Multi-Flash Imaging”, ACMSIGGRAPH, August 2004. [9] Lindeberg, T.,“Edge detection and ridge detection with automatic scale selection”, International Journal of Computer Vision, 30, 2, pp. 117-154, 1998. [10] T. Chen, Q. Wu, R. Rahmani-Torkaman, J. Hughes,“A pseudo top-hat mathematical morphological approach to edge detection in dark regions”, Pattern Recognition, Vol. 35, No. 1, pp. 199-210, January 2009. [11] J. Matthews (2002),“An introduction to edge detection: The sobel edge detector”, [Online] Available: http://www. generation5.org/content/2002/im01.asp [12] Chang-Huang, C.,"Edge detection based on class ratio", 152, sec.3, Peishen Rd., Shenkeng, Taipei, Taiwan, R.O.C, 2002.
International Journal of Computer Science And Technology
1159
IJCST Vol. 3, Issue 2, April - June 2012
ISSN : 0976-8491 (Online) | ISSN : 2229-4333 (Print)
[13] Orlando J. Tobias, Rui Seara,"Image Segmentation by Histogram Thresholding Using Fuzzy Sets”, IEEE Transactions on Image Processing, Vol. 11, No. 12, 2004, pp. 1457-1465. [14] . Lianquiang Niu,Wenjuli,“Color Edge Detection on Direction Information Measure”, In Proceedings of the sixth world congress on Intelligent Control and Automation, June 21-23, 2006. [15] N. Senthilkumaran, R. Rajesh,“A Study on Split and Merge for Region based Image Segmentation”, Proceedings of UGC Sponsored National Conference Network Security (NCNS08), 2008, pp. 57-61. [16] Xian Bin Wen, Hua Zhang, Ze Tao Jiang,"Multiscale Unsupervised Segmentation of SAR Imagery Using the Genetic Algorithm”, Sensors, Vol. 8, 2008, pp.1704-1711. [17] Mantas Paulinas, Andrius Usinskas,“A Survey of Genetic Algorithms Applicatons for Image Enhancement and Segmentation”, Information Technology and Control, Vol. 36, No. 3, 2007, pp. 278-284. [18] Fathy, M. ; Mahmoudi, M.T.,“A classified and comparative study of edge detection algorithms”, IEEE, pp. 117-120 2002. [19] Robinson, G. S.,"Detection and coding of edges using directional masks", Proceedings of the Seminar, San Diego, Calif., August 24-25, 1976. [20] Y. Yakimovsky,“Boundary and object detection in real world images”, JACM, Vol. 23, No. 4, pp. 598-619, 1976. [21] T. Peli, D. Malah,“A Study of Edge Detection Algorithms”, Computer Graphics and Image Processing, Vol. 20, pp. 1-21, 1982.
1160
International Journal of Computer Science And Technology
w w w. i j c s t. c o m