File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleFitting B-spline curves to point clouds by curvature-based squared distance minimization
Authors
KeywordsB-Spline Curve
Curve Fitting
Gauss-Newton Method
Least Squares Problem
Optimization
Point Cloud
Quasi-Newton Method
Scatter Data Approximation
Shape Reconstruction
Squared Distance
Issue Date2006
Citation
Acm Transactions On Graphics, 2006, v. 25 n. 2, p. 214-238 How to Cite?
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.
Persistent Identifierhttp://hdl.handle.net/10722/152338
ISSN
2015 Impact Factor: 4.218
2015 SCImago Journal Rankings: 2.552
ISI Accession Number ID
References

 

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.rightsACM Transactions on Graphics. Copyright © Association for Computing Machinery, Inc.-
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.description.naturelink_to_subscribed_fulltexten_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-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats