0.參考

貝塞爾(Bezier)曲線與B樣條：這個視頻講的很好，尤其是對樣條曲線的兩種理解方式上，會對后面B樣條曲線性質(zhì)的分析有很大的幫助。本文在前面的部分也會較多的參考這個視頻中講解的內(nèi)容。但是視頻后面講解B樣條曲線的時候稍微簡略了一點，因此本文給出我自己的理解。

1.問題起源與插值法的曲線擬合

1.1.問題起源

樣條曲線起源于一個常見問題，即已知若干點的條件下，如何得到通過這些點的一條光滑曲線？

一個簡答的方法是對曲線進行 插值：在原有數(shù)據(jù)點上進行填充生成曲線，曲線必經(jīng)過原有數(shù)據(jù)點。

1.2.拉格朗日插值

當(dāng)有多個點的時候，可以使用拉格朗日插值法得到插值的曲線函數(shù)表達式：

其中每個函數(shù) $L_k$稱為拉格朗日插值基函數(shù)。注意這個基的概念，對于后面理解貝塞爾曲線和B樣條曲線非常有幫助。

1.3.“基”的概念

我們之前學(xué)過的知識中，有很多地方用到了 基 的概念，比如下面的內(nèi)容：

• 線性代數(shù)：向量的線性組合就是在對向量空間的基向量給不同的權(quán)重相加，然后得到新的向量。
• 微積分：Taylor展式，Fourier級數(shù)：他們都是有基函數(shù)，然后最終我們的函數(shù)是由很多這種基函數(shù)組成的
• Lagrange插值法：一組基的線性組合：前面剛剛提到，我們插值得到的函數(shù)其實是由一組基函數(shù)組合來的。

1.4.插值存在的Runge現(xiàn)象

插值存在一些問題，比如Runge現(xiàn)象。這是因為插值要求插值函數(shù)必須經(jīng)過所有的插值點，導(dǎo)致非線性程度很嚴重。

為了解決這個問題，并且考慮到人們往往想要一個比較光滑的曲線，而并不要求曲線通過所有點，所以擬合就產(chǎn)生了。

2.貝塞爾曲線

2.1.控制點的思想

一個簡單且行之有效的方法是，把這些點作為限制點，然后在這些限制點中放置一條具有彈性的金屬片，最后金屬片繞過這些點后的最終狀態(tài)即為所需曲線。而最終得到的形狀曲線，就是樣條曲線。這也是該名字的由來，其中金屬片就是樣條，形成的曲線就是樣條曲線。
注意：上圖中的藍色圓形可以變的很大，這樣生成的樣條曲線就離圓心很遠了，所以就是明顯不通過這些圓心點的。如果把圓的半徑縮小成0，那么結(jié)果就變成插值了。

2.2.由控制點生成貝塞爾曲線

步驟如下：

1. 先由前2個控制點，按照 $t$ 的比例生成一個中間過程點 $P_i$
   $$P_i=(1?t)P_0+P_1$$
2. 再由后2個控制點，按照 $t$ 的比例生成一個中間過程點 $P_j$
   $$P_j=(1?t)P_1+P_2$$
3. 對兩個中間過程點，按照 $t$ 的比例生成最后我們要的曲線上的一個點 $P_x$。
   $$P_x=(1?t)P_i+P_j$$

最后，通過遍歷所有的比例值 $t\in [0,1]$，我們就可以得到貝塞爾曲線上的所有點，也就是得到了整條貝塞爾曲線。

如果控制點的個數(shù)比3個多呢？那么就要不斷重復(fù)上面2個點生成1個中間點的過程，直到最后只剩下一個點，這個點就是曲線上的點。所以當(dāng)有多個控制點的時候，只需要對上面的過程進行多次，最后得到一個曲線上的點$P_x$，然后改變比例$t$，就得到整條貝塞爾曲線了。

2.3.多個控制點時的貝塞爾曲線公式

