||The lead section of this article may need to be rewritten. (August 2014) (Learn how and when to remove this template message)|
In the mathematical subfield of numerical analysis, a B-spline, or basis spline, is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. Any spline function of given degree can be expressed as a linear combination of B-splines of that degree. Cardinal B-splines have knots that are equidistant from each other. B-splines can be used for curve-fitting and numerical differentiation of experimental data.
The term "B-spline" was coined by Isaac Jacob Schoenberg and is short for basis spline. A spline function of order is a piecewise polynomial function of degree in a variable . The places where the pieces meet are known as knots. The key property of spline functions is that they are continuous at the knots. Some derivatives of the spline function may also be continuous, depending on whether the consecutive knots are distinct or not.
B-splines of order are basis functions for spline functions of the same order defined over the same knots, meaning that all possible spline functions can be built from a linear combination of B-splines, and there is only one unique combination for each spline function.
B-spline function is a combination of flexible bands that passes through the number of points that are called control points and creates smooth curves. These functions enable the creation and management of complex shapes and surfaces using a number of points. B-spline function and Bezier functions are applied extensively in shape optimization methods. A B-spline of order is a piecewise polynomial function of degree in a variable . It is defined over locations , called knots or breakpoints, which must be in non-descending order . The B-spline is contributes only in the range between the first and last of these knots and is zero elsewhere. If each knot is separated by the same distance (where ) from its predecessor, the knot vector and the corresponding B-splines are called 'uniform' (see cardinal B-spline below).
For each finite knot interval where it is non-zero, a B-spline is a polynomial of degree . A B-spline is a continuous function at the knots.[note 1] When all knots belonging to the B-spline are distinct, its derivatives are also continuous up to the derivative of degree . If the knots are coincident at a given value of , the continuity of derivative order is reduced by 1 for each additional coincident knot. B-splines may share a subset of their knots, but two B-splines defined over the exact same knots are identical. In other words, a B-spline is uniquely defined by its knots.
One distinguishes internal knots and end points. Internal knots cover the -domain one is interested in. Since a single B-spline already extends over knots, it follows that the internal knots need to be extended with end points on each side, to give full support to the first and last B-spline which affect the internal knot intervals. The values of the endpoints do not matter, usually the first or last internal knot is just repeated.
The usefulness of B-splines lies in the fact that any spline function of order on a given set of knots can be expressed as a linear combination of B-splines:
B-splines play the role of basis functions for the spline function space, hence the name. This property follows from the fact that all pieces have the same continuity properties, within their individual range of support, at the knots.
Expressions for the polynomial pieces can be derived by means of the Cox-de Boor recursion formula
That is, is piecewise constant one or zero indicating which knot span x is in (zero if knot span j is repeated). The recursion equation is in two parts:
ramps from zero to one as x goes from to and
ramps from one to zero as x goes from to . The corresponding Bs are zero outside those respective ranges. For example, is a triangular function that is zero below , ramps to one at and back to zero at and beyond . However, because B-spline basis functions have local support, B-splines are typically computed by algorithms that do not need to evaluate basis functions where they are zero, such as de Boor's algorithm.
This relation leads directly to the FORTRAN-coded algorithm BSPLV which generates values of the B-splines of order n at x. The following scheme illustrates how each piece of order n is a linear combination of the pieces of B-splines of order n-1 to its left.
Application of the recursion formula with the knots at gives the pieces of the uniform B-spline of order 3
These pieces are shown in the diagram. The continuity property of a quadratic spline function and its first derivative at the internal knots are illustrated, as follows
The second derivative of a B-spline of degree 2 is discontinuous at the knots:
A cardinal B-spline has a constant separation, h, between knots. The cardinal B-splines for a given order n are just shifted copies of each other. They can be obtained from the simpler definition.
The "placeholder" notation is used to indicate that the nth divided difference of the function of the two variables t and x is to be taken by fixing x and considering as a function of t alone.
A cardinal B-spline has uniform spaced knots, therefore interpolation between the knots equals convolution with a smoothing kernel.
Example, if we want to interpolate three values in between B-spline nodes (), we can write the signal as:
Convolution of the signal with a rectangle function gives first order interpolated b-spline values. Second-order B-spline interpolation is convolution with a rectangle function twice , by iterative filtering with a rectangle function higher order interpolation is obtained.
Fast b-spline interpolation on a uniform sample domain can be done by iterative mean-filtering. Alternatively, a rectangle function equals Sinc in Fourier domain. Therefore, cubic spline interpolation equals multiplying the signal in Fourier domain with Sinc^4.
See Irwin–Hall distribution#Special cases for algebraic expressions for the cardinal B-splines of degree 1-4.
The term P-spline stands for "penalized B-spline". It refers to using the B-spline representation where the coefficients are determined partly by the data to be fitted, and partly by an additional penalty function that aims to impose smoothness to avoid overfitting.
The derivative of a B-spline of degree k is simply a function of B-splines of degree k-1.
This implies that
which shows that there is a simple relationship between the derivative of a spline function and the B-splines of degree one less.
A piecewise/composite Bézier curve is a series of Bézier curves joined with at least C0 continuity (the last point of one curve coincides with the starting point of the next curve). Depending on the application, additional smoothness requirements (such as C1 or C2 continuity) may be added. C1 continuous curves have identical tangents at the breakpoint (where the two curves meet). C2 continuous curves have identical curvature at the breakpoint.
To gain C2 continuity the Bézier Curve loses local control, because to enforce C2 continuity the control points are dependent on each other. If a single control point moves, the whole spline needs to be re-evaluated. B-Splines have both C2 continuity and local control, but they lose the interpolation property of a piecewise Bézier.
Usually in curve fitting, a set of data points is fitted with a curve defined by some mathematical function. For example, common types of curve fitting use a polynomial or a set of exponential functions. When there is no theoretical basis for choosing a fitting function, the curve may be fitted with a spline function composed of a sum of B-splines, using the method of least squares.[note 2] Thus, the objective function for least squares minimization is, for a spline function of degree k,
W(x) is a weight and y(x) is the datum value at x. The coefficients are the parameters to be determined. The knot values may be fixed or they too may be treated as parameters.
The main difficulty in applying this process is in determining the number of knots to use and where they should be placed. de Boor suggests various strategies to address this problem. For instance, the spacing between knots is decreased in proportion to the curvature (2nd. derivative) of the data. A few applications have been published. For instance, the use of B-splines for fitting single Lorentzian and Gaussian curves has been investigated. Optimal spline functions of degrees 3-7 inclusive, based on symmetric arrangements of 5, 6, and 7 knots, have been computed and the method was applied for smoothing and differentiation of spectroscopic curves. In a comparable study, the two-dimensional version of the Savitzky-Golay filtering and the spline method produced better results than moving average or Chebyshev filtering.
In computer aided design, computer aided manufacturing, and computer graphics, a powerful extension of B-splines is non-uniform rational B-splines (NURBS). NURBS are essentially B-splines in homogeneous coordinates. Like B-splines, they are defined by their order, and a knot vector, and a set of control points, but unlike simple B-splines, the control points each have a weight. When the weight is equal to 1, a NURBS is simply a B-spline and as such NURBS generalizes both B-splines and Bézier curves and surfaces, the primary difference being the weighting of the control points which makes NURBS curves "rational".
By evaluating a NURBS at various values of the parameters, the curve can be traced through space; likewise, by evaluating a NURBS surface at various values of the two parameters, the surface can be represented in Cartesian space.
Like B-splines, NURBS control points determine the shape of the curve. Each point of the curve is computed by taking a weighted sum of a number of control points. The weight of each point varies according to the governing parameter. For a curve of degree d, the influence of any control point is only nonzero in d+1 intervals (knot spans) of the parameter space. Within those intervals, the weight changes according to a polynomial function (basis functions) of degree d. At the boundaries of the intervals, the basis functions go smoothly to zero, the smoothness being determined by the degree of the polynomial.
The knot vector is a sequence of parameter values that determines where and how the control points affect the NURBS curve. The number of knots is always equal to the number of control points plus curve degree plus one. Each time the parameter value enters a new knot span, a new control point becomes active, while an old control point is discarded.
A NURBS curve takes the following form:
Here the notation is as follows. u is the independent variable (instead of x), k is the number of control points, N is a B-spline (used instead of B), n is the polynomial degree, P is a control point and w is a weight. The denominator is a normalizing factor that evaluates to one if all weights are one.
It is customary to write this as
in which the functions
are known as the rational basis functions.
as rational basis functions.
- Strictly speaking B-splines are usually defined as being left-continuous
- de Boor gives FORTRAN routines for least-squares fitting of experimental data.
- de Boor, p. 114
- Gary D. Knott (2000), Interpolating cubic splines. Springer. p. 151
- Talebitooti, R.; shojaeefard, M.H.; Yarmohammadisatri, Sadegh (2015). "Shape design optimization of cylindrical tank using b-spline curves". computer & fluids. 109: 100–112. doi:10.1016/j.compfluid.2014.12.004.
- de Boor, p113.
- de Boor, p 131.
- de Boor, p. 131
- de Boor, p. 134.
- Lee, E. T. Y. (December 1982). "A Simplified B-Spline Computation Routine". Computing. Springer-Verlag. 29 (4): 365–371. doi:10.1007/BF02246763.
- Lee, E. T. Y. (1986). "Comments on some B-spline algorithms". Computing. Springer-Verlag. 36 (3): 229–238. doi:10.1007/BF02240069.
- de Boor, p 322.
- Eilers, P.H.C. and Marx, B.D. (1996). Flexible smoothing with B-splines and penalties (with comments and rejoinder). Statistical Science 11(2): 89-121.
- de Boor, p. 115
- Eugene V. Shikin; Alexander I. Plis (14 July 1995). Handbook on Splines for the User. CRC Press. pp. 96–. ISBN 978-0-8493-9404-1.
- Wernecke, Josie (1993). "8". The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor, Release 2 (1st ed.). Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc. ISBN 0201624958.
- Zorin, Denis (2002), Bezier Curves and B-splines, Blossoming (PDF), New York University, retrieved 4 January 2015
- de Boor, Chapter XIV, p. 235
- Gans, Peter; Gill, J. Bernard (1984). "Smoothing and Differentiation of Spectroscopic Curves Using Spline Functions". Applied Spectroscopy. 38 (3): 370–376. doi:10.1366/0003702844555511.
- Vicsek, Maria; Neal, Sharon L.; Warner, Isiah M. (1986). "Time-Domain Filtering of Two-Dimensional Fluorescence Data". Applied Spectroscopy. 40 (4): 542–548. doi:10.1366/0003702864508773.
- Piegl and Tiller, chapter 4, sec. 2
- Piegl and Tiller, chapter 4, sec. 4
- Carl de Boor (1978). A Practical Guide to Splines. Springer-Verlag. ISBN 3-540-90356-9.
- Piegl, Les; Tiller, Wayne (1997). The NURBS Book (2nd. ed.). Springer. ISBN 3-540-61545-8.
- Richard H. Bartels; John C. Beatty; Brian A. Barsky (1987). An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. Morgan Kaufmann. ISBN 978-1-55860-400-1.
- Jean Gallier (1999). Curves and Surfaces in Geometric Modeling: Theory and Algorithms. Morgan Kaufmann. Chapter 6. B-Spline Curves. This book is out of print and freely available from the author.
- Hartmut Prautzsch; Wolfgang Boehm; Marco Paluszny (2002). Bézier and B-Spline Techniques. Springer Science & Business Media. ISBN 978-3-540-43761-1.
- David Salomon (2006). Curves and Surfaces for Computer Graphics. Springer. Chapter 7. B-Spline Approximation. ISBN 978-0-387-28452-1.