Гис как разновидность информационных систем

ОСНОВНЫЕ КОМПОНЕНТЫ ГИС

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

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

Программное обеспечение Программное обеспечение – совокупность программных средств, реализующих функциональные возможностей ГИС, и программных документов, необходимых при их эксплуатации. Структурно программное обеспечение ГИС включает базовые и прикладные программные средства. Базовые программные средства включают: операционные системы (ОС), программные среды, сетевое программное обеспечение и системы управления базами данных. Операционные системы предназначены для управления ресурсами ЭВМ и процессами, использующими эти ресурсы. На настоящее время основные ОС: Windows и Unix. Любая ГИС работает с данными двух типов данных - пространственными и атрибутивными. Для их ведения программное обеспечение должно включить систему управления базами тех и других данных (СУБД), а также модули управления средствами ввода и вывода данных, систему визуализации данных и модули для выполнения пространственного анализа. Прикладные программные средства предназначены для решения специализированных задач в конкретной предметной области и реализуются в виде отдельных приложений и утилит.

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

механизм обмена данными.
Программное обеспечение ГИС

Программные обеспечения ГИС делятся на пять основных используемых классов. Первый наиболее функционально полный класс программного обеспечения - это инструментальные ГИС. Они могут быть предназначены для самых разнообразных задач: для организации ввода информации (как картографической, так и атрибутивной), ее хранения (в том числе и распределенного, поддерживающего сетевую работу), отработки сложных информационных запросов, решения пространственных аналитических задач (коридоры, окружения, сетевые задачи и др.), построения производных карт и схем (оверлейные операции) и, наконец, для подготовки к выводу на твердый носитель оригинал-макетов картографической и схематической продукции. Как правило, инструментальные ГИС поддерживают работу, как с растровыми, так и с векторными изображениями, имеют встроенную базу данных для цифровой основы и атрибутивной информации или поддерживают для хранения атрибутивной информации одну из распространенных баз данных: Paradox, Access, Oracle и др. Наиболее развитые продукты имеют системы run time, позволяющие оптимизировать необходимые функциональные возможности под конкретную задачу и удешевить тиражирование созданных с их помощью справочных систем.

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

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

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

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

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

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

Стремительный рост количества потребителей ГИС-технологий за счет децентрализации расходования бюджетных средств и приобщения к ним все новых и новых предметных сфер их использования. Если до середины 90-х годов основной рост рынка был связан лишь с крупными проектами федерального уровня, то сегодня главный потенциал перемещается в сторону массового рынка. Это мировая тенденция: по данным исследовательской фирмы Daratech (США), мировой рынок ГИС для персональных компьютеров в настоящий момент в 121,5 раза опережает общий рост рынка ГИС-решений.

Массовость рынка и возникающая конкуренция приводят к тому, что потребителю за ту же или меньшую цену предлагается все более качественный товар. Так, для ведущих поставщиков инструментальных ГИС стала уже правилом поставка вместе с системой и цифровой картографической основы того региона, где распространяется товар. Да и сама приведенная классификация ПО стала реальностью. Еще буквально два-три года назад функции автоматизированной векторизации и справочных систем можно было реализовать только с помощью развитых и дорогостоящих инструментальных ГИС (Arc/Info, Intergraph).

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

Такие продукты, как GeoDraw / GeoGraph, Sinteks / Tri, GeoCAD, EasyTrace, обладают не только значительным количеством пользователей, но и имеют уже все атрибуты рыночного оформления и поддержки. В российской, геоинформатике есть некая критичная цифра работающих инсталляций - пятьдесят. Как только вы ее достигли, дальше есть только два пути: или резко вверх, наращивая число своих пользователей, либо - уход с рынка из-за невозможности обеспечить необходимую поддержку и развитие своему продукту. Интересно, что все упомянутые программы обслуживают нижний ценовой уровень; другими словами, в них найдено оптимальное соотношение между ценой и напором функциональных возможностей именно для российского рынка.

Строительство и ремонт

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

