Растровые модели и алгоритм визуализации пространственных данных в системах мониторинга природных и техногенных катастроф тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Белов, Александр Владимирович

• Белов, Александр Владимирович
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Белов, Александр Владимирович

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 Выводы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.6 Выводы

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

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

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

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

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

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

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

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

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

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

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

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

3.5 Выводы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.9 Выводы

Заключение

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

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

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

на языке SQL

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

Введение диссертации (часть автореферата) на тему «Растровые модели и алгоритм визуализации пространственных данных в системах мониторинга природных и техногенных катастроф»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 ПОСТАНОВКА ЗАДАЧИ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ

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

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

Согласно ГОСТ Р 22.0.02-94 [24] и ГОСТ Р 22.0.09-95 [27] чрезвычайная ситуация это - «обстановка на определенной территории или акватории, сложившаяся в результате аварии, опасного природного явления, катастрофы, стихийного или иного бедствия, которые могут повлечь или повлекли за собой человеческие жертвы, ущерб здоровью людей или окружающей природной среде, значительные материальные потери и нарушение условия жизнедеятельности людей».

Согласно ГОСТ Р 22.0.05-94 [26] авария это - «опасное техногенное происшествие, повлекшее чрезвычайную ситуацию, а техногенная катастрофа это -крупная авария, как правило с человеческим жертвами».

В результате аварий и техногенных катастроф возникает техногенная чрезвычайная ситуация.

Согласно ГОСТ Р 22.0.03-95 [25] природно-техногенная катастрофа это -«разрушительный процесс, развивающийся в результате анормального взаимодействия технологических объектов с компонентами окружающей природной среды, приводящий к гибели людей, разрушению и повреждению объектов экономики и компонентов окружающей природной среды».

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

Согласно ГОСТ Р22.1.02-95 [28] объект мониторинга это - «природный, техногенный или природно-техногенный объект или его часть, в пределах ко-

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

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

Основной задачей системы мониторинга является снижение риска возникновения чрезвычайной ситуации [32]. Имеются три варианта использования системы: мониторинг опасных объектов и территорий, разведка возникшей чрезвычайной ситуации, контроль развития чрезвычайной ситуации и ее ликвидации. При этом основной задачей является не простая фиксация состояния объекта мониторинга, а анализ изменений состояния с целью предупреждения возникновения чрезвычайной ситуации и возможности оперативного управления при ее возникновении [59].

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

Существуют два вида систем мониторинга: система мониторинга состояний природного или техногенного объекта [29] и структурированная система мониторинга и управления инженерными системами зданий и сооружений [30].

Первая система осуществляет свои функции в основном с применением

аэрокосмических методов дистанционного зондирования [46], а вторая - предназначена для осуществления мониторинга технологических процессов и процессов обеспечения функционирования оборудования непосредственно на потенциально опасных объектах.

Системы мониторинга подробно рассмотрены в [32,33]. Проектированию систем мониторинга с применением методов системного анализа [21,40,42,43,44,45,47] посвящена работа [38]. Одной из систем, которая оказы-

вает существенное влияние на показатели качества функционирования [5,6] является ее подсистема хранения передачи и обработки данных, структурно-функциональная схема которой приведена на рисунке 1.1.

Объект

монито-

и

ринга

Система

1 наблюдения за

- состоянием

объекта

мониторинга ми и (

Система хранения и

передачи данных

Система приема данных

Система хранения и обработки данных

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

Модель [пространственных 'данных

ВСПР

Рисунок 1.1- Структурно-функциональная организация подсистемы хранения передачи и обработки данных в системах мониторинга

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

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

Кроме оперативности, при дистанционном зондировании, основанном на фиксации электромагнитного излучения, к системам мониторинга предъявляют требования по пространственному разрешению, радиометрическому разрешению, спектральному разрешению и временному разрешению [38,46].

а

а.

ъ

о «

ї ш й Є

а

а. Є

и

о £

10000

1000 -■

100 -•

10

1 -

0.1

0.1

Гидрометеорология

ЛЕСНОЕ ХОЗЯЙСТВО

КОНТРОЛЬ ЧРЕЗВЫЧАЙНЫХ СИТУ А-

ций

фундаментальные

исследования

1 I

ЭКОЛОГИЯ

СЕЛЬСКОЕ и водное хозяйство

ГЕОЛОГИЯ

КАРТОГРА ФИЯ

землеустройство, строительство, транспорт

| ' и---1-—-

-1-

10 100 1000 Периодичность обзора, час

-+-

10000

100000

Рисунок 1.2- Требования к оперативности и пространственному разрешению систем мониторинга космического базирования

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

мониторинга

Мониторинг за состоянием окружающей среды и техногенных объектов может осуществляться дистанционным способом. Так дистанционное зондирование земли [46] широко применяют в системах мониторинга и управления рисками чрезвычайных ситуаций [2,29,32,33,57]. Кроме дистанционного зондирования земли, дистанционное зондирование, как метод дистанционного измерения параметров, может применяться при мониторинге состояния инженерных сетей опасных техногенных объектов.

Данные дистанционного зондирования состояния пространственных объектов всегда имеют пространственную составляющую в двумерном или трехмерном пространстве. Другими словами, значения измеряемых характеристик пространственного объекта связаны с определенными точками пространства. Пространство является базой для данных дистанционного зондирования [35].

Все это приводит к использованию того, что в научно-технической литературе называется пространственными данными и пространственными базами данных [58,82,89,93,95,96], составляющих основу ГИС [20,31,37,61,70].

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

мониторинга

В соответствии с ГОСТ Р 52438-2005 [31] под пространственными данными понимаются сведения (данные) о пространственных объектах. Сам пространственный объект бывает двух типов: простым и сложным. Простой пространственный объект представляется структурой, состоящей из трех частей: идентификатора объекта, координатных данных объекта и атрибутивных данных объекта. Сложный пространственный объект содержит несколько простых.

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

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

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

Таким образом, пространственные данные полностью описывают объект мониторинга. На рисунке 1.3 приведены примеры объектов мониторинга, за которыми осуществляется наблюдение с применением методов дистанционного зондирования. При этом на рисунках 1.3а [55] и 1.36 [53] показаны объекты для систем мониторинга, контролирующих состояние объектов, а на рисунке 1.3в

[54] - состояние инженерных сетей объекта.

а) б) в)

