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

МИНИСТЕРСТВО ВЫСШЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ТАГАНРОГСКИЙ ГОСУДА1Ч: I ВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ЭГ6 од

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

п СсН

АНДРЮЩННКО Алексей Александрович

УДК 519.85:528.9 "Разработка и исследование моделей представления картографической информации для построения оптимальных ГИС".

Специальности:

05.13.16 - "Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях".

05.13.17 - "Теоретические основы информатики".

АВТОРЕФЕРАТ

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

Таганрог 1998г.

Работа выполнена на кафедре ЭИиК Таганрогского государственного радиотехнического университета.

Научный руководи!ель:

Профессор, доктор технических наук, академик PARK, заслуженный деятель науки и техники РФ БЕРШТЕЙН Леонид ('амойлович.

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

Доктор технических наук, профессор ФИНАЕВ Валерий Иванович (ТРТУ, г. Таганрог).

Кандидат технических наук, старший научный сотрудник САПРЫКИН Владимир Абрамович (ТРТУ, г. Татнрог).

Ведущее предприятие:

Ростовский государственный университет путей сообщения (РГУПО, г. Ростов).

Защита состоится СИ^&Хс&р-эк____ 1998г. в____ часов

на заседании диссертационного совета Д063.13.02 по защите диссертации при Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, пер. Некрасовский 44, ауд.

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

Д-406.

Автореферат разослан " £__" 1998г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

А.Н. Целых

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

Актуальность работы. Геоинформационные системы (ГИГ), то есть системы сбора, управления, анализа и отображения пространственно распределенной информации, находят в последнее время все большее применение в различных сферах человеческой деятельности. Наиболее яркие примеры использования ГИС информационно-справочные, кадастровые системы, системы поддержки принятия решений и моделирования природных и техногенных процессов. Однако, недостаточно высокая пропускная способность информационных каналов, низкие объемы носителей данных, технологическая Сложность отдельных этапов обработки информации в ГИС являются сдерживающими факторами в их развитии. Для более широкого внедрения ГИС необходимо разработать новые эффективные методы представления картографической информации.

Целью работы является разработка новых моделей представления данных в ГИС, а именно методов и алгоритмов, позволяющих:

1. Улучшить качество карт, их точность и информативность;

2. Повысить "интеллектуальность" ГИС, упростить наиболее сложные технологические процедуры;

3. Увеличить объем картографической информации, которой может оперировать ГИС.

Для достижения поставленной цели были выполнены следующие задачи:

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

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

3. Анализ и разработка моделей представления картографической информации в ГИС, обеспечивающих наилучшие характеристики по критериям занимаемого пространства и времени доступа.

Методы исследовании в диссертации основаны на использовании теории обработки изображений, теории распознавания образов и теории сжатия данных.

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

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

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

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

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

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

Практическую ценност ь работы представляют':

1. Алгоритм п программа предварительной обработки растровых картографических изображений;

2. Алгоритм и программа векгоргпации растровых картографических изображений;

3. Алгоритм и программа компрессии (декомпрессии) атрибутной и пространственной информации ГИГ.

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в

хоздоговорных и госбюджетных рабохах, проводимых на кафедре ЭИнК ТРТУ: НИР х/д 12542, ПИР г/б 44251, НИР г/б 15550.

Разработанные алгоритм и программа векторизации карто1рафпческих изображений внедрены в НКБ ВС (г. Таганрог), что подтверждается соответствующим актом.

Апробация основных теоретических и практических результатов работы проводилась: на научных семинарах кафедры 'ЭИиК (ТРТУ, г.Таганрог, 1995-1997гг.); на второй всероссийской научной студенческой конференции "Техническая кибернетика,

радиоэлектроника и системы управления" (ТРТУ, г.Таганрог, 1994г.); на 41-й НТК профессорско-преподавательского состава (ТРТУ, г.Таганрог, 1994г.); на всероссийской научно-технической конференции с международным участием "Компьютерные технологии в инженерной и управленческой деятельности" (г.Таганрог, 1997г.); на научном совете НКБ ВС (г.Таганрог, 1996г.).

Публикации. Основные положения диссертации опубликованы в 5 печатных работах.

Структура н обьем диссертационной работы. Диссертационная работа состоит из вводной главы, трех основных глав, практической главы, выводов, списка литературы из 53 наименований и приложений. Работа содержит 212 страниц, включая 33 рисунка, 12 таблиц, 53 страницы приложений.

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

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

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

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

Р ~ П'Де у) - интенсивность изображения в точке

(х,у).

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

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

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

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

В начале главы выделены основные отличия растровой и векторной моделей представления графической информации,

рассмотрена проблема их совместимости и перехода между ними, дано формальное определение векторной модели:

Векторное изображение задается как множество объектов

/>'=ИиИиИ

Каждое из объединяемых множеств содержит объекты конкретного типа, определяемого но геометрической форме объекта. В случае с географическими картами выделяются 3 типа объектов:

1. Объекты точечного пита. Каждый объекг определяется также как и точка растрового изображения v'' = , г де

(,r,g,b) е Я х G х В,(х,у) е X х Y; R,G,R и X,Y • базисы цветового

и геометрического пространства соответственно. Гео-обьектами точечного типа могут обозначаться, например, города.

2. Объекты тина ломаной линии. Каждый объект онределяе!ся как множество отрезков (задаваемых координатами их концов), составляющих ломаную линию.

V1 = {{Pl>P2)>{P2>Pi)>-(P/~2>Pf.l)'{Pf-l>Pj)}>

р], pj- е Р, / - число точек излома. Гео-объекты данного типа могут являться, например, дорогами, реками.

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

v° = {(PMP2)>(P2>PÍ)>-(P/.I>P/-I)>(PJ -x>Pj)} > rae

/?, ,Pj £ Р, j - число точек излома. Гео-обьекгы данного типа

наиболее распространены. Это любые регионы, покрывающие определенную площадь изображения.

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

являются: Vectory (Consistent Software, Россия), HasyTrace (Easy Trace Group, Россия). По каждому примеру определены схема, параметры и процедуры технологического процесса.

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

1. Определяются параметры векторизации;

2. В автоматическом либо ручном режиме просматриваются все объекты на изображении;

3. Для каждого выделяемого объекта автоматически определяются ег о тип и возможгго некоторые специфичные типу параметры;

4. В зависимости от типа объекта автоматически выбираются и применяются алгоритмы построения векторной формы объекта по его растровому изображению;

5. Процесс повторяется до тех пор, ггока не будет построена векторная карта, содержащая все объекты растрового изображения.

Согласно приведенной выше схеме разработаны следующие процедуры алгоритма векторизации:

1. Процедура поиска произвольного объекта на изображении;

2. Процедура выделения произвольного объекта из изображения;

3. Процедуры идентификации типа и параметров объекта;

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

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

выделения связной обласш объекта Р° из изображения Л; Р° с: Р.

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

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

Пространство образов

Пространство признаков

Пространство классов

/ , Блок выделения / , Классификатор / .

Изображение, признаков Признаки ■ Классы

Рнс.1. Схема идентификации объектов.

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

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

1. Значение функции интенсивности объекта изображения g(p);

2. Площадь объекта Я;

3. Слепень вытянутое™ объекта Л : Р" —> [0,1], где Р° С1 Р есть множество точек растра изображения, составляющих объект;

4. Степень периодичности структуры объекта: т \ Р° —> [ОД],

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

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

переменные: а

5 '

а,

(X.

характеризующие соответственно

точечноегь объекта, его вытянутость и периодичность.

(X с — < , где К - площадь

[0,если : £ £ ]

классифицируемого объекта, [Я^Л1,] - интервал значений площади объекта, при котором он может быть идентифицирован как точечный. [\,если : Л > Л,

IX х , где Л - значение признака вытянутости

[0,если : Я < Лх

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

[ 1, если: г = 1

(Хт — < , где Г - значение признака периодичности

[0,если : т Ф 1

для классифицируемого объекта. Класс точечных объект

ов определяется как набор объектов, офаниченных по площади и лишенных периодичности.

(рр = ац & аг

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

<р' = (а3 & аг) V (а5 & ах & ах)"

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

(р° =а5 & (ал V (ах & ат)) = а5 & (ал V ) & (ал V ат)

= а5 & 1 & (ах V аг) = а3 & (ах V а1)

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

<рр= 0, <р" &(р° = 0, <р' &(р° =0. Таким образом была доказана необходимость и достаточность выбранного набора признаков.

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

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

множестве значений решающих функций (рр,(/)' ,<р". Он построен таким образом, чтобы избежать излишних вычислений значений признаков, так, как показано на схеме, изображенной на рисунке 2.

Результат процедуры выделения объектов установленного типа есть сформированное множество Р' ~ (у'' }и {}'' }и }-

Для выделения точечного объекта необходим!1 вычислить центр ограничивающего его прямоугольника р( е Р°. Координаты центра

можно считать векторными координатами объекта, у'' = рс .

При проходе по элементам (подобъектам) линии, их центральные точки р £ Р используются для формирования множества точек,

представляющих линию в векторной форме Р7 С Р°. Из

элементов Рт — ,]?-, | формируется множество

V' = {(Р\>Рг)АР2>Ръ)>-(Р/ 2 >Р.1 . . )} •

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

определяющих границу объекта Р' С1 Р". Из

элементов Р1 = — р( формируется множество

V" = {(Рх>Р2)>(Р2>Р3)>-(Р/.2>Р/ <)>(Р,-ПР/)}-

Далее в третьей главе производится оценка трудоемкости операций, выполняемых автоматически и вручную для разработанною алгоритма векторизации, производится ее сравнительный анализ с трудоемкостью в системах "ЕаБуТгасе" и "УесЮгу", на основании чего делается вывод о преимуществе нового алгоритма векторизации в плане уменьшения объема ручного труда.

11олигон Линия Точка

Рис. 2. Схема классификации картографических объектов.

В четвертой главе производится анализ и разпаботкл модели нредстаиления картографической информации в ГТ1С, обладающей следующими свойствами:

1. Оптимальность с функциональной точки зрения;

2. Минимальный объем передаваемых данных;

3. Высокая скорость выполнения запросов к данным.

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

Для оптимизации модели по объему занимаемой памяти был проанализирован ряд алгоритмов из теории сжат: данных и выделен ряд следующих базовых способов компрессии:

1. Метод двоичного сжатия;

2. Словарный метод;

3. Кодирование переменной длины;

4. Вероятностный метод (кодирование Хаффмена);

5. Дифференциальный метод;

6. Кодирование с потерями.

Для каждого базового способа произведена оценка коэффициента компрессии и условия применимости рассматрив емою метода в зависимости от набора входных данных.

Па основании анализа базовых способов ,-гмпроссии и ограничений, накладываем!.IX структурой данных ГПС, разработал алгоритм компрессии картогрлфщгеской информгц^и, включающийся в-совмещении ряда базовых подходов для компрессии символьных, числовых и пространственных данных следующим ооразо?.::

1. Компрессия символьных данных: словарный метод, вероятностный метод со словарем из значгинл атрибутов, вероятностный метод со словарем из слоз, вероятностный .метод со слог.арем из лексем, вероятностный мсгод со словарем и; символов;

2. Компрессия .числовых данных: дифференциальный метод, кодирование переменной длины с фикспрозап::ы.м префиксом, либо с префиксом, работающим на основа вероятное!"кого метода;

3. Компрессия пространственных данных. Этот тин данных рассмотрен особо, специализированы его характерные особенности:

• Пространственные атрибуты содержат числовые значения, являющиеся координатами географического объекта;

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

• Атрибуты упорядочены географически по координатным осям, т.е. расстояние между двумя соседними атрибутами составляет незначительную величину;

• Распределение значений координат в атрибутах близко к нормальному.

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

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

Для оптимизации Г'ИС по времени доступа к данным в работе предложена модель представления информации, содержащая следующие структурные особенности:

*1. Раздельное хранение атрибутной и пространственной информации, что необходимо вследствие функциональных особенностей ГИС, выполняющих пространственные и атрибутные запросы в разные моменты времени.

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

3. Наличие дополнительных индексов по неключевым атрибутам отношения.

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

которой на 150-200% превышает коэффициент, полученный при помощи аналогичных программ.

В пятой главе рассматриваются особенное! и программной реализации разработанных моделей представления картографической информации в ГИС. Производится постановка инженерной задачи, выбор стратегии реализации, а также приводится структурное описание программных модулей в рамках объектно-ориентированного подхода.

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

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

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

3. Примеры результатов векторизации растровых картофафнческих изображений;

4. Примеры словарей и таблиц распределений данных, создаваемых компрессорами в процессе предварительного анализа отношений;

5. Примеры программного кода, реализующего поведение основных объектов технологической цепочки подготовки данных в ГИС.

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

Получены следующие научные и практические результаты:

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

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

3. Разработан алгоритм эффективного сжатия картографической информации, использующий знания о вероятностном распределении атрибутной информации н знания о структуре пространственных данных ITIC. Алг оритмы сжатия, разработанные с учетом ограничений, накладываемых структурой данных ГИС, позволяют получать коэффициент компрессии, превышающий на 150-200% коэффициент, получаемый на том же наборе данных при помощи известных программ - компрессоров.

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

Результаты диссертации изложены в 5 печатных работах.

1. Андрющепко A.A., Целых А.Н., "Алгоритмы и программа предварительной обработки и анализа изображений в ГИС", тез. доклада, Вторая всероссийская научная студенческая конференция, Таганрог, 1994г.

2. Андрющенко A.A., "Векторизация карт п ГИС", Сборник научных трудов молодых ученых, аспирантов и студентов ТРТУ", второй вьптуск, Таганрог', 1996.

3. Андрющенко A.A., "Векторизация географических карт", Известия ТРТУ N1, 1997г.

4. Андрющенко A.A., "Оптимальная по времени обработки запросов ШС", Известия ТРТУ N1,1998г.

5. Андрющенко A.A., "Векторизация карт в географических информационных системах", Известия ТРТУ N1, 1998г.

Типография ТРТУ Зак N 285 Тираж 100