Approximation und geometrische Modellierung – B-Splines

Rekursionsformel

Knotenfolge: Eine Knotenfolge

\begin{align*} \xi \colon \dotsb \le \xi _{-1} \le \xi _0 \le \xi _1 \le \dotsb \end{align*} ist eine endliche, unendliche oder bi-unendliche nicht-fallende Folge von reellen Zahlen. Sie induziert eine Partition von \([\inf _k \xi _k, \sup _k \xi _k)\) in Knotenintervalle \([\xi _\ell , \xi _{\ell +1})\). Die Vielfachheit \(\#\xi _k\) eines Knotens ist die maximale Zahl an Wiederholungen von \(\xi _k\) in der Folge \(\xi \). Man spricht analog zu Nullstellen von Funktionen von einfachen und doppelten Knoten usw.

Rekursionsformel: Für eine Knotenfolge \(\xi \) sind die B-Splines \(b_{k,\xi }^n\) vom Grad \(n\) definiert durch die Rekursion

\begin{align*} b_{k,\xi }^n := \gamma _{k,\xi }^n b_{k,\xi }^{n-1} + (1 - \gamma _{k+1,\xi }^n) b_{k+1,\xi }^{n-1},\quad \gamma _{k,\xi }^n(x) := \frac {x - \xi _k}{\xi _{k+n} - \xi _k}, \end{align*} beginnend mit den charakteristischen Funktionen

\begin{align*} b_{k,\xi }^0(x) := \begin{cases}1 & \text {für } \xi _k \le x < \xi _{k+1}\\0 & \text {sonst}\end {cases} \end{align*} der Knotenintervalle \([\xi _k, \xi _{k+1})\), wobei Terme mit \(0\) als Nenner weggelassen werden.

Jeder B-Spline \(b_{k,\xi }^n\) ist durch seine Knoten \(\xi _k, \dotsc , \xi _{k+n+1}\) eindeutig bestimmt und verschwindet außerhalb des Intervalls \([\xi _k, \xi _{k+n+1})\). Außerdem ist \(b_{k,\xi }^n\) auf jedem nicht-leeren Knotenintervall \([\xi _\ell , \xi _{\ell +1})\) mit \(\ell = k, \dotsc , k + n\) ein nicht-negatives Polynom vom Grad \(\le n\).
Falls der Grad und die Knotenfolge bei der Diskussion eines bestimmten Themas fixiert sind, schreibt man \(b_k = b_{k,\xi }^n\), um eine übermäßige Nutzung von tief- und hochgestellten Indizes zu vermeiden.

Bernstein-Polynome als B-Splines: Die B-Splines enthalten die Bernstein-Polynome als Spezialfall. Der B-Spline \(b_{k,\xi }^n\) mit den Knoten

\begin{align*} 0 = \xi _k = \dotsb = \xi _n < \xi _{n+1} = \dotsb = \xi _{k+n+1} = 1 \end{align*} entspricht einem Bernstein-Polynom:

\begin{align*} b_{k,\xi }^n(x) = b_k^n(x) = \binom {n}{k} (1 - x)^{n - k} x^k,\quad 0 \le x < 1. \end{align*}

erstes und letztes B-Spline-Segment: Für \(\xi _k < \xi _{k+1}\) ist bloß der erste Summand in der Rekursion für \(b_{k,\xi }^n\) auf dem Intervall \([\xi _k, \xi _{k+1})\) ungleich Null. Daher ist auf diesem Intervall der B-Spline ein Produkt der Faktoren \(\gamma _{k,\xi }^m\):

\begin{align*} b_{k,\xi }^n(x) = \frac {(x - \xi _k)^n}{(\xi _{k+1} - \xi _k) \dotsm (\xi _{k+n} - \xi _k)},\quad \xi _k \le x < \xi _{k+1}. \end{align*} Eine analoge Formel gilt für das am weitesten rechts liegende Intervall \([\xi _{k+n}, \xi _{k+n+1})\) des Trägers von \(b_{k,\xi }^n\). Insbesondere gilt für \(\xi _{k+1} = \dotsb = \xi _{k+n}\), dass der B-Spline aus zwei Monomen zusammengesetzt ist, die am mittleren Knoten \(1\) ergeben.

stetige Abhängigkeit vom Knotenvektor: Wenn \(x\) im Inneren von einem der Knotenintervalle des B-Splines \(b_{k,\xi }^n\) liegt und

\begin{align*} \eta _\ell \to \xi _\ell ,\quad \ell = k, \dotsc , k + n + 1, \end{align*} dann gilt

\begin{align*} \lim _{\eta \to \xi } b_{k,\eta }^n(x) = b_{k,\xi }^n(x). \end{align*}

Ableitung eines B-Splines

Ableitung eines B-Splines: Die Ableitung eines B-Splines vom Grad \(n\) mit den Knoten \(\xi _k, \dotsc ,\)
\(\xi _{k+n+1}\) ist die gewichtete Differenz zweier B-Splines vom Grad \(n - 1\). Auf jedem Knotenintervall \([\xi _\ell , \xi _{\ell +1})\) gilt

\begin{align*} (b_{k,\xi }^n)’ = \alpha _{k,\xi }^n b_{k,\xi }^{n-1} - \alpha _{k+1,\xi }^n b_{k+1,\xi }^{n-1},\quad \alpha _{k,\xi }^n := \frac {n}{\xi _{k+n} - \xi _k}, \end{align*} wobei Terme mit \(0\) als Nenner weggelassen werden.

Aus der Rekursion folgt, dass \(b_{k,\xi }\) an einem Knoten \(\xi _\ell \) \((n - m)\)-mal stetig differenzierbar ist, falls \(\xi _\ell \) unter \(\xi _k, \dotsc , \xi _{k+n+1}\) die Vielfachheit \(m \le n\) besitzt. Insbesondere ist \(b_{k,\xi }^n\) stetig auf \(\real \), falls keiner der Knoten die Vielfachheit \(n + 1\) hat.

Nullstellenordnungen bei B-Splines: Mithilfe der Ableitungsformel kann man auch das genaue Verhalten eines B-Splines an den Endpunkten seines Trägers bestimmen. Wenn \(\xi _k\) die Vielfachheit \(m\) unter den Knoten von \(b_{k,\xi }^n\) besitzt, dann ist der linke Endpunkt \(\xi _k\) des B-Spline-Trägers eine Nullstelle der Ordnung \(n + 1 - m\).

Dies folgt per Induktion über dem Grad: Für den Induktionsschritt von \(n - 1\) nach \(n\) bemerkt man, dass die zwei B-Splines von Grad \(n - 1\) im Ausdruck von \((b_{k,\xi }^n)’\) jeweils Nullstellen von Ordnung \(n - m\) und \(n - (m - 1)\) besitzen. Daher hat \((b_{k,\xi }^n)’\) in \(\xi _k\) eine Nullstelle der Ordnung \(n - m\). Durch Integration erhöht sich die Ordnung um \(1\).

Darstellung von Polynomen durch B-Splines

Marsden-Identität: Für eine bi-unendliche Knotenfolge \(\xi \) mit \(\lim _{k \to \pm \infty } \xi _k = \pm \infty \) kann jedes Polynom vom Grad \(\le n\) durch eine Linearkombination von B-Splines dargestellt werden. Genauer gilt für beliebige \(y \in \real \)

\begin{align*} (x - y)^n = \sum _{k \in \integer } \psi _{k,\xi }^n(y) b_{k,\xi }(x),\quad x \in \real , \end{align*} mit \(\psi _{k,\xi }^n(y) := (\xi _{k+1} - y) \dotsm (\xi _{k+n} - y)\).

Durch Differentiation der Identität nach \(y\) und Auswertung in \(y = 0\) erhält man explizite Darstellungen für die Monome \(x^m\). Es gilt z. B.

\begin{align*} 1 = \sum _k b_{k,\xi }^n(x),\quad x = \sum _k \xi _k^n b_{k,\xi }^n(x) \end{align*} mit \(\xi _k^n := (\xi _{k+1} + \dotsb + \xi _{k+n})/n\) den Knotenmitteln.

Einschränkung des Parameters: Die Marsden-Identität ist zwar für bi-unendliche Knotenfolgen formuliert, die sich über die ganze reelle Achse erstrecken. Offensichtlich kann man aber auch endliche Knotenfolgen betrachten. Wenn man \(x\) auf ein Knotenintervall \(D_\ell = [\xi _\ell , \xi _{\ell +1})\) einschränkt, sind nur B-Splines mit Träger, die \(D_\ell \) überlappen, relevant:

\begin{align*} (x - y)^n = \sum _{k=\ell -n}^\ell \psi _{k,\xi }^n(y) b_{k,\xi }^n(x),\quad \xi _\ell \le x < \xi _{\ell +1}, \end{align*} falls \(\xi \) die involvierten Knoten \(\xi _{\ell -n}, \dotsc , \xi _{\ell +n+1}\) enthält.

Beispiel (Darstellung der Standard-Parabel durch B-Splines): Die Darstellung des Monoms \(x^2\) erhält man durch Koeffizientenvergleich in der Marsden-Identität bei \((-y)^{n-2}\) und Division durch \(\binom {n}{2}\) auf beiden Seiten:

\begin{align*} x^2 = \sum _k c_k b_k(x),\quad c_k = \frac {2}{n(n - 1)} \sum _{1 \le i < j \le n} \xi _{k+i}\xi _{k+j}, \end{align*} da die Summe gleich dem Koeffizienten von \((-y)^{n-2}\) in einer Entwicklung von \(\psi _{k,\xi }^n\) ist. Mit

\begin{align*} \xi _k^n := \frac {1}{n} \sum _{\ell =1}^n \xi _{k+\ell },\quad \sigma _k^2 := \frac {1}{n - 1} \sum _{\ell =1}^n (\xi _{k+\ell } - \xi _k^n)^2 \end{align*} den Knotenmitteln und der geometrischen Varianz von \(n\) aufeinanderfolgenden Knoten kann man \(c_k\) kompakter schrieben, denn es gilt

\begin{align*} c_k = (\xi _k^n)^2 - \sigma _k^2/n. \end{align*}

Splines

Spline: Ein Spline \(p\) vom Grad \(\le n\) mit Knotenfolge \(\xi \) auf einem Parameterintervall \(D\) ist eine Linearkombination der B-Splines \(b_k = b_{k,\xi }^n\):

\begin{align*} p(x) = \sum _{k \sim D} c_k b_k(x),\quad x \in D. \end{align*} Der Summenindex läuft über alle relevanten B-Splines, d. h. die B-Splines, die an Punkten \(x\) in \(D\) nicht verschwinden. Die Koeffizienten \(c_k\) sind eindeutig bestimmt, d. h. die B-Splines formen eine Basis des Spline-Raums \(S_\xi ^n(D)\).

Ein Standard-Spline-Raum \(S_\xi ^n\) hat eine endliche Knotenfolge \(\xi _0, \dotsc , \xi _{m+n}\) mit Vielfachheiten \(\le n\), das Parameterintervall \(D = [\xi _n, \xi _m]\) und relevante B-Splines \(b_0, \dotsc , b_{m-1}\). Der Raum besteht aus allen stetigen Funktionen, die

auf den abgeschlossenen Knotenintervallen \([\xi _\ell , \xi _{\ell +1}]\) in \(D\) Polynome vom Grad \(\le n\) und
an Knoten im Inneren von \(D\) mit Vielfachheit \(\mu \) mindestens \((n - \mu )\)-mal stetig differenzierbar sind.

\(S_\xi ^n\) hat die \(\real \)-Dimension \(m\).

Beispiel (Knotenfolgen bei kubischen Splines): In Anwendungen sind kubische Splines wichtig. Zwei häufig benutzte Knotenfolgen sind:

einfache Knoten: Wenn \(\xi _0 < \dotsb < \xi _{m+3}\) gilt, dann besteht der Standard-Spline-Raum \(S_\xi ^3\) aus allen zweifach stetig differenzierbaren Funktionen, die Polynome vom Grad \(\le 3\) auf jedem abgeschlossenen Knotenintervall \([\xi _\ell , \xi _{\ell +1}]\) in \(D = [\xi _3, \xi _m]\) sind.
doppelte Knoten: Wenn \(\xi _0 = \xi _1 < \xi _2 = \xi _3 < \dotsb < \xi _m = \xi _{m+1} < \xi _{m+2} = \xi _{m+3}\) gilt, dann können die zweiten Ableitungen der kubischen Splines Sprünge besitzen. In diesem Fall sind die kubischen Splines auf jedem abgeschlossenen Knotenintervall \([\xi _{2k-1}, \xi _{2k}]\) eindeutig bestimmt durch die Werte und Ableitungen an den Knoten. Diese Daten stellen bei der Bestimmung eines Splines in \(S_\xi ^3\) eine Alternative zur B-Spline-Basis dar.

Beispiel (äußere Knoten beim Standard-Spline-Raum): Für eine Knotenfolge
\(\xi _0, \dotsc , \xi _{n+m}\) benötigt die B-Spline-Basis des Standard-Spline-Raums \(S_\xi ^n\) \(n\) äußere Knoten auf jeder Seite des Parameterintervalls \(D = [\xi _n, \xi _m]\). Diese Knoten \(\xi _k\) mit \(k < n\) oder \(k > m\) sind für die Definition von \(S_\xi ^n\) bezüglich der abschnittsweisen polynomialen Struktur irrelevant. Jedoch beeinflussen sie die B-Spline-Basis. Es gibt zwei Standardfälle:

einfache äußere Knoten: Mit \(\Delta \xi _\ell := \xi _{\ell +1} - \xi _\ell \) definiert man \(\xi _{n-\ell } := \xi _n - \ell \Delta \xi _n\) und \(\xi _{m+\ell } := \xi _m + \ell \Delta \xi _{m-1}\) für \(\ell = 1, \dotsc , n\). Diese Wahl der Knoten erhält den Abstand zwischen Knoten auf dem ersten und letzten Knotenintervall in \(D\) und maximiert die Glattheit der B-Splines.
mehrfache äußere Knoten: Man definiert \(\xi _1 := \dotsb := \xi _n\) und \(\xi _m := \dotsb := \xi _{m+n-1}\) und wählt nur \(\xi _0\) und \(\xi _{m+n}\) außerhalb des Intervalls \(D\). Wegen der maximal möglichen Vielfachheit sind nur die B-Splines \(b_0\) und \(b_{m-1}\) nicht Null auf den Intervallendpunkten (diese sind dort gleich Eins). Daher gilt für einen Spline \(p = \sum _{k=0}^{m-1} c_k b_k\), dass \(p(\xi _n) = c_0\) und \(p(\xi _m) = c_{m-1}\). Der Nachteil der Vielfachheit \(n\) ist, dass die Ableitungen der B-Splines nicht länger stetig sind. Die Konvention der Stetigkeit von rechts führt daher zu einem asymmetrischen Verhalten auf den Intervallendpunkten von \(D\).

uniforme B-Splines: Der uniforme B-Spline \(b^n\) hat die Knoten \(0, 1, \dotsc , n + 1\). In diesem Spezialfall vereinfachen sich die Rekursionen für Auswertung und Differentiation:

\begin{align*} n b^n(x) &= xb^{n-1}(x) + (n + 1 - x)b^{n-1} (x - 1),\\ \frac {d}{dx} b^n(x) &= b^{n-1}(x) - b^{n-1}(x - 1). \end{align*} Die zweite Gleichung kann als Bildung eines Mittelwerts geschrieben werden:

\begin{align*} b^n(x) = \int _0^1 b^{n-1}(x - y)\dy . \end{align*} Die B-Splines für eine beliebige uniforme Knotenfolge

\begin{align*} \xi = h\integer \colon \dotsc , -h, 0, h, \dotsc , \end{align*} sind skalierte Translate von \(b^n\), d. h. \(b_{k,h}^n(x) := b^n(x/h - k)\), \(k \in \integer \).

Beispiel (Rekursion für die Taylor-Koeffizienten von uniformen B-Splines):
Die Rekursion für die Auswertung kann auch als Rekursion für die Taylor-Koeffizienten der polynomialen Abschnitte eines uniformen B-Splines formuliert werden. Für \(x \in [k, k + 1)\) definiert man

\begin{align*} p_k^n(y) := \sum _{\ell =0}^n a_{k,\ell }^n y^\ell = b^n(x),\quad x - k = y \in [0, 1). \end{align*} Damit kann die Rekursion umgeschrieben werden zu

\begin{align*} np_k^n(y) = (k + y)p_k^{n-1}(y) + (n + 1 - k - y) p_{k-1}^{n-1}(y),\quad k = 0, \dotsc , n, \end{align*} mit \(p_{-1}^{n-1} = p_n^{n-1} = 0\). Die entsprechende Identität für die Koeffizienten ist

\begin{align*} n a_{k,\ell }^n = k a_{k,\ell }^{n-1} + a_{k,\ell -1}^{n-1} + (n + 1 - k) a_{k-1,\ell }^{n-1} - a_{k-1,\ell -1}^{n-1} \end{align*} mit \(a_{k,-1}^{n-1} = a_{k,n}^{n-1} = 0\). Die ersten paar Koeffizientenvektoren lauten

\begin{align*} a_0^1 &= \left (0, 1\right ), & a_1^1 &= \left (1, -1\right ),\\ a_0^2 &= \left (0, 0, \frac {1}{2}\right ), & a_1^2 &= \left (\frac {1}{2}, 1, -1\right ), & a_2^2 &= \left (\frac {1}{2}, -1, \frac {1}{2}\right ),\\ a_0^3 &= \left (0, 0, 0, \frac {1}{6}\right ), & a_1^3 &= \left (\frac {1}{6}, \frac {1}{2}, \frac {1}{2}, -\frac {1}{2}\right ), & a_2^3 &= \left (\frac {2}{3}, 0, -1, \frac {1}{2}\right ), & a_3^3 &= \left (\frac {1}{6}, -\frac {1}{2}, \frac {1}{2}, -\frac {1}{6}\right ). \end{align*} Mithilfe der tabulierten Taylorkoeffizienten kann man uniforme B-Splines schneller als mit der Rekursion auswerten.

Auswertung und Differentiation

Auswertung eines Splines: Ein Spline \(p = \sum _k c_k b_k\) vom Grad \(\le n\) mit Knotenfolge \(\xi \) kann in \(x \in [\xi _\ell , \xi _{\ell +1})\) ausgewertet werden, indem man Konvexkombinationen der Koeffizienten der B-Splines bildet, die in \(x\) nicht verschwinden. Mit

\begin{align*} p_k^0 := c_k,\quad k = \ell - n, \dotsc , \ell , \end{align*} startend berechnet man sukzessive für \(i = 0, \dotsc , n - 1\)

\begin{align*} p_k^{i+1} := \gamma _{k,\xi }^{n-i} p_k^i + (1 - \gamma _{k,\xi }^{n-i}) p_{k-1}^i,\quad k = \ell - n + i + 1, \dotsc , \ell , \end{align*} mit

\begin{align*} \gamma _{k,\xi }^{n-i} := \frac {x - \xi _k}{\xi _{k+n-i} - \xi _k} \end{align*} und erhält \(p(x)\) als letzten Wert \(p_\ell ^n\).

Das entstehende Dreiecksschema vereinfacht sich etwas, wenn \(x = \xi _\ell \) gilt. In diesem Fall gilt \(p(x) = p_{\ell -\mu }^{n-\mu }\), d. h. es sind nur \(n - \mu \) Schritte für \(c_{\ell -n}, \dotsc , c_{\ell -\mu }\) notwendig, wenn \(\xi _\ell \) Vielfachheit \(\mu \) besitzt.

Differentiation eines Splines: Die Ableitung eines Splines ist ein Spline mit derselben Knotenfolge. Genauer gilt für jedes \(x\) in einem offenen Knotenintervall \((\xi _\ell , \xi _{\ell +1})\) mit \(n + 1\) relevanten B-Splines \(b_{k,\xi }^n\)

\begin{align*} \frac {d}{dx} \left (\sum _{k=\ell -n}^\ell c_k b_{k,\xi }^n(x)\right ) = \sum _{k=\ell -n+1}^\ell \alpha _{k,\xi }^n \nabla c_k b_{k,\xi }^{n-1}(x),\quad \alpha _{k,\xi }^n := \frac {n}{\xi _{k+n} - \xi _k} \end{align*} mit \(\nabla \) dem Rückwärts-Differenz-Operator (d. h. \(\nabla c_k := c_k - c_{k-1}\)). Die Identität bleibt auch an den Endpunkten \(\xi _\ell \) und \(\xi _{\ell +1}\) des Knotenintervalls gültig, falls die Knoten Vielfachheit \(< n\) haben.

Für einen Spline \(p = \sum _{k=0}^{m-1} c_k b_k\) in einem Standard-Spline-Raum \(S_\xi ^n\) mit Knotenfolge
\(\xi _0, \dotsc , \xi _{m+n}\) und Vielfachheiten \(< n\) gilt mit \(d_k := \alpha _{k,\xi } \nabla c_k\)

\begin{align*} p’ = \sum _{k=1}^{m-1} d_k b_{k,\xi ’}^{n-1} \in S_{\xi ’}^{n-1}, \end{align*} wobei \(\xi ’\) aus \(\xi \) durch Weglassen des ersten und des letzten Knotens entsteht. Dies ist mit der Differenzenbildung \(\nabla \) konsistent, weil die Anzahl der möglichen Indizes um Eins reduziert wird.

Periodische Splines

periodische Splines: Ein Spline \(p = \sum _{k \in \integer } c_k b_k \in S_\xi ^n(\real )\) mit einer bi-unendlichen Knotenfolge \(\xi \) ist \(T\)-periodisch genau dann, wenn die Knoten \(\xi _k\) und die Koeffizienten \(c_k\) die Periodizitätsbedingungen

\begin{align*} \xi _{k+M} = \xi _k + T,\quad c_{k+M} = c_k,\quad k \in \integer , \end{align*} erfüllen (für ein \(M \in \natural \)).

Die periodischen Splines bilden einen Unterraum \(S_{\eta ,T}^n\) von \(S_\xi ^n(\real )\) der Dimension \(M\), wobei \(\eta \) eine beliebige Teilfolge von \(M\) aufeinanderfolgenden Knoten aus \(\xi \) ist.