автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Растровые модели и алгоритм визуализации пространственных данных в системах мониторинга природных и техногенных катастроф

На правах рукописи

Белов Александр Владимирович

РАСТРОВЫЕ МОДЕЛИ И АЛГОРИТМ ВИЗУАЛИЗАЦИИ ПРОСТРАНСТВЕННЫХ ДАННЫХ В СИСТЕМАХ МОНИТОРИНГА ПРИРОДНЫХ И ТЕХНОГЕННЫХ КАТАСТРОФ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (технические и медицинские системы)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Курск-2013

I О ИЮН 2013

005062084

Работа выполнена в Юго-Западном государственном университете на кафедре программного обеспечения вычислительной техники.

Научный руководитель: доктор технических наук, профессор

Атакищев Олег Игоревич

Официальные оппоненты:

Филист Сергей Алексеевич доктор технических наук, профессор, Юго-Западный государственный университет, профессор кафедры биомедицинской инженерии

Пихлап Сергей Викторович кандидат технических наук, Научно-исследовательский центр (г.Курск) ФГУП «18 ЦНИИ» МО РФ, ведущей научный сотрудник

Ведущая организация: Госуниверситет - учебно-научно-

производственный комплекс, г. Орёл

Защита диссертации состоится 24 июня 2013 года в 15-00 часов в конференц-зале на заседании диссертационного совета Д 212.105.03 при Юго-Западном государственном университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94.

С диссертацией можно ознакомиться в библиотеке Юго-Западного государственного университета.

Автореферат разослан 23 мая 2012 г.

Ученый секретарь

диссертационного совета Д 212.105.03

Милостная Наталья Анатольевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Повышение оперативности функционирования системы мониторинга, повышает оперативность функционирования системы управления рисками природным и техногенных катастроф, в состав которой входит система мониторинга.

Диссертационная работа выполнена в рамках федеральной целевой программы «Снижение риска и уменьшение последствий природных и техногенных катастроф» по теме НИР «Методы и модели создания информационно-аналитических систем мониторинга и прогнозирования рисков возникновения природных и техногенных катастроф на основе геоинформационных технологий», номер гос.регистрации 1.61.10 ГК № П 519 от 14.05.2010 Минобрнауки России.

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

Задачи, решение которых необходимо для достижения поставленной цели:

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

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

- разработка алгоритма визуализации пространственных данных в системах мониторинга природных и техногенных катастроф и оценка вариантов его реализации на основании различных растровых моделей по показателю оперативности его выполнения;

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

Объект исследования. Подсистема хранения, передачи и обработки пространственных данных в системах мониторинга природных и техногенных катастроф, построенных на основе геоинформационных технологий.

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

Соответствие паспорту научной специальности. Содержание диссертации соответствует п.5 «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации» и п. 12 «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальности 05.13.01 - Системный анализ, управление и обработка информации.

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

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

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

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

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

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

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

Результаты работы использованы: в учебном процессе Юго-Западного государственного университета на кафедре программного обеспечения вычислительной техники при обучении студентов по направлению магистерской подготовки 231000.68 «Программная инженерия» в дисциплине «Пространственные базы данных» и в научно-исследовательской работе кафедры по теме «Методы и модели создания информационно-аналитических систем мониторинга и прогнозирования рисков возникновения природных и техногенных катастроф на основе геоинформационных технологий», в ООО «Научно-финансовый центр «ЦЕНТР КАПИТАЛ», ООО «МеталлЭксперт», что подтверждено соответствующими актами.

Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на научно-технических конференциях: IX, X Международных конференциях «Распознавание» (Курск, 2010, 2012 гг.); Международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике - КЛИН - 2006» (Ульяновск, 2006 г.); IV Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно временных сигналов» (Пенза, 2006 г.); Международной научно-технической конференции «Современные информационные технологии» (Пенза, 2010, 2011 гг.) и научно-технических семинарах кафедры программного обеспечения вычислительной техники Юго-Западного государственного университета (2010-2012 гг.).

Публикации. Самостоятельно и в соавторстве по теме диссертации опубликовано 14 научных работ, в том числе 6 статей в рецензируемых научных журналах и два свидетельства о регистрации программы для ЭВМ.

Личный вклад автора. Все научные результаты диссертационного исследования получены автором лично. В основных научных работах по теме диссертации, опубликованных в соавторстве и приведенных в конце автореферата, личный вклад соискателя состоит в следующем: в [1] предложена модель представления

пространственных данных, основанная на декомпозиции квадродеревьев на адресную и содержательную части; в [2] предложена модель представления пространственных данных, основанная на агрегации содержательных частей данных отдельных объектов в единую содержательную часть; в [3] разработаны запросы на языке SQL для реализации основных процедур визуализации пространственных данных; в [8] написана процедура получения линейного квадродерева по фрагменту цветного изображения; в [10] разработана процедура определения пересечения двух фрагментов, представленных в виде квадродеревьев; в [13] разработана модифицированная структура записи для линейных квадродеревьев в модели представления пространственных данных.

Структура н объем работы. Диссертация состоит из введения, четырех разделов, заключения, библиографического списка, включающего 59 отечественных и 42 зарубежных наименований и приложений. Работа изложена на 154 страницах машинописного текста, содержит 52 рисунка и 5 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Системой, которая оказывает существенное влияние на показатели оперативности и емкости требуемой памяти исследованных систем мониторинга, является система представления пространственных данных.

Для представления пространственных данных используются два типа растровых моделей. Одна с использованием минимальных ограничивающих прямоугольников и хранением данных, связанных с отдельным идентифицируемым элементом объекта мониторинга, в бинарных blob {binary large object) файлах. В диссертационной работе она обозначена как модель типа mbr (minimum bounding rectangle). Вторая с использованием отношений Пеано, построенных на основании линейных квадродеревьев. В диссертационной работе она обозначена как модель типа рг.

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

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

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

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

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

