Иерархические растровые структуры

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

Рис.2.3. Иерархические растровые структуры данных, представленные пирамиды (а) и дерева (б)

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

На15-м уровне разрешение ячейки сравнимо с тем, что получают с геоспутников, на 26-м уровне пространственное разрешение сопоставимо с разрешением аэрофотоснимков, а на 30-м уровне - это разрешение сантиметрового масштаба. В ГИС ORRMIS, разработанной в США для целей регионального планирования, выделено в ней иерархии. На верхнем уровне, предназначенном для агрегированных данных масштаба биома или континента, раз в 7.5х7.5 минут (площадь 15606.6 га), на нижнем — размер, которым хранятся высотные отметки поверхности, 10х10 м э 0.01 га). Число максимальных по размерам ячеек 140, мини более 200 млн. памяти, необходимый для хранения пирамидальных структурированных несколько больше, чем для хранения исходного изображений. При последовательном удвоении стороны ячейки при переходе от подлежащего уровня к вышележащему это увеличение составляет примерно 30%. Однако, оно, безусловно, оправдывается повышением нормативности и универсальности базы данных, а также эффективности ряда алгоритмов обработки, таких как выделение контуров, анализ областей и др.

Сжатие информации

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

Групповое кодирование заключается в кодировании информации, содержащейся в каждой строке исходной матрицы с помощью пар значений, первое из которых представляет количество следующих друг за другом одинаковых значений кодируемого элемента, второе - значение элемента. В таком случае матрица, представленная на Рис. 2.2, редуцируется к виду:

4,1 5,2

2,1 7,2

9,2

9,2

6,2 1,1 2,2

6,22,1 1,2

В том же случае, если нет необходимости построчного представления - данных, к виду:

4,1 5,2 2,1 31,2 1,1 8,2 2,1 10,2 Как видим, информация, представленная на Рис. 2.2 кодируется с помощью 26 или 16 чисел, вместо 64 при записи в формате 1:1. Таким образом, объем занимаемой в этом случае памяти составит, соответственно, 41% и 25% от первоначального. Необходимо заметить также, что это, строго говоря, относится к случаю, когда информация, содержащаяся в растре, кодируется целыми числами (типа integer). Если эти числа - вещественные (типа real), то коэффициент сжатия будет еще больше.

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

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

Информация, содержащаяся в растре, представленном на Рис. 2.2 с помощью строчного кода представляется в виде:

1 1,4; 2 1,2; 5 7; 6 7,8.

Весьма эффективным способом сжатия растровой информации является использование Квадротомических (quadtree, Q-tree) структур, или Квадродеревъев, которые являются разновидностью иерархиальных (пирамидальных) структур растровых данных.

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

Рис. 2.4 Представление растровой информации с использованием квадротомических структур

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

 

Векторная модель данных

Векторно-нетопологическое представление данных (см. модель "спагетти") - цифровое представление точечных, линейных и полигональных пространственных объектов в виде набора координатных пар, с описанием только геометрии объектов.

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

Векторная модель данных:

• Основана на векторах (направленных отрезках прямых)
• Базовым примитивом является точка
• Объекты создаются путем соединения точек прямыми линиями или дугами
• Площади определяются набором линий
• Представляет собой объектно-ориентированную систему

Пример векторного представления пространственных объектов