A doubly optimal ellipse fit. (English) Zbl 1255.62214
Summary: We study the problem of fitting ellipses to observed points in the context of errors-in-variables regression analysis. The accuracy of fitting methods is characterized by their variances and biases. The variance has a theoretical lower bound (the KCR bound), and many practical fits attend it, so they are optimal in this sense. There is no lower bound on the bias, though, and in fact our higher order error analysis (developed just recently) shows that it can be eliminated, to the leading order. K. Kanatani and P. Rangarajan [ibid. 55, No. 6, 2197–2208 (2011)] recently constructed an algebraic ellipse fit that has no bias, but its variance exceeds the KCR bound; so their method is optimal only relative to the bias. We present here a novel ellipse fit that enjoys both optimal features: the theoretically minimal variance and zero bias (both to the leading order). Our numerical tests confirm the superiority of the proposed fit over the existing fits.
MSC:
| 62J99 | Linear inference, regression |
| 65C60 | Computational problems in statistics (MSC2010) |
Keywords:
errors-in-variables regression; ellipse fitting; conic fitting; Cramer-Rao bound; bias reductionReferences:
| [1] | Ahn, S. J., (Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space. Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space, LNCS, vol. 3151 (2004), Springer: Springer Berlin) · Zbl 1067.65019 |
| [2] | Al-Sharadqah, A.; Chernov, N., Error analysis for circle fitting algorithms, Electron. J. Stat., 3, 886-911 (2009) · Zbl 1268.65022 |
| [3] | Bookstein, F. L., Fitting conic sections to scattered data, Comput. Graph. Image Process., 9, 56-71 (1979) |
| [4] | Chernov, N., On the convergence of fitting algorithms in computer vision, J. Math. Imaging Vision, 27, 231-239 (2007) · Zbl 1478.62185 |
| [5] | Chernov, N., Circular and Linear Regression: Fitting Circles and Lines by Least Squares, Vol. 117 (2010), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton |
| [6] | Chernov, N.; Lesort, C., Statistical efficiency of curve fitting algorithms, Comp. Stat. Data Anal., 47, 713-728 (2004) · Zbl 1429.62018 |
| [7] | Chojnacki, W.; Brooks, M. J.; van den Hengel, A., Rationalising the renormalisation method of Kanatani, J. Math. Imaging Vision, 14, 21-38 (2001) · Zbl 0990.68175 |
| [8] | Chojnacki, W.; Brooks, M. J.; van den Hengel, A.; Gawley, D., On the fitting of surfaces to data with covariances, IEEE Trans. Pattern Analysis Machine Intelligence, 22, 1294-1303 (2000) |
| [9] | Fazekas, I.; Kukush, A.; Zwanzig, S., Correction of nonlinear orthogonal regression estimator, Ukr. Math. J., 56, 1101-1118 (2004) · Zbl 1070.62053 |
| [10] | Gander, W.; Golub, G. H.; Strebel, R., Least squares fitting of circles and ellipses, BIT, 34, 558-578 (1994) · Zbl 0817.65008 |
| [11] | Kanatani, K., Statistical bias of conic fitting and renormalization, IEEE Trans. Pattern Analysis Machine Intelligence, 16, 320-326 (1994) · Zbl 0808.65004 |
| [12] | Kanatani, K., Statistical Optimization for Geometric Computation: Theory and Practice (1996), Elsevier Science: Elsevier Science Amsterdam, Netherlands · Zbl 0851.62078 |
| [13] | Kanatani, K., For geometric inference from images, what kind of statistical model is necessary?, Syst. Comp. Japan, 35, 1-9 (2004) |
| [14] | Kanatani, K., Ellipse fitting with hyperaccuracy, IEICE Trans. Inform. Syst., E89-D, 2653-2660 (2006) |
| [15] | Kanatani, K., 2006b. Ellipse fitting with hyperaccuracy. In: Proc. 9th European Conf. Computer Vision, ECCV 2006, Vol. 1, pp. 484-495.; Kanatani, K., 2006b. Ellipse fitting with hyperaccuracy. In: Proc. 9th European Conf. Computer Vision, ECCV 2006, Vol. 1, pp. 484-495. |
| [16] | Kanatani, K., Statistical optimization for geometric fitting: theoretical accuracy bound and high order error analysis, Int. J. Comput. Vis., 80, 167-188 (2008) · Zbl 1477.68383 |
| [17] | Kanatani, K., Optimal estimation, (Ikeuchi, K., Encyclopedia of Computer Vision (2011), Springer: Springer Berlin) |
| [18] | Kanatani, K.; Rangarajan, P., Improved algebraic methods for circle fitting, Electron. J. Stat., 3, 1075-1082 (2009) · Zbl 1263.68152 |
| [19] | Kanatani, K.; Rangarajan, P., Hyper least squares fitting of circles and ellipses, Comput. Statist. Data Anal., 55, 2197-2208 (2011) · Zbl 1328.62399 |
| [20] | Kanatani, K.; Rangarajan, P.; Sugaya, Y.; Niitsuma, H., HyperLS and its applications, IPSJ Trans. Computer Vision Appl., 3 (2011) |
| [21] | Kukush, A.; Markovsky, I.; Van Huffel, S., Consistent estimation in an implicit quadratic measurement error model, Comput. Statist. Data Anal., 47, 123-147 (2004) · Zbl 1429.62295 |
| [22] | Leedan, Y.; Meer, P., Heteroscedastic regression in computer vision: problems with bilinear constraint, Int. J. Comput. Vis., 37, 127-150 (2000) · Zbl 0985.68627 |
| [23] | Sampson, P. D., Fitting conic sections to very scattered data: an iterative refinement of the Bookstein algorithm, Comput. Graph. Image Process., 18, 97-108 (1982) |
| [24] | 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, 13, 1115-1138 (1991) |
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.