Техническое задание на проектирование объекта строительства, реконструкции и капитального ремонта также должно включать приблизительное расположение объекта на местности. Кроме того, включение в ТЗ на проектирование в качестве исходных данных пространственной моде- ли существующей инфраструктуры может снизить стоимость изыскательских работ и повысить качество проектного решения в части связи нового проектируемого объекта с имеющейся сетью дорог. В результате проектных работ получается проектная документация. На текущий момент она представляется в бумажном виде (ряд «плоских» чертежей и смет). Представление запроектированного объекта в виде САПР-модели, которую можно внедрить в геоинформационное представление сети автомобильных дорог, существенно повысит полезность проекта. Это связано с тем, что на этапе реализации автоматизируется анализ объемов выполненных работ и контроль соответствия геометрии нового объекта предложенному проектному решению. Также совмещение САПР-моделей не- скольких смежных проектов в геоинформационной системе с существующей обстановкой позволит на качественно новом уровне проанализировать проектную деятельность. По результатам строительства выполняется исполнительная документация. Именно в этот момент должна появляться точная геопространственная модель дороги, дополняющая модель существующей дорожной сети. Если в рамках исполнительной документации будет появляться эта модель, полностью отпадет необходимость в последующих работах по паспортизации. Введение подобной практики получения ГИС-модели автомобильных дорог, во-первых, существенно уточнит знания ОУДХ об объекте управления, а во-вторых, исключит работы по получению низкокачественных паспортов и ведомостей, создаваемых по устаревшим нормативам. На основании единой геоинформационной модели, в которую интегрируются как проектные материалы, так и исполнительные данные, легко автоматически получать сводные карты выполненных работ, фактически отражающие то, что и как сделано.

Содержание дорог

Содержание автомобильных дорог – непрерывный процесс обслуживания дорог для поддержания их транспортно-эксплуатационных характеристик и безопасности дорожного движения. Состав работ по содержанию является сезонным (например, уборка снега, восстановление дорожной разметки). Дорогам (или их отдельным участкам, а также искусственным сооружениям) назначается категория (уровень) содержания, исходя из их значимости, транспортной работы и климатических особенностей. Таким образом, для адекватного планирования и исполнения содержания необходима информация о действительном расположении дорог и объектов, их точной геометрии и связи с окружающей обстановкой. Планирование работ по содержанию существенным образом опирается на актуальные транспортно-эксплуатационные показатели (данные диагностики), точно привязанные к расположению на местности. При планировании также важными являются данные о транспортной работе участков дорожной сети. Все эти данные естественным образом вписываются в геоинформационную модель дороги; более того, без геоинформационной модели невозможно адекватно рассчитать транспортную работу и стратегическую важность участков дорог, обеспечивающих транспортную доступность населения, промышленности и военных объектов. Технические задания на содержание дорожной сети также полезно формировать на основе точной геометрии автомобильных дорог. Это позволит очень точно (в пределах 1%) учесть площадные показатели и протяженность. Кроме того, для ряда работ (например, для ямочного ремонта, нанесения разметки) наличие точной геометрической привязки выполняемых работ существенно повысит их качество и эффективность расходования средств. Что касается организации дорожного движения, применение ГИС эффективно в следующем случае. Актуальная геоинформационная модель сети автомобильных дорог становится исходным базисом для выполнения проектов организации дорожного движения, исключая повторение работ по съемке обстановки. Кроме того, единая метрика, заложенная в модели, обеспечит предельную точность позиционирования средств организации движения, как на этапе их проектирования, так и на этапе реализации. Все это повышает безопасность движения, исключая абсурдные ситуации, когда горизонтальная разметка не соответствует дорожным знакам.

Подсистемы ГИС.

В соответствии с данным выше определением, ГИС имеют следующие

подсистемы:

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

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

3. Подсистема манипуляции данными и анализа, которая, выполнив различныезадачи на основе этих данных, группирует и разделяет их;

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

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

табличной, диаграммной или картографической форме.

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

процесс картографирования - сбором данных и компиляцией (составлением) карт.

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

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

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

эквивалент, компьютерная картография, выходной продукт в целом тот же - карта.

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

 

Составные части ГИС.

Работающая ГИС включает в себя пять ключевых составляющих:

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

Программное обеспечение- ГИС содержит функции и инструменты, необходимые для хранения, анализа и визуализации географической (пространственной) информации. Ключевыми компонентами программных продуктов являются: инструменты для ввода и оперирования географической информацией; система управления базой данных (DBMS или СУБД); инструменты поддержки пространственных запросов, анализа и визуализации (отображения); графический пользовательский интерфейс (GUI или ГИП) для легкого доступа к инструментам.

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

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

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

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