重要：對貝塞爾曲線公式的兩種理解：

1. 從 基 是 基函數(shù) 的角度理解：貝塞爾曲線前面的權(quán)重$W$就是插值基函數(shù)，它是和$t$有關(guān)的函數(shù)，所以他是有次數(shù)的，比如下圖所示的就是關(guān)于$t$為3次的基函數(shù)。后面的點$P$就相當(dāng)于插值點，也就是給基函數(shù)的權(quán)重。但是貝塞爾曲線和拉爾朗日插值的不同之處在于，貝塞爾曲線的結(jié)果并不全都通過這些插值點。

也就是說，這種理解方式，基 是 基函數(shù)，也就是關(guān)于$t$的一些函數(shù)，而 權(quán)重 則是這些 控制點。

這種理解方式就是微積分的理解方式，也就是泰勒展開、級數(shù)的理解方式，因為最終我們的曲線是可以用一個函數(shù)表示的，而這個函數(shù)是由 基函數(shù) 施加不同的 權(quán)重 得到的，而這個權(quán)重就是各個控制點的坐標值。

2. 從 基 是 控制點 的角度理解：

也就是說，這種理解方式，基 是 基向量，也就是控制點；而 權(quán)重 則是關(guān)于 $t$的一些函數(shù)，對于任意一個 $t$確定了之后，我們就可以把函數(shù)值算出來，就得到了一個具體的權(quán)重值。然后把權(quán)重值施加到控制點上，我們就得到了曲線上的一個具體的點。

這種理解方式就是線性代數(shù)的理解方式，也就是對向量空間的基向量進行線性組合的理解方式。這里相當(dāng)于把整個曲線分成一個個的點來看，對于每一個點來說，它對應(yīng)著一個確定的$t$值，這個確定的$t$值帶入函數(shù)$W$里面就可以得到確定的權(quán)重。然后利用這個確定的權(quán)重對控制點進行線性組合，就得到了曲線上的一個點。最后遍歷所有的$t$值，我們就得到了曲線上的所有點，也就是得到了整條貝塞爾曲線。

2.4.貝塞爾曲線的遞推公式

其實這個很簡單，因為前面我們講解多個控制點的貝塞爾曲線的具體做法時，其實就是按照遞推的公式來講解的它的思路，只不過是寫成最終的公式的時候我們可以寫出一個最終的結(jié)果。而遞推公式就是描述了一步步求中間點的過程。

2.5.貝塞爾曲線的性質(zhì)

• Bezier曲線是BSpline的特例
• 曲線總是通過第一個和最后一個點
• 曲線在始點處的切線落在前兩個控制的連線上，曲線在終點處的切線落在最后兩個控制點的連線上
• 改變其中任何一個點，整條曲線都會隨之改變。這個很容易發(fā)現(xiàn)，以為如果從 基 是 基函數(shù) 的角度來看就會發(fā)現(xiàn)，每個基函數(shù)的定義域都是 $t\in [0,1]$。所以一個控制點改變了之后，它會影響整個曲線中這個控制點對應(yīng)的 基函數(shù) 的函數(shù)值分量，從而導(dǎo)致整條曲線從頭到尾都會受到影響。
• 貝塞爾曲線冪次 = 控制點個數(shù) - 1。 對于一條復(fù)雜的曲線，如果使用一個貝塞爾曲線來插值獲得目標曲線，就需要通過增加控制點來進行插值，需要的計算也越復(fù)雜。冪次的問題很好理解，因為每生成一個中間點冪次就上升一次。
  因此對于復(fù)雜曲線，不要求用n-1次曲線，而是讓次數(shù)低一點，經(jīng)常使用三次貝塞爾曲線一段一段地拼接成目標曲線，如Ps 或 Ai 中使用鋼筆工具畫出物體輪廓所做的那樣。 如果使用這種方法，確保最終整體曲線一次光滑的條件是在連接點出兩側(cè)的斜率相等，即連接點和其兩側(cè)控制點共線。

