next up previous [pdf]

Next: 2-D example Up: Interpolation with convolutional bases Previous: Interpolation with convolutional bases

B-splines

B-splines represent a particular example of a convolutional basis. Because of their compact support and other attractive numerical properties, B-splines are a good choice of the basis set for the forward interpolation problem and related signal processing problems (Unser, 1999). According to Thévenaz et al. (2000), they exhibit superior performance for any given order of accuracy in comparison with other methods of similar efficiency.

B-splines of the order 0 and 1 coincide with the nearest neighbor and linear interpolants (5) and (6) respectively. B-splines $\beta^n(x)$ of a higher order $n$ can be defined by a repetitive convolution of the zeroth-order spline $\beta^0(x)$ (the box function) with itself:

\begin{displaymath}
\beta^n(x) =
\underbrace{\beta^0(x) \ast \cdots \ast \beta^0(x)}_{(n+1)\quad
\mbox{times}}\;.
\end{displaymath} (43)

There is also the explicit expression
\begin{displaymath}
\beta^n(x) =
\frac{1}{n!}\,\sum_{k=0}^{n+1} C_k^{n+1} (-1)^k
(x + \frac{n+1}{2} - k)_{+}^n\;,
\end{displaymath} (44)

which can be proved by induction. Here $C_k^{n+1}$ are the binomial coefficients, and the function $x_{+}$ is defined as follows:
\begin{displaymath}
x_{+} = \left\{\begin{array}{lcr}
x, & \mbox{for} & x > 0 \\
0, & \mbox{otherwise} &
\end{array}\right.
\end{displaymath} (45)

As follows from formula (44), the most commonly used cubic B-spline $\beta ^3(x)$ has the expression
\begin{displaymath}
\beta^3(x) = \left\{\begin{array}{lcr}
\displaystyle \lef...
...t x\vert \geq 1 \\
0, & \mbox{elsewhere} &
\end{array}\right.
\end{displaymath} (46)

The corresponding discrete filter $\beta^3(n)$ is a centered 3-point filter with coefficients 1/6, 2/3, and 1/6. According to the traditional method, deconvolution with this filter is performed as a tridiagonal matrix inversion (de Boor, 1978). One can, however, accomplish the same task more efficiently by spectral factorization and recursive filtering (Unser et al., 1993). The recursive filtering approach generalizes straightforwardly to B-splines of higher orders.

Both the support length and the smoothness of B-splines increase with the order. In the limit, B-splines converge to the Gaussian function. Figures 13 and 14 show the third- and seventh-order splines $\beta ^3(x)$ and $\beta ^7(x)$, respectively, and their continuous spectra.

splint3
splint3
Figure 13.
Third-order B-spline $\beta ^3(x)$ (left) and its spectrum (right).
[pdf] [png] [sage]

splint7
splint7
Figure 14.
Seventh-order B-spline $\beta ^7(x)$ (left) and its spectrum (right).
[pdf] [png] [sage]

It is important to realize the difference between B-splines and the corresponding interpolants $W (x, n)$, which are sometimes called cardinal splines. An explicit computation of the cardinal splines is impractical, because they have infinitely long support. Typically, they are constructed implicitly by the two-step interpolation method outlined above. The cardinal splines of orders 3 and 7 and their spectra are shown in Figures 15 and 16. As B-splines converge to the Gaussian function, the corresponding interpolants rapidly converge to the sinc function (21). Good convergence is achieved with the help of the implicitly-generated long support, which results from recursive filtering at the first step of the interpolation procedure.

crdint3
crdint3
Figure 15.
Effective third-order B-spline interpolant (left) and its spectrum (right).
[pdf] [png] [sage]

crdint7
crdint7
Figure 16.
Effective seventh-order B-spline interpolant (left) and its spectrum (right).
[pdf] [png] [sage]

In practice, the recursive filtering step adds only marginally to the total interpolation cost. Therefore, an $n$-th order B-spline interpolation is comparable in cost with any other method that uses an $(n+1)$-point interpolant. The comparison in accuracy usually turns out in favor of B-splines. Figures 17 and 18 compare interpolation errors of B-splines and other similar-cost methods on the example from Figure 4.

cubspl4
Figure 17.
Interpolation error of the cubic-convolution interpolant (dashed line) compared to that of the third-order B-spline (solid line).
cubspl4
[pdf] [png] [scons]

kaispl8
Figure 18.
Interpolation error of the 8-point windowed sinc interpolant (dashed line) compared to that of the seventh-order B-spline (solid line).
kaispl8
[pdf] [png] [scons]

Similarly to the comparison in Figures 9 and 10, we can also compare the discrete responses of B-spline interpolation with those of other methods. The right plots in Figures 19 and 20 show that the discrete spectra of the effective B-spline interpolants are genuinely flat at low frequencies and wider than those of the competitive methods. Although the B-spline responses are infinitely long because of the recursive filtering step, they exhibit a fast amplitude decay.

speccubspl4
Figure 19.
Discrete interpolation responses of cubic convolution and third-order B-spline interpolants (left) and their discrete spectra (right) for $x=0.7$.
speccubspl4
[pdf] [png] [scons]

speckaispl8
Figure 20.
Discrete interpolation responses of 8-point windowed sinc and seventh-order B-spline interpolants (left) and their discrete spectra (right) for $x=0.7$.
speckaispl8
[pdf] [png] [scons]


next up previous [pdf]

Next: 2-D example Up: Interpolation with convolutional bases Previous: Interpolation with convolutional bases

2014-02-21