Рисунок 1.3 - Объекты мониторинга

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

мониторинга

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

' 3

ш

а) б) в)

г) Д) е)

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

На рисунке 1.5 [54] показан вариант идентификации элементов объекта мониторинга на основе дистанционного зондирования в инфрокрасном диапазоне, параметры которых выходят за допустимые границы и которые могут быть инициирующими источниками техногенной катастрофы. Идентификация таких элементов возможна в автоматическом режиме на основе пространсвен-ных данных. Координатные данные определяют сам элемент, а атрибутивные

данные - его характеристики.

а) б) в)

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

Таблица 1.1 - Идентификация опасных элементов объекта мониторинга по их пространственным данным

и элемента Наименование элемента Изображение Описание дефекта

11 Щит К/А №11. АВ ввода. Фаза «А». БКС верхнего вывода АВ и шины. С Нагрев 94° С (норма 59° С)

32 Щит К/А №11. АВ ввода. Фаза «А». БКС нижнего вывода АВ и шины. г Нагрев 900 С (норма 470 С )

43 Щит К/А №11. АВ ввода. Фаза «А». БКС нижнего вывода АВ и шины. Нагрев 900 С (норма 460 С)

44 Щит К/А №11. Фаза «С». БКС нижнего вывода и шины. Нагрев 940 С (норма 460 С)

56 Щит К/А №11. Фаза «С». БКС нижнего вывода и шины. Нагрев 940 С (норма 470 С )

67 Щит К/А №11. Фаза «В». БКС нижнего вывода и проводника. Нагрев 970 С (норма 430 С )

Окончание таблицы 1.1

68 Ш/Ш 11А. Шкаф управления. Нагрев 1140 С (норма 440 С)

71 Ш/Ш 11 А. Шкаф управления * Нагрев 970 С (норма 430 С )

92 Ш/Ш 11 А. Шкаф управления Нагрев 1500 С (норма 430 С )

Еще одним источником пространственных данных для объектов мониторинга могут быть пространственные данные, полученные на основании точечных измерений, в результате их интерполяции при помощи расчетов на другие точки пространственных данных в растровой форме. На рисунке 1.6 [1] показаны зоны загрязнения, полученные расчетным путем.

Система ЭкопогическОГО Моннкшинг.1- ІЛ1 Км: іиіря.іжїнно .имоеферы 1:100000

Показать Масштаб Объекты Обработка £кна

ПОМОЩЬ : Ї

Пегенда

□ Пинии электропередач . П Газопровод

□ Менее 0.01 ГЩК И 0.01-0.02 ГЩК

□ 0 02 0.03 ГЩК

■ 0.03-0.04 ПДК

■ 0.04-0 05 ГШК

■ 0 05 0.1 ГШК

■ 0.1-0.5 ПДК

Рисунок 1.6- Зоны загрязнения, полученные в результате расчетов Обработка и сжатие атрибутивной части, представленной в виде прямоугольного изображения, хорошо изучены [3,4,23,41,50]. Представление, обработка и сжатие пространственных данных объектов произвольной формы требуют дополнительных исследований.

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

данных в системах мониторинга

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

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

Растровая модель представления пространственных данных (рисунок 1.7) основана на координатной сетке или матрице ячеек, где каждая ячейка соответствует пикселю.

X

■■■■

яаявааве ■■■■■■■■■■■

вааваававв ■■ ■■■■ вавввав но ■■■<

лап ■■■

■■я

ававш: вав ■■■

■вввваввваввв ■аааааааааааа

Ч5В5 —►■«"-Н-ІЯ

У

Рисунок 1.7 - Растровая модель представления пространственных данных Положение каждой ячейки матрицы обозначается номером х столбца и номером у ряда от начала отсчета. В машинной графике за начало отсчета принимают верхний левый угол, в геосистемах - нижний левый угол матрицы. Пара значений <х>< у> представляет координатные данные, определяющие местоположение пикселя. Для каждого пикселя пространственного объекта определяются атрибутивные данные < ах ><а2 >... < ат >. Полностью пространственный объект определяется структурой вида < X >< У >< А] >< Л2 >... < Ат >,

где X, У, А], А2, ..., Ат - имена элементов структуры, которые содержат соот-

ветственно значениях, у, а1г а.2, ...,ат.

Такое представление - наиболее простое и его можно назвать каноническим представлением пространственного объекта.

Каноническое представление в виде набора значений < х >< у >< я, >< а2 >...< ат > используется в обменных форматах типа Geo-EAS format [91].

Каноническое представление в виде отношения r(X,Y,A],A2,...,Am), называется в диссертационной работе растровой моделью типа sr.

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

Основной моделью представления простого пространственного объекта сложной формы (рисунок 1.8) в настоящее время является его представление с использованием минимальных ограничивающих прямоугольников [70,79,92].

STUDY AREA (Wur)

Рисунок 1.8 - Представление простого пространственного объекта сложной

формы в растровой модели Элементами такого представления являются:

STUDY AREA -область представления объекта, сегмент данных произвольной пространственной формы;

Cell length - длина стороны квадрата ячейки растрового изображения;

Missing value - отсутствующее значение, ячейка, с которой не связано атрибутивное значение;

Number of columns -количество столбцов в ограничивающем область изучения прямоугольнике;

Number of rows -количество строк в ограничивающем область изучения прямоугольнике;

(xUL,yUL) - координаты верхнего левого угла ограничивающего прямоугольника в реальной системе координат;

(xUR,yUR) - координаты верхнего правого угла ограничивающего прямоугольника в реальной системе координат;

(xLR, yLR) - координаты нижнего правого угла ограничивающего прямоугольника в реальной системе координат;

(xLL,yLL) - координаты нижнего левого угла ограничивающего прямоугольника в реальной системе координат.

В случае сложного пространственного объекта требуется подобная структура данных, представленная на рисунке 1.9 и рисунке 1.10.

Пиксели со значениями «нет данных)^

ВІоЬ-файл

МБР

□С1ГТГ ги ииЭСЛ-'-'Са

ис^цц-ц»

ВІоЬ-файл

МВК

МВК

Пиксели со знач^ ниями «нет данных»

ВІоЬ-файл

авааява: ипии В ЯЯВаааЯЯЯ. )1 ) -Л__ШЯЯЯЯЯЯи.

□С Ji.ii

ииииьиииивяя иі_ л*С!—ч—

еанаяаааввава вавав. л.....

ВІоЬ-файл

■ ■ ■ ■ ■ ■

МВК

1-й иииі-и и О!

-I ; ,.л..ии и ии_ .-ихтасха ии.

1-ил—IU.JL.Ul- и им

і__іиі__іииі_иі- иі_ипи.

і-ил—,ииі_иі_иі_ опзсппас: псини ^ ^ииьиьи^ик-и

i-L.JI.iU- С и ьиси.

: п гп агп_

■■■■■■■■■■■ ВВВВІ

■вівіікіїлхіїаа . ■■ ■■■■■■ ■ ■■ і

ікавка« ■■ ■■■■■ вава

■■■■ авав;

■■■■■■»«■■Ні ■■■■■■■■■■■І Я ВВВВВВВВВВВІ

■■■•■■■■■■І шіііввіавв;

□□□ ■ І иии

иии І

іич

ииииии ииииии

ииииир и иииии □ ииииии ииииии 'З пииииии ииииииииь иииииииии иии-иииии : і і иииииі піпптппг

ч

В1оЬ-файл Пиксели со значениями «нет данных»

Пиксели со значениями «нет данных»

Рисунок 1.9 - Представление пространственных объектов в ограничивающих

прямоугольниках

ЧИІЧИ 4*11- III

■Нт* Т'гГ I___

ишияш.*

Ції«* ЩІІЇЯ 81 I

■■■■■■■■ваві

ЛІ III +Н"І"-

і І І І І Г І І Гіввв /

■■■■■■■

■»■■•■■■в

Зш шва ■ ■ ■■■ ■■■

■■ ■■■ ■■■ ■■ ■■■■■■ ■■ ■■■■■■■ ■■ ■ ■■

■ ■■■■■

■■■■■■■■■■а яявяи

■■■■■»«■■»в апаша

■■ ■■■■■■ мааа

■■ ■■■■■ вшите

вчіч ■■■■

■■■■■■■■■■■а шя ■■■■■■■■■■■а

■ ■■•■■■■■■«¡а ■■■■•■■■■■■а

■■■N«■■■■11 ■■■■■■■■■■■В

м, м (Vf.il ■)!■*

ИТТН ■ *ГРР

НвхявдХзш*

ИИ І И И І І І І

ТП ГТГ ГГКаЕгаї

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Белов, Александр Владимирович

4.9 Выводы

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

Использование моделей данных ere и сг в алгоритме визуализации позволило повысить оперативность обработки данных при изменении состояния объектов мониторинга от 1,3 до 1,6 раз в зависимости от сравниваемой модели.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Белов, Александр Владимирович, 2013 год

СПИСОК ЛИТЕРАТУРЫ

1. Автоматизированные системы экологического мониторинга атмосферы промышленно развитых территорий: монография / Панарин В.М. [и др.] Тула: Изд-во ТулГУ, 2006. 165 с.

2. Акимов В.А., Лесных В.В., Радаев H.H. Основы анализа и управления риском в природных и техногенных сферах. М.: Деловой экспресс, 2004. 352с.

3. Александров В.В., Горский Н.Д. Представление и обработка изображений: Рекурсивный подход. Л.:Наука, 1985. 192 с.

4. Александров В.В., Кулешов C.B., Цветков О.В. Цифровая технология инфокоммуникации. Передача, хранение и семантический анализ текста, звука, видео. СПб.: Наука, 2008. 244 с.

5. Антонов A.B. Системный анализ. Учеб. для вузов. М.: Высш. шк., 2004. 454 с.

6. Анфилатов B.C. и др. Системный анализ в управлении : учеб. пособие / под ред. A.A. Емельянова. М. : Финансы и статистика, 2002. 368 с.

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

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

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

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

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

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

13. Белов A.B. Преобразование квадродерева пространственных данных ГИС в бинарное дерево // Современные информационные технологии сборник статей международной научно-технической конференции (Computer -based conference). Пенза: Пензенская государственная технологическая академия. 2010. Вып. 11. С. 154-156.

14. Белов A.B. Представление квадродерева пространственных данных ГИС в виде цифровой последовательности // Современные информационные технологии сборник статей международной научно-технической конференции (Computer - based conference). Пенза: Пензенская государственная технологическая академия. 2011. Вып. 13. С. 164-165.

15. Белов А. В. Формирование классификатора с нечеткими границами на основании кривых, заполняющих дискретное признаковое пространство // Известия ЮЗГУ. 2012. №4(43).Ч.2. С. 71 - 73.

16. Белов A.B. Передача и хранение фрагментов изображения дистанционного зондирования при помощи различных схем кодирования квадроде-

ревьев. Часть 2. Сравнительный аналитический и экспериментальный анализ схем кодирования квадродеревьев // Телекоммуникации. 2013. №3. С.36 - 40.

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

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

19. Белов A.M. Исследование эффективности одномерных дискретных косинусных преобразований на развертках двумерных сигналов, порожденных каноническими системами счисления // Компьютерная оптика. 2011. Т. 35. №4. С. 519-521.

20. Берлянт A.M. Теоретические проблемы картографии. М.: Изд-во МГУ, 1993. 116 с.

21. Волкова В.Н., Денисов A.A. Основы теории систем и системного анализа : учебник для вузов. СПб. : Изд-во СПбГТУ, 2003.

22. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс.: Пер. с англ. М.: Издательский дом «Вильяме, 2003. 1088 с.

23. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2005. 1070 с.

