Ponderação de distância inversa - Inverse distance weighting

Ponderação de distância inversa ( IDW ) é um tipo de método determinístico para interpolação multivariada com um conjunto conhecido de pontos espalhados. Os valores atribuídos a pontos desconhecidos são calculados com uma média ponderada dos valores disponíveis nos pontos conhecidos.

O nome dado a este tipo de método foi motivado pela média ponderada aplicada, uma vez que recorre ao inverso da distância a cada ponto conhecido ("quantidade de proximidade") para atribuir pesos.

Definição do problema

O resultado esperado é uma atribuição discreta da função desconhecida em uma região de estudo: ${\ displaystyle u}$

${\ displaystyle u (x): x \ to \ mathbb {R}, \ quad x \ in \ mathbf {D} \ subset \ mathbb {R} ^ {n},}$

onde fica a região de estudo. ${\ displaystyle \ mathbf {D}}$

O conjunto de pontos de dados conhecidos pode ser descrito como uma lista de tuplas : ${\ displaystyle N}$

${\ displaystyle [(x_ {1}, u_ {1}), (x_ {2}, u_ {2}), ..., (x_ {N}, u_ {N})].}$

A função é ser "suave" (contínua e uma vez diferenciável), ser exata ( ) e atender às expectativas intuitivas do usuário sobre o fenômeno sob investigação. Além disso, a função deve ser adequada para uma aplicação de computador a um custo razoável (hoje em dia, uma implementação básica provavelmente fará uso de recursos paralelos ). ${\ displaystyle u (x_ {i}) = u_ {i}}$

Método de Shepard

Referência histórica

No Laboratório de Harvard para Computação Gráfica e Análise Espacial, a partir de 1965, uma coleção variada de cientistas convergiu para repensar, entre outras coisas, o que hoje chamamos de sistemas de informação geográfica .

A força motriz por trás do Laboratório, Howard Fisher, concebeu um programa de mapeamento por computador aprimorado que chamou de SYMAP, que, desde o início, Fisher queria melhorar a interpolação. Ele mostrou aos calouros da Harvard College seu trabalho no SYMAP, e muitos deles participaram de eventos do Laboratório. Um calouro, Donald Shepard, decidiu revisar a interpolação no SYMAP, resultando em seu famoso artigo de 1968.

O algoritmo de Shepard também foi influenciado pela abordagem teórica de William Warntz e outros do laboratório que trabalharam com análise espacial. Ele conduziu uma série de experimentos com o expoente da distância, decidindo por algo mais próximo do modelo gravitacional (expoente de -2). Shepard implementou não apenas a ponderação de distância inversa básica, mas também permitiu barreiras (permeáveis ​​e absolutas) para a interpolação.

Outros centros de pesquisa estavam trabalhando em interpolação nesta época, particularmente a Universidade de Kansas e seu programa SURFACE II. Mesmo assim, os recursos do SYMAP eram de última geração, embora tenham sido programados por um aluno de graduação.

Forma básica

Interpolação de Shepard para diferentes parâmetros de potência p , a partir de pontos dispersos na superfície${\ displaystyle z = \ exp (-x ^ {2} -y ^ {2})}$

Uma forma geral de encontrar um valor interpolado em um determinado ponto com base em amostras para usar IDW é uma função de interpolação: ${\ displaystyle u}$${\ displaystyle x}$${\ displaystyle u_ {i} = u (x_ {i})}$${\ displaystyle i = 1,2, ..., N}$

${\ displaystyle u (\ mathbf {x}) = {\ begin {cases} {\ dfrac {\ sum _ {i = 1} ^ {N} {w_ {i} (\ mathbf {x}) u_ {i} }} {\ sum _ {i = 1} ^ {N} {w_ {i} (\ mathbf {x})}}}, & {\ text {if}} d (\ mathbf {x}, \ mathbf { x} _ {i}) \ neq 0 {\ text {para todos}} i, \\ u_ {i}, & {\ text {if}} d (\ mathbf {x}, \ mathbf {x} _ { i}) = 0 {\ text {para alguns}} i, \ end {casos}}}$

Onde

