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
    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$ 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.