Взвешивание обратных расстояний - Inverse distance weighting

Взвешивание обратных расстояний (IDW) является разновидностью детерминированный метод за многомерная интерполяция с известным разбросанным набором точек. Присвоенные значения неизвестным точкам вычисляются с помощью средневзвешенное значений, доступных в известных точках.

Название, данное этому типу методов, было мотивировано средневзвешенное применяется, поскольку он обращается к обратному расстоянию до каждой известной точки ("количество близости") при назначении весов.

Определение проблемы

Ожидаемый результат - дискретное присвоение неизвестной функции ${ displaystyle u}$ в изучаемом регионе:

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

куда ${ displaystyle mathbf {D}}$ регион исследования.

Набор ${ displaystyle N}$ известные точки данных можно описать как список кортежи:

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

Функция должна быть «гладкой» (непрерывной и однократно дифференцируемой), а именно ( ${ Displaystyle и (х_ {я}) = и_ {я}}$ ) и оправдать интуитивные ожидания пользователя в отношении исследуемого явления. Кроме того, функция должна подходить для компьютерного приложения по разумной цене (в настоящее время базовая реализация, вероятно, будет использовать параллельные ресурсы ).

Метод Шепарда

Историческая справка

Начиная с 1965 года в Гарвардской лаборатории компьютерной графики и пространственного анализа собралось множество ученых, чтобы переосмыслить то, что мы сейчас называем географические информационные системы.^[1]

Движущая сила лаборатории, Говард Фишер, задумал улучшенную программу компьютерного картографирования, которую он назвал SYMAP, которую с самого начала Фишер хотел улучшить интерполяцию. Он показал первокурсникам Гарвардского колледжа свою работу над SYMAP, и многие из них участвовали в лабораторных мероприятиях. Один новичок, Дональд Шепард, решил пересмотреть интерполяцию в SYMAP, результатом чего стала его знаменитая статья 1968 года.^[2]

На алгоритм Шепарда также повлиял теоретический подход Уильям Варнц и другие сотрудники лаборатории, которые занимались пространственным анализом. Он провел ряд экспериментов с показателем расстояния, выбрав что-то более близкое к модели гравитации (показатель -2). Шепард реализовал не только базовое взвешивание обратных расстояний, но также разрешил барьеры (проницаемые и абсолютные) для интерполяции.

В то время над интерполяцией работали другие исследовательские центры, в частности Университет Канзаса и их программа SURFACE II. Тем не менее, возможности SYMAP были самыми современными, даже если они были запрограммированы студентом.

Основная форма

Интерполяция Шепарда для различных параметров мощности п, из разрозненных точек на поверхности

{ Displaystyle Z = ехр (-x ^ {2} -y ^ {2})}

Общая форма поиска интерполированного значения ${ displaystyle u}$ в данный момент ${ displaystyle x}$ на основе образцов ${ Displaystyle и_ {я} = и (х_ {я})}$ за ${ Displaystyle я = 1,2, ..., N}$ использование IDW - это интерполирующая функция:

{ Displaystyle и ( mathbf {x}) = { begin {case} { 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 {для всех}} i, u_ {i}, & { text {if}} d ( mathbf {x}, mathbf {x} _ { i}) = 0 { text {для некоторых}} i, end {case}}}

куда

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

простая функция взвешивания IDW, как определено Шепардом,^[2] Икс обозначает интерполированную (произвольную) точку, Икс_я - интерполирующая (известная) точка, ${ displaystyle d}$ заданное расстояние (метрика оператор) из известной точки Икс_я в неизвестную точку Икс, N - общее количество известных точек, используемых при интерполяции, и ${ displaystyle p}$ положительное действительное число, называемое параметром мощности.

Здесь вес уменьшается по мере увеличения расстояния от интерполированных точек. Высшие ценности ${ displaystyle p}$ назначать большее влияние значениям, ближайшим к интерполированной точке, в результате чего получается мозаика плиток ( Диаграмма Вороного ) с почти постоянным интерполированным значением для больших значений п. Для двух измерений параметры мощности ${ displaystyle p leq 2}$ приводят к тому, что в интерполированных значениях преобладают точки, находящиеся далеко, поскольку с плотностью ${ displaystyle rho}$ точек данных и соседних точек между расстояниями ${ displaystyle r_ {0}}$ к ${ displaystyle R}$ , суммарный вес составляет примерно

{ displaystyle sum _ {j} w_ {j} приблизительно int _ {r_ {0}} ^ {R} { frac {2 pi r rho , dr} {r ^ {p}}} = 2 pi rho int _ {r_ {0}} ^ {R} r ^ {1-p} , dr,}

который расходится для ${ Displaystyle R rightarrow infty}$ и ${ displaystyle p leq 2}$ . За M размеры, тот же аргумент верен для ${ displaystyle p leq M}$ . За выбор стоимости для пможно учитывать желаемую степень сглаживания при интерполяции, плотность и распределение интерполируемых отсчетов, а также максимальное расстояние, на котором отдельному отсчету разрешено влиять на окружающие.

Метод Шепарда является следствием минимизации функционала, связанного с мерой отклонений между кортежи интерполирующих точек {Икс, ты} и я наборы интерполированных точек {Икс_я, ты_я}, определяется как:

{ 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}},}

выводится из условия минимизации:

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

Метод может быть легко распространен на другие размерные пространства, и фактически он является обобщением аппроксимации Лагранжа на многомерные пространства. Модифицированная версия алгоритма, предназначенная для трехмерной интерполяции, была разработана Робертом Дж. Ренка и доступна в Netlib как алгоритм 661 в библиотеке томов.

Пример в 1 измерении

Интерполяция Шепарда в одном измерении по 4 разрозненным точкам и с использованием п = 2

Метрика Лукашика – Кармовского

Еще одна модификация метода Шепарда была предложена Лукашиком.^[3] также в приложениях к экспериментальной механике. Предлагаемая весовая функция имела вид

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

куда ${ Displaystyle D _ {**} ( mathbf {x}, mathbf {x} _ {k})}$ это Метрика Лукашика – Кармовского выбран также в отношении статистическая ошибка распределения вероятностей измерения интерполированных точек.

Модифицированный метод Шепарда

Другая модификация метода Шепарда вычисляет интерполированное значение, используя только ближайших соседей в пределах р-сфера (вместо полной выборки). В этом случае веса немного изменены:

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

В сочетании с быстрой структурой пространственного поиска (например, kd-дерево ) становится работоспособным N бревно N метод интерполяции, подходящий для крупномасштабных задач.

Смотрите также

[1] Крисман, Николас. "История Гарвардской лаборатории компьютерной графики: выставка плакатов" (PDF).

[shepardArticle-2] а ^б Шепард, Дональд (1968). «Функция двумерной интерполяции для нерегулярных данных». Труды 1968 г. ACM Национальная конференция. С. 517–524. Дои:10.1145/800186.810616.

[3] Лукашик С. (2004). «Новая концепция вероятностной метрики и ее применения в аппроксимации разрозненных наборов данных». Вычислительная механика. 33 (4): 299–304. Дои:10.1007 / s00466-003-0532-2.

[1]

[2]

[3]