C Задание №3. Геометрическое упрощение линий

Цель задания — освоение методики геометрического упрощения линий.

Аннотация. Необходимо сравнить эффективность алгоритмов Дугласа-Пейкера, Висвалингам-Уайатта, Ванга-Мюллера и Ли-Оупеншоу при геометрическом урпощении береговых линий. При выполнении работы реализуются инструменты для вычисления коэффициента относительной извилистости и модифицированного расстояния Хаусдорфа.

Алгоритмы Дугласа-Пейкера, Висвалингам-Уайатта и Ли-Оупеншоу берутся из программной библиотеки cartagen для языка Python

Алгоритм Ванга-Мюллера используется из дополнительного модуля Geo Simplification для QGIS.

C.1 Теоретические сведения

C.1.1 Алгоритмы генерализации

Алгоритм Ли-Оупеншоу (Li and Openshaw 1992) использует «естественный принцип», суть которого заключается в удалении деталей, размер которых менее видимой величины. Для этого на исходное множество линий накладывается регулярная сет ка ячеек с разрешением d Участок линии, пересекающий ячейку, имеет точку входа в нее и точку выхода. Этот участок заменяется на середину отрезка, соединяющего две данные точки. Таким образом, удаляются все изгибы, находящиеся внутри ячеек. Принцип работы алгоритма иллюстрирует Рис. C.1. Видно, что по своему поведению результирующая линия похожа на скользящее среднее.

Принцип работы алгоритма Ли-Оупеншоу

Рис. C.1: Принцип работы алгоритма Ли-Оупеншоу

В основе работы алгоритма Ванга-Мюллера (Wang and Müller 1998) лежит сегментация линий на отдельные изгибы. Изгиб определяется как участок линии, на котором угол ее поворота сохраняет свой знак. Важным аспектом алгоритма является четкий алгоритм вычисления вершины изгиба, которая определяется как точка, имеющая максимальную сумму расстояний до начальной и конечной точки изгиба. Для каждого изгиба в алгоритме Ванга-Мюллера определяется его размер, изолированность, близость и схожесть с соседним изгибом. Изолированные изгибы подвергаются преувеличению. Расположенные рядом схожие изгибы объединяются в один путем слияния вершин и удаления изгиба между ними. Наконец, изгибы малого размера удаляются. Данные операции проиллюстрированы на Рис. C.2. В ArcGIS метод Ванга-Мюллера реализован в инструменте Simplify Line (режим BEND_SIMPLIFY).

Элементы алгоритма Ванга-Мюллера: а) удаление; б) объединение; в) преувеличение изгибов

Рис. C.2: Элементы алгоритма Ванга-Мюллера: а) удаление; б) объединение; в) преувеличение изгибов

Алгоритм Дугласа-Пейкера (Douglas and Peucker 1973) относится к алгоритмам редуцирования точек и основан на последовательном нахождении узлов линии, образующих максимальное отклонение от стягивающей хорды (Рис. C.3). В ArcGIS метод Дугласа-Пейкера реализован в инструменте Simplify Line (режим POINT_REMOVE).

Принцип работы алгоритма Дугласа-Пейкера

Рис. C.3: Принцип работы алгоритма Дугласа-Пейкера

Наконец, алгоритм Висвалингам-Уайатта (Visvalingam and Whyatt 1993) относится к алгоритмам редуцирования точек и основан на последовательном удалении точек, углы которых образуют минимальную эффективную площадь (Рис. C.4). В ArcGIS данный алгоритм представлен в модификации Жу и Джонса (Zhou and Jones 2005), где каждая площадь приобретает различный вес в зависимости от пропорций угла линии и реализован в инструменте Simplify Line (режим WEIGHTED_AREA).

Принцип работы алгоритма Висвалингам-Уайатта

Рис. C.4: Принцип работы алгоритма Висвалингам-Уайатта

C.1.2 Модифицированное расстояние Хаусдорфа

Модифицированное расстояние Хаусдорфа (MHD), широко используется как метрика оценки геометрической точности линий.