3.B樣條曲線

3.1.B樣條曲線的基本概念

生成曲線，本質(zhì)上就是找一組基函數(shù)，然后用各個控制點當(dāng)權(quán)重進行線性組合。或者理解為把控制點作為基向量，然后用函數(shù)當(dāng)權(quán)重，給定一個$t$帶入函數(shù)中就得到一個具體的權(quán)重值，然后就可以得到曲線上一個點，最后遍歷所有的比例$t$就可以得到曲線上的所有點。

下面給出B樣條曲線的一些基本概念，然后后面再給出詳細的解釋。
舉例說明如下：

3.2.對B樣條的疑問

前面的概念中，不太清楚的就是 控制點(Control Points) 和 節(jié)點(Knots) 這兩個概念。而且前面的講解中一開始說了節(jié)點的個數(shù)和控制點無關(guān)，是自己選取的；但是后面又說控制點和節(jié)點的個數(shù)必須要滿足的關(guān)系是 $m=n+k+1$，這個屬實有點讓人疑惑。

另外一個讓人不太清楚的就是 次(Degree) 和 階(Order) 的區(qū)別，實際上 階數(shù) = 次數(shù) + 1。

直接解釋這兩個問題是無法解釋的，因為這個必須從B樣條的原理觸發(fā)，當(dāng)明白了B樣條的原理，自然就可以明白為什么B樣條中除了控制點還會有節(jié)點，然后才可以推導(dǎo)前面的兩個關(guān)系式。

3.3.B樣條遞推公式的過程

我們直接從最終的遞推形式的$k$次B樣條基函數(shù)出發(fā)，來解釋B樣條的思想。所以這里我們把曲線的樣條擬合問題變成了對 基函數(shù) 的線性組合問題，線性組合的權(quán)重變成了各個點的坐標值。

有了控制點，為什么還要使用節(jié)點呢？貝塞爾曲線只用控制點就可以了啊？其實這個就是為了改進貝塞爾曲線只有全局特性、沒有局部特性的問題，也就是貝塞爾曲線只要修改了一個控制點之后，即使基函數(shù)不變，整個曲線也都會被修改，因為它的基函數(shù)的定義域是在$t\in [0,1]$ 的整個區(qū)間上的。而B樣條加入節(jié)點，目的就是為了給擬合的曲線增加局部性，從而實現(xiàn)改變一個控制點只會影響整個擬合曲線的一部分，而不會影響整個曲線。而實現(xiàn)的關(guān)鍵就是插入節(jié)點，讓控制點只能作用到部分節(jié)點區(qū)間上，而不會作用到整個節(jié)點區(qū)間上。

貝塞爾曲線的基函數(shù)區(qū)間定義域是在$t\in [0,1]$ 的，B樣條曲線就在這個區(qū)間上插入很多節(jié)點，從而把整個區(qū)間分成很多小的區(qū)間。如下圖所示，假設(shè)我把區(qū)間$[0,1]$分成8個子區(qū)間，那么我要插入$8+1=9$個節(jié)點，假設(shè)他們的序號分別是$0?8$。

根據(jù)前面B樣條曲線的遞推公式（這個公式為什么是這樣大家就不要追究了，這種結(jié)論大佬發(fā)現(xiàn)了直接用就行了）：

可以發(fā)現(xiàn)，在這些節(jié)點區(qū)間內(nèi)的基函數(shù)都是0次的，也就是他們在各自的區(qū)間內(nèi)都是1，不在自己區(qū)間范圍內(nèi)的都是0，并且這個取值和$t$是無關(guān)的，所以這個區(qū)間內(nèi)的基函數(shù)都是0次的，如下圖所示。注意圖中的$B_{i,0}$表示的就是當(dāng)前的樣條基函數(shù)都是0次的，然后$i$表示的是哪個區(qū)間的樣條基函數(shù)，因為我們有9個點，所以有8個樣條基函數(shù)，注意下圖中的索引都是從0開始的。

那么B樣條曲線的遞推公式就是在說：可以使用兩個相鄰的小區(qū)間組成一個大區(qū)間，同時基函數(shù)次數(shù)增加1。如下圖所示，最開始的子區(qū)間里面的B樣條函數(shù)都是0次的，而由于B樣條的遞推公式中組合兩個相鄰區(qū)間的時候前面的系數(shù)是帶有 $t$ 的，而且一個是$t$，另一個是$1?t$（實際公式不是這樣，但是也大概是這個思想）。所以組合了兩個區(qū)間之后，在這個新的區(qū)間中的基函數(shù)就變成1次的了。同理新區(qū)間中的樣條基函數(shù)$B_i,1$表示樣條基函數(shù)都是1次的，而$i$表示它的哪個區(qū)間的樣條基函數(shù)。

注意：

• 圖中為了方便畫圖，合并之后的區(qū)間和之前的區(qū)間長度畫成一樣大的了，實際上合并之后的區(qū)間長度應(yīng)該是翻倍的。
• 另外圖中也是為了方便表示出兩個區(qū)間合成一個區(qū)間的結(jié)果，把區(qū)間畫的而有點問題了。實際上由于第0和第1個區(qū)間合成新的區(qū)間0，第1和第2個區(qū)間合成新的區(qū)間1，那么新的區(qū)間0和1之間應(yīng)該是有一般重疊的，但是圖中沒有把重疊畫出來，因為畫出來的話就太亂了。如果是正常有重疊的區(qū)間的話，那么此時新的區(qū)間的基函數(shù)應(yīng)該就是像下圖這樣也有重疊：
  
  那么如此不斷的用B樣條的遞推公式合并相鄰的兩個區(qū)間的話，可以發(fā)現(xiàn)區(qū)間個數(shù)越來越少，但是區(qū)間上的樣條基函數(shù)的次數(shù)會越來越高，如下圖所示：

假設(shè)我們進行3次這樣的區(qū)間合并，最終我們得到的每個區(qū)間上的樣條基函數(shù)就是3次的，整個過程如下：

另外也可以看參考視頻的講解中作者給出的PPT，其實也是在表達這個 區(qū)間合并、基函數(shù)次數(shù)遞增 的過程：

以上就是B樣條曲線的遞推公式表示的過程，可以發(fā)現(xiàn)其實和前面貝塞爾曲線遞推的過程是非常像的，其實都是用相鄰的兩個點組合成一個新的中間點，然后再用相鄰的兩個中間點組合成一個更新的中間點，如此迭代……

3.4.B樣條引入節(jié)點帶來的好處——局部性

我們看之前的圖，最終我們得到了5個B樣條的基函數(shù)，并且每個基函數(shù)都是3次的。由B樣條的公式可以發(fā)現(xiàn)，最終我們也需要5個控制點來控制樣條曲線，因為控制點的個數(shù)和基函數(shù)的個數(shù)是一樣的，因為控制點就是權(quán)重，有幾個基函數(shù)肯定就要有幾個權(quán)重嘛。

那么我們來分析一下，第0個控制點$P_0$它作用到了幾個最初的節(jié)點區(qū)間上呢？如下圖所示，可以發(fā)現(xiàn)它之作用到了前4個區(qū)間上。也就是說，如果改變控制點$P_0$，最終只會影響在區(qū)間$0?4$之間的B樣條曲線，而不會影響它后面的B樣條曲線，這就是B樣條曲線引入控制點之后帶來的好處——擬合的曲線具有局部性！不會由于一個控制點的改變而導(dǎo)致牽一發(fā)而動全身！

3.5.為什么 m = n + k + 1 ?

首先再次定義以上變量的意思：

