HOME

TheInfoList



OR:

In the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
subfield of
numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
, a B-spline or basis spline is a spline function that has minimal support with respect to a given
degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...
, smoothness, and
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function * Do ...
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 In numerical analysis, numerical differentiation algorithms estimate the derivative of a mathematical function or function subroutine using values of the function and perhaps other knowledge about the function. Finite differences The simp ...
of experimental data. In computer-aided design and
computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
, spline functions are constructed as linear combinations of B-splines with a set of control points.


Introduction

The
term Term may refer to: * Terminology, or term, a noun or compound word used in a specific context, in particular: **Technical term, part of the specialized vocabulary of a particular field, specifically: ***Scientific terminology, terms used by scient ...
"B-spline" was coined by
Isaac Jacob Schoenberg Isaac Jacob Schoenberg (April 21, 1903 – February 21, 1990) was a Romanian-American mathematician, known for his invention of splines. Life and career Schoenberg was born in Galați. He studied at the University of Iași, receiving his ...
and is short for basis spline. A spline function of order n is a
piecewise In mathematics, a piecewise-defined function (also called a piecewise function, a hybrid function, or definition by cases) is a function defined by multiple sub-functions, where each sub-function applies to a different interval in the domain. P ...
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
function of degree n - 1 in a variable x. The places where the pieces meet are known as knots. The key property of spline functions is that they and their derivatives may be continuous, depending on the multiplicities of the knots. B-splines of order n 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.


Definition

A spline of order n is a
piecewise In mathematics, a piecewise-defined function (also called a piecewise function, a hybrid function, or definition by cases) is a function defined by multiple sub-functions, where each sub-function applies to a different interval in the domain. P ...
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
function of degree n-1 in a variable x. The values of x where the pieces of polynomial meet are known as knots, denoted t_0, t_1, t_2, \ldots, t_n and sorted into nondecreasing order. When the knots are distinct, the first n-2 derivatives of the polynomial pieces are continuous across each knot. When r knots are coincident, then only the first n-r-1 derivatives of the spline are continuous across that knot. For a given sequence of knots, there is, up to a scaling factor, a unique spline B_(x) satisfying :B_(x) = \begin 0 & \text x < t_i \text x \geq t_, \\ \text & \text. \end If we add the additional constraint that \sum_i B_(x) = 1 for all x between the first and last knot, then the scaling factor of B_(x) becomes fixed. The resulting B_(x) spline functions are called B-splines. Alternatively, B-splines can be defined by construction by means of the Cox–de Boor recursion formula. Given a knot sequence \ldots, t_0, t_1, t_2, \ldots, the B-splines of order 1 are defined by :B_(x) := \begin 1 & \text t_i \leq x < t_, \\ 0 & \text. \end These satisfy \sum_i B_(x) = 1 for all x because for any x exactly one of the B_(x) = 1, and all the others are zero. The higher-order B-splines are defined by recursion :B_(x) := \omega_(x) B_(x) + -\omega_(x)B_(x), where :\omega_(x) := \begin \dfrac, & t_ \neq t_i, \\ 0 & \text. \end


Properties

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. A B-spline of order n is a piecewise polynomial function of degree n - 1 in a variable x. It is defined over 1 + n locations t_j, called knots or breakpoints, which must be in non-descending order t_j \leq t_. The B-spline 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 h (where h = t_ - t_j) 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 n - 1. A B-spline is a continuous function at the knots.Strictly speaking, B-splines are usually defined as being left-continuous. When all knots belonging to the B-spline are distinct, its derivatives are also continuous up to the derivative of degree n - 2. If the knots are coincident at a given value of x, 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 exactly the 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 x-domain one is interested in. Since a single B-spline already extends over 1 + n knots, it follows that the internal knots need to be extended with n - 1 endpoints 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 n on a given set of knots can be expressed as a linear combination of B-splines: : S_(x) = \sum_i \alpha_i B_(x). 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 :B_(x) := \begin 1 & \text t_i \leq x < t_, \\ 0 & \text. \end :B_(x) := \frac B_(x) + \frac B_(x). That is, B_(x) 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: :\frac ramps from zero to one as ''x'' goes from t_i to t_, and :\frac ramps from one to zero as ''x'' goes from t_ to t_. The corresponding ''B''s are zero outside those respective ranges. For example, B_(x) is a
triangular function A triangular function (also known as a triangle function, hat function, or tent function) is a function whose graph takes the shape of a triangle. Often this is an isosceles triangle of height 1 and base 2 in which case it is referred to as ''th ...
that is zero below x = t_i, ramps to one at x = t_ and back to zero at and beyond x = t_. 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 In the mathematical subfield of numerical analysis de Boor's algorithmC. de Boor 971 "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121. is a polynomial-time and numerically sta ...
. 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. : \begin & & 0 \\ & 0 & \\ 0 & & B_ \\ & B_ & \\ B_ & & B_\\ & B_ & \\ 0 & & B_ \\ & 0 & \\ & & 0 \end Application of the recursion formula with the knots at (0, 1, 2, 3) gives the pieces of the uniform B-spline of order 3 : \begin B_1 &= x^2/2, & 0 &\le x < 1, \\ B_2 &= (-2x^2 + 6x - 3)/2, & 1 &\le x < 2, \\ B_3 &= (3 - x)^2/2, & 2 &\le x < 3. \end 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 : \begin & \textx = 1\colon\ B_1 = B_2 = 0.5,\ \frac = \frac = 1. \\ pt& \textx = 2\colon\ B_2 = B_3 = 0.5,\ \frac = \frac = -1. \end The second derivative of a B-spline of degree 2 is discontinuous at the knots: : \frac = 1,\ \frac = -2,\ \frac = -1. Faster variants of the de Boor algorithm have been proposed, but they suffer from comparatively lower stability.


