Direct least-squares fitting of algebraic surfaces
Tóm tắt
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 (
Từ khóa
Tài liệu tham khảo
C. de Boor , A P r a c t i c a l Guide t o Splines , Springer-Verlag , 1978 . C. de Boor, A P r a c t i c a l Guide t o Splines, Springer-Verlag, 1978.
I.D. Faux and M.J. Pratt , Computational Geometry for Design and Manufacture , Ellis Horwood , 1978 . I.D. Faux and M.J. Pratt, Computational Geometry for Design and Manufacture, Ellis Horwood, 1978.
Y. Gordon , Numerical Methods for CAD , MIT Press , 1986 . Y. Gordon, Numerical Methods for CAD, MIT Press, 1986.
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 . 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.
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 . 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.
C. Hoffman and J. Hopcroft , Automatic Surface Generation in Computer Aided Design, The Visual Computer , 1 , 2 , 92-100 ( 1985 ). C. Hoffman and J. Hopcroft, Automatic Surface Generation in Computer Aided Design, The Visual Computer, 1, 2, 92-100 (1985).
C.L. Lawson and R.J. Hanson , Solving Least-Squares P r o b - lems , Prentice-Hall , 1974 . C.L. Lawson and R.J. Hanson, Solving Least-Squares P r o b - lems, Prentice-Hall, 1974.
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 . 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.
V.S. Nalwa and E. Pauchon , Edgel-Aggregation and Edge-Description , Eighth International Conference on Pattern Rccogrdtion, 604-609 , Paris , Oct. 1986 , V.S. Nalwa and E. Pauchon, Edgel-Aggregation and Edge-Description, Eighth International Conference on Pattern Rccogrdtion, 604-609, Paris, Oct. 1986,
K. Pearson , On lines and planes of closest fit to systems of points in space , Philos. Mag. Eer. 6 , 2 ,559, 1901 . K. Pearson, On lines and planes of closest fit to systems of points in space, Philos. Mag. Eer. 6, 2,559, 1901.
C. Pearson , Numerical Methods in Engineering and Science , Van Nostrand Reinhold , 1986 . C. Pearson, Numerical Methods in Engineering and Science, Van Nostrand Reinhold, 1986.
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 . 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.
D. Proflltt , The Measurement of Circularity and Ellipticity on a Digital Grid , Pattern Recognition 15 , 5 , 383-387, 1982 . D. Proflltt, The Measurement of Circularity and Ellipticity on a Digital Grid, Pattern Recognition 15, 5, 383-387, 1982.