×

Robust fitting of circle arcs. (English) Zbl 1255.68245

Summary: Geometric fitting is present in different fields of sciences, engineering and astronomy. In particular, circular arc primitives are some of the most commonly employed geometric features in digital image analysis and visual pattern recognition. In this paper, a robust geometric method based on mean absolute error to fit a set of points is proposed. Most geometric and algebraic methods are sensitive to noise and outlier points and so the results are not usually acceptable. It is well known that the least absolute error criterion leads to robust estimations. However, the objective function is non differentiable and thus algorithms based on gradient cannot be applied. We propose an algorithm based on left and right side partial derivatives that is computationally efficient as an alternative to conventional algorithms, and evaluate the sensitivity of circle fits for different types of data.

MSC:

68U10 Computing methodologies for image processing
68T10 Pattern recognition, speech recognition
68T45 Machine vision and scene understanding

Software:

AMPL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shunmugam, M.S.: Criteria for computer-aided form evaluation. J. Eng. Ind. 113, 233–238 (1991) · doi:10.1115/1.2899684
[2] Van-Ban, L., Lee, D.T.: Out-of-roundness problem revisited. IEEE Trans. Pattern Anal. Mach. Intell. 13, 217–23 (1991) · Zbl 05110933 · doi:10.1109/34.75510
[3] Ventura, J.A., Yeralan, S.: The minimax centre estimation problem for automated roundness inspection. Eur. J. Oper. Res. 41, 64–72 (1989) · Zbl 0668.90038 · doi:10.1016/0377-2217(89)90039-8
[4] Yeralan, S., Ventura, J.A.: Computerized roundness inspection. Int. J. Prod. Res. 26, 1921–1935 (1988) · doi:10.1080/00207548808948005
[5] Schalk, P., Ofner, R., O’Leary, P.: Pipe eccentricity measurement using laser triangulation. Image Vis. Comput. 25, 1194–1203 (2007) · doi:10.1016/j.imavis.2006.04.021
[6] Karimäki, V.: Effective circle fitting for particle trajectories. Nucl. Instrum. Methods Phys. Res., Sect. A, Accel. Spectrom. Detect. Assoc. Equip. 305, 187–191 (1991) · doi:10.1016/0168-9002(91)90533-V
[7] Joseph, S.H.: Unbiased least-squares fitting of circular arcs. Graph. Models Image Process. 56, 424–432 (1994) · doi:10.1006/cgip.1994.1039
[8] Ahn, S.J., Rauh, W., Warnecke, H.J.: Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola and parabola. Pattern Recognit. 34, 2283–2303 (2001) · Zbl 0991.68127 · doi:10.1016/S0031-3203(00)00152-7
[9] Rorres, C., Romano, D.G.: Finding the centre of a circular starting line in an ancient Greek Stadium. SIAM Rev. 39(4), 745–754 (1997) · Zbl 0888.01001 · doi:10.1137/S0036144596305727
[10] Chernov, N., Sapirstein, P.N.: Fitting circles to data with correlated noise. Comput. Stat. Data Anal. 52, 5328–5337 (2008) · Zbl 1452.62041 · doi:10.1016/j.csda.2008.05.025
[11] Paton, K.: Conic sections in chromosome analysis. Pattern Recognit. 2, 39–51 (1970) · doi:10.1016/0031-3203(70)90040-3
[12] Corral, C.A., Lindquist, C.S.: On Implementing Kåsa’s circle fit procedure. IEEE Trans. Instrum. Meas. 47, 789–795 (1998) · doi:10.1109/19.744352
[13] Gander, W., Golub, G.H., Strebel, R.: Least-square fitting of circles and ellipses. BIT Numer. Math. 43, 558–578 (1994) · Zbl 0817.65008 · doi:10.1007/BF01934268
[14] Calafiore, G.: Approximation of n-dimensional data using spherical and ellipsoidal primitives. IEEE Trans. Syst. Man Cybern., Part A, Syst. Hum. 32, 269–278 (2002) · doi:10.1109/TSMCA.2002.1021114
[15] Kåsa, I.: A curve fitting procedure and its error analysis. IEEE Trans. Instrum. Meas. 25, 8–14 (1976) · doi:10.1109/TIM.1976.6312298
[16] Zelniker, E.E., Clarkson, I.V.L.: A statistical analysis of the Delogne-Kåsa method for fitting circles. Digit. Signal Process. 16, 498–522 (2006) · doi:10.1016/j.dsp.2005.04.001
[17] Landau, U.M.: Estimation of a circular arc centre and its radius. Comput. Vis. Graph. Image Process. 38, 317–326 (1987) · doi:10.1016/0734-189X(87)90116-2
[18] Späth, H.: Least-squares fitting by circles. Computing 57, 179–185 (1996) · Zbl 0860.65005 · doi:10.1007/BF02276879
[19] Chernov, N., Lesort, C.: Least squares fitting of circles. J. Math. Imaging Vis. 23, 239–252 (2005) · Zbl 1478.65011 · doi:10.1007/s10851-005-0482-8
[20] Drezner, Z., Steiner, S., Wesolowsky, G.O.: On the circle closet to a set of points. Comput. Oper. Res. 29, 637–650 (2002) · Zbl 0994.90088 · doi:10.1016/S0305-0548(99)00105-7
[21] Plastria, F.: GBSSS, the generalized big square small square method for planar single facility location. Eur. J. Oper. Res. 62, 163–174 (1992) · Zbl 0760.90067 · doi:10.1016/0377-2217(92)90244-4
[22] Hansen, P., Peeters, D., Richard, D., Thisse, J.F.: The minisum and minimax location problems revisited. Oper. Res. 33, 1251–1265 (1985) · Zbl 0582.90027 · doi:10.1287/opre.33.6.1251
[23] Umbach, D., Jones, K.N.: A few methods for fitting circles to data. IEEE Trans. Instrum. Meas. 52, 1881–1885 (2003) · doi:10.1109/TIM.2003.820472
[24] Caudill, S.B.: Estimating the circle closest to a set of points by maximum likelihood using the BHHH algorithm. Eur. J. Oper. Res. 172, 120–126 (2006) · Zbl 1116.62367 · doi:10.1016/j.ejor.2004.09.031
[25] Berndt, E.R., Hall, B.H., Hall, R.E., Hausman, J.A.: Estimation and Inference in nonlinear structural models. Ann. Econ. Soc. Meas. 3, 653–665 (1974)
[26] Al-Sharadqah, A., Chernov, N.: Error analysis for circle fitting algorithms. Electron. J. Stat. 3, 886–911 (2009) · Zbl 1268.65022 · doi:10.1214/09-EJS419
[27] Rangarajan, P., Kanatani, K.: Improved algebraic methods for circle fitting. Electron. J. Stat. 3, 1075–1082 (2009) · Zbl 1263.68152 · doi:10.1214/09-EJS488
[28] Fischler, M.A., Bolles, R.C.: Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 381–395 (1981) · doi:10.1145/358669.358692
[29] Fourer, R., Gay, D.M., Kernighan, B.W.: Ampl. A Modelling Language for Mathematical Programming. The Scientific Press, San Francisco (1993)
[30] Canny, J.: A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8, 679–698 (1986) · doi:10.1109/TPAMI.1986.4767851
[31] Coope, I.D.: Circle fitting by linear and nonlinear least squares. J. Optim. Theory Appl. 76, 381–388 (1993) · Zbl 0790.65012 · doi:10.1007/BF00939613
[32] Gruntz, D.: Finding the best fit circle. MathWorks Newsl. 1, 5 (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.