Direct and specific least-square fitting of hyperbolæ and ellipses

• Published in: Journal of electronic imaging 2004-07, Vol.13 (3), p.492-503
• Main Authors: O'Leary, Paul, Zsombor-Murray, Paul
• Format: Article
• Language: English
• ISSN: 1017-9909; 1560-229X
• DOI: 10.1117/1.1758951

A new method based on quadratic constrained least-mean-square fitting to simultaneously determine both the best hyperbolic and elliptical fits to a set of scattered data is presented. Thus a linear solution to the problem of hyperbola-specific fitting is revealed for the first time. Pilu's method to fit an ellipse (with respect to distance) to observed data points is extended to select, without prejudice, both ellipses and hyperbolæ as well as their degenerate forms as indicated by optimality with respect to the algebraic distance. This novel method is numerically efficient and is suitable for fitting to dense datasets with low noise. Furthermore, it is deemed highly suited to initialize a better but more computationally costly least-square minimization of orthogonal distance. Moreover, Grassmannian coordinates of the hyperbolæ are introduced, and it is shown how these apply to fitting a prototypical hyperbola. Two new theorems on fitting hyperbolæ are presented together with rigorous proofs. A new method to determine the spatial uncertainty of the fit from the eigen or singular values is derived and used as an indicator for the quality of fit. All proposed methods are verified using numerical simulation, and working MATLAB programs for the implementation are made available. Further, an application of the methods to automatic industrial inspection is presented. ©