Cubic Hermite spline - Cubic Hermite spline

v numerická analýza, a kubický Hermitův spline nebo kubický Hermitův interpolátor je spline kde každý kus je třetího stupně polynomiální uvedeno v Hermitská forma, tedy svými hodnotami a první deriváty v koncových bodech odpovídající doména interval.^[1]

Kubické Hermitové splajny se obvykle používají pro interpolace číselných dat zadaných při zadaných hodnotách argumentů ${ displaystyle x_ {1}, x_ {2}, ldots, x_ {n}}$ , získat a spojitá funkce. Data by měla vždy obsahovat požadovanou hodnotu funkce a derivaci ${ displaystyle x_ {k}}$ . (Pokud jsou k dispozici pouze hodnoty, musí se z nich odvodit derivace.) Na každý interval se použije Hermitův vzorec ${ displaystyle (x_ {k}, x_ {k + 1})}$ odděleně. Výsledný spline bude spojitý a bude mít spojitou první derivaci.

Krychlové polynomické splajny mohou být specifikovány jinými způsoby, Bézierův krychlový je nejběžnější. Tyto dvě metody však poskytují stejnou sadu splajnů a data lze snadno převádět mezi formami Bézier a Hermite; jména se často používají, jako by byla synonyma.

Krychlové polynomiální splajny jsou široce používány v počítačová grafika a geometrické modelování získat křivky nebo pohyb trajektorie které procházejí určenými body letadlo nebo trojrozměrný prostor. V těchto aplikacích je každá souřadnice roviny nebo prostoru samostatně interpolována kubickou spline funkcí samostatného parametrut. Krychlové polynomické splajny se také hojně používají v aplikacích strukturní analýzy, jako je Teorie paprsku Euler – Bernoulli.

Kubické splajny lze rozšířit na funkce dvou nebo více parametrů několika způsoby. Bikubické splajny (Bikubická interpolace ) se často používají k interpolaci dat na pravidelné obdélníkové mřížce, například pixel hodnoty v a digitální obraz nebo nadmořská výška údaje o terénu. Bikubické povrchové záplaty, definované třemi bikubickými spline, jsou základním nástrojem v počítačové grafice.

Kubické splajny se často nazývají csplines, zejména v počítačové grafice. Poustevnické splajny jsou pojmenovány po Charles Hermite.

Interpolace v jednom intervalu

Jednotkový interval (0, 1)

V jednotkovém intervalu ${ displaystyle (0,1)}$ , vzhledem k výchozímu bodu ${ displaystyle { boldsymbol {p}} _ {0}}$ na ${ displaystyle t = 0}$ a konečný bod ${ displaystyle { boldsymbol {p}} _ {1}}$ na ${ displaystyle t = 1}$ s počáteční tečnou ${ displaystyle { boldsymbol {m}} _ {0}}$ na ${ displaystyle t = 0}$ a končící tečnu ${ displaystyle { boldsymbol {m}} _ {1}}$ na ${ displaystyle t = 1}$ , polynom lze definovat pomocí

{ displaystyle { boldsymbol {p}} (t) = (2t ^ {3} -3t ^ {2} +1) { boldsymbol {p}} _ {0} + (t ^ {3} -2t ^ {2} + t) { boldsymbol {m}} _ {0} + (- 2t ^ {3} + 3t ^ {2}) { boldsymbol {p}} _ {1} + (t ^ {3} -t ^ {2}) { boldsymbol {m}} _ {1}}

Čtyři základní funkce Hermita. Interpolant v každém subintervalu je lineární kombinací těchto čtyř funkcí.

kde t ∈ [0, 1].

Interpolace v libovolném intervalu

Interpolace ${ displaystyle x}$ v libovolném intervalu ${ displaystyle (x_ {k}, x_ {k + 1})}$ se provádí jeho mapováním na ${ displaystyle [0,1]}$ přes afinní (stupeň 1) změna proměnné. Vzorec je

{ displaystyle { boldsymbol {p}} (x) = h_ {00} (t) { boldsymbol {p}} _ {k} + h_ {10} (t) (x_ {k + 1} -x_ { k}) { boldsymbol {m}} _ {k} + h_ {01} (t) { boldsymbol {p}} _ {k + 1} + h_ {11} (t) (x_ {k + 1} -x_ {k}) { boldsymbol {m}} _ {k + 1}.}

