B樣條

在數學的子學科數值分析裡，B-樣條是樣條曲線一種特殊的表示形式。它是B-樣條基曲線的線性組合。B-樣條是貝茲曲線的一種一般化，可以進一步推廣為非均勻有理B樣條（NURBS），使得我們能給更多一般的幾何體建造精確的模型。

De Boor演算法是一個數值上穩定的計算B樣條的方法。

術語 B樣條是Isaac Jacob Schoenberg創造的，B 是基（basis）樣條的縮略。

## 定義

給定m+1 個節點ti，分布在0,1區間，滿足

$$t_0 < t_1 < \ldots < t_m$$

一個n次B樣條是一個參數曲線：

$$\mathbf{S}:[0,1] \to \mathbb{R}^2$$

它由n次B樣條基(basis B-spline)組成

$\mathbf{S}(t)= \sum_{i=0}^{m} \mathbf{P}_{i} b_{i,n}(t) \mbox{ , } t \in [0,1]$.

Pi稱為控制點或de Boor點.

m+1個n次B樣條基可以用Cox-de Boor遞歸公式 定義

$$b_{j,0}(t) := \left\{\begin{matrix} 1 & \mathrm{} \quad t_j < t < t_{j+1} \\ 0 & \mathrm{...} \end{matrix} \right.$$

$$b_{j,n}(t) := \frac{t - t_{j}}{t_{j+n} - t_j} b_{j,n-1}(t) + \frac{t_{j+n+1} - t}{t_{j+n+1} - t_{j+1}} b_{j+1,n-1}(t).$$

當節點等距，稱B樣條為均勻(uniform)否則為非均勻(non-uniform)。

### 均勻B樣條曲線

當B樣條是均勻的時候，對於給定的n，每個B樣條基是其他基的平移拷貝而已。一個可以作為替代的非遞歸定義是

$$b_{j,n}(t) := b_n(t + n - j) \qquad \mbox{ , } j = -1, \ldots m+1$$

滿足

$$b_n(t) := (m+1) \sum_{i=0}^{m+1} \omega_i(t_i - t)_+^{m} \qquad \mbox{ , } t \in [0,1]$$

滿足

$$\omega_i := \prod_{j=0, i \neq j}^{m+1} \frac{1}{t_i - t_k}$$

其中

$$(t_i - t)_+$$

是截斷冪函數（truncated power function）

## 註解

當節點數和多項式次數相等時，B樣條退化為貝茲曲線。即函數的形狀由節點的位置決定。縮放或者平移節點向量不會改變基函數。

樣條包含在它的控制點的凸包中

n次B樣條的一個基

$$b_{i,n}(t)$$

僅當在區間ti, ti+n+1上非0。就是

$$b_{i,n}(t) = \left\{\begin{matrix} >0 & \mathrm{} \quad t_{i} \le t < t_{i+n+1} \\ 0 & \mathrm{...} \end{matrix} \right.$$

換句話說，如果我們操作一個控制點，我們只改變曲線在局部的行為，而不像Bezier曲線那樣是全局行為。

## 例子

### 常數B樣條

常數B樣條是最簡單的樣條。只定義在一個節點距離上，而且不是節點的函數。它只是不同節點段（knot span）的指示函數。

$$b_{j,0}(t) = 1_{[t_j,t_{j+1})} = \left\{\begin{matrix} 1 & \mathrm{} \quad t_j \le t < t_{j+1} \\ 0 & \mathrm{...} \end{matrix} \right.$$

### 線性B樣條

線性B樣條定義在兩個相鄰的節點段上，在節點連續但不可微。

$$b_{j,1}(t) = \left\{\begin{matrix} \frac{t - t_j}{t_{j+1} - t_j} & \mathrm{if} \quad t_j \le t < t_{j+1} \\ \frac{t_{j+2} - t}{t_{j+2} - t_{j+1}} & \mathrm{ } \quad t_{j+1} \le t < t_{j+2} \\ 0 & \mathrm{... } \end{matrix} \right.$$

### 三次B樣條

一個片斷上的B樣條的表達式可以寫作：

$$S_{i} (t) = \sum_{k=0}^3 \mathbf{P}_{i-3+k} b_{i-3+k,3} (t) \qquad \mbox{ , } t \in [0,1]$$

其中Si是第i個B樣條片斷而P是一個控制點集，i和k是局部控制點索引。控制點的集合會是$P_i^w = ( w_i x_i, w_i y_i, w_i z_i, w_i)$的集合，其中$w_i$是比重，當它增加時曲線會被拉向控制點$P_i$，在減小時則把曲線遠離該點。

片段的整個集合m-2條曲線（$S_3,S_4,...,S_m$）由m+1個控制點（$P_0,P_1,...,P_m, m \ge 3$）定義，作為t上的一個B樣條可以定義為

$$S(t) = \sum_{i=0}^m \mathbf{P}_{i} b_{i,} (t)$$

其中i是控制點數，t是取節點值的全局參數。這個表達式把B樣條表示為B樣條基函數的線性組合，這也是這個名稱的原因。

有兩類B樣條-均勻和非均勻。非均勻B樣條相鄰控制點間的距離不一定要相等。一個一般的形式是區間隨著插入控制點逐步變小到0。

## B樣條的程式指令

### Matlab

In Matlab，the command「spline」 can be used for spline interpolation.

(Note： In the command, the cubic B-spline is used)

Cubic B-Spline Interpolation by Matlab

Generating a sine-like spline curve and samples it over a finer mesh:

x = 0:1:10; % original sampling points

y = sin(x);

xx = 0:0.1:10; % new sampling points

yy = spline(x,y,xx);

plot(x,y,'o',xx,yy)

### Python

事前安裝模組

- pip install numpy
- pip install scipy
- pip install matplotlib

Cubic B-Spline Interpolation by Python

from scipy.interpolate import interp1d

import matplotlib.pyplot as plt

import numpy as np

x = np.arange(0, 11) # original sample points, 0, 1, 2, …, 9, 10

y = np.sin(x)

f = interp1d(x, y, kind=' cubic ') ) # Cubic means the cubic B-spline.

x_new = np.arange(0, 10.1, 0.1) # new sample points, 0, 0.1, 0.2, ….., 9.9, 10

y_new = f(x_new)

plt.plot(x,y,'o',x_new, y_new)

plt.show

## B樣條曲線及曲面相關演算法

關於此處涉及的演算法，在著作中有針對Bézier、B樣條（B-spline）以及非均勻有理B樣條（Nurbs）的相關演算法的詳細數學表達和程序實現方法。

### 求導

在幾何處理中，對參數曲線及曲面的求導是最基本的運算之一，由於參數表達的特性，在給定點的切線及法線可通過求導直接得到。

先來考察曲線的情形：採用本頁定義中的B樣條曲線表達式$$\mathbf{S}(t)= \sum_{i=0}^{m} \mathbf{P}_{i} b_{i,n}(t) \mbox{ , } t \in [0,1]$$ 對參數$t$進行求導：

$$\frac{d\mathbf{S}}{dt} = \sum_{i=0}^{m} b'_{i,n}(t) \mathbf{P}_{i}$$

## 應用

### 陣列信號處理

假設有多個訊號源，並考慮在遠場 (far-field) 的條件下，以一個多天線接收機所接收，多天線接收機具有 N 個獨立天線，且天線之間間距相同 𝑑 = 𝜆/2。

接收訊號$$x(t) = a(\theta_s(t))s(t) + a(\theta_i(t))i(t) + n(t), \quad t = 1, 2, \dots, L$$

其中，s(t) 為欲接收的訊號源，i(t) 為其他訊號源造成的干擾，n(t) 為雜訊。

指向向量 (steering vector)為:

$$a(\theta_s(t)) = \begin{bmatrix} 1 & e^{j\pi \sin\theta} & e^{j2\pi \sin\theta} & \dots & e^{j(N-1)\pi \sin\theta} \end{bmatrix}^T$$

權重向量 (weight vector) 定義為:

$$w = \begin{bmatrix} w_0 & w_1 & \dots & w_{N-2} & w_{N-1} \end{bmatrix}^T$$

波束成型 (beamformer)的輸出為:

$$y(t) = w^H x(t) = w^H \left( a(\theta_s(t))s(t) + a(\theta_i(t))i(t) + n(t) \right)$$

由於接收端不知道訊號源傳送的訊號為何，利用分段平均、內插重建方法可以降低雜訊 n(t) 的影響，還原低雜訊的角度成分。

Step 1: 分段平均 (Segment Average)

$$\tilde{\theta}_s(\tau + 1) = \frac{1}{L} \sum_{i=0}^{L-1} \tilde{\theta}_s(L\tau + i), \; \tau \in \mathbb{N}$$

$$\tilde{\theta}_i(\tau + 1) = \frac{1}{L} \sum_{i=0}^{L-1} \tilde{\theta}_i(L\tau + i), \; \tau \in \mathbb{N}$$

Step 2: 利用 cubic B-Spline Interpolation B-Spline Interpolation 的關係式如下:

$$B_{n,0}(t) = \begin{cases} 1, & \text{for } t_n < t < t_{n+1} \\ 0, & \text{otherwise} \end{cases}$$

$$B_{n,m}(t) = \frac{t - t_n}{t_{n+m} - t_n} B_{n,m-1}(t) + \frac{t_{n+m+1} - t}{t_{n+m+1} - t_{n+1}} B_{n+1,m-1}(t) \quad \text{for } t_n < t < t_{n+1}$$

$$\text{where } B_{n,m}(t) \text{ is the } m\text{th order polynomial.}$$

因為我們是使用 cubic B-Spline interpolation，所以選擇 m = 3 代入關係式。

藉由上述兩步驟，我們可以得到訊號源和干擾源的DOA:

$$\hat{\theta}_s(t) = \sum_{n=1}^N \tilde{\theta}_s(t_n) B_{n,3}(t)$$

$$\hat{\theta}_i(t) = \sum_{n=1}^N \tilde{\theta}_i(t_n) B_{n,3}(t)$$

優點:

用多項式內插函數重建平均化後的離散訊號可擬和出更接近連續的波型，同時降低高頻成分造成的影響。

## 參考

本條目部分或全部內容出自以GFDL授權發佈的《自由線上電腦詞典》（FOLDOC）

## 外部連結

- Interactive java applets for B-splines
- Introduction to Computing with Geometry Notes (Dr.C.-K.Shene/Michigan Technological University)