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

Wenping Wang*, Helmut Pottmann, Yang Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

299 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)214-238
Number of pages25
JournalACM transactions on graphics
Volume25
Issue number2
DOIs
StatePublished - Apr 2006
Externally publishedYes

Keywords

  • B-spline curve
  • Curve fitting
  • Gauss-Newton method
  • Least squares problem
  • Optimization
  • Point cloud
  • Quasi-Newton method
  • Scatter data approximation
  • Shape reconstruction
  • Squared distance

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Fitting B-spline curves to point clouds by curvature-based squared distance minimization'. Together they form a unique fingerprint.

Cite this