B-spline

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 Jacob 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 de infografia, el terme B-spline freqüentment es refereix a un 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 | modifica el codi]

Donats m valors reals ti, anomenats nusos, amb

t_0 \le t_1 \le \cdots \le 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 bi,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 tj 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\le j' < j''\le m{-}n{-}2.

Quan j''\ge j'+n-1 aquí, llavors aquesta suma és, per aquesta recurrència, idènticament igual a 1 dins del subrang limitadt_{j'{+}n limitat} \le t \le 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 | modifica el codi]

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 \ge t_i \\
0 &\mbox{if}\ t < t_i
\end{matrix}\right.

és la funció potencial truncada.

B-spline Cardinal[modifica | modifica el codi]

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

B_k := B_{k-1} * B_0, ~k =1, 2, \dots

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

Bk 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 | modifica el codi]

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} \le 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 | modifica el codi]

B-spline Constant[modifica | modifica el codi]

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 \le t < t_{j+1} \\
0 & \mathrm{altrament} 
\end{matrix}
\right.

B-spline Lineal[modifica | modifica el codi]

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 \le t < t_{j+1} \\
\frac{t_{j+2} - t}{t_{j+2} - t_{j+1}} & \mathrm{si} \quad t_{j+1} \le t < t_{j+2} \\
0 & \mathrm{altrament} 
\end{matrix}
\right.

B-spline quadràtic uniforme[modifica | modifica el codi]

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\le t \le t_{j+1} \\ -(t-t_{j+1})^2 + (t-t_{j+1}) + \frac{1}{2} & t_{j+1} \le t \le t_{j+2}\\ \frac{1}{2}(1-(t-t_{j+2}))^2 & t_{j+2} \le t \le 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 | modifica el codi]

La formula 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 Si és el segment ièssim del B-spline, P és el conjunt de punts de control, i i k són els índex 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 complert 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 \ge 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 dóna 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 | modifica el codi]

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 | modifica el codi]

Referències[modifica | modifica el codi]

  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, vol. 29, 4, December 1982, pàg. 365–371. DOI: 10.1007/BF02246763.
  5. . Lee, E. T. Y.. «Comments on some B-spline algorithms». Computing. Springer-Verlag, vol. 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


Enllaços externs[modifica | modifica el codi]