B-Splines

Matheseitenüberblick
Algorithmus von de Casteljau

B-Splines und Bernsteinpolynome

Die Wahrscheinlichkeiten der Binomialverteilung: B_n;p(k) = (n
k)·p^k·(1-p)^n-k geben an, mit welcher Wahrscheinlichkeit ein Experiment, das man n-mal jeweils mit der konstant bleibenden Erfolgswahrscheinlichkeit p durchführt (sogenannte Bernoullikette), k-mal erfolgreich ausgeht. Wenn man beispielsweise einen fairen Würfel 100mal wirft (d.h. n=100 und p= 1
6 für jede der sechs gleichwahrscheinlichen Augenzahlen), würfelt man mit der Wahrscheinlichkeit B_100;1/6(16) = (100
16)·( 1
6)¹⁶·( 5
6)⁸⁴ ≈ 0,10650 = 10,65% genau 16 Sechsen. Dabei liefert der Binomialkoeffizient (100
16) = 100·99·98·...·85
16·15·14·...·1 = 1345860629046814650 die Anzahl der Möglichkeiten, in der Folge dieser 100 Würfe genau 16 erfolgreiche unterzubringen, die jeweils alle die gleiche Erfolgswahrscheinlichkeit ( 1
6)¹⁶·( 5
6)⁸⁴ haben, nämlich eben 16mal Erfolg (eine Sechs) mit jeweils p= 1
6 und 84mal Mißerfolg (keine Sechs) mit jeweils der Gegenwahrscheinlichkeit 1−p = 5
6.

Da es sich bei der Binomialverteilung um eine Zufallsverteilung handelt, ist die Summe der Wahrscheinlichkeiten für alle möglichen Fälle k=0 bis k=n stets 1, d.h. B_n;p(0) + B_n;p(1) + B_n;p(2) + ... + B_n;p(n) = 1 für alle Anzahlen n und alle Wahrscheinlichkeiten p. Das folgt aus dem binomischen Lehrsatz, der besagt, daß (a + b)ⁿ = (n
0)aⁿb⁰ + (n
1)a^n-1b¹ + (n
2)a^n-2b² + ... + (n
n)a⁰bⁿ ist, also beispielsweise (a + b)² = (2
2)a²b² + (2
1)a¹b¹ + (2
0)a⁰b⁰ = 1a²b⁰ + 2a¹b¹ + 1a⁰b² = a² + 2ab + b², die allseits bekannte erste binomische Formel.
Und mit 1-p=a und p=b ist (a+b) = (1-p+p) = 1, und (a+b)ⁿ = 1ⁿ = 1 für alle n. Die o.g. Summe der Binomialwahrscheinlichkeiten für alle Fälle k entspricht ja genau der Summe des binomischen Lehrsatzes für a=1-p und b=p und ist also stets 1.

Der russische Mathematiker Sergei Natanowitsch Bernstein (С. Н. Вернштейн, *1880 in Odessa, †1968 in Moskau) betrachtete die Binomialwahrscheinlichkeiten, die sich bei festem n und auch festem k zu variablem p ergeben, also als Funktionen p ↦ B_n;p(k). Es ergeben sich ganzrationale Polynomfunktionen vom Grad n, denn die p (und 1-p), d.h. reele Zahlen zwischen und 1, stehen nach Ausmultiplizieren der Binome alle in der Basis der Potenzen, und alle Exponenten, also k bzw. n-k, sind ganze Zahlen von 0 bis n. Nach diesem Mathematiker wurden sie Bernsteinpolynome genannt. Zur Unterscheidung von der Binomialverteilung verwende ich hier nicht die übliche Abkürzung B für diese Bernsteinpolynome, sondern BP. Für n=5 und k=3 ist beispielsweise BP₃(p) = B_5;p(3) = 10p³(1-p)² = 10p³(1-2p+p²) = 10p⁵ - 20p⁴ + 10p³. Wie oben dargestellt, ist die Summe aller Bernsteinpolynome (wieder umgekehrt) für festes p und alle k stets 1.

Es sei nun eine Anzahl von n+1 Punkten P₀, P₁, ..., P_n gegeben. Nimmt man die Binomialwahrscheinlichkeiten als deren Gewichte, d.h. für den ersten Punkt ist die Gewichtung B_n;p(0), für den zweiten B_n;p(1) usw., bekommt man für jedes p aus dem Bereich 0 bis 1 eine spezielle Gewichteverteilung. Stellt man die sich als Anziehungskräfte vor, die die n+1 Punkte auf einen Raumpunkt S, der dem Wert p zugeordnet ist, jeweils ausüben, so ergibt sich dessen Ortsvektor OS anschaulich als gewichtetes Mittel aus den n+1 Ortsvektoren der gegebenen Punkte mit OS = BP₀(p)·OP₀ + BP₁(p)·OP₁ + ... + BP_n(p)·OP_n. Das kann natürlich für die einzelnen Koordinaten separat berechnet werden. Die x-Koordinate des Splinepunktes S für ein gewisses p ist beispielsweise: x_S(p) = BP₀(p)·x₀ + BP₁(p)·x₁ + ... + BP_n(p)·x_n, wobei die x_i die x-Koordinaten der n+1 gegebenen Stützpunkte darstellen.

