0%

B-Spline in Space I - Euclidean Space

Posted on Edited on Disqus:

Motivation

In a robot system, tens of sensors collecting data in different frequencies and phases. When intermediate values between samples are required, linear interpolation can be used to approximate these values according to their surrounding samples. In some cases, however, linear interpolation is not qualified due to its lack of continuity in high order derivatives.

Moreover, in robotics, computer graphics and computer vision, physical values are not only expressed in Euclidean Space. The orientation of a digital object, the pose of a automatic robot, are described by Quaternion or Lie Group. Some of the readers may have heard about Quaternion SLERP (Spherical Linear Interpolation), which is a general method used in Quaternion interpolation. But SLERP only keeps the intermediate quaternion unit, the derivative continuity before and after a knot is not guaranteed.

With but not limited to the reasons above, B-Spline is widely used in industry and research. Here is a introduction to the principle of B-Spline, both in Euclidean Space and Lie Group.

Terminologies of B-Spline

Terminologies Notation Explanation
Independent Variable \(t\) In state estimation, the independent variable is time \(t\).
Order \(n\) Same as the order of final polynomial, the highest exponent.For instance, \(f(x) = 3x^3\) has an order of 4.
Degree \(p\) Same as the degree of final polynomial, the highest exponent.For instance, \(f(x) = 3x^3\) has a degree of 3.
Segment Index \(i\) A B-Spline is combined with piecewise polynomial, each piece is a segment.
Knot Vector \(k\) The connect knot, or joint, between every piece of polynomial segment. Knot vector lies in the axis of independent variable \(t\).
Basis Function \(B_{i,p}(t)\) In the expression, \(i\) is the index of polynomial segment, \(p\) is the degree of the basis function.
Control Points \(C_i\) Also named as coefficients. Control points are used to describe the weight of each piece of polynomial segment.

Intuitive Understanding from Figures

Fig.1 - Iterative composition of basis functions. Each segment of basis function \(B_{i,p}(t)\) is composed by its adjacent basis functions in lower degree, which are \(B_{i,p-1}(t)\) and \(B_{i + 1,p-1}(t)\). While basis functions in degree 0 are unit square wave signals. [source code]
Fig.2 - The point \(P_{0,2}\) of basis function \(B_{0,2}(t)\) (degree 2 and segment 0), is evaluated by the weighted combination of \(B_{0,1}(t)\) and \(B_{1,1}(t)\). The weight of each component is defined by the distance between \(P_{0,2}\) and its correspondent knot points. As shown in the figure, the knot vector is \([0, 3, 6, 9]^\top\). [source code]
Fig.3 - A B-Spline with degree 2, named \(S_2(t)\) is generated by weighted combinations of all its basis functions. The weight comes from control points, which are \([1.2, 0.8, 1.1, 1.2, 1.1]\) in the figure. The brown dash lines show how control point affect the weight of basis function, these lines finally compose the brown spline. The knot vector is \([0, 1, 2, 3, 4, 5, 6, 7]^\top\). [source code]

Cox-de Boor Recursion Formula

A mathematical representation of B-Spline is necessary after the intuitive concept.

Let \(K\) be a set of \(m\) non-decreasing numbers, \(k_0 \le k_1 \le \cdots \le k_{m-1} \). The \(k_i\)s are called knots, the set \(K\) the knot vector, and the half-open interval \([k_i, k_{i+1})\) the i-th knot span. Note that since some \(k_i\)s may be equal, some knot spans may not exist. If the knots are equally spaced (i.e., \(k_{i+1} - k_i\) is a constant for \((0 \le i \le m - 1)\), the knot vector or the knot sequence is said uniform; otherwise, it is non-uniform[1].

The i-th B-spline basis function of degree \(p\), written as \(B_{i,p}(t)\), is defined recursively as follows:

\[ B_{i,0}(t) = \begin{cases} 1 & \text{if} \ \ t_i \le t < t_{i+1} \\ 0 & \text{otherwise} \end{cases} \tag{2-1} \] \[ B_{i,p}(t) = \frac{t - t_i}{t_{i+p} - t_i} B_{i,p-1}(t) + \frac{t_{i+p+1} - t}{t_{i+p+1} - t_{i+1}} B_{i+1,p-1}(t) \tag{2-2} \]

References

  1. Shene, B-spline Basis Functions: Definition
  2. Kim, M.J., Kim, M.S. and Shin, S.Y., 1995, September. A general construction scheme for unit quaternion curves with simple high order derivatives. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques (pp. 369-376).
  3. Qin, Kaihuai, General matrix representations for B-splines , The Visual Computer (2000) 16:177–186