b-spline

b-spline

- basics

b-spline-00-basics

$$$
% From AsciiMath
\newcommand{\bb}[0]{\mathbf}
\newcommand{\bbb}[0]{\mathbb}
\newcommand{\cc}[0]{\mathcal}
\newcommand{\RR}[0]{\bbb{R}}
\newcommand{\CC}[0]{\bbb{C}}
\newcommand{\ZZ}[0]{\bbb{Z}}
\newcommand{\xx}[0]{\times}
\newcommand{\del}[0]{\partial}
% Quick begin/end
\newcommand{\Ba}[0]{\begin{aligned}}
\newcommand{\Ea}[0]{\end{aligned}}
\newcommand{\Bc}[0]{\begin{cases}}
\newcommand{\Ec}[0]{\end{cases}}
\newcommand{\Bm}[0]{\begin{matrix}}
\newcommand{\Em}[0]{\end{matrix}}
\newcommand{\Bmp}[0]{\begin{pmatrix}} % round bracket
\newcommand{\Emp}[0]{\end{pmatrix}}
% Others
\newcommand{\t}[0]{\text}
\newcommand{\l}[0]{\left}
\renewcommand{\r}[0]{\right}
$$$

## Uniform B-spline

### Def. 1

Define $B^k : \RR \to \RR$ for $k: 0, 1, ...$ by:

$$
\Ba
B^0(x)
  &\equiv E_{[0, 1)}(x)
  =
    \Bc
      1 ~~(\t{if}~~ x \in [0, 1)) \\
      0 ~~(\t{otherwise}),
    \Ec
\\\\
B^k(x) &\equiv x B^{k-1}(x) + (k + 1 - x) B^{k - 1}(x - 1).
\Ea
$$

**N.B.**

- For the translation of function, we denote $B^k_i(x) \equiv B^k(x - i)$.
- For the translation, recursive definition becomes:

  $$B^k_i(x) = (x - i) B^{k - 1}_i(x) + (k + 1 - (x - i)) B^{k - 1}_{i + 1}(x).$$

- It's easy to see that $\t{supp}(B^k) = [0, k + 1]$.
- Also it's easy to see that $B^k$ is $k$-deg polynomial for all intervals of the form $[i, i + 1]$.


### Prop. 2 (Derivatives)

$$
\del_x B^k_i = k (B^{k-1}_i - B^{k-1}_{i + 1}).
$$

**N.B.**

- Strictly speaking, for $k = 1$, it only holds when $x \in (i, i + 1)$ (i.e. interior).
- When $k > 1$, both $\del_x B^k$ and $B^{k-1}$ are continuous, so this becomes true for whole $\RR$.

***Proof***

We prove this by induction.

For the initial case of $k = 1$, we directly see:

$$
\Ba
\del_x B^1_0(x)
  &=
    \Bc
      1  &(\t{if}~~ x \in (0, 1)) \\
      -1 &(\t{if}~~ x \in (1, 2)) \\
      0  &(\t{otherwise})
    \Ec \\
  &= B^0_0(x) - B^0_{1}(x).
\Ea
$$

For $k > 1$, from the recursive definition, we have:

$$
\Ba
\del_x B^k_{i}
  &=
    \del_x \l(
      (x - i) B^{k - 1}_{i}
      +
      (k + 1 - (x - i)) B^{k - 1}_{i + 1}
    \r) \\
  &=
    (B^{k-1}(x) - B^{k - 1}_1(x))
    + (x - i) \del_x  B^{k - 1}_{i}
    + (k + 1 - (x - i)) \del_x B^{k - 1}_{i + 1} \\
  &=
    (B^{k-1}(x) - B^{k - 1}_1(x)) \\
  &~~~~
    + (k - 1)
      \l(
        (x - i) ( B^{k-2}_{i} - B^{k - 2}_{i + 1} )
        +
        (k + 1 - (x - i)) ( B^{k-2}_{i + 1} - B^{k - 2}_{i + 2} )
      \r) \\
  &~~~~~~(\because \t{IH}).
\Ea
$$

Here, the last term becomes:

$$
\Ba
& (x - i) ( B^{k-2}_{i} - B^{k - 2}_{i + 1} )
  + (k + 1 - (x - i)) ( B^{k-2}_{i + 1} - B^{k - 2}_{i + 2} ) \\
&=
  (x - i) B^{k-2}_{i}
  + (k - (x - i)) B^{k-2}_{i + 1} 
  - (x - (i + 1)) B^{k - 2}_{i + 1}
  + (k - (x - (i  + 1))) B^{k - 2}_{i + 2} \\
