Vážené inverzní vzdálenosti

Váž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} \subset \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. 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). 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

Shepardova interpolace pro různé hodnoty parametru p, z rozptýlených bodů na povrchu $z=\exp(-x^{2}-y^{2})$.

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, x_i je interpolovaný (známý) bod, $d$ is je učena vzdáleností (metrický operátor) ze známého bodu x_i 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. 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\leq 2$. 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ů {x_i, u_i}, 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. 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}))}{Rd(\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.

Podívejte se také

• Multivariační interpolace