) of detected circle. R is the pre-input radius and r is the radius of detected circle. PN is the number of pixels on the contour of detected circle. C is the circularity of detected circle. Avg T (ms) represents the average running time in millisecond. T c c is the threshold of circularity.

4.1. Locating Mark with Standard RCD Algorithm

In this part the marks will be detected by using standard RCD algorithm. As shown in Figure 5 there are many correct and incorrect circles in images. In Figure 5(c) the true mark circle is not included in the detected possible circles. There is no way to discard the incorrect circles and find the true mark. According to the threshold T c , there are twenty possible detected circles at most, which are drawn in Figure 5. In Tables 2-5 only ten possible circles are described.

(a) (b) (c) (d)

Figure 5. Locating results using standard RCD algorithm. (a)-(c) The detected results, obtained from Figures 4(a)-(c); (d) The result obtained from Figure 4(d).

Table 2. Ten results shown in Figure 5(a).

Table 3. Ten results shown in Figure 5(b).

Table 4. Ten results shown in Figure 5(c).

Table 5. Ten results shown in Figure 5(d).

4.2. Locating Mark with Improved RCD Algorithm

In the following experiments, the fiducial marks will be detected by our improved RCD algorithm and corresponding circularity. As illustrated in Figure 6, the left four images (a)-(d) denote the results, which are obtained without calculating minimal circularity. Because of unsharpness of edge, the correct and bias circles are detected, which have similar radius and position. It is difficult to determine the best true circle without additional decision condition. After calculating the minimal circularity, the true marks are located in the right four images (e)-(h). The detected possible circles are shown in Tables 6-9. Compared to the former standard RCD algorithm, the number of possible circles is fewer and the results are close to the true mark. By calculating minimal circularity, in Table 6 the true circle with center pixel (71.500, 80.500) and radius 26.163 pixels is detected. In Table 7 the true circle with center pixel (71.369, 81.622) and radius 27.132 pixels is detected. In Table 8 the true circle with center pixel (75.601, 81.013) and

(a) (b) (c) (d) (e) (f) (g) (h)

Figure 6. Results obtained by using our improved RCD algorithm and circularity. (a)-(d) Results obtained without calculating minimal circularity; (e)-(h) Results obtained by calculating the minimal circularity.

Table 6. Results shown in Figure 6(a).

Table 7. Results shown in Figure 6(b).

Table 8. Results shown in Figure 6(c).

Table 9. Results shown in Figure 6(d).

Table 10. Time performance comparison between standard RCD and the improved RCD in terms of milliseconds.

radius 26.951 pixels is detected. In Table 9 the true circle with center pixel (114.992, 108.471) and radius 34.629 pixels is detected.

4.3. Comparing the Execution-Time

In order to compare the execution-time, all concerned experiments are performed on the Intel i5-5200U CPU with 2.20 GHz and 8 GB RAM. The adopted operating system is MS-Windows 7 and the programming environment is VS2010. In order to accurately evaluate the execution-time, we run each image 100 times and calculate the average time in Table 10. For locating mark in small images, the execution-time is almost the same for both algorithms. The time will be significantly reduced, when the mark is detected in a larger and complex image.

5. Conclusions

This paper has presented the proposed improved RCD strategy to improve the performance of execution-time and the accuracy of detection. The refined method can suppress the interference between different objects significantly. After calculating minimal circularity, the true mark will be located efficiently and accurately. The experimental results demonstrate that the proposed improved RCD improves significantly the accuracy of detection. Experimental results also demonstrate that the proposed algorithm provides a considerable execution-time improvement. The algorithm has significant execution-time superiority in large and complex image.

At the current stage, the quality of the image, such as the stability of the light source, the degree of image damage, clarity, etc., has a great influence on the calculation results. In the future, some normalization methods will be studied to reduce these interferences, such as combining with pattern recognition.


This article is supported by Science and Technology Project of Fujian Provincial Department of Education under contract JAT170917 and Youth Science and Research Foundation of Chengyi College Jimei University under contract C16005.

Cite this paper
Liu​, J. and Fan, Q. (2019) An Improved Randomized Circle Detection Algorithm Using in Printed Circuit Board Locating Mark. Applied Mathematics, 10, 848-861. doi: 10.4236/am.2019.1010061.

[1]   Gonzalez, R.C. and Woods, R.E. (1992) Digital Image Processing. Addison Wesley, New York.

[2]   Forsyth, D.A. (2002) Computer Vision: A Modern Approach. Prentice-Hall, New Jersey.

[3]   Leavers, V.F. (1993) Survey: Which Hough Transform. CVGIP: Image Understanding, 58, 250-264.

[4]   Duda, R.O. and Hart, P.E. (1972) Use of the Hough Transformation to Detect Lines and Curves in Pictures. Communications of the ACM, 15, 11-15.

[5]   Xu, L. and Oja, E. (1993) Randomized Hough Transform (RHT): Basic Mechanisms, Algorithms, and Computational Complexities. CVGIP: Image Understanding, 57, 131-154.

[6]   Chen, T.C. and Chung, K.L. (2001) An Efficient Randomized Algorithm for Detecting Circles. Computer Vision and Image Understanding, 83, 172-191.

[7]   Fischer, M.A. and Bolles, R.C. (1981) Random Sample Consensus: A Paradigm to Model Fitting with Applications to Image Analysis and Automated Cartography. Communications of the ACM, 24, 381-395.

[8]   Jia, L.Q., Peng, C.Z., Liu, H.M. and Wang, Z.H. (2011) A Fast Randomized Circle Detection Algorithm. International Congress on Image and Signal Processing, 4, 835-838.

[9]   Gomes, J. and Velho, L. (1997) Image Processing for Computer Graphics. Springer-Verlag, New York.

[10]   Gonzalez, R.C. and Woods, R.E. (2008) Digital Image Processing. Pearson Prentice Hall, New Jersey.

[11]   Davies, E.R. (2005) Machine Vision: Theory Algorithms Practicalities. Morgan Kaufmann, San Francisco.

[12]   Fan, Y. (2007) Digital Image Processing and Analysis. Beijing University of Aeronautics and Astronautics, Beijing.