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.
In computer-aided design and computer graphics, spline functions are constructed as linear combinations of B-splines with a set of control points.
According to Gerald Farin, B-splines were explored as early as the nineteenth century by Nikolai Lobachevsky at Kazan University in Russia.[1] The term "B-spline" was coined by Isaac Jacob Schoenberg[2] in 1978 and is short for basis spline.[3] A spline function of order
n
n-1
B-splines of order
n
A B-spline of order
p+1
Bi,p(t)
p
t
t
t0,t1,t2,\ldots,tm
For a given sequence of knots, there is, up to a scaling factor, a unique spline
Bi,p(t)
Bi,p(t)=\begin{cases} non-zero&ifti\leqt<ti+p+1,\\ 0&otherwise. \end{cases}
If we add the additional constraint that
m-p-1 | |
\sum | |
i=0 |
Bi,p(t)=1
t
tp
tm-p
Bi,p(t)
tp
tm-p
B-splines can be constructed by means of the Cox–de Boor recursion formula. We start with the B-splines of degree
p=0
Bi,0(t):=\begin{cases} 1&ifti\leqt<ti+1,\\ 0&otherwise. \end{cases}
The higher
(p+1)
Bi,p(t):=\dfrac{t-ti}{ti+p-ti}Bi,p-1(t)+\dfrac{ti+p+1-t}{ti+p+1-ti+1
A B-spline function is a combination of flexible bands that is controlled by a number of points that are called control points, creating smooth curves. These functions are used to create and manage complex shapes and surfaces using a number of points. B-spline function and Bézier functions are applied extensively in shape optimization methods.[5]
A B-spline of order
n
n-1
x
1+n
tj
tj\leqtj+1
h
h=tj+1-tj
For each finite knot interval where it is non-zero, a B-spline is a polynomial of degree
n-1
n-2
x
One distinguishes internal knots and end points. Internal knots cover the
x
1+n
n-1
The usefulness of B-splines lies in the fact that any spline function of order
n
Sn,t(x)=\sumi\alphaiBi,n(x).
Expressions for the polynomial pieces can be derived by means of the Cox–de Boor recursion formula[8]
Bi,0(x):=\begin{cases} 1&ifti\leqx<ti+1,\\ 0&otherwise. \end{cases}
Bi,k(x):=
x-ti | |
ti+k-ti |
Bi,k-1(x)+
ti+k+1-x | |
ti+k+1-ti+1 |
Bi+1,k-1(x).
That is,
Bj,0(x)
x-ti | |
ti+k-ti |
ti
ti+k
ti+k+1-x | |
ti+k+1-ti+1 |
ti+1
ti+k+1
Bi,1(x)
x=ti
x=ti+1
x=ti+2
This relation leads directly to the FORTRAN-coded algorithm BSPLV, which generates values of the B-splines of order n at x.[9] 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.
\begin{matrix} &&0\\ &0&\\ 0&&Bi-2,2\\ &Bi-1,1&\\ Bi,0&&Bi-1,2\\ &Bi,1&\\ 0&&Bi,2\\ &0&\\ &&0 \end{matrix}
Application of the recursion formula with the knots at
(0,1,2,3)
\begin{align} B1&=x2/2,&0&\lex<1,\\ B2&=(-2x2+6x-3)/2,&1&\lex<2,\\ B3&=(3-x)2/2,&2&\lex<3. \end{align}
\begin{align} &Atx=1\colon B1=B2=0.5,
dB1 | |
dx |
=
dB2 | |
dx |
=1.\\[6pt] &Atx=2\colon B2=B3=0.5,
dB2 | |
dx |
=
dB3 | |
dx |
=-1. \end{align}
| |||||||
dx2 |
=1,
| |||||||
dx2 |
=-2,
| |||||||
dx2 |
=1.
Faster variants of the de Boor algorithm have been proposed, but they suffer from comparatively lower stability.[10] [11]
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.[12]
Bi,n,t(x)=
x-ti | |
h |
n[0,...,n]( ⋅ -
n-1 | |
t | |
+. |
The "placeholder" notation is used to indicate that the n-th divided difference of the function
n-1 | |
(t-x) | |
+ |
(t-
n-1 | |
x) | |
+ |
A cardinal B-spline has uniformly 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 (
bf{b}
x=[b1,0,0,b2,0,0,b3,0,0,...,bn,0,0].
Convolution of the signal
x
h=[1/3,1/3,1/3]
y=x*h*h
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 sinc4.
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.[13]
Two- and multidimensional P-spline approximations of data can use the face-splitting product of matrices to the minimization of calculation operations.[14]
The derivative of a B-spline of degree k is simply a function of B-splines of degree k − 1:[15]
dBi,k(x) | |
dx |
=k\left(
Bi,k-1(x) | |
ti+k-ti |
-
Bi+1,k-1(x) | |
ti+k+1-ti+1 |
\right).
d | |
dx |
\sumi\alphaiBi,k=
s-1 | ||
\sum | k | |
i=r-k+2 |
\alphai-\alphai-1 | |
ti+k-ti |
Bi,k-1 on [tr,ts],
Univariate B-splines, i.e. B-splines where the knot positions lie in a single dimension, can be used to represent 1-d probability density functions
p(x)
i
n
p(x)=\sumici ⋅ Bi,n,bf{norm
and with normalization constant constraint
\sumici=1
\muk
Bi,n,bf{norm
Rk
\muk=Rk(m;t)=
infty | |
\int | |
-infty |
xk ⋅ Bi,n,bf{norm
with
Dk=
1 | |
k |
k | |
\sum\limits | |
u=1 |
j | |
\left[\left(\sum\limits | |
i=1 |
mi ⋅
u | |
{t | |
i} |
\right)Dk-u\right]
D0=1
t
j
m
p(x)
A Bézier curve is also a polynomial curve definable using a recursion from lower-degree curves of the same class and encoded in terms of control points, but a key difference is that all terms in the recursion for a Bézier curve segment have the same domain of definition (usually
[0,1]
n
m\ggn
m/n
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.[18] C1 continuous curves have identical tangents at the breakpoint (where the two curves meet). C2 continuous curves have identical curvature at the breakpoint.[19]
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.[20] [21] Thus, the objective function for least-squares minimization is, for a spline function of degree k,
U=\sumall~x\left\{W(x)\left[y(x)-\sumi\alphaiBi,k,t(x)\right]\right\}2,
\alphai
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.[22] 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.[23]
In computer-aided design and computer graphics applications, a spline curve is sometimes represented as
C(t)
t
C(t)
(x(t),y(t))
(x(t),y(t),z(t))
x(t)
y(t)
z(t)
t1,t2,\ldots,tn
Because a B-splines form basis functions, each of the coordinate functions can be expressed as a linear sum of B-splines, so we have
\begin{align} X(t)&=\sumixiBi,n(t),\\ Y(t)&=\sumiyiBi,n(t),\\ Z(t)&=\sumiziBi,n(t). \end{align}
The weights
xi
yi
zi
Pi=(xi,yi,zi)
Pi
Working in reverse, a sequence of control points, knot values, and order of the B-spline define a parametric curve. This representation of a curve by control points has several useful properties:
Pi
\sumiBi,n(x)=1
Bi,n(x)\geq0
A less desirable feature is that the parametric curve does not interpolate the control points. Usually the curve does not pass through the control points.
A cubic B-spline curve
C(t)
t\in[0,1]
bf{b}0
bf{b}1
bf{b}2
bf{b}3
C(t)=
1 | |
6 |
\begin{bmatrix}t3&t2&t&1\end{bmatrix}\begin{bmatrix} -1&3&-3&1\\ 3&-6&3&0\\ -3&0&3&0\\ 1&4&1&0 \end{bmatrix}\begin{bmatrix}b0\\b1\\b2\\b3\end{bmatrix}
\begin{align} B0(t)&=
1 | |
6 |
(-t3+3t2-3t+1)\\ B1(t)&=
1 | |
6 |
(3t3-6t2+4)\\ B2(t)&=
1 | |
6 |
(-3t3+3t2+3t+1)\\ B3(t)&=
1 | |
6 |
t3 \end{align}
C(t)=
3 | |
\sum | |
i=0 |
Bi(t)bi
C(t)=
1 | |
6 |
l((-b0+3b1-3b2+b3)t3 +(3b0-6b1+3b2)t2 +(-3b0+3b2)t+(b0+4b1+b2)r)
bf{P}0
bf{P}1
bf{P}2
bf{P}3
\begin{align} P0&=
1 | |
6 |
(b0+4b1+b2),\\ P1&=
1 | |
3 |
(2b1+b2),\\ P2&=
1 | |
3 |
(b1+2b2),\\ P3&=
1 | |
6 |
(b1+4b2+b3). \end{align}
See main article: Non-uniform rational B-spline.
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:[24]
C(u)=
| ||||||||||
|
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
k | |
C(u)=\sum | |
i=1 |
Ri,n(u)Pi
in which the functions
Ri,n(u)=
Ni,n(u)wi | |||||||||
|
are known as the rational basis functions.
A NURBS surface is obtained as the tensor product of two NURBS curves, thus using two independent parameters u and v (with indices i and j respectively):[25]
S(u,v)=
k | |
\sum | |
i=1 |
\ell | |
\sum | |
j=1 |
Ri,j(u,v)Pi,j
with
Ri,j(u,v)=
Ni,n(u)Nj,m(v)wi,j | |||||||||||||||
|
as rational basis functions.
Works cited