Direct least-squares fitting of algebraic surfaces

ABSTRACT

In the course of developing a system for fitting smooth curves to camera input we have developed several direct (i.e. noniterative) methods for fitting a shape (line, circle, conic, cubic, plane, sphere, quadric, etc.) to a set of points, namely exact fit, simple fit, spherical fit, and blend fit. These methods are all dimension-independent, being just as suitable for 3D surfaces as for the 2D curves they were originally developed for.Exact fit generalizes to arbitrary shapes (in the sense of the term defined in this paper) the well-known determinant method for planar exact fit. Simple fit is a naive reduction of the general overconstrained case to the exact case. Spherical fit takes advantage of a special property of circles and spheres that permits robust fitting; no prior direct circle fitters have been as robust, and there have been no previous sphere fitters. Blend fit finds the best fit to a set of points of a useful generalization of Middleditch-Sears blending curves and surfaces, via a nonpolynomial generalization of planar fit.These methods all require (am+bn)n² operations for fitting a surface of order n to m points, with a = 2 and b = 1/3 typically, except for spherical fit where b is larger due to the need to extract eigenvectors. All these methods save simple fit achieve a robustness previously attained by direct algorithms only for fitting planes. All admit incremental batched addition and deletion of points at cost an² per point and bn³ per batch.

References

1. 1.A. Albano, Representation of Digitized Contours in Terms of Conic Arcs and Straight-Line Segments, Computer Graphics and Image Processing 3, 23-33, 1974.
2. 2.R.H. Biggerstaff, Three Variations in Dental Arch Form Estimated by a Quadratic Equation, Journal of Dental Research 51, 1509, 1972.
3. 3.F.L. Bookstein, Fitting Conic Sections to Scattered Data, Computer Graphics and Image Processing 9, 56-71, 1979.
4. 4.D.B. Cooper and N. Yalabik, On the Computational Cost of Approximating and Recognizing Noise-Perturbed Straight Lines and Quadratic Arcs in the Plane, IEEE Transactions on Computers (3-25, 10, 1020- 1032~ October 1976.
5. 5.C. de Boor, A P r a c t i c a l Guide t o Splines, Springer-Verlag, 1978.
6. 6.I.D. Faux and M.J. Pratt, Computational Geometry for Design and Manufacture, Ellis Horwood, 1978.
7. 7.Y. Gordon, Numerical Methods for CAD, MIT Press, 1986.
8. 8.A.A. Giordano and F.M. Hsu, L e a s t Squares E s t i m a t i o n w i t h A p p l i c a t i o n s t o D i g i t a l S i g n a l P r o c e s s i n g , Wiley, 1985.
9. 9.R. Gnanadesikan, Methods for S t a t i s t i c a l Data A n a l y s i s o f M u l t i v a r i a t e O b s e r v a t i o n s , Wiley, 1977.
10. 10.C. Hoffman and J. Hopcroft, Automatic Surface Generation in Computer Aided Design, The Visual Computer, 1, 2, 92-100 (1985).
11. 11.C. Hoffman and J. Hopcroft, Quadratic Blending Surfaces, Computer Aided Design, 18, 6, 301-306 (Jnl-Aug. 1986).
12. 12.C.L. Lawson and R.J. Hanson, Solving Least-Squares P r o b - lems, Prentice-Hall, 1974.
13. 13.E.A. Lord and C.B. Wilson, The Mathematical D e s c r i p t i o n o f Shape and Form, Ellis Horwood, Chichester, 1984.
14. 14.A.E. Middleditch and K.H. Sears, Blend Surfaces for Set Theoretic Volume Modelling Systems, Computer Graphics 19, 3 (Siggraph-85), 161-170, July 1985.
15. 15.V.S. Nalwa and E. Pauchon, Edgel-Aggregation and Edge-Description, Eighth International Conference on Pattern Rccogrdtion, 604-609, Paris, Oct. 1986,
16. 16.K. Paton, Conic Sections in Chromosome Analysis, Pattern Recognition 2, 39-51, 1970.
17. 17.T. Pavlidis, Curve Fitting with Conic Splines, ACM Transactions on Graphics 2, 1, 1-31, January 1983.
18. 18.K. Pearson, On lines and planes of closest fit to systems of points in space, Philos. Mag. Eer. 6, 2,559, 1901.
19. 19.C. Pearson, Numerical Methods in Engineering and Science, Van Nostrand Reinhold, 1986.
20. 20.M.A. Penna and R.R. Patterson, P r o j e c t i v e Geometry and i t s A p p l i c a t i o n s t o Computer G r a p h i c s , Prentice-HMl, New Jersey, 1986.
21. 21.M. Plass and M. Stone, Curve-Fitting with Piecewise Parametric Cnbics, Computer Graphics 17, 3 (Siggraph-83), 229-239, July 1983.
22. 22.V. Pratt, Techniques for Conic Splines, Computer Graphics 19, 3 (Siggraph85), 151-159, July 1985.
23. 23.D. Proflltt, The Measurement of Circularity and Ellipticity on a Digital Grid, Pattern Recognition 15, 5, 383-387, 1982.
24. 24.P.D. Sampson, Fitting Conic Sections to "Very Scattered" Data: An Iterative R.efinement of the Bookstein Algorithm, Computer Graphics and Image Processing 18, 97-108, 1982.
25. 25.K. Turner, Computer Perception of Curved Objects using a Television Camera, Ph.D. Thesis~ Dept. of Machine Intelligenc% University of Edinburgh, Nov. 1974.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

  • Probability and statistics

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis