Тикунов В.С. (ред.) Основы геоинформатики. В 2 книгах. Книга 1

Подождите немного. Документ загружается.

разует исходный растровый слой в ряд пар целых (обычно двух-

байтовых) чисел, нечетные позиции которого отводятся для ука-

зания числа повторяющихся пикселов (групп) со значениями,

занимающими четные позиции ряда, образуя счетчик и значение

группы соответственно. Порядок просмотра исходной матрицы кон-

венциализируется, и в случае движения компрессора слева на-

право и сверху вниз (в лексикографическом порядке) матрица на

рис. 6 будет свернута в одномерный массив вида:

4С ID 2С IB 2Е 3D 1С IB 1Е 1С 3D 4С 3D IB ЗС ЗА 1В ЗС 1А

ЗВ 4D 1А2В.

Новая пара чисел (пакет) генерируется тогда, когда изменяет-

ся группа, или количество ее элементов превысит допустимое

(двухбайтовое) значение счетчика.

Степень сжатия данных, составляющая в нашем примере всего

около 2%, в общем случае будет зависеть от пространственной

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

ки, а при определенных условиях приближаясь по компактности

к векторным представлениям и форматам (которые сами по себе

обычно настолько компактны, что не нуждаются в сжатии). Су-

ществуют различные модификации группового кода, широко ис-

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

использовать и другие методы, разумеется, если это методы сжа-

тия данных без потерь: LZW-owdcmt по методу Лемпела—Зива

—

Велча, CCITT-кодирование по алгоритму Хаффмена и др.

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

модель данных пригодна для цифрового представления не только

пространственных объектов в ГИС, но и изображений. Примера-

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

ственно цифровой фотокамерой или полученные путем цифрова-

ния аналоговых негативов или фотоотпечатков на сканере хоро-

шего разрешения и далее превращенные (возвращенные) в гра-

фику на страницах иллюстрированных журналов или в семейном

фотоальбоме. Данные дистанционного зондирования Земли

—

аэро-

снимки и космические снимки, получаемые с борта космических

платформ и других летательных аппаратов и представляющие со-

бой, как мы отмечали ранее, один из основных источников дан-

ных для ГИС, сейчас в существенной своей части по форме тоже

цифровые, образуют класс растровых цифровых изображений, об-

рабатываемых программными средствами цифровой обработки

изображений. Растровой цифровой копией можно назвать оциф-

рованную на том же сканере бумажную карту, используемую в

Подробные сведения о методах сжатия растровых данных содержатся в Эн-

циклопедии форматов графических файлов (Мюррей, Рипер; 1997); в ней же

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

лей в программных средствах ГИС.

качестве графической подложки (растровой цифровой карты-ос-

новы) в малозатратных геоинформационных проектах.

Во всех перечисленных случаях речь идет о цифровых растро-

вых изображениях, образованных множеством его элементов —

пикселов, каждому из которых ставится в соответствие значение

(код) цвета или спектрального коэффициента яркости объекта

съемки. На эти далее неделимые элементы растра «разбивается» и

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

растровом представлении. Если атомарной единицей данных при

их описании служит элемент «разбиения» территории

—

регуляр-

ная пространственная ячейка (территориальная ячейка) правиль-

ной геометрической формы — речь идет о другой, отличной от

растровой, хотя и формально с нею схожей, регулярно-ячеистой

модели данных. Формальное сходство абсолютно в случае квадрат-

ной (прямоугольной) формы ячеек, хотя известны примеры регу-

лярных (или квазирегулярных) сетей (решеток) с ячейками пра-

вильной треугольной, гексагональной или трапециевидной фор-

мы, равновеликих или квазиравновеликих. При этом сеть может

строиться (разумеется, мысленно) на плоскости в условных пря-

моугольных координатах некоторой картографической проекции

или на поверхности шара или эллипсоида; в последнем случае

регулярными ячейками обычно являются сферические трапеции

фиксированного или переменного углового размера. Пример по-

строения сети равновеликих трапеций на сфере (что эквивалент-

но равновеликой цилиндрической (квадратной) проекции Лам-

берта) иллюстрируется рис. 7.

По ряду технологических и технических причин ГИС первых по-

колений (60

—

70-х годов XX в.) использовали регулярно-ячеистую

