A Comparisonal Study on Circle Detection for Real-World Images

 

 

Md. Omar Faruq

Lecturer

Department of Computer Science and Engineering

Bangladesh Army University of Engineering & Technology, Natore, Bangladesh

E-mail: [email protected]

 

Md. Almash Alam

Lecturer

Department of Computer Science and Engineering

Bangladesh Army University of Engineering & Technology, Natore, Bangladesh

E-mail: [email protected]

 

Md. Muktar Hossain

Lecturer

Department of Computer Science and Engineering

Bangladesh Army University of Engineering & Technology, Natore, Bangladesh

E-mail: [email protected]

 

 

Abstract

Real-life objects have different characteristics such as form characteristics, texture characteristics, and color characteristics and so on. The circular objects are the most common shape in our day to day lives and industrial production. So circle detection algorithm is ever ending research today. The most common algorithm is Circular Hough Transform which is used to detect a circle in an image. It is not very robust to noise so a simple approach to modified Circular Hough Transform algorithm is applied to detect the circle from an image. The image is pre-processed by edge detection. A comparison between Circular Hough Transform and modified Circular Hough Transform algorithm is presented in this research.

 

Keywords: Circle Detection, Hough Transform, Modified Hough Transform.                                                                                  

 

1. Introduction

The circle is one of the most common shapes in our daily life, and indeed the universe. Planets, the movement of the planets, natural cycles, and natural shapes there are circles everywhere. The circle is one of the most complex shapes, and indeed the most difficult for a man to create, yet nature manages to do it perfectly. The centers of flowers, eyes, and many more things are circular and we see them in our everyday life. Detection of circles is very important for us. Usually, detect the object by detecting the object characteristics in the machine vision field. For these reasons, circle detection is an ever ending research application in the real world.Each circle detection should be accurate. The object including circle characteristics exist widely in our daily lives and industrial production, such as iris of eye automatic detection in face recognition, the inhibition halos of antibacterial activity detection (Silveira, 2004) in food industry, the camera calibration in optical study (Jiang & Quan, 2005) concentric circles precise identify of printed circuit board (PCB) round hole photoelectric image i. e. reflector in industrial production (Qiao et al., 2010) concentric circles ring recognition of targeting system (Wang et al., 2008) and PET bottle of online inspection in blowing machines and beverage packaging industry and so on, are all need to use concentric circles detection technology. The circular shape when detected perfectly then recognition for iris of the eye in identifies the purpose, people counting, industrial production, etc. The goal of this thesis to find the circle or a set of circles includes its radius and center from an image.

 

2. Literature Review

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

Image Compression, Image Enhancement, and Restoration, Image Segmentation (Gonzalez et al., 2005).

Image Compression: Image compression means reducing the amount of data required to represent an image. This technique is used for converting an image to a discrete signal for computer processing and compressing it to economize on storage capacity or communication bandwidth for transmitting purpose.

Image Enhancement and Restoration: Whenever an image is converted from one form to another, such as digitizing, transmitting, scanning, etc, some form of degradation occurs at the output. Improvement 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 human viewing. Removing blurring and noise, increasing contrast and revealing details are examples of enhancement operations. The image signals are sometimes degraded by noise, low contrast or blurring. To obtain the original image or to improve it for analysis purposes, image enhancement, restoration or reconstruction techniques are used depending on the objective.

Image Segmentation: Segmentation subdivides an image into its constituent regions and objects. When images taken by different sensors or at different times are to be compared, we use matching or registration techniques. This analysis includes segmentation of an image, measuring the properties of different parts and obtaining a relationship between the parts and comparing. The resulting descriptions are examined using certain models. The ultimate goal of the above techniques is to help an observer translate the contents of an image into useful information.

Edge detection is part of image segmentation. Edge detection is very useful in some contexts. Edge characterizes object boundaries and is, therefore, useful for segmentation, registration, and identification of objects in scenes. The output of edge detection should be an edge image, in which the value of each pixel reflects how strong the corresponding pixel in the original image meets the requirements of being an edge pixel. Many edge detectors have been proposed, such as Sobel, Robert, and Prewitt.

 

3. Research Methodology

3.1 Circular Hough Transform

Input Image


The Circle Hough Transform (CHT) is a feature extraction technique for detecting circle. Detecting circles in an image are one of the problems that are discussed in this paper. Many algorithms, such as Linear Square Method (Hsiao et al., 2006), Hough Transform, and Canny Edge detection Algorithms have been proposed to detect circles. These algorithms detect circles from the edge detected images. Among these algorithms, Early Circular Hough Transform has been widely successful in meeting the real-time requirement of being able to detect the circles in noisy environments. Modified Circular Hough Transform discussed in the next section. And also discussed Modified CHT is the best algorithm to detect circle as compared to Circular Hough Transform. Hough Transform was introduced by Paul Hough in 1962 and patented by IBM. In 1972 (Shapiro & George, 2002) modified Hough Transform, which is used universally today.

Parameter Representation

Edge Detected


         

Output Circle Detected Image

                     

Accumulator

