Cesko.wiki Vážené inverzní vzdálenosti
Author
Albert FloresVážené inverzní vzdálenosti (IDW) je typ určující metody pro multivariační interpolaci se známou rozptýlenou sadou bodů. Přiřazené hodnoty neznámým bodům jsou vypočítávané s váženým průměrem z hodnot známých bodů.
Pojmenování těchto metod bylo motivováno používáním vážených průměrů inverzních vzdáleností od každého známého bodu ("míra blízkosti") při přiřazování vah.
Definice problému
Očekávaný výsledek je diskrétní přiřazení neznámé funkce u v pozorované oblasti:
u(x): x \rightarrow \mathbb{R}, \quad x \in \mathbf{D} \sub \mathbb{R}^n
kde \mathbf{D} je studovaná oblast.
Sada N známých datových bodů lze popsat jako seznam n-tic:
[(x_1, u_1), (x_2, u_2), ..., (x_N, u_N)]
Funkce má být "hladká" (kontinuální a jednou diferencovatelná), aby byla přesná (u(x_i)=u_i) a aby plnila uživatelovo intuitivní očekávání o jevu, který je předmětem šetření. Kromě toho by funkce měla být použitelná pro počítačové aplikace za přijatelnou cenu (dnes se základní implementace používá u paralelních zdrojů).
Shepardova metoda
Historická zmínka
V Harvardových laboratořích pro počítačovou grafiku a prostorové analýzy, s počátky v roce 1965, rozmanitý výběr vědců se shodli, aby přehodnotili názory, kromě jiného ohledně toho, co dnes nazýváme geografické informační systémy.
Hybná síla laboratoře, Howard Fisher, vytvořil vylepšený mapovací program nazvaný SYMAP, kterým od počátku chtěl Fisher zlepšit interpolaci. On ukazoval svou práci na SYMAPu studentům prvního ročníku Harvardovy univerzity, a mnoho z nich se podílelo na laboratorních výzkumech. +more Jeden ze studentů, Donald Shepard, se rozhodl přepracovat interpolaci V SYMAPu, výsledky zveřejnil ve svém slavném článku z roku 1968.
Shepardův algoritmus byl také podložen teoretickými poznatky Williama Warntze a ostatních kteří pracovali v laboratoři na prostorových analýzách. Prováděl řadu experimentů s exponentem vzdálenosti, došel k závěru blízkému gravitačnímu modelu (exponent -2). +more Shepard neimplementoval jen základní verzi vážené inverzní vzdálenosti, ale doplnil ji o omezení (propustné a absolutní) interpolace.
Další výzkumná střediska pracovala na interpolaci ve stejné době, zejména Kansaská univerzita a její program SURFACE II. Stále byla funkce SYMAP nejmodernější, když naprogramovaná studentem vysoké školy.
Základní forma
Základní forma jak najít interpolované hodnoty u v daném bodě x na základě vzorce u_i=u(x_i) pro i=0,1,...,N užitím IDW je interpolační funkce:
:u(\mathbf{x}) = \sum_{i = 0}^{N}{ \frac{ w_i(\mathbf{x}) u_i } { \sum_{j = 0}^{N}{ w_j(\mathbf{x}) } } },
kde
:w_i(\mathbf{x}) = \frac{1}{d(\mathbf{x},\mathbf{x}_i)^p}
je jednoduchá funkce IDW, jak ji definoval Shepard, x označuje interpolovaný (libovolný) bod, xi je interpolovaný (známý) bod, d is je učena vzdáleností (metrický operátor) ze známého bodu xi k neznámému bodu x, N je celkový počet známých bodů použitých k interpolaci a p je kladné reálné číslo, které nazýváme silový parametr.
Váha se snižuje se zvyšující se vzdáleností od interpolovaného bodu. Větší hodnota p přiřazuje větší vliv na hodnoty nejblíže interpolovaného bodu, výsledky se mění do mozaiky dlaždic ( Voronoiův diagram) s téměř konstantní interpolovanou hodnotou pro velké hodnoty p. +more Pro dva rozměry, silové parametry p \leq 2, způsobuje interpolaci hodnot, které dominují nad vzdálenými body, protože s hustotou \rho datových bodů a sousedních bodů mezi vzdálenostmi r_0 to R, je výsledná váha přibližně :\sum_j w_j \approx \int_{r_0}^R \frac{2\pi r\rho dr}{r^p} = 2\pi\rho\int_{r_0}^R r^{1-p} dr, která diverguje pro R\rightarrow\infty a p\leq2. Pro N rozměrů, ty samé argumenty platí pro p\leq N. Pro volbu hodnoty p, zaprvé zvážíme míru shlazení, hustotu a rozdělení bodů pro interpolaci, maximální vzdálenost ve které jednotlivé body ovlivňují okolní.
Shepardova metoda je zjednodušení funkčního vztahu k měření odchylky mezi páry interpolovaných bodů {x, u} a i párů interpolovaných bodů {xi, ui}, definovaných vztahem: :\phi(\mathbf{x}, u) = \left( \sum_{i = 0}^{N}{\frac{(u-u_i)^2}{d(\mathbf{x},\mathbf{x}_i)^p}} \right)^{\frac{1}{p}} , odvozené od zjednodušené podoby: :\frac{\partial \phi(\mathbf{x}, u)}{\partial u} = 0.
Tuto metodu lze snadno rozšířit i na další rozměry prostoru a je to ve skutečnosti zobecnění Langrageovy aproximace do multirozměrového prostoru. Upravená verze algoritmu navržená pro trojvariační interpolaci vytvořená Robertem J. +more Renkou a je dostupná na Netlib jako algoritmus 661 v tomsově knihovně.
Příklad v rovině
Shepardova interpolace, ze 4 rozptýlených bodů s použitím p=2.
Metrika Lukaszyk-Karmowski
Jiná modifikace Shepardovy metody byla navržena Łukaszykem tedy aplikace experimentální techniky. Navržený vážený funkční vztah má formu:
:w_k(\mathbf{x}) = \frac{1}{(D_{**}(\mathbf{x}, \mathbf{x}_k) )^\frac{1}{2}}, kde D_{**}(\mathbf{x}, \mathbf{x}_k) je metrika Lukaszyk-Karmowski vybraná s ohledem na statistické rozdělení pravděpodobnosti chyby měření interpolovaných bodů.
Modifikovaná Shepardova metoda
Další modifikace Shepardovy metody počítá interpolované hodnoty na základě nejbližších sousedů v R-prostoru (místo celého vzorku). Váhy jsou nepatrně modifikovány v tomto případě:
:w_k(\mathbf{x}) = \left( \frac{\max(0,R-d(\mathbf{x},\mathbf{x}_k))}{R d(\mathbf{x},\mathbf{x}_k)} \right)^2
V kombinaci s rychlou strukturou prostorového vyhledávání (jako kd-strom) se stává efektivní N*logN interpolační metoda vhodná pro velkoměřítkové problémy.