Durchläuft nun p alle möglichen Werte (von 0 bis 1, denn es sind Wahrscheinlichkeiten), durchlaufen die sich bei dieser Gewichtung ergebenden Punkte S eine Kurve vom Startpunkt P₀ bis zum Endpunkt P_n. Da es sich um eine Kurve handelt, die über einen Parameter definiert ist, verwendet man (wie dafür üblich) das Symbol t (statt p). Die sich ergebenden Kurven nennt man auch B-Splines bzw. B-B-Splines. (Das andere B steuert Pierre Bézier bei, der diese Kurven Anfang der 1960er-Jahre als Designer bei und für Renault verwendete. Paul de Faget de Casteljau bei Citroën entwickelte unabhängig davon das selbe Verfahren, allerdings mit einem rekursiven und numerisch sehr stabilen Verfahren (siehe →hier). Er starb übrigens erst vor kurzem, 91jährig, am 24. März 2022. Bernstein wurde 88, Bézier 89.)

Alsbald wurde diese wegen der ausschließlichen Verwendung von Grundrechenarten für Computer sehr geeignete und bezüglich der Modellierung von kurvigen Formen im Wortsinn sehr flexible Möglichkeit für viele weitere Anwendungen in der Informatikwelt und im computergestützen Design genutzt, etwa für vektorbasierte (und daher stufenlos skalierbare) Schriftarten (Postscript, TrueType, OpenType ...), wobei sich diese auf Splines 3. oder sogar nur 2. Grades beschränken. Siehe dazu →hier. (Die verlinkte Seite ist zwar derzeit noch im Entwurfsstadium — es fehlen weitgehend alle Erklärungen — die interaktiven Elemente funktionieren aber schon prima, und die nachzutragenden Erklärungen werden dann natürlich manches hier Erläuterte duplizieren, vor allem die mathematischen Hintergründe betreffend; der Rest ist mehr oder weniger selbsterklärend.)

Interaktive Graphik

Diese über die Gewichtung mit Bernsteinpolynomen (also im Grunde mit binomial verteilten Wahrscheinlichkeiten) generierten Splines können nun auf dieser Seite interaktiv studiert werden. Die Punkte sind per Maus verschiebbar; man kann weitere Stützpunkte durch Doppelklick erzeugen (und so nach Belieben auch wieder entfernen) sowie auch alles per Maus verschieben und auch zoomen (Mausrad). Die Anzahl und damit der Grad der Polynome läßt sich auch mit dem Schiebregler unterhalb der Graphik einstellen.

Zeigt man mit der Maus auf die Kurve, werden die zugehörigen jeweiligen Gewichte durch Größe der Stützpunkte dargestellt und wahlweise zusätzlich durch entsprechend dicke Verbindungslinien. In der Zusatzgraphik (rechts) werden die Graphen der jeweils n+1 Bernsteinpolynome dargestellt. Dort folgt das t ebenfalls der Maus. (Zuätzlich gibt es für den t-Wert noch einen Schiebregler.) Man sieht hier schön, daß der Einfluß jedes Punktes in seinem jeweiligen Bereich am stärksten ist, denn die Ordinate (Höhe) gibt den Wert des zugehörige Bernsteinpolynoms an, also sein Gewicht. (Das ist kein Wunder, denn die zugehörige Binomalverteilung hat ja jeweils den Erwartungswert bei n·p, und so hat der i. Punkt folglich das größte Gewicht bei t= i
n.)

Die Zuordnung der Graphen zu den Polynomen läßt sich anhand der Farben gut erkennen. Für jedes t, das aus dem markierten Kurvenpunkt oder beim Zeigen auf diese Graphik bestimmt wird, werden die zugehörigen Werte der Polynome angezeigt (und zur Kontrolle deren Summe berechnet). Die n+1 Polynome werden jeweils unterhalb der Graphik angezeigt.

Polygonzug durch die Stützpunkte
Gewichte (Anziehungen) mit variablen Punktgrößen, mit Linienverbindungen darstellen

3 Punkte, Polynom 2. Grades.

Bernsteinpolynome (s.u.l.):

Bemerkung

Betrachtet man die Polynome, so sieht man schnell, daß (und warum) generell nur die ersten beiden ein lineares Glied haben, dessen Koeffizienten zudem im Betrag gleich sind, nämlich n. Bei BP₀ ist es immer -n und bei BP₁ immer +n. Das hat zur Folge, daß lediglich in den Ableitungen dieser ersten beiden Polynome genau dieser Summand konstant ist. Für t=0 verschwinden dort nun alle übrigen Summanden, da sie ja alle den Faktor t in erster oder höherer Potenz enthalten. Für die Ableitung an der Stelle 0 gilt also stets x'_S(0) = n·x₁ − n·x₀ und analog y'_S(0) = n·y₁ − n·y₀. Daraus wird leicht ersichtlich, daß der Spline zu Beginn in Richtung des 1. Stützpunktes (P₁) läuft. Die Gerade durch P₀ und P₁ ist also eine Tangente an den Spline in P₀. Symmetrisch dazu verhält es sich am Ende, wo die Gerade durch P_n und P_n-1 eine Tangente an den Spline in seinem Endpunkt P_n ist.