13008

Методи організації баз картографічних даних в геоінформаційних системах реального часу

Лекция

Информатика, кибернетика и программирование

Лекция №2.3. Методи організації баз картографічних даних в геоінформаційних системах реального часу. План Логічна й фізична організація баз графічних даних. Структура баз картографічних даних на основі квадротомічних дерев. 1. Логическая и физиче...

Украинкский

2013-05-07

61.5 KB

1 чел.

Лекция №2.3.

Методи організації баз картографічних даних в геоінформаційних системах реального часу.

План

  1.  Логічна й фізична організація баз графічних даних.
  2.  Структура баз картографічних даних на основі квадротомічних дерев.

1. Логическая и физическая организация баз графических данных

 

Итак, исходными данными для логического проектирования БКД являются разработанные инфологическая модель картографических данных и множество запросов к КБД, каждому из которых ставится в соответствие некоторое значение приоритета выполнения и требование к времени его реализациии. На этом шаге проектирования в рассмотрение включаются спецификации используемой СУБД, а инфологическая структура преобразуется в СУБД-ориентированную логическую структуру базы данных. Здесь особое внимание следует уделить ограничениям на содержимое записей и тому, где могут быть определены точки входа.

Установлено, что не существует особой организации базы данных, предназначенной только для машинной графики или СОИ в АСУ. Основную роль при выборе типа модели организации графических данных и метода управления файлами играют скорее особенности приложений, в которых БГД применяется в качестве инструмента. Хорошо известные иерархическая, реляционная и сетевая модели данных, как наиболее общие и мощные методы, применимы и в этой области. Однако было бы ошибкой предлагать одну из этих моделей как стандартную систему для машинной графики. Мощь и гибкость такой универсальной системы могут оказаться излишними и обременительными для многих приложений, потребности которых полностью удовлетворяются базами данных с более простыми структурами.

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

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

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

Преобразование информационной структуры, изображенной на рис. 2.9, в реляционную модель потребует нормализации отношений, т. е. дублирования данных для поддержания взаимосвязей между записями. Нерациональное использование памяти может привести к снижению производительности СУБД.

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

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

Иногда после объединения представлений многих пользователей в интегрированную структуру базы данных, учитывающую требования концептуальной модели и специфику обработки запросов, может оказаться целесообразным формирование нескольких баз данных, т. е. выбрать наиболее эффективную конфигурацию баз данных или файлов. Например, в КБД можно отдельно выделить тематическую и пространственно-графическую базу данных. При этом декомпозиция, во-первых, позволит резко уменьшить объем обрабатываемой информации при построении изображения за счет замены связи РОТОGO на РОGO; во-вторых, обеспечит более эффективное использование ресурсов ЭВМ (время и объемы памяти); в-третьих, позволит более полно удовлетворить информационные и временные требования пользователей и, наконец, создаст предпосылки для применения многопроцессорной обработки данных и для повышения качества работы КБД.

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

  •  формирование обобщенной сетевой модели, в которой не учитываются ограничения, накладываемые используемой СУБД;
  •  трансформация обобщенной сетевой модели с учетом ограничений, накладываемых конкретной СУБД;
  •  модификация трансформированной модели с учетом «очевидных» соображений, влияющих на производительность.

Основными компонентами сетевой модели данных являются записи и наборы. Типы записей на графической диаграмме БД представляются прямоугольниками. Типы наборов используются для представления типов связей между записями и изображаются поименованными дугами. Тип записи, из которого исходит дуга, называют владельцем набора, а тип записи, к которому направлена дуга, — членом набора. Тип набора представляет собой логическую связь «один ко многим» между владельцем набора и членами набора. Отметим, что связи определяют возможные пути доступа к данным, хотя на практике не обязательно реализовывать все связи как пути доступа. Тогда результат преобразования концептуальной модели в логическую, основанную на сетевой модели данных, может быть представлен рис. 2.9. Здесь названия типов записей написаны над прямоугольниками диаграммы, внутри которых указаны основные элементы данных и агрегаты данных, входящие в запись.

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

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

2. Структура баз картографических данных ГИС ОВ на основе квадратомических деревьев

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

