Shuai Liguo (帥立國), Chen Huiling

(*School of Mechanical and Electrical Engineering, Henan Institute of Science and Technology, Xinxiang 453003, P.R.China) (**School of Mechanical Engineering, Southeast University, Nanjing 211189, P.R.China)

Study on circle detection algorithm based on data dispersion①

Shuai Liguo (帥立國)②, Chen Huiling**

(*School of Mechanical and Electrical Engineering, Henan Institute of Science and Technology, Xinxiang 453003, P.R.China) (**School of Mechanical Engineering, Southeast University, Nanjing 211189, P.R.China)

To reduce time-consuming, a new algorithm is proposed for circle detection based on the theory of data dispersion. The center coordinates and radius can be detected with the following steps in this algorithm precisely and quickly. Firstly, image processing is needed to extract the boundary of the primary image, which is almost like a circle in shape, and after that, the original circle is reduced to a single-pixel width circle by image processing. Secondly, the center coordinates are calculated by three selected points on the circle. There might be a deviation between the calculated center and real center. Thirdly, a square area is determined for the center coordinates computing with an experimental range and each pixel inside the square is a potential center. Fourthly, the center is computed with distance criterion and the center coordinate is determined when the variance reaches the minimum. Lastly, the radius is equal to the means of the distance vector with minimum variance. Experiments are conducted and the results show that the proposed algorithm gets the same accuracy and better real-time performance in comparison with traditional Hough transform.

circle detection, center coordinates, dispersion

0 Introduction

The growing development of artificial intelligence has urgent demands on accuracy and real-time performance in image identification field. Artificial intelligence is a new technology to mimic human intelligence, which can be widely used in robots, natural language processing, image identification, expert system, etc., among which, the image identification is very important which can simulate human eyes to draw out meaningful visual information for the whole artificial intelligence system. There are a lot of circular objects in military, biological field and industrial site such as cells, snap rings, eyes, balls, etc. How to detect out the position and the size of the circle precisely and quickly with image identification is an indispensable part of artificial intelligence.

The traditional Hough transform was put forward by Hough in 1962, which is regarded as an effective method to identify arbitrary analytical curves based on an edge detection algorithm[1]. Traditional Hough transform has good robustness to the random noise and it is capable of detecting incomplete analytical curves. The creation of Hough transform is that it converts global detection into local peak detection in the parameter space[2]. The disadvantage of the traditional Hough transform is that the mapping of image space to the parameters space is a one-to-many transform, and results in a large memory usage with bad real-time performance.

Lots of methods have been proposed to improve the traditional Hough transform, which mainly focus on decreasing the dimension of parameters space and avoiding a large number of pixels involved. In 1993, Xu, et al. proposed the randomized Hough transform (RHT)[3], which selected three different points on the circle arbitrarily to calculate the center and radius of circle, and then the voting result of the distances between the center and each point on the circle was used as criterion; RHT reduces the amount of calculation and memory usage, and its shortage is too sensitive to the distortion of circle, which leads to an invalid voting result. In 2005, Zhang, et al. proposed a method to detect circle for simple image identification[4], the chain code of the image is used to calculate the circularity of image and the radius of circle if without intersection. In 2008, Shang, et al. proposed a method for circle detection based on right triangles inscribed in a circle[5], which extracted constructs array storage space based on the positon of valid pixels to avoid searching triangles in image space but compressed arrays, the translation of calculation from circle parameters to triangles avoided repeated arithmetic operations and reduced the running time, and the accuracy of the detection result is less than pixel. In 2015, Cai, et al. proposed a fast circle detection method based on region-growing of gradient and histogram of Euclidean distance[6], which computed the gradient module and direction of pixels to get support regions, and then a square fitting area was determined to get a three dimensional accumulator and a histogram to display the voting result.

This paper proposes a circle detection algorithm based on data dispersion, which uses image processing to acquire a single-pixel width circle, determine the feature region according to the characteristics of circle, builds the distance criterion and picks up the real center using data dispersion. Once the real center of circle is found, the radius can be figured out correspondingly.

1 Theory of detection algorithms of circles

1.1 Traditional Hough transform

The traditional Hough transform is to map the edge points to the parameter space, and then accumulate all the coordinate points in the parameter space,

where the point with the maximum accumulated value corresponds to the center of the circle[7,8].

The equation of circle in Cartesian coordinate system is

(1)

Each point (xi, yi) in image space corresponds to a cone in parameter space, and the equation of the cone is

(a-xi)2+(b-yi)2=r2

(2)