Figure 1. Circular Hough Transform Algorithm (Nitasha, et al., 2012)

 

The equation 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 center of the circle in the direction x & y respectively and r is the radius.

 

The parameter representation of the circle is:

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

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

Thus the parameter space for a circle will belong to R3. As the number of parameters needed to describe the shape increase as well as the dimension of the parameter space R increase so do the complexity of the Hough Transform.

4. Accumulator

In this way, we sweep over the energy edge point in the input image drawing circle with the desired circle with desired radii and incrementing the value in our accumulator. When every edge point and every desired radius is used we can turn our attention to accumulator ill now contain numbers corresponding to the number of circles passing through the individual coordinate. Thus the highest number corresponds to the circle of the circle in the image.


Figure 3. Coins image input of CHT algorithm (Virtanen, 2019)

 

 

Figure 4: Circle detected image

Table1: Data points of the detected circle


Since the parameter space of CHT is three dimensional, it may require lots of storage and computation. Also, CHT is not very robust to noise. Circle detected but redundant and spurious circles frequently occur.

 

5. Modified CHT Algorithm

The first stage noise is removed from the image by using a Gaussian filter. After that Edge strength and Edge Direction is found out at each pixel by using Sobel operator. Then non-maximum suppression. It is a process for marking all pixels whose intensity is not maximal as zero within a certain local neighborhood.


 

Multiple Circle’s images with Different Radius

Figure 5. Bicycle image

Figure 6. Circle detected image

 


Table 2. Data of the above result

 


Here seen the result with Long Radius

 

Figure 7. Circle image with long radius


Figure 8. Circle detected image Table 3. Represents data of the above result

 

6. Comparison between CHT and Modified CHT

The CHT algorithm is implemented in the previous section where circle detected but redundant and spurious circles frequently occur and also CHT is not very robust to noise. In modified CHT algorithm, multiple circles with different radius and circle with long radius are detected in this section in Figure 4.2  and Figure 4.4 were redundant and spurious circles are not occurring and the modified circular hough transform algorithm needs less storage and computation.

Table 4. Comparison between CHT and Modified CHT Algorithm

 

Parameters

CHT Algorithm

Modified CHT Algorithm

Robustness

Not very robust to noise

Very robust to noise

Redundant and Spurious

Circles

Frequently occurs

Not occur

Processing Time

More time required

Ten timeless than CHT

 

7. Conclusion

The Hough transform has attracted a lot of research efforts over the decades. The circle is one of the most complex shapes, and indeed the most difficult for a man to create, yet nature manages to do it perfectly. For these reasons, it is often non-trivial to group the extracted edge features to an appropriate set of circles. Each circle detection should be accurate. The main motivations behind such interest are the noise immunity, the ability to deal with occlusion, and the expandability of the transform. Many variations of it have evolved. The comparison between CHT and Modified CHT performed successfully. The modified circular hough transform algorithm requires less storage and computation.

 

8. Acknowledgment

Authors are sincerely grateful Department of Computer Science & Engineering, Bangladesh Army University of Engineering & Technology.

 

9. References

Gonzalez, R. C., Woods, R. E., & Eddins, S. L. (2005). Digital image processing using MATLAB (Beijing: Publishing House of Electronics Industry): p252.

Hsiao, P. Y., Chen, C. H., Chou, S. S., Li, L. T., & Chen, S. J. (2006, May). A parameterizable digital-approximated 2D Gaussian smoothing filter for edge detection in noisy image. In 2006 IEEE International Symposium on Circuits and Systems (pp. 4-pp). IEEE.

Jiang, G., & Quan, L. (2005, October). Detection of concentric circles for camera calibration. In Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 (Vol. 1, pp. 333-340). IEEE.

Nitasha, S. S., Sharma, R., & Sharma, R. (2012). Comparison between circular Hough transform and modified cCanny edge detection algorithm for circle detection. Int J Eng Res Technol (IJERT), 1(3), 15.

Qiao, N. S., Ye, Y. T., Mo, C. H., Wu, Y. F., & Liu, L. (2010). Method for the detection of concentric circles of photoelectric image of circular hole in printed circuit board. Acta Optica Sinica, 30(1), 75-78.

Silveira, M. (2004, May). Antibacterial activity detection and evaluation based on the detection of multiple concentric circles with the Hough transform. In First Canadian Conference on Computer and Robot Vision, 2004. Proceedings. (pp. 329-335). IEEE.

Shapiro, L., & George, C. (2002). An Introduction of Computer Vision. Prentice-Hall, Inc.

Virtanen,M.(2019).Myymälän aktiivinen varastosaldojen seuranta. Retrieved from https://www.cis.rit.edu/class/simg782.old/talkHough/HoughLecCircles.html

Wang, H., Niu, J., Liu, S., & Wang, D. (2008). A concentric circles adaptive detection algorithm of measured imagery target surface. Acta Photonica Sinica, 37(10), 2094-2098.

 

 

 

Copyrights

Copyright for this article is retained by the author(s), with first publication rights granted to the journal. This is an open-access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).