24. ГОСТ Р 22.0.02-94 Безопасность в чрезвычайных ситуациях. Термины и определения основных понятий. М.: ИПК Издательство стандартов, 1995. Юс.

25. ГОСТ Р 22.0.03-95 Безопасность в чрезвычайных ситуациях. Природные чрезвычайные ситуации. Термины и определения. М.: ИПК Издательство стандартов, 1995. 9 с.

26. ГОСТ Р 22.0.05-94 Безопасность в чрезвычайных ситуациях. Техногенные чрезвычайные ситуации. Термины и определения. М.: ИПК Издательство стандартов, 1994. 11 с.

27. ГОСТ Р 22.0.09-95 Безопасность в чрезвычайных ситуациях. Чрезвычайные ситуации на акваториях. Термины и определения. М.: ИПК Издательство стандартов, 1995. 35 с.

28. ГОСТ Р 22.1.02-95 Мониторинг и прогнозирование. Термины и определения. - М.: ИПК Издательство стандартов. 1996. - 6 с.

29. ГОСТ Р 22.1.04-96 Мониторинг аэрокосмический. Номенклатура контролируемых параметров чрезвычайных ситуаций. М.: ИПК Издательство стандартов, 1996. 15 с.

30. ГОСТ Р 22.1.12-05 Структурированная система мониторинга и управления инженерными системами зданий и сооружений. М.: Стандартин-форм, 2005. 13 с.

31. ГОСТ Р 52438-2005 Географические информационные системы. Термины и определения. М.: Стандартинформ, 2006. 28 с.

32. Ефремов A.B. Современные технологии дистанционного мониторинга территорий и управление рисками чрезвычайных ситуаций [Электронный ресурс] // Технологии техносферной безопасности: интернет-журнал. 2008. № 6 (22). URL: http://agps-2006.narod.ru/ttb/2008-6/03-06-08.ttb.pdf (дата обращения 20.05.2013).

33. Калинин М.Ю., Волчек А.А, Шведовский П.В. Чрезвычайные ситуации и их последствия: мониторинг, оценка, прогноз и предупреждение. Минск: «Белсэнс», 2010. 275 с.

34. Карпов В.Е., Коньков К.А. Основы операционных систем. Курс лекций: учебное пособие. / Под ред. В.П. Иванникова. М.: ИНТУИТ.РУ «Интернет - Унивеситет информационных технологий», 2005. 536 с.

35. Клир Д. Системология. М. : Радио и связь, 1973. 262 с.

36. Концепция развития российской космической системы дистанционного зондирования Земли на период до 2025 года [Электронный ресурс]. URL: http://do.gendocs.ru/docs/index-306053.html (дата обращения: 20.05.2013).

37. Кошкарев A.B., Тикунов B.C. Геоинформатика. М.: Картгеоцентр-Геодезиздат, 1993. 348 с.

38. Малышев В.В., Красильщиков М.Н., Бобронников В.Т., Нестеренко О.П., Федоров A.B. Спутниковые системы мониторинга. Анализ, синтез и управление / Под ред. В.В. Малышева. М.: Изд-во МАИ, 2000. 568 с.

39. Мейер Д. Теория реляционных баз данных. М.: Мир, 1987. 608 с.

40. Месарович М., Такахара И. Общая теория систем: математические основы М. : Мир, 1978. 311 с.

41. Методы компьютерной обработки изображений / Под ред. В.А. Сойфера. М.: Физматлит, 2003. 784 с.

42. Моисеев H.H. Математические задачи системного анализа. М. : Наука, 1981.

43. Новосельцев В.И. [и др.] Теоретические основы системного анализа. / Под ред. В. И. Новосельцева. М.: Майор, 2006. 592 с.

44. О'Коннор Дж., Макдермот И. Искусство системного мышления: Необходимые знания о системах и творческом подходе к решению проблем. М.: Альпина Бизнес Букс, 2006. 256 с.

45. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ : учеб. пособие. М.: Высшая школа, 1989. 367 с.

46. Рис У.Г. Основы дистанционного зондирования. М.: Техносфера, 2006. 336 с.

47. Рыков A.C. Модели и методы системного анализа: принятие решений и оптимизация: Учебное пособие для вузов. М.: МИСИС. Издательский дом «Руда и металлы». 2005, 352 с.

48. Свидетельство о государственной регистрации программы для ЭВМ №2012613730 Программа минимизации и анализа линейного квадродере-

ва для представления фрагментов цветного изображения произвольной формы. /Белов, A.B. заявлено 28.02.2012, опубл. 20.04.2012.

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

50. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера, 2004. 368с.

51. Федосеев В.А. Компрессия изображений с помощью дискретных ортогональных преобразований, определённых на развёртках двумерных областей // Компьютерная оптика. 2005. № 28. С. 132-135.

52. Фотография [Электронный ресурс]. URL: http://landsat.usgs.gov/images/gallery/52_L.jpg (дата обращения: 20.05.2013).

53. Фотография [Электронный ресурс]. URL: http://www.kaloshino.ru/userfiles/Image/map_google.jpg (дата обращения: 20.05.2013).

54. Фотография [Электронный ресурс]. URL: http://www.termografia.ru/about/gallery/ (дата обращения: 20.05.2013).

55. Фотография [Электронный ресурс]. URL: http://www.geosystema.net/gallery/analytica/Gamalia3.jpg (дата обращения: 20.05.2013).

56. Фотография [Электронный ресурс]. URL: http://devmag.org.za/201 l/02/23/quadtrees-implementation/ (дата обращения: 20.05.2013)

57. Шахраманьян М.А., Епихин A.B., Щербенко Е.В., Дорошенко С.Г., Челюканов A.B. Космический мониторинг наводнений и их последствий // Технологии гражданской безопасности. 2003, №1-2. С. 54 - 61.

58. Шекхар Ш., Чаула С. Основы пространственных баз данных. /Пер. с англ. М.: КУДИЦ-ОБРАЗ, 2004. 336 с.

59. Яковлев O.B. Концептуальные основы мониторинга рисков в условиях системных конфликтов // Проблемы анализа риска. 2007. Т. 4. № 3. С. 281291.

