class: center, middle, inverse, title-slide .title[ # Пространственная интерполяция ] .subtitle[ ## Визуализация и анализ географических данных на языке R ] .author[ ### Тимофей Самсонов ] .institute[ ### МГУ имени Ломоносова, Географический факультет ] .date[ ### 2023-12-12 ] --- --- ## Детерминистическая интерполяция - Предполагается что анализируемые данные описываются некоторой аналитической функцией `\(Z(p, \lambda)\)`, где `\(p\)` — точка, а `\(\lambda\)` — набор внутренних параметров модели. - Задача: на основе известных данных `\(Z_i = Z(p_i)\)`, измеренных в точках `\(p_i\)`, и другой информации об исследуемом явлении подобрать набор параметров `\(\lambda\)` и построить функцию `\(Z(p, \lambda)\)` для всей исследуемой области `\(S\)`. --- ## Узлы интерполяции - Как правило, оценка производится по регулярной сетке узлов - В общем случае положение узлов интерполяции произвольно  --- ## Сетка (растр) интерполяции Каждый узел регулярной сетки можно сопоставить с центром ячейки, что обеспечивает сплошное покрытие и позволяет построить изолинии распределения показателя  --- ## Триангуляция Делоне и диаграмма Вороного .left-column[] .right-column[ __Триангуляция__ (на плоскости) — это разбиение фигуры на треугольники. > Под триангуляцией множества точек понимается триангуляция их выпуклой оболочки, в которой сами точки являются вершинами треугольников. __Диаграмма Вороного__ однозначно соответствует триангуляции Делоне и строится на основе серединных перпендикуляров к сторонам треугольников ] --- ## Линейные интерполяторы Искомая функция в произвольной точке `\(\mathbf{p}\)` ищется в виде линейной комбинации: `$$Z^{*}(\mathbf{p}) = \sum_{p_i \in D(\mathbf{p})} w_i (\mathbf{p}) Z(\mathbf{p}_i),$$` где: - `\(Z^{*}(\mathbf{p})\)` — оцениваемое значение в точке `\(\mathbf{p}\)`, - `\(Z(\mathbf{p}_i)\)` — известные значения в точках `\(\mathbf{p}_i\)`, - `\(D(\mathbf{p})\)` — множество точек `\(\mathbf{p}_i\)`, из некоторой окрестности точки p, определяемой расстоянием или количеством, - `\(w_i(\mathbf{p})\)` — нормированный вес точки `\(\mathbf{p}_i\)` для точки `\(\mathbf{p}\)` --- ## Метод ближайшего соседа - Каждый узел интерполяции `\(p\)` получает значение, равное значению ближайшей к нему точки наблюдений `\(p_k\)` - Множество `\(D\)` состоит из единственной точки `\(p_k (w_k = 1)\)`, в полигон Вороного которой попадает точка `\(p\)`. - Результатом является ступенчатая поверхность, где в пределах зоны влияния каждой точки `\(p_i\)` значение функции постоянно и равно `\(Z(p_i)\)` --- ## Метод ближайшего соседа Всю область интерполяции можно разбить с помощью диаграммы Вороного на зоны принадлежности к точкам наблюдений  --- ## Метод ближайшего соседа В пределах каждой ячейки значений интерполируемой величины считается постоянным  --- ## Метод ближайшего соседа Каждый узел интерполяции получает значение, равное значению ближайшей к нему точки наблюдений  --- ## Метод ближайшего соседа Результирующая поверхность является кусочно-постоянной  --- ## Метод ближайшего соседа Результирующая поверхность является кусочно-постоянной  --- ## Метод естественного соседа Множество `\(D\)` состоит из точек `\(p_i\)`, которые являются соседями точки p при встраивании ее в диаграмму Вороного точек `\(p_i\)` .pull-left[ Веса определяются из соотношения: `$$w_i(p) = A(v \cap v_i) / A(v)$$` - `\(v_i\)` — зона влияния точки `\(p_i\)` в исходной диаграмме Вороного, - `\(v\)` — зона влияния точки `\(p\)` при ее встраивании в диаграмму, - `\(A\)` — площадь зоны влияния, - `\(\cap\)` — пересечение ] .pull-right[  ] --- ## Интерполяция на основе триангуляции Для выполнения интерполяции на первом этапе необходимо для каждого треугольника найти уравнение плоскости, которое содержит четыре неизвестных коэффициента: `$$Ax + By + Cz + D = 0$$` `$$z(x, y) = -\frac{1}{C}(Ax+By+D)$$` Имея три точки `\(p_1\)`, `\(p_2\)` и `\(p_3\)`, искомые коэффициенты `\(A, B, C, D\)` можно получить путем решения уравнения, левая часть которого задана в форме определителя: `$$\begin{vmatrix} x - x_1 & y - y_1 & z - z_1 \\ x_2 - x_1 & y_2 - y_1 & z_2 - z_1 \\ x_3 - x_1 & y_3 - y_1 & z_3 - z_1 \end{vmatrix} = 0$$` --- ## Интерполяция на основе триангуляции Линейная интерполяция:  --- ## Интерполяция на основе триангуляции Бикубический метод Акимы:  --- ## Метод обратно взвешенных расстояний В методе обратно взвешенных расстояний значение показателя в произвольной точке получается как средневзвешенная сумма значений в исходных точках. Веса определяются обратно пропорционально расстоянию: чем дальше исходная точка удалена, тем меньший вес она будет иметь в оценке. `$$z(\mathbf{p}) = \begin{cases} \dfrac{\sum_{i = 1}^{N}{ w_i(\mathbf{p}) z_i } }{ \sum_{i = 1}^{N}{ w_i(\mathbf{p}) } }, & \text{если } d(\mathbf{p},\mathbf{p}_i) \neq 0 \text{ для всех } i, \\ z_i, & \text{если } d(\mathbf{p},\mathbf{p}_i) = 0 \text{ для одного } i, \end{cases}$$` где `\(w_i(\mathbf{p}) = | \mathbf p - \mathbf p_i | ^{-\beta}\)` --- весовая функция. --- ## Метод обратно взвешенных расстояний Метод __Шепарда__ — одна из наиболее распространенных модиификаций метода IDW. Веса вычисляются по формуле: `$$w_i(p) = d^{-2}_i / \sum_{j=1}^n d^{-2}_j$$` --- ## Метод обратно взвешенных расстояний `\(\beta = 2\)`  --- ## Метод обратно взвешенных расстояний `\(\beta = 3\)`  --- ## Метод обратно взвешенных расстояний `\(\beta = 4\)`  --- ## Метод обратно взвешенных расстояний `\(\beta = 5\)`  --- ## Метод обратно взвешенных расстояний `\(\beta \rightarrow \infty\)`  В предельном случае при больших значениях β метод IDW вырождается в метод ближайшего соседа --- ## Радиальные базисные функции В методе радиальных базисных функций значение в точке `\(p\)` находится путем взвешенного осреднения радиальных функций `\(\phi\)`: `$$Z(\textbf{p}) = \sum_{i=1}^n \lambda_i \phi\big(\lVert \textbf{p} - \textbf{p}_i\rVert\big)$$` где коэффициенты `\(\lambda_i\)` определяются заранее перед интерполяцией исходя из `\(n\)` условий вида `\(Z(\textbf{p}_i) = z_i\)`. __Радиальной функцией__ называется вещественнозначная функция, значение которой зависит только от расстояния между аргументом `\(\textbf{p}\)` и некой фиксированной точкой в пространстве `\(\textbf{c}\)`: `$$\phi(\textbf{p}, \textbf{c}) = \phi\big(\lVert \textbf{p} - \textbf{c}\rVert\big)$$` --- ## Радиальные базисные функции Метод __РБФ__ является одним из самых гибких благодаря широким возможностям выбора радиальной функции. К числу широко используемых радиальных функций относятся: - _Мультиквадрики_: `\(\phi(r) = \sqrt{r^2 + \delta^2}\)` - _Обратные мультиквадрики_: `\(\phi(r) = 1 / \sqrt{r^2 + \delta^2}\)` - _Мульти-логарифмическая_: `\(\phi(r) = \ln(r^2 + \delta^2)\)` - _Сплайны минимальной кривизны_: `\(\phi(r) = r^2 \ln(r^2)\)` > Недостатком метода РБФ является то, что поверхность может выходить за пределы исходного диапазона значений (хотя и обязательно проходит через исходные точки). --- ## Радиальные базисные функции __Сплайн минимальной кривизны__ (_thin plate spline — TPS_), дает поверхность, обладающую максимально низкой кривизной между исходными точками.  --- ## Иерархические базисные сплайны В данном методе поверхность представляется как сумма кусочно-полиномиальных функций, определяемых на основе двумерных базисных сплайнов  --- ## Глобальная регрессия Используется для глобальной аппроксимации тренда `$$P_1(x, y) = a + bx + cy$$` `$$P_{1.5}(x, y) = a + bx + cy + dxy$$` `$$P_{2}(x, y) = a + bx + cy + dxy + ex^2 + fy^2$$` Неизвестные коэффициенты находятся по методу наименьших квадратов решением системы линейных уравнений относительно коэффициентов a, b и т.д. Минимизируется функция потери: `$$L = \sum_{i=1}^{n} \Large[Z(x_i, y_i) - P_k(x_i, y_i) \Large]^2$$` --- ## Глобальная регрессия Полином степени 1  --- ## Глобальная регрессия Полином степени 2  --- ## Глобальная регрессия Полином степени 3  --- ## Локальная регрессия Полином степени 0 (горизонтальная плоскость)  --- ## Локальная регрессия Полином степени 1 (наклонная плоскость)  --- ## Локальная регрессия Полином степени 2