2
$\begingroup$

Consider the Cox-deBoor recursion formula for producing b-spline basis functions given a knot vector:

$N_{i,0}(u)=1 $ if $u_i\leq u < u_{i+1}$ otherwise, $=0$

$N_{i,p}(u)=\frac{u-u_{i}}{u_{i+p}-u_{i}}N_{i,p-1}(u)+ \frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u)$

Now, I read that b-Splines can also be produced using recursive convolution instead of the recursion formula above. For example, see this page: http://www.chebfun.org/examples/approx/BSplineConv.html

Can someone explain if these two are related in any way, I am just not seeing it? And if so, how can I apply convolution to the knot spans of a knot vector to produce the same b-spline basis that we'd get by using the Cox-deBoor formula?

Thanks.

$\endgroup$
2
  • $\begingroup$ It is probably easier to characterize the B-spline with its properties ($p-1$-times differentiable, piecewise polynomial, support on $[u_i,u_{i+p+1}]$) and then show that with both ways you achieve these properties. $\endgroup$
    – user35593
    Commented Sep 6, 2016 at 9:24
  • $\begingroup$ @user35593 Right. But can we use convolution integrals along a domain defined by a knot vector? The Cox deboor recursion starts with step functions so it leads me to think there's a way to space out these step functions according to the knot vector and then convolve with a "moving box" to produce the b spline basis functions according to that knot vector. However I have been unsuccessful in doing so. $\endgroup$ Commented Sep 6, 2016 at 17:34

1 Answer 1

2
$\begingroup$

The B-Spline basis functions as defined by the Cox-DeBoor formula cannot, in general, be constructed with convolution. The convolution construction, as I'll explain below, only works for the special case when the knot vector is $\mathbb{Z}$ (i.e., the uniform knot vector with interval 1, sometimes called the cardinal spline).

To see this construction won't work in general, we can look at a simple example of a knot vector $0,1,3,4$. The basis of the Cox-DeBoor recursive formula (the degree-0 basis functions) gives us a step function over $[0,1]$, $[1,3]$ and $[3,4]$ (see for example here).

$$ N_{0,0}(u) = \left\{ \begin{array}{ll} 1 & 0 \leq u < 1 \\ 0 & \text{otherwise} \\ \end{array} \right\} $$

$$ N_{1,0}(u) = \left\{ \begin{array}{ll} 1 & 1 \leq u < 3 \\ 0 & \text{otherwise} \\ \end{array} \right\} $$ $$ N_{2,0}(u) = \left\{ \begin{array}{ll} 1 & 3 \leq u < 4 \\ 0 & \text{otherwise} \\ \end{array} \right\} $$

The degree-1 basis functions, by the Cox-DeBoor formula, are then (the "triangular functions"):

$$ N_{0,1}(u) = \left\{ \begin{array}{ll} u & 0 \leq u < 1 \\ (3-u)/2 & 1 \leq u < 3 \\ 0 & \text{otherwise} \\ \end{array} \right\} $$ $$ N_{1,1}(u) = \left\{ \begin{array}{ll} (u-1)/2 & 1 \leq u < 3 \\ 4-u & 3 \leq u < 4 \\ 0 & \text{otherwise} \\ \end{array} \right\} $$

However, convolving $N_{0,0}$ with $N_{1,0}$ will not give you $N_{0,1}$, nor will convolving $N_{1,0}$ with $N_{2,0}$. To get a triangular function from $N_{1,0}$, you will need to convolve it with a step function of support 2, and that will not result in $N_{0,1}$ either (since the result is of support 4 and $N_{0,1}$ is of support 3).

The convolution construction of the cardinal B-Spline basis functions results from the B-Spline derivative recursive formula (which itself results from Cox-DeBoor, see answers here and here for example). The following development follows DeBoor's exposition in Section 10 of his paper.

Given the B-Spline recursive derivative formula: $$ N_{i,p}'(u) = \frac{p}{u_{i+p}-u_i} N_{i,p-1}(u) - \frac{p}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u) $$

We can integrate both sides and get (from the basic theorem of calculus): $$ N_{i,p}(u) = \frac{p}{u_{i+p}-u_i} \int_{-\infty}^{u} N_{i,p-1}(t) dt - \frac{p}{u_{i+p+1}-u_{i+1}} \int_{-\infty}^{u} N_{i+1,p-1}(t) dt $$

When the knots are equally spaced (and only then) the coefficients cancel themselves, since $u_{i+p}-u_i = u_{i+p+1}-u_{i+1}$. Furthermore, if the equally spaced interval is unit length the coefficient is 1 (since $p=u_{i+p}-u_i$), and we get:

$$ N_{i,p}(u) = \int_{-\infty}^{u} N_{i,p-1}(t) - N_{i+1,p-1}(t) dt $$

Now, when the knots are equally spaced $N_{i+1,p-1}$ is just a translation of $N_{i,p-1}$, (indeed all the basis functions are just translations of themselves) so: $$ N_{i+1,p-1}(t+1) = N_{i,p-1}(t) $$

Therefore, we can write: $$ N_{i,p}(u) = \int_{-\infty}^{u} N_{i,p-1}(t) dt - \int_{-\infty}^{u-1} N_{i,p-1}(t) dt = \int_{u-1}^{u} N_{i,p-1}(t) dt $$

The right-hand side can be re-written as: $$ N_{i,p}(u) = \int_{-\infty}^{\infty} N_{0,0}(u-t) N_{i,p-1}(t) dt $$ which is the convolution formula of $N_{i,p-1}$ with $N_{0,0}$.

Thus, $$ N_{i,p} = N_{0,0}*N_{i,p-1} $$

To conclude, the convolution formula is related to the Cox-DeBoor formula through the derivative equation, but only for uniform, unit-support knot vectors. For non-uniform knot vectors the basis functions will not be a translation of each other, nor will the coefficients of the integrals be the same. Furthermore, even for uniform knot vectors with support $h \neq 1$ the convolution formula won't work as-is and will require a correction scalar multiplication by $1/h$ (since the coefficient terms will be $1/h$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .