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: 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: R.H. Biggerstaff, Three Variations in Dental Arch Form Estimated by a Quadratic Equation, Journal of Dental Research 51, 1509, 1972.
• 3: F.L. Bookstein, Fitting Conic Sections to Scattered Data, Computer Graphics and Image Processing 9, 56-71, 1979.
• 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: C. de Boor, A P r a c t i c a l Guide t o Splines, Springer-Verlag, 1978.
• 6: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• 7: Y. Gordon, Numerical Methods for CAD, MIT Press, 1986.
• 8: Arthur A. Giordano , Frank M. Hsu, Least Square Estimation with Applications to Digital Signal Processing, John Wiley & Sons, Inc., New York, NY, 1985
• 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: C. Hoffman and J. Hopcroft, Automatic Surface Generation in Computer Aided Design, The Visual Computer, 1, 2, 92-100 (1985).
• 11: Christoph Hoffmann , John Hopcrott, Quadratic blending surfaces, Computer-Aided Design, v.18 n.6, p.301-306, July/Aug. 1986 [doi>10.1016/0010-4485(86)90091-6]
• 12: C.L. Lawson and R.J. Hanson, Solving Least-Squares P r o b - lems, Prentice-Hall, 1974.
• 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: Alan E. Middleditch , Kenneth H. Sears, Blend surfaces for set theoretic volume modelling systems, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.161-170, Jul. 1985
• 15: V.S. Nalwa and E. Pauchon, Edgel-Aggregation and Edge-Description, Eighth International Conference on Pattern Rccogrdtion, 604-609, Paris, Oct. 1986,
• 16: K. Paton, Conic Sections in Chromosome Analysis, Pattern Recognition 2, 39-51, 1970.
• 17: Theodosios Pavlidis, Curve Fitting with Conic Splines, ACM Transactions on Graphics (TOG), v.2 n.1, p.1-31, Jan. 1983 [doi>10.1145/357314.357315]
• 18: K. Pearson, On lines and planes of closest fit to systems of points in space, Philos. Mag. Eer. 6, 2,559, 1901.
• 19: C. Pearson, Numerical Methods in Engineering and Science, Van Nostrand Reinhold, 1986.
• 20: Michael A. Penna , Richarad R. Patterson, Projective geometry and its applications to computer graphics, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 21: Michael Plass , Maureen Stone, Curve-fitting with piecewise parametric cubics, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.229-239, July 25-29, 1983, Detroit, Michigan, United States
• 22: Vaughan Pratt, Techniques for conic splines, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.151-160, Jul. 1985
• 23: D. Proflltt, The Measurement of Circularity and Ellipticity on a Digital Grid, Pattern Recognition 15, 5, 383-387, 1982.
• 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: 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

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Least squares approximation

Additional Classification:
  G. Mathematics of Computing

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Design, Measurement, Performance, Theory