4.1 Модели представления пространственных данных

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

Представление пространственных данных (spatial data representation; geospatial data model, spatial data model) – способ цифрового описания пространственных объектов и тип структуры пространственных данных.

В практике геоинформатики уже достаточно давно определился набор базовых моделей (представлений) пространственных данных, используемых для описания объектов размерности не более двух (планиметрических объектов): растровая модель; регулярно-ячеистая (матричная) модель; квадротомическая модель (квадродерево, дерево квадратов, квадрантное дерево, Q-дерево, 4-дерево); векторные модели – векторная топологическая (линейно-узловая) модель и векторная нетопологическая модель (модель «спагетти»).

Растровая модель данных.

Модель данных, именуемая растровой имеет аналогии в компьютерной графике, где растр – прямоугольная решетка – разбивает изображение на составные однородные (гомогенные) далее неделимые части, называемые пикселами (от англ, pixel, сокращение от «picture element» – элемент изображения), каждому из которых поставлен в соответствие некоторый код, обычно идентифицирующий цвет в той или иной системе цветов (цветовой модели). Из множества значений логических пикселов складывается цифровое изображение.

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

Рисунок 4 - Растровая модель данных.

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

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

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

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

Регулярно-ячеистая модель данных.

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

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

Размеры ячеек могут быть различны, определяясь необходимым пространственным разрешением, образуя иерахически организованные системы их трех или более вложенных друг в друга территориальных ячеек, соответствующих разным уровням разрешения. Заметим, что зачастую в понятие растровой модели данных объединяются как собственно растровые, так и регулярно-ячеистые модели данных, а разница между пикселом (элементом изображения) и регулярной ячейкой (территориальным элементом), четко различаемых, как упоминалось выше, стандартом SDTS, игнорируется. По ряду технологических и технических причин ГИС первых поколений (60-70-х годов XX в.) использовали регулярно-ячеистую модель данных.

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

Квадротомическая модель данных.

Квадротомическая модель данных (quadtree, quad tree, Q-tree, квадродерево, дерево квадратов. Q-дерево, 4-дерево) один из способов представления пространственных объектов в виде иерархической древовидной структуры, основанный на декомпозиции пространства на квадратные участки или квадратные блоки-квадранты (quarters, quads) каждый из которых делится рекурсивно на 4 вложенных класса до достижения некоторого уровня (числа Мортона (Morton оrdеr)), обеспечивающего требуемую детальность описания объектов, эквивалентную разрешению растра; обычно используется как средство снижения времени доступа, повышения эффективности обработки и компактности хранимых данных по сравнению с растровыми представлениями, являясь, образно выражаясь, «интеллектуализированным» растром. Обычно используется схема пространственной нумерации (индексирования) элементов, известная как матрица Мортона (Morton matrix).

Обычно описание этой своеобразной модели начинают с того, что главный мотив ее использования и поддержки программными средствами ГИС – компактность по сравнению с растровой моделью, расточительной по объемам магии мной памяти, требуемой для храпения растровых данных. Данная модель основана на подходе, известном как квадротомическое дерево (квадродерево).

Рисунок 5 - Исходный участок территории с пятью областями A, B, C и D (по Тикунову, 2004).

Рисунок 6 - Декомпозиция исходного участка (по Тикунову, 2004).

Векторные модели данных.

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

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

- уникальный идентификационный номер объекта /идентификатор);

- значение координаты X;

- значение координаты Y в системе условных плановых прямоугольных декартовых координат.

Рисунок 7 - Векторная модель данных.

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

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

Векторная нетопологическая модель (модель «спагетти»).

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

Векторная топологическая модель.

Векторная топологическая модель обязана своим происхождением задаче описания полигональных объектов. Ее называют еще линейно-узловой моделью. С ней связаны и особые термины, отражающие ее структуру.

Главные ее элементы (примитивы):

1. промежуточная точка;

2. сегмент (линейный сегмент, отрезок);

3. узел;

4. дуга;

5. полигон (область, полигональный объект, многоугольник, контур, контурный объект), в том числе:

- простой полигон;

- внутренний полигон («остров», анклав);

- составной полигон;

- универсальный полигон (внешняя область).

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

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

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

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

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

Выделим несколько групп разновидностей форматов данных:

1. Форматы систем автоматизированного проектирования (формат DXF программного средства типа САПР AutoCAD). Используются для различных инженерных расчётов и приведения схем.

2. Форматы различных графических редакторов (PCX, GIF, JPEG, TIFF и др.).

- GIF. Это довольно известный стандарт фирмы CompuServe для определения растровых цветных изображений. Этот формат позволяет высвечивать на различном оборудовании графические высококачественные изображения с большим разрешением и подразумевает механизм обмена и высвечивания изображений.

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

Высокая эффективность сжатия, которую дает этот алгоритм, основана на том факте, что в матрице частотных коэффициентов, образующейся из исходной матрицы после дискретного косинусного преобразования, низкочастотные компоненты расположены ближе к левому верхнему углу, а высокочастотные – внизу справа. Это важно потому, что большинство графических образов на экране компьютера состоит из низкочастотной информации, так что высокочастотные компоненты матрицы можно безболезненно выбросить. «Выбрасывание» выполняется путем округления частотных коэффициентов. После округления отличные от нуля значения низкочастотных компонент остаются, главным образом, в левом верхнем углу матрицы. Округленная матрица значений кодируется с учетом повторов нулей. В результате графический образ сжимается более чем на 90% , теряя очень немного в качестве изображения только на этапе округления.

3. Форматы систем записи, обмена и передачи данных дистанционного зондирования (BIL, BIB, BIP, BSQ).

4. Собственные форматы ГИС. Например, известный TIGER, VPF (США), DEM (геологическая служба США), NTF (Великобритания), SAIF (Канада) и относительно новый векторный формат VMap0, популярный в последнее время формат SFX.