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. Разбиение должно быть бесконечно разложимо во все более и более мелкие узоры, т.е., должно выполняться правило более высокого разрешения.


 

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

5865. Роль цен, тарифов, льгот, субсидий, компенсаций в регулировании национального рынка 183 KB
  Происходящие изменения в экономике РФ обусловлены переходом на рыночные связи и отношения. Чтобы свести к минимуму предполагаемые потери при переходе к рынку, необходимо познать сущность и закономерности его развития. Все современные эконом...
5866. Технология разработки, перемещения и уплотнения грунта с элементами бетонирования 395.5 KB
  Определение объемов земляных работ по вариантам Для одиночных стаканных фундаментов возможны два вида земляных сооружений: - траншея по ряду фундаментов - котлован 3.1. Траншея по ряду фундаментов Отметка подошвы фундамента: м, где - абсолютная...
5867. История АМО ЗИЛ 42.5 KB
  Завод, основанный в 1916 г. как частное предприятие, через два года был национализирован, а спустя три четверти века, в 1992 г., вновь становится частным предприятием. В 1996 г. завод перешел практически в муниципальную собственность, сохранив форму...
5868. Место и роль монополии на рынке 103 KB
  Введение: формирование монополии Абсолютная (чистая) монополия - редкое для хозяйственной практики явление. Однако довольно часто приходится сталкиваться с монопольным влиянием, более реальными рыночными структурами монополистической конк...
5869. Взгляды Советских вождей на управление 97.5 KB
  За время существования СССР потерпело много реформ и преобразований. При разных правителях ситуация в СССР была совершенно разная т.к. у каждого из них были разные взгляды на жизнь и на управление страной. Скорее всего каждый из них руково...
5870. Воздействие ценовой дискриминации на экономическое благосостояние 237 KB
  Термин дискриминация образован от латинского discriminatio, что означает различие, различение. Под ценовой дискриминацией понимают практику установления разных цен на один и тот же товар при условии, что различия в ценах не связаны с затра...
5871. Организация защиты личного состава формирований ГО и РСЧС при проведении АСДНР 121 KB
  Организация защиты личного состава формирований ГО и РСЧС при проведении АСДНР Учебные цели: 1. Изучить основные мероприятия, осуществляемые руководителями (командирами) формированиям ГО и РСЧС по организации обеспечения защиты личного состава...
5872. Формальные методы спецификации программ 431.5 KB
  В предлагаемом учебном пособии рассматриваются два основных метода формального описания программных систем: метод алгебраических спецификаций и метод типизированных машин абстрактных состояний. Первый метод предназначен для описания статических аспе...
5873. Асинхронная машина. Общие понятия 1.07 MB
  Асинхронная машина. Общие понятия. Асинхронная машина это электрическая машина переменного тока, частота вращения ротора которой отличается от частоты вращения основной гармонической магнитного поля воздушного зазора. Частота вращения основной гармо...