CAGD-banner.gif
On-Line Geometric Modeling Notes
A PROOF OF THE TWO-SCALE RELATION
FOR UNIFORM B-SPLINES


Overview

The two-scale relation for the uniform B-spline blending function can be used to represent this function as a linear combination of scaled and translated versions of itself. This remarkable property is extremely useful in defining wavelets on B-splines.

In these notes, we develop the coefficients of the linear combination. The fact that the blending function can be defined using convolution allows us to analyze this relationship in terms of its Fourier transform.

pdficonsmall.gif For a pdf version of these notes look here


The Two-Scale Relation for Uniform B-Splines

Given the general B-Spline blending function of order $ k$, the two-scale relation is written as

$\displaystyle N_k(t) \: = \: \sum_{j=0}^{k} p_j N_k(2t-j)
$

where

$\displaystyle p_j \: = \: \frac{1}{2^{k-1}} { k \choose j }
$

We calculate these coefficients by taking the Fourier transform of both sides of the two-scale equation.


Calculating the Fourier Transform of the Blending Function

First let $ \hat{N}_k(\omega)$ be the Fourier Transform of $ N_k(t)$, that is

$\displaystyle \hat{N}_k(\omega) \: = \: \int_{-\infty}^{\infty} e^{-\imath \omega x}
N_k(x) dx
$

Using the fact that for any $ k$, $ N_k(t)$ is defined to be $ ( N_{k-1} * N_1 ) ( t )$, we have that

$\displaystyle \hat{N}_k(\omega) \: = \: \widehat{( N_{k-1} * N_1 )}(\omega)
\: = \: \hat{N}_{k-1}(\omega) \hat{N}_1(\omega)
$

since convolution translates to multiplication in the Fourier transform. But since

$\displaystyle \hat{N}_1(\omega) \: = \: \frac{1 - e^{-\imath \omega}}{\imath \omega}
$

it is easy to conclude that

$\displaystyle \hat{N}_k(\omega) \: = \: \left( \frac{1 - e^{-\imath \omega}}{\imath \omega}
\right) ^ k
$


Taking the Fourier Transform of Both Sides of the Two-Scale Equation

If we take the Fourier Transform of both sides of the equation

$\displaystyle N_k(t) \: = \: \sum_{j=-\infty}^{\infty} p_j N_k(2t-j)
$

we obtain

$\displaystyle \hat{N}_k(\omega) \: = \: \frac{1}{2}
\left(
\sum_{j=-\infty}^{\...
...{-\frac{\imath j \omega}{2}}
\right)
\hat{N}_k \left( \frac{\omega}{2} \right)
$

This gives

$\displaystyle \left( \frac{1 - e^{-\imath \omega}}{\imath \omega} \right) ^ k
\...
...( \frac{1 - e^{-\imath \frac{\omega}{2}}}{\imath \frac{\omega}{2}} \right) ^ k
$

and so

\begin{displaymath}\begin{aligned}\frac{1}{2} \left( \sum_{j=-\infty}^{\infty} p...
...^{k} {k \choose j} e^{-\frac{\imath j \omega}{2}} \end{aligned}\end{displaymath}

where we have used the binomial theorem in the final step.


The Coefficients

Comparing both sides of the above equation, we can see that

$\displaystyle p_j \: = \: \begin{cases}
\frac{1}{2^{k-1}} { k \choose j } &
\text{for } 0 \leq j \leq k \\
0 & \text{otherwise}
\end{cases}$


Bibliography

1
BARTELS, R., BEATTY, J., AND BARSKY, B.
An Introduction to Splines for Use in Computer Graphics and Geometric Modeling.
Morgan Kaufmann Publishers, Palo Alto, CA, 1987.

2
UEDA, M., AND LODHA, S.
Wavelets: An elementary introduction and examples.
Technical Report UCSC-CRL-94-47, Jan. 1994.


\begin{singlespace}
\noindent
\footnotesize\bfseries All contents copyright (c) ...
...ment, University of California, Davis \\
All rights reserved.
\end{singlespace}


Ken Joy
2000-11-28