Растровые модели в виде системы отношений обозначены как: cr, ere, qcr. Они определены следующим образом:

[r{Id,L\ r{BCd, Lev, Id),

r(BCd, ECd,Id), qcr r(Cd,Cl)

K/£U)' r{ld,L),

r(BCd,ECd,ld\

r(BCd,Lev,D), r(Cl).

r(BCd,ECd,D), r{Cl)

В состав моделей входят перечисленные ниже элементы:

1. Множество идентификаторов элементов, составляющих объект мониторинга, Id = {id\ide [1,2,...,им]}, где пы-количество всех идентификаторов.

2. Множество идентификаторов тематических слоев элементов объекта мониторинга/, = {/|/е [1,2...,и^]}, где nL -количество всех тематических слоев.

3. Атрибутивное пространство элементов объекта мониторинга

С/ = {(с/1;с/2,... ,clm) | с/[ е С/, = dom(cl\),cl2 е С/2 = dom(cí7),..., с/„, е Cl„, =dom(clm)}, где каждое из Cl¡ представляет собой домен определенного типа. Частным случаем атрибутивного пространства является трехмерное цветовое пространство в системе RGB, где С/ = {(г,g,b)\ re R = [0,1,...,255],ge G = [0,1,...,255],be В = [0,1,...,255]}.

4. Одномерное дискретное координатное пространство

Cd = {cd | cde [0,1,..„г2" -1], cd = fE¡cd(x,y)}, где E = {(x,y) \ xe [0,1,...,2" -1],

ye [0,1,..„2" -1]} - двумерное дискретное координатное Евклидово пространство.

5. Отображение fE C<¡ : £Cd, которое при трансформации одномерного пространства в двумерное на основании кривой Лебега, определяется равенством cd<2> = Уп-\хп-\ - УкЧ - Уохо •

Отображение Íec<¡ основано на квадротомическом делении двумерного пространства Е на основе квадродерева с обходом его вершин в глубину.

Построение моделей сг ,сгс и qcr осуществлено следующим образом.

В качестве исходной модели рассматривается отношение г(Е,Ы,Ь,С1), соответствующее определению пространственных данных по ГОСТ Р 52438-2005 «Географические информационные системы. Термины и определения». Это отно-

шение на основании /Е С(1 трансформируется в г(Сс/,/с/, I, С/), которое декомпозируется в систему отношений

Отношение г(Е,М,С1), эквивалентное по объему г(С£>,/с/,С/), представляет модель пространственных данных, которая обозначена как модель яг.

С отношением г(Сс!,1с1,Ь,С1) и системой (1) связана система функциональных зависимостей / = {Сс/ Ы,С1;М Ь), которая фиксирует закономерности предметной области, содержащей пространственные объекты.

Снижение избыточности для представления пространственных данных осуществляется декомпозицией пары (г(Сс!,Ы,Ь,С1),/) на основании выполнения операции проекции с учетом ограничений, накладываемых функциональными зависимостями, в виде следующей последовательности процедур:

1. Декомпозиции пары (г(СУ,Л/,1,С7),/), на: (г(/с/,£),{/с/-»1}), (г(Сс/,С1),{Сс! -> С/}) и (г(Се/, ¡с/),{Сс1 -> Ы}).

2. Упорядочиванию г(Сс1,Ы) по значению сс1, формирующей зависимость ЯМ->Сс1 или ЯМ —» Сс/,1с!, где ЯМ- порядковый номер кортежа в отношении г{Сс1,Ы), полученном в результате упорядочивания. В результате чего получаются пара (г(СУ, Ы), {СУ -> Ы, ЯМ ->Сс/}).

3. Упорядочиванию г(Сс/,С/) по значению сс! с получением 0(Сс/, С/), {ЯМ -> Сс/, Сс1 —> ЯМ, С/}) и последующей ее декомпозицией на (г(Сс/),{Я№ —> Сс/, Сс! —» ЯМ}) и (#-(С/),{ДЛГ-»С/}).

В итоге получается система '(г(ВД, {Л/->!}), (г{Сс1, Ы), {СУ -> М, ЯМ -> Сс!}),

' (г(Сс!),{ЯМ —» Сс/}),

Эквивалентность системы (2) и пары (г(Сс/,/с/,£,С/),/) основывается на выполнении при декомпозиции условий теоремы Риссанена.

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

Для упорядоченного по значению сс/ отношения г(Сс/,/с/) определяется отношение эквивалентности его кортежей. Пусть /,уеЛЛГ, а /,=(«/,-,/с/,) и /у = (сс/у-, г'с/у): / -ый и у'-ый кортежи упорядоченного по коду сс1 отношения г(Сс1,1с1), тогда

г(С<1,М,С1).

(1)

Для упорядоченного по cd отношения r(Cd) отношение эквивалентности его кортежей определяется как t¡ = tj <=> cd¡ - i = cd¡ -j = d¡, где d¡ фиксирует величину разности между координатным кодом и номером кортежа. Для эквивалентных кортежей значение этой разницы одинаковое. Значения d¡ объединяются во множество D.

В упорядоченных по cd отношениях r(Cd,Id) или r(Cd) каждая из максимальных по количеству ne¡ кортежей последовательность t¡ =/;+1 = /,-+2 = ... = t¡+ne _| для отношения r(Cd,Id)заменяется одним кортежем ct¡=(bcd¡,ecd¡,id), а для отношения r(Cd) кортежем ct¡ = (bcd¡, ecd¡, d¡), где bcd¡ = cd¡, ecd¡ = cd¡+ne _¡. Таким образом отношение r{Cd,Id) трансформируется в r(BCd,ECd,Id), а отношение r(Cd) в отношение r(BCd,ECd,D), где BCd -объединение всех bcd¡, a ECd - объединение всех ecd¡, BCd,ECd cCrf.B итоге формируется система отношений сг, в которой кортежи отношений r(BCd,ECd,Id) и r{BCd,ECd,D) соответствуют отрезкам кривых, заполняющих пространство Cd. Система отношений сгс отличается от сг тем, что в ней используется не подвергнутое декомпозиции отношение r(Cd, CI).

При использовании для представления отношений квадрантов линейных квадродеревьев на значение я<?| накладывается ограничение

пе, = 4""', lev, = maх(сс/, mod 4le" = 0), lev, 6 [0,l)...,[log4|Ca'|']]

I'JVr

и последовательность эквивалентных кортежей заменяется одним кортежем, называемым квадрантом. Для r(Cd,ld) это будет ct¡ ={cd¡,lev¡,id,), а для r(Cd) это будет ctj={cdi,levi,di). Отсюда r(Cd,Id) трансформируется в r{BCd,Lev,Id), а r(Cd) в r(BCd,Lev,D), где Lev- объединение всех значений lev¡. В итоге формируется система qcr.

Особенностью систем сг, сгс, qcr является то, что отношения, полученные в результате сжатия методом группового кодирования, возможно использовать при обработке пространственных данных без их разжатия. Это доказывается тем, что: r(CdJd) эквивалентно r(BCd, ECd, Id) при cd = bcd = ecd или r{Cd,Id) эквивалентно r(BCd,Lev,Id) при cd = bcd &.lev = 0.

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

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

Пусть ve, ved, vbed, vecd, vid, vd,vlev,vcl - количество байт для представления атрибутов E,Cd, BCd, ECd, Id, D, Lev, Cl\ s- количество пикселей для пред-

ставления пространственных данных. При этом ve = ved = vbed = vecd = vd. Отсюда объем любого отношения рассчитывался как сумма байт атрибутов одного кортежа, умноженная на количество кортежей vk.

Для всех отношений, содержащих атрибут С/, vk = s. Для отношения r(BCd,ECd,Id) в наихудшем случае vk = s, а в наилучшем случае vk = 1. Для отношения r{BCd, ECd, D) в случае прямоугольных изображений vk ~ Г*.

Во всех моделях для осуществления анализа состояний с использованием запросов по координатам использовалось отношение r(Cd) или г(Е) с максимальным объемом ved ■ s. Для анализа с использованием запросов по пространственным атрибутам использовалось отношение r{Cl,SId) с максимальным объемом vcl-s . Атрибут Sid хранит идентификатор класса, определяющий тип или характеристики атрибутивных данных С/, используемых в запросе.

Для всех моделей учитывался объем индекса в виде В+ дерева по атрибуту отношения, равный количеству кортежей отношения, умноженному на сумму байт атрибута и указателя. Количество байт в указателе определялось значением ved. В модели сг для отношения r(Cl, Sid) строился индекс по RN и не строился индекс по D в отношении r{BCd,ECd,D).

Для всех моделей не учитывался объем отношения r(ld,L) из-за его малого влияния на окончательный результат.

В модели системы мониторинга mbr объем атрибутивных данных в blob файлов оценивался как r(cl) s. При этом не учитывались: перекрытие минимальных ограничивающих объекты прямоугольников, NULL значения, затраты на адресную часть и ее индексацию, что занижало оценку объема памяти для ее представления. Для реализации пространственных запросов по значениям пространственных атрибутов с/ и для возможности идентификации объектов при выполнении операций в растровой форме требовалось отношение r{E, Id, CI). Максимальный требуемый состав структур данных для модели mbr содержал: три отношения типа г(с/), два отношения r(E,Id,Cl), отношения r(Cl,SId) и г(Е); индексы по всем атрибутам: для одного отношения r(E,Id,Cl), отношений r{Cl,SId) и г(Е). Отсюда объем требуемой памяти рассчитывался как vmbr = (8vel + \0- ved + 3 ■ vid + vsid) ■ s.

Максимальный требуемый состав структур данных для модели sr определялся из того, что состояния объекта мониторинга хранились в отношениях типа r(E,Id,Cl). Отсюда объем памяти рассчитывался как vsr = (6 • vel +10 • ved + 3 ■ vid + vsid) ■ s.

Максимальный требуемый состав структур данных для модели рг определялся из того, что координатные данные объекта мониторинга хранились в отношении типа r(BCd, ECd, Id), а атрибутивные в отношениях типа r(BCd, ECd, CI). Максимальный требуемый состав структур данных для модели сгс определялся из того, что координатные данные объекта мониторинга хранились в отношении типа r{BCd, ECd, Id), а атрибутивные в отношениях типа r(Cd,Cl). Максимальный требуемый состав структур данных для модели сг определялся из того, что коорди-

натные данные объекта мониторинга хранились в отношении типа r(BCd,ECd,Id), а атрибутивные в отношениях типа r(BCd,ECd,D)n r(Cl).

Отсюда выражения для расчета объема памяти для моделей cr, ere и рг в наихудшем случае определялись как:

ver = (5 ■ vcl +14 ■ ved + 2 ■ vid + vsid) ■ s + (2 • ved + vd) ■ -Js, vere = (5 • vcl +15 ■ ved + 2 ■ vid + vsid) ■ s, vpr = (6 ■ vcl + 20 ■ ved + 2 • vid + vsid) ■ s , а в наилучшем случае как:

verc = (5 ■ vcl + 8 • ved + vsid) ■ s + 2 ■ vid + 7 • ved,

ver = (5 • vcl + 7 • ved + vsid) ■ s + (2 ■ ved + vd) ■ ~Js + 2 ■ vid + 7 • ved,

vpr = (6 ■ vcl +13 ■ ved + vsid) ■ s + 2 • vid + 7 • ved.

На рисунках 1 и 2 приведены графики отношения объемов памяти моделей систем мониторинга для наихудшего и наилучшего случаев в зависимости от изменения vcl от 8 до 256 байт при ved = 8 (байт), vid = 4 (байт), vsid =4 (байт). Выбор vcl как параметра обусловлен возможным использованием гиперспектральных снимков.

vcrc(vcl)

vcrdvcV)

v'STÍvd) vcrdvcl)

0.75-

байт

^_| байт

154

vcl \'с1

Рис. 1. Графики отношения объемов памяти моделей систем мониторинга в наихудшем случае

vprtvel) 1.5" vcrc( ve])

„ 1.25-f vmbitvcl)

vertí vcl) vsrtvcl)

- * '^W --n íTr

vpr(vcl) 1.5-p

VCI(VCI)

vmMvcl) 1-25 '

vCl^VCl) vsrtvcl)

-+-

4-

-+-

81 154 227 300

4-

-H

4

байт

о -1- .

154 227 300

ус1 Ус]

Рис. 2. Графики отношения объемов памяти моделей систем мониторинга в наилучшем случае

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

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

*t Г*.

iM**? *

.о*?

щш

ml

>■ J

fb г с' - i

, > ' ЩвШ

- - •• х ■ 1Ш

-^rv* -

Рис.3. Варианты объектов мониторинга В таблице 1 приведен объем требуемой памяти сравниваемых моделей для объектов мониторинга, приведенных на рисунке 3.

Таблица 1

Тип объекта ver (байт) vcrc (бант) vpr (байт) vsr (байт) vmbr (байт)

Сельская местность 8,009-107 8,645-107 1,249-108 1,152-108 1,376-Ю8

Промышленная зона 8,066 107 8,688-107 1,254-108 1,152-108 1,414-Ю8

Экспериментальные данные подтвердили корректность полученных граничных аналитических зависимостей. Установлено, что при реальных данных отношения объемов памяти близки к значениям, рассчитанным по аналитическим выражениям в наилучшем случае, с абсолютной погрешностью не более 0,1. При этом и для первого и для второго объекта мониторинга:

ЖUi,4; ^1 = 1,6; J5L = i,3;JPl = l,6; ^ = 1,7;^ = 1,4.

