Применение сплайнов при автоматизации процесса картографической генерализации

Термин «генерализация» пришел в картографию из французского языка, где слово «generalisation» обозначает обобщение, выделение наиболее общих, главных характеристик объектов. Лингвистические корни хорошо выражают картографическую сущность генерализации - отбор главного, существенного и целенаправленное обобщение, имеющее в виду изображение на карте той или иной части действительности в ее основных, типических чертах и характерных особенностях соответственно назначению, тематике и масштабу карты [1].

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

На современном этапе основной задачей картографической генерализации является генерализация географической основы тематических карт с целью построения картографических баз данных для геоинформационных систем (ГИС). С развитием ГИС ставятся требования к усовершенствованию методов обработки и отображения пространственной информации, основанной на данных картографических баз. Возникает необходимость отсекать ту часть информации, которая не может быть отображена согласно ограничениям, связанным с масштабом изображения и разрешающей способностью экрана.

Таким образом, ставится задача автоматизированной генерализации - отбор и обобщение изображенных на цифровой карте объектов соответственно масштабу изображения, разрешающей способности экрана и особенностям картографируемой территории с целью уменьшения объема и искажений при отображении обрабатываемых данных, увеличения скорости отображения [2].

Существующие алгоритмы и программы генерализации (ЦНИИГАиК, «Панорама») имеют ряд недостатков и не удовлетворяют тем требованиям, которые предъявляются к созданию цифровых карт.

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

Другой не менее важной задачей является формализация структуры данных исходной цифровой топографической карты (ЦТК), поскольку она, как правило, не содержит информации, необходимой для автоматической генерализации, а представлена в виде последовательного и неструктурированного списка объектов. Формализация структуры данных - идентификация объектов ЦТК или их совокупностей, их пространственные отношения (определение топологических отношений) и определение степени важности (приоритетов). На процесс распознавания структуры воздействуют управляющие параметры - масштаб производной карты, особенности территории и т. д.

Требует доработки формализация функций автоматической генерализации, заключающаяся в определении типов процессов генерализации для получения информационных структур на основании управляющих параметров.

Определены пять основных типов процессов: отбор картографических объектов, обобщение количественных характеристик, обобщение качественных характеристик, геометрическая генерализация и замена отдельных объектов их собирательными значениями. Эти процессы составляют библиотеку функций и определяют характерный для них набор формальных параметров [3].

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

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

Сплайном называется функция, которая вместе с несколькими производными непрерывна на всем заданном интервале [a;b]. Область определения [a;b] разбивают на частичные интервалы [x_i;x_i+1] шагом h=(b-a)/N (рис. 1). На каждом интервале сплайн-функция представлена алгебраическим многочленом степени n. Максимальная по всем частичным интервалам степень многочленов называется степенью сплайна, а разность между степенью сплайна и порядком наивысшей непрерывной на интервале [a;b] производной - дефектом сплайна.

На практике наиболее широкое применение получили сплайны третьей степени, имеющие на [a;b] непрерывную, по крайне мере, первую производную [3]. Эти сплайны называют кубическими и имеют на частичном интервале [x_i;x_i+1] общий вид

Рисунок 1 - Общий вид сплайн-функции на интервале [a;b]

(1)

Где f_i, f_i+1 - значения функции в узлах x_i, x_i+1: S₃(x_i)=f_i, S₃(x_i+1)=f_i+1;

- наклоны сплайна (первые производные) в узлах x_i, x_i+1.

Для того чтобы задать кубический сплайн S₃(x) на интервале [a;b], необходимо задать значения функции и наклоны в (N+1) узлах.

По способу построения сплайнов различают локальные и глобальные способы. В локальных способах сплайны строятся отдельно на каждом частичном отрезке [x_i;x_i+1] непосредственно с применением формулы (1). Наклоны сплайна определяются значениями первой производной в узлах

(2)

Если значения первой производной в узлах неизвестны, то используют приближенные формулы численного дифференцирования

(3)

Применение локального способа позволяет соблюсти непрерывность первой производной в узлах интерполяции. Непрерывность же второй производной не гарантируется, поэтому дефект такого сплайна обычно равен двум.

Применение глобального способа позволяет обеспечить непрерывность второй производной. Вторая производная характеризует кривизну сплайна. Обозначим значение второй производной в узле x_i «справа» и «слева» . Вторую производную «справа» определяем непосредственно из формулы (1), а слева - делаем замену i на (i-1).

В результате, из формулы (1) получим

(4)

Требуя непрерывности второй производной в узлах получим систему линейных уравнений относительно наклонов

(5)

Общее число неизвестных (N+1), поэтому нужно задать еще два условия, которые называют краевыми, связанными с «крайними» значениями m₀ и m_N.

Существует три варианта задания краевых условий:

1) заданы наклоны в краевых точках

и ;(6)

2) аппроксимацией по формулам численного дифференцирования

(7)

3) заданы вторые производные в краевых точках и , тогда наклоны в краевых точках могут быть найдены по формулам

(8)

Если в краевых точках вторые производные равны нулю и , то такая функция называется свободным кубическим сплайном. Она обладает минимальной кривизной и является самой гладкой из всех интерполяционных функций (рисунок 2).

Краевые условия (6)-(8) можно комбинировать между собой, т.е. в левом и правом узлах выбирать их независимо.

Система уравнений (5) имеет единственное решение, которое может быть найдено с применением любых численных методов [3]. Из решения системы находим наклоны m_i во всех узлах (i = 0, 1, …, N). Затем по формуле (1) задаем сплайн на каждом частичном интервале [x_i;x_i+1].

Сплайн, построенный глобальным способом, имеет дефект не выше единицы и обладает непрерывной второй производной [4].

Механической моделью сплайн-функции служит гибкий тонкий стержень из упругого материала. Если закрепить его в двух соседних узлах интерполяции с заданными углами наклона б и в (рисунок 2), то между узлами данный стержень (механический сплайн) примет форму, соответствующую минимуму его потенциальной энергии деформации [4]. Пусть форма деформированного стержня определяется функцией y=S(x). Из курса сопротивления материалов уравнение свободного равновесия упругого деформированного стержня описывается равенством нулю четвертой производной S^IV(x)=0. Отсюда следует, что между соседними узлами интерполяции функция S(x) является многочленом третьей степени [5].

Рисунок 2 - Механическая модель свободного кубического сплайна

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

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

Предельная ошибка равна графической точности масштаба (0,2 мм). Выполним расчеты допустимых отклонений l_max и l_min, которые не должны превышать значение уровня значимости у для каждого масштаба карты.

Результаты расчетов приведены в таблице.

Таблица 1 Расчеты допустимых отклонений

Точность автоматизированной генерализации напрямую связана с масштабом карты, так как предельная ошибка зависит от масштаба. С целью ликвидации искажения генерализируемого изображения мы предлагаем усовершенствовать существующие алгоритмы, которые с учетом масштаба карты будут автоматически очерчивать изображение при помощи сплайн-функций [6].

топографический карта сплайн генерализация

Список литературы

1. Вахрамеева Л.А. Картография. М.: Недра, 1981.

2. Берлянт А.М. Картография. М.: Аспект-Пресс, 2001.

3. Колосков Ю.В., Хлебникова Т.А. Технология автоматизированной генерализации // Геодезия и картография. 2005. № 6. 38 c.

4. Волков Е.А. Численные методы. М.: Наука, 1987.

5. Турчак Л.И. Основы численных методов. М.: Наука, 1987.

6. Альберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения. М.: Мир, 1972.

Размещено на Allbest.ru