The Unimodality of Initial B-Spline Approximations in Spline Fitting

Abstract

Finding optimal knots is a challenging problem in spline fitting due to a lack of prior knowledge regarding optimal knots. The unimodality of initial B-spline approximations associated with given data is a promising characteristic of locating optimal knots and has been applied successfully. The initial B-spline approximations herein are required to approximate given data well enough and characterized by the unimodality if jumps from the highest-order derivatives of the approximations at some interior knots are local maxima. In this paper, we prove the unimodality of the initial B-spline approximations that are constructed under two assumptions: Data points are sampled uniformly and sufficiently from B-spline functions, and initial knots are chosen as the parameters of sampling points. Our work establishes the theoretical basis of the unimodality of initial B-spline approximations and pioneers the theoretical study of locating optimal knots.

Keywords

Unimodality property / Jumps / Spline fitting / B-spline approximations / Optimal knots

References

[1] Beliakov G. Least squares splines with free knots: global optimization approach. Appl. Math. Comput.. 2004, 149 3 783-798

[2] Brandt, C., Seidel, H.-P., Hildebrandt, K.: Optimal spline approximation via $l_0$-minimization. In: Computer Graphics Forum, vol. 34, pp. 617–626. Wiley Online Library (2015)

[3] Burchard HG. Splines (with optimal knots) are better. Appl. Anal.. 1974, 3 309-319

[4] de Boor C. Good approximation by splines with variable knots. ISNM Spline Funct. Approx. TheoryBirkhäuser Verlag Basel. 1973, 21 57-72

[5] De Boor C. A Practical Guide to Splines. 2001 Berlin: Springer

[6] De Boor, C., Rice J.R.: Least Squares Cubic Spline Approximation, II-Variable Knots. Computer Science Technical Reports, Purdue University, (1968)

[7] Dierckx P. Curve and Surface Fitting with Splines. 1993 New York, NY, USA: Oxford University Press Inc

[8] Jupp DLB. Approximation to data by splines with free knots. SIAM Journal on Numerical Analysis. 1978, 15 2 328-343

[9] Kang H, Chen F, Li Y, Deng J, Yang Z. Knot calculation for spline fitting via sparse optimization. Computer-Aid. Des.. 2015, 58 179-188

[10] Laube, P., Franz, M.O., Umlauf, G.: Learnt knot placement in B-spline curve approximation using support vector machines. Comput. Aid. Geom. Des. 62 (2018)

[11] Lin F, Shen L-Y, Yuan C-M, Mi Z. Certified space curve fitting and trajectory planning for CNC machining with cubic B-splines. Comput.-Aid. Des.. 2019, 106 13-29

[12] Loach P, Wathen A. On the best least squares approximation of continuous functions using linear splines with free knots. IMA J. Numer. Anal.. 1991, 11 393-409

[13] Loock, W.V., Pipeleers, G., Schutter, J.D., Swevers J.: A convex optimization approach to curve fitting with B-splines. In: Preprints of the 18th International Federation of Automatic Control (IFAC), Milano (Italy), pp. 2290–2295 (2011)

[14] Luo J, Kang H, Yang Z. Knot calculation for spline fitting based on the unimodality property. Comput. Aid. Geom. Des.. 2019, 73 54-69

[15] Lyche T, Mørken K. Knot removal for parametric B-spline curves and surfaces. Comput. Aid. Geom. Des.. 1987, 4 217-230

[16] Lyche T, Mørken K. A data reduction strategy for splines with applications to the approximation of functions and data. IMA J. Num. Anal.. 1988, 8 185-208

[17] Ma W, Kruth JP. Parameterization of randomly measured points for least squares fitting of B-spline curves and surfaces. Comput.-Aid. Des.. 1995, 27 9 663-675

[18] Ma W, Kruth JP. NURBS curve and surface fitting for reverse engineering. Int. J. Adv. Manuf. Technol.. 1998, 14 12 918-927

[19] Miyata S, Shen X. Adaptive free-knot splines. J. Comput. Graph. Stat.. 2003, 12 1 197-231

[20] Piegl LA, Tiller W. The NURBS Book. 1997 Heidelberg: Springer

[21] Precioso, F., Barlaud, M., Blu, T., Unser, M.: Smoothing B-spline active contour for fast and robust image and video segmentation. In: International Conference on Image Processing, pp. 137–140. Barcelona, Spain, IEEE (2003)

[22] Randrianarivony, M., Brunnett, G.: Approximation by Nurbs Curves with Free Knots. In: Proceedings of the Vision, Modeling, and Visualization Conference, pp. 195–201. Erlangen, Germany (2002)

[23] Rice, J.R.: On the degree of convergence of nonlinear spline approximation. In: Proceedings of Symposium on Approximation Theory (Madison, WI), vol. 31, pp. 349–365. I. J. Schoenberg, ed., Academic Press, New York (1969)

[24] Unser M, Aldroubi A, Eden M. B-spline signal processing II. Efficiency design and applications. IEEE Trans. Sig. Process.. 1993, 41 2 834-848

[25] Yang Z, Shen L-Y, Yuan C-M, Gao X-S. Curve fitting and optimal interpolation for CNC machining under confined error using quadratic B-splines. Comput.-Aid. Des.. 2015, 66 62-72

[26] Yuan Y, Chen N, Zhou S. Adaptive B-spline knots selection using multi-resolution basis set. IIE Trans.. 2013, 45 12 1263-1277

Funding

National Natural Science Foundation of China(11801393)

Natural Science Foundation of Jiangsu Province(BK20180831)