Reproducing Polynomials with B-Splines: Unterschied zwischen den Versionen

Aus NOBAQ
Zur Navigation springenZur Suche springen
 
(9 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
 
<section begin="head"/>
 
<section begin="head"/>
[[Datei:poly_repro_lin.png|right]]
+
[[Datei:bspline_family.png|right|150px|Family of B-splines up to N=4]]
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>:
  
 
<math>
 
<math>
Zeile 7: Zeile 7:
 
</math>
 
</math>
  
In words, a proper linear combination of shifted versions of a B-Spline can reproduce any polynomial up to order <math>N</math>. This is needed for different applications, for example, for the Sampling at Finite Rate of Innovation (FRI) framework<ref>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</ref>. In this case any kernel <math>\varphi</math> 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.
+
In words, a proper linear combination of shifted versions of a B-Spline can reproduce any polynomial up to order <math>N</math>. This is needed for different applications, for example, for the Sampling at Finite Rate of Innovation (FRI) framework. In this case any kernel <math>\varphi</math> 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 <math>c_{m,n}</math> for the reproduction-formula. In this small article, I describe one way.
 
An important question is how to obtain the coefficients <math>c_{m,n}</math> for the reproduction-formula. In this small article, I describe one way.
Zeile 18: Zeile 18:
 
</math>
 
</math>
  
the coefficients can be obtained using the dual of <math>\varphi</math>, <math>\tilde{\varphi}</math> (I set <math>\beta_N = \varphi</math> for consistency with my notes):
+
the coefficients can be obtained using the dual of <math>\varphi</math>, <math>\tilde{\varphi}</math><ref>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</ref> (I set <math>\beta_N = \varphi</math> for consistency with my notes):
  
 
<math>
 
<math>
Zeile 56: Zeile 56:
 
</math>
 
</math>
  
Now the whole procedure has been reduced to calculate the derivative of <math>f(\omega)</math> and set the result to zero.
+
Now the whole procedure has been reduced to calculating the derivative of <math>f(\omega)</math> and set the result to zero.
  
An open question is how to obtain the dual of <math>\varphi</math>. As the reproduction formula spans a vector space, the <math>\varphi</math> must be at least bi-orthogonal to <math>\tilde{\varphi}</math>. This translates in fourier domain to<ref>S. Mallat: "A Wavelet Tour of Signal Processing", ''Academic Press'' 1999</ref>:
+
An open question is how to obtain the dual of <math>\varphi</math>. As the reproduction formula spans a vector space, <math>\varphi</math> must be at least bi-orthogonal to <math>\tilde{\varphi}</math>. This translates in fourier domain to<ref>S. Mallat: "A Wavelet Tour of Signal Processing", ''Academic Press'' 1999</ref>:
  
 
<math>
 
<math>
Zeile 71: Zeile 71:
 
</math>
 
</math>
  
The following derivation of the sum is borrowed from <ref>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</ref>. For this derivation to work, I set <math>L=N+1</math> temprarily:
+
The following derivation of the sum is borrowed from <ref>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</ref>. For this derivation to work, I set <math>L=N+1</math> temporarily:
  
 
<math>
 
<math>
Zeile 95: Zeile 95:
  
 
<math>
 
<math>
= \sin^{2L}(\frac{\omega}{2}) \sum_{k \in \mathbb{Z}}\frac{1}{(\frac{\omega}{2} + \pi k)^{2L}}
+
= \sin^{2L}\left(\frac{\omega}{2}\right) \sum_{k \in \mathbb{Z}}\frac{1}{(\frac{\omega}{2} + \pi k)^{2L}}
 
</math>
 
</math>
  
And finally the following relation is used:
+
And finally the following relation is used<ref>L.V. Ahlfors: "Complex Analysis", ''McGraw-Hill'', 1979</ref>:
  
 
<math>
 
<math>
Zeile 136: Zeile 136:
 
</math>
 
</math>
  
== Examples for a cubic spline ==
+
= Examples for a cubic spline =
  
 
For a cubic spline (N=3) the coefficients are:
 
For a cubic spline (N=3) the coefficients are:
  
\begin{array}{lcr}
+
<math>
 +
\begin{array}{lcl}
 
c_{0,n}  & = & 1 \\
 
c_{0,n}  & = & 1 \\
 
c_{1,n}  & = & n \\
 
c_{1,n}  & = & n \\
Zeile 146: Zeile 147:
 
c_{3,n}  & = & -n + n^3
 
c_{3,n}  & = & -n + n^3
 
\end{array}
 
\end{array}
 +
</math>
 +
 +
[[Datei:poly_repro_quad.png|center|cubic spline reproducing polynomial of order 2]]
  
 +
[[Datei:poly_repro_cubic.png|center|cubic spline reproducing polynomial of order 3]]
  
 +
= References =
  
== References ==
+
<ref name="schoenberg">I.J. Schoenberg: "Cardinal interpolation and spline functions", ''J. Approx. Theory volume 2'', pp. 167-206, 1969</ref>
  
 
<references/>
 
<references/>
 +
 +
= Comments =
 +
 +
<comments />{{:{{TALKSPACE}}:{{PAGENAME}}}}
 +
 +
[[Kategorie:Weblog]]

Aktuelle Version vom 19. Juli 2010, 16:45 Uhr

Family of B-splines up to N=4

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

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. 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 , [1] (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[2]:

so that

Now the whole procedure has been reduced to calculating 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, must be at least bi-orthogonal to . This translates in fourier domain to[3]:

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

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

and because is always even:

Because of the periodicity it is known that

such that

And finally the following relation is used[6]:

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:

Examples for a cubic spline

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

cubic spline reproducing polynomial of order 2
cubic spline reproducing polynomial of order 3

References

[7]

  1. 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
  2. http://en.wikipedia.org/wiki/Dirac_delta_function
  3. S. Mallat: "A Wavelet Tour of Signal Processing", Academic Press 1999
  4. M.Unser: "Splines - A Perfect Fit for Signal and Imaging Processing", IEEE Signal Processing Magazine Nov. 1999
  5. 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
  6. L.V. Ahlfors: "Complex Analysis", McGraw-Hill, 1979
  7. I.J. Schoenberg: "Cardinal interpolation and spline functions", J. Approx. Theory volume 2, pp. 167-206, 1969

Comments

<comments />

Manu said ...

Bussi

--Manu 19:47, 19. Jul. 2010 (MSD)