B-spline

En el camp matemàtic d'anàlisi numèrica, un B-spline és un spline que té suport mínim respecte a un grau, suavitat, i partició del domini donats. Els B-splines varen ser investigats a segle xix per Nikolai Lobachevsky. Un teorema fonamental estableix que cada spline d'un grau, suavitat, i partició del camp donats, es pot representar de manera única com a combinació lineal de B-splines d'aquell mateix grau i suavitat, i sobre aquella mateixa partició.^[1]

El terme "B-spline" va ser encunyat per Isaac Schoenberg i és una abreviatura de base spline.^[2][3] els B-splines poden ser avaluats d'una manera numèricament estable amb l'algorisme de De Boor. S'han creat variants simplificades, potencialment més ràpides de l'algorisme de De Boor però pateixen d'estabilitat comparativament més baixa.^[4][5]

En els camps d'informàtica de gràfics i d'infografia, el terme B-spline freqüentment es refereix a una corba spline parametritzada per funcions spline que s'expressen com combinacions lineals de B-splines (en el sentit matemàtic de damunt). Un B-spline és simplement una generalització d'una [corba de Bézier], i pot evitar el fenomen de Runge sense augmentar el grau del B-spline.

Definició

Donats m valors reals t_i, anomenats nusos, amb

${\displaystyle t_{0}\leq t_{1}\leq \cdots \leq t_{m-1}}$

un B-spline de grau n és una corba paramètrica

${\displaystyle \mathbf {S} :[t_{n},t_{m-n-1}]\to \mathbb {R} ^{d}}$

composta per una combinació lineal de B-splines base b_i,n de grau n

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

Els punts ${\displaystyle \mathbf {P} _{i}\in \mathbb {R} ^{d}}$ s'anomenen punts de control o punts de Boor. Hi ha m−n-1 punts de control, i formen un embolcall convex.

Els m-n-1 B-splines base de grau n poden ser definits, per n =0,1...,m-2, utilitzant la fórmula de recurrència de De Boor Cox

${\displaystyle b_{j,0}(t):=\left\{{\begin{matrix}1&\mathrm {if} \quad t_{j}\leq t<t_{j+1}\\0&\mathrm {otherwise} \end{matrix}}\right.,\qquad j=0,\ldots ,m{-}2}$

${\displaystyle 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),\qquad j=0,\ldots ,m{-}n{-}2.}$

Fixeu-vos que j+n+1 no pot excedir m-1, que limita tant j com n.

Quan els nusos són equidistants el B-splines es diu que és uniforme, altrament no-uniforme. Si dos nusos t_j són idèntics, totes les formes 0/0 indeterminades que resulten es consideren que són 0.

Fixeu-vos que quan se suma un conjunt de B-splines adjacents de base de grau n s'obté, d'aquesta recurrència

${\displaystyle \sum _{j=j'}^{j''}b_{j,n}(t)={\frac {t-t_{j'}}{t_{j'+n}-t_{j'}}}b_{j',n-1}(t)\quad +\sum _{j=j'{+}1}^{j''}b_{j,n{-}1}(t)\quad +\;{\frac {t_{j''+n+1}-t}{t_{j''+n+1}-t_{j''+1}}}b_{j''+1,n-1}(t)}$

