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)
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.
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.
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.
Figure
5.
Bicycle image
Figure
6.
Circle detected image
Table
2.
Data of the above result
Figure
7.
Circle image with long radius
Figure 8. Circle detected image Table 3.
Represents data of
the above result
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 |
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.
Authors
are sincerely grateful Department of Computer Science & Engineering,
Bangladesh Army University of Engineering & Technology.
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/).