• $m$：節(jié)點的個數(shù)-1，也就是節(jié)點的個數(shù)=m+1，或者說$m$是節(jié)點區(qū)間的個數(shù)。比如在上圖中，節(jié)點的個數(shù)為9，則$m=8$；
• $n$：控制點的個數(shù)-1，也就是控制點的個數(shù)=n+1，或者說$n$是控制點區(qū)間的個數(shù)。比如在上圖中，控制點的個數(shù)為5，則$n=4$。注意：最后的時候區(qū)間是5個，表示控制點個數(shù)就是5個，因為每個控制點是作用在一個區(qū)間上的；而在節(jié)點的那個地方區(qū)間是8個，而節(jié)點數(shù)是9個！
• $k$：基函數(shù)的次數(shù)，也就是合并區(qū)間的最后得到的基函數(shù)的次數(shù)；

那么為什么 $m=n+k+1$呢？其實從上面合并區(qū)間的過程中就可以看出來，每合并一次，基函數(shù)的次數(shù)上升一次，區(qū)間的個數(shù)就減少一次。

• 一開始是時候區(qū)間的個數(shù)就是$m$。
• 最后區(qū)間的個數(shù)是$n+1$。注意不是$n$，最終的區(qū)間個數(shù)就是控制點的個數(shù)，因為一個控制點對應(yīng)一個區(qū)間的基函數(shù)。
• 一共合并了$k$次區(qū)間，所以有$m?k=n+1$，因此得到$m=n+k+1$。

注意：既然有上面的公式，到底誰是自變量，誰是因變量？其實從寫法就可以看出來，$n$和$k$是自變量，而$m$是因變量。也就是說，控制點的個數(shù)$n+1$是自己事先確定的，基函數(shù)的次數(shù)$k$也是自己事先確定的，確定了這兩個之后，選擇幾個節(jié)點$m+1$也自然就確定了，因為這是由B樣條曲線的遞推公式?jīng)Q定的。

3.6.為什么 階數(shù)(Order) = 次數(shù)(Degree) + 1？

首先我們已經(jīng)明白了**次數(shù)(Degree)**的含義，它代表的是最終的基函數(shù)的次數(shù)，也就是$t$的最高次冪。

那么 階數(shù)(Order) 有什么意義呢？以及為什么滿足 階(Order) = 次(Degree) + 1？

首先說階數(shù)的物理意義：它其實反應(yīng)了當(dāng)前的點最多受到幾個控制點的控制，也就是如果是4階的B樣條曲線，那么一個點最多受到它周圍的4個控制點的控制。

前面我們已經(jīng)說了，B樣條曲線具有局部性，而且分析了為什么具有局部性，本質(zhì)上是因為區(qū)間合并這種操作導(dǎo)致最終基函數(shù)所在的區(qū)間只能影響到整個節(jié)點區(qū)間的一部分，所以這個基函數(shù)對應(yīng)的權(quán)重（也就是控制點）如果改變，也只會影響到最終擬合的這個區(qū)間的樣條曲線，而不會影響整個樣條曲線。

那么怎么分析的當(dāng)前的一個點最多受到幾個控制點的影響呢？其實也很簡單，我們就分析每個控制點覆蓋的區(qū)間范圍，直到某個控制點和第0個控制點沒有重合的節(jié)點區(qū)間。

如下圖所示，節(jié)點區(qū)間$0?1$只受到控制點$P_0$的影響；節(jié)點區(qū)間$1?2$會受到控制點$P_0$、$P_1$的影響；節(jié)點區(qū)間$2?3$會受到控制點$P_0$、$P_1$、$P_2$的影響；節(jié)點區(qū)間$3?4$會受到控制點$P_0$、$P_1$、$P_2$、$P_3$的影響；而到了區(qū)間$4?5$的時候，此時前面的控制點$P_0$已經(jīng)無法施加控制作用了，此時起作用的控制點是$P_1$、$P_2$、$P_3$、$P_4$。