vcrc vcrc vcrc vcrc vcrc vcrc

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

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

Модели построены с использованием квадродерева (QT ) на основании обхода его вершин в ширину по уровням и состоят из:

1. Последовательности L =< us >< LKn >< Lei >, где us - тетрада или байт, хранящий максимальный номер уровня квадродерева; LKn- последовательность ко-

дов вершин QT при его обходе в ширину; Lei - последовательность значений атрибутов, которая в модели FBLQ отсутствует.

2. Системы кодирования вершин QT. Для BCQT это - система равенств {CI =< 1 >2,СВ =< 1 >2,СШ =< 0>2,СЖ =< 0 >2}; для MCQT - система равенств {С/ =< 1 >2,СВ1 =<01 >2,СВ =< 1 >2,CWI =< 00>2,CFF =< 0 >2}; для FBLQ - система равенств {С/ =< 1 >т,СВ1 =< 0 >2< код атрибута >2,С5 =< код атрибута >2,

CWI =< 0 >2< код ampu6yma>2,CW =< код атрибута >2}; где С/- внутренняя вершина QT ;СВ1 - внутренний лист QT квадранта используемых пикселей QT; СВ-терминальный лист QT используемого пикселя; CWI - внутренний лист QT квадранта неиспользуемых пикселей; CW - терминальный лист QT неиспользуемого пикселя.

3. Системы ограничений

J/0 = 0, /ж = (/,- + 5; + Wj)/A, В„ =Wn = 0, если п > 0, [1„ = 0, (Вп = 1 & Wn = 0) V (5„ = 0 &Wn = 1), если п = 0, определяемых структурой квадродерева, где IhBhWt - количество на /-ом уровне QT соответственно: внутренних вершин; листьев, соответствующих квадрантам с используемыми пикселями; листьев, соответствующих квадрантам с неиспользуемыми пикселями. Если QT такое, что все листья для используемых пикселей терминальные, то Bj = 0 для всех i > 0.

Для построения модели MCQT использовалась часть системы отношений модели qcr. Это отношение r(BCd,Lev,D), по которому строилось квадродерево QT , а по нему последовательность < LKn >, и отношение г{С1), из которого значения с/ в виде двоичного кода записывались в последовательность < Lei >.

Для построения модели BCQT использовалась часть системы (2). Это отношение r(Cd), по которому строилось квадродерево QT, а по нему последовательность < LKn > . И отношение г(С1), из которого значения el в виде двоичного кода записывались в последовательность < Lei >.

Для построения модели FBLQ использовалось отношения r(Cd, CI), по которому строилась последовательность < LKn > .

На рисунке 4 представлен пример трехуровневых квадродеревьев с кодами вершин для моделей BCQT, MCQT и FBLQ соответственно. Десятичными числами представлен код цвета из четырех бит, включающий код отсутствия значения в виде числа восемь.

Рис. 4. Трехуровневые квадродеревья для моделей BCQT , MCQT и FBLQ Аналитическое сравнение моделей проведено следующим образом.

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

Таблица 2

Модели Lewi LCBI ^св Lew

FBLQ 1 m+2 m + 2 m+1 m +1

BCQT 1 1 0 m +1 1

MCQT 1 2 2 + 4' • m m +1 1

Тогда количество бит, требуемое для пространственного объекта, представленного в виде QT, в любой модели рассчитывается по формуле

F = Ztf ' LCI + Bi' Lcbi + wi ■ Lcwi) + 5o ' LCB + Щ ■ Lcw .

/=1

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

Для всех моделей на основе программной генерации квадродеревьев для наихудшего (один используемый пиксель в квадранте единичного уровня ) и наилучшего (четыре используемых пикселя в квадранте единичного уровня) случаев их сжатия и по результатам программного расчета количества вершин /,, В,, Wj, / = 0,1,...п выведены зависимости требуемого объема данных от количества терминальных листьев используемых пикселей s = 2k, к = 0,1,... ,п. Так для модели MCQT в наихудшем случае сжатия требуемый объем данных в битах

