A Comparative Assessment of the Performances of Different Edge Detection Operator using Harris Corner Detection Method

International Journal of Computer Applications (0975 – 8887) Volume 59– No.19, December 2012 A Comparative Assessment of the Performances of Different Edge Detection Operator using Harris Corner Detection Method Pranati Rakshit Dipanwita Bhaumik Kriti Bhowmik HOD, Dept of CSE, JISCE M.Tech Scholar, JISCE M.Tech Scholar,JISCE Kalyani Kalyani Kalyani ABSTRACT Edge detection is one of the most commonly used and one of the most important operations in image processing which reduces the useless information while retaining the important structural properties of an image. Here a comparative study of Sobel, Roberts, Prewitt, LoG, Canny, Zerocross algorithms are conducted and corner points using Harris Corner detection algorithm on the image are obtained after applying edge detection operators. General Terms Algorithm, Operator, Edge detection, Corner point detection. Keywords Sobel, Roberts, Prewitt, LoG, Canny, Zerocross, Harris Corner. Figure 1. Lena (Original Image) 1. INTRODUCTION An edge is the boundary between an object and the 2. EDGE DETECTION OPERATORS background, and indicates the boundary between overlapping 2.1 Sobel Operator objects. Edge detection is the process of identifying Mathematically, Sobel Operator uses two 3×3 matrix which discontinuities in images. are convolved with the original image to calculate Several variables are involved in selection of an edge approximations of the derivatives - one for horizontal detection operator such as edge orientation, noise changes, and one for vertical changes. The horizontal and environment, and edge structure. The geometry of the vertical derivative approximations are given as follows: operator determines the characteristic direction in which it is -1 0 1 most sensitive to edges. Edge detection is difficult in noisy 1 2 1 images since both the noise and edges contain high frequency -2 0 2 content[1]. Reduction of noise results in blurring and 0 0 0 distortion of image, removal of which results in less accurate -1 0 1 localization of edges. Effects such as refraction or poor focus 1 2 1 results in objects with boundaries defined by gradual change in intensity. Thus edge detection operators chosen must be responsive to such changes. Therefore problems of edge Gx Gy detection are false edge detection, missing of true edges, edge localization etc. Thus, here various edge detection techniques Figure 2. Masks used by Sobel Operator are compared and corner points on the edge detected images are generated using Harris Corner Detection algorithm. Here The x-coordinate is defined as increasing in the right- the very popular image of Lena has been taken for our direction, and the y-coordinate is defined as increasing in the research purpose. down-direction.The resulting gradient approximations can be combined to give the gradient magnitude, using: G=(Gx2+Gy2)1/2 Using the above equation, the gradient's direction can also be calculated: 7 International Journal of Computer Applications (0975 – 8887) Volume 59– No.19, December 2012 where, for example, Θ is 0 for a vertical edge which is darker Table 1. Table representing Harris-Corner points for on the right side. Sobel edge detected image Operators X-Coordinate Y-Coordinate 32 85 167 138 161 152 204 158 222 162 247 171 186 175 SOBEL 120 228 224 139 194 240 32 296 275 296 33 339 222 339 Figure 3.a) Lena after applying Sobel 2.2 Robert’s Cross Operator: Visual Inference : In the above image(Figure 3.a) it can be An edge detector should have the following properties: the seen that Sobel detects the edges of the image but breaks the edges produced should be well-defined, the background continuity of the edges which leads to lack of prominence . should have little noise, and the intensity of edges should be As a result, the image cannot be visually identified properly. close to human perception. With these criteria, Roberts Now Harris Corner Detection algorithm is applied on this proposed the following equation image (Figure: 3.a) to generate the corner points. As a result, 14 corner points are generated which are shown in Figure:3.b. where x is the initial intensity value in the image, z is the computed derivative and i, j represent the location in the image. The results of this operation highlights changes in intensity in a diagonal direction. In order to perform edge detection with the Roberts operator, first the original image is convolved, with the following two kernels: Figure 4 . Mask for Robert’s cross Operator Let I(x,y) be a point in the original image and Gx(x,y)be a point in an image formed by convolving with the first kernel Figure 3.b) Harris corner implemented on Sobel edge and Gy(x,y) be a point in an image formed by convolving with detected image (Fig 3.a) the second kernel. The gradient can then be defined as: The direction of the gradient can also be defined as follows: 8 International Journal of Computer Applications (0975 – 8887) Volume 59– No.19, December 2012 2.3 Prewitt’s Operator Prewitt’s Operator is similar to Sobel Operator but detects the horizontal and vertical edges of an image. The operator uses two 3×3 matrix which are convolved with the original image to calculate approximations of the derivatives - for horizontal changes, and for vertical changes respectively. Here Gx and Gy are defined as the horizontal and vertical derivative approximations and are computed as: -1 0 1 1 1 1 -1 0 1 0 0 0 -1 0 1 -1 -1 -1 Figure 5.a) Lena after applying Robert’s Visual Inference: In above image (Figure 5.a) when Robert’s cross operator is implemented, it is seen that it detects the Gx Gy edges but not as minutely as Zerocross, Canny and Sobel. As a result, most of the detailing of the image is lost making it Figure 6. Mask for Prewitt Edge detector even less recognizable than other detectors. When Harris Corner Detection algorithm is applied on image (Figure 5.a), 14 corner points are generated (Figure 5.b). Figure 7.a) Lena after applying Prewitt’s Figure 5.b) Harris corner implemented on Robert’s edge detected image (Fig 5.a) Visual Inference: In edge detection using Prewitt’s operator, it is observed that Prewitt detects edges (Figure: 7.a) better than Sobel and Robert’s but is not as detailed as Canny, LoG Table 2. Table representing Harris-Corner points for and Zerocross. When Harris Corner Detection algorithm is Robert’s edge detected image applied on Figure 7.a , 12 corner points are generated (Figure:7.b). Operators X-Coordinate Y-Coordinate 32 85 286 92 165 137 286 146 217 162 206 163 246 170 ROBERT’S 165 220 119 228 286 274 32 296 33 339 222 339 286 339 Figure 7.b) Harris corner implemented on Prewitt’s edge detected image (Fig 7.a) 9 International Journal of Computer Applications (0975 – 8887) Volume 59– No.19, December 2012 Table 3. Table representing Harris-Corner points for Prewitt’s edge detected image Operators X-Coordinate Y-Coordinate 32 85 286 92 286 99 286 114 167 138 286 144 PREWITT’S 224 239 286 275 32 296 33 339 222 339 286 339 2.4 Laplacian of Gaussian Figure 8. The 2-D LoG function.X,Y are marked in Laplacian filters are derivative filters that are used to find standard derivatives() areas of edges in images.Derivative filters are very sensitive to noise, it is common to smooth the image using a Gaussian filter before applying the Laplacian. This two-step process is called the Laplacian of Gaussian (LoG) operation. A possible matrix that approximates the effect of the Laplacian is This is called a negative Laplacian because the central peak is negative. It is just as appropriate to reverse the signs of the Figure 9.a) Lena after applying LoG elements, using -1s and a +4, to get a positive Laplacian. To include a smoothing Gaussian filter, combine the Laplacian and Gaussian functions to obtain a single equation: Visual Inference: This operator detects the edges more minutely than Robert’s, Prewitt’s, Sobel operators respectively, but the image generated after edge detection is not as prominent as generated after using Canny operator(Figure 9.a).When Harris Corner Detection algorithm is applied on Figure 9.a, it generates 12 corner points (Figure The LoG operator takes the second derivative of the image. 9.b). Where the image is basically uniform, the LoG will give zero. Wherever a change occurs, the LoG will give a positive response on the darker side and a negative response on the lighter side. At a sharp edge between two regions, the response will be: i) zero away from the edge ,ii)positive just to one side iii) negative just to the other side iv) zero at some point in between on the edge itself. Figure 9.b) Harris corner implemented on LoG edge detected image (Fig 9.a) 10 International Journal of Computer Applications (0975 – 8887) Volume 59– No.19, December 2012 Table 4. Table representing Harris-Corner points for LoG edge detected image Operators X-Coordinate Y-Coordinate 32 85 286 85 285 93 285 104 285 114 285 142 LoG 285 155 285 162 262 170 251 174 33 339 286 339 Figure 9.b) Harris corner implemented on Canny edge detected image (Fig 9.a) 2.5 Canny Operator Table 5. Table representing Harris-Corner points for The Canny operator works in a multi-step process. Initially Canny edge detected image the image is smoothed by Gaussian convolution. In order to highlight regions of the image with high first spatial Operators X-Coordinate Y-Coordinate derivative, a 2-D first derivative operator is applied on the smoothed image. Edges give rise to ridges in the gradient- 32 85 magnitude image. The algorithm then tracks along the top of 285 91 these ridges and sets zero to all pixels that are not actually on 285 103 the ridge top thus giving a thin line in the output. This process 285 114 is known as non-maximal suppression. The tracking process 251 134 exhibits hysteresis controlled by two threshold values: T1, T2, with T1 > T2. Tracking can only begin from a point on a ridge 286 140 higher than T1. Tracking then continues in both the directions CANNY 207 146 from that point until the height of the ridge falls below T2. 224 153 This hysteresis ensures that noisy edges are not broken up into 130 154 multiple edge fragments. 286 157 62 167 33 339 286 339 2.6 Zerocross Operator The Zerocross Operator looks for places in the Laplacian of an image where the value of the Laplacian passes through zero --- i.e. points where the Laplacian changes sign. Such points mostly occur at edges of the images --- i.e. points where the intensity of the image changes rapidly, but they also occur at places that are not as easy to associate with edges. Zero crossings always lie on closed contours, and so the output from the zero crossing detector is usually a binary image with single pixel thickness lines showing the positions of the zero crossing points. Figure 9.a) Lena after applying Canny Visual Inference: Among all six edge detection algorithm Canny gives the best result i.e. it gives most prominent image after edge detection(Figure 9.a).When Harris Corner Detection algorithm is applied on Figure 9.a it generates 13 corner points(Figure 9.b ). Figure 10.a) Lena after applying Zerocross 11 International Journal of Computer Applications (0975 – 8887) Volume 59– No.19, December 2012 VISUAL INFERENCE: Zerocross Operator gives more detailing than Sobel , Robert’s , Prewitt operators respectively and less than Canny and Log operators respectively. Yet it is not as prominent and continuous as Canny (Figure 9.a).When Harris Corner Detection algorithm is applied on Figure 10.b, it generates 13 corner points (Figure 10.b). where Ix (xi, yi) and Iy (xi, yi) indicate the partial derivatives with respect to xi and yi respectively. With a filter like [-1, 0, 1] and [-1, 0, 1] T, the partial derivative can be calculated from the image by substituting Eqn. (2) in Eqn. (1). The intensity structure of the local neighborhoods is calculated by the auto-correlation matrix given by C(x, y). Let α1 and α2 be Eigen values of C(x, y), there may be three cases that needs to be considered: 1. Both the Eigen values are small signifying uniform region (constant intensity). 2. Both the Eigen values are high signifying Interest point Figure 10.b) Harris corner implemented on Zerocross (corner) edge detected image (Fig 10.a) 3. One Eigen value is high signifying contour (edge) To find out the points of interest, corner responses Table 6. Table representing Harris-Corner points for characterized as H(x, y) by Eigen values of C(x, y). Zerocross edge detected image • C(x, y) is symmetric and positive it is definite Operators X-Coordinate Y-Coordinate that α1 and α2 are >0 • α1 α2 = det(C(x, y)) = AC –B2 32 85 • α1 + α2 = trace(C(x, y)) = A + C 234 132 • Harris suggested: the corner response 184 135 HcornerResponse = α1 α2 – 0.04(α1 + α2)2 236 142 Finally, corner points are obtained as local maxima of the 150 152 corner response. 210 158 Zerocross 250 159 4. Conclusion Since edge detection is one of the primitive steps of image 262 170 recognition, it is very important to know the difference 251 174 between different edge detection algorithms. In Biomedical 146 198 field, these techniques have huge impact. Also this facilitates 266 293 us to know which algorithm to apply in which circumstance. 32 295 Here, through this comparative study,both visual and 222 338 mathematical analysis has been done. 4.1 Visual Analysis 3. Harris Corner Detection After performing edge detection on Lena, the conclusion is made that among all six edge detection techniques, Canny Harris corner detector is based on the local auto-correlation operator provides the most accurate result i.e. the edges of the function of a signal which is used to measure the local image are continuous and clearly demarcated; thus making the changes of the signal with patches shifted by a small amount image recognizable. On a contrary, LoG and Zerocross in different directions. Given a shift (∆x, ∆y) to a point (x,y) operators detect edges more minutely. But in order to achieve the auto-correlation function is defined as : precision, it makes the image discontinuous and the features C(x,y) = ∑w[I(xi, yi)-I(xi+∆x,yi+∆y)]2 become less prominent. In case of Sobel, Robert's and …… (1) Prewitt's operators, neither they provide fine-level precision nor is the output image as recognizable as that of Canny. Thus roughly the conclusion is that in case of portrait or scenery, where I (xi, yi) represents the image function for (xi, yi) points canny provides best result due to its intelligent way of in the window W centered around (x, y). Here the Gaussian detecting edges in which it maintains both precision and window is defined as W, where σ defines the width of the image identity at the same time. Again LoG, Sobel are the window. The shifted image is approximated by an expansion choice for detecting fine-features such as biometric images known as Taylor expansion which is truncated to first order like retinal fundus image as they contain fine blood vessels. terms as shown in equation (2): 4.2 Mathematical Analysis I(xi+∆x,yi+∆y) ≈ [I(xi,, yi)+[Ix(xi, yi)Iy(xi,yi)]] [∆x ∆y] The following table shows the comparative results of the application of Harris Corner Detection algorithm on images …… (2) 12 International Journal of Computer Applications (0975 – 8887) Volume 59– No.19, December 2012 obtained as a result of applying different edge detection 5. References algorithms: [1] Raman Maini, Dr. Himanshu Aggarwal, “Study and Comparison of Various Image Edge Detection # Harris Techniques” Operators Corner Points [2] E. Argyle. “Techniques for edge detection,” Proc. IEEE, 14 vol. 59, pp. 285-86, 1971 Sobel [3] F. Bergholm. “Edge focusing,” in Proc. 8th Int. Conf. Robert’s 14 Pattern Recognition, Paris, France, pp. 597- 600, 1986 Prewitt’s 12 [4] J. Matthews. “An introduction to edge detection: The sobel edge detector,” Available at LoG 12 http://www.generation5.org/content/2002/im01.asp, Canny 13 2002. [5] L. G. Roberts. “Machine perception of 3-D solids” ser. Zerocross 13 Optical and Electro-Optical Information Processing. MIT Press, 1965 . [6] R. C. Gonzalez and R. E. Woods. “Digital Image Graphically it can shown as, Processing”. 2nd ed. Prentice Hall, 2002. [7] S.L.A.Lee, A.Z.Kouzani ,E.J.Hu “From Lung Images To Lung Models” :A review. [8] Mamta Juneja , Parvinder Singh Sandhu “Performance Evaluation of Edge Detection Techniques for Images in Spatial Domain” International Journal of Computer Theory and Engineering, Vol. 1, No. 5, December, 2009 [9] KonstantinosG. Derpanis, 2004, The Harris Corner Detector. [10] Tanmay Bhattacharya, Nilanjan Dey,S. R. Bhadra Chaudhuri,” A Novel Session Based Dual Steganographic Technique Using DWT and Spread Spectrum”, International Journal of Modern Engineering Research , Vol.1, Issue1, pp- 157-161 13