&=
  B^{k - 1}_i - B^{k - 1}_{i + 1}.
\Ea
$$

Therefore, 

$$
\del_x B^k_{i}
  = (B^{k-1}(x) - B^{k - 1}_1(x)) + (k - 1) (...)
  = k (B^{k-1}(x) - B^{k - 1}_1(x)).
$$


### Prop. 3

$$
\sum_{i \in \ZZ} B^k_i(x)
  = \sum_{i = ⌊x⌋ - k}^{⌊x⌋} B^k_i(x)
  = k!.
$$

***Proof***

We prove this by induction.

For the base case $k = 0$, obviously $\sum_{i} B^0_i = \sum_{i} E_{[i, i + 1]} = 1$.

For the case $k > 0$, we have:

$$
\Ba
\sum_{i} B^{k}_{i}
  &= \sum_{i} (x - i) B^{k - 1}_{i} + (k + 1 - (x - i)) B^{k - 1}_{i + 1} \\
  &= \sum_{i} ((x - i) +  (k + 1 - (x - (i - 1)))) B^{k - 1}_{i} \\
  &= k \sum_{i} B^{k - 1}_{i} = k (k - 1)! ~~(\because \t{IH}) \\
  &= k!.
\Ea
$$


### Prop. 4 (Linear independence)

For $(a_i)_i \in \RR^\ZZ$,

$$
\sum_{i \in \ZZ} a_i B^k_i =0 \implies \forall i.~ a_i = 0
$$

**N.B.**

- Inifinite sum on the RHS is well-defined because each $B^k_i$ has compact support.

- If we consider the single interval, then we see that, for $x \in [0, 1]$,

  $$
    \sum_{i \in -k, .., 0} a_i B^k_i = 0 \implies a_i = 0.
  $$
  
  This means that these $k+1$ polynomials $\{ B^k_i(x) \}_{i: -k, .., -1, 0}$ is independent,
  ant thus they make basis for degree-$k$ polynomials.

***Proof***

We prove this by induction.

For $k = 0$, this is obvious.

For $k > 0$, by taking the derivative of the sum:

$$
\Ba
0 &= \sum_i a_i \del_x B^k_i \\
  &= k \sum_i a_i (B^{k - 1}_i - B^{k - 1}_{i + 1}) ~~(\because \t{Prop. 2}) \\
  &= k \sum_i (a_i - a_{i - 1}) B^{k-1}_i.
\Ea
$$

Thus, by IH, we have $a_i - a_{i - 1} = 0$, and thus $\forall_i. ~ a_i = c$.
But, from Prop. 3, we see:

$$
0 = \sum_i a_i B^k_i = c \sum_i B^k_i = c k!.
$$

Therefore, we obtain $a_i = c = 0$.


### Prop. 5 (Subdivision property)

$$
B^k(x / 2) = \frac{1}{2^k} \sum_{i: 0, .., k + 1} \binom{k + 1}{i} B^k_i(x).
$$

**N.B.**

- We denote these coefficient as $(s^k_i)_i$ i.e. $B^k(x/2) = \sum_i s^k_i B^k_i(x)$.
- For the translation, it becomes:
  
  $$
  B^k_j(x/2) = B^k((x - 2j) / 2) = \sum_i s^k_i B^k_i(x - 2j) = \sum_i s^k_i B^k_{i + 2j}.
  $$


***Proof***

For $k = 0$, it reduces to $B^0(x/2) = B^0(x)$ and it holds true.

For $k > 0$, we expand LHS as:

$$
\Ba
2^k B^k(x/2)
  &=
    2^k \l(
      x/2 B^{k-1}(x/2) + (k + 1 - x/2) B^{k-1}_1(x/2)
    \r) \\
  &=
    2^{k - 1} \l(
      x B^{k-1}(x/2) + (2(k + 1) - x) B^{k-1}_1(x/2)
    \r) \\    
  &=
    \sum_i
      \binom{k}{i} \l(
        x B^{k-1}_i(x) + (2 (k + 1) - x) B^{k-1}_{i + 2}(x)
      \r)
    ~~ (\because \t{IH}) \\
  &=
    \sum_i
      \l(
        \binom{k}{i} x +
        \binom{k}{i - 2} (2 (k + 1) - x)
      \r) 
      B^{k-1}_i
    ~~ (\because \t{slide sum index of the 2nd term}) \\
  &=
    \sum_i
      \l(
        \l(
          \binom{k}{i} - \binom{k}{i - 2}
        \r) x +
        \binom{k}{i - 2} 2 (k + 1)
      \r) 
      B^{k-1}_i.