${\ displaystyle w_ {i} (\ mathbf {x}) = {\ frac {1} {d (\ mathbf {x}, \ mathbf {x} _ {i}) ^ {p}}}}$

é uma função de ponderação IDW simples, conforme definido por Shepard, x denota um ponto interpolado (arbitrário), x _i é um ponto de interpolação (conhecido), é uma determinada distância ( operador métrico ) do ponto conhecido x _i ao ponto desconhecido x , N é o número total de pontos conhecidos usados ​​na interpolação e é um número real positivo, chamado de parâmetro de potência. ${\ displaystyle d}$${\ displaystyle p}$

Aqui, o peso diminui à medida que a distância aumenta dos pontos interpolados. Valores maiores de atribuem maior influência aos valores mais próximos do ponto interpolado, com o resultado se transformando em um mosaico de ladrilhos (um diagrama de Voronoi ) com valor interpolado quase constante para grandes valores de p . Para duas dimensões, os parâmetros de potência fazem com que os valores interpolados sejam dominados por pontos distantes, uma vez que com uma densidade de pontos de dados e pontos vizinhos entre distâncias a , o peso somado é de aproximadamente ${\ displaystyle p}$${\ displaystyle p \ leq 2}$${\ displaystyle \ rho}$${\ displaystyle r_ {0}}$${\ displaystyle R}$

${\ displaystyle \ 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,}$

que diverge para e . Para dimensões M , o mesmo argumento é válido para . Para a escolha do valor de p , pode-se considerar o grau de suavização desejado na interpolação, a densidade e distribuição das amostras sendo interpoladas, e a distância máxima na qual uma amostra individual pode influenciar as vizinhas. ${\ displaystyle R \ rightarrow \ infty}$${\ displaystyle p \ leq 2}$${\ displaystyle p \ leq M}$

O método de Shepard é uma consequência da minimização de um funcional relacionado a uma medida de desvios entre tuplas de pontos de interpolação { x , u } e i tuplas de pontos interpolados { x _i , u _i }, definidos como:

${\ displaystyle \ 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}},}$

derivado da condição de minimização:

${\ displaystyle {\ frac {\ partial \ phi (\ mathbf {x}, u)} {\ partial u}} = 0.}$

O método pode ser facilmente estendido a outros espaços dimensionais e é de fato uma generalização da aproximação de Lagrange em espaços multidimensionais. Uma versão modificada do algoritmo projetado para interpolação trivial foi desenvolvida por Robert J. Renka e está disponível no Netlib como algoritmo 661 na biblioteca de toms.

Exemplo em 1 dimensão

Interpolação de Shepard em 1 dimensão, a partir de 4 pontos espalhados e usando p = 2

Métrica Łukaszyk – Karmowski

Ainda outra modificação do método de Shepard foi proposta por Łukaszyk também em aplicações à mecânica experimental. A função de ponderação proposta tinha a forma

${\ displaystyle w_ {k} (\ mathbf {x}) = {\ frac {1} {(D _ {**} (\ mathbf {x}, \ mathbf {x} _ {k})) ^ {\ frac {1} {2}}}},}$

onde é a métrica Łukaszyk – Karmowski escolhida também em relação às distribuições de probabilidade de erro estatístico de medição dos pontos interpolados. ${\ displaystyle D _ {**} (\ mathbf {x}, \ mathbf {x} _ {k})}$

Método de Shepard modificado

Outra modificação do método de Shepard calcula o valor interpolado usando apenas os vizinhos mais próximos dentro da esfera R (em vez da amostra completa). Os pesos são ligeiramente modificados neste caso:

${\ displaystyle w_ {k} (\ mathbf {x}) = \ left ({\ frac {\ max (0, Rd (\ mathbf {x}, \ mathbf {x} _ {k}))} {Rd ( \ mathbf {x}, \ mathbf {x} _ {k})}} \ right) ^ {2}.}$

Quando combinado com uma estrutura de busca espacial rápida (como kd-tree ), torna-se um método de interpolação N log N eficiente , adequado para problemas de grande escala.

Referências

Veja também

• Estimativa de densidade do kernel