Comparison Between Circular Hough Transform And Modified Canny Edge Detection Algorithm For Circle Detection

Comparison Between Circular Hough Transform And Modified Canny Edge Detection Algorithm For Circle Detection

1Nitasha, 2Shammi Sharma, 3Reecha Sharma

1M.tech Student, UC OE, Punjabi University, Patiala,

2M.Tech Student, IITT pojewal,

3Assistant Professor, UC OE, Punjabi University,

Abstract: The circle is one of the most common shapes in our daily life, and indeed the universe. Planets, the move ment of the planets, natural cycles, natural shapes – there are circ les absolutely everywhere. The circle is one of the most comple x shapes, and indeed the most difficult for man to create, yet nature manages to do it perfectly. The centers of flowers, eyes, and many more things are circula r and we see them in our every-day life. Detection of circles is very important for us. In this paper, first detect a circle with Circu lar Hough Transform and then with Modified Canny Edge Detection Algorith m. Coding is done in MATLAB R2010a . It proves that Modified Canny Edge Detection Algorith m is best algorithm for circ le detection as compared to Circula r Hough Transform. The Modified Canny Edge Detection Algorith m is very fast algorithm to detect circles from the images as compared to Circu lar Hough Transform.

Keywords: Canny Detection, Co mparison between Canny and Circular Hough Transform, Circ le detection.

1. Introduction:

   Dig ital image processing is the use of computer algorithm to perform image processing on digital images. Image processing operations can be roughly divided into three ma jor categories:

   Image Co mpression, Image Enhance ment and Restoration, Image Seg mentation.

   Image Compression: Image co mpression means reducing the amount of data required to represent an image.

   Image Enhance ment and Restoration: Whenever an image is converted from one form to another, such as digitizing, transmitting, scanning, etc, some form of

   degradation occur at the output. Improve ment in the quality of these degraded images can be achieved by the application of restoration and/or enhancement technique. Image enhancement improves the quality (clarity ) of images for hu man vie wing. re mov ing blurring and noise, increasing contrast and revealing details are exa mp les of enhancement operations.

   Image Segmentati on: Seg mentation subdivides an image into its constituent regions and objects.

   Edge detection is part of image segmentation. Edge detection is very useful in a number of contexts. Edge characterizes object boundaries and are, therefore, useful for segmentation, registration and identificat ion of objects in scenes. The output of edge detection should be an edge image, in which the value of each pixe l re flects how strong the corresponding pixe l in the origina l image meets the requirements of being an edge pixel. Many edge detectors have been proposed, such as Sobel, Robert and Prewitt.

   Detecting and recognizing the shapes in an image is e xtre me ly important in industrial applications in recognizing the object. Detecting circles in an image is one of the problems that is discussed in this paper. Many algorith ms, such as Linear Square Method [2], Hough Transform, and Canny Edge Detection Algorithms have been proposed to detect circles. These algorith ms detect circ les fro m the edge detected images. A mong these algorith ms, Early Circula r Hough Transform has been wide ly successful in meeting the real time require ment of being able to detect the circles in noisy environments. Circula r Hough Transform and Modified Canny Algorith m are discussed in next section. And also discussed Modified Canny Algorithm is best algorithm to detect circle as co mpared to Circu lar Hough Transform.

2. Circular Hough Transform:

   One of the most common ly used algorith ms to recognize diffe rent shapes in an image is Hough Transform [3]. Hough Transform was introduced by Paul Hough in 1962 and patented by IBM. In 1972 Richard Duda and Peter Hart modified Hough Transform, which is used universally today under the name Genera lized Hough Transform [4]. An e xtended form of Genera l Hough Transform, Circular Hough Transform (CHT) [3], is used to detect circles. Flo w-chat of Circu lar Hough Transform is shown in figure 1.

   The edge detected from the Canny edge detector forms the input to extract the circle using the Circular Hough Transform.

   Figure 1. Fl ow-chat of Circular Hough Tr ansfor m

   1. Parame ter Re presentation: The e quati on of the circle is :

      r2 = (x-a )2 + (y-b)2 (1)

      As it can be seen the circle to get three parameter r, a and b, where a & b are the centre of the circle in the direction x & y respectively and r is the radius .

      The parame ter re presentation of the circle is:

      x=a +r*cos() (2)

      y=b + r*sin() (3)

      Thus the parameter space for a circ le will belong to R3. As the number of para meter needed to describe the shape increase as well as the dimension of the parameter space R increase so do the comple xity of the Hough transform.

   2. Accumul ator:

      At each edge point we draw a circle with centre in the point with the desired radius .This circle is drawn in the parameter space, such that our x-a xis is the a-value and y- a xis in the b-value and z-a xis is the radii. At the coordinates which belongs to the parameter o f the drawn circ le .We inc re ment the value in our accumulator matrix which essentially has same size as para meter space .In this way we sweep over energy edge point in the input image dra wing c irc le with the desired circle with desired

      radii and incre menting the value in our accumulator. When every edge point and every desired radius is used we can turn our attention to accumulator will now contain numbers corresponding to the number of c irc les passing through the individual coordinate. Thus the highest number correspond to the circle of the c irc le in the image.

      Figure2. Illustration of circul ar houg h tr ansfor m.

