Fitting B-spline curves to point clouds by curvature-based squared distance minimization

Abstract

Computing a curve to approximate data points is a problem encountered frequently in many applications in computer graphics, computer vision, CAD/CAM, and image processing. We present a novel and efficient method, called squared distance minimization (SDM), for computing a planar B-spline curve, closed or open, to approximate a target shape defined by a point cloud, that is, a set of unorganized, possibly noisy data points. We show that SDM significantly outperforms other optimization methods used currently in common practice of curve fitting. In SDM, a B-spline curve starts from some properly specified initial shape and converges towards the target shape through iterative quadratic minimization of the fitting error. Our contribution is the introduction of a new fitting error term, called the squared distance (SD) error term, defined by a curvature-based quadratic approximant of squared distances from data points to a fitting curve. The SD error term faithfully measures the geometric distance between a fitting curve and a target shape, thus leading to faster and more stable convergence than the point distance (PD) error term, which is commonly used in computer graphics and CAGD, and the tangent distance (TD) error term, which is often adopted in the computer vision community. To provide a theoretical explanation of the superior performance of SDM, we formulate the B-spline curve fitting problem as a nonlinear least squares problem and conclude that SDM is a quasi-Newton method which employs a curvature-based positive definite approximant to the true Hessian of the objective function. Furthermore, we show that the method based on the TD error term is a Gauss-Newton iteration, which is unstable for target shapes with high curvature variations, whereas optimization based on the PD error term is the alternating method that is known to have linear convergence.

References

1. Ambrosio, L. and Montegazza, C. 1998. Curvature and distance function from a manifold. J. Geomet. Analy. 8, 723--748.
2. Bercovier, M. and Jacob, M. 1994. Minimization, constraints and composite bézier curves. Comput. Aided Geomet. Design 11, 533--563.
3. Bjorck, A. 1996. Numerical Methods for Least Squares Problems. Mathematics Society for Industrial and Applied Mathematics, Philadelphia, PA.
4. Blake, A. and Isard, M. 1998. Active Contours. Springer Verlag, New York, NY.
5. Djebali, M., Melkemi, M., and Sapidis, N. 2002. Range-image segmentation and model reconstruction based on a fit-and-merge strategy. In Proceedings of the 7th ACM Symposium on Solid Modeling and Applications. 127--138.
6. Farin, G. 1997. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide, 4th Ed. Academic Press, New York, NY.
7. Forsey, D. R. and Bartels, R. H. 1995. Surface fitting with hierarchical splines. ACM Trans. Graph. 14, 134--161.
8. Goldenthal, R. and Bercovier, M. 2004. Spline curve approximation and design by optimal control over the knots. Computing 72, 53--64.
9. Goshtasby, A. A. 2000. Grouping and parameterizing irregularly spaced points for curve fitting. ACM Trans. Graph. 19, 185--203.
10. Greiner, G., Kolb, A., and Riepl, A. 2002. Scattered data interpolation using data dependant optimization techniques. Graphical Models 64, 1--18.
11. Haber, J., Zeilfelder, F., Davydov, O., and Seidel, H. P. 2001. Smooth approximation and rendering of large scattered data sets. In Proceedings of Visualization. 341--348.
12. Hoppe, H. 1996. Progressive meshes. In Proceedings of SIGGRAPH. 99--108.
13. Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., and Stuetzle, W. 1994. Piecewise smooth surface reconstruction. In Proceedings of SIGGRAPH. 295--302.
14. Hoschek, J. 1988. Intrinsic parameterization for approximation. Comput. Aided Geomet. Design 5, 27--31.
15. Hoschek, J. and Lasser, D. 1993. Fundamentals of Computer Aided Geometric Design. AK Peters.
16. Hu, S. M. and Wallner, J. 2005. Second order algorithm for orthogonal projection onto curves and surfaces. Comput. Aided Geomet. Design 22, 251--260.
17. Kass, M., Witkin, A., and Terzopoulos, D. 1988. Snakes: Active contour models. Int. J. Comput. Vision 1, 321--331.
18. Kelley, C. T. 1999. Iterative Methods for Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA.
19. Laurent-Gengoux, P. and Mekhilef, M. 1993. Optimization of a nurbs representation. Comput.-aided Design 25, 699--710.
20. Lee, E. T. Y. 1989. Choosing nodes in parametric curve interpolation. Comput.-aided Design 21, 363--370.
21. Luenberger, D. 1984. Linear and Nonlinear Programming. Addision-Wesley.
22. Ma, W. Y. and Kruth, J. P. 1995. Parameterization of randomly measured points for least squares fitting of b-spline curves and surfaces. Comput.-aided Design 27, 663--675.
23. Maekawa, I. and Ko, K. 2002. Surface construction by fitting unorganized curves. Graphical Models 64, 316--332.
24. Malladi, R., Sethian, J., and Vemuri, B. C. 1995. Shape modeling with front propagation: A level set approach. IEEE Trans. Pattern Analy. Mach. Intell. 17, 158--175.
25. Osher, S. and Fedkiw. 2003. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag, New York, NY.
26. Pavlidis, T. 1983. Curve fitting with conic splines. ACM Trans. Graph. 2, 1--31.
27. Plass, M. and Stone, M. 1983. Curve-fitting with piecewise parametric cubics. Comput. Graphics 17, 3, 229--239.
28. Pottmann, H. and Hofer, M. 2003. Geometry of the squared distance function to curves and surfaces. In Visualization and Mathematics III, H. Hege and K. Polthier, Eds. 223--244.
29. Pottmann, H., Leopoldseder, S., and Hofer, M. 2002. Approximation with active b-spline curves and surfaces. In Proceedings of Pacific Graphics. IEEE Computer Society Press, 8--25.
30. Pottmann, H. and Wallner, J. 2001. Computational Line Geometry. Springer-Verlag, Berlin, Germany.
31. Pratt, V. 1985. Techniques for conic splines. In Proceedings of SIGGRAPH. 151--160.
32. Ruhe, A. and Wedin, P. 1980. Algorithms for separable nonlinear least squares problems. SIAM Rev. 22, 318--337.
33. Sarkar, B. and Menq, C.-H. 1991. Parameter optimization in approximating curves and surfaces to measurement data. Comput. Aided Geomet. Design 8, 267--290.
34. Saux, E. and Daniel, M. 2003. An improved hoschek intrinsic parametrization. Comput. Aided Geomet. Design 20, 513--521.
35. Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press, Cambridge, UK.
36. Speer, T., Kuppe, M., and Hoschek, J. 1998. Global reparameterization for curve approximation. Comput. Aided Geomet. Design 15, 869--877.
37. Taubin, G. 2002. Dual mesh resampling. Graphical Models 64, 94--113.
38. Walton, D. J. and Xu, R. 1991. Turning point preserving planar interpolation. ACM Trans. Graph. 10, 297--311.
39. Wang, X. C. and Phillips, C. 2002. Multi-weight enveloping: least-squares approximation techniques for skin animation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 129--138.
40. Weiss, V., Andor, L., Renner, G., and Varady, T. 2002. Advanced surface fitting techniques. Comput.-Aided Geomet. Design 19, 19--42.
41. Yang, H. P., Wang, W., and Sun, J. G. 2004. Control point adjustment for b-spline curve approximation. Comput.-aided Design 36, 639--652.

Index Terms

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization