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

editovat

Očekávaný výsledek je diskrétní přiřazení neznámé funkce   v pozorované oblasti:

 

kde   je studovaná oblast.

Sada   známých datových bodů lze popsat jako seznam n-tic:

 

Funkce má být "hladká" (kontinuální a jednou diferencovatelná), aby byla přesná ( ) 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

editovat

Historická zmínka

editovat

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.[1]

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

editovat
 
Shepardova interpolace pro různé hodnoty parametru p, z rozptýlených bodů na povrchu  .

Základní forma jak najít interpolované hodnoty u v daném bodě x na základě vzorce   pro   užitím IDW je interpolační funkce:

 

kde

 

je jednoduchá funkce IDW, jak ji definoval Shepard,[1] x označuje interpolovaný (libovolný) bod, xi je interpolovaný (známý) bod,   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   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ř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  , způsobuje interpolaci hodnot, které dominují nad vzdálenými body, protože s hustotou   datových bodů a sousedních bodů mezi vzdálenostmi   to  , je výsledná váha přibližně

 

která diverguje pro   a  . Pro N rozměrů, ty samé argumenty platí pro  . 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:

 

odvozené od zjednodušené podoby:

 

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ě

editovat
 
Shepardova interpolace, ze 4 rozptýlených bodů s použitím p=2.

Metrika Lukaszyk-Karmowski

editovat

Jiná modifikace Shepardovy metody byla navržena Łukaszykem[2] tedy aplikace experimentální techniky. Navržený vážený funkční vztah má formu:

 

kde   je metrika Lukaszyk-Karmowski vybraná s ohledem na statistické rozdělení pravděpodobnosti chyby měření interpolovaných bodů.

Modifikovaná Shepardova metoda

editovat

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ě:

 

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.

Reference

editovat
  1. a b Shepard, Donald (1968). "A two-dimensional interpolation function for irregularly-spaced data". Proceedings of the 1968 ACM National Conference: 517–524. doi:10.1145/800186.810616. 
  2. Łukaszyk S. A new concept of probability metric and its applications in approximation of scattered data sets. Computational Mechanics. S. 299–304. DOI 10.1007/s00466-003-0532-2. 

Podívejte se také

editovat