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


 

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

37417. Пифагор и «Пифагорейский союз» 76 KB
  политический союз пифагорейцев перестал существовать. Верования пифагорейцев как и орфиков касались души и метемпсихоза и по своему содержанию были далеки от ионийской философии. Это верование орфиков и пифагорейцев возникло из их убежденности в совершенстве разнообразии потенций и устойчивости души придающей крепость тленному и легко уничтожимому телу. Это была характерная для пифагорейцев и не только для них попытка объяснить почему душа находится в вынужденной связи с телом.
37418. Расчет параметров линейной непрерывной акустической антенны 1.16 MB
  Выбор конструкции антенны. Таким образом гидроакустические антенны могут рассматриваться либо как передающие либо как приемные устройства в зависимости от удобства их рассмотрения в каждом конкретном случае. Формируемые элементами антенны пространственновременные выборки значений поля представляют ту первичную информацию использование которой позволяет найти оценки параметров сигнала.
37419. Организация управления воздушным движением в районе аэродрома 1.31 MB
  Инструкция по производству полетов ИПП Общие положения ИПП аэродрома Кишинев разработана на основании Воздушного кодекса РФ Федеральных правил использования воздушного пространства РФ Федеральных авиационных правил полетов в воздушном пространстве РФ Федеральных авиационных правил Подготовка и выполнение полетов в гражданской авиации РФ Федеральных авиационных правил Организация воздушного движения в РФ Федеральных авиационных правил Осуществление радиосвязи в воздушном пространстве РФ Положения об оперативных органах о...
37420. Предмет философии 78.5 KB
  Предмет философии. Основная проблема: соотношение философии и науки по предмету. Цель: определить предмет философии как отношение человека к миру так что аспекты этого отношения онтологический гносеологический и аксиологический определяют основные разделы философии а философия рассматривается как теоретическое мировоззрение. Множество определений философии.
37421. ПОЛИТОЛОГИЯ. КУРС ЛЕКЦИЙ 718.5 KB
  Методология политической науки. 2 1 2 Власть в политике Природа и сущность политической власти. Субъекты политики и ресурсы власти 2 1 3 Политические системы общества Сущность структура и функции политической системы. 2 6 Выборы и избирательный процесс Роль выборов в политической жизни общества.
37422. Модель: оцінка наявної ситуації та впливу чинників ринку на розвиток системи або її суб’єкта 206.99 KB
  Повільність та негаразди пов’язані з цим процесом можна пояснити тим що більшість підприємців та полісімейкерів особи що приймають політичні рішення не усвідомлюють того що кожний суб’єкт ринку взаємопов’язаний з будьяким іншим а отже має вплив фактично на всю ринкову систему. Які б не були думки з цього приводу дуже велику роль в економічних системах відіграють закони ринку зокрема їх математичне вираження. Таким чином завданням моделі що ми її будемо будувати є оцінка наявної ситуації та впливу чинників ринку на розвиток системи...
37423. Автоматизированное рабочее место оператора автоматизированного переговорного пункта и информационной системы 286.94 KB
  Междугородная телефонная связь должна работать четко, бесперебойно. Работники междугородной телефонной связи на основе сознательного, рыночного отношения 'к труду и строгой производственной дисциплины должны культурно и внимательно обслуживать государственные учреждения и предприятия, общественные организации и население Украины.
37425. Влияние инфляционных процессов на результаты финансовой деятельности предприятия и на уровень жизни населения РФ 335.5 KB
  Денежная масса в обращении достигала 496 квинтиллионов марок а денежная единица обесценилась в триллион раз. Невозможно найти серьёзного учёногоэкономиста который считал бы систематический рост цен безобидным явлением. Опережающий рост цен на товары независимо от длинны инфляционной волны представляет собой крайне болезненный процесс для любого даже высокоразвитого нацио нального хозяйственного комплекса[15] . В настоящее время инфляция один из самых опасных процессов негативно воздействующих на финансы денежную и...