Guaranteed ellipse fitting with a confidence region and an uncertainty measure for centre, axes, and orientation. (English) Zbl 1330.68319
Summary: A simple and fast ellipse estimation method is presented based on optimisation of the Sampson distance serving as a measure of the quality of fit between a candidate ellipse and data points. Generation of ellipses, not just conics, as estimates is ensured through the use of a parametrisation of the set of all ellipses. Optimisation of the Sampson distance is performed with the aid of a custom variant of the Levenberg-Marquardt algorithm. The method is supplemented with a measure of uncertainty of an ellipse fit in two closely related forms. One of these concerns the uncertainty in the algebraic parameters of the fit and the other pertains to the uncertainty in the geometrically meaningful parameters of the fit such as the centre, axes, and major axis orientation. In addition, a means is provided for visualising the uncertainty of an ellipse fit in the form of planar confidence regions. For moderate noise levels, the proposed estimator produces results that are fully comparable in accuracy to
those produced by the much slower maximum likelihood estimator. Due to its speed and simplicity, the method may prove useful in numerous industrial applications where a measure of reliability for geometric ellipse parameters is required.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
ellipse fitting; maximum likelihood; uncertainty measure; simultaneous confidence region; centre; semi-major and semi-minor axes; orientationReferences:
| [1] | Ahn, SJ, Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space, No. 3151 (2004), Heidelberg · Zbl 1067.65019 |
| [2] | Ahn, S.J., Rauh, W., Warnecke, H.: Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola. Pattern Recog. 34(12), 2283-2303 (2001) · Zbl 0991.68127 · doi:10.1016/S0031-3203(00)00152-7 |
| [3] | Al-Sharadqah, A., Chernov, N.: A doubly optimal ellipse fit. Comput. Stat. Data Anal. 56(9), 2771-2781 (2012) · Zbl 1255.62214 · doi:10.1016/j.csda.2012.02.028 |
| [4] | Albert, A.: Regression and the Moore-Penrose Pseudoinverse. Academic Press, New York (1972) · Zbl 0253.62030 |
| [5] | Bartoli, A.: Towards gauge invariant bundle adjustment: a solution based on gauge dependent damping. In: Proceedings of 9th International Conference on Computer Vision, pp. 760-765 (2003) |
| [6] | Brooks, M.J., Chojnacki, W., Gawley, D., van den Hengel, A.: What value covariance information in estimating vision parameters? In: Proceedings of 8th International Conference on Computer Vision, vol. 1, pp. 302-308 (2001) |
| [7] | Chernov, N., Huang, Q., Ma, H.: Does the best-fitting curve always exist? ISRN Prob. Stat. (2012). doi:10.5402/2012/895178 · Zbl 1398.62178 |
| [8] | Chernov, N., Huang, Q., Ma, H.: Fitting quadratic curves to data points. Br. J. Math. Comput. Sci. 4(1), 33-60 (2014) · doi:10.9734/BJMCS/2014/6016 |
| [9] | Chernov, N., Lesort, C.: Statistical efficiency of curve fitting algorithms. Comput. Stat. Data Anal. 47(4), 713-728 (2004) · Zbl 1429.62018 · doi:10.1016/j.csda.2003.11.008 |
| [10] | Chernov, N.; Ma, H.; Yoshida, SR (ed.), Least squares fitting of quadratic curves and surfaces, 285-302 (2011), New York |
| [11] | Chernov, N., Wijewickrema, S.: Algorithms for projecting points onto conics. J. Comput. Appl. Math. 251, 8-21 (2013) · Zbl 1288.65016 · doi:10.1016/j.cam.2013.03.031 |
| [12] | Chojnacki, W., Brooks, M.J.: On the consistency of the normalized eight-point algorithm. J. Math. Imaging Vis. 28, 19-27 (2007) · Zbl 1478.62117 · doi:10.1007/s10851-007-0009-6 |
| [13] | Chojnacki, W., Brooks, M.J., van den Hengel, A., Gawley, D.: On the fitting of surfaces to data with covariances. IEEE Trans. Pattern Anal. Mach. Intell. 22(11), 1294-1303 (2000) · Zbl 0971.60064 · doi:10.1109/34.888714 |
| [14] | Chojnacki, W., Brooks, M.J., van den Hengel, A., Gawley, D.: Revisiting Hartley’s normalized eight-point algorithm. IEEE Trans. Pattern Anal. Mach. Intell. 25(9), 1172-1177 (2003) · doi:10.1109/TPAMI.2003.1227992 |
| [15] | Csurka, G., Zeller, C., Zhang, Z., Faugeras, O.D.: Characterizing the uncertainty of the fundamental matrix. Comput. Vis. Image Underst. 68(1), 18-36 (1997) · doi:10.1006/cviu.1997.0531 |
| [16] | Fazekas, I., Kukush, A., Zwanzig, S.: Correction of nonlinear orthogonal regression estimator. Ukr. Math. J. 56(8), 1308-1330 (2004) · Zbl 1070.62053 · doi:10.1007/s11253-005-0059-0 |
| [17] | Fitzgibbon, A., Pilu, M., Fisher, R.B.: Direct least square fitting of ellipses. IEEE Trans. Pattern Anal. Mach. Intell. 21(5), 476-480 (1999) · doi:10.1109/34.765658 |
| [18] | Förstner, W.; Corrochano, EB (ed.); Förstner, W. (ed.), Uncertainty and projective geometry, 493-534 (2005), Berlin Heidelberg · doi:10.1007/3-540-28247-5_15 |
| [19] | Gander, W., Golub, G.H., Strebel, R.: Least-squares fitting of circles and ellipses. BIT 34(4), 558-578 (1994) · Zbl 0817.65008 · doi:10.1007/BF01934268 |
| [20] | Golub, G.H., Pereyra, V.: The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. Anal. 10(2), 413-432 (1973) · Zbl 0258.65045 · doi:10.1137/0710036 |
| [21] | Halíř, R., Flusser, J.: Numerically stable direct least squares fitting of ellipses. In: Proceedings of 6th International Conference in Central Europe on Computer Graphics and Visualization, vol. 1, pp. 125-132 (1998) |
| [22] | Haralick, R.M.: Propagating covariance in computer vision. Int. J. Pattern Recogn. Artif. Intell. 10(5), 561-572 (1996) · doi:10.1142/S0218001496000347 |
| [23] | Hartley, R.: In defense of the eight-point algorithm. IEEE Trans. Pattern Anal. Mach. Intell. 19(6), 580-593 (1997) · doi:10.1109/34.601246 |
| [24] | Hartley, R.I., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press, Cambridge (2004) · Zbl 1072.68104 · doi:10.1017/CBO9780511811685 |
| [25] | Hunyadi, L., Vajk, I.: Constrained quadratic errors-in-variables fitting. Visual Comput. (2013). doi:10.1007/s00371-013-0885-2 · doi:10.1007/s00371-013-0885-2 |
| [26] | Kanatani, K.: Statistical bias of conic fitting and renormalization. IEEE Trans. Pattern Anal. Mach. Intell. 16(3), 320-326 (1994) · Zbl 0808.65004 · doi:10.1109/34.276132 |
| [27] | Kanatani, K.: Statistical Optimization for Geometric Computation: Theory and Practice. Elsevier, Amsterdam (1996) · Zbl 0851.62078 |
| [28] | Kanatani, K.: Ellipse fitting with hyperaccuracy. IEICE Trans. Inf. Syst. E89-D(10), 2653-2660 (2006) · doi:10.1093/ietisy/e89-d.10.2653 |
| [29] | Kanatani, K., Al-Sharadqah, A., Chernov, N., Sugaya, Y.: Renormalization returns: hyper-renormalization and its applications. In: Proceedings of 12th European Conference on Computer Vision, Lecture Notes on Computer Science, vol. 7574, pp. 384-397 (2012) |
| [30] | Kanatani, K., Rangarajan, P.: Hyper least squares fitting of circles and ellipses. Comput. Stat. Data Anal. 55(6), 2197-2208 (2011) · Zbl 1328.62399 · doi:10.1016/j.csda.2010.12.012 |
| [31] | Kanazawa, Y., Kanatani, K.: Optimal conic fitting and reliability evaluation. IEICE Trans. Inf. Syst. E79-D(9), 1323-1328 (1996) |
| [32] | Kim, I.: Orthogonal distance fitting of ellipses. Commun. Korean Math. Soc. 17(1), 121-142 (2002) · Zbl 1101.65307 · doi:10.4134/CKMS.2002.17.1.121 |
| [33] | Kukush, A., Markovsky, I., Huffel, S.V.: Consistent estimation in an implicit quadratic measurement error model. Comput. Stat. Data Anal. 47(1), 123-147 (2004) · Zbl 1429.62295 · doi:10.1016/j.csda.2003.10.022 |
| [34] | Lehmann, E.L., Romano, J.P.: Testing Statistical Hypotheses, 3rd edn. Springer, New York (2005) · Zbl 1076.62018 |
| [35] | Lütkepol, H.: Handbook of Matrices. Wiley, Chichester (1996) · Zbl 0856.15001 |
| [36] | Magnus, J.R., Neudecker, H.: Matrix Differential Calculus with Applications in Statistics and Econometrics. Wiley, Chichester (1988) · Zbl 0651.15001 |
| [37] | Matei, B., Meer, P.: Reduction of bias in maximum likelihood ellipse fitting. In: Proceedings of 15th International Conference on Pattern Recognition, vol. 3, pp. 794-798 (2000) · Zbl 0052.15202 |
| [38] | Newsam, G.N., Redding, N.J.: Fitting the most probable curve to noisy observations. In: Proceedings of International Conference on Image Processing 2, 752-755 (1997) |
| [39] | Newsam, G.N., Redding, N.J.: Fitting the most likely curve through noisy data. Technical Report DSTO-RR-0242, Electronics and Surveillance Research Laboratory, Defence Science and Technology Organisation, Edinburgh, South Australia (2002) · Zbl 1255.62214 |
| [40] | Okatani, T., Deguchi, K.: Improving accuracy of geometric parameter estimation using projected score method. In: Proceedings of 12th International Conference on Computer Vision, pp. 1733-1740 (2009) · Zbl 0991.68127 |
| [41] | Okatani, T., Deguchi, K.: On bias correction for geometric parameter estimation in computer vision. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 959-966 (2009) |
| [42] | O’Leary, P., Zsombor-Murray, P.: Direct and specific least-square fitting of hyperbolæ and ellipses. J. Electron. Imaging 13(3), 492-503 (2004) · doi:10.1117/1.1758951 |
| [43] | Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000) · Zbl 0949.65053 · doi:10.1137/1.9780898719468 |
| [44] | Osborne, M.R.: Nonlinear least squares-the Levenberg algorithm revisited. J. Aust. Math. Soc. Ser. B 19(3), 343-357 (1976) · Zbl 0364.90100 · doi:10.1017/S033427000000120X |
| [45] | Penrose, R.: A generalized inverse for matrices. Math. Proc. Cambridge Philos. Soc. 51, 406-413 (1955) · Zbl 0065.24603 · doi:10.1017/S0305004100030401 |
| [46] | Porrill, J.: Fitting ellipses and predicting confidence envelopes using a bias corrected Kalman filter. Image Vis. Comput. 8(1), 37-41 (1990) · doi:10.1016/0262-8856(90)90054-9 |
| [47] | Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes in C. Cambridge University Press, Cambridge (1995) · Zbl 0778.65003 |
| [48] | Rosin, P.L.: A note on the least squares fitting of ellipses. Pattern Recogn. Lett. 14(10), 799-808 (1993) · Zbl 0802.68155 |
| [49] | Rosin, P.L.: Analysing error of fit functions for ellipses. Pattern Recogn. Lett. 17(14), 1461-1470 (1996) · doi:10.1016/S0167-8655(96)00102-X |
| [50] | Sampson, P.D.: Fitting conic sections to ‘very scattered’ data: an iterative refinement of the Bookstein algorithm. Comput. Graph. Image Process. 18(1), 97-108 (1982) · doi:10.1016/0146-664X(82)90101-0 |
| [51] | Scheffé, H.: A method for judging all contrasts in the analysis of variance. Biometrika 40, 87-104 (1953) · Zbl 0052.15202 |
| [52] | Stewart, G.W.: On the continuity of the generalized inverse. SIAM J. Appl. Math. 17(1), 33-45 (1969) · Zbl 0172.03801 · doi:10.1137/0117004 |
| [53] | Sturm, P., Gargallo, P.: Conic fitting using the geometric distance. In: Proceedings of 8th Asian Conference on Computer Vision, Lecture Notes on Computer Science, vol. 4844, pp. 784-795 (2007) · Zbl 0172.03801 |
| [54] | Szpak, Z., Chojnacki, W., van den Hengel, A.: Guaranteed ellipse fitting with the Sampson distance. In: Proceedings of 12th European Conference on Computer Vision, Lecture Notes on Computer Science, vol. 7576, pp. 87-100 (2012) · Zbl 0052.15202 |
| [55] | Szpak, Z.L., Chojnacki, W., van den Hengel, A.: A comparison of ellipse fitting methods and implications for multiple-view geometry estimation. In: Proceedings of International Conference on Digital Image Computing Techniques and Applications, pp. 1-8 (2012) |
| [56] | 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 Anal. Mach. Intell. 13(11), 1115-1138 (1991) · doi:10.1109/34.103273 |
| [57] | Triggs, B., McLauchlan, P.F., Hartley, R.I., Fitzgibbon, A.W.: Bundle adjustment—a modern synthesis. In: Proceedings of International Workshop on Vision Algorithms, Lecture Notes in Computer Science, vol. 1883, pp. 298-372 (1999) |
| [58] | Turner, K.: Computer perception of curved objects using a television camera. Ph.D. thesis, Department of Machine Intelligence, University of Edinburgh (1974) · Zbl 0065.24603 |
| [59] | Varah, J.M.: Least squares data fitting with implicit functions. BIT 36(4), 842-854 (1996) · Zbl 0865.65003 · doi:10.1007/BF01733795 |
| [60] | Wong, C.Y., Lin, C.F., Ren, T.R., Kwok, N.M.: A survey on ellipse detection methods. In: IEEE International Symposium on Industrial Electronics, pp. 1105-1110 (2012) |
| [61] | Zhang, Z.: Parameter estimation techniques: a tutorial with application to conic fitting. Image and Vision Computing 15(1), 59-76 (1997) · doi:10.1016/S0262-8856(96)01112-2 |
| [62] | Zwillinger, D.: CRC Standard Mathematical Tables and Formulae, 32nd edn. CRC Press, Boca Raton (2012) · Zbl 1222.00012 |
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.