Пусть даны два множества точек \(\mathcal{A} = \lbrace a_1,...,a_{N_a} \rbrace\) и \(\mathcal{B} = \lbrace b_1,...,b_{N_b} \rbrace\). Тогда среднее расстояние между \(\mathcal{A}\) и \(\mathcal{B}\) может быть вычислено как \(\overline{d}(\mathcal{A},\mathcal{B}) = \frac{1}{N_a}\sum_{a \in \mathcal{A}}d(a,\mathcal{B})\), где \(d(a, \mathcal{B}) = \min_{b \in \mathcal{B}}\lVert a - b \rVert\). Аналогично, обратное расстояние между \(\mathcal{B}\) и \(\mathcal{A}\) вычисляется как \(\overline{d}(\mathcal{B},\mathcal{A}) = \frac{1}{N_b}\sum_{b \in \mathcal{B}}d(b,\mathcal{A})\), где \(d(b, \mathcal{A}) = \min_{a \in \mathcal{A}}\lVert b - a \rVert\).

Имея прямое и обратное расстоения между \(\mathcal{A}\) и \(\mathcal{B}\), модифицированное расстояние Хаусдорфа MHD вычисляется как:

\[ MHD(\mathcal{A}, \mathcal{B}) = max\big(\overline{d}(\mathcal{A},\mathcal{B}), \overline{d}(\mathcal{B},\mathcal{A})\big), \]

Грубо говоря, MHD есть есть максимальное из средних расстояний от \(\mathcal{A}\) к \(\mathcal{B}\) и от \(\mathcal{B}\) к \(\mathcal{A}\). Чем меньше значение MHD, тем интегрально ближе \(\mathcal{A}\) и \(\mathcal{B}\) друг к другу. Введение этой метрики вдохновлено классическим расстоянием Хаусдорфа (в котором \(d(\mathcal{A},\mathcal{B}) = max_{a \in \mathcal{A}} d(a,\mathcal{B})\)), которое, как видно из определения, чувствительно к точкам-выбросам, поскольку использует максимальное расстояние вместо среднего.

При оценке геометрической точности в качестве множеств \(\mathcal{A}\) и \(\mathcal{B}\) используются ребра исходного и генерализованного множеств линий соответственно.

C.1.3 Коэффициент относительной извилистости

Коэффициент извилистости — мера извилистости объекта, вычисляемая как отношение длины линии к длине отрезка, соединяющего ее концы. Пусть линия \(L\) состоит из \(n\) узлов, соединенных ребрами. Тогда коэффициент ее извилистости будет равен:

\[K = \frac{\sum_{i=1}^{n-1} l_{i, i+1}}{l_{1,n}}\]

где \(l_{i,k}\) — Евклидово расстояние между i-м и k-м узлом линии.

Коэффициент извилистости зависит от конфигурации сглаживающей, описывающей общую траекторию линии. В предельном случае, когда имеют дело с замкнутой фигурой, величина \(К\) не определена, т.к. длина стягивающей хорды равняется нулю. Помимо этого, общая извилистость дает мало информации о характере изгибов линии. Чтобы исправить этим недостатки, предлагается вычислить извилистость для каждого изгиба линии, а затем их осреднить:

\[\overline{K} = \frac{\sum_{j=1}^{m} K_j}{m}\]

где \(K_j\) — коэффициент извилистости для \(k\)-го изгиба линии, \(m\) — число изгибов

Часть 1. Автоматизация методов оценки геометрической точности и коэффициента относительной извилистости

Автоматизация вычисления модифицированного расстояния Хаусдорфа MHD (оценка геометрической точности)

Напишите на языке Python функцию, которая берет на вход два объекта (условно A и B) класса Shapely LineString и вычисляет между ними модифицированное расстояние Хаусдорфа.

Общий алгоритм действий в одну сторону (от A к B) должен быть такой:

  1. Конвертировать A во множество точек.
  2. Вычислить расстояние от каждой точки до B с использованием функции shapely.distance().
  3. Осреднить полученные расстояния.

