Abstract: Fitting quadratic curves (a.k.a.\ conic sections, or conics) to data points (digitized images) is a fundamental task in image processing and computer vision. This problem reduces to minimization of a certain function over the parameter space of conics. Here we undertake a thorough investigation of that space and the properties of the objective function on it. Our analysis leads us to many important conclusions relevant to the performance of minimization algorithms.

Abstract: We develop a new algorithm for fitting circles that does not have drawbacks commonly found in existing circle fits. Our fit achieves ultimate accuracy (to machine precision), avoids divergence, and is numerically stable even when fitting circles get arbitrary large. Lastly, our algorithm takes less than 10 iterations to converge, on average.

Abstract: We study the problem of projecting 2D points onto quadratic curves (ellipses, hyperbolas, parabolas). We investigate various projection algorithms focusing on those that are mathematically proven to produce (or converge to) correct results in all cases. Our tests demonstrate that those may be still unfit for practical use due to large computational errors. We present two new algorithms that are not only theoretically proven to converge, but achieve nearly perfect accuracy.

Abstract: In regression problems where covariates are subject to errors (albeit small) it often happens that maximum likelihood estimators (MLE) of relevant parameters have infinite moments. We study here circular and elliptic regression, i.e., the problem of fitting circles and ellipses to observed points whose both coordinates are measured with errors. We prove that several popular circle fits due to Pratt, Taubin, and others return estimates of the center and radius that have infinite moments. We also argue that estimators of the ellipse parameters (center and semiaxes) should have infinite moments, too.

Abstract: Fitting straight lines and simple curved objects (circles, ellipses, etc.) to observed data points is a basic task in computer vision and modern statistics (errors-in-variables regression). We have investigated the problem of existence of the best fit in our previous paper (see Chernov et al. (2012)). Here we deal with the issue of uniqueness of the best fit.

Abstract: Fitting geometric shapes to observed data points (images) is a popular task in computer vision and modern statistics (Errors-In-Variables regression). We investigate the problem of existence of the best fit using geometric and probabilistic approaches.

Abstract: 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. Kanatani and Rangarajan 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.

Abstract: The technique of “renormalization” for geometric estimation attracted much attention when it was proposed in early 1990s for having higher accuracy than any other then known methods. Later, it was replaced by minimization of the reprojection error. This paper points out that renormalization can be modified so that it outperforms reprojection error minimization. The key fact is that renormalization directly specifies equations to solve, just as the “estimation equation” approach in statistics, rather than minimizing some cost. Exploiting this fact, we modify the problem so that the solution has zero bias up to high order error terms; we call the resulting scheme hyper-renormalization. We apply it to ellipse fitting to demonstrate that it indeed surpasses reprojection error minimization. We conclude that it is the best method available today.

Abstract: In computer vision one often fits ellipses and other conics to observed points on a plane or ellipsoids/quadrics to spacial point clouds. The most accurate and robust fit is obtained by minimizing geometric (orthogonal) distances, but this problem has no closed form solution and most known algorithms are prohibitively slow. We revisit this issue based on recent advances by S. J. Ahn, D. Eberly, and our own. Ahn has sorted out various approaches and identified the most efficient one. Eberly has developed a fast method of projecting points onto ellipses/ellipsoids (and gave a proof of its convergence). We extend Eberly's projection algorithm to other conics, as well as quadrics in space. We also demonstrate that Eberly's projection method combined with Ahn's most efficient approach (and using Taubin's algebraic fit for initialization) makes a highly efficient fitting scheme working well for all quadratic curves and surfaces.

Abstract: Regression models in which all variables are subject to errors are known as errors-in-variables (EIV) models. The respective parameter estimates have many unusual properties: their exact distributions are very hard to determine, and their absolute moments are often infinite (so that their mean and variance do not exist). In our paper Error analysis for circle fitting algorithms (see Electr. J. Stat. 3 (2009), pp. 886-911) we developed an unconventional statistical analysis that allowed us to effectively assess EIV parameter estimates and design new methods with superior characteristics. In this paper we validate our approach in a series of numerical tests.

Abstract: We study a nonlinear regression problem of fitting a circle (or a circular arc) to scattered data. We prove that under any standard assumptions on the statistical distribution of errors that are commonly adopted in the literature, the estimates of the circle center and radius have infinite moments. We also discuss methodological implications of this fact.

Abstract: We present a detailed error analysis for all popular circle fitting methods -- geometric fit, Kasa fit, Pratt fit, and Taubin fit. Our error analysis goes deeper than the traditional expansion to the leading order. We also obtain higher order terms, which show exactly why and by how much circle fits differ from each other. Our analysis allows us to construct a new algebraic (non-iterative) circle fitting algorithm that outperforms all the existing methods, including the (previously regarded as unsurpassable) geometric fit.

Abstract: We study the problem of fitting circles to scattered data. Unlike many other studies, we assume that the noise is (strongly) correlated; we adopt a particular model where correlations decay exponentially with the distance between data points. Our main results are formulas for the maximum likelihood estimates and their covariance matrix. Our study is motivated by (and applied to) arcs collected during archeological field work.

Abstract: We investigate numerical schemes for estimating parameters in computer vision problems (HEIV, FNS, renormalization method, and others). We prove mathematically that these algorithms converge rapidly, provided the noise is small. In fact, in just 1-2 iterations they achieve maximum possible statistical accuracy. Our results are supported by a numerical experiment. We also discuss the performance of these algorithms when the noise increases and/or outliers are present.

Abstract: We study a popular algorithm for fitting polynomial curves to scattered data based on the least squares with gradient weights. We show that sometimes this algorithm admits a substantial reduction of complexity, and, furthermore, find precise conditions under which this is possible. It turns out that this is, indeed, possible when one fits circles but not ellipses or hyperbolas.

Abstract: We study the problem of fitting parameterized curves to noisy data. Under certain assumptions (known as Cartesian and radial functional models), we derive asymptotic expressions for the bias and the covariance matrix of the parameter estimates. We also extend Kanatani's version of the Cramer-Rao lower bound, which he proved for unbiased estimates only, to more general estimates that include many popular algorithms (most notably, the orthogonal least squares and algebraic fits). We then show that the gradient-weighted algebraic fit is statistically efficient and describe all other statistically efficient algebraic fits.

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.