R e s e a r c h a r t i c l e s
( c l i c k o
n t h e P D
F l o g o t o
d o w n l o a d t h
e P D F v e r s i o
- Fitting quadratic curves to data points
N. Chernov, Q. Huang, and H. Ma
British Journal of
Mathematics & Computer Science, 4 (2014), 33-60.
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.
- Fast and numerically stable circle fit
Abdul-Rahman and N. Chernov
Journal of Mathematical Imaging and
Vision, DOI 10.1007/s10851-013-0461-4
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,
- Algorithms for projecting points onto conics
N. Chernov and S. Wijewickrema
Journal of Computational and Applied Mathematics, 251
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.
- Errors-In-Variables regression and the problem of
A. Al-Sharadqah, N. Chernov, and Q. Huang
Brazilian Journal of Probability and Statistics, 27
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,
- Is the best fitting curve always unique?
Q. Huang, and H. Ma
Journal of Mathematics (2013), Article
ID 753981 (5 pages).
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.
- Does the best fitting curve always exist?
Q. Huang, and H. Ma
ISRN Probability and Statistics (2012),
Article ID 895178 (25 pages).
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.
- A doubly optimal ellipse fit
A. Al-Sharadqah and N.
Computational Statistics and Data Analysis,
56 (2012), 2771-2781. (170Kb)
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.
- Renormalization Returns: Hyper-renormalization and Its
K. Kanatani, A. Al-Sharadqah, N. Chernov, Y.
Lecture Notes in Computer Science, 7574
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.
- Least squares fitting of quadratic curves and
N. Chernov and H. Ma
In: Computer Vision,
Editor S. R. Yoshida, Nova Science Publishers 2011; pp. 285-302.
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.
- Statistical analysis of curve fitting methods in
A. Al-Sharadqah and N. Chernov
Theor. Imovir. ta Matem. Statyst., 84 (2011), 4-17.
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
- Fitting circles to scattered data: parameter estimates have
METRIKA, 73 (2011),
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.
- Error analysis for circle fitting algorithms
Al-Sharadqah and N. Chernov
Electronic Journal of
Statistics, 3 (2009), 886-911.
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)
- Fitting circles to data with correlated noise
Chernov and P. N. Sapirstein
Computational Statistics and Data
Analysis, 52 (2008), 5328-5337. (170Kb)
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.
- On the convergence of fitting algorithms in computer
Journal of Mathematical Imaging and
Vision, 27 (2007), 231-239. (170Kb)
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.
- On the complexity of curve fitting algorithms
Chernov, C. Lesort, and N. Simanyi
Journal of Complexity,
20 (2004), 484-492. MR
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.
- Statistical efficiency of curve fitting algorithms
Chernov and C. Lesort
Computational Statistics and Data
Analysis, 47 (2004), 713-728. MR
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.
- Least squares fitting of circles
N. Chernov and C.
Journal of Mathematical Imaging and Vision, 23
(2005), 239-251. MR
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.
- Robust fitting of ellipses to non-complete and contaminated
N. Chernov, G. Ososkov, I. Silin
Journal of Physics, 50 (2000), 347-354. (380Kb)
- 3-dimensional multivertex reconstruction from 2-dimensional tracks
observations using likelihood inference
N. I. Chernov, G. A. Ososkov, L. Pronzato
Applied Mathematics, 37:6 (1992), 437-452.
- Effective algorithms for circle fitting
N. I. Chernov and G. A. Ososkov
Journal of Computer Physics Communications,
33 (1984), 329-333.