LMCQT(2) =

и, +-

32 ■ 2 + 42/7 — 2\к-

44 i

32 ■ 2 + 84п — 42к -

+ т2к ,к - нечетное,

а в наилучшем случае сжатия \4п-1к + 4

HMCQT(2 ) =

г/г 4---\-т2 ,к -четное,

2

\4n-lk +11 -к . и н---\- т2 ,к — нечетное.

Графики отношений объемов данных для моделей МСОТ ,ВС0Т и в

наихудшем и наилучшем случаях в зависимости от количества передаваемых пикселей пространственных данных при и = 20,т = 64(бит) представлены на рисунке 5. Из них следует, что модели МСОТ и ВС^Г во всех случаях, отличных от наихудшего, эффективнее модели РВЬ<2.

ивсдт (») ялсег(а)

¿Д С£)7~м ¿л-/сег(1) о.1

нгв1.<}иь

НМСвТ(э)

шсдп*)«

пмсдть)2 ¿мсег(^) '■

Рис. 5. Графики отношений объемов данных для моделей МС0.Т , ВС()Т и РВЬ<2 При экспериментальном сравнении моделей исследовались два фрагмента одного изображения размером 1000*1000 пикселей, показанные на рисунке 6. Один фрагмент, состоящий из множества небольших сегментов, по размерам приближающихся к одному пикселю, соответствует по характеристикам наихудшему случаю. Другой фрагмент, состоящий из трех сегментов, соответствует по характеристикам наилучшему случаю.

¿1

%

Рис. 6. Изображение и его фрагменты для экспериментального сравнения В результате эксперимента получены следующие отношения:

= 1,6.

1всот ьмсдт нвсдт нмсот

Отсюда следует, что использование моделей ВСОТ и МСОТ позволило снизить при передаче объем данных от 1,2 до 1,6 раза по сравнению с моделью , в зависимости от формы фрагмента передаваемых данных о состоянии объекта мониторинга.

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

Рис. 7. Схема алгоритма визуализации пространственных данных в системах мониторинга природных и техногенных катастроф

Процедура обработки данных при изменении состояния объектов мониторинга состоит из последовательности действий: 1 .Удалить (архивировать отношения предыдущего состояния). 2. Переименовать отношения текущего состояния в отношения предыдущего состояние. 3. Преобразовать полученные новые данные в отношения нового текущего состояния. 4. Построить для отношений текущего состояния индексы по Cd и по С/. 5. Построить индексы для отношений г(Е) и r(CI,SId). Выполнение процедуры для конкретной модели зависит от состава отношений, входящих в ее состав.

Координатный запрос реализуется выполнением операции реляционной алгебры

r(E, Id, Cl) := r(E, Id, Cl) > < r(E), где содержимое отношения г(Е), определяющего координатную выборку, определяется пользователем в интерактивном режиме.

Запрос по пространственным атрибутам реализуется выполнением операции реляционной алгебры

r(E,Id,Cl,SId) := r(E,Id, Cl) >< r{Cl,Sid), где отношение r(CI,SId), содержащее классификатор для выборки, определяется пользователем в интерактивном режиме.

Запрос по непространственным атрибутам реализуется выполнением операции реляционной алгебры

r(E,Id,Cl) := r{E,Id,Cl)xr{Id), где отношение r(Id), содержащее идентификаторы объектов, выбранные по значениям непространственных атрибутов, заранее определяется пользователем при выполнении соответствующего запроса в интерактивном режиме.

Запрос по комбинации атрибутов в общем случае реализуется операцией реляционной алгебры

r(E,Id,Cl,SId)~((r(E,Id,a)><r(Id))><r(Cl,SId))><r(E) и содержит все три отношения г(Е), г(С/,SId) и r(Id).

Перечисленные выше операции реляционной алгебры определяют семантику выполняемого запроса и при реализации совпадают только с их реализацией в моделях sr и mbr. В моделях pr, сг,сгс и qcr данные операции модифицируются в зависимости от вида представления отношения r(E,Id,Cl).

Время выполнение запроса по комбинации атрибутов в сумме со временем выполнения процедуры обработки данных при изменении состояния объектов мониторинга определяет время реализации алгоритма визуализации.

Аналитическое сравнение вариантов реализации алгоритма в различных системах мониторинга по показателю оперативности произведено с использованием моделей расчета времени на его выполнение. Модели простроены следующим образом.

Для расчета оперативности использована принятая в теории баз данных модель, основанная на времени считывания и записи данных при обращении к внешней памяти с применением kb = tb/vb ,(сек/байт), где tb - время считывания одного блока (кластера) в файловой системе; vb- объем блока в байтах.

Считалось, что данные поступают в виде стандартного файла передачи данных с количеством пикселей s. Кроме того, для моделей mbr при расчете времени на построение пространственного индекса учитывалось только время считывания отношения, для которого строится индекс.

На основании этого время выполнения алгоритма визуализации при использовании сравниваемых моделей в наихудшем случае определялось выражениями: tcr = (10- vcl + 13- ved + 3 vsid + 2 ■ vid + vd) ■ s ■ kh, tmbr = (12 • vcl +16 ■ ved + S-vid + 3- vsid) -s-kb, tsr = (10- vcl + 13 -ved + 9- vid + 3-vsid+)-s-kb. tere = (10 • vcl +15 ■ ved + 3 • vsid + 3 • vid) ■s-kb, tpr = (12 • vcl + 24 • ved + 3 • vsid + 3 vid) ■s-kb, а в наилучшем случае определялось выражениями: tsr = (10 • vcl +13 • ved + 9 ■ vid + 3 ■ vsid+) -s-kb, tmbr = (12 • vcl +16 • ved + 8 ■ vid + 3 • vsid)-s ■ kb, tcr = (10- vcl +11- ved + 3 vsid + vid + vd) -s-kb, tere = (10- vcl + 15- ved + 3 • vsid + 2 ■ vid) ■s-kb, tpr = (12- vcl + 22 ■ ved + 3 • vsid + 2 • vid) -s-kb.

