A Review: Circle Detection Using Modified Canny Edge Detection Algorithm

A Review: Circle Detection Using Modified Canny Edge Detection Algorithm

Nitasha1, Reecha Sharma2

1M.Tech Student, UCOE, Punjabi University,

2Assistant Professor, UCOE, Punjabi University

Abstract:

In our ro utine life or day-to-day experiences, many objects that perceive are in circular form like coins, rings etc. The detection of their presence in an image reliably and efficiently is an important task in image processing. The Hough transform techniques for detection of shapes require a huge memory space for data processing, hence needs a lot of time in computing the location of the data space, writing to and searching through the memory space. In this paper, it is propose a efficient scheme for circle detection in grayscale digital images. First, it detect edges of the digital image using Canny Edge Detection Technique. Second, for contour tracing applies Freeman Chain Code. This algorithm can be applied to static images as well as vedio.

Keywords: Edge detection; Canny Edge Detection Algorithm; Chain Code; Circle Detection.

1. Introduction

   A human being can find out a particular object like circle or rectangle fro m various objects by observing their shape, color, te xture and feature and after that we can calculate properties of shapes like perimeter, area etc. To generate this intelligence into a system, we need to imple ment techniques to help the system in recognizing the shapes of object. For this, use modified canny edge detection algorith m. Edge detection is the first and very important step in shapes detection. In this paper we use canny edge detection technique for edge detection because canny edge detection technique is optimal a lgorithm for edge detection as compared to Sobel, Prewitt and Robert cross operators. The Canny edge detector is a very popular and effectiv e edge feature detector that is used as a pre-processing step in many computer vision algorithms. It is a multi-step detector which perfo rms smoothing and filtering, non-ma xima suppression, followed by a connected-component analysis stage to detect true edges, while suppressing false non

   edge filter responses. After finding edges in image we apply Free man chain code for contour detection. Th e flow- chat is shown in figure 2 to detect circle fro m images using Canny edge detection technique [3].

   1. Canny Edge Detection Technique:

      The Canny edge detector is a very popular and effective edge feature detector that is used as a pre-processing step in many computer vision algorithms. It is a multi-step detector which perfo rms smoothing and filtering, non -ma xima suppression, followed by a connected-component analysis stage to detect true edges, while suppressing false non edge filter responses. Steps of canny edge detection algorith m a re shown in the form of flow-chat in figure no 1.

      Canny defined a set of criteria that ma ximize the probability of detecting true edges while minimizing the probability of false edges [7].

      There are many ways to perform edge detection. However, the ma jority of d ifferent methods may be grouped into two categories:

      Gr adient: The gradient method detects the edges by looking for the ma ximu m and min imu m in the first derivative of the image.

      Laplaci an: The Laplacian method searches for zero crossings in the second derivative of the image to find edges.

      To smooth the image, the Canny edge detector uses Gaussian convolution as shown in figure no 1.

      Ne xt, the image is convolved with a 2D first derivative operator to determine grad ient magnitude and direction at each pixel. Note that the ma xima and min ima of the first derivative gradient are the same as the zero-crossings of the second directional derivative. Only the ma xima crossings are of interest because these pixe ls represent the areas of the sharpest intensity changes in the image. These zero- crossings are the pixe ls that represent the set of possible edges. All other pixe ls are subsequently suppressed. Finally, a two-threshold technique or hysteresis is

      performed along the rema ining pixels to determine the final set of edges.

      Gaussian S moothing

      Gradient Filtering

      Non-maximum S upression

      Hysteresis Thresholding

      Figure 1: Flow diagram of Canny Edge Detector

      If a single threshold, T1 is applied to an image, and an edge has an average strength equal to T1, then due to noise, there will be instances where the edge dips below the threshold. Equally it will also e xtend above the threshold making an edge look like a dashed line. To avoid this, hysteresis uses 2 thresholds, a high and a low. . Any pixe l in the image that has a value greater than T1 is presumed to be an edge pixel, and is marked as such immediately. Then, any pixels that are connected to this edge pixel and that have a value greater than T2 a re a lso selected as edge pixels. If you think of following an edge, you need a gradient of T2 to start but you don't stop till you hit a gradient below T1.

      Figure2: Method for shapes detection in Gray Scale images.

   2. Freeman Chain Code for contour tracing:

