Iterative circle fitting based on circular attracting factor

WANG Heng-sheng(王恒升)^{1, 2}, ZHANG Qiang(张强)¹, WANG Fu-liang(王福亮)^{1, 2}

(1. College of Mechanical and Electrical Engineering, Central South University, Changsha 410083, China;
2. State Key Laboratory for High Performance Complex Manufacturing (Central South University),
Changsha 410083, China)

Abstract:An intuitive method for circle fitting is proposed. Assuming an approximate circle (C_A,n) for the fitting of some scattered points, it can be imagined that every point would apply a force to C_A,n, which all together form an overall effect that “draws” C_A,n towards best fitting to the group of points. The basic element of the force is called circular attracting factor (CAF) which is defined as a real scalar in a radial direction of C_A,n. An iterative algorithm based on this idea is proposed, and the convergence and accuracy are analyzed. The algorithm converges uniformly which is proved by the analysis of Lyapunov function, and the accuracy of the algorithm is in accord with that of geometric least squares of circle fitting. The algorithm is adopted to circle detection in grayscale images, in which the transferring to binary images is not required, and thus the algorithm is less sensitive to lightening and background noise. The main point for the adaption is the calculation of CAF which is extended in radial directions of C_A,n for the whole image. All pixels would apply forces to C_A,n, and the overall effect of forces would be equivalent to a force from the centroid of pixels to C_A,n. The forces from would-be edge pixels would overweigh that from noisy pixels, so the following approximate circle would be of better fitting. To reduce the amount of calculation, pixels are only used in an annular area including the boundary of C_A,n just in between for the calculation of CAF. Examples are given, showing the process of circle fitting of scattered points around a circle from an initial assuming circle, comparing the fitting results for scattered points from some related literature, applying the method proposed for circular edge detection in grayscale images with noise, and/or with only partial arc of a circle, and for circle detection in BGA inspection.

Key words:circle detection; circle fitting; grayscale image; iterative algorithm; least squares fitting (LSF); circular attracting factor (CAF); BGA inspection