Уменьшение затрат машинной памяти для хранения растровых данных достигается использованием алгоритмов Сжатия. Одним из простых и достаточно эффективных методов сжатия растровых данных является Групповое кодирование (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 Представление растровой информации с использованием квадротомических структур

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

 

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

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

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

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

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

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

Безразмерные типы объектов

· Точка - определяет геометрическое местоположение

· Узел - топологический переход или конечная точка, также может определять местоположение

Одномерные типы объектов

· Линия - одномерный объект

· Линейный сегмент - прямая линия между двумя точками

· Строка - последовательность линейных сегментов

· Дуга - геометрическое место точек, которые формируют кривую определенную математической функцией

· Связь - соединение между двумя узлами

· Направленная связь - связь с одним определенным направлением

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

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

Двумерные типы объектов

· Область - ограниченный непрерывный объект, который может включать или не включать в себя собственную границу

· Внутренняя область - область, которая не включает собственную границу

· Полигон (контур) - 2-мерный (площадной) объект, внутренняя область, образованная замкнутой последовательностью дуг в векторно-топологических представлениях или сегментов в модели "спагетти". Различают простой П., не содержащий внутренних П., и составной П, содержащий внутренние П., называемые также "островами" (island) и анклавами (hole).

· Пиксель - элемент изображения, который является самым малым неделимым элементом изображения

Пример слоев, составленных из пространственных объектов линейного типа

Примеры слоев, составленных из пространственных объектов полигонального типа

Преимущества

Растровая модель	Векторная модель
1. Простая структура данных 2. Эффективные оверлейные операции 3. Работа со сложными структурами 4. Работа со снимками	1. Компактная структура 2. Топология 3. Качественная графика

 

 

Квадротомическое дерево (квадродерево) - структура данных, используемая для представления двумерных пространственных данных. Существует несколько типов квадродеревьев в зависимости от базового типа данных. (точки, площади, кривые, поверхности или объемы). Наиболее общим типом квадродерева и примером использования является квадродерево растрового изображения (см. рисунок 1, рисунок 3 и рисунок 4 - примеры изображения и его бинарного представления, блоков разбиения и квадродерева). Далее, для конкретности, под пространственными данными везде будем понимать растровое изображение.

Следуя Samet (1990), под двумерным изображением понимается массив элементов изображения (пикселов, pixel). Если каждый из пикселов имеет только два состояния - черный или белый (подсвечен или нет), то изображение называется бинарным. Если пикселы могут принимать более двух значений, то их значения могут трактоваться как оттенки серого, а изображение в этом случае называется изображением в градациях серого (grey-scale). Цветные изображения организованы аналогичным образом. Квадродеревья наиболее широко используются для работы с двухцветными изображениями, поэтому в дальнейшем будем иметь дело преимущественно с бинарными изображениями. Будем также в дальнейшем подразумевать, что фоновым в бинарном изображении является белый цвет.

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

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

Рис. 1: (a) изображение (b) его бинарный образ (c) его квадротомическое разбиение

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

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

Рис. 2: Пример квадродерева

 

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

Рис. 3: (a) первый этап разбиения (b) второй этап разбиния
(c) третий этап разбиения (d) изображение полностью разбито

На каждом этапе построения квадродерева изображение разбивается на четыре квадранта и каждому присваивается одно из следующих значений

• 1) белый -->квадрант полностью белый. Обозначается белым квадратом.
• 2) черный -->квадрант полностью черный. Обозначается черным квадратом.
• 3) серый -->квадрант - смесь черного и белого. Обозначается белым кругом.

На нулевом этапе полному изображению (рисунок 1a) сопоставляется корневой узел дерева (рисунок 4). Далее четырем равновеликим квадрантам первого этапа разбиения (рисунок 3a) ставятся в соответствие дочерние узлы первого уровня. В показанном на рисунках частном случае северо-западный NW -квадрант обозначен белым квадратом, а остальные три - серыми кругами (рисунок 4). На очередно этапе серые квадранты снова подвергаются разбиению (на рисунке 3b для простоты показано лишь разбиение SW -квадранта). Как видно по рисунку 3b SW -квадрант на этом этапе содержит два белых, один черный и один серый подквадранты. Они представлены в дереве на рисунке 4. узлами второго уровня. Единственный серый квадрант снова разбивается. В данном случае это разбиение является последним, т.к. ни один из получившихся в результате подквадрантов не оказался серым (один белый и три черных). Подобным же образом обрабатываются и остальные квадранты изображения всех уровней. Окончательный вид квадродерева показан на рисунке 4.

Рис. 4: Окончательный вид квадродерева

 

Burroughs (1986) и Samet (1990) также упоминают о том, что квадродерево полезно при изменении разрешения объекта. Рассмотрим, например, квародерево на рисунке 4, которое представляет изображение, приведенное на рисунке 1.a. Если мы хотим изменить разрешение этого изображения, нам необходимо просто заменить все серые узлы второго уровня на черные узлы. Результатом будет новое изображение, показанное на рисунке 5.

Рис. 5: Изображение с измененным при помощи квадродерева разрешением

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

 

6. Недостатки квадродерева

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

Алгоритмы поворота квадротомированного изображения ограничиваются лишь поворотами на углы, кратные 90 градусам. Повороты на любые другие углы невозможны.

Хотя квадродеревья имеют массу плюсов в ГИС-приложениях, их распространение в других областях сдерживается их недостатками. Большинство проблем связано именно с тем, что при повороте изображения для него приходится заново перестраивать квадродерево. При этом сопоставление квадродеревьев исходного и повернутого