There are no files associated with this item.

##### Supplementary
• Bookmarks:
• CiteULike: 1
• Appears in Collections:

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

Title Fitting B-spline curves to point clouds by curvature-based squared distance minimization Wang, WPottmann, HLiu, Y B-Spline CurveCurve FittingGauss-Newton MethodLeast Squares ProblemOptimizationPoint CloudQuasi-Newton MethodScatter Data ApproximationShape ReconstructionSquared Distance 2006 Acm Transactions On Graphics, 2006, v. 25 n. 2, p. 214-238 How to Cite? 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. © 2006 ACM. http://hdl.handle.net/10722/152338 0730-03012015 Impact Factor: 4.2182015 SCImago Journal Rankings: 2.552 WOS:000238447200003 References in Scopus

DC FieldValueLanguage
dc.contributor.authorWang, Wen_US
dc.contributor.authorPottmann, Hen_US
dc.contributor.authorLiu, Yen_US
dc.date.accessioned2012-06-26T06:37:18Z-
dc.date.available2012-06-26T06:37:18Z-
dc.date.issued2006en_US
dc.identifier.citationAcm Transactions On Graphics, 2006, v. 25 n. 2, p. 214-238en_US
dc.identifier.issn0730-0301en_US
dc.identifier.urihttp://hdl.handle.net/10722/152338-
dc.description.abstractComputing 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. © 2006 ACM.en_US
dc.languageengen_US
dc.relation.ispartofACM Transactions on Graphicsen_US
dc.subjectB-Spline Curveen_US
dc.subjectCurve Fittingen_US
dc.subjectGauss-Newton Methoden_US
dc.subjectLeast Squares Problemen_US
dc.subjectOptimizationen_US
dc.subjectPoint Clouden_US
dc.subjectQuasi-Newton Methoden_US
dc.subjectScatter Data Approximationen_US
dc.subjectShape Reconstructionen_US
dc.subjectSquared Distanceen_US
dc.titleFitting B-spline curves to point clouds by curvature-based squared distance minimizationen_US
dc.typeArticleen_US
dc.identifier.emailWang, W:wenping@cs.hku.hken_US
dc.identifier.authorityWang, W=rp00186en_US
dc.identifier.doi10.1145/1138450.1138453en_US
dc.identifier.scopuseid_2-s2.0-33745771700en_US
dc.identifier.hkuros141115-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33745771700&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume25en_US
dc.identifier.issue2en_US
dc.identifier.spage214en_US
dc.identifier.epage238en_US
dc.identifier.eissn1557-7368-
dc.identifier.isiWOS:000238447200003-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridWang, W=35147101600en_US
dc.identifier.scopusauthoridPottmann, H=7003351050en_US
dc.identifier.scopusauthoridLiu, Y=27172089200en_US
dc.identifier.citeulike2461073-