Skip to main content

Advertisement

Log in

Least Squares Fitting of Circles

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

Fitting standard shapes or curves to incomplete data (which represent only a small part of the curve) is a notoriously difficult problem. Even if the curve is quite simple, such as an ellipse or a circle, it is hard to reconstruct it from noisy data sampled along a short arc. Here we study the least squares fit (LSF) of circular arcs to incomplete scattered data. We analyze theoretical aspects of the problem and reveal the cause of unstable behavior of conventional algorithms. We also find a remedy that allows us to build another algorithm that accurately fits circles to data sampled along arbitrarily short arcs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. G.J. Agin, “Fitting Ellipses and General Second-Order Curves,” Carnegi Mellon University, Robotics Institute, Technical Report 81–5, 1981.

  2. S.J. Ahn, W. Rauh, and H.J. Warnecke, “Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola,” Pattern Recog., Vol. 34, pp. 2283–2303, 2001.

    Article  Google Scholar 

  3. M. Berman and D. Culpin, “The statistical behaviour of some least squares estimators of the centre and radius of a circle,” J. R. Statist. Soc. B, Vol. 48, pp. 183–196, 1986.

    Google Scholar 

  4. R.H. Biggerstaff, “Three variations in dental arch form estimated by a quadratic equation,” J. Dental Res., Vol. 51, pp. 1509, 1972.

    Google Scholar 

  5. F.L. Bookstein, “Fitting conic sections to scattered data,” Comp. Graph. Image Proc., Vol. 9, pp. 56–71, 1979.

    Google Scholar 

  6. Y.T. Chan and S.M. Thomas, “CramerRao Lower Bounds for Estimation of a Circular Arc Center and Its Radius,” Graph. Models Image Proc., Vol. 57, pp. 527–532, 1995.

    Article  Google Scholar 

  7. B.B. Chaudhuri and P. Kundu, “Optimum Circular Fit to Weighted Data in Multi-Dimensional Space,” Patt. Recog. Lett., Vol. 14, pp. 1–6, 1993.

    Article  Google Scholar 

  8. N. Chernov and C. Lesort, “Fitting circles and lines by least squares: theory and experiment, preprint,” available at http://www.math.uab.edu/cl/cl1

  9. N. Chernov and C. Lesort, “Statistical efficiency of curve fitting algorithms,” Comput. Statist.&Data Analysis, Vol. 47, pp. 713–728, 2004.

    Google Scholar 

  10. N.I. Chernov and G.A. Ososkov, “Effective algorithms for circle fitting,” Comp. Phys. Comm., Vol. 33, pp. 329–333, 1984.

    Article  Google Scholar 

  11. W. Chojnacki, M.J. Brooks, and A. van den Hengel, “Rationalising the renormalisation method of Kanatani,” J. Math. Imaging&Vision, Vol. 14, pp. 21–38, 2001.

    Google Scholar 

  12. J.F. Crawford, “A non-iterative method for fitting circular arcs to measured points,” Nucl. Instr. Meth., Vol. 211, pp. 223–225, 1983.

    Article  Google Scholar 

  13. P. Delonge, “Computer optimization of Deschamps’ method and error cancellation in reflectometry,” in Proceedings IMEKO-Symp. Microwave Measurement, Budapest, 1972, pp. 117–123.

    Google Scholar 

  14. P.R. Freeman, “Note: Thom’s survey of the Avebury ring,” J. Hist. Astronom., Vol. 8, pp. 134–136, 1977.

    Google Scholar 

  15. W. Gander, G.H. Golub, and R. Strebel, “Least squares fitting of circles and ellipses,” BIT, Vol. 34, pp. 558–578, 1994.

    Article  Google Scholar 

  16. S.H. Joseph, “Unbiased Least-Squares Fitting Of Circular Arcs,” Graph. Models Image Proc., Vol. 56, pp. 424–432, 1994.

    Google Scholar 

  17. K. Kanatani, “Cramer-Rao lower bounds for curve fitting,” Graph. Models Image Proc., Vol. 60, pp. 93–99, 1998.

    Article  Google Scholar 

  18. V. Karimäki, “Effective circle fitting for particle trajectories,” Nucl. Instr. Meth. Phys. Res. A, Vol. 305, pp. 187–191, 1991.

    Google Scholar 

  19. I. Kasa, “A curve fitting procedure and its error analysis,” IEEE Trans. Inst. Meas., Vol. 25, pp. 8–14, 1976.

    Google Scholar 

  20. U.M. Landau, “Estimation of a circular arc center and its radius,” Computer Vision, Graphics and Image Processing, Vol. 38, pp. 317–326, 1987.

    Google Scholar 

  21. Y. Leedan and P. Meer, “Heteroscedastic regression in computer vision: Problems with bilinear constraint,” Intern. J. Comp. Vision, Vol. 37, pp. 127–150, 2000.

    Article  Google Scholar 

  22. K. Levenberg, “A Method for the Solution of Certain Non-linear Problems in Least Squares,” Quart. Appl. Math., Vol. 2, pp. 164–168, 1944.

    Google Scholar 

  23. D. Marquardt, “An Algorithm for Least Squares Estimation of Nonlinear Parameters,” SIAM J. Appl. Math., Vol. 11, pp. 431–441, 1963.

    Article  Google Scholar 

  24. L. Moura and R.I. Kitney, “A direct method for least-squares circle fitting,” Comp. Phys. Comm., Vol. 64, pp. 57–63, 1991.

    Article  Google Scholar 

  25. G.A. Ososkov, “JINR technical report P10-83-187,” Dubna, 1983, pp. 40 (in Russian).

  26. K. Paton, “Conic sections in chromosome analysis,” Pattern Recogn., Vol. 2, pp. 39–51, 1970.

    Article  Google Scholar 

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

    Google Scholar 

  28. S.M. Robinson, “Fitting spheres by the method of least squares,” Commun. Assoc. Comput. Mach., Vol. 4, p. 491, 1961.

    Google Scholar 

  29. P.D. Sampson, “Fitting conic sections to very scattered data: An iterative refinement of the Bookstein algorithm,” Comp. Graphics Image Proc., Vol. 18, pp. 97–108, 1982.

    Article  Google Scholar 

  30. C. Shakarji, “Least-squares fitting algorithms of the NIST algorithm testing system,” J. Res. Nat. Inst. Stand. Techn., Vol. 103, pp. 633–641, 1998.

    Google Scholar 

  31. H. Spath, “LeastSquares Fitting By Circles,” Computing, Vol. 57, pp. 179–185, 1996.

    Google Scholar 

  32. H. Spath, “Orthogonal least squares fitting by conic sections,” in Recent Advances in Total Least Squares techniques and Errors-in-Variables Modeling, SIAM, 1997, pp. 259–264.

  33. G. Taubin, “Estimation Of Planar Curves, Surfaces And Nonplanar Space Curves Defined By Implicit Equations, With Applications To Edge And Range Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 13, pp. 1115–1138, 1991.

    Article  Google Scholar 

  34. S.M. Thomas and Y.T. Chan, “A simple approach for the estimation of circular arc center and its radius,” Computer Vision, Graphics and Image Processing, Vol. 45, pp. 362–370, 1989.

    Google Scholar 

  35. K. Turner, “Computer perception of curved objects using a television camera,” Ph.D. Thesis, Dept. of Machine Intelligence, University of Edinburgh, 1974.

  36. Z. Wu, L. Wu, and A. Wu, “The Robust Algorithms for Finding the Center of an Arc,” Comp. Vision Image Under., Vol. 62, pp. 269–278, 1995.

    Article  Google Scholar 

  37. Z. Zhang, “Parameter Estimation Techniques: A Tutorial with Application to Conic Fitting,” International Journal of Image and Vision Computing, Vol. 15, pp. 59–76, 1997.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

Nikolai Chernov PhD in mathematics from Moscow University in 1984, scientist in Joint Institute for Nuclear Research (Dubna, Russia) 1983–1991, professor of mathematics in UCLA 1991–92, Georgia Tech 1992–93, Princeton University 1993–94, University of Alabama at Birmingham since 1994.

Claire Lesort MS in mathematics from University of Limoges in 1994, MS in mathematics from University of Alabama at Birmingham 2000, PhD in Statistics from University of Alabama at Birmingham 2004. Statistician at BellSouth Telecommunication Inc. since 2003.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chernov, N., Lesort, C. Least Squares Fitting of Circles. J Math Imaging Vis 23, 239–252 (2005). https://doi.org/10.1007/s10851-005-0482-8

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-005-0482-8

Keywords

Navigation