60. Abel, D.J. (1984). A B+tree structure for large quadtrees. International Journal of Computer Vision, Graphics and Image Processing, 27(1), 19-31.

61. Arc View GIS. The Geographic Information System for Everyone. (1996). ESRI, Inc. USA

62. Chang, H. K.-C., Cheng, L.-L, Liao, S.-H. & Kuo, C.-K. (1996). Breadth first linear quadtrees for water resource management in Geographical Information Systems. HydroGIS 96: Application of Geographic Information Systems in Hydrology and Water Resources Management (Proceedings of the Vienna Conference, April 1996). lAHSPub), 235, 55-62.

63. Chang, H.K., & Chang, J-W. (1994). The fixed binary linear quadtree coding scheme for spatial data. The International Society for Optical Engineering SPIE, Visual Communications and Image Processing, 2308, 1214-1220.

64. Chang, H.K.-C., Liu, S.-H. & Tso C.-K. (1997). Two-Dimensional Template-Based Encoding for Linear Quadtree Representation. Photogrammetric Engineering & Remote Sensing, 63(11), 1275-1282.

65. Chen, C.-S., Liang, J.-Y., Lee, Y.-K., Fan, M.-H. & Huang, C.-H. (2011). Large Efficient Searching Algorithms for Multi-dimensional Space Data Using Hilbert Space-filling Curves. Journal of Information & Computational Science, 8(1), 41-50.

66. Chen, P-M. (2002). Variant code transformations for linear quadtrees. Pattern Recognition Letters, 23(11), 1253-1262.

67. Chung, K.-L., Huang, Y.-L. & Liu Y.-W. Efficient algorithms for coding Hilbert curve of arbitrary-sized image and application to window query. Information Sciences, 177(10), 2130-2151.

68. Chung, K.-L., Tsai Y.-H. & Hu, F.-C. (2000). Space-Filling Approach for Fast Window Query on Compressed Images. IEEE Transaction on Image Processing, 9(12), 2109-2116.

69. Chung, K.-L., Tsai, Y.-H & and Hu, F.-C. (2000). Space-Filling Approach for Fast Window Query on Compressed Images, IEEE Transaction on Image Processing, 9( 12), 2109-2116.

70. Crosier S. (2004). Getting Started With Arcgis: ArcGIS 9. ESRI.

71. Dai, H.-K. & Su, H.-C. (2003). Approximation and Analytical Studies of Inter-clustering Performances of Space-Filling Curves. Discrete Mathematics and Theoretical Computer Science AC, 53-68.

72. Finkel, R.A., & Bentley, J.L. (1974). Quadtrees: A data structure for retrieval on composite keys. Acta Informatica, 4, 1-9.

73. Frank, A.U. & Timpf, S. (1994). Multiple Representations for Cartographie Objects in a Multi-scale Tree - An Intelligent Graphical Zoom. In Computer and Graphics Special Issue on Modelling and Visualization of Spatial Data in GIS, 18(6), 823-829.

74. Gargantini, I. (1982). An effective way to represent quadtrees. Communications of A CM, 25{ 12), 905-910.

75. Hamilton, C.H.& Rau-Chaplin, A. (2008). Compact Hilbert indices: Space-filling curves for domains with unequal side lengths. Information Processing Letters, 105, 155-163.

76. Harakal, M. & Chmurny, J. (1996). Image Generation by Octree. Radio-ingineering, 5 (3 ), 1 -5.

77. Hunter, G.M. (1979). Operations on Images Using Quad Trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, Pami-1(2), 145-153.

78. Jagadish, H.V. (1990). Linear Clustering of Objects with Multiple Attributes. Proc. ACMSIGMOD Conf., 332-342.

79. Kothuri, R., Godfrind, A., & Beinat, E. (2007). Pro Oracle Spatial for Oracle Database 1 lg. Apress.

80. Kothuri, R.K.V., Ravada, S., & Abugov, D. (2002). Quadtree and R-tree indexes in oracle spatial: a comparison using GIS data. Proceedings of the ACM SIGMOD International Conference on Management of Data, (SIGMOD 2002), 546557.

81. Kriegel, H.-P., Peter Kunath, P., Pfeifle, M. & Renz, M. (2003). Acceleration of relational index structures based on statistics. Proceeding SSDBM '03 Proceedings of the 15th International Conference on Scientific and Statistical Database Management, 258-261.

82. Laurini, R. & Thompson, D. (1992). Fundamentals of Spatial Information Systems. The Apic Series 37. Academic Press.

83. Li, S.X. & Loew, M.H. (1987). The quadcode and its arithmetic. Communications of ACM, 30(7), 621-626.

84. Lin, T-W. (1997a). Compressed quadtree representations for storing similar images. Image and Vision Computing, 75(11), 833-843.

85. Lin, T-W. (1997b). Set operations on constant bit-length linear quadtrees. Pattern Recognition, 30(7), 1239-1249.

86. Liu, X. & Schrack, G.F. (1996). Encoding and decoding the Hilbert order. Software: Practice and Experience, 26(12), 1335-1346,.

87. Liu, X. & Schrack, G.F. (1997). An algorithm for encoding and decod-ingthe 3-D Hilbert order. IEEE Transaction on Image Processing, 6(9),1333-1337.

88. Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A.N. & Yannis Theodoridis, Y. (2006). R-Trees: Theory and Applications. Springer-Verlag London Limited.

89. Manolopoulos, Y., Papadopoulos, A.N. & Vassilakopoulos, M.Gr. (2005). Spatial databases : technologies, techniques and trends. Idea Group Publishing Hershey, Inc.

90. Moon, B., Jagadich, H.V., Faloutsos, C. & Saltz, J.H. (2001). Analysis of the Clustering Properties of the Hilbert Space-Filling Curve. IEEE Transaction on Knowledge and Data Engineering, 13(1), 1-18.

91. PCRaster Documentation. Release 3.0.1. PCRaster Team. (2011). URL: http://pcraster.geo.uu.nl/documentation/PCRaster/PCRaster.pdf (20.05.2013).

