Circular and Linear Regression: Fitting Circles and Lines by Least Squares

Find the right algorithm for your image processing application
Exploring the recent achievements that have occurred since the mid-1990s, Circular and Linear Regression: Fitting Circles and Lines by Least Squares explains how to use modern algorithms to fit geometric contours (circles and circular arcs) to observed data in image processing and computer vision. The author covers all facets—geometric, statistical, and computational—of the methods. He looks at how the numerical algorithms relate to one another through underlying ideas, compares the strengths and weaknesses of each algorithm, and illustrates how to combine the algorithms to achieve the best performance.

After introducing errors-in-variables (EIV) regression analysis and its history, the book summarizes the solution of the linear EIV problem and highlights its main geometric and statistical properties. It next describes the theory of fitting circles by least squares, before focusing on practical geometric and algebraic circle fitting methods. The text then covers the statistical analysis of curve and circle fitting methods. The last chapter presents a sample of "exotic" circle fits, including some mathematically sophisticated procedures that use complex numbers and conformal mappings of the complex plane.

Essential for understanding the advantages and limitations of the practical schemes, this book thoroughly addresses the theoretical aspects of the fitting problem. It also identifies obscure issues that may be relevant in future research.

Nikolai Chernov is a professor of mathematics at the University of Alabama at Birmingham.

Introduction and Historic Overview Classical regression Errors-in-variables (EIV) model Geometric fit Solving a general EIV problem Nonlinear nature of the "linear" EIV Statistical properties of the orthogonal fit Relation to total least squares (TLS) Nonlinear models: general overview Nonlinear models: EIV versus orthogonal fit

Fitting LinesParametrization Existence and uniqueness Matrix solution Error analysis: exact results Asymptotic models: large n versus small σ Asymptotic properties of estimators Approximative analysis Finite-size efficiency Asymptotic efficiency

Fitting Circles: TheoryIntroduction Parametrization (Non)existenceMultivariate interpretation of circle fit (Non)uniqueness Local minima Plateaus and valleys Proof of two valley theorem Singular case

Geometric Circle FitsClassical minimization schemes Gauss–Newton method Levenberg–Marquardt correction Trust regionLevenberg–Marquardt for circles: full version Levenberg–Marquardt for circles: reduced versionA modification of Levenberg–Marquardt circle fit Späth algorithm for circles Landau algorithm for circles Divergence and how to avoid it Invariance under translations and rotationsThe case of known angular differences

Algebraic Circle FitsSimple algebraic fit (Kåsa method) Advantages of the Kåsa method Drawbacks of the Kåsa method Chernov–Ososkov modification Pratt circle fit Implementation of the Pratt fit Advantages of the Pratt algorithm Experimental test Taubin circle fit Implementation of the Taubin fit General algebraic circle fits A real data example Initialization of iterative schemes

Statistical Analysis of Curve FitsStatistical models Comparative analysis of statistical models Maximum likelihood estimators (MLEs) Distribution and moments of the MLE General algebraic fits Error analysis: a general schemeSmall noise and "moderate sample size" Variance and essential bias of the MLE Kanatani–Cramer–Rao lower boundBias and inconsistency in the large sample limit Consistent fit and adjusted least squares
Statistical Analysis of Circle FitsError analysis of geometric circle fit Cramer–Rao lower bound for the circle fit Error analysis of algebraic circle fits Variance and bias of algebraic circle fits Comparison of algebraic circle fits Algebraic circle fits in natural parametersInconsistency of circular fits Bias reduction and consistent fits via Huber Asymptotically unbiased and consistent circle fits Kukush–Markovsky–van Huffel method Renormalization method of Kanatani: 1st order Renormalization method of Kanatani: 2nd order
Various "Exotic" Circle FitsRiemann sphere Simple Riemann fits Riemann fit: the SWFL version Properties of the Riemann fit Inversion-based fits The RTKD inversion-based fit The iterative RTKD fit Karimäki fit Analysis of Karimäki fit Numerical tests and conclusions
Bibliography
Index