Cardinal B-spline

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. :B_(x) = \frac n , \dots, n\cdot - t_i)^_+. The "placeholder" notation is used to indicate that the ''n''-th
divided difference In mathematics, divided differences is an algorithm, historically used for computing tables of logarithms and trigonometric functions. Charles Babbage's difference engine, an early mechanical calculator, was designed to use this algorithm in it ...
of the function (t-x)^_+ of the two variables ''t'' and ''x'' is to be taken by fixing ''x'' and considering (t - x)^_+ as a function of ''t'' alone. 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 (\textbf), we can write the signal as : \mathbf = mathbf_1, 0, 0, \mathbf_2, 0, 0, \mathbf_3, 0, 0, \dots, \mathbf_n, 0, 0 Convolution of the signal \mathbf with a rectangle function \mathbf = /3, 1/3, 1/3/math> gives first order interpolated B-spline values. Second-order B-spline interpolation is convolution with a rectangle function twice \mathbf = \mathbf * \mathbf * \mathbf; 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 mathematics, physics and engineering, the sinc function, denoted by , has two forms, normalized and unnormalized.. In mathematics, the historical unnormalized sinc function is defined for by \operatornamex = \frac. Alternatively, the u ...
in
Fourier domain In physics, electronics, control systems engineering, and statistics, the frequency domain refers to the analysis of mathematical functions or signals with respect to frequency, rather than time. Put simply, a time-domain graph shows how a sig ...
. 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.


P-spline

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 Penalty methods are a certain class of algorithms for solving constrained optimization problems. A penalty method replaces a constrained optimization problem by a series of unconstrained problems whose solutions ideally converge to the solution of ...
that aims to impose smoothness to avoid overfitting. Two- and multidimensional P-spline approximations of data can use the face-splitting product of matrices to the minimization of calculation operations.


Derivative expressions

The derivative of a B-spline of degree ''k'' is simply a function of B-splines of degree ''k'' − 1: :\frac = k\left(\frac - \frac\right). This implies that :\frac \sum_i \alpha_i B_ = \sum_^ k\fracB_ \quad \text \quad _r, t_s which shows that there is a simple relationship between the derivative of a spline function and the B-splines of degree one less.


Moments of univariate B-splines

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). An example is a weighted sum of i B-spline basis functions of order n, which each are area-normalized to unity (i.e. not directly evaluated using the standard de-Boor algorithm) : p(x) = \sum_i c_i \cdot B_(x) and with normalization constant constraint \sum_i c_i = 1. The ''k''-th raw moment \mu_k of a normalized B-spline B_ can be written as Carlson's Dirichlet average R_k, which in turn can be solved exactly via a contour integral and an iterative sum as : \mu_k = R_k(\mathbf;\mathbf) = \int_^\infty x^k \cdot B_(x\mid t_1 \dots t_j) \, dx = \frac \cdot D_k(\mathbf,\mathbf) with : D_k= \frac\sum\limits_^k \left left(\sum\limits_^j m_i \cdot ^u \right) D_\right and D_0=1. Here, \mathbf represents a vector with the j knot positions and \mathbf a vector with the respective knot multiplicities. One can therefore calculate any moment of a probability density function p(x) represented by a sum of B-spline basis functions exactly, without resorting to numerical techniques.


Relationship to piecewise/composite Bézier

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
, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
/math>), whereas the supports of the two terms in the B-spline recursion are different (the outermost subintervals are not common). This means that a Bézier curve of degree n given by m \gg n control points consists of about m/n mostly independent segments, whereas the B-spline with the same parameters smoothly transitions from subinterval to subinterval. To get something comparable from a Bézier curve, one would need to impose a smoothness condition on transitions between segments, resulting in some manner of Bézier spline (for which many control points would be determined by the smoothness requirement). 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.


Curve fitting

