Spline

Beispiel eines Splines mit 8 Knoten

Geflecht: Die Geometrie der horizontalen Zweige kann mit Splines beschrieben werden

Ein Spline n-ten Grades (auch Polynomzug) ist eine Funktion, die stückweise aus Polynomen höchstens n-ten Grades zusammengesetzt ist. Dabei werden an den Stellen, an denen zwei Polynomstücke zusammenstoßen (man spricht auch von Knoten), bestimmte Bedingungen gestellt, etwa dass der Spline (n-1)-mal stetig differenzierbar ist.

Handelt es sich bei dem Spline in all seinen Abschnitten um jeweils eine lineare Funktion, so nennt man den Spline linear (es handelt sich dann um einen Polygonzug), analog gibt es quadratische, kubische usw. Splines.

Zu den Pionieren der Spline-Erforschung gehören Isaac Jacob Schoenberg (ab den 1940er Jahren), Paul de Faget de Casteljau, Pierre Bézier und Carl de Boor.

Allgemeines

Der Begriff Spline wurde zuerst in einer englischen Veröffentlichung von Isaac Jacob Schoenberg im Jahr 1946 für glatte, harmonische, zusammengesetzte mathematische Kurven dritten Grades benutzt.

Splines werden vor allem zur Interpolation und Approximation benutzt. Durch die stückweise Definition sind Splines flexibler als Polynome und dennoch relativ einfach und glatt. Dadurch ergeben sich bei der Spline-Interpolation nicht die Nachteile, die durch die starke Oszillation von Polynomen höheren Grades und deren Unbeschränktheit bei der Polynominterpolation entstehen (Runges Phänomen). Splines lassen sich auch gut benutzen, um Kurven darzustellen. Hier finden sie Einsatz im CAD. Mathematisch analog lassen sich auf beide Weisen nicht nur Kurven, sondern auch Flächen beschreiben.

Wortherkunft: Der Begriff stammt aus dem Schiffbau: eine lange, dünne Latte (Straklatte, englisch spline), die an einzelnen Punkten durch Molche fixiert wird, biegt sich genau wie ein kubischer Spline mit natürlicher Randbedingung. Dabei wird die Spannungsenergie minimal.

Spline-Raum