s ${ displaystyle t = (x-x_ {k}) / (x_ {k + 1} -x_ {k})}$ a ${ displaystyle h}$ odkazuje na základní funkce definované níže. Všimněte si, že hodnoty tečny byly změněny o ${ displaystyle x_ {k + 1} -x_ {k}}$ ve srovnání s rovnicí na jednotkovém intervalu.

Jedinečnost

Výše uvedené vzorce poskytují jedinečnou polynomickou cestu třetího stupně mezi dvěma body s danými tečnami.

Důkaz. Nechat ${ displaystyle P, Q}$ být dva polynomy třetího stupně splňující dané okrajové podmínky. Definovat ${ displaystyle R = Q-P,}$ pak:

{ displaystyle R (0) = Q (0) -P (0) = 0,}

{ displaystyle R (1) = Q (1) -P (1) = 0.}

Protože oba ${ displaystyle Q}$ a ${ displaystyle P}$ jsou polynomy třetího stupně, ${ displaystyle R}$ je nanejvýš polynom třetího stupně. Tak ${ displaystyle R}$ musí mít formu:

{ displaystyle R (x) = sekera (x-1) (x-r),}

výpočet derivátu dává:

{ displaystyle R '(x) = sekera (x-1) + sekera (x-r) + a (x-1) (x-r).}

Dále víme, že:

{ displaystyle R '(0) = Q' (0) -P '(0) = 0}

{ displaystyle R '(0) = 0 = ar}

(1)

{ displaystyle R '(1) = Q' (1) -P '(1) = 0}

{ displaystyle R '(1) = 0 = a (1-r)}

(2)

Uvedení (1) a (2) společně to odvodíme ${ displaystyle a = 0}$ a proto ${ displaystyle R = 0,}$ tím pádem ${ displaystyle P = Q.}$

Zastoupení

Interpolační polynom můžeme napsat jako

{ displaystyle { boldsymbol {p}} (t) = h_ {00} (t) { boldsymbol {p}} _ {0} + h_ {10} (t) { boldsymbol {m}} _ {0 } + h_ {01} (t) { boldsymbol {p}} _ {1} + h_ {11} (t) { boldsymbol {m}} _ {1}}

kde ${ displaystyle h_ {00}}$ , ${ displaystyle h_ {10}}$ , ${ displaystyle h_ {01}}$ , ${ displaystyle h_ {11}}$ jsou Hermitovy základní funkce. Ty lze psát různými způsoby, přičemž každý způsob odhaluje různé vlastnosti.

	rozšířený	faktorizovaný	Bernstein
${ displaystyle h_ {00} (t)}$	${ displaystyle 2t ^ {3} -3t ^ {2} +1}$	${ displaystyle (1 + 2t) (1-t) ^ {2}}$	${ displaystyle B_ {0} (t) + B_ {1} (t)}$
${ displaystyle h_ {10} (t)}$	${ displaystyle t ^ {3} -2t ^ {2} + t}$	${ displaystyle t (1-t) ^ {2}}$	${ displaystyle { frac {1} {3}} cdot B_ {1} (t)}$
${ displaystyle h_ {01} (t)}$	${ displaystyle -2t ^ {3} + 3t ^ {2}}$	${ displaystyle t ^ {2} (3-2t)}$	${ displaystyle B_ {3} (t) + B_ {2} (t)}$
${ displaystyle h_ {11} (t)}$	${ displaystyle t ^ {3} -t ^ {2}}$	${ displaystyle t ^ {2} (t-1)}$	${ displaystyle - { frac {1} {3}} cdot B_ {2} (t)}$

Sloupec „rozbalený“ zobrazuje reprezentaci použitou ve výše uvedené definici. Sloupec „faktorizovaný“ ukazuje okamžitě toto ${ displaystyle h_ {10}}$ a ${ displaystyle h_ {11}}$ jsou na hranicích nulové. To můžete dále uzavřít ${ displaystyle h_ {01}}$ a ${ displaystyle h_ {11}}$ mít nula multiplicity 2 v 0 a ${ displaystyle h_ {00}}$ a ${ displaystyle h_ {10}}$ mají takovou nulu na 1, takže mají na těchto hranicích sklon 0. Sloupec „Bernstein“ ukazuje rozklad hermitských základních funkcí na Bernsteinovy polynomy objednávky 3:

{ displaystyle B_ {k} (t) = {3 zvolit k} cdot t ^ {k} cdot (1-t) ^ {3-k}}

Pomocí tohoto spojení můžete vyjádřit kubickou Hermitovu interpolaci z hlediska kubických Bézierovy křivky s ohledem na čtyři hodnoty ${ displaystyle { boldsymbol {p}} _ {0}, { boldsymbol {p}} _ {0} + { frac {{ boldsymbol {m}} _ {0}} {3}}, { boldsymbol {p}} _ {1} - { frac {{ boldsymbol {m}} _ {1}} {3}}, { boldsymbol {p}} _ {1}}$ a proveďte interpolaci Hermitů pomocí de Casteljauův algoritmus Ukazuje, že v kubické Bézierově záplatě dva kontrolní body ve středu určují tečny interpolační křivky v příslušných vnějších bodech.

Interpolace datové sady

Soubor dat, ${ displaystyle (x_ {k}, { boldsymbol {p}} _ {k})}$ pro ${ displaystyle k = 1, ldots, n}$ , lze interpolovat použitím výše uvedeného postupu na každý interval, kde jsou tečny zvoleny rozumným způsobem, což znamená, že tečny pro intervaly sdílející koncové body jsou stejné. Interpolovaná křivka pak sestává z po částech kubických Hermitových splajnů a je globálně kontinuálně diferencovatelná ${ displaystyle (x_ {1}, x_ {n})}$ .

Výběr tečen není jedinečný a je k dispozici několik možností.

Konečný rozdíl

Příklad s tečnami konečných rozdílů

Nejjednodušší volbou je tříbodový rozdíl, který nevyžaduje konstantní délky intervalů,

{ displaystyle { boldsymbol {m}} _ {k} = { frac {1} {2}} vlevo ({ frac {{ boldsymbol {p}} _ {k + 1} - { boldsymbol { p}} _ {k}} {x_ {k + 1} -x_ {k}}} + { frac {{ boldsymbol {p}} _ {k} - { boldsymbol {p}} _ {k- 1}} {x_ {k} -x_ {k-1}}} vpravo)}

pro vnitřní body ${ displaystyle k = 2, ldots, n-1}$ a jednostranný rozdíl v koncových bodech sady dat.

Kardinální spline

Kardinální spline příklad ve 2D. Čára představuje křivku a čtverce představují kontrolní body

{ displaystyle { boldsymbol {p}} _ {k}}

. Všimněte si, že křivka nedosahuje prvního a posledního bodu; tyto body však ovlivňují tvar křivky. Použitý parametr napětí je 0,1

A kardinální spline, někdy nazývané a kanonický spline,^[2] je získáno^[3] -li

{ displaystyle { boldsymbol {m}} _ {k} = (1-c) { frac {{ boldsymbol {p}} _ {k + 1} - { boldsymbol {p}} _ {k-1 }} {x_ {k + 1} -x_ {k-1}}}}

se používá k výpočtu tečen. Parametr $C$ je napětí parametr, který musí být v intervalu $[0,1]$ . V určitém smyslu to lze interpretovat jako „délku“ tečny. Výběr $C =1$ získá všechny nulové tečny a výběr $C =0$ dává spline Catmull – Rom.

Catmull – Rom spline

Geometrická interpretace kubické interpolace černého bodu s rovnoměrně rozmístěnými úsečkami.^[4]

Pro tečny, které byly vybrány

{ displaystyle { boldsymbol {m}} _ {k} = { frac {{ boldsymbol {p}} _ {k + 1} - { boldsymbol {p}} _ {k-1}} {x_ { k + 1} -x_ {k-1}}}}

A Catmull – Rom spline je získán, což je speciální případ kardinálního spline. To předpokládá jednotné rozestupy parametrů.

Křivka je pojmenována po Edwin Catmull a Raphael Rom. Hlavní výhodou této techniky je, že body podél původní sady bodů také tvoří kontrolní body křivky spline.^[5] Na každém konci křivky jsou vyžadovány dva další body. Výchozí implementace^{[který? ]} algoritmu Catmull – Rom může vytvářet smyčky a vlastní křižovatky. Chordal a dostředivá Catmull – Rom implementace ^[6] tento problém vyřešit, ale použijte mírně odlišný výpočet.^[7] v počítačová grafika „Křivky Catmull – Rom se často používají k hladkému interpolovanému pohybu mezi nimi klíčové rámečky. Například většina animací cest kamery generovaných z diskrétních klíčových snímků je zpracována pomocí spline Catmull – Rom. Jsou oblíbené hlavně proto, že je lze relativně snadno vypočítat, což zaručuje, že každá pozice klíčového rámečku bude přesně zasažena, a také zaručuje, že tečny generované křivky jsou spojité na více segmentech.

Kochanek – Bartels spline

Kochanek – Bartelsova spline představuje další zobecnění toho, jak zvolit tečny dané datovými body ${ displaystyle { boldsymbol {p}} _ {k-1}}$ , ${ displaystyle { boldsymbol {p}} _ {k}}$ a ${ displaystyle { boldsymbol {p}} _ {k + 1}}$ , se třemi možnými parametry, napětím, předpětím a parametrem spojitosti.

Monotónní kubická interpolace

Pokud se používá kubický Hermitský spline některého z výše uvedených typů interpolace a monotóní datová sada, interpolovaná funkce nemusí být nutně monotónní, ale monotónnost může být zachována úpravou tečen.

Interpolace v jednotkovém intervalu se shodnými deriváty v koncových bodech

Vzhledem k jediné souřadnici bodů ${ displaystyle { boldsymbol {p}} _ {n-1}, { boldsymbol {p}} _ {n}, { boldsymbol {p}} _ {n + 1}}$ a ${ displaystyle { boldsymbol {p}} _ {n + 2}}$ jako hodnoty, které funkce, F(X), bere na celočíselné souřadnice X=n−1, n, n+1 a n+2,

{ Displaystyle p_ {n} = f (n) quad forall n in mathbb {Z}}

Pokud jsou navíc tečny v koncových bodech definovány jako centrované rozdíly sousedních bodů,

{ displaystyle m_ {n} = { frac {f (n + 1) -f (n-1)} {2}} = { frac {p_ {n + 1} -p_ {n-1}} { 2}} quad forall n in mathbb {Z}}

Vyhodnotit interpolované F(X) opravdu X, první samostatný X do celočíselné části, na zlomková část, u

{ displaystyle x = n + u}

{ displaystyle n = lfloor x rfloor = operatorname {floor} (x)}

{ displaystyle u = x-n = x- lpodlaha x rpodlaha}

{ displaystyle 0 leq u <1}

Pak je spline Catmull – Rom ^[8]

{ displaystyle { begin {aligned} f (x) = f (n + u) & = mathrm {CINT} _ {u} left (p_ {n-1}, p_ {n}, p_ {n + 1}, p_ {n + 2} right) [8pt] & = { begin {bmatrix} 1 & u & u ^ {2} & u ^ {3} end {bmatrix}} cdot { begin {bmatrix } 0 & 1 & 0 & 0 - { tfrac {1} {2}} & 0 & { tfrac {1} {2}} & 0 1 & - { tfrac {5} {2}} & 2 & - { tfrac {1} { 2}} - { tfrac {1} {2}} & { tfrac {3} {2}} & - { tfrac {3} {2}} & { tfrac {1} {2}} end {bmatrix}} cdot { begin {bmatrix} p_ {n-1} p_ {n} p_ {n + 1} p_ {n + 2} end {bmatrix }} & = { frac {1} {2}} { begin {bmatrix} -u ^ {3} + 2u ^ {2} -u 3u ^ {3} -5u ^ {2 } +2 - 3u ^ {3} + 4u ^ {2} + u u ^ {3} -u ^ {2} end {bmatrix}} ^ { mathrm {T}} cdot { začít {bmatrix} p_ {n-1} p_ {n} p_ {n + 1} p_ {n + 2} end {bmatrix}} & = { frac {1} {2}} { begin {bmatrix} u ((2-u) u-1) u ^ {2} (3u-5) +2 u ((4-3u) u + 1) u ^ {2} (u-1) end {bmatrix}} ^ { mathrm {T}} cdot { begin {bmatrix} p_ {n-1} p_ {n} p_ {n + 1} p_ {n + 2} end {bmatrix}} & = { tfrac {1} {2}} { bigg (} { big (} u ^ {2} (2- u) -u { big)} p_ {n-1} + { big (} u ^ {2} (3u-5) +2 { big)} p_ {n} + { big ( } u ^ {2} (4-3u) + u { big)} p_ {n + 1} + u ^ {2} (u-1) p_ {n + 2} { bigg)} & = { tfrac {1} {2}} { bi gg (} (- u ^ {3} + 2u ^ {2} -u) p_ {n-1} + (3u ^ {3} -5u ^ {2} +2) p_ {n} + ( -3u ^ {3} + 4u ^ {2} + u) p_ {n + 1} + (u ^ {3} -u ^ {2}) p_ {n + 2} { bigg)} & = { tfrac {1} {2}} { bigg (} (- p_ {n-1} + 3p_ {n} -3p_ {n + 1} + p_ {n + 2}) u ^ { 3} + (2p_ {n-1} -5p_ {n} + 4p_ {n + 1} -p_ {n + 2}) u ^ {2} + (-p_ {n-1} + p_ {n + 1}) u + 2p_ {n} { bigg)} & = { tfrac {1} {2}} { bigg (} { Big (} (- p_ {n -1} + 3p_ {n} -3p_ {n + 1} + p_ {n + 2}) u + (2p_ {n-1} -5p_ {n} + 4p_ {n + 1} -p_ {n +2}) { Big)} u + (-p_ {n-1} + p_ {n + 1}) { bigg)} u + p_ {n} end {zarovnáno}} }

${ displaystyle lfloor x rfloor}$ označuje funkce podlahy který vrací největší celé číslo ne větší než X a ${ displaystyle mathrm {T}}$ označuje maticová transpozice. Spodní rovnost znázorňuje použití Hornerova metoda.

Tento text je relevantní pro tricubická interpolace, kde jedna optimalizace vyžaduje, abyste vypočítali CINT_u šestnáctkrát se stejným u a jiné p.

Viz také

Bikubická interpolace, zobecnění do dvou dimenzí
Tricubická interpolace, zobecnění do tří dimenzí
Hermitova interpolace
Vícerozměrná interpolace
Spline interpolace
Diskrétní spline interpolace

Reference

^ Erwin Kreyszig (2005). Pokročilá inženýrská matematika (9 ed.). Wiley. str. 816. ISBN 9780471488859.
^ Petzold, Charles (2009). „Kanonické splajny ve WPF a Silverlight“.
^ "Kardinální splajny". Microsoft Developer Network. Citováno 2018-05-27.
^ Kubická interpolace není jedinečná: tento model využívající Catmull-Rom spline a Lagrangeovy polynomy prochází všemi čtyřmi body. Poznámka: V levé třetině je žlutá vodorovná vzdálenost záporná, protože černý bod je nalevo od žlutého bodu; v pravé třetině je zelená vodorovná vzdálenost záporná, protože černý bod je vpravo od zeleného bodu.
^ Catmull, Edwin; Rom, Raphaeli (1974), „Třída lokálních interpolačních splajnů“, Barnhill, R. E .; Riesenfeld, R. F. (eds.), Počítačem podporovaný geometrický design, New York: Academic Press, s. 317–326
^ N. Dyn, M. S. Floater a K. Hormann. Čtyřbodové dělení křivek na základě iterovaných chordálních a dostředivých parametrizací. Computer Aided Geometric Design, 26 (3): 279 {286, 2009
^ P. J. Barry a R. N. Goldman. Algoritmus rekurzivního vyhodnocení pro třídu spline Catmull-Rom. Počítačová grafika SIGGRAPH, 22 (4): 199 {204, 1988.
^ Dvě hierarchie spline interpolací. Praktické algoritmy pro vícerozměrné splajny vyššího řádu

externí odkazy

[kreyszig-1] Erwin Kreyszig (2005). Pokročilá inženýrská matematika (9 ed.). Wiley. str. 816. ISBN 9780471488859.

[2] Petzold, Charles (2009). „Kanonické splajny ve WPF a Silverlight“.

[3] "Kardinální splajny". Microsoft Developer Network. Citováno 2018-05-27.

[4] Kubická interpolace není jedinečná: tento model využívající Catmull-Rom spline a Lagrangeovy polynomy prochází všemi čtyřmi body. Poznámka: V levé třetině je žlutá vodorovná vzdálenost záporná, protože černý bod je nalevo od žlutého bodu; v pravé třetině je zelená vodorovná vzdálenost záporná, protože černý bod je vpravo od zeleného bodu.

[5] Catmull, Edwin; Rom, Raphaeli (1974), „Třída lokálních interpolačních splajnů“, Barnhill, R. E .; Riesenfeld, R. F. (eds.), Počítačem podporovaný geometrický design, New York: Academic Press, s. 317–326

[6] N. Dyn, M. S. Floater a K. Hormann. Čtyřbodové dělení křivek na základě iterovaných chordálních a dostředivých parametrizací. Computer Aided Geometric Design, 26 (3): 279 {286, 2009

[7] P. J. Barry a R. N. Goldman. Algoritmus rekurzivního vyhodnocení pro třídu spline Catmull-Rom. Počítačová grafika SIGGRAPH, 22 (4): 199 {204, 1988.

[8] Dvě hierarchie spline interpolací. Praktické algoritmy pro vícerozměrné splajny vyššího řádu

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]