Polyharmonické splajny se používají pro aproximace funkce a data interpolace. Jsou velmi užitečné pro interpolaci a přizpůsobení rozptýlených dat v mnoha dimenzích. Zvláštní případy zahrnují tenké dlahy[1][2] a přírodní kubické splajny v jedné dimenzi.[3]
Polyharmonický spline je lineární kombinace polyharmonie radiální základní funkce (RBF) označené plus polynomiální výraz:
(1)
kde
Polyharmonické základní funkce
( označuje transpozici matice, význam je sloupcový vektor) je skutečný vektor nezávislé proměnné,
jsou vektory stejné velikosti jako (často nazývané středy), které musí křivka nebo povrch interpolovat,
jsou váhy RBF,
jsou váhy polynomu.
Polynom s koeficienty zlepšuje přesnost lícování pro polyharmonické vyhlazovací splajny a také zlepšuje extrapolaci směrem od středu Viz obrázek níže pro srovnání splajnů s polynomiálním členem a bez polynomiálního členu.
Polyharmonické RBF mají formu:
Další hodnoty exponentu nejsou užitečné (např ), protože řešení problému s interpolací nemusí existovat. Aby se předešlo problémům v (od té doby ), polyharmonické RBF s přirozeným logaritmem lze implementovat jako:
Váhy a jsou určeny tak, aby funkce interpolovala dané body (pro ) a splňuje podmínky ortogonality
Dohromady jsou tato omezení ekvivalentní symetrickému lineárnímu systému rovnic
(2)
kde
Aby tento systém rovnic měl jedinečné řešení, musí být v plné hodnosti. je plná hodnost pro velmi mírné podmínky na vstupních datech. Například ve dvou dimenzích to zajišťují tři centra tvořící nedegenerovaný trojúhelník je plná hodnost a ve třech dimenzích čtyři centra tvořící nedegenerovaný čtyřstěn zajišťují, že B je plná hodnost. Jak je vysvětleno dále, lineární transformace vyplývající z omezení domény lineární transformace do prázdný prostor z je pozitivní určitý. To znamená, že pokud je plná hodnost, soustava rovnic (2) má vždy jedinečné řešení a lze jej vyřešit pomocí Choleský rozklad po vhodné transformaci. Vypočítané váhy umožňují vyhodnotit spline pro libovolné pomocí rovnice (1). Mnoho praktických detailů implementace a používání polyharmonických splajnů je vysvětleno ve Fasshaueru.[4] V Iske[5] polyharmonické splajny jsou považovány za speciální případy jiných multirezolučních metod při modelování rozptýlených dat.
Důvod názvu „polyharmonie“
Polyharmonická rovnice je a parciální diferenciální rovnice formuláře pro jakékoli přirozené číslo , kde je Operátor Laplace. Například biharmonická rovnice je a triharmonická rovnice je . Všechny polyharmonické radiální bazické funkce jsou řešením polyharmonické rovnice (nebo přesněji upravené polyharmonické rovnice s Diracova delta funkce na pravé straně místo 0). Například radiální bázová funkce tenké desky je řešením modifikované 2-dimenzionální biharmonické rovnice.[6] Použití 2D Laplaceova operátoru () k radiální bázové funkci tenké desky ručně nebo pomocí a počítačový algebraický systém ukázat to . Použití operátoru Laplace na (tohle je ) dává 0. Ale 0 není úplně správný. Chcete-li to vidět, vyměňte jej s (kde je nějaké malé číslo se sklonem k 0). Operátor Laplace se přihlásil k výnosy . Pro pravá strana této rovnice se blíží k nekonečnu jako se blíží 0. Pro všechny ostatní , pravá strana se blíží 0 jako blíží se 0. To znamená, že pravá strana je Diracova delta funkce. Ukáže to počítačový algebraický systém
Radiální bázová funkce tenké desky je tedy řešením rovnice .
Použití 3D Laplacian () do biharmonického RBF výnosy a použití 3D operátor na triharmonický RBF výnosy . Pronájem a výpočetní technika opět znamená, že pravá strana PDE pro biharmonické a triharmonické RBF jsou delta funkce Dirac. Od té doby
přesné PDE uspokojené biharmonickými a triharmonickými RBF jsou a .
Polyharmonické vyhlazovací drážky
Polyharmonické splajny se minimalizují
(3)
kde je nějaký box in obsahující sousedství všech center, je nějaká pozitivní konstanta a je vektorem všeho parciální deriváty řádu th. řádu Například ve 2D a a ve 3D . Ve 2D zjednodušení integrálu energie tenké desky funkční.
Chcete-li ukázat, že polyharmonické křivky minimalizují rovnici (3), vhodný výraz musí být transformován na integrál pomocí definice delta funkce Dirac:
kde je multi-index který se pohybuje nad všemi částečnými derivacemi řádu pro Aby bylo možné použít Euler-Lagrangeova rovnice pro jedinou funkci více proměnných a derivátů vyššího řádu veličiny
a
jsou potřeba. Vložení těchto veličin do rovnice E-L to ukazuje
pro všechny funkce hladkého testu které zmizí mimo Slabé řešení rovnice (4) bude stále minimalizovat (3) a zároveň se zbavit funkce delta integrací.[7]
Nechat být polyharmonickým spline, jak je definováno rovnicí (1). Následující výpočty to ukážou splňuje (5). Uplatnění operátor do rovnice (1) výnosy
Jediným možným řešením (6) pro všechny testovací funkce je
(7)
(což znamená interpolaci, pokud ). Kombinace definice v rovnici (1) s rovnicí (7) má za následek téměř stejný lineární systém jako rovnice (2) kromě toho, že matice je nahrazen kde je matice identity. Například pro 3D triharmonické RBF, je nahrazen
Vysvětlení dalších omezení
V (2), spodní polovina soustavy rovnic () je uveden bez vysvětlení. Vysvětlení nejprve vyžaduje odvození zjednodušené formy když je vše
Nejprve to vyžadujte Tím je zajištěno, že všechny deriváty objednávky a vyšší z zmizet v nekonečnu. Například pojďme a a být triharmonickým RBF. Pak (s ohledem na jako mapování z na ). Pro dané centrum
Na řádku pro libovolný bod a jednotkový vektor
Vydělením čitatele i jmenovatele tímto ukázat to množství nezávislé na centru Takže na daném řádku
Nestačí to jen vyžadovat protože v následujícím je to nutné pro zmizet v nekonečnu, kde a jsou multiindexy takové, že Pro triharmonii (kde a jsou váhy a středy ) je vždy součet celkových polynomů stupně 5 a děleno druhou odmocninou polynomu celkového stupně 8. Zvažte chování těchto výrazů na řádku tak jako blíží se nekonečnu. Čitatel je polynom stupně 5 Dělení čitatele a jmenovatele pomocí opouští termíny stupně 4 a 5 v čitateli a funkci pouze ve jmenovateli. Termín stupně 5 děleno je produktem pěti souřadnice a The (a Díky omezením to zmizí všude na trati. Termín stupně 4 děleno je produktem čtyř souřadnice a souřadnice nebo součin čtyř souřadnice a jeden nebo koordinovat. The Díky omezení zmizí první typ výrazu všude na trati. Další omezení způsobí, že druhý typ výrazu zmizí.
Nyní definujte vnitřní produkt dvou funkcí definována jako lineární kombinace polyharmonických RBF s a tak jako
To ukazuje integrace po částech
(8)
Například pojďme a Pak
(9)
Integrace prvního funkčního období částmi, jakmile se získá
od té doby zmizí v nekonečnu. Integrace po částech má opět za následek
Takže integrace po částech dvakrát pro každý termín (9) výnosy
Nyní původ omezení lze vysvětlit. Tady je zobecněním definováno výše, aby případně zahrnovalo monomily až do stupně Jinými slovy,
kde je sloupcový vektor všech stupňů monomials souřadnic Horní polovina (2) je ekvivalentní s Abyste získali vyhlazovací spline, měli byste skalární pole minimalizovat definován
Rovnice
a
(kde označuje řádek z ) jsou ekvivalentní dvěma soustavám lineárních rovnic a Od té doby je invertibilní, první systém je ekvivalentní s Takže první systém naznačuje, že druhý systém je ekvivalentní Stejně jako v předchozím odvození vyhlazovacího spline koeficientu, horní polovina (2) se stává
Toto odvození systému polyharmonických vyhlazovacích spline rovnic nepředpokládalo omezení nezbytná k zajištění toho Ale omezení nutná k zajištění toho, a jsou podmnožinou což platí pro kritický bod z Tak platí pro vytvořený z řešení systému polyharmonické vyhlazovací spline rovnice. Protože integrál je pozitivní pro všechny lineární transformace vyplývající z omezení domény lineární transformace na takhle musí být kladně definitivní. Tato skutečnost umožňuje transformovat systém polyharmonických vyhlazovacích spline rovnic na symetrický pozitivní určitý systém rovnic, který lze řešit dvakrát rychleji pomocí Choleského rozkladu.[6]
Příklady
Následující obrázek ukazuje interpolaci čtyřmi body (označenými „kruhy“) pomocí různých typů polyharmonických splajnů. „Zakřivení“ interpolovaných křivek roste s řádkem spline a extrapolace na levé hranici (x <0) je přiměřená. Obrázek také zahrnuje radiální bázové funkce phi = exp (-r2) který také poskytuje dobrou interpolaci. Nakonec obrázek zahrnuje také nepolyharmonické spline phi = r2 prokázat, že tato radiální bazická funkce není schopna projít předdefinovanými body (lineární rovnice nemá řešení a je řešena ve smyslu nejmenších čtverců).
Interpolace s různými polyharmonickými splajny, které musí projít 4 předdefinovanými body označenými kružnicí (interpolace s phi = r2 není užitečné, protože systém lineárních rovnic interpolační úlohy nemá řešení; je řešen ve smyslu nejmenších čtverců, ale poté neprochází středy)
Následující obrázek ukazuje stejnou interpolaci jako na prvním obrázku, s jedinou výjimkou, že body, které mají být interpolovány, jsou škálovány faktorem 100 (a případ phi = r2 již není součástí dodávky). Protože phi = (měřítko * r)k = (měřítkok) * rk, faktor (stupnicek) lze extrahovat z matice A systému lineárních rovnic, a proto řešení není ovlivněno škálováním. U logaritmické formy spline se to liší, i když změna měřítka nemá velký vliv. Tato analýza se odráží na obrázku, kde interpolace neukazuje velké rozdíly. Všimněte si, pro další radiální základní funkce, jako je phi = exp (-k * r2) s k = 1, interpolace již není rozumná a bylo by nutné upravit k.
Stejná interpolace jako na prvním obrázku, ale body, které se mají interpolovat, se zmenší o 100
Následující obrázek ukazuje stejnou interpolaci jako na prvním obrázku, s jedinou výjimkou, že polynomiální člen funkce není brán v úvahu (a případ phi = r2 již není součástí dodávky). Jak je patrné z obrázku, extrapolace pro x <0 již není pro některé základní funkce tak „přirozená“ jako na prvním obrázku. To naznačuje, že polynomický člen je užitečný, pokud dojde k extrapolaci.
Stejná interpolace jako na prvním obrázku, ale bez polynomiálního členu
Diskuse
Hlavní výhodou polyharmonické spline interpolace je, že obvykle jsou pro rozptýlená data získány velmi dobré výsledky interpolace bez provedení jakéhokoli „vyladění“, takže je možná automatická interpolace. To neplatí pro jiné radiální základní funkce. Například Gaussova funkce je třeba vyladit, takže je vybrán podle podkladové mřížky nezávislých proměnných. Pokud je tato mřížka nejednotná, proveďte správný výběr dosáhnout dobrého výsledku interpolace je obtížné nebo nemožné.
Hlavní nevýhody jsou:
K určení vah musí být vyřešen hustý lineární systém rovnic. Řešení hustého lineárního systému se stane nepraktickým, pokud bude dimenze je velký, protože požadovaná paměť je a počet požadovaných operací je
Vyhodnocování vypočítané polyharmonické spline funkce při datové body vyžadují operace. V mnoha aplikacích (příkladem je zpracování obrazu) je mnohem větší než a pokud jsou obě čísla velká, není to praktické.
Nedávno byly vyvinuty metody k překonání výše uvedených obtíží. Například Beatson et al.[8] představit metodu interpolace polyharmonických splajnů v jednom bodě ve 3 rozměrech v operace místo operace.
^J. Duchon: Splines minimalizující rotační invariantní semi-normy v Sobolevových prostorech. Konstruktivní teorie funkcí několika proměnných, W. Schempp a K. Zeller (eds), Springer, Berlín, str. 85-100