Вспомним классический  пример,  когда база данных содержит карту контуров в 50-метровых интервалах высоты и карту урожайности пшеницы. Необходимо определить все области между уровнями высоты от 300 до 500 м, где растет зерно, затрачивая при этом минимальные ресурсы. Здесь традиционные подходы определения граничных точек для выявления искомых областей являются весьма неэффективными. Напротив, в случае организации иерархических баз географических данных в виде квадратомического дерева областей, анализ сводится к операции пересечения двух карт, что допускает удаление больших массивов данных из рассмотрения и, что в свою очередь, ведет к значительной экономии вычислительных ресурсов и обеспечивает быстрый поиск и отображение нужной картографической информации.    

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

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

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

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

     Рассмотрим представление изображения с помощью применения принципа квадратомического дерева, показанного на рис. 2.11.

Область, показанная на рис. 2.11a, которая представлена двоичным массивом размерностью 8 на 8, рис. 2.11b, единицы соответствуют элементам изображения внутри области, а нули соответствуют элементам изображения, находящимся вне области. Двоичный массив на рис. 2.11 представлен блоками, рис. 2.11c, а его отображение в виде  квадратомического дерева  показано на рис. 2.11d. Как видно из этого рисунка иерархическая структура данных об изображении представляется деревом степени 4, т.е. каждый нелистовой узел имеет четырех потомков. Каждый потомок узла представляет квадрант области, на рис.2.11d, они отмечены как NW, NE, SW, SEd. Листовые узлы дерева соответствуют тем блокам, для которых никакое дальнейшее деление становится невозможным. Вершина считается ЧЕРНОЙ или БЕЛОЙ в зависимости от того, находится ли соответствующий блок полностью внутри или полностью вне рассматриваемой области.

КРАЙ изображения – это внешний край квадрата, соответствующего массиву. Два пикселя считаются 4-смежными, если они смежные друг к другу в горизонтальных или вертикальных направлениях. Если имеет место смежность в угле (т.е. диагональная смежность), то пиксели считаются 8-смежными.

ЧЕРНАЯ ОБЛАСТЬ – это максимальный 4-связный набор ЧЕРНЫХ пикселей, т.е. набор S такой, что для любых пикселей p,q из S существует последовательность пикселей =, ,…, в S такая, что 4-смежен к, причем 0<i<n.

БЕЛАЯ ОБЛАСТЬ – это максимальный восьмисвязный набор БЕЛЫХ пикселей, который определен аналогично. Считается, что пиксель имеет четыре грани, каждая из которых имеет единичную длину. Граница ЧЕРНОЙ ОБЛАСТИ состоит из набора граней пикселей, непосредственно её составляющих, которые также являются гранями БЕЛЫХ пикселей.

Аналогичная формулировка применима и для блоков. Если изображение представлено полутоновым, то вводится понятие уровней СЕРОГО. Это понятие  может  распространяться  на  узел, так  все  не   листовые  узлы  на  рис. 2.11 считаются СЕРЫМИ.

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

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

Например, рис. 2.12 b, с, и d показывает результаты последовательного применения объединения, разбиения, и группировки к начальной декомпозиции изображения представленного на рис. 2.12a. В этом случае, изображение первоначально разбивается на 16 равновеликих квадратных блоков. Затем, «объединяющий» шаг пытается формировать блоки побольше, рекурсивно объединяя группы из четырех гомогенных «братьев» (например, четыре блока в NW и SE квадрантах на рис. 2.11b). Шаг «расщепляющий» рекурсивно разбивает блоки, которые не гомогенны: например, NE и SW квадранты на рис. 2.11c. В заключение, «группирующий» шаг объединяет все гомогенные 4-смежные ЧЕРНЫЕ блоки в одну область; 8-смежные БЕЛЫЕ блоки аналогично объединяются в БЕЛЫЕ области.

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

Будем полагать, что наша область – это 2n на 2n бинарное изображение с 1 или ЧЕРНЫМ, и 0 или БЕЛЫМ, рис. 2.11. Здесь основной принцип разбиения заключается в том, что любая плоская декомпозиция, необходимая для представления изображения в виде квадратомического дерева, должна иметь следующие два свойства:

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

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


 