Результат сравнения моделей по оперативности выполнения алгоритма визуализации в наихудшем и наилучших случаях при значениях параметров, аналогичных приведенным во втором разделе, представлен на рисунках 8 и 9.

2.2

tsK vcl) 2.1

teit vcl) 2

——' 1.9

tmbr(vc!) 1.8

icrf vcl) 1.7

1.6

tpr< vcl) 1.5

tcitvcl) 1.4

tsr(vci) tcrc( vcl)

tmbr( vcl) tertf vcl)

tpr( vcl)

154 vcl

Рис. 8. Сравнение моделей по оперативности выполнения алгоритма визуализации

в наихудшем случае

2.2 1.64

lsr( vcl) 2.1 tsr(vcl) 159

Mvcl) 2 1.9 1 R Icrdvcl) 1.53

tmbr( vcl) tmbr(vcl) | Jt

tcr( vcl) 1.7 tcrc<vcl) 1.37

tpr( vcl) 1.6 1 í i. >P1 vcl) i ?7

M vcl) 1.4 tcrc(vcl) 121

1.3 ••.v.... ----- 1.16

1.2 1.1 1.11 « ^ 105 байт

154 vcl

Рис. 9. Сравнение моделей по оперативности выполнения алгоритма визуализации

в наилучшем случае

Анализ графиков показывает, что предлагаемые в диссертационной работе модели представления пространственных данных превосходят сравниваемые аналоги как минимум в 1,2 раза.

Процедуры алгоритма реализованы в виде запросов на языке SQL.

Реализация процедуры запроса по пространственным атрибутам основана на сегментации пространственных данных в интерактивном режиме. В этом случае оператор вручную задает на изображении область для выборки по образцу, то есть задает множество прецедентов в признаковом пространстве, относящихся к определенному классу и, тем самым, строит отношение r(Cl,SId), где Sid является идентификатором класса. Частным случаем признакового пространства может являться цветное пространства системы RGB. Для реализации данной возможности разработана процедура построения классификатора с использованием модели типа qcr и сг, в которых использовались кривые Лебега и Гильберта в трехмерном пространстве.

Экспериментальное сравнение вариантов реализации алгоритма визуализации проведено для пространственных данных при ved = 8 (байт), vid = 4 (байт), vsid = 4 (байт), ve/= 8 (байт) и представлено в таблице 3. Основная техническая характеристика вычислительных средств, использовавшихся при эксперименте, кь = 7,163• Ю-4/212 (сек/байт).

_ Таблица 3

Количество пикселей ter tere (mihi) tmbr (мин) tsr (мин) tpr (мин)

1000*800 26,9 (сек) 28,5 (сек) 37,5 (сек) 42,5 (сек) 40,9 (сек)

8192*8192 37,6 (мин) 39,9 (мин) 52,5 (мин) 59,5 (мин) 57,1 (мин)

_ tmbr , , tsr , . tpr , . tmbr , , ísr . , , tpr

При этом:-= 1,3;-= 1,5= 1,4;-= 1,5; — = 1,6; — = 1,4.

tere tere tere 1er ter ter

Отсюда следует, что использование моделей данных сгс и сг в алгоритме визуализации позволило повысить оперативность его реализации от 1,3 до 1,6 раз в зависимости от сравниваемой модели.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

В диссертационной работе получены следующие основные результаты:

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

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

композиции и метода группового кодирования, позволяющие снизить затраты памяти для своего представления и, тем самым, повысить эффективность системы мониторинга природных и техногенных катастроф по показателю затрат памяти в диапазоне от 1,3 до 1,7 раза по сравнению с существующими аналогами.

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых научных журналах и изданиях

1. Белов, A.B. Использование квадродеревьев в динамических электронных фотокартах [Текст]/ А.О. Атакищев, A.B. Белов, A.B. Николаев // Известия Юго-Западного государственного университета. - 2011. - №6(39). - 4.2. - С. 36 - 40.

2. Белов, A.B. Использование адресных и содержательных квадродеревьев для представления и отображения фрагментов изображения [Текст]/ О.И. Атакищев, A.B. Белов, В.Г. Белов // Наукоёмкие технологии. - 2012. - № 9. - С. 34 - 35.

3. Белов, A.B. Отображение графической и атрибутной информации фрагментов изображения, представленных линейными квадродеревьями, на основе операций реляционной алгебры [Текст]/ A.B. Белов, О.И. Атакищев // Наукоёмкие технологии. - 2012. - № 9. - С.52-55.

4. Белов, A.B. Формирование классификатора с нечеткими границами на основании кривых, заполняющих дискретное признаковое пространство [Текст]/ A.B. Белов// Известия Юго-Западного государственного университета. - 2012. -№6(39). - 4.2. - С. 36 - 40.

5. Белов, A.B. Передача и хранение фрагментов изображения дистанционного зондирования при помощи различных схем кодирования квадродеревьев. Часть 1. Схемы кодирования квадродеревьев [Текст]/ A.B. Белов // Телекоммуникации. - 2013. - №2. - С. 37 - 41.

6. Белов, A.B. Передача и хранение фрагментов изображения дистанционного зондирования при помощи различных схем кодирования квадродеревьев. Часть 2. Сравнительный аналитический и экспериментальный анализ схем коди-

10

рования квадродеревьев [Текст]/ A.B. Белов // Телекоммуникации. - 2013. - №3. -С.36 - 40.

Свидетельства о государственной регистрации программ для ЭВМ

