Grouping and parameterizing irregularly spaced points for curve fitting

ABSTRACT

Given a large set of irregularly spaced points in the plane, an algorithm for partitioning the points into subsets and fitting a parametric curve to each subset is described. The points could be measurements from a physical phenomenon, and the objective in this process could be to find patterns among the points and describe the phenomenon analytically. The points could be measurements from a geometric model, and the objective could be to reconstruct the model by a combination of parametric curves. The algorithm proposed here can be used in various applications, especially where given points are dense and noisy. Examples demonstrating the behavior of the algorithm under noise and density of the points are presented and discussed.

REFERENCES

• 1: BANFIELD,D.B.AND RAFTERY, A. E. 1992. Ice floe identification in satellite images using mathematical morphology and clustering about principal curves. J. Am. Stat. Assoc. 87, 7-16.
• 2: Robert C. Beach, An introduction to the curves and surfaces of computer-aided design, Van Nostrand Reinhold Co., New York, NY, 1991
• 3: BUHMANN, M. D. 1990. Multivariate cardinal interpolation with radial basis functions. Constr. Approx. 6, 225-255.
• 4: Kenneth R. Castleman, Digital image processing, Prentice Hall Press, Upper Saddle River, NJ, 1996
• 5: E. Cohen , C. L. O'Dell, A data dependent parametrization for spline approximation, Mathematical methods in computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1989
• 6: DYN, N. 1987. Interpolation of scattered data by radial functions. In Topics in Multivariate Approximation. Academic Press, Inc., New York, NY, 47-61.
• 7: G. Farin, Curves and surfaces for computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1990
• 8: Rida T. Farouki, Optimal parameterizations, Computer Aided Geometric Design, v.14 n.2, p.153-168, Feb. 1997 [doi>10.1016/S0167-8396(96)00026-X]
• 9: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• 10: Tom Lyche , Larry L. Schumaker, Mathematical methods in computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1989
• 11: FRITSCH,R.E.AND CARLSON, R. E. 1980. Monotone piecewise cubic interpolation. SIAM J. Numer. Anal. 17, 238-246.
• 12: GOSHTASBY, A. 1995. Geometric modeling using rational gaussian curves and surfaces. Comput. Aided Des. 27, 363-375.
• 13: Ardeshir Goshtasby , William D. O'Neill, Surface fitting to scattered data by a sum of Gaussians, Computer Aided Geometric Design, v.10 n.2, p.143-156, April 1993 [doi>10.1016/0167-8396(93)90017-W]
• 14: GROSSMAN, M. 1970. Parametric curve fitting. Computer J. 14, 169-172.
• 15: Hans Hagen, Curve and surface design, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 16: HARDY, R. L. 1990. Theory and applications of the multiquadrics--biharmonic method. Comput. Math. Appl. 19, 163-208.
• 17: HARTLEY,P.J.AND JUDD, C. J. 1980. Parametrization and shape of b-spline curves for cad. Comput. Aided Des. 12, 235-238.
• 18: HASTIE,T.AND STUETZLE, W. 1989. Principal curves. J. Am. Stat. Assoc. 84, 502-516.
• 19: H~LZLE, G. E. 1983. Knot placement for piecewise polynomial approximation of curves. Comput. Aided Des. 15, 295-296.
• 20: Josef Hoschek, Approximate conversion of spline curves, Computer Aided Geometric Design, v.4 n.1-2, p.59-66, July 1987 [doi>10.1016/0167-8396(87)90024-0]
• 21: J. Hoschek, Intrinsic parametrization for approximation, Computer Aided Geometric Design, v.5 n.1, p.27-31, June 1988 [doi>10.1016/0167-8396(88)90017-9]
• 22: J. Hoschek, Spline approximation of offset curves, Computer Aided Geometric Design, v.5 n.1, p.33-40, June 1988 [doi>10.1016/0167-8396(88)90018-0]
• 23: Kozo Ichida , Takeshi Kiyono , Fujiichi Yoshimoto, Curve Fitting by a One-Pass Method With a Piecewise Cubic Polynomial, ACM Transactions on Mathematical Software (TOMS), v.3 n.2, p.164-174, June 1977 [doi>10.1145/355732.355737]
• 24: Bert Jüttler, A vegetarian approach to optimal parameterizations, Computer Aided Geometric Design, v.14 n.9, p.887-890, Dec. 1997 [doi>10.1016/S0167-8396(97)00044-7]
• 25: KANSA, E. J. 1990. Multiquadrics: A scattered data approximation scheme with applications to computational fluid dynamics-I. Comput. Math. Appl. 19, 127-145.
• 26: KOSTERS, M. 1991. Curvature-dependent parametrization of curves and surfaces. Comput. Aided Des. 23, 8, 569-578.
• 27: LANCASTER,P.AND SALKAUSKAS, L. 1986. Curve and Surface Fitting. Academic Press, Inc., New York, NY.
• 28: E. T. Y. Lee, Choosing nodes in parametric curve interpolation, Computer-Aided Design, v.21 n.6, p.363-370, July/Aug. 1989 [doi>10.1016/0010-4485(89)90003-1]
• 29: In-Kwon Lee, Curve reconstruction from unorganized points, Computer Aided Geometric Design, v.17 n.2, p.161-177, Feb. 2000 [doi>10.1016/S0167-8396(99)00044-8]
• 30: David Levin, The approximation power of moving least-squares, Mathematics of Computation, v.67 n.224, p.1517-1531, Oct. 1998 [doi>10.1090/S0025-5718-98-00974-0]
• 31: MARIN, S. P. 1984. An approach to data parametrization in parametric cubic spline interpolation problem. J. Approx. Theory 41, 1 (May), 64-86.
• 32: MEINGUET, J. 1979. An intrinsic approach to multivariate spline interpolation at arbitrary points. In Polynomial and Spline Approximation, B. N. Sahney, Ed. D. Reidel Publishing Co., Inc., New York, NY, 163-190.
• 33: MULLINEUX, M. 1982. Approximating shapes using parametrized curves. IMA J. Appl. Math. 29, 203-220.
• 34: L. Piegl, A technique for smoothing scattered data with conic sections, Computers in Industry, v.9 n.3, p.223-238, Nov. 1987 [doi>10.1016/0166-3615(87)90039-X]
• 35: H. Pottmann , T. Randrup, Rotational and helical surface approximation for reverse engineering, Computing, v.60 n.4, p.307-322, 1998 [doi>10.1007/BF02684378]
• 36: M. J. D. Powell, Radial basis functions for multivariable interpolation: a review, Algorithms for approximation, Clarendon Press, New York, NY, 1987
• 37: Biplab Sarkar , Chia-Hsiang Menq, Parameter optimization in approximating curves and surfaces to measurement data, Computer Aided Geometric Design, v.8 n.4, p.267-290, Oct. 1991 [doi>10.1016/0167-8396(91)90016-5]
• 38: SCHAGEN, I. P. 1980. The use of stochastic processes in interpolation and approximation. Int. J. Comput. Math., 63-76.
• 39: Thomas Speer , Markus Kuppe , Josef Hoschek, Global reparametrization for curve approximation, Computer Aided Geometric Design, v.15 n.9, p.869-877, Oct. 1998 [doi>10.1016/S0167-8396(98)00024-7]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
irregularly spaced points, node estimation, noisy point set, parametric curve