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ó modifica

Donats m valors reals t_i, anomenats nusos, amb

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

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

\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

\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 $\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

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

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

\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 $0\leq j'<j''\leq m{-}n{-}2.$

Quan $j''\geq j'+n-1$ aquí, llavors aquesta suma és, per aquesta recurrència, idènticament igual a 1 dins del subrang limitad $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 modifica

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

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

amb

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

i

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

on

(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 modifica

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

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 $[-{\tfrac {k+1}{2}},{\tfrac {k+1}{2}}]$ i és una funció parella. Com $k\rightarrow \infty$ els B-splines cardinals normalitzats tendeixen a la funció gaussiana.^[6]

Notes modifica

Quan el nombre de punts de control de De Boor és un més que el grau i $t_{0}=\ldots =t_{n}=0$ i $t_{n+1}=\ldots =t_{2n}=1$ (així $t\in [0,1]$ ), el B-Spline degenera en una corba de Bézier. En particular, la funció B-Spline base $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

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

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

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 modifica

B-spline Constant modifica

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.

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 modifica

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

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 modifica

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.

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]

\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

t\in [0,1],i=1,2\ldots m-2

B-Spline Cúbic modifica

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

\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 $P_{i}^{w}=(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})$ on el $w_{i}$ és el pes, que estira la corba cap al punt de control $P_{i}$ quan augmenta o aparta la corba lluny del punt quan disminueix.

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

\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.

Comparació entre un B-spline cúbic uniforme (groc) i un spline cúbic d'Hermite (vermell fosc).

B-splines cúbics uniformes modifica

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:

\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 $t\in [0,1].$ ..

Vegeu també modifica

Spline
B-spline Racional No Uniforme (NURBS)

Referències modifica

↑ Carl de Boor. A Practical Guide to Splines. Springer-Verlag, 1978, p. 113–114.
↑ Carl de Boor. A Practical Guide to Splines. Springer-Verlag, 1978, p. 114–115.
↑ Gary D. Knott (2000), Interpolating cubic splines. Springer. p. 151
↑ Lee, E. T. Y. «A Simplified B-Spline Computation Routine». Computing. Springer-Verlag, 29, 4, desembre 1982, pàg. 365–371. DOI: 10.1007/BF02246763.
↑ . Lee, E. T. Y. «Comments on some B-spline algorithms». Computing. Springer-Verlag, 36, 3, 1986, pàg. 229–238. DOI: 10.1007/BF02240069.
↑ Brinks R: On the convergence of derivatives of B-splines to derivatives of the Gaussian function, Comp. Appl. Math., 27, 1, 2008
↑ Prautzsch et al., Hartmut. Bezier and B-Spline Techniques. Springer-Verlag, 2002, p. 60–66. ISBN 3540437614.
↑ Splitting a uniform B-spline curve

Enllaços externs modifica

[1] Carl de Boor. A Practical Guide to Splines. Springer-Verlag, 1978, p. 113–114.

[2] Carl de Boor. A Practical Guide to Splines. Springer-Verlag, 1978, p. 114–115.

[3] Gary D. Knott (2000), Interpolating cubic splines. Springer. p. 151

[4] Lee, E. T. Y. «A Simplified B-Spline Computation Routine». Computing. Springer-Verlag, 29, 4, desembre 1982, pàg. 365–371. DOI: 10.1007/BF02246763.

[5] . Lee, E. T. Y. «Comments on some B-spline algorithms». Computing. Springer-Verlag, 36, 3, 1986, pàg. 229–238. DOI: 10.1007/BF02240069.

[6] Brinks R: On the convergence of derivatives of B-splines to derivatives of the Gaussian function, Comp. Appl. Math., 27, 1, 2008

[7] Prautzsch et al., Hartmut. Bezier and B-Spline Techniques. Springer-Verlag, 2002, p. 60–66. ISBN 3540437614.

[8] Splitting a uniform B-spline curve

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]