модель данных. Рис. 8 иллюстрирует пример одной из ранних авст-

ралийских геоинформационных систем

континентального масштаба ARIS, со-

здаваемой с начала 70-х годов, основу

которой составляла картографическая

БД GRID с представлением данных в

ячейках размером 0,5x0,5 мин и

0,25x0,25 мин и БД EIGHT с 50 тыс.

ячеек размером 1/8x1/8 мин.

Размеры ячеек могут быть различ-

ны, определяясь необходимым про-

странственным разрешением, образуя

иерахически организованные системы

их трех, как в вышеприведенном при-

мере ГИС ARIS\ или более вложен-

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

на равновеликие трапеции

к, соответствующих разным уровням

[Картография.., 1994, с. 95] разрешения (рис. 9).

Рис. 8. Регулярная сеть картографической БД GRID 0,5 Австралийской

национальной геоинформационной системы ARIS [Картография...,

1994, с. 169]

Представление данных на основе регулярных пространственных

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

рельефа

(ЦМР)

Земли ЕТ0Р05 и GTOP030. Первая из них содержит более 8 млн

высотных отметок в узлах регулярной сети сферических трапеций с

размерами 5x5 угл. мин, вторая, более детальная, представляет

высоты в узлах трапеций 30x30 с. Аналогичный регулярно-ячеи-

стый принцип организации данных, как увидим позже в разделе о

цифровом моделировании рельефа, положен в основу американ-

ского национального стандарта на цифровую модель рельефа DEM

Геологической съемки США с хранением высотных отметок по

профилям в узлах ячеек 30x30 м в системе координат километро-

вой сетки американских топографических карт (в проекции UTM),

а также в узлах трапеций разных размеров.

Заметим в заключение, что зачастую в понятие растровой мо-

дели данных объединяются как собственно растровые, так и регу-

лярно-ячеистые модели данных, а разница между пикселом (эле-

ментом изображения) и регулярной ячейкой (территориальным

элементом), четко различаемых, как упоминалось выше, стан-

Рис. 7, 8 заимствованы из работы [М.В.Dillencourt, H.Samet, 1988].

Угловой

размер

ячейки

Юм

Площадь

ячейки,

156006

1733,4

69,33 17,33 1,08 0,01

га

Число

ячеек

140 1260

28800 115200 1843000 200000000

Рис. 9. Иерархическая организация регулярной сети представления данных

в информационной системе для регионального планирования Ок-Риджа

ORMIS (США) [Computer software, 1981]

дартом SDTS, игнорируется. Причина в том, что и те, и другие

данные могут храниться в идентичных форматах и обрабатываться

одними и теми же средствами, не принимая во внимание (за не-

многими исключениями) семантического различия между ними.

Ранние реализации ГИС (конца 60-х

—

начала 70-х годов XX в.)

ориентировались преимущественно на растровые и регулярно-яче-

истые модели данных, что объясняется техническими и технологи-

ческими причинами: неразработанностью и непопулярностью век-

торных моделей в условиях отсутствия или недоступности средств

векторного цифрования картографических источников и средств

компьютерной графики, используемых в то время в основном в

экспериментах по автоматизированному картографированию.

Квадротомическая модель данных. Обычно описание этой свое-

образной модели начинают с того, что главный мотив ее ис-

пользования и поддержки программными средствами ГИС

—

ком-

пактность по сравнению с растровой моделью, расточительной

по объемам машинной памяти, требуемой для хранения растро-

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

можностях их значительного сжатия. Не меньшей эффективнос-

тью при сохранении быстрого доступа к элементам описания

пространственных объектов обладает квадротомическая модель дан-

ных, основанная на подходе, известном как квадротомическое

дерево (квадродерево). В его основе лежит разбиение территории

или изображения на вложенные друг в друга пикселы или регу-

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

туры

—

декомпозиции пространства на квадратные участки (квад-

раты, квадратные блоки, квадранты), каждый из которых де-

лится рекурсивно на четыре вложенных до достижения некото-

рого уровня пространственного разрешения. Механизм построе-

ния квадродерева исходного участка территории с пятью облас-

тями (полигонами), которому в растровом представлении соот-

ветствовал бы рис. 10, в результате его последовательной (рекур-

сивной) декомпозиции на квадранты иллюстрируется рис. 11.