92. Racine, P. (2010). Introducing PostGIS WKT Raster. Seamless Raster/Vector Operations in a Spatial Database. URL: http://2010. foss4g.org/presentations/3221 .pdf (20.05.2013).

93. Rigaux, P., Scholl, M. & Voisard, A. (2002). Spatial Databases with Application to GIS. Morgan Kaufmann Publishers.

94. Sagan, H. (1994). Space-filling curves. Springer-Verlag New York, Inc.

95. Samet, H. (1990a). The design and analysis of spatial data structures. Reading, MA: Addison Wesley.

96. Samet, H. (1990b). Applications of spatial data structures: computer graphics, image processing, and GIS. Reading, MA: Addison Wesley.

97. Shaffer, C.A. & Samet, H. (1990). Set Operations for Unaligned Linear Quadtrees. Computer Vision, Graphics and Image Processing, 50, 29-49.

98. Shaffer, C.A., Samet, H., & Nelson, R.C. (1990). QUILT: A geographic information system based on quadtrees. International Journal on Geographical Information Systems, 4(2), 103-131.

99. Stonebraker, M., Abadi, D. J., Batkin, A., Chen, X., Cherniack, M., Ferreira, M., Lau, E„ Lin, A., Madden, S. R., O'Neil, E. J., O'Neil, P. E., Rasin, A., Tran, N. & Zdonik, S. B. (2005). C-Store: A Column-Oriented DBMS. Published in: Proceeding VLDB '05 Proceedings of the 31st international conference on Very large data bases, 553-564.

100. Vassilakopoulos, M., Manolopoulos, Y. & K Economou, K. (1993). Overlapping quadtrees for the representation of similar images. Image and Vision Computing, 11(5), 257-262.

101. Vicente, J. & Guillemant, P. (2002). An image processing technique for automatically detecting forest fire. International Journal of Thermal Sciences 41, 1113-1120.

131

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

//-------------------------------------------------------------------------

#include <vcl.h> #pragma hdrstop

#include "Classif.h"

//--------------------------------------------------------------------------

#pragma package(smart_init) #pragma resource "*.dfm"

#include <Math.hpp> #include <math.h> //---------------------------------------------------------------------------

#include <stdio.h> #include <stdlib.h>

#define nc 100000

typedef unsigned int ui; typedef unsigned char uc;

//Функция перевода кода цвета Cbgr в код Гильберта НЗ ui H3(ui Cbgr){

// Массивы для автомата перевода ui рег[12][8]={{ 1,2,2,33,5,5,4},

{2,0,0,8,8,7,7,6},

{0,1,1,9,9,11,11,10},

{11,6,6,0,0,9,9,8},

{9,7,7,11,11,0,0,5},

{10,8,8,6,6,4,4,0},

{3,11,11,5,5,1,1,7},

{4,9,9,10,10,6,6,1},

{5,10,10,1,1,3,3,9},

{7,4,4,2,2,8,8,3},

{8,5,5,7,7,2,2,11},

{6,3,3,4,4,10,10,2}};

ui sost[12][8]={{0,1,3,2,6,7,5,4},

{0,2,6,4,5,7,3,1},

{0,4,5,1,3,7,6,2},

{3,2,0,1,5,4,6,7},

{5,7,3,1,0,2,6,4},

{6,2,3,7,5,1,0,4},

{3,7,6,2,0,4,5,1},

{5,4,6,7,3,2,0,1},

{6,4,0,2,3,1,5,7},

{5,1,0,4,6,2,3,7},

{6,7,5,4,0,1,3,2},

{3,1,5,7,6,4,0,2}};

ui perl [ 12][8]={ {1,2,3,2,4,5,3,5},

{2,6,0,7,8,8,0,7},

{0,9,10,9,1,1,11,11},

{6,0,6,11,9,0,9,8},

{11,11,0,7,5,9,0,7},

{4,4,8,8,0,6,10,6},

{5,7,5,3,1,1,11,11},

{6,1,6,10,9,4,9,10},

{10,3,1,1,10,3,5,9},

{4,4,8,8,2,7,2,3},

{7,2,11,2,7,5,8,5},

{10,3,2,6,10,3,4,4}};

ш вовг 1 [ 12] [8]={ {0,1,3,2,7,6,4,5},

{0,7,1,6,3,4,2,5},

{0,3,7,4,1,2,6,5},

{2,3,1,0,5,4,6,7},

{4,3,5,2,7,0,6,1},

{6,5,1,2,7,4,0,3},

{4,7,3,0,5,6,2,1},

{6,7,5,4,1,0,2,3},

{2,5,3,4,1,6,0,7},

{2,1,5,6,3,0,4,7},

{4,5,7,6,3,2,0,1},

{6,1,7,0,5,2,4,3}};

ш раск=0х00000000,Б1=0; ис

//Перевод кода цвета в

Ь=ис((С1^г&0хРР0000)>> 16);

g=uc((Cbgr&0xFF00)»8);

г=ис(С1^г&0хРР);

// Ь=81гТо1п1(Ес1к2->Тех1);

for (int i=0;i<8 ;i++) {t=0x00;

if (b&0x80)t|=0x4; if (g&0x80)t|=0x2; if (r&0x80)t|=0xl;

bgr=sostl[st][t];

раск=раск«3; if(bgr&0xl){pack|=0xl;

r|=0xl;} if (bgr&0x2) {pack|=0x2;

g|=0xl;} if (bgr&0x4) {pack|=0x4;

b|=0xl;} st=perl[st][t];

r=r«l; g=g«i;

b=b«l; }

//Editl ->Text=IntToStr(pack); return pack;

}//Конец функции перевода кода цвета в код Гильберта

struct sr { II Структура для октодерева

unsigned int cs,lev,sid; float mu;} ;

struct srk { //Структура для октодерева, используемого при построении клас-сиф.

unsigned int csk,lev,sid,cskp; };

struct hsr { //Структура для кривых, заполн. пространство

unsigned int bes,ees,lev,sid; float mu;} ;