\Ea
$$

Next, we expand RHS as:

$$
\Ba
&\sum_i \binom{k+1}{i} B^k_i \\
  &=
    \sum_i \binom{k+1}{i} \l(
      (x - i) B^{k - 1}_i + (k + 1 - (x - i)) B^{k - 1}_{i + 1}
    \r) \\
  &=
    \sum_i
      \l(
        \binom{k+1}{i} (x - i) +
        \binom{k+1}{i - 1} (k - (x - i))
      \r)
      B^{k-1}_i
    ~~(\because \t{slide sum index of the 2nd term}) \\
  &=
    \sum_i
      \l(
        \l(\binom{k+1}{i} - \binom{k+1}{i-1} \r) x
        - \binom{k+1}{i} i
        + \binom{k+1}{i - 1} (k + i)
      \r)
      B^{k-1}_i.
\Ea
$$

For the term with $x$, from usual binomial coefficient identity, we have:

$$
\binom{k+1}{i} - \binom{k+1}{i-1}
  =
    \l( \binom{k}{i} + \binom{k}{i-1} \r) -
    \l( \binom{k}{i-1} + \binom{k}{i-2} \r)
  = \binom{k}{i} - \binom{k}{i - 2}.
$$


For the other terms, we resort to direct compututation by factorial:

$$
\Ba
&- \binom{k+1}{i} i
+ \binom{k+1}{i - 1} (k + i) \\
  &=
    \frac{(k + 1)!}{(k + 1 - i)! ~ i!} (- i) +
    \frac{(k + 1)!}{(k + 1 - (i - 1))! ~ (i - 1)!} (k + i) \\
  &=
    \frac{(k + 1)!}{(k + 1 - (i - 1))! ~ (i - 1)!} \l(
      - (k + 1 - (i - 1)) + (k + i)
    \r) \\
  &=
    \frac{(k + 1)!}{(k + 1 - (i - 1))! ~ (i - 1)!} 2 (i - 1) \\
  &=
    (k + 1) 
      \frac{k!}{(k + (i - 2))! ~ i!} 2.
\Ea
$$


### Prop. 6 (1D subidivision mask)

Given $(a_i)_i, (b_i)_i \in \RR^\ZZ$ s.t. $b_{i_0} = \sum\limits_{p + 2i = i_0} s^k_p a_i$, then:

$$
\sum_i a_i B^k_i(x/2) = \sum_i b_i B^k_i(x).
$$

**N.B.**

- Converse holds from the fact that B-splines $(B^k_i)_i$ forms basis.

- For the special case of $k = 3$, we have:

  $$
  (s_0, s_1, s_2, s_3, s_4)
    = \frac{1}{8}(1, 4, 6, 4, 1),
  $$
  
  and thus:
  
  $$
  \Ba
  b_0
    &= (s_0, s_2, s_4) \Bmp a_0 \\ a_{-1} \\ a_{-2} \Emp
    = \frac{1}{8} (1, 6, 1) \Bmp a_0 \\ a_{-1} \\ a_{-2} \Emp, \\\\
  b_{-1}
    &= (s_1, s_3) \Bmp a_{-1} \\ a_{-2} \Emp
     = \frac{1}{8} (4, 4) \Bmp a_{-1} \\ a_{-2} \Emp.
  \Ea
  $$
  
  Since $B^3_0(x)$ has maximum at $x = 2$,
  so we can interpret $b_0$ represents a finer version of control point value at $x = 2$ and 
  $a_0$ represents a coarser one at $x = 4$.
  
  From this point of view, applying such rewriting of index (here using hat $\hat{a}, \hat{b}$),
  we are lead to:
  
  $$
  \Ba
  \hat{b}_2 &= \frac{1}{8} (1, 6, 1) \Bmp \hat{a}_4 \\ \hat{a}_2 \\ \hat{a}_0 \Emp
  ~~(\t{aka. vertex mask}),
  \\\\
  \hat{b}_1 &= \frac{1}{2} (1, 1) \Bmp \hat{a}_2 \\ \hat{a}_0 \Emp
  ~~(\t{aka. edge mask}).
  \Ea
  $$
  
  A bit more graphically (excuse my ascii), it's represented by something like:
  
```
[ Geometry (o: original, +: new) ]
o -- + -- o -- + -- o 

[ Edge mask ]
1 -- + -- 6@ -- + -- 1

[ Vertex mask ]
1 -- @ -- 1
```


***Proof***

From Prop. 5, we have:

$$
\sum_i a_i B^k_i(x/2) 
  = \sum_i a_i \sum_p s^k_p B^k_{p + 2i} (x)
  = \sum_{i_0}
      \l( \sum_{p + 2i = i_0} s^k_p a_i \r) B^k_{i_0}(x).
$$

### Def. 7 (2D B-spline)

Define $B^{k, l} : \RR^2 \to \RR$ by:

$$
B^{k, l}(x, y) \equiv B^k(x) B^l(y).
$$

**N.B.**

- When $k = l$, we denote $B^k(x, y) \equiv B^{k, k}(x, y)$.

- For the translation of the function,
  we denote $B^{k, l}_{i, j}(x, y) \equiv B^{k, l}(x-i, y-j) = B^k_i(x) B^l_j(y)$.

- Many property easily follows from 1D case, e.g. basis, linear independence.


### Prop. 8 (2D subdivision mask)

Given $(a_{i, j})_{i, j} \in \RR^{\ZZ \xx \ZZ}$, we have:

$$
\sum_{i, j} a_{i, j} B^{k, l}_{i, j}(x/2, y/2)
  = \sum_i b_i B^{k, l}_{i, j}(x, y),
$$

with $(b_{i, j})$ given by:

$$
b_{i_0, j_0} =
  \sum_{\substack{p + 2i = i_0 \\ q + 2j = j_0}} s^k_p s^l_q a_{i, j}.
$$

***Proof***

Simply applying 1D case twice, we obtain the result:

$$
\Ba
\sum_{i, j} a_{i, j} B^{k, l}_{i, j}(x/2, y/2)
  &= \sum_{i, j} a_{i, j} B^k_i(x/2) B^l_j(y/2) \\
  &= \sum_{i, j} a_{i, j}
      \sum_p s^k_p B^k_{p + 2i}(x)
      \sum_q s^l_q B^l_{q + 2j}(y) \\
  &=
    \sum_{i_0, j_0}
      \l(
        \sum_{\substack{p + 2i = i_0 \\ q + 2j = j_0}}
          s^k_p s^l_q a_{i, j} 
      \r)
      B^k_{i_0}(x) B^l_{j_0}(y) \\
  &=
    \sum_{i_0, j_0} b_{i_0, j_0} B^{k, l}_{i_0, j_0}(x, y).
\Ea
$$

**N.B.**

- For the special case of $k = l = 3$, we have (denoting $s_i \equiv s^3_i$):

  $$
  \Ba
    b_{0, 0}
      &=
        \Bmp s_0 & s_2 & s_4 \Emp
        \Bmp
          a_{0, 0} & a_{-1, 0} & a_{-2, 0} \\
          a_{0, -1} & a_{-1, -1} & a_{-2, -1} \\
          a_{0, -2} & a_{-1, -2} & a_{-2, -2} \\          
        \Emp
        \Bmp s_0 \\ s_2 \\ s_4 \Emp, \\\\
    b_{0, -1}
      &=
        \Bmp s_1 & s_3 \Emp
        \Bmp
          a_{0, -1} & a_{-1, -1} & a_{-2, -1} \\
          a_{0, -2} & a_{-1, -2} & a_{-2, -2} \\
        \Emp
        \Bmp s_0 \\ s_2 \\ s_4 \Emp, \\\\
    b_{-1, -1}
      &=
        \Bmp s_1 & s_3 \Emp
        \Bmp
          a_{-1, -1} & a_{-2, -1} \\
          a_{-1, -2} & a_{-2, -2} \\
        \Emp
        \Bmp s_1 \\ s_3 \Emp.
  \Ea
  $$
  
  Or, graphically, we write:

```
[ Geometry (o: original, +: new) ]
o -- + -- o -- + -- o 
|    |    |    |    |
+ -- + -- + -- + -- +
|    |    |    |    |
o -- + -- o -- + -- o 
|    |    |    |    |
+ -- + -- + -- + -- +
|    |    |    |    |
o -- + -- o -- + -- o 

[ Face mask ]
1 -- + -- 1
|    |    | 
+ -- @ -- +
|    |    |
1 -- + -- 1

[ Edge mask ]
1 -- + -- 6 -- + -- 1 
|    |    |    |    |
+ -- + -- @ -- + -- +
|    |    |    |    |
1 -- + -- 6 -- + -- 1 

[ Vertex mask ]
1 -- + -- 6 -- + -- 1
|    |    |    |    |
+ -- + -- + -- + -- +
|    |    |    |    |
6 -- + --36@-- + -- 6
|    |    |    |    |
+ -- + -- + -- + -- +
|    |    |    |    |
1 -- + -- 6 -- + -- 1
```