A(x1, y1), B(x2, y2), C(x3, y3) and D(x4, y4) are four points on the circle with center (a0, b0) and radius r0, their corresponding cones intersect at (a0, b0, r0) in parameter space as shown in Fig.1.

Fig.1 Theory of circle detection using Hough transform

1.2 Algorithm based on data dispersion

1.2.1 Procedure

Fig.2 shows the procedure of the algorithm proposed.

Fig.2 Procedure of the new algorithm

(1) Image preprocessing is to get the circle with single-pixel width. Circle with multi pixels width has no obvious influence on the accuracy of detection and it brings unnecessary calculation and increases the running time of the algorithm, which will weaken the real-time performance of system. Therefore, the effect of image preprocessing will directly influence the performance of the algorithm.

(2) A theoretical center O′ is calculated with three selected points on the circle, these three points separate the circle with single-pixel width into four part with approximate distance. Then a square area is determined with an experimental range, O′ is the center of this area, each pixel inside this square is a potential center of the circle.

(3) Calculation of feature means calculating the distance between each potential center and each pixel on the circle.

(4) For all the points on the same circle have the equidistant distance to the center of the circle, in other words, the variance of the distances between the center and points on the circle is zero, and the radius equals to the average distance. According to this theory, the potential center corresponding to the minimum variance of the distance vector is the real center and the means of this distance vector is the real radius[9,10].

1.2.2 Theory of the algorithm

There are several parameters that are used to describe the dispersion of data, for instance, range, interquartile range (IQR), variance, standard deviation, mean deviation, coefficient of variation (CV). The statistic related to this new detection algorithm of circle is variance.

A set is formed by the coordinates of the pixels on the circle, {(x1, y1),…,(xk, yk),…,(xN, yN)}.The theoretical center O′(a0, b0) is calculated by three arbitrary points (Point 1, Point 2, and Point 3) in this set. According to experimental δ, a square area is determined, (a0-δ≤a≤a0+δ, b0-δ≤b≤b0+δ), and each pixel inside this square is a potential center. Fig.3 shows the theory of this new algorithm, (2δ+1) is the number of the pixels.

Fig.3 Theory of circle detection using new algorithm

For two points (ai, bj) and (xk, yk), (ai, bj)∈(a0-δ≤a≤a0+δ, b0-δ≤b≤b0+δ) and (xk, yk)∈{(x1, y1),…,(xk, yk),…,(xN, yN)}, the distance between this two points is D(i, j, k)[6]

(3)

1≤i≤2δ+1, 1≤j≤2δ+1， 1≤k≤N， N is the number of the pixels on the circle.

The three-dimensional matrix D can be written in a two-dimensional form.

(4)

Element Vijis a vector and it represents the distances between the theoretical center (ai, bj) and all the pixels on the circle.

(5)

2 Analysis and experiment

Accuracy and real-time performance are two key index of algorithm. This paper analyzes the calculation to compare the real-time performance of this proposed algorithm with the traditional Hough transform, and compares the accuracy of these two algorithms by an experiment.

2.1 Analysis of real-time performance

For the detection of circle whose center and radius are unknown, firstly, traditional Hough transform needs two loops to find the circle, the number of involved pixels is H×W, H is the height of the image, W is the width of the image. Secondly, traverse should be done on the range of radius, (r1, rn), which needs one loop. Thirdly, for ri∈(r1, rn), each pixel on the circle in the image has a corresponding circle in the parameters space; for each pixel, it needs two loops in the parameters space, the number of involved pixels is 2ri×2ri, for all the pixels on the circle, the number of involved pixels is 2ri×2ri×N, where N is the number of the pixels on the circle. In conclusion, traditional Hough transform needs five loops when detecting circle.

The algorithm proposed in this paper needs two loops to find the circle, the number of involved pixels is H×W, H is the height of the figure, W is the width of the figure. Secondly, the distance between each potential and each pixel on the circle is calculated. Three loops are needed in this procedure, the number of pixels involved is L×L×N, and L is width of the square that consists of potential centers, L is far less than ri.

The number of involved pixels suggests that the algorithm proposed has better real-time performance than traditional Hough transform.

2.2 Comparison of accuracy

An example is designed to verify the accuracy of the new algorithm compared with the traditional Hough transform.

2.2.1 Image processing

Image processing is used to acquire the circle with the single-pixel width, for different situation, the procedure of image processing is different. Fig.4 shows the image processing of the example.

Fig.4 Image processing

Fig.4(a) is the original image; Fig.4(b) shows the result of gray processing; Fig.4(c) is the binary image of the gray image; Fig.4(d) is the result of morphological processing; Fig.4(e) shows the skeleton extraction of the circle; Fig.4(f) shows the result of deburring and this is the result needed.

