THE TWO STAGES CIRCLE FITTING METHOD

Nicolae URSU-FISCHER, Diana Ioana POPESCU, Iuliana Fabiola MOHOLEA

Abstract


The problem of circle fitting (and also of other conics, especially of ellipse) to a number of given points in plane is one of the great importance in computer graphics, image processing, quality control, metrology and other fields of science and engineering. Even if it is necessary to fit an entire circle or just an arc, the same methods are used. The solving of linear and nonlinear algebraic equations, the extensive use of well-known method of least-squares (for the first time discovered by Legendre [10]), the error analysis, are the main mathematical tools used in these procedures for perform the accurate fit of the points with a circle, if this is the demand. The first part of the paper summarizes the existing methods of algebraic and geometric fit, using a circle: the methods of Kåsa [8], Pratt [13] and Taubin [17], having in common the use of least-squares method. With these methods, the coordinates of the centre of the circle and its radius result simultaneously, after solving the system of nonlinear equations. The authors present a new original method for solving the same problem: the coordinates of the centre of the circle are obtained first as a consequence of approximate solving of an over-determined system of linear equations and, in the second stage, is determined the value of the radius by minimizing the objective function. The paper also contains two examples of fitting (with a complete circle and with an arc) solved with the new-imaged procedure.


Key words: Least-square method, circle fitting, algebraic and geometric fitting, Newton iterative method, nonlinear equations.


Full Text:

PDF

References


Ahn, S. J., Rauh, W., Oberdorfer, B., Least squares fitting of circle and ellipse, Int. Journal of Pattern Recognition and Artificial Intelligence, vol. 13, no. 7, 1999, pp. 987-996.

Al-Sharadqah, A., Chernov, N., Error analysis for circle fitting algorithms, Electronic Journal of Statistics, 2009, Vol. 3, pp. 886-911.

Chernov, N., Lesort, C., Statistical efficiency of curve fitting algorithms, Comp. Stat. Data Anal., 2004, Vol. 47, pp. 713–728.

Chernov, N., Lesort, C., Least squares fitting of circles, J. of Math. Imag. Vision, 2005, Vol. 23, pp. 239–251.

Coope, I.D., Circle fitting by linear and nonlinear least squares, Journal of Optimization Theory and Applications, 1993, Vol. 76, No. 2, pp. 381-388.

Gander, W., Golub, G. H., Strebel, R., Least-squares fitting of circles and ellipses, BIT 34, 1994, pp. 558-578.

Gluchshenko, Olga N., Annulus and center location problems, PhD Thesis, Technische Universitat Kaiserlautern, 2008, 101 pp.

Kåsa, I., A circle fitting procedure and its error analysis, IEEE Trans. Instrumentation and Measurement, 1976, Vol. 25, pp. 8-14.

Kim, E., Haseyama, M., Kitajima, H., A new fast and robust circle extraction algorithm, The 15th International Conference on Vision Interface, May 27-29, 2002, Calgary, Canada, 6 pp., http://www. cipprs.org/vi2002/pdf/s8-6.pdf

Legendre, A. M., Méthode des moindres carrés, pour trouver le milieu le plus probable entre les résultats de différentes observations, Paris, Mem. Inst. Fr., 1810, pp. 149-154.

Moura, L., Kitney, R., A direct method for least-squares circle fitting, Computer Physics Communications, 1991, Vol. 64, pp. 57-63.

Pearson, K., On lines and planes of closest fit to systems of points in space, The Philosophical Magazine, 1901, Ser. 6, 2(11), pp. 559-572.

Pratt, V., Direct least-squares fitting of algebraic surfaces, Computer Graphics, 1987, Vol. 21, pp. 145–152.

Press, W. H. a.o., Numerical Recipes in C++. The Art of Scientific Computing, Cambridge University Press, 2003, 1002 pp., ISBN 0-521-75033-4

Späth, H., Least-squares fitting by circles, Computing, 1996, Vol. 57, pp. 179–185.

Stache, N., Zimmer, H., Robust circle fitting in industrial vision for process control of laser welding, Proceedings of the 11th International Conference on Electrical Engineering, Prague, 2007.

Taubin, G., Estimation of planar curves, surfaces and nonplanar space curves defined by implicit equations, with applications to edge and range image segmentation, IEEE Trans. Pattern Analysis Machine Intelligence, 1991, Vol. 13, No. 11, pp. 1115–1138.

Ursu-Fischer, N., Ursu, M., Numerical Methods in Engineering and Programs in C/C++, Vol. I, (in Romanian), Casa Cărţii de Ştiinţă, Cluj-Napoca, 2000, 282 pp.

Ursu-Fischer, N., Ursu, M., A new and efficient method to perform the circle fitting, Acta Technica Napocensis, Series: Applied Mathematics and Mechanics, 2004, No. 47, Vol. III, pp. 21-30, ISSN 1221-5872

Ursu-Fischer, N., Ursu, M., Numerical Methods in Engineering (in Romanian), Casa Cărţii de Ştiinţă, Cluj-Napoca, 2019, 836 pp. (in print)


Refbacks

  • There are currently no refbacks.


JOURNAL INDEXED IN :