Аналогичным образом надо получить среднее расстояние в обратную сторону (от B к A).

Из двух средних расстояний взять максимальное.

Автоматизация вычисления коэффициента относительной извилистости (оценка морфологического соответствия)

Напишите на языке Python функцию, которая берет на вход один объект класса Shapely LineString и вычисляет его относительную извилистость.

Общий алгоритм действий должен быть такой:

  1. Пройтись по всем точкам линии от первой до последней
  2. Для каждой последующей точки определить ее расположение относительно прямой, проходящей через две предыдущие точки (\(-1\), \(0\) или \(1\), см. оператор side в лекциях по геоинформатике).
  3. Разметить изгибы точками, в которых меняется знак поворота.
  4. Вычислить для каждого изгиба его извилистость как отношение его длины к длине базовой линии.
  5. Осреднить полученные значения.

Отчет

Опишите ваш опыт разработки инструментов оценки геометрической точности и морфологического соответствия для линий. Сопроводите данный раздел отчета снимками экрана и примерами получаемых результатов

Часть 2. Сравнение алгоритмов генерализации

  1. Выберите береговую линию для экспериментов.

  2. Используя шаг сетки, равный 2 мм в результирующем масштабе (1:5 000 000), упростите линию с помощью метода Ли-Оупеншоу.

  3. Подберите параметры алгоритмов Дугласа-Пейкера, Ванга-Мюллера и Висвалингам-Уайатта таким образом, чтобы количество результирующих точек в линиях было примерно равно (±5%) количеству точек после генерализации методом Ли-Оупеншоу. Выпишите эти параметры в отчет.

  4. Рассчитайте модифицированное Хаусдорфово расстояние от оригинальной линии для четырех полученных результатов генерализации

  5. Рассчитайте коэффициент относительной извилистости для исходной и результирующей линии.

  6. Сведите в одну таблицу параметры алгоритмов, а также рассчитанные величины MHD и коэффициента относительной извилистости по каждому алгоритму.

  7. Оцените алгоритмы по следующим критериям:

    1. При каких параметрах инструментов количество результирующих узлов линий одинаково?

    2. Модоифицированное хаусдорфово расстояние. Насколько эффективно алгоритм использует точки? Какой из алгоритмов дает контур, наиболее близко повторяющий исходную кривую?

    3. Относительная извилистость. Насколько сглаженным/угловатым получается изображение? Какой из алгоритмов дает значение извилистости более близкое к оригиналу?

    4. Какой метод на ваш взгляд дает наиболее удовлетворительные результаты с точки зрения принципов картографической генерализации и лучше передает морфологию объектов?

  8. Сделайте для отчета 4 иллюстрации с мини-легендой, на каждой из которых показан исходный контур и поверх — его генерализованная версия (по иллюстрации на каждый алгоритм). Разные алгоритмы выделите разными цветами.

  9. Изложите в отчете свой опыт сравнительного анализа алгоритмов генерализации.

References

Douglas, D. H., and T. K. Peucker. 1973. “Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature.” The Canadian Cartographer, no. 10(2): 112–22.
Li, Zhilin, and Stan Openshaw. 1992. “Algorithms for Automated Line Generalization Based on a Natural Principle of Objective Generalization.” International Journal of Geographical Information Systems 6 (5): 373–89. https://doi.org/10.1080/02693799208901921.
Visvalingam, M, and J D Whyatt. 1993. “Line Generalisation by Repeated Elimination of Points.” The Cartographic Journal 30 (1): 46–51. https://doi.org/10.1179/caj.1993.30.1.46.
Wang, Zeshen, and Jean-Claude Müller. 1998. “Line Generalization Based on Analysis of Shape Characteristics.” Cartography and Geographic Information Science 25 (1): 3–15. https://doi.org/10.1559/152304098782441750.
Zhou, Sheng, and Christopher B Jones. 2005. “Shape-Aware Line Generalisation With Weighted Effective Area.” In Developments in Spatial Data Handling, 12. Berlin, Heidelberg: Springer.