Chain code is a list of codes ranging from 0 to 7 in clockwise direction. These codes represent the direction of the next pixel connected in 3×3 window, as shown in table

1. The coordinates of the next pixe l is calculated based on the addition and subtraction of columns and row by 1, depending on the value of chain code. Corresponding to the code in table 1, the next pixel position can be obtained by using table 2. For e xa mple , if a current pixe l is located at coordinate (5,5), the coordinate of the next pixel based on chain code is given by table 2. The disadvantage is that we have to scan all the eight neighboring pixel while contour tracing.

   There are two princip les to track the edges which form the boundary of an object: one based on edge strength, and the other based on pixe l d irection [5].

   Table 1. Chain code

   	Column-1	Column	Column+1
   Row-1	5	6	7
   Row	4	Current pi xel	8
   Row+1	3	2	1

   Current Pi xel at c oor di nate (5,5 )
   Code	Next Row	Next Column
   0	5	5
   1	6	6
   2	6	5
   3	6	4
   4	5	4
   5	4	4
   6	4	5
   7	4	6

   Table 2. Pixel position

   At each pixel we determine the position of ne xt p ixe l and so on the outline of the whole object can be obtained. Hence, given a binary image, the boundary of the shape can be determined efficiently.

   1. Results: Input Image:

      Output Image: (1) After Edge Detection

      (2) Afte r Circle Detection

   2. Conclusion and Future Scope:

      We imp le ment this algorithm to detect shapes in digital images. Chain code is the best method for boundary detection so we can use this method to detect numerica l numbers an to recognize characters. Sometime its very difficult to recognize simila r numbers like 5 and 6 , O and 0 etc. To recognize these characters correctly we can use Free man chain code algorith m.

   3. References:

1. Kaushik Chattopadhyay¹, Joydeep Basu², Amit Konar³, An Efficient Circ le Detection Scheme in Digita l Images Using Ant System Algorith m, Depart ment of Electronics and Telecommunication Engineering, Jadavpur University, Kolkata-700032, India.

2. Free man H. 1974. Co mputer Processing of Line Dra wing Images. Co mputing Surveys. 6(1): 5797 .

3. R S Vaddi1, L N P Boggavarapu1, H D Vankayalapati2,

   K. R. Anne1, CONTOUR DETECTION USIN G FREEMA N CHAIN CODE A ND APPROXIMATION METHODS FOR THE REA L TIM E OBJECT

   DETECTION. 1Depart ment of Information Technology, V R Siddhartha Engineering College, Kanuru, Vijayawada, India. 2 Department of Co mputer Science & Engineering, V R Siddhartha Engineering College, Vijayawada, India.

4. HABIBOLLA H HARON1, SITI MARIYAM SHAMSUDDIN2& DZULKIFLI M OHAM ED3, CHAIN CODE A LGORITHM IN DERIVING T -JUNCTION AND REGION OF A FREEHAND SKETCH, Jurnal Teknologi, 40(D) Jun. 2004: 25 36 © Universit i Te knologi Ma laysia.

5. R. C. Gon zale z and R. E. Woods. Digita l Image Processing. 2nd ed. Prentice Hall, 2002.

6. J. F. Canny. A computational approach to edge detection. IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, no. 6, pp. 679-697, 1986.

7. Yuancheng Mike Luo and Raman i Duraiswa mi,Canny Edge Detection on NVIDIA CUDA, Perceptual Interfaces and Reality Laboratory Co mputer

   Science & UM IACS, University of Maryland, Co llege Park.

8. Walid Shahab, Ha ze m Al-Otu m, and Farouq Al-Ghoul, A Modified 2D Chain Code Algorith m for Object Segmentation and Contour Tracing EE Depart ment, Jordan University of Sc ience & Technology, Jordan,2009.

9. Jau Ruen Jen, Mon Chau Shie, and Charlie Chen (2006). A Circu lar Hough Transform Hardwa re for Industrial Circle Detection Applications.

10. Marcin Sme reka and Ignacy Duleba (2008). Circula r object detection using a modified Hough transform. Int. J. Appl. Math. Comput. Sci., vol. 18, no. 1, pp. 85-91 Doi:10.2478/v10006-008-0008-9.