sr r[nc]; // Исходный массив классификатора с облаком точек кодов цвета sr ar[nc]; // Октодерево классификатора

hsr har[nc]; //Классификатор классификатор на кривых, заполняющих пространство

srk rk[nc];// Массив для построения классификатора

srk nrk[nc]; // Массив для построения классификатора на новом шаге

int car =0; // Текущее количество кортежей в аг int с_11аг=0;//Количество кортежей в har

float ro=1.0/oct; //Коэффициент компактности

void classificator(void){ /* Формирование массива r[nc]*/

/*Окончание формирования массива г[пс]*/

/* Формирование rl и начального состояния аг*/ int ncrk =0; // Текущее количество кортежей в crk

for(int i=0;i<crk;i++)

if(r[i].mu==1.0)

{

rk[ncrk] .csk=r[i] .es;

rk[ncrk] .lev=r[i] .lev;

rk[ncrk].sid=r[i].sid;

rk[ncrk].cskp= div(r[i].cs,oct).quot*oct;

ncrk++;

}//Окончание if(r[i],mu==1.0)

eise // Формирование начального состояния аг { ar[car].cs=r[i].cs; ar[car].lev=r[i].lev; ar[car].sid=r[i].sid; ar[car].mu= r[l].mu;

car++; //Текущее количество кортежей в аг }//Окончание else if(r[i],mu==1.0) crk=ncrk;// Начальное количество кортежей в rk

/* Формирование классов эквивалентности АЕ, НЕ, Е */ int сАЕ=1; // Количество классов АЕ

int fhom=l; // Флажок гомогенности октанта

int сЕ=1; // Количество кортежей в октанте с одинаковым значением cskp

int k=l; // Номер шага итерации при построении классификатора

while(cAE) { сАЕ=0;

// pcsk=rk[0].cskp; // psid=rk[0].sid;

ncrk=0; // Текущее количество кортежей в rk

if(crk=l)//To кортеж один и его надо сразу переписать в результат {

ar[car].cs=rk[0].csk; ar[car].lev=rk[0].lev; ar[car].sid=rk[0].sid; ar[car].mu=l;

car++;// Текущее количество кортежей в аг } //Конец if(crk==l)//To кортеж один и его надо // сразу переписать в результат else // Кортеж не один

{

for(int i=l;i<crk;i++)

if(rk[i-1 ] .cskp==rk[i] .cskp) { cE++;

if(rk[i-l].sid!=rk[i].sid)

fhom=0; // Нарушение гомогенности в текущем классе Е } //Конец условия if(pcsk==rk[i+l].cskp) else // Завершение класса Е { if(float(cE)/float(oct)>=ro && fhom)

// то это апроксимирующий октант АЕ

{

nrk[ncrk] .csk=rk[i-1 ] .cskp; nrk[ncrk].lev=rk[i-l].lev+l; nrk[ncrk] .sid=rk[i-1 ] .sid; nrk[ncrk] ,cskp=div(rk[i-1 ] .cskp ,IntPower(oct,k+1 )).quot*IntPower(oct,k+1); ncrk++; //Текущее количество кортежей в rk сЕ=1;//Установка счетчика кортежей для нового класса сАЕ++;

}// if(float(cE)/float(oct)>=ro && fhom)

if(float(cE)/float(oct)<ro && fhom)

// то это гомогенный октант НЕ

{

// Заполнение аг

for(int j=i-cE;j<i;j++) {

ar[car].cs=rk[j].csk;

ar[car].lev=rk[j].lev;

ar[car].sid=rk[j].sid;

}//Конец цикла &>г(]=1-сЕ;]<1;]++) //Заполнение гк

пгк[псгк] .сзк=гк[ь1 ] .свкр; пгк[псгк].1еу=гк[ь1].1еу+1; пгк[псгк].з1ё=0;

пгк[псгк].с8кр=сИу(гк[ь 1].с8кр,1п1Ро^'ег(ос1,к+1)).чио1*1п1Рошег(ос1,к+1); псгк++; //Текущее количество кортежей в гк сЕ=Т; //Установка счетчика кортежей для нового класса

}// Конец 1Я(Аоа1(сЕ)/Аоаг(ос1)<го && Ают) if(! йот)

// то это негомогенный октант

{

// Заполнение аг

Гог(т1.Н-сЕ;]<1;]++) {

{

аг[саг].сз=гк[]].с8к;

аг[саг].1еу=гк[)].1еу;

аг[саг].Б1ё=гк[]].81(1;

ar[car].mu=T;

car++;// Текущее количество кортежей в аг }//Конец if(!rk[j].sid) }//Конец цикла for(j=i-cE;j<i;j++)

//Заполнение rk

nrk[ncrk] .csk=rk[i-1 ] .cskp; nrk[ncrk] .lev=rk[i-1 ] .lev+1; nrk[ncrk].sid=0;

nrk[ncrk] .cskp=div(rk[i-1 ].cskp,IntPower(oct,k+1 )).quot*IntPower(oct,k+l);

ncrk++; //Текущее количество кортежей в rk

сЕ=1; //Установка счетчика кортежей для нового класса

fhom= 1 ¡//Начальная установка флажка гомогенности }// Конец if(! fhom) }// Конец else // Завершение класса Е

if(i==crk-l) { if(float(cE)/float(oct)>-ro && fhom)

// то это апроксимирующий октант АЕ

{

nrk[ncrk].csk=rk[i].cskp; nrk[ncrk].lev=rk[i].lev+l; nrk[ncrk].sid=rk[i].sid; nrk[ncrk].cskp=div(rk[i].cskp,IntPower(oct,k+l)).quot*IntPower(oct,k+l);

ncrk++; //Текущее количество кортежей в rk

сЕ=1 ¡//Установка счетчика кортежей для нового класса

сАЕ++;

}// if(float(cE)/float(oct)>=ro && fhom) if(float(cE)/float(oct)<ro && fhom)

// то это гомогенный октант НЕ

{

// Заполнение аг

for(int j=i-cE+1 ;j<i+1 ;j++) {

ar[car].cs=rk[j].csk; ar [car] .lev=rk[j ] .lev; ar[car].sid=rk[j].sid; ar[car].mu=l;

car++;// Текущее количество кортежей в ar }//Конец цикла for(j=i-cE;j<i;j++)

//Заполнение rk nrk[ncrk]. csk=rk[i]. cskp; nrk[ncrk] .lev=rk[i] .lev+l; nrk[ncrk].sid=0;

nrk[ncrk].cskp=div(rk[i].cskp,IntPower(oct,k+l)).quot*IntPower(oct,k+l); ncrk++; //Текущее количество кортежей в rk сЕ=1; //Установка счетчика кортежей для нового класса }// Конец if(float(cE)/float(oct)<ro && fhom) if(! fhom)

// то это негомогенный октант

{

// Заполнение аг

if(rk[j].sid)

{

ar[car].cs=rk[j].csk; ar[car].lev=rk[j].lev; ar[car].sid=rk[j].sid; ar[car].mu=l;

car++;// Текущее количество кортежей в ar }//Конец if(!rk[j].sid) }//Конец цикла for(j=i-cE;j <i;j++)

//Заполнение гк пгк[псгк] .сзк=гк[і] .сэкр; пгк[псгк] Леу=гк[і] .1єу+ 1; nrk[ncrk].sid=0;

ш•k[ncrk].cskp=div(rk[i].cskp,IntPower(oct,k+l)).quot*IntPower(oct,k+l); псгк++; //Текущее количество кортежей в гк сЕ=1; //Установка счетчика кортежей для нового класса Аіош=1;//Начальная установка флажка гомогенности }// Конец Щ! йіош)

}// Конец іґ(і=сгк-1)

} //Конец цикла &г(т11=0;Ксгк;}++)

сгк=псгк; //новое количество элементор в гк к++;// Очередной номер итерации

for(int il=0;il<ncrk;il++) //Новое значение rk rk[il]=nrk[il]; }//Конец else // Кортеж не один }//Конец цикла while(cAE) //Упорядочивание аг по es sr d; // Структура для обмена for(intk=l;k<car;k++) for(int i=0;i<car-k;i++)

if(ar[i] .cs>ar[i+1 ] .es)

{

d= ar[i];

ar[i]=ar[i+l];

ar[i+l]=d;

} //Конец if(ar[i].cs>octocolstat[i+l].cs) // Преобразование ar в интервалы кривых, заполняющих пространство unsigned int esb; //Коды начала и окончания интервала кривой csb=ar[0].cs;

if(car==l) // То кортеж один и интервал один {

har[c_har] .bcs=csb;

har[c_har].ecs=ar[0].cs+IntPower(oct,ar[0].lev)-1 ;

har[c_har].sid=ar[0].sid;

har[c_har] .mu=ar[0].sid;

csb=ar[0].cs;

c_har++;

} //Конец if(car==l) // To кортеж один и интервал один else //Кортеж не один for(int j =l;j<car;j++)

{ int j j j j = ar[J-l].cs+IntPower(oct,ar[)-l].lev);//Для отладки if( ar[j-l].cs+IntPower(oct,ar[j-l].lev)=ar|j].cs &&

ar[j-l].sid==ar[j].sid && ar[j-l].sid=ar[j].mu); else {//Формирование интервала кривой и запись его в har har[c_har] .bcs=csb;

har[c_har] .ecs=ar[j -1 ] .cs+IntPower(oct,ar[j-1 ] .lev)-1;

har[c_har].sid=ar[j-l].sid;

har[c_har] .mu=ar[j -1 ] .sid;

csb=ar[j].cs;

c_har++;

} //Конец else { //Формирование интервала кривой

if (j==car-l) // Для того, чтобы записать последний интервал {

har[c_har] .bcs=csb;

har[c_har].ecs=ar[j].cs+IntPower(oct,ar|j].lev)-l;

har [char] .sid=ar [j ] .sid; har[c_har] .mu=ar[j ]. sid; c_har++;

} //Конец if (j==car) }//Конец цикла for(int j =0;j<car;j++) Преобразование ar };// Конец функции classificator

TForml *Forml; //-------------------------------------------------------------

_fastcall TForml ::TForml(TComponent* Owner)

: TForm(Owner)

{

void_fastcall TForml::ButtonlClick(TObject * Sender)

{

classificator(); // Вывод для проверки г Memo 1 ->Lines->Add(" г "); for(int i=0; i<cont;i++)

Memo 1 ->Lines->Add(IntToStr(r[i].cs)+" "+ IntToStr(r[i].lev) +" "+IntToStr(r[i].sid)+" "+ FloatToStr(r[i].mu));

Memo 1 ->Lines->Add(" rk "); // Вывод для проверки rk for(int i=0; i<cont;i++)

Memo 1 ->Lines->Add(IntToStr(rk[i] ,csk)+" "+ IntToStr(rk[i] .lev) +" "+IntTo Str(rk[i]. sid)+" "+ IntToStr(rk[i] .cskp)); Memo 1 ->Lines->Add(" ar "); // Вывод для проверки ar for(int i=0; i<cont;i++)

Memo 1 ->Lines->Add(IntToStr(ar[i].cs)+" "+ IntToStr(ar[i].lev) +" M+IntToStr(ar[i].sid)+" "+ FloatToStr(ar[i] ,mu)); Memo 1 ->Lines->Add(" har "); // Вывод для проверки har for(int i=0; i<cont;i++)

Memol->Lines->Add(IntToStr(har[i].bcs)+" M+ IntToStr(har[i].ecs)+" " +" "+IntToStr(har[i].sid)+" "+ FloatToStr(har[i].mu)); Memo 1 ->Lines->Add(" H3 "); for(int i=0; i<cont;i++)

Memol->Lines->Add(IntToStr(H3(r[i].cs))+" "+IntToStr(r[i].lev) +" "+IntToStr(r[i].sid)+" "+ FloatToStr(r[i].mu)); Memo 1 ->Lines->Add(" rk ");

}

//-------------------------------------------------------------------------

147