Usually in
curve fitting Curve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data i ...
, 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 function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...
s. 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.de Boor gives FORTRAN routines for least-squares fitting of experimental data. Thus, the
objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
for least-squares minimization is, for a spline function of degree ''k'', : U = \sum_ \left\^2, where ''W''(''x'') is a weight, and ''y''(''x'') is the datum value at ''x''. The coefficients \alpha_i are the parameters to be determined. The knot values may be fixed or 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 Carl Friedrich Gauss (1777–1855) is the eponym of all of the topics listed below. There are over 100 topics all named after this German mathematician and scientist, all in the fields of mathematics, physics, and astronomy. The English eponymo ...
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 filter A Savitzky–Golay filter is a digital filter that can be applied to a set of digital data points for the purpose of smoothing the data, that is, to increase the precision of the data without distorting the signal tendency. This is achieved, in ...
ing and the spline method produced better results than
moving average In statistics, a moving average (rolling average or running average) is a calculation to analyze data points by creating a series of averages of different subsets of the full data set. It is also called a moving mean (MM) or rolling mean and is ...
or
Chebyshev filter Chebyshev filters are analog or digital filters that have a steeper roll-off than Butterworth filters, and have either passband ripple (type I) or stopband ripple (type II). Chebyshev filters have the property that they minimize the error betwee ...
ing.


Computer-aided design and computer graphics

In computer-aided design and
computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
applications, a spline curve is sometimes represented as C(t), a parametric curve of some real parameter t. In this case the curve C(t) can be treated as two or three separate coordinate functions (x(t), y(t)), or (x(t), y(t), z(t)). The coordinate functions x(t), y(t) and z(t) are each spline functions, with a common set of knot values t_1, t_2, \ldots, t_n. 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 X(t) &= \sum_i x_i B_(t), \\ Y(t) &= \sum_i y_i B_(t), \\ Z(t) &= \sum_i z_i B_(t). \end The weights x_i, y_i and z_i can be combined to form points P_i=(x_i,y_i,z_i) in 3-d space. These points P_i are commonly known as control points. 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: # The control points P_i define a curve. If the control points are all transformed together in some way, such as being translated, rotated, scaled, or moved by any affine transformation, then the corresponding curve is transformed in the same way. # Because the B-splines are non-zero for just a finite number of knot intervals, if a single control point is moved, the corresponding change to the parametric curve is just over the parameter range of a small number knot intervals. # Because \sum_i B_(x) = 1, and at all times each B_(x) \geq 0, then the curve remains inside the bounding box of the control points. Also, in some sense, the curve broadly follows the control points. 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.


NURBS

In computer aided design,
computer aided manufacturing Computer-aided manufacturing (CAM) also known as computer-aided modeling or computer-aided machining is the use of software to control machine tools in the manufacturing of work pieces. This is not the only definition for CAM, but it is the most ...
, and
computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
, a powerful extension of B-splines is non-uniform rational B-splines (NURBS). NURBS are essentially B-splines in
homogeneous coordinates In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. ...
. 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: : C(u) = \frac 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 : C(u)=\sum_^k R_(u)P_i in which the functions : R_(u) = \frac are known as the rational basis functions. A NURBS surface is obtained as the
tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
of two NURBS curves, thus using two independent parameters ''u'' and ''v'' (with indices ''i'' and ''j'' respectively):Piegl and Tiller, chapter 4, sec. 4 : S(u,v) = \sum_^k \sum_^\ell R_(u,v) P_ with : R_(u,v) = \frac as rational basis functions.


See also

* Bézier curve *
Box spline In the mathematical fields of numerical analysis and approximation theory, box splines are piecewise polynomial functions of several variables. Box splines are considered as a multivariate generalization of basis splines (B-splines) and are gene ...
*
De Boor algorithm In the mathematical subfield of numerical analysis de Boor's algorithmC. de Boor 971 "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121. is a polynomial-time and numerically st ...
*
I-spline In the mathematical subfield of numerical analysis, an I-spline is a monotone spline function. Definition A family of ''I-spline'' functions of degree ''k'' with ''n'' free parameters is defined in terms of the M-splines ''M'i''(''x'', ''k' ...
*
M-spline In the mathematical subfield of numerical analysis, an M-spline is a non-negative spline function. Definition A family of ''M-spline'' functions of order ''k'' with ''n'' free parameters is defined by a set of knots ''t''1  ≤ ''t''2 ...
*
Spline wavelet In the mathematics, mathematical theory of wavelets, a spline wavelet is a wavelet constructed using a spline function. There are different types of spline wavelets. The interpolatory spline wavelets introduced by C.K. Chui and J.Z. Wang are based ...
* T-spline


Notes


References

Works cited * *


Further reading

* * This book is out of print and freely available from the author. * * * Hovey, Chad (2022). Formulation and Python Implementation of Bézier and B-Spline Geometry
SAND2022-7702C
(153 pages)


External links

* * {{cite web , url=http://www.oxford-man.ox.ac.uk/~jruf/papers/ruf_bspline.pdf , title=B-splines of third order on a non-uniform grid , first1=Johannes , last1=Ruf , access-date=2012-05-02 , archive-url=https://web.archive.org/web/20131106031347/http://www.oxford-man.ox.ac.uk/~jruf/papers/ruf_bspline.pdf , archive-date=2013-11-06 , url-status=dead
Interactive B-splines with JSXGraphTinySpline: Opensource C-library with bindings for various languagesUniform non rational B-Splines, Modelling curves in 2D space. Author:Stefan G. BeckB-Spline Editor by Shukant Pal
Splines (mathematics) Interpolation de:Spline#B-Splines