Funktionen $p:[{\tau }_0,{\tau }_{n-1}[\to ℝ$, die sich in jedem der Teilintervalle $[{\tau }_i,{\tau }_{i+1}[$ einer streng wachsenden Knotenfolge $\tau :=({\tau }_i{)}_{i=0,.\dots ,n-1}\in {ℝ}^n$ als Polynome mit Maximalgrad $d\in {\mathbb{Z}}_{\ge 0}$ darstellen lassen, heißen stückweise Polynomfunktionen auf $\tau$ (mit Maximalgrad $d$).

Außer diesem einfachen Aufbau aus Polynomabschnitten verlangt man bei Splines auch noch maximale Glattheit.

Der Spline-Raum $S_{d,\tau }$ ist der Vektorraum aller $(d-1)$-mal stetig differenzierbaren stückweisen Polynomfunktionen auf $\tau$ mit Maximalgrad $d$.

Bei der Konstruktion von Splines erweisen sich die abgeschnittenen Potenzfunktionen

$(u{)}_{+}^d:=\{\begin{array}{cc}0& \text{ für}u<0\\ u^d& \text{ für}u\ge 0\end{array}$

mit $d=0,1,\dots$ als nützlich. $(u{)}_{+}^d$ ist für $d=0$ die Sprungfunktion, für $d=1$ die Rampenfunktion, und für $d\ge 1$ ist diese Funktion $(d-1)$-mal stetig differenzierbar.

Jede stückweise Polynomfunktion auf $\tau$ mit Maximalgrad $d$ ist mit eindeutig bestimmten Koeffizienten $c_{i,j}\in ℝ$, $(i=0,\dots ,d;j=0,\dots ,n-2)$ in der Form

$p(u)=\sum _{j=0}^{n-2}\sum _{i=0}^d{c}_{i,j}(u-{\tau }_j{)}_{+}^i$

darstellbar. Da Splines $(d-1)$-mal stetig differenzierbar sein sollen, müssen bei ihnen die Koeffizienten $c_{i,j}$ für die niedrigeren Potenzen $i=0,\dots ,d-1$, die die Differenzierbarkeitsforderung nicht erfüllen, an den inneren Knoten $j=1,\dots ,n-2$ verschwinden. Splines $p\in S_{d,\tau }$ haben also die Darstellung

$p(u)=\sum _{i=0}^d{c}_{i,0}(u-{\tau }_0{)}_{+}^i+\sum _{j=1}^{n-2}{c}_{d,j}(u-{\tau }_j{)}_{+}^d.$

Die (auf $[{\tau }_0,{\tau }_{n-1}[$ eingeschränkten) Funktionen $(u-{\tau }_0{)}_{+}^i$ für $i=0,\dots ,d$ und $(u-{\tau }_j{)}_{+}^d$ für $j=1,\dots ,n-2$ stellen also zusammen eine Basis für den Splineraum $S_{d,\tau }$ dar. Damit ist der Splineraum $(n+d-1)$-dimensional.

Die $(d-1)$-malige Differenzierbarkeit der Splines kann man gezielt an vorgegebenen Knotenpunkten wieder abschwächen. In obiger Darstellung erreicht man das durch Wiederhinzunehmen ausgewählter Basisfunktionen niedrigeren Grades an inneren Knoten. Beim Algorithmus von De-Boor zur Darstellung von Splines ergibt sich das automatisch, wenn man mehrfache Knoten in der Knotensequenz zulässt, genauer die Forderung ${\tau }_i<{\tau }_{i+1}$ für $i=0,\dots ,n-2$ abschwächt zu ${\tau }_i\le {\tau }_{i+1}$ für $i=0,\dots ,n-2$ und ${\tau }_i<{\tau }_{i+d+1}$ für $i=0,\dots ,n-d-2$.

Die in Mathematik und Technik genutzten Varianten der Splines, wie B-Splines oder kubische Splines, unterscheiden sich im Wesentlichen durch die für den Spline-Raum eingesetzte Basis.

Grad und Ordnung

Spline-Kurven werden in der Regel entweder, wie oben beschrieben, über den Grad der stückweise zusammengesetzten Polynome definiert oder über deren Ordnung. Hierbei werden für den Grad meist die Buchstaben $d$ oder $p$ verwendet, während es üblich ist, für die Ordnung den Buchstaben $k$ zu verwenden. Hierbei gilt der Zusammenhang:

$k=d+1$

Kubische Splines

Kubische Splines werden unter anderem zur Berechnung des Bahnverlaufs bei Achterbahnen verwendet, um ruckartige Beschleunigungswechsel für die Fahrgäste zu vermeiden. Kubische Splines finden weitere Anwendung bei der exakten Verlegung der Schienen bei Hochgeschwindigkeitsstrecken der Eisenbahn. Auch beim Entwurf von Kurven und Oberflächen (sogenannte „Freiformkurven und -flächen“), wie sie häufig im Schiff-, Flugzeug- und Automobilbau vorkommen, sind Splines von Bedeutung.

Splines eignen sich für solche Anwendungen, weil für jeden Polynomabschnitt Randbedingungen sowohl in Form von Punkten als auch in Form von Werten für die erste und zweite Ableitung (und abhängig davon Steigung und Krümmung bzw. Kurvenradius) vorgegeben werden können. Dadurch kann eine über den gesamten Kurvenverlauf stetige Krümmung erreicht werden. So werden Querbeschleunigungen beim Abfahren der Kurve immer allmählich aufgebaut bzw. an den Knotenpunkten vorgegebene Werte eingehalten.

Burmester-Schablonen stellen kubische Splines dar. Diese Schablonen werden genutzt, um Ausgleichskurven von Wertescharen zu zeichnen.

B-Splines

B-Spline-Kurven dritter Ordnung, mit Knoten bei 0, 0,5 and 1

B-Spline ist die Kurzform von Basis-Spline. Im Kontext numerischer Verfahren, wo Splines häufig eingesetzt werden, entscheidet die Wahl der Basis für den Spline-Raum über eventuelle Rundungsfehler und damit über die praktische Einsetzbarkeit. Eine bestimmte Basis hat sich hier als am besten geeignet herausgestellt: Sie ist numerisch stabil und erlaubt die Berechnung von Werten der Spline-Funktion mittels einer Drei-Term-Rekursion. Diese sogenannten B-Spline-Basisfunktionen haben einen kompakten Träger, sie sind nur auf einem kleinen Intervall von Null verschieden. Änderungen der Koeffizienten wirken sich also nur lokal aus.

Carl de Boor weist in seinem Artikel B(asic) Spline Basics darauf hin, dass der Begriff B-Spline ursprünglich für bestimmte Splines mit minimalem Träger eingeführt wurde, dass sich jedoch im Bereich von Computer Aided Geometric Design die etwas unglückliche Verwendung des Begriffs B-Spline für Splines eingebürgert hat, die in der B-Spline-Basis dargestellt werden.

Definition

Die als Basis-Splines (B-Splines) bezeichneten Basisfunktionen $N_{i,p,\tau }(i=0,\dots ,n-p-2)$ des Grads $p$ mit Knotenvektor $\tau =({\tau }_0,\dots ,{\tau }_{n-1})(n\ge 2p)$ sind von Curry und Schoenberg 1947 bis auf die Normierung in folgender Form eingeführt worden:

$N_{i,p,\tau }(u)=({\tau }_{i+p+1}-{\tau }_i)[{\tau }_i,\dots ,{\tau }_{i+p+1}{]}_{\bar{u}}(\overline{u}-u{)}_{+}^p$

Dabei steht $[{\tau }_i,\dots ,{\tau }_{i+p+1}{]}_{\bar{u}}(\overline{u}-u{)}_{+}^p$ für die $(p+1)$-ste dividierte Differenz der abgeschnittenen Potenzfunktion $(\tau -u{)}_{+}^p$ bzgl. $\tau$. Die dividierte Differenz $[x_0,\dots ,x_d{]}_{x}f(x)$ ist der zu $x^d$ gehörige Koeffizient im (eindeutig gegebenen) Polynom $c_0+c_{1}x+c_2{x}^2+\dots +c_d{x}^d$, das die Funktion $f$ an den Stellen $x_0,\dots ,x_d$ interpoliert. Stimmen die Werte von $k$ der Variablen $x_i$ überein, so interpoliert das Polynom die Funktion $f$ an dieser Stelle bis zur $(k-1)$-ten Ableitung (oskulierende Interpolation, engl.: `osculating interpolation').

In obiger Definition von $N_{i,p,\tau }(u)$ gilt $(\overline{u}-u{)}_{+}^p=(\overline{u}-u{)}^p$ für $\overline{u}={\tau }_i,\dots ,{\tau }_{i+p+1}$ solange $u$ kleiner ${\tau }_i$ bleibt. In diesem Bereich für $u$ ergibt sich also eine dividierte Differenz vom Grad $p+1$ für ein Polynom $p$-ten Grades, die trivialerweise null ist. Auf der anderen Seite ist für $u>{\tau }_{i+p+1}$ die Funktion $(\overline{u}-u{)}_{+}^p$ an allen für die dividierte Differenz auszuwertenden Stellen bei $N_{i,p,\tau }(u)$ gleich null, womit dort ebenfalls $N_{i,p,\tau }(u)=0$ gilt.

Der Träger von $N_{i,p,\tau }(u)$ liegt also innerhalb des Intervalls $[{\tau }_i,{\tau }_{i+p+1}]$.

Unterscheiden sich die Stellen ${\tau }_i$ alle voneinander, so ist die dividierte Differenz in $N_{i,p,\tau }$ eine endliche Linearkombination von Funktionen $u\mapsto (\overline{u}-u{)}_{+}^p$ mit unterschiedlichen Werten für $\overline{u}$ und als solche $(p-1)$-mal stetig differenzierbar.

Eigenschaften

Die folgenden Eigenschaften zeichnen die B-Splines $N_{i,p,\tau }(u)$ mit $i=0,\dots ,n-p-2$ im Raum der Splines $S_{p,\tau }$ mit Knotenvektor $\tau =({\tau }_i{)}_{i=0}^{n-1}$ und Maximalgrad $p$ aus:

• Nicht-Negativität: $N_{i,p,\tau }(u)\ge 0$
• Lokaler Träger: $N_{i,p,\tau }(u)>0$ falls $u\in ]{\tau }_i,{\tau }_{i+p+1}[$ und $N_{i,p,\tau }(u)=0$ falls $u\in ̸[{\tau }_i,{\tau }_{i+p+1}[$
• Zerlegung der Eins: $\sum _{i=0}^{n-p-2}{N}_{i,p,\tau }(u)=1$ für $u\in [{\tau }_p,{\tau }_{n-p-1}[$

Effiziente Berechnung

Die Basis-Splines können effektiv mit der Rekursionsformel von de Boor/Cox/Mansfield berechnet werden:

$N_{i,0,\tau }(u)=\{\begin{array}{cc}1,& u\in [{\tau }_i,{\tau }_{i+1}[\\ 0,& \text{sonst}\end{array}$

und

$N_{i,p,\tau }(u)=\frac{u-{\tau }_i}{{\tau }_{i+p}-{\tau }_i}{N}_{i,p-1,\tau }(u)+\frac{{\tau }_{i+p+1}-u}{{\tau }_{i+p+1}-{\tau }_{i+1}}{N}_{i+1,p-1,\tau }(u)$ für $p>0$.

Die Elemente des Knotenvektors heißen auch Knotenpunkte (engl. knots) und müssen die Bedingungen ${\tau }_i\le {\tau }_{i+1}$ und ${\tau }_i<{\tau }_{i+p}$ erfüllen.

Zur Berechnung der Ableitung eines B-Splines kann man obige Rekursionsformel mit der folgenden Vorschrift kombinieren:

$\frac{d}{du}{N}_{i,p,\tau }(u)=N{\text{'}}_{i,p,\tau }(u)=\frac{p}{{\tau }_{i+p}-{\tau }_i}{N}_{i,p-1,\tau }(u)-\frac{p}{{\tau }_{i+p+1}-{\tau }_{i+1}}{N}_{i+1,p-1,\tau }(u)$ für $p\ge 1$.

Bemerkung:

Die Bedingungen an die Knotenpunkte ${\tau }_i$ erlauben es, dass in der Rekursionsformel unter Umständen Null als Nenner auftritt (nämlich wenn ${\tau }_{i+p}={\tau }_i$ bzw. ${\tau }_{i+p+1}={\tau }_{i+1}$ gilt). Allerdings ist dann die Funktion $N_{i,p,\tau }$ bzw. $N_{i+1,p,\tau }$ automatisch die Nullfunktion. Auf die entsprechende Fallunterscheidung wird hier verzichtet, man ignoriere die entsprechenden Summanden in diesen Fällen (ersetze sie durch Null). Dies entspricht auch dem Grenzverhalten für z. B. ${\tau }_{i+p}\to {\tau }_i.$

B-Spline-Kurve

Eine Spline-Kurve, deren Darstellung auf B-Splines beruht, nennt man B-Spline-Kurve. Bestimmt wird die Kurve durch sogenannte De-Boor-Punkte, mit denen sich das Aussehen der Kurve leicht steuern lässt: Die Kurve liegt immer in der konvexen Hülle der De-Boor-Punkte, wird also von ihnen eingeschlossen.

Eine B-Spline-Kurve $C(u),u\in [{\tau }_p,{\tau }_{n-p-1}[$ des Maximalgrads $p$ mit Knotenvektor $\tau$ (s. o.) und Kontrollpunkten $P_i(i=0,\dots ,n-p-2)$ (auch De-Boor-Punkte genannt) wird definiert durch

$C(u)=\sum _{i=0}^{n-p-2}{P}_i{N}_{i,p,\tau }(u)$.

Für Kurven in der Ebene sind die Kontrollpunkte zweidimensional, für Kurven im Raum dreidimensional.

Eigenschaften:

• Lokalität: Der Kontrollpunkt $P_i$ beeinflusst die Kurve nur im Intervall $[{\tau }_i,{\tau }_{i+p+1}[$
• Endpunkt-Interpolation: Es ist $P_0=C({\tau }_p)$, falls die ersten $p+1$ Knotenpunkte ${\tau }_0,\dots ,{\tau }_p$ gleich sind und $P_{n-p-2}=C({\tau }_{n-1-p})$, falls die letzten $p+1$ Knotenpunkte ${\tau }_{n-1-p},\dots ,{\tau }_{n-1}$ gleich sind.

Eine ähnliche Darstellung haben Bézierkurven. Diese basieren nicht auf der oben genannten Basis, sondern auf den Bernsteinpolynomen. Genau wie bei B-Spline-Kurven die De-Boor-Punkte gibt es hier die Bézier-Punkte, die das sogenannte Kontrollpolygon bilden und mit denen man die Kurve leicht graphisch darstellen kann.

Einen einfachen Zusammenhang von Bézierkurven und B-Spline-Kurven in Verbindung mit einer einfachen Berechnung stellt das Blossoming dar, welches von Paul de Faget de Casteljau Anfang der 1980er Jahre entdeckt und von Lyle Ramshaw verbreitet wurde.

Algorithmus von De Boor

Statt der Gleichung in obiger Definition für $C(u)$ wird zur effizienten Berechnung von B-Spline-Kurven $C(u)$ mit $u$ im Intervall $[{\tau }_p,{\tau }_{n-p-1}[$ meist der im Folgenden beschriebene Algorithmus von De Boor verwendet.

1. Suche $i\in \{0,\dots ,n-p-2\}$, so dass $u\in [{\tau }_i,{\tau }_{i+1}[$ gilt.
   Gibt es keinen solchen Index $i$, so liegt $u$ außerhalb des Definitionsbereiches der Splinekurve $C$,
   und es muss extrapoliert oder eine Fehlermeldung ausgegeben werden.
2. Initialisiere Hilfsgrößen $q_{0,j}:=P_{i+j}$ für $j=0,\dots ,d$
3. Führe für $l=1,\dots ,d$ und $j=0,\dots ,d-l$ folgende Teilschritte 3.1 bis 3.3 iterativ aus:
3.1. Im Ausnahmefall gleicher Knoten ${\tau }_{i+j}={\tau }_{i+j+l}$ setze $q_{l,j}:=q_{l-1,j}$ und fahre mit dem nächsten Iterationsschritt $j:=j+1$ bei 3.1. fort.
3.2. Gilt dagegen ${\tau }_{i+j}<{\tau }_{i+j+l}$, so berechne ${\alpha }_{l,j}:=\frac{u-{\tau }_{i+j}}{{\tau }_{i+j+l}-{\tau }_{i+j}}$.
3.3. Berechne damit $q_{l,j}:=q_{l-1,j}\cdot (1-{\alpha }_{l,j})+q_{l-1,j+1}\cdot {\alpha }_{l,j}$.
4. Als Endergebnis der Iteration erhält man $C(u):=q_{d,0}$.

Sind mehrere Splines, die sich nur durch die Koeffizienten $P_i$ unterscheiden, an derselben Stelle $u$ auszuwerten, so kann die in der Definition der B-Spline-Kurve aufgeführte Berechnungsvorschrift $C(u)=\sum _{i=0}^{n-p-2}{P}_i{N}_{i,p,\tau }(u)$ effizienter als der Algorithmus von De Boor sein.

B-Spline-Fläche

Eine B-Spline-Fläche der Maximalgrade $p$ und $q$ in der ersten beziehungsweise zweiten Variablen mit Knotenvektoren $\tau =({\tau }_0,\dots ,{\tau }_{n-1})(n\ge 2p+1)$ und $\mu =({\mu }_0,\dots ,{\mu }_{m-1})(m\ge 2q+1)$ und Kontrollpunkten (bzw. De Boor Punkten) $P_{ij}$ wird definiert durch

$C(u,v)=\sum _{i=0}^{n-p-2}\sum _{j=0}^{m-q-2}{P}_{ij}{N}_{i,p,\tau }(u)N_{j,q,\mu }(v)$

Die Fläche ist definiert über dem Rechteck $[{\tau }_p,{\tau }_{n-1-p}]\times [{\mu }_q,{\mu }_{m-1-q}]$.

Eigenschaften:

• Lokalität: Der Kontrollpunkt $P_{ij}$ beeinflusst die Fläche nur im Rechteck $[{\tau }_i,{\tau }_{i+p}]\times [{\mu }_j,{\mu }_{j+q}]$
• Endpunktinterpolation: Werden die ersten $p+1$ Knotenpunkte in $\tau$ auf den gleichen Wert gesetzt, die letzten $p+1$ Knotenpunkte in $\tau$ auf den gleichen Wert gesetzt, die ersten $q+1$ Knotenpunkte in $\mu$ auf den gleichen Wert gesetzt und die letzten $q+1$ Knotenpunkte in $\mu$ auf den gleichen Wert gesetzt, dann gilt die Endpunktinterpolation, d. h. $P_{0,0}=C({\tau }_p,{\mu }_q)$, $P_{0,m-q-2}=C({\tau }_p,{\mu }_{m-1-q})$, $P_{n-p-2,0}=C({\tau }_{n-1-p},{\mu }_q)$ und $P_{n-p-2,m-q-2}=C({\tau }_{n-1-p},{\mu }_{m-1-q})$

Weitere Varianten und Verallgemeinerungen

Neben den B-Splines gibt es weitere Varianten von Splines, beispielsweise den kubisch hermiteschen Spline. Eine Verallgemeinerung von Splines sind NURBS, die durch stückweise rationale Funktionen anstelle von Polynomen beschrieben werden. Mit NURBS-Kurven sind Kreise exakt darstellbar.

Literatur

• Andrew Blake and Michael Isard: "Active Contours". Springer Verlag, 1998, ISBN 978-1-4471-1555-7
• Carl de Boor: A Practical Guide to Splines. Springer Verlag, New York 1978, ISBN 0-387-90356-9 und ISBN 3-540-90356-9 (Rev. Auf.. 2001 ISBN 0-387-95366-3)
• Paul de Faget de Casteljau: Formes à Pôles. Hermès, Paris 1985, ISBN 2-86601-044-2
• Gerald Farin: Curves and Surfaces for CAGD. A practical guide. 5. Aufl. Academic Press, San Diego 2002 ISBN 1-55860-737-4
• Günther Nürnberger: Approximation by Spline Functions. Springer Verlag, 1989, ISBN 3-540-51618-2 und ISBN 0-387-51618-2
• Hartmut Prautzsch, Wolfgang Böhm, Marco Paluszny: Bezier and B-Spline Techniques. Springer Verlag, Berlin 2001 ISBN 3-540-43761-4
• David Salomon: Curves and Surfaces for Computer Graphics. 2006 Springer Science+Business Media, Inc.; ISBN 0-387-24196-5
• Isaac Jacob Schoenberg: Contributions to the problem of approximation of equidistant data by analytic functions. Quart. Appl. Math., vol. 4, S. 45–99 und 112–141, 1946.
• Martin Hermann: Numerische Mathematik, Band 2: Analytische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065765-4.

Weblinks

• LP – Räume von Spline-Funktionen
• Java-Applet zum Berechnen von B-Spline-Kurven
• Website mit Erklärungen und Tool zur Berechnung von kubischen Splines
• TinySpline: Open Source C-Programmbibliothek für NURBS, B-Splines und Bezier Splines mit Bindings für verschiedene Sprachen