3. Modified Canny Edge Detection Algorithm:

   Flow-chat of Modified Canny Edge Detection Algorithm to detect circles fro m the images is shown in figure no 3.

   Figure3. Fl ow-chat of Modi fie d Canny Edge De tection Algorithm

   The goal of this algorithm is to locate the circles in an image more quickly and with effic ient use of resources by finding the edges.

   In the first stage noise is removed fro m the image by using Gaussian filter. After that Edge strength and Edge Direction is find out at each pixe l by using Sobel Operator. Then non-ma ximu m suppression. It is a process for marking all pixels whose intensity is not ma ximal as zero within a certa in loca l neighborhood[5]. Th is local neighborhood can be a linear window at d iffe rent directions. Figure 4. shows four e xa mples of linear windows at angles of 0o, 45o, 90o, and 135o.

   Figure 4. Line ar window at the angle of (a) 135 o (b) 90o (c) 0o (d) 45o

   Fro m this operation we thereby get thin edges of the objects in an image. These thin edges found can form a boundary of a circular object in the image. In the next

   section, we use these thin edges found to find the arcs which can be part of a potential c ircle.

   For contour tracing, Freeman Chain Code Algorithm is used. Chain code is a list of codes ranging from 0 to 7 in clockwise direction. These codes represent the direction of the next pixe l connected in 3×3 windows. After that we find circ le fro m the images very easily and effic iently.

4. Results:

   Co mparison between Hough Transform And Modified Canny Edge Detection Algorith m : When apply ough Transform and Modified Canny Edge Detection algorith m to detect circles than we see these parameters which are shown in Table no 1:

   S.No .	Para meters	Hough Transform	Modified Canny Edge Detection Algorith m
   1)	Mean Square Error (MSE)	0.015603	0.006836
   2 )	Peak Signal Noise Rat io (PSNR)	152.5067 db	160.7587 db
   3)	Norma lized Absolute Error (NA E)	0.000364	0.524588
   4)	Cross Core lation	39.29142	83.05369
   5)	Average Diffe rence	0.0000348	0.0041113
   6)	Maximu m Diffe rence	0.720027	0.631108

   1. Original Image:

   2. After Circ le Detection Using Circula r Hough Transform:

      1. 3D Accu mulation array of Circu lar Hough Transform:

      2. Circ le Detection Image using Circular Hough Transform:

   3. Image After Circ le detection using Modified Canny Edge Detection Algorith m:

5. Conclusion:

   In this paper, we compare Hough transform and Modified Canny Edge Detection Algorithm to detect circles from images. Here we co mpare various parameters like M SE, PSNR, SC etc. Fro m table we observed that Mean Square Error (MSE) value is less, when we detect circle fro m images using Modified Canny Edge Detection algorith m and Peak Signal No ise Rat io (PSNR) is large as co mpared to Circula r Hough Transform. There a re some more parameters a lso which we co mpare for both algorith ms. So Modified Canny Edge Detection Algorithm is best as compared to Hough Transform.

6. References:

1. R. C. Gon za lez and R. E. Woods, Digital Image Processing Second Edit ion[M]. Upper Saddle River, NJ: Pearson Education Inc., 2002.

2. P. Y. Hsiao, C. H. Chen, S. S. Chou, L. T. Li, and S. J. Chen, A parameterizable dig ital-appro ximated 2D Gaussian smoothing filter for edge detection in noisy image, in IEEE Inter. Sy mp. Circuits and System, Island of Kos, Greece, 2006, pp. 3189-3192.

3. F. Yan, X. Shao, G. Li, Z. Sun, and Z. Yang, Edge detection of tank level IR imaging based on the auto – adaptive double-threshold canny operator, Intell. Inform. Technology Applicat. Research Assoc., vol. 3, pp. 366 – 370, Dec. 2008.

4. R. O. Duda and P. E. Hart, Use of the hough transformation to detect lines and curves in pictures, Commun. the ACM, vol. 15, pp. 11-15, Jan. 1972.

5. C. Sun and P. Va llotton, Fast linear feature detection using multiple d irectional non ma ximu m suppression, in Proc. Int. Conf. Pattern Recognition, Hong Kong, China, 2006, pp. 288-291.

6. Yu , Wing Hong W, Memo ry- Efficient Circ le And Ellipse Detection Algorithm in Digita l Images Vo l. 0- 7803-2559-1/95.

7. G. M . Schuster and A. K. Katsaggelos, Robust circle detection using a weighted MSE estimator, in Proc. Inter. Conf. Image Processing, Singapore, 2004, pp. 2111- 2114.

8. Jianping Wu, Jinxiang Li, Changshui xiao, Fangyong Tan, Ca idong Gu, Real-time Robust Algorithm for Circ le Object DetectionDept.Co mputer Eng., Suzhou vocational University, Suzhou Jiangsu, 215104, P.R.China.

9. Sabina Priyadarshini and Gadadhar Sahoo , A New Edge Detection Method based on Additions and Div isions, Department of Information Technology Birla Institute of Technology Mesra, Ranchi, International Journal of Co mputer Applicat ions (0975 8887) Vo lu me 9 No.10, Nove mber 2010.

10. Teh-Chuan Chen and Kuo-Liang Chung1, An Efficient Randomized Algorith m for Detecting Circ les, Co mputer Vision and Image Understanding 83, 172 191 (2001).