На первом этапе деления исходного участка на четыре квад-

ратных блока и одновременном «ветвлении» квадродерева (рис. 12)

образуется один неделимый далее элемент №

(ему соответствует

«лист» дерева на рис. 12) и три «узла» делимых далее квадратов

первого уровня иерархии (принимая «корневой» уровень квадрат-

ного участка в целом за нулевой). За исключением девяти гомо-

генных квадратов, на втором иерархическом уровне все осталь-

ные элементы делятся далее, пока необходимость дальнейшего

деления не будет исчерпана на последнем, четвертом, этапе. Эко-

номия в сравнении с растровой моделью данных очевидна — об-

ласть Е оказалась представленной одним квадратом под номером

33 (а не 16 элементами растра или ячеек регулярной сети), и ее

цифровое описание подразумевает лишь формализованное пред-

ставление структуры квадродерева. Обычно оно строится на осно-

ве так называемой матрицы Мортона, определяющей оптималь-

ный в некотором смысле порядок ее кодирования и физической

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

Принимая за нулевой уровень иерархии земную сферу в це-

лом, можно построить глобальное квадротомическое дерево. Из-

вестные формулы между пространственным разрешением и уров-

нем дерева показывают, что уже на 23-м уровне иерархии достига-

ется метровое его разрешение [Картография..., 1994, с. 98

—

99].

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

реализована в немногих из известных программных средств ГИС.

Ее не следует путать с так называемыми пирамидальными моде-

лями, также рекурсивно организуемыми и используемыми при

обработке цифровых изображений, включая данные дистанци-

онного зондирования. В отличие от квадродерева они представ-

ляют собой набор растровых слоев изображений с механически

двукратно уменьшаемым разрешением, а потому более компак-

тных, искусственно «затрубленных» в целях их быстрого воспро-

изведения.

Известны трехмерные расширения линейной квадротомиче-

ской модели — это так называемая октотомическая модель (мо-

дель октарного дерева) как результат рекурсивного деления трех-

мерного пространства на восемь октантов, используемая для циф-

рового описания тел.

О матрице Мортона (G.Morton) см. подробней [П.Кингстон, 1976].

Рис. 10. Исходный участок территории с пятью областями

А, В, С, D и Е

6 7

8 9

13 14

31 32

15 16

31 32

25] 26

27 28

Рис. 11. Декомпозици51 исходного участка (рис. 10)

на квадранты

(1 —

34)

Рис. 12. Итоговое квадродерево как графическая иллюстрация

результатов декомпозиции участка на рис. 11

Предлагалась также модель трихотомического дерева с анало-

гичным квадратомическому делению треугольных элементов.

Векторные модели данных. Обобщенный класс векторных моде-

лей включает два их типа: векторные топологические и векторные

нетопологические модели. Они используются для цифрового пред-

ставления точечных, линейных и площадных (полигональных)

объектов по аналогии с картографией, где различаются объекты с

точечным, линейным и площадным характером пространственной

локализации, что определяет выбор графических средств их кар-

тографического отображения, и исторически связаны с технологи-

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

с помощью устройств ввода векторного типа — дигитайзеров (циф-

рователей) с ручным обводом, генерирующих поток пар плановых

координат (векторов) вслед за движением курсора (обводной го-

ловки) по планшету дигитайзера при отслеживании и записи гра-

фических объектов помещенного на него оригинала.

Множество точечных объектов, образующее слой однородных

данных (например, множество объектов, соответствующих насе-

ленным пунктам), может быть представлено в векторном формате

в виде неупорядоченной (необязательно упорядоченной) после-

довательности записей (строк таблицы), каждая из которых со-

держит три числа: уникальный идентификационный номер объекта

(iидентификатор), значение координаты Хи значение координа-

ты У в системе условных плановых прямоугольных декартовых

координат, например, плоскости стола дигитайзера:

х,

Линейный объект (в общем случае кривая) или граница полиго-

нального объекта могут быть представлены в виде последовательно-

сти образующих их точек (промежуточных точек), т.е. набором ли-

нейных отрезков прямых (сегментов), образующих полилинию.

Расположение образующих полилинию точек будет зависеть от

структуры исходной кривой. Их привязка к характерным точкам