7. Белов, A.B. Программа минимизации и анализа линейного квадродерева для представления фрагментов цветного изображения произвольной формы [Текст]/ A.B. Белов // Программа для ЭВМ № 2012613730; заявлено 28.02.2012, опубликовано 20.04.2012.

8. Белов, A.B. Программа взаимного преобразования фрагментов произвольной формы цветного изображения и линейного квадродерева [Текст]/ A.B. Белов, С .А. Хорошилов // Программа для ЭВМ № 2012616014; заявлено 18.05.2012, опубликовано 29.06.2012.

Статьи и материалы конференций

9. Белов, A.B. Внешняя и внутренняя структуры, предназначенные для представления пространственных данных в виде деревьев [Текст]/ A.B. Белов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: сб. материалов IX Междунар. конф. «Распознавание - 2010». - Курск: КурскГТУ, 2010. - С. 228-229.

10. Белов, A.B. Особенности выполнения пространственных запросов в ГИС с использованием квадродеревьев пространственных данных [Текст]/ A.B. Белов, О.И. Атакищев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: сб. материалов IX Междунар. конф. «Распознавание - 2010». - Курск: КурскГТУ, 2010. -С. 232-234.

11. Белов, A.B. Преобразование квадродерева пространственных данных ГИС в бинарное дерево [Текст]/ A.B. Белов // Современные информационные технологии: сборник статей международной научно-технической конференции. Пенза: Пензенская государственная технологическая академия, 2010, Вып. 11. С. 154156.

12. Белов, A.B. Представление квадродерева пространственных данных ГИС в виде цифровой последовательности [Текст]/ A.B. Белов// Современные информационные технологии: сборник статей международной научно-технической конференции. - Пенза: Пензенская государственная технологическая академия, 2011. -Вып. 13. — С.164-165.

13. Белов, A.B. Модифицированные линейные квадродеревья для представления фрагментов изображения [Текст]/ A.B. Белов, О.И. Атакищев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: сб. матер. X Междунар. науч.-тех. конф. «Распознавание - 2012». - Курск: ЮЗГУ, 2012. - С. 17-18.

14. Белов, A.B. Устройство отображения фрагментов изображения, представленных линейными квадродеревьями [Текст]/ A.B. Белов// Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: сб. матер. X Междунар. науч.-тех. конф. «Распознавание - 2012». - Курск: ЮЗГУ, 2012. - С. 232-233.

Подписано в печать 22.05.2013 г. Формат 60x84 1/16. Печатных листов 1,1. Тираж 100 экз. Заказ № 55. Отпечатано в ООО «Принт-Центр».

Юго-Западный государственный университет

На правах рукописи

Белов Александр Владимирович

04201360564

РАСТРОВЫЕ МОДЕЛИ И АЛГОРИТМ ВИЗУАЛИЗАЦИИ ПРОСТРАНСТВЕННЫХ ДАННЫХ В СИСТЕМАХ МОНИТОРИНГА ПРИРОДНЫХ И ТЕХНОГЕННЫХ КАТАСТРОФ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (технические и медицинские системы)

Диссертация на соискание ученой степени кандидата технических наук

Курск - 2013

•

> і - -1

Содержание

Введение 6

1 Постановка задачи диссертационного исследования 12

1.1 Системы мониторинга природных и техногенных катастроф.......................12

1.1.1 Природные, техногенные катастрофы и чрезвычайные ситуации..............12

1.1.2 Мониторинг и системы мониторинга.............................................................12

1.1.3 Задачи систем мониторинга............................................................................13

1.1.4 Виды и состав систем мониторинга...............................................................13

1.1.5 Требования к системам мониторинга.............................................................14

1.1.6 Применение методов дистанционного зондирования в системах мониторинга...............................................................................................................15

1.1.7 Пространственные данные и пространственные объекты в системах мониторинга...............................................................................................................16

1.1.8 Анализ и идентификация пространственных данных в системах мониторинга...............................................................................................................17

1.2 Растровые модели для хранения и обработки пространственных данных в

системах мониторинга..............................................................................................21

1.2.1 Существующие формы представления фрагментов пространственных данных произвольной области.................................................................................21

1.2.1.1 Представление фрагментов пространственных данных произвольной области в канонической форме................................................................................21

1.2.1.2 Представление объектов пространственных данных с использованием минимальных ограничивающих прямоугольников и бинарных файлов.............22

1.2.1.3 Представление фрагментов пространственных данных произвольной области с использованием квадродеревьев............................................................25

1.2.1.4 Представление фрагментов пространственных данных произвольной области с использованием линейных квадродеревьев..........................................29

1.2.1.5 Представления фрагментов пространственных данных произвольной области с использованием отношений Пеано........................................................31

1.2.2 Предлагаемые новые модели представления................................................34

1.3 Растровые модели для передачи пространственных данных в системах мониторинга...............................................................................................................35

1.3.1 Существующие модели представления..........................................................37

1.3.2 Предлагаемые новые модели представления................................................38

1.4 Выводы.................................................................................................................41

2 Растровые модели, предназначенные для хранения и обработки пространственных данных состояния объекта мониторинга в виде системы отношений 43

2.1 Понятие сложного пространственного объекта, характеризующего состояние объекта мониторинга..............................................................................43

2.2 Структура моделей..............................................................................................44

2.3 Построение моделей............................................................................................45

2.3.1 Трансформация многомерного координатного пространства пространственного объекта в одномерное..............................................................45

2.3.2 Декомпозиция...................................................................................................49

2.3.3 Снижение избыточности на основании метода группового кодирования 54

2.4 Аналитическое сравнение вариантов реализации моделей для систем мониторинга по показателю требуемого объема памяти......................................56

2.4.1 Требования и ограничения на характеристики моделей..............................56

2.4.2 Определение аналитических выражений для модели тЬг ..........................58

2.4.3 Определение аналитических выражений для модели бг.............................59