(1) Gray processing. Gray processing is used to delete useless information of colorful image.

(2) Binarization. For the detection of circle, binarization is used to extract the target from the background.

(3) Morphological processing. The original image contained image noise, and after procedures (1) and (2), the image noise is converted to spots like target, morphological processing is used to remove these spots.

(4) Skeleton extraction. The purpose of image processing is to get the circle with single-pixel width; skeleton extraction is used to get the skeleton of the circle.

(5) Deburring. The acquired skeleton of circle has some spurs, deburring is used to remove these spurs and get the circle with single-pixel width.

2.2.2 Experiment and analysis

Traditional Hough transform has very high accuracy in the detection of circle. This paper analyzes the accuracy of the proposed algorithm by the comparison with traditional Hough transform. These two methods are developed in Visual Studio software as shown in Fig.5. Two different images are experimented to detect the circles for a ring and a disk.

From the figure it can be seen that the traditional Hough algorithm and LiSan algorithm proposed can extract the edges of the two shapes out and present most consistency in coordinate of the center and the size of the radius, while the LiSan algorithm is superior to Hough transform in time-cost of detection. Although LiSan algorithm takes 15ms in detecting the circle of the ring, only 1ms faster than that of Hough transform, the new algorithm takes almost 1/14 time in detecting the disk as shown in Fig.5(b). From the above it can be seen that, the proposed algorithm has more advantages in detecting rate than Hough transform with the same detecting accuracy.

Fig.5 Comparison experiment between Hough transform and the new algorithm

3 Conclusions

Real-time performance and accuracy are two critical index of the recognition system. Traditional Hough transform has high accuracy, but it is time-consuming and hard to reach a better real-time performance. This paper proposes a new detection algorithm of circle based on data dispersion. Compared with the traditional Hough transform, the new algorithm can avoid the mapping of image space to parameter space and reduce the number of pixels involved, in addition, the new algorithm has good robustness and is capable of detecting incomplete curve as well. Analysis and experiment suggest that the new algorithm has good accuracy and a better real-time performance.

On cases of two or more circles in the image, some other methods should be used to separate these circles, and then the parameters of these circles can be calculated out separately with the new algorithm.

[ 1] Duda R O, Hart P E. Use of the Hough transformation to detect lines and curves in pictures. Communications of the ACM, 1972, 15(1):12-15

[ 2] Xia L, Cai C, Zhou C P, et al. New fast algorithm of Hough transform detection of circles. Application Research of computers, 2007, 24(10):197-199

[ 3] Xu L, Ja E. Randomize Hough transform (RHT): basic mechanisms, algorithms, and computational complexities. CVGIP Image Understanding, 1993, 57(2):131-154

[ 4] Zhang J E, Cao C X, Jin Q. Algorithm of circle analyse in image processing. Journal of Chongqing University (Natural Science Edition), 2005, 28(11): 43-45

[ 5] Shang F, Wang F G, Tian D, et al. A method for circle detection based on right triangles inscribed in a circle. Acta Optica Sinica, 2008, 28(4): 739-743

[ 6] Cai J, Huang P F, Zhang B. Fast circle detector based on region-growing of gradient and histogram of Euclidean distance. Acta Optica Sinica, 2015, 35(3): 185-194

[ 7] Hough P V C. Method and means for recognizing complex patterns. US patent: 3069654, 1962

[ 8] Zhu X L, Gao C H, He B W, et al. An improved method of Hough transform circle detection based on the midpoint circle-producing algorithm. Journal of Engineering Graphics, 2010, 31(6):29-33

[ 9] Yang N, Chen H J, Li Z L, et al. A new algorithm of the circle detection in a complex background image. Journal of Beijing Jiaotong University, 2010, 34(2): 67-70

[10] Yang F. Digital Image Processing and Analysis. Beijing: Beijing University of Aeronautics and Astronautics Press, 2007. 271-274

10.3772/j.issn.1006-6748.2017.04.008

①Supported by the National Natural Science Foundation of China (No. 61175069) and the Prospective Project of Jiangsu Province for Joint Research (No. SBY201320601).

②To whom correspondence should be addressed. E-mail: liguo.shuai@126.com

on Aug. 22， 2016*, Wei Youying**

the Ph.D degree and M.S. degree from Southeast University in 2001 and 1998 respectively. He also received his B.S. degree from Xi’an Jiaotong University in 1991. His research interests include smart robots, nondestructive testing, tactile display and virtual reality.