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

Пусть в качестве примера объектов в растровом формате имеем простейшие растровые полигоны А и В на рис. 3.15. Изобразим в виде квадрантов результат деления полигона А в соответствии с идеологией квадродерева. Получим структуру в виде дерева степени 4, известного как квадродерево (рис. 3.16).

Рис. 3.15. Простейшее растровое изображение

Учтем, что вся область из 2ⁿ * 2ⁿ пикселей начинается из корневого узла и представляется квадродеревом, по крайней мере, из n уровней. В нашем примере это иерархическое квадродерево имеет 4 уровня, а листья находятся на нулевом. Если обозначить – узел, - пиксель со значением 1, а – пиксель со значением 0, то результат кодирования из рис. 3.16 будет представлен квадродеревом на рис. 3.17. Из рис. 3.17 видно, что ячейки-пиксели имеют различный размер: минимальный 2⁰ * 2⁰, затем 2¹ * 2¹, 2² * 2² и максимальный 2³ * 2³. Минимальный размер пикселя имеют все листья. Из рис. 3.16 и 3.17 видим, что пикселем максимального размера являются ячейки 1 и 2, ячейка 44 имеет размер 2² * 2² , пикселем на уровне 1 имеют размер 2¹ * 2¹, к ним относятся пиксели с номерами 11, 12, 21 и т.д. На нулевом уровне находятся листья с минимальным размером пикселей 2⁰ * 2⁰. Нетрудно видеть, что номер уровня играет важную роль при кодировании растровых изображений: он определяет размер хранимых ячеек растра.

Рис. 3.16. Кодирование в виде квадродерева полигона А из рис. 3.15

Рис. 3.17. Построенное квадродерево

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

2.8. Преобразования «вектор–растр» и «растр–вектор»

Операции преобразования данных из векторного представления в растровое и обратно важны для многих ГИС, но особенно они необходимы в ГИС, поддерживающих как растровые, так и векторные форматы. Преобразования типа «вектор-растр» (векторно-растровое преобразование) – это типичная задача растровых ГИС (IDRISI, EPPL7 и т.д.) с поддержкой векторного ввода данных. Задача растрово–векторного преобразования актуальна для векторных ГИС (MapInfo Professional, ArcGIS и т.п.), когда в них необходимо ввести растровые изображения.

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

Алгоритм векторно-растрового преобразования довольно прост, а результаты его применения вполне однозначны. В качестве иллюстрации работы алгоритма рассмотрим пример. Пусть имеем набор векторных данных в виде полигонов с их номерами (рис. 3.18а). Наложим на исходное изображение регулярную сеть с необходимым размером квадратных или прямоугольных ячеек (рис. 3.18б). Покажем точками центры ячеек. Это делается для удобства при реализации операции принадлежности ячейки полигону: именно положение геометрического центра ячейки показывает принадлежность ячейки полигону. Ячейка получает номер того полигона, к которому она принадлежит (рис. 3.18в).

а	б	в

Рис. 3.18. Схема преобразования «вектор – растр»

Определение 3.14. Растрово–векторное преобразование или векторизация– это автоматическое или полуавтоматическое преобразование (конвертирование) растрового представления объектов в векторное с помощью определенного набора операций.

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

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

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

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

а	б	в

Рис. 3.19. Пример векторизации линии
(конвертации данных из растрового формата в векторный)

Вопросы и задания для самопроверки

1. Перечислите типы пространственных объектов, используемых в ГИС.

2. Приведите примеры реальных пространственных объектов, полученных из наборов объектов-примитивов (элементарных объектов).

3. С чем суть принципа послойной организации данных?

4. В каких случаях при послойном разделении пространственных данных имеет смысл в одном слое хранить данные о неоднотипных объектах?

5. Перечислите наиболее универсальные модели пространственных данных.

6. Чем отличается формат пространственных данных от модели пространственных данных?

7. Какие существуют варианты связи пространственных и атрибутивных данных в современных ГИС?

8. Назовите основные характеристики растровых моделей пространственных данных.

9. Известный Интернет-ресурс Google Maps для хранения космоснимков использует квадротомическую модель пространственных данных. Как вы думаете, почему разработчики выбрали именно эту модель?

10. Чем отличаются векторные топологические и нетопологические модели?

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

12. Предложите способ кодирования связей между объектами пространственных сетей с использование дополнительных атрибутов.

13. Какие понятия теории графов используются при построеии топологических моделей данных?

14. Какие проблемы и задачи возникают при преобразовании растровых моделей данных в векторные?