Direct least-squares fitting of algebraic surfaces

Association for Computing Machinery (ACM) - Tập 21 Số 4 - Trang 145-152 - 1987
Vaughan Pratt1
1Sun Microsystems, Inc.

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 ( am + bn ) n 2 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 2 per point and bn 3 per batch.

Từ khóa


Tài liệu tham khảo

10.1016/0146-664X(74)90008-2

10.1177/00220345720510055101

10.1016/0146-664X(79)90082-0

10.1109/TC.1976.1674543

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).

10.1016/0010-4485(86)90091-6

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.

10.1145/325165.325231

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,

10.1016/0031-3203(70)90040-3

10.1145/357314.357315

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.

10.1145/800059.801153

10.1145/325165.325225

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.

10.1016/0146-664X(82)90101-0

Thông tin
Thông tin xuất bản

Association for Computing Machinery (ACM)

Tập 21 Số 4

145-152

Thông tin tác giả