А также другие работы, которые могут Вас заинтересовать

34653. Введение в теорию графов 56 KB
  Граф – это множество вершин V и множество ребер(дуг) Е. Вершины графа - объекты любой природы; поскольку их должно быть конечное число, то мы будем обозначать их натуральными числами. Ребра (дуги) графа соединяют некоторые из его вершин. Если ребра имеют направление, то граф называется ориентированным (орграфом) – рисунок А; в противном случае он неориентированный.
34654. Технологический цикл обработки информации на компьютере 49.5 KB
  Также стадия разработки может отражать количество реализованных функций запланированных для определённой версии программы. Также так называются программы не вышедшие еще в стадию альфа или бета но прошедшие стадию разработки для первичной оценки функциональных возможностей в действии. В отличие от альфа и бета версий преальфа может включать в себя не весь спектр функциональных возможностей программы. В этом случае подразумеваются все действия выполняемые во время проектирования и разработки программы вплоть до тестирования.
34655. Условный оператор. Оператор выбора 50.5 KB
  Например вычисление квадратного корня из числа проводится при условии =0 операторами: IF =0 Then b := Sqrt Else begin WriteLn' 0'; Redln; Hlt end; Оператор Hlt прекращает выполнение программы. PROGRM VES; { определение весовой категории спортсмена } Условная схема программы CONST 1='легкая категория'; 2='средняя категория'; 3='тяжелая категория';...
34656. Операторы организации циклов 57 KB
  Операторы ограничения и прерывания цикла Цикл с параметром Оператор цикла применяется при выполнении расчетов или других действий повторяющихся определенное количество раз. Оператор имеет вид: For i:= N1 To N2 Do оператор ; либо For i:= N1 DownTo N2 Do оператор ; Здесь i параметр цикла переменная порядкового типа N1 N2 начальное и конечное значения параметра цикла i. Напомним что оператор может иметь вид: Begin операторы end; Схема выполнения оператора цикла с параметром имеет вид: В случае связки To цикл...
34657. Стандартные процедуры и функции модуля CRT 54 KB
  Текстовый вывод на экран Процедура TextModeMode: Word;. Процедура TextColorColor: Byte Определяет цвет выводимых символов. Процедура TextBckgroundColor: Byte; Определяет цвет фона. Единственным параметром обращения к этим процедурам должно быть выражение типа Byte задающее код нужного цвета.
34658. Основы визуального программирования. Пустая форма и ее модификация. Компоненты страницы Standart 5.01 MB
  Если это свойство равно true то окно будет прозрачным. Степень прозрачности задаётся через свойство lphBlendVlue. nchors Это свойство есть и у формы и у компонентов. Это свойство раскрывающееся.
34659. Графические возможности Delphi, система координат 407.3 KB
  Методы вывода графических примитивов рассматривают свойство Cnvs как некоторую поверхность на которой можно рисовать. Координаты области вывода Метод построения графического примитива в общем случае имеет следующий синтаксис...
34660. Динамические структуры данных. Стеки, очереди. Списки. Бинарные деревья 178.5 KB
  При создании дерева вызывается рекурсивная процедура следующего вида: procedure Insertvr Root: TTree; X: T; { Дополнительная процедура создающая и инициализирующая новый узел } procedure CreteNodevr p: TTree; n: T; begin Newp; p^.Right := nil end; begin if Root = nil Then CreteNodeRoot X { создаем новый узел дерева } else with Root^ do begin if vlue X then InsertRight X else if vlue X Then InsertLeft X else { Действия производимые в случае повторного...
34661. Доступ к системным ресурсам. Определение переменной как Absolute. Предопределенные массивы MEM. Прерывания. Обработка прерываний 66 KB
  Прерывания. Прерывания Прерывание это особое состояние вычислительного процесса. В момент прерывания нарушается нормальный порядок выполнения команд программы и управление передается специальной процедуре которая входит в состав ДОС и называется процедурой обработки прерывания. В архитектуре центрального процессора ПК предусмотрены прерывания двух типов аппаратные и программные.