Iterative circle fitting based on circular attracting factor  

作　　者：王恒升 张强 王福亮 

机构地区：[1]College of Mechanical and Electrical Engineering,Central South University [2]State Key Laboratory for High Performance Complex Manufacturing (Central South University)

出　　处：《Journal of Central South University》2013年第10期2663-2675,共13页中南大学学报（英文版）

基　　金：Project(2013CB035504) supported by the National Basic Research Program of China;Project(2012zzts078) supported by the Fundamental Research Funds for the Central Universities of Central South University,China;Project(2009ZX02038) supported by the National Science and Technology Major Project of the Ministry of Science and Technology of China

摘　　要：An intuitive method for circle fitting is proposed. Assuming an approximate circle(CA,n) for the fitting of some scattered points, it can be imagined that every point would apply a force to CA,n, which all together form an overall effect that "draws" CA,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 CA,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 CA,n for the whole image. All pixels would apply forces to CA,n, and the overall effect of forces would be equivalent to a force from the centroid of pixels to CA,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 CA,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.An intuitive method for circle fitting is proposed. Assuming an approximate circle(CA,n) for the fitting of some scattered points, it can be imagined that every point would apply a force to CA,n, which all together form an overall effect that "draws" CA,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 CA,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 CA,n for the whole image. All pixels would apply forces to CA,n, and the overall effect of forces would be equivalent to a force from the centroid of pixels to CA,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 CA,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.

关 键 词：circle detection circle FITTING GRAYSCALE image ITERATIVE algorithm least squares fitting(LSF) CIRCULAR attracting factor(CAF) BGA inspection 

分 类 号：TP391.7[自动化与计算机技术—计算机应用技术]