所以可以發(fā)現(xiàn)，一個節(jié)點區(qū)間最多受到幾個控制點的控制，和一個控制點可以控制幾個節(jié)點區(qū)間是一樣的！那么一個控制點可以控制幾個節(jié)點區(qū)間呢？顯然控制點自己就是一個區(qū)間，然后每往上走一次，控制點控制的節(jié)點區(qū)間個數(shù)就+1，所以最終一個控制點控制的節(jié)點區(qū)間個數(shù)就是 k+1 ！所以說 階數(shù) = 次數(shù) + 1。

可以看到就像一種滑窗的感覺，如下圖所示：

• 一開始的時候在節(jié)點區(qū)間開頭，只有第0個控制點能發(fā)揮作用，滑窗長度是1；
• 慢慢往后遍歷節(jié)點區(qū)間，發(fā)揮作用的控制點個數(shù)逐漸增加，滑窗長度逐漸變大；
• 從滑動到某個節(jié)點區(qū)間開始，就只能有恒定個數(shù)的控制點發(fā)揮作用了，而不會一直增加，也就是滑窗開始保持固定長度，這個長度就是B樣條曲線的 階數(shù)(Order) ；
• 快到達節(jié)點區(qū)間結(jié)尾的時候，發(fā)揮作用的控制點個數(shù)逐漸減少，滑窗長度逐漸變小；
• 最后到達節(jié)點區(qū)間末尾，只有最后一個控制點能發(fā)揮作用，滑窗長度又變成1。

另外從這個圖中也可以發(fā)現(xiàn)，起始和最后的$k$個區(qū)間，也就是階數(shù)-1個區(qū)間，有效的控制點個數(shù)是不足的，所以一般來說不使用前面的幾個節(jié)點區(qū)間，而使用有效控制點個數(shù)到達階數(shù)的那些區(qū)間，也就是從中間區(qū)間開始使用。

3.7.B樣條曲線的特點

• 優(yōu)點：和Bezier樣條一樣，B樣條也是通過逼近一組控制點來產(chǎn)生的。但是B樣條具有兩個Bezier樣條所不具備的特點：
  （1）B樣條多項式的次數(shù)可獨立于控制點數(shù)目（有一定限制）；
  （2）B樣條允許局部控制曲線或曲面。
• 缺點：比Bezier樣條更復(fù)雜。

3.8.B樣條曲線的歷史

最后給出這個吧，其中前面的B樣條曲線的遞推公式就是de Boor-Cox公式，1972年就提出來了，真理經(jīng)久不衰啊……

• 均勻節(jié)點意義下的一元B樣條(B-splines，Basis Splines縮寫)是在1946年由I.J.Schoenberg提出
• 非均勻節(jié)點定義的B樣條由Curry在1947年提出
• 1962年，法國數(shù)學(xué)家Pierre Bézier研究了一種曲線，即Bézier曲線
• 1972年，de Boor與Cox分別獨立提出了計算B樣條基函數(shù)的公式，這個公式對B樣條作為計算機輔助幾何設(shè)計(CAGD)重要工具起到了至關(guān)重要的作用，稱之為de Boor-Cox公式。在此之前，計算B樣條基函數(shù)大多用差分方法計算，數(shù)值上可能不穩(wěn)定。

4.B樣條曲線的矩陣表達式及在SLAM中的應(yīng)用

參考：均勻B樣條曲線的表達式

4.1.均勻B樣條的矩陣表達式

注意：這個矩陣形式的推導(dǎo)可以不用關(guān)注，實際上是有公式的，在上面的參考博客中就有。只需要知道其中的自變量有$t$和控制點$P$即可。比如在SLAM中，位置樣條曲線$P(t)$對$t$求導(dǎo)，得到的就是速度樣條曲線，再對$t$求導(dǎo)得到的就是加速度曲線。如果要優(yōu)化軌跡的時候，那么就是對控制點求導(dǎo)來有優(yōu)化軌跡。

4.2.均勻B樣條表示李群空間的矩陣表達式

4.3.B樣條曲線用于SLAM的軌跡表示