кривой при достаточно мелком шаге цифрования позволяет дать

достаточно точное ее приближение. Два из возможных варианта ее

цифровой записи (формата) иллюстрируются ниже:

А В

END

Запись линейного объекта образована последовательностью ко-

ординатных пар (в нашем случае пяти точек) и содержит элемент,

позволяющий выделить его в общей совокупности записей линей-

ных объектов слоя, которому соответствует обычно файл данных.

В случае А это делается путем помещения вслед за идентификато-

ром целого числа, указывающего число координатных пар, в вари-

анте В линейные объекты отделяются друг от друга меткой END.

Разумеется, запись должна быть снабжена идентификатором объекта.

Таким же образом может быть представлена граница полиго-

нального объекта. При этом каждый именованный полигон (со

своим идентификатором) представляется записью пар координат,

образующих его границу в избранной последовательности (напри-

мер, по часовой стрелке). При описании множества полигонов

каждый отрезок границы, заключенный между двумя узловыми

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

описан в этом случае дважды (по часовой стрелке и против). Такая

модель данных для описания точечных, линейных и полигональ-

ных объектов носит наименование модели «спагетти». Она не яв-

ляется эффективной с точки зрения неизбыточности хранимых

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

ГИС и поддерживается недорогими программными средствами

настольного картографирования и ГИС. Другое ее наименование

—

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

Векторная топологическая модель обязана своим происхожде-

нием задаче описания полигональных объектов. Ее называют еще

линейно-узловой моделью. С ней связаны и особые термины, от-

ражающие ее структуру. Главные ее элементы (примитивы):

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

— сегмент (линейный сегмент, отрезок (прямой);

— узел;

— дуга;

— полигон (область, полигональный объект, многоугольник,

контур, контурный объект), в том числе:

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

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

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

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

Описание полигона в векторной топологической модели — это

множество трех элементов: узлов,

дуг и

собственно полигонов. Между

этими объектами устанавливаются некоторые топологические от-

ношения, необходимым элементом которых должна быть связь

дуг и узлов, полигонов и дуг. Последним приписываются указате-

ли разграничиваемых ею правого и левого полигонов, конвенци-

ализируя направление обхода контуров (рис. 13).

Соотношение между элементами векторного представления

пространственных объектов точечного, линейного и полигональ-

ного типов иллюстрируется рис. 14.

Последнее, что стоит сказать о векторной топологической мо-

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

В классическом варианте их взаимодействия, когда атрибутивные

данные управляются средствами реляционной СУБД и организо-

ваны в таблицы, а модель взаимодействия носит название геореля-

ционной, как уже упоминалось выше, связь устанавливается и под-

держивается через идентификатор объекта (рис. 15).

Различные варианты реализации векторных моделей допускают

введение других типов элементарных объектов. Так, граница поли-

гона может быть описана не только ломаной линией (полилини-

ей), но и математической кривой, например кривой Безье, опира-

Рис. 13. Линейно-узловое (вектор-

но-топологическое представление)

данных:

/, 2, 3, 6, 8, 10, 11, 12, 13 - узлы;

4, 5, 7, 9, 14, 15 — промежуточные

точки линейных сегментов (дуг); (/—

2), (2-3), (3-6), (6-8), (8-1),

(10- 11), (11-8), (3-12), (12- 10) -

дуги; полигоны А, В, С, D («ост-

ров», анклав, для описания которого

вводится фиктивный узел (псевдо-

узел) (13), Е (внешний по отноше-

нию ко всем полигонам в пределах

прямоугольного участка координатной

плоскости) полигон

Рис. 14. Одна из возможных векторных моделей данных (Molenaar М.

Single valued vector maps — a concept in geographic information sustems //

Geo-Informationssysteme. — 1989. — № 1. — P.

18 — 26).

Объекты точечно-

го, линейного и полигонального типов (point, line, area feature), дуги

(arc), узлы (node), последовательности координат (coordinates), формы

(shape), связанные отношениями типа «часть чего-либо» (part of),

«левый» и «правый» по отношению к чему-либо (left, right), «начало» и

«конец» чего-либо (begin, end)

ющейся на множество контрольных точек. Могут быть введены осо-

бые объекты, например прямоугольники, заданные двумя конт-

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