Reproducing Polynomials with B-Splines: Unterschied zwischen den Versionen

Aus NOBAQ
Zur Navigation springenZur Suche springen
Zeile 1: Zeile 1:
 
<section begin="head"/>
 
<section begin="head"/>
 +
[[Datei:poly_repro_lin.png|right]]
 
A B-Spline of order <math>N</math> is known to be able to reproduce any polynomial up to order <math>N</math><ref>I.J. Schoenberg: "Cardinal interpolation and spline functions", ''J. Approx. Theory volume 2'', pp. 167-206, 1969</ref>:
 
A B-Spline of order <math>N</math> is known to be able to reproduce any polynomial up to order <math>N</math><ref>I.J. Schoenberg: "Cardinal interpolation and spline functions", ''J. Approx. Theory volume 2'', pp. 167-206, 1969</ref>:
  
Zeile 116: Zeile 117:
 
-\sin^{2(N+1)}\left(\frac{\omega}{2}\right) \frac{1}{(2N+1)!} \frac{d^{2N+1}}{d\left(\frac{\omega}{2}\right)^{2N+1}} \cot{\left(\frac{\omega}{2}\right)}
 
-\sin^{2(N+1)}\left(\frac{\omega}{2}\right) \frac{1}{(2N+1)!} \frac{d^{2N+1}}{d\left(\frac{\omega}{2}\right)^{2N+1}} \cot{\left(\frac{\omega}{2}\right)}
 
</math>
 
</math>
 +
 +
Therefore, together with <math>\Phi(\omega)</math> this yields:
 +
 +
<math>
 +
\tilde{\Phi}(\omega) = \frac{(2N+1)!}{\left(\frac{\omega}{2}\right) \sin\left(\frac{\omega}{2}\right)^{N+1} \frac{d^{2N+1}}{d\left(\frac{\omega}{2}\right)^{2N+1}} \cot{\left(\frac{\omega}{2}\right)}}
 +
</math>
 +
 +
and finally substituting for <math>t(\omega)</math>:
 +
 +
<math>
 +
f(\omega) = \frac{(2N+1)!}{\left(\frac{\omega}{2}\right) \sin\left(\frac{\omega}{2}\right)^{N+1} \frac{d^{2N+1}}{d\left(\frac{\omega}{2}\right)^{2N+1}} \cot{\left(\frac{\omega}{2}\right)}} e^{j \omega n}
 +
</math>
 +
 +
As this function is not well defined it is better to use the limit:
 +
 +
<math>
 +
c_{m,n} = j^m \lim_{\omega \rightarrow 0} f(\omega)
 +
</math>
 +
 +
For a cubic spline (N=3) the coefficients are:
 +
 +
<math>
 +
c_{0,n} = 1
 +
</math>
 +
 +
<math>
 +
c_{1,n} = n
 +
</math>
 +
 +
<math>
 +
c_{2,n} = \frac{1}{3}\left( -1 + 3n^2 \right)
 +
</math>
 +
 +
<math>
 +
c_{3,n} = -n + n^3
 +
</math>
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
  
  
  
 
<references/>
 
<references/>

Version vom 19. Juli 2010, 16:14 Uhr

Poly repro lin.png

A B-Spline of order is known to be able to reproduce any polynomial up to order [1]:

In words, a proper linear combination of shifted versions of a B-Spline can reproduce any polynomial up to order . This is needed for different applications, for example, for the Sampling at Finite Rate of Innovation (FRI) framework[2]. In this case any kernel reproducing polynomials (that is, satisfying the Strang-Fix conditions) can be used. However, among all possible kernels, the B-Splines have the smallest possible support.

An important question is how to obtain the coefficients for the reproduction-formula. In this small article, I describe one way.


Starting from

the coefficients can be obtained using the dual of , (I set for consistency with my notes):

However, even if the dual would be known, solving the infinite integral is only feasible when the dual has finite support. This is the case with the B-Spline itself but not with its dual!

A closer look at the formula tells that this is nothing more than a convolution (under the assumption that is symmetric which is the case):

Now, this can be transformed to fourier domain:

Writing the inverse of this expression yields:

It is known that[3]:

so that

Now the whole procedure has been reduced to calculate the derivative of and set the result to zero.

An open question is how to obtain the dual of . As the reproduction formula spans a vector space, the must be at least bi-orthogonal to . This translates in fourier domain to[4]:

The fourier transform of a B-Spline of order is (e.g. [5]):

The following derivation of the sum is borrowed from [6]. For this derivation to work, I set temprarily:

and because is always even:

Because of the periodicity it is known that

such that

And finally the following relation is used:

in order to finally obtain:

and with :

Therefore, together with this yields:

and finally substituting for :

As this function is not well defined it is better to use the limit:

For a cubic spline (N=3) the coefficients are:







  1. I.J. Schoenberg: "Cardinal interpolation and spline functions", J. Approx. Theory volume 2, pp. 167-206, 1969
  2. P.L. Dragotti, M. Vetterli, T.Blu: "Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang-Fix", IEEE Transactions on Signal Processing, vol. 55, No. 5, May 2007
  3. http://en.wikipedia.org/wiki/Dirac_delta_function
  4. S. Mallat: "A Wavelet Tour of Signal Processing", Academic Press 1999
  5. M.Unser: "Splines - A Perfect Fit for Signal and Imaging Processing", IEEE Signal Processing Magazine Nov. 1999
  6. M.J.C.S. Reis, P.J.S.G. Ferreira, S.F.S.P. Soares: "Linear combinations of B-splines as generating functions for signal approximation", Elsevier Digital Signal Processing 15, 2005