Knot calculation for spline fitting via sparse optimization. (January 2015)

• Record Type: Journal Article
• Authors: Kang, Hongmei; Chen, Falai; Li, Yusheng; Deng, Jiansong; Yang, Zhouwang
• Is Part Of: Computer aided design. Volume 58(2015)
• Page Start: 179
• Page End: 188
• Publication Date: 2015-01
• Subjects: Spline fitting -- Knot calculation -- Sparse optimization; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2014.08.022
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Curve fitting with splines is a fundamental problem in computer-aided design and engineering. However, how to choose the number of knots and how to place the knots in spline fitting remain a difficult issue. This paper presents a framework for computing knots (including the number and positions) in curve fitting based on a sparse optimization model. The framework consists of two steps: first, from a dense initial knot vector, a set of active knots is selected at which certain order derivative of the spline is discontinuous by solving a sparse optimization problem; second, we further remove redundant knots and adjust the positions of active knots to obtain the final knot vector. Our experiments show that the approximation spline curve obtained by our approach has less number of knots compared to existing methods. Particularly, when the data points are sampled dense enough from a spline, our algorithm can recover the ground truth knot vector and reproduce the spline. Highlights: We reduce the computation time dramatically by solving convex optimization problem. We can simultaneously find a good combination of the knot number and knot locations. The algorithm has less knots with good fitting performance compared to other methods. We can recover the ground truth knots when data is sampled enough from a B-spline.