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


 

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

23301. Байрон. Еволюція творчості 24.95 KB
  Байронізм. Поема Манфред Байронічна течі байронізм не прийняття дійсності відторгнення. Мазепа Цікавою особливо для українського читача є романтична поема Мазепа останній з творів про сильну особистість байронічного типу.
23302. Історія української культури 22.5 KB
  Українська наука та національна культура. Народна культура та її матеріальні і духовні складові та їх елементи. Культура і побут населення України 1. розвитку і представлений кількома історикогеографічними регіонами: Полісся та Волинь Волинська Рівненська Житомирська Чернігівська частина Київської та Сумської областей Карпати Львівська ІваноФранківська Закарпатська Чернівецька області Поділля Хмельницька Рівненська частина Житомирської областей Наддніпрянська Україна або середина Подніпровя Черкаська Кіровоградська...
23303. Культурно-мистецьке життя Київської держави 26 KB
  Запровадження християнства Образотворче мистецтво Київської держави архітектура Літературний процес Київської держави Література: 1. Перша стадія Київської держави умовно поділяється на два великих етапи згідно з археологічними розкопками та літописами: VIII початок ІХ ст. про хрещення Київської держави за князя Аскольда.
23304. Культурно-мистецьке життя Київської держави. Літературний процес 16 KB
  Літературний процес Традиції писемності давніх словян зокрема давньословянських племен Київської держави повязані з писемністю цивілізацій Давнього Світу свідченням чого є написи малюнковозвукового письма у кургані €œКамяна Могила€ у Запорізькії області в якій відображена історична самосвідомість зокрема уявлення про те як вони з Індії з Месопотамії прийшли до Карпат. Отже на території Київської держави існували цивілізації при чому в ІХХ ст. Літературні памятки Київської держави умовно поділяються на: Перекладна література:...
23306. Етномовні макроспільності первісності - загальна хар-ка; індоєвропейська родина 19 KB
  Ностратична макроспільнота Ескалеутська родина екімоси алеути мови народів Півночі Алтайська родина тюркська татарська узбецька киргизька туркменська турецька монгольська бурятська калмицька Уральські мови фіноугорські мови та діалекти Дравідійська родина еламська протоіранська Картвельська грузинська та діалекти народів Закавказзя Індоєвропейська 12 мов та мовних груп: 1. індоіранські давньоіндійські мови зокрема мова Вед санскрит давньоіранські мови Авести 3. тохарські мови 7. альбанські мови 8.
23307. Археологічні культури первісності на території України 18.5 KB
  ; €œІсторія української культури€ т. 1 Основні етапи розвитку матеріальної та духовної культури первісного суспільства на території України 1. Головним обєктом дослідження історії первісних суспільств зокрема на території України є так звані археологічні культури група або декілька груп чи комплексів груп матеріальних викопних археологічних знахідок які харся трьома спільностями: спільність території поширення цих памяток часу або хронологічного періоду поширення технології виготовлення 1 знаряддя праці з природних та штучних...
23308. Культурно-мистецьке життя Галицько-Волинського князівства 15 KB
  життя ГВК літературни процес образотворче мистецтво та архітектура ГВК 1 Впродовж другої половини ХІІІ ст. процеси давньоукраїнського державотворення переміщується на західноукраїнські землі де галицькі князі Роман Мстиславич і його син Данило Галицький створили ГВК. Протяго майже 40 років Данило Романович обєднав етнічні українські землі у складі ГВК. ГВК втратило політичну незалежність і було поділено між Польським та Угорським королівствами.
23309. ІУК як наукова дисципліна 26.5 KB
  Розвиток ІУК в ХХ ст. Важливий внесок у становлення ІУК як науки про культуру протягом ХІХ ст. зробили: вихованці та викладачі внз Харківський Київський університети науковці з академічних установ Росія АвстроУгорщина Німеччниа Франція представники різних державних і громадських наукових товариств ІсторикоФілологічне Товариство Харківський унт КАК Київська археографічна комісія Південнозахідний відділ РГТ Російське географічне товариство комісій КАК обєдання наковців та окремі дослідники Основними напрямами...