per a qualsevol suma amb ${\displaystyle 0\leq j'<j''\leq m{-}n{-}2.}$

Quan ${\displaystyle j''\geq j'+n-1}$ aquí, llavors aquesta suma és, per aquesta recurrència, idènticament igual a 1 dins del subrang limitad${\displaystyle t_{j'{+}nlimitat}\leq t\leq t_{j''{+}1}}$ (ja que aquest interval exclou els suports dels dos B-splines base en els termes separats als extrems d'aquesta suma).

B-spline Uniforme

Quan el B-spline és uniforme, la base de B-splines per a un grau donat n són còpies desplaçades l'un de l'altre. Una definició no recursiva alternativa per la base m−n-1 dels B-splines és

${\displaystyle b_{j,n}(t)=b_{n}(t-t_{j}),\qquad \;j=0,\ldots ,m-n-2}$

amb

${\displaystyle b_{n}(t):={\frac {n+1}{n}}\sum _{i=0}^{n+1}\omega _{i,n}(t-t_{i})_{+}^{n}\,\;}$

i

${\displaystyle \omega _{i,n}:=\prod _{j=0,j\neq i}^{n+1}{\frac {1}{t_{j}-t_{i}}}\,\;}$

on

${\displaystyle (t-t_{i})_{+}^{n}:=\left\{{\begin{matrix}(t-t_{i})^{n}&{\mbox{if}}\ t\geq t_{i}\\0&{\mbox{if}}\ t<t_{i}\end{matrix}}\right.}$

és la funció potencial truncada.

B-spline Cardinal

Es defineixi B₀ com la funció característica de ${\displaystyle [-{\tfrac {1}{2}},{\tfrac {1}{2}}]}$, i B_k recursivament com el producte de convolució

${\displaystyle B_{k}:=B_{k-1}*B_{0},~k=1,2,\dots }$

llavors B_k s'anomenen B-splines cardinals (centrats). Aquesta definició es remunta a Isaac Schoenberg.

B_k té suport compacte ${\displaystyle [-{\tfrac {k+1}{2}},{\tfrac {k+1}{2}}]}$ i és una funció parella. Com ${\displaystyle k\rightarrow \infty }$ els B-splines cardinals normalitzats tendeixen a la funció gaussiana.^[6]

Notes

Quan el nombre de punts de control de De Boor és un més que el grau i ${\displaystyle t_{0}=\ldots =t_{n}=0}$ i ${\displaystyle t_{n+1}=\ldots =t_{2n}=1}$ (així ${\displaystyle t\in [0,1]}$), el B-Spline degenera en una corba de Bézier. En particular, la funció B-Spline base ${\displaystyle b_{i,n}(t)}$ coincideix amb el polinomi de Bernstein de grau de n-th.^[7] La forma de les funcions base està determinada per la posició dels nodes. Una dilatació o una Translació dels vector de nodes no canvia les funcions base.

L'spline és contingut al embolcall convex dels seus punts de control.

Una base de B-splines de grau n

${\displaystyle b_{i,n}(t)\,\;}$

és diferent de zero només a l'interval [t _i , t _i+n+1 ] és a dir

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

En altres paraules si es manipula un punt de control que només es canvia el comportament local de la corba i no el comportament global com en les corbes de Bézier.

Exemples

B-spline Constant

El B-spline constant és l'spline més simple. Es defineix en només una amplitud de node i no és ni tan sols continu als nodes. És la funció característica pels diferents intervals entre nodes.

${\displaystyle b_{j,0}(t)=1_{[t_{j},t_{j+1}]}=\left\{{\begin{matrix}1&\mathrm {si} \quad t_{j}\leq t<t_{j+1}\\0&\mathrm {altrament} \end{matrix}}\right.}$

B-spline Lineal

El B-spline lineal està definit en dos intervals entre nodes consecutius i és continu als nodes, però no diferenciable.

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

B-spline quadràtic uniforme

Els B-splines quadràtics amb vector de nodes uniforme és un tipus de B-splines que es fa servir sovint. La funció base es pot precalcular fàcilment, i en aquest cas, és igual per a cada segment.

${\displaystyle b_{j,2}(t)={\begin{cases}{\frac {1}{2}}(t-t_{j})^{2}&t_{j}\leq t\leq t_{j+1}\\-(t-t_{j+1})^{2}+(t-t_{j+1})+{\frac {1}{2}}&t_{j+1}\leq t\leq t_{j+2}\\{\frac {1}{2}}(1-(t-t_{j+2}))^{2}&t_{j+2}\leq t\leq t_{j+3}\\0&{\mbox{altrament}}\end{cases}}}$

Posada en forma de matriu, és:^[8]

${\displaystyle \mathbf {S} _{i}(t)={\begin{bmatrix}t^{2}&t&1\end{bmatrix}}{\frac {1}{2}}{\begin{bmatrix}1&-2&1\\-2&2&0\\1&1&0\end{bmatrix}}{\begin{bmatrix}\mathbf {p} _{i-1}\\\mathbf {p} _{i}\\\mathbf {p} _{i+1}\end{bmatrix}}}$ per ${\displaystyle t\in [0,1],i=1,2\ldots m-2}$

B-Spline Cúbic

La fórmula del B-spline per a un segment únic es pot escriure com:

${\displaystyle \mathbf {S} _{i}(t)=\sum _{k=0}^{3}\mathbf {P} _{i-3+k}b_{i-3+k,3}(t){\mbox{; }}\ t\in [0,1]}$

on S_i és el segment i-èsim del B-spline, P és el conjunt de punts de control, i i k són els índexs dels punts de control locals. Un conjunt de punts de control serien ${\displaystyle P_{i}^{w}=(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})}$ on el ${\displaystyle w_{i}}$ és el pes, que estira la corba cap al punt de control ${\displaystyle P_{i}}$ quan augmenta o aparta la corba lluny del punt quan disminueix.

Un conjunt complet de segments de m-2 corbes (${\displaystyle S_{3},S_{4}...,S_{m}}$) definit per m +1 punts de control (${\displaystyle P_{0},P_{1}...,P_{m},m\geq 3}$), com un B-spline en t estaria definit per:

${\displaystyle \mathbf {S} (t)=\sum _{i=0}^{m-1}\mathbf {P} _{i}b_{i,3}(t)}$

on i és el número de punt de control i t és un paràmetre global que dona els valors dels nodes. Aquesta formulació expressa una corba B-spline com una combinació lineal de B-spline base, d'aquí el nom.

Hi ha dos tipus de B-splines - uniformes i no-uniformes. Un B-spline no uniforme és una corba on els intervals entre punts successius de control no són necessàriament iguals (les separacions entre els nodes del vector de nodes no són iguals). Una forma freqüent és quan l'amplada dels intervals es redueix successivament cap a zero, interpolant punts de control.

B-splines cúbics uniformes

Els B-splines cúbics amb un vector de nodes uniforme és la forma més habitualment emprada de B-splines. La funció base es pot precalcular fàcilment, i en aquest cas és igual per a cada segment. Posada en forma matricial, és:

${\displaystyle \mathbf {S} _{i}(t)={\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\frac {1}{6}}{\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&0&3&0\\1&4&1&0\end{bmatrix}}{\begin{bmatrix}\mathbf {p} _{i-1}\\\mathbf {p} _{i}\\\mathbf {p} _{i+1}\\\mathbf {p} _{i+2}\end{bmatrix}}}$

per a ${\displaystyle t\in [0,1].}$..

Vegeu també

• Spline
• B-spline Racional No Uniforme (NURBS)

Referències

Enllaços externs

• B-spline a MathWorld
• Mòdul de B-Splines per John H. Mathews
• B-splines de tercer ordre en un reixat no uniforme per Johannes Ruf Arxivat 2011-10-04 a Wayback Machine.
• Codi FORTRAN per interpolació emprant B-splines Arxivat 2011-06-14 a Wayback Machine.
• B-spline bivariant a numpy
• B-splines interactiu amb JSXGraph