2.4.4 Определение аналитических выражений для модели рг............................61

2.4.5 Определение аналитических выражений для модели сгс...........................63

2.4.6 Определение аналитических выражений для модели сг.............................65

2.4.7 Результаты аналитического сравнения моделей объемов памяти для систем мониторинга в наихудшем и наилучшем случаях....................................69

2.5 Экспериментальное сравнение систем мониторинга по показателю требуемого объема памяти.......................................................................................71

2.6 Выводы.................................................................................................................72

3 Растровые модели передачи пространственных данных о состоянии объекта мониторинга в виде последовательности бит 73

3.1 Структура моделей..............................................................................................73

3.2 Построение моделей............................................................................................75

3.2.1 Декомпозиция...................................................................................................76

3.2.2 Обход вершин квадродерева в ширину для кодирования и получения последовательностей бит..........................................................................................76

3.3 Аналитическое сравнение вариантов реализации моделей по показателю требуемого объема передаваемых данных.............................................................77

3.3.1 Определение аналитических аппроксимирующих выражений количества различных вершин в квадродеревьях......................................................................77

3.3.1.1 Определение аналитических аппроксимирующих выражений количества различных вершин в квадродеревьях для наихудшего случая.............................77

3.3.1.2 Определение аналитических аппроксимирующих выражений количества различных вершин в квадродеревьях для наилучшего случая.............................81

3.3.2 Аналитические аппроксимирующие зависимости для определения объема передаваемых данных с использованием исследуемых моделей.........................89

3.3.3 Результаты аналитического сравнения моделей по показателю требуемого объема передаваемых данных в наихудшем и наилучшем случаях....................91

3.4 Экспериментальное сравнение моделей по показателю требуемого объема передаваемых данных...............................................................................................92

3.5 Выводы.................................................................................................................93

4 Алгоритм визуализации пространственных данных в системах мониторинга94 4.1 Процедуры запросов обработки изменения состояния объектов мониторинга для моделей................................................................................................................95

4.1.1 Аналитические выражения для расчета времени выполнения процедуры обработки изменения состояния объектов мониторинга для модели ¿г.............95

4.1.2 Аналитические выражения для расчета времени выполнения процедуры обработки изменения состояния объектов мониторинга для модели тЪг..........96

4.1.3 Аналитические выражения для расчета времени выполнения процедуры обработки изменения состояния объектов мониторинга для модели рг............97

4.1.4 Аналитические выражения для расчета времени выполнения процедуры обработки изменения состояния объектов мониторинга для модели сгс...........98

4.1.5 Аналитические выражения для расчета времени выполнения процедуры обработки изменения состояния объектов мониторинга для модели сг.............99

4.2 Процедуры обработки запросов по координатам............................................99

4.3 Процедуры обработки запросов по пространственным атрибутам.............102

4.3.1 Определение отношения для выборки данных по пространственным атрибутам..................................................................................................................104

4.4 Процедуры обработки запросов по непространственным атрибутам.........109

4.5 Процедуры запросов по комбинации атрибутов............................................111

4.6 Процедура передачи данных в видеосистему................................................114

4.7 Аналитическое сравнение моделей по времени выполнения алгоритма визуализации............................................................................................................114

4.8 Экспериментальное сравнение моделей по времени выполнения алгоритма визуализации............................................................................................................117

4.9 Выводы...............................................................................................................118

Заключение....................................................................................119

Список литературы..........................................................................121

Приложение 1 Тексты программ трансформации данных..........................131

Приложение 2 Реализация запросов алгоритма визуализации

на языке SQL.................................................................................147

Приложение 3 Документы о внедрении результатов.................................152

ВВЕДЕНИЕ

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

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

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

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

Повышение оперативности функционирования системы мониторинга повышает оперативность функционирования системы управления рисками природным и техногенных катастроф, в состав которой входит система мониторинга.

Диссертационная работа выполнена в рамках федеральной целевой программы «Снижение риска и уменьшение последствий природных и техногенных катастроф» по теме НИР «Методы и модели создания информационно-аналитических систем мониторинга и прогнозирования рисков возникновения природных и техногенных катастроф на основе геоинформационных технологий», номер гос. регистрации 1.61.10 ГК № П 519 от 14.05.2010 Минобрнауки России.

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

Задачи, решение которых необходимо для достижения поставленной цели:

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

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

оперативности, для хранения, обработки, передачи и визуализации пространственных данных;

- разработка алгоритма визуализации пространственных данных в системах мониторинга природных и техногенных катастроф и оценка вариантов его реализации на основании различных растровых моделей по показателю оперативности его выполнения;

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

Объект исследования. Подсистема хранения, передачи и обработки пространственных данных в системах мониторинга природных и техногенных катастроф, построенных на основе геоинформационных технологий.

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

Соответствие паспорту научной специальности. Содержание диссертации соответствует п.5 «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации» и п. 12 «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальности 05.13.01 - Системный анализ, управление и обработка информации.

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

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

- растровые модели для хранения и обработки пространственных данных в виде системы отношений, полученных на основании кривых, заполняю-

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

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

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

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

Результаты работы использованы: в учебном процессе Юго-Западного государственного университета на кафедре программного обеспечения вычислительной техники при обучении студентов по направлению магистерской подготовки 231000.68 «Программная инженерия» в дисциплине «Пространственные базы данных» и в научно-исследовательской работе кафедры по теме «Методы

и модели создания информационно-аналитических систем мониторинга и прогнозирования рисков возникновения природных и техногенных катастроф на основе геоинформационных технологий», в ООО «Научно-финансовый центр «ЦЕНТР КАПИТАЛ», ООО «МеталлЭксперт», что подтверждено соответствующими актами (приложение 3).

Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на научно-технических конференциях: IX, X Международных конференциях «Распознавание» (Курск, 2010, 2012 гг.); Международной конференции «Континуальные алгебраические логики, исчи