Fitting B-spline curves to point clouds by 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*, i.e., a set
of unorganized, possibly noisy data points. We show that SDM outperforms significantly 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
measures faithfully 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.

Bibtex:

@INPROCEEDINGS{wpl_curves_06, AUTHOR = "W. Wang and H. Pottmann and Y. Liu", TITLE = "Fitting B-spline curves to point clouds by squared distance minimization", BOOKTITLE = " ACM Trans. Graphics", VOLUME = "25", PAGES = "214--238", YEAR = "2006", }