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

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

Федоров Роман Константинович

ПРОГРАММНЫЙ КОМПЛЕКС ГРАФОВОГО И ЛОГИЧЕСКОГО ПРЕДСТАВЛЕНИЯ И АНАЛИЗА ПРОСТРАНСТВЕННО-РАСПРЕДЕЛЕННЫХ

ДАННЫХ

05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ

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

Иркутск 2005

Работа выполнена в Институте динамики систем и теории управления (ИДСТУ) Сибирского отделения Российской академии наук.

Научный доктор технических наук Бычков Игорь Вячеславович

руководитель: профессор

Официальные доктор технических наук оппоненты:

Ноженкова Людмила Федоровна

кандидат технических наук доцент

Феоктистов Александр Геннадьевич

Ведущая организация: Институт вычислительной математики и математической геофизики СО РАН

Защита состоится 11 июля 2005 г. в 16 часов на заседании диссертационного совета Д 003.021.01 в ИДСТУ СО РАН по адресу: 664033, г. Иркутск, ул. Лермонтова, 134, зал заседаний Ученого совета, ком. 407.

С диссертационной работой можно ознакомиться в библиотеке ИДСТУ СО РАН.

Автореферат разослан "10" июня 2005 г.

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

Г.А. Опарин

1еов-1/

(о ^ев

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

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

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

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

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

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

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

Приведенные примеры обосновывают актуальность моделирования и автоматизации анализа ПРД.

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

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

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

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

Защищаемые положения. На защиту выносятся следующие результаты.

1. Алгоритмы сегментации области ПРД, которые позволяют получить

совокупность > примитивов и сегментов, описывающие структурные

особенности ПРД. Данные алгоритмы выделяют линейно-площадные объекты и возможные разрывы контуров объектов на основе графовой модели ПРД.

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

3. Реализация представленных алгоритмов в виде программного комплекса для представления и анализа ПРД.

4. Решение задачи на основе созданного программного комплекса автоматического выделения дорожной сети населенного пункта.

Апробация результатов работы. Основные положения и результаты докладывались на всероссийских и международных конференциях по математике и информатике:

1. Международная конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова, Новосибирск, 2001.

2. Выездное заседание Совета по информатизации СО РАН, Иркутск, 2002 (Отделение Всероссийской конференции).

3. IFAC Workshop Modelling and Analysis of Logic Controlled Dynamic Systems, Irkutsk, Lake Baikal, Russia, 2003.

4. Всероссийская конференция "Математические и информационные технологии в энергетике, экономике, экологии", Иркутск, 2003.

5. Всероссийская конференция "Инфокоммуникационные и вычислительные технологии и системы", Улан-Удэ - Байкал, 2003.

6. Семинар "Ляпуновские чтения & Презентация информационных технологий ", Иркутск, 2002.

7. Школа-семинар молодых ученых России "Проблемы устойчивого развития региона", 2001, Улан-Удэ.

8. Школа-семинар "Математическое моделирование и информационные технологии", Иркутск, 2002.

Внедрение. Программная система внедрена в Институте географии СО РАН.

Практическая значимость. Программный комплекс может использоваться для реализации подсистем векторизации и анализа представления ПРД. В частности, такие подсистемы применимы для подготовки данных о структуре дорожной сети при решении транспортных и других задач, выделения классов объектов ПРД с заданными свойствами, генерализации карт и т.д. Программный комплекс апробирован на задачах выделения дорожной сети населенного пункта, создания дендрологической карты территории ИНЦ СО РАН.

Личный вклад соискателя и других. Из совместных с соавторами [2-4] результатов (см. список основных публикаций) в диссертационную работу включены только реализация блоков построения диаграммы и скелета диаграммы Вороного, интерпретатора Пролог-программ, осуществленных в неделимом соавторстве с к.т.н. А.Е. Хмельновым. Все остальные результаты и положения диссертации получены лично автором.

Благодарности. Автор благодарит д.т.н. Бычкова И.В. за руководство диссертационной работой и помощь в подготовке рукописи, к.т.н. Хмельнова А.Е. за сотрудничество и помощь в разработке ряда блоков программного комплекса, к.т.н. Черкашина Е.А. за помощь при подготовке рукописи, а также чл.-к. РАН Васильева С.Н. за критические замечания и предложения.

Структура и объем работы. Диссертация изложена на 130 страницах. Она состоит из введения, 4-х глав, заключения, списка литературы и приложения.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ В главе 1 приводится обзор современных методов, алгоритмов и программных средств обработки и анализа ПРД.

В главе 2 предлагаются и обосновываются графовые и логические модели, алгоритмы их использования для представления и анализа ПРД.

В рамках известной методологии моделирования решение задачи разбивается на три этапа: «модель - алгоритм - программа».

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

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

Рассмотрим основные способы геометрического представления объекта ПРД в виде:

• точки;

• совокупности ломанных (полилиний);

• совокупности многоугольников (полигональное представление);

• композиции объектов (комплексный объект);

• части комплексного объекта;

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

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

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

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

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

4. Выделение полигонального объекта из состава комплексного объекта. Сложность данного преобразования состоит в том, что необходимо произвести декомпозицию комплексного объекта на графические примитивы или, если это невозможно, то — на более простые объекты.

На основании выполненного в диссертационной работе анализа делаются следующие выводы.

• Полигональное представление является предпочтительным с точки зрения

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

эффективно преобразовать во все другие представления.

• Декомпозиция комплексных объектов ПРД является ключевой процедурой

при преобразовании представления объектов.

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

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

7

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

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

1) создание графовой модели на основе исходных ПРД;

2) разработка алгоритмов построения и обработки графовой модели (алгоритмы разбиения на сегменты и т.д.);

3) создание формальной логической модели ПРД на основе графовой модели;

4) разработка алгоритмов построения и обработки логической модели;

5) реализация моделей и алгоритмов.

В п. 2.1 приводится графовая модель ПРД.

Определение. Точки р = (х,у), ре Л2, с помощью которых задаются объекты ПРД, будут называться базовыми. Множество базовых точек обозначим как Р, количество базовых точек — ыр = |р|| .

Определение. Незамкнутой планарной ломаной / называется ломаная на плоскости, задаваемая структурой (р0>Р„ЛР,У,*I >{г,},"=!). где точки плоскости р0, р„ являются несовпадающими концевыми точками ломаной, последовательность {/>,}"=л является последовательностью несовпадающих промежуточных точек ломаной, {гХ, - последовательность непересекающихся отрезков данной ломаной, причем отрезок г, ((' = 1, п -1) проходит между точками /V, и р, ,при условии, что никакая промежуточная точка р, не совпадает с концевой, / € Ь -множество незамкнутых планарных ломанных.

Определение. Замкнутой планарной ломаной V называется ломаная на плоскости, задаваемая структурой ({/?, },"=|, },"=!), где последовательность {р,}"-\ является последовательностью несовпадающих точек ломаной, -

последовательность непересекающихся отрезков данной ломаной, причем отрезок г, (/ = 1, и -1) проходит между точками и р,, а отрезок гп соединяет две точки р„ и р,. I' е и - множество замкнутых планарных ломанных.

Определение. Точки pt и р, структуры (р0, p„,{p,V,l! < {'',},"-1) незамкнутой планарной ломаной или структуры ({р,}%\Лг,/Г-i) замкнутой планарной ломанной называются соседними если |' - j\ = 1 или ' — 7 = ±1 mod я соответственно.

Множество входных данных для алгоритмов обработки ПРД определим как тройку М = M{P,L,L'}.

Диаграмма Вороного используется в качестве вспомогательной структуры данных, позволяющей производить анализ геометрии объектов более эффективно. Так операция поиска ближайшей точки имеет сложность не более, чем О(С). Что позволяет проводить более качественный анализ данных. Диаграмму Вороного, построенную на множестве базовых точек Р, будем обозначать как D = D{P,E, V}.

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

1) базовые точки, разделенные ребром, являются соседними;

2) расстояние между базовыми точками ребра меньше, чем D^ (константы, задаваемой пользователем).

Еь множество граничных ребер. EbciE.

Ds = Ds {Ps ,ES,VS} - скелет диаграммы Вороного, где Р, е Р,Е, е E,V, eV . Критерии построения скелета диаграммы Вороного приведены в пункте 2.1.2.

Определение. Сегментом s', задаваемой структурой (p'0Js), называется связанная область, ограниченная замкнутой планарной ломанной /' и содержащая точку Ро.

Множество сегментов обозначим как s е S' . Геометрия площадных объектов ПРД представляется с помощью сегментов.

Множество линейно-площадных сегментов обозначим как s'е S1, а соответствующее одноместное отношение как Я,.

Множество всех остальных сегментов обозначим как s" 6 S" , соответствующее одноместное отношение как R, . S1 u S" = 5 , S1 r\S" = 0.

Определение. Сегменты s,, Sj являются соседними, если существует хотя бы одна базовая точка ph, принадлежащая обоим сегментам. Отношение соседства будем обозначать как R„b.

Теперь определим графовую модель ПРД как структуру G = G(M,D,S,Rnb,R„R,).

В п. 2.2 рассматривается построение графовой модели ПРД. Алгоритмы сегментации и выделения графических примитивов базируются на анализе свойств диаграммы Вороного и скелета диаграммы Вороного.

Общая схема алгоритма построения графовой модели ПРД состоит из следующих этапов:

- предварительная обработка исходных данных;

- скелетизация области обработки;

- выделение линейно-площадных объектов;

- выделение вероятных разрывов.

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

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

..¿¿'""м-^ГЧГ --------------— ..Я u I I UlC^iift- 7ГГУ-» .1^1--1 J Е.Ч1

Рис. 1: Диаграмма Вороного и скелет диаграммы Вороного.

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

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

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

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

Для нахождения линейно-площадных объектов используется производная функции ширины объекта. Производная является инвариантной к масштабу данных и позволяет отказаться от настройки алгоритма под конкретные данные. Участки, соответствующие скелетной линии, будут являться линейно-площадными, если производная этой функции на этих участках будет равняться нулю: /'(0 = 0 ■ На практике используется некоторая константа, задаваемая пользователем: | /'(01< С.

Схема алгоритма выглядит следующим образом.

Шаг 1. Получение скелетного ребра.

Шаг 2. Трассирование скелетной линии и запоминание в буфер пар где

м> - ширина линейно-площадного объекта в точке /.

Шаг 3. Аппроксимация полученных пар совокупностью полиномов 4 степени.

Шаг 4. Повторная трассировка скелетной линии с использованием гладкой аппроксимации и выделение участков, где модуль значения производной аппроксимированной функции меньше заданной константы | /'(/) |< С

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

площадным объектам.

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

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

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

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

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

Определение. Трехместное отношение ), называется отношением

противоположности Лор)ИШ , если з, - линейно-площадной объект, а сегменты и находятся по разные стороны .

Введем следующие функции, возвращающие свойства сегментов. /«.(*,)- функция определения ширины линейного-площадного сегмента . 1шц (О - функция определения угла наклона линейного-площадного сегмента ь, по отношения оси Ох.

/ДО- функция определения длины линейного-площадного сегмента .

Определение. Двухместное отношение >, называется отношением

линейности Ясоп1, если линейно-площадные объекты, а и ^ лежат приблизительно на одной прямой.

Определение. Логической моделью ПРД назовем структуру / = где Яи это дополнительные

отношения, задаваемые экспертом.

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

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

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

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

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

- linearobject(V), истинный тогда и только тогда, когда объект V - линейно-площадной;

- nblist(V,L), всегда истинный, возвращает список соседей, имеющих хотя бы одну общую базовую точку с данным объектом;

- contslist(V,L), всегда истинный, возвращает список соседей, имеющие хотя бы одно общее с данным объектом скелетное ребро;

- getobjflag(V,F), всегда истинный, возвращает тип объекта;

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

- against(A,B,C), истинный тогда и только тогда, когда объекты А, С находятся по разные стороны линейно-площадного объекта В;

- width(V,W), всегда истинный, возвращает среднюю ширину линейно-площадного объекта;

- length(V,L), всегда истинный, возвращает длину скелетной линии линейно-площадного объекта;

- getobjangle(V,F), всегда истинный, возвращает угол наклона линейно-площадного объекта;

- areonline(A,B), истинный тогда и только тогда, когда оба объекта лежат на одной линии;

- getinfo(X, Name, Т), истинный тогда и только тогда, когда в семантике объекта имеется значение атрибута Name объекта X. Предикат возвращает значение этого атрибута в Т.

Информацию о сегменте интерпретатор может задать с помощью предиката setflag(V,F), который всегда истинный. Для получения этой информации используется предикат getobjtype(V,T). Также в интерпретатор встроен предикат, выполняющий операцию объединения двух объектов, имеющих общее скелетное ребро: concat(V,V2), истинный тогда и только тогда, когда объединяются два объекта (к объекту V добавляется объект V2 как его продолжение).

В п. 2.3.3 рассматривается использование логического вывода на формальной логической модели свойств и отношений сегментов.

Количество объектов в ПРД может превышать десятки тысяч. Запуск цели на интерпретаторе Пролога для классификации всей совокупности объектов может

привести к комбинаторному взрыву или, по крайней мере, будет иметь слишком большую сложность. Тем не менее, в большинстве случаев для классификации объекта ПРД достаточно рассмотреть его свойства и свойства окружающих его объектов. Поэтому вывод некоторой цели языка Пролог по классификации запускается отдельно для каждого объекта. Если конкретная цель выведена для заданного объекта, то считается, что объект обладает семантикой, определяемой целью, т.е. весь набор интересующих свойств объекта - это список выведенных для этого объекта целей. Использование такого механизма предполагает, что правила на языке Пролог будут задаваться пользователем таким образом, чтобы интерпретатор в процессе вывода анализировал в первую очередь свойства соседних объектов. Вывод цели запускается в цикле для каждого объекта. Для получения кода текущего объекта в Прологе встроен предикат сиг_оЬ](Х), который возвращает текущий объект. Логический вывод дпя каждого объекта производится до получения первого решения или неудачи поиска.

В главе 3 рассматриваются назначение (п. 3.1), архитектура (п. 3.2), методика использования (п. 3.3) и реализация (п. 3.4) разработанной системы.

Основным назначением инструментальных средств (ИС) обработки ПРД является идентификация объектов ПРД на основе топологии (топологических отношений). Кроме того, ИС позволяет:

• идентифицировать линейно-площадные объекты;

• переводить представление объектов при помощи ломанных в полигональное представление и обратно;

• производить поиск объектов в ПРД с использованием семантики и топологической информации;

• производить классификацию объектов ПРД на основе логического вывода;

• выделить дорожную сеть на топооснове населенного пункта.

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

По сравнению с известными существующими системами пространственного анализа данных основными особенностями ПК являются-

• в процессе обработки ПРД существует возможность использования топологической информации об объекте;

• выделение линейно-площадных объектов;

• использование логического вывода для анализа ПРД.

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

языке Object Pascal, среда разработки - Delphi. Архитектура программного комплекса представлена на рис. 3.

Интерактивный интерфейс предназначен для взаимодействия пользователя с программным комплексом через пользовательское меню.

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

ПРД.

ИПП - интерфейс прикладного программирования.

( Внешняя ._____программа

Пользователь

=

Подсистема 4"" «вола вывода

ИПП

IE

Подсистема обработки ПРД

Интерактивный интерфейс

Ж

Подсистема управления

Машина вывода

\ Программный комплекс ^

Рис. 3: Архитектура программного комплекса. Методика использования

Основной схемой использования программного комплекса является встраивание в другие программные системы в качестве подсистемы обработки ПРД. Взаимодействие между системами осуществляется через СОМ интерфейс прикладного уровня.

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

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

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

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

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

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

6. Сохранение результатов.

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

Структура программного комплекса.

Программный комплекс состоит из нескольких функциональных блоков (см. рис. 4).

Рис. 4: Структура программного комплекса.

Блок ввода/вывода данных осуществляет чтение векторных данных в формате SHAPE и растровых данных в формате BMP. Позволяет одновременно обработку нескольких слоев данных. Также блок предназначен для отображения результатов обработки пользователю и сохранения полученных результатов.

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

Блок построения диаграммы Вороного содержит алгоритм заметающей прямой (sweepline algorithm) Стивена Форчуна (Steven Fortune), основанный на преобразовании Форчуна. Алгоритм имеет линейную сложность относительно числа точек.

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

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

Интерпретатор Пролога - это механизм выполнения программ на языке Пролог. Также включает в себя редактор для ввода и редактирования правил.

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

Для взаимодействия с программной библиотекой выбрана технология Component Object Model (СОМ). Данная технология позволяет использовать разработанные алгоритмы из многих популярных средств разработки приложений. Например, Borland Delphi позволяет автоматически создавать необходимые модули для работы с СОМ интерфейсами.

Программный комплекс состоит из более чем 100 модулей программного

кода.

Глава 4 посвящена описанию двух практических задач, решенных с использованием ИС.

В п. 4.1 рассматривается задача выделения дорожной сети. Одной из задач, решаемых при помощи ГИС, является оптимизация движения транспорта. Для решения этой задачи дорожную сеть требуется представить в виде нагруженного графа, где вершинами являются перекрестки и тупики, а дугами - осевые линии улиц. Однако существующая в г. Иркутске топографическая карта городских территорий масштаба 1:2000 не позволяет получить необходимое представление дорожной сети непосредственно из исходных данных. Проблема заключается в том, что на имеющейся карте объекты, представляющие улицы, отсутствуют. Улицы представлены косвенным образом: объектами, ограничивающими дорожное полотно. Примерами таких объектов выступают бордюры, площадки, дома и т.п. Более того, информация об отдельном ограничивающем объекте часто не позволяет сказать, с какой стороны от него находится дорожное полотно.

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

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

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

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

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

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

§е1сгозз1тез([Х|Сиг],Ргеу,[Х|Апз],С,М):- С<М, ИпеагоЬКХ), Сп ¡б С + 1, £е1сгоззНпез(Сиг,[Х|Ргеу],Апз,Сп,М),!.

§е1сгоззПпез([Х|Сиг],Ргеу,Апз,С,М):-С<М, агеа1о^(Х), Сп ¡б С + 1, §е1сгоБ51 ¡пез(Сиг, [Х|Ргеу], Апз,Сп,М),!.

§е1сгозз1тез([Х|Сиг],Ргеу,Апз,С,М):-С<М, соШзНб^Х.ЫЬ),

§е1аЬзепсез(МЬ,8р,Ргеу), аррепс!(Сиг,8р,ЫСиг), Сп ¡б С + 1, §е1сгоззИпез(МСиг,[Х|Ргеу], Апз,Сп,М),!. £е1сгоззНпез(_,_,[],С,М):- С=М,!. §е1сгоззНпез([],_,[],_,_).

Правила фильтрации линейно-площадных объектов, примыкающих к перекрестку. В соответствии с этим правилом все объекты, параллельные текущему объекту, и не являющиеся его продолжением, отбрасываются. Шг([Х|8],[Х|0],Веё):- по1(1з_раг(Веё,Х)), !, Шг(8,0,Веё). Шг([Х|8],[Х|0],Ве§):- 13_раг(Ве&Х), агеопИпеСВе&Х), !, Шг(8,0,Веё). Шг([Х|8]АВеё):- Шг(8АВеё).

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

¡з_з1гее1(Х):-Ипеаго^(Х), соп&Нз1(Х,МЬ), шетЬег(У,ЫЬ),

§е1сгоззПпез([У],[Х],А,0,20), Я^ААХ), 1епёЙ1(0,С1), С1>1, тетЬег(г^Ь), 1<>У, по1(13_ёеаёепс!(2,Х,[])), зеШа§з(0,1).

Правила определения перекрестков. Если к площадному объекту подходит не менее двух дорожных линейно-площадных объектов, то этот площадной объект является перекрестком.

¡з_сгозз(Х) :- по1(агеа1оЬХХ)), соШзПб^Х.МЬ), шетЬег(У,ЫЬ), тетЬег(2,ЫЬ), гоУ, ¡зо1уЯаё(У,1), ¡эо1уАаё(2,1), $еЮЬ]Аа§(Х,1).

¡з_сгозз(Х):-по1(агеа1о^(Х)), соп1зПз1(Х,ЫЬ), тетЬег(У,КЬ), 1еп§И1(КЬ,С), С=1, ¡зоЬ|Ааё(У,1), setobjflag(X,l).

На основе набора правил распознавания дорожной сети и в соответствии общей схемой решения задачи определена последовательность логического вывода целей языка ПРОЛОГ для выделения дорожной сети. ?- сигоЬКХ), ¡з_з1гее1(Х).

?- сигоЬКХ), ¡Бо1уЙа§(Х,1), со^бПз^Х.ЫЬ), тешЬег(У^Ь),

тагкоп1те(У,Х,Х,0).

?- СиГО^(Х), ¡Б_СГ055(Х).

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

Рис. 5: Дорожная сеть.

Используя этот набор правил и целей, удалось правильно найти почти все дорожные объекты (не менее 95%). Ошибки распознавания происходили как следствие таких ошибок исходных данных, как отсутствие большого участка границы объекта, прохождение бессмысленных (не относящихся к границам дорожного полотна) линий и т.д.

В п. 4.2 рассмотрена задача создания электронной дендрологической карты территории ИНЦ СО РАН на основе топографической карты.

В Институте географии СО РАН разработан проект парковой зоны Академгородка. В соответствии с проектом Академгородок разделен на 5 зон. Предполагалось, что в дендрологической карте такие участки, как газоны, лесонасаждения и т.д., должны быть окрашены в определенные цвета в зависимости от зональной принадлежности. В дальнейшем эти участки будем условно называть газонами.

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

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

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

Кроме правил выделения дорожной сети, в базу знаний разработаны и добавлены следующие правила.

Объект X является газоном, если он не является объектом, принадлежащим дорожной сети, и не является зданием.

is_lawn(X):- getobjflag(X,F), Fol, getinfo(X,'Object Type',

T),To'ЗДАНИЕ',То'ПЛОЩАДКА'.

Для выделения газонов после выделения дорожной сети используется единственная цель:

?- curobj(X), is_lawn(X), setobjflag(X,2).

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ Выполненная работа посвящена созданию алгоритмического и модельного обеспечения, инструментального средства для поддержки программирования подсистем анализа и обработки ПРД. Полученные результаты могут применяться в системах автоматизированного проектирования и в геоинформационных системах. В рамках диссертации получены и на защиту выносятся следующие результаты.

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

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

3. Реализация представленных алгоритмов в виде программного комплекса для представления и анализа ПРД.

4. Решение задачи на основе созданного программного комплекса автоматического выделения дорожной сети населенного пункта.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Федоров Р.К. Программный комплекс для анализа топологии пространственно-распределенных данных // Материалы Всероссийской конференции "Инфокоммуникационные и вычислительные технологии и системы". -Улан-Удэ, 2003. -С. 99-103.

2. Бычков И.В., Хмельнов А.Е., Федоров Р.К. Об одном подходе к анализу топологии пространственно-распределенных данных с использованием логического вывода // Вычислительные технологии. —2005. —Т. 10, N 1, —С. 116-130.

3. Федоров Р.К., Хмельнов А.Е. Программа построения осевых линий дорог // Программа и тезисы докладов школы-семинара "Математическое моделирование и информационные технологии". —Иркутск, 2002. —С. 33-34.

4. Федоров Р.К., Хмельнов А.Е. Программный комплекс для анализа топологии пространственно-распределенных данных // Труды Всероссийской конференции "Математические и информационные технологии в энергетике, экономике, экологии". -Иркутск, ИСЭМ СО РАН, 2003. -С. 147-152.

5. "Программный комплекс графового и логического представления и анализа пространственно-распределенных данных" зарегистрирован в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ), № 2003611851.

Редакционно-издательский отдел Института динамики систем и теории управления СО РАН. 664033, г. Иркутск, ул. Лермонтова, д. 134.

Подписано к печати 09.06.2005. Формат бумаги 60x84 1/16, объем 1,1 пл.

_Заказ 4. Тираж 100 экз._

Отпечатано в ИДСТУ СО РАН.

IM2 43S

РНБ Русский фонд

2006-4 10089

ВВЕДЕНИЕ.

ГЛАВА 1 ОБЗОР ПОДХОДОВ И СУЩЕСТВУЮЩИХ АЛГОРИТМОВ В ЗАДАЧАХ ОБРАБОТКИ ПРОСТРАНСТВЕННО - РАСПРЕДЕЛЕННЫХ ДАННЫХ.

1.1 Основные определения и обозначения.

1.2 Основные подходы и алгоритмы.

1.2.1 Методы обработки растровых изображений.

1.2.2 Методы сегментации и аппроксимации графических примитивов.

1.2.3 Логические методы распознавания.

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

ГЛАВА 2 АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПРОГРАММНОГО КОМПЛЕКСА.

2.1 Графовая модель ПРД.

2.2 Построение графовой модели ПРД.

2.2.1 Предварительная обработка исходных данных.

2.2.2 Построение диаграммы Вороного и скелета диаграммы Вороного.

2.2.3 Выделение линейно-площадных объектов.

2.2.4 Выделение вероятных локальных разрывов.

2.2.5 Сегментация.

2.2.6 Выделение признаков сегментов.

2.3 Классификация сегментов на основе логического вывода.

2.3.1 Формальная логическая модель ПРД.

2.3.2 Алгоритмы встроенных в машину вывода предикатов.

2.3.3 Логический вывод на формальной модели ПРД.

ГЛАВА 3 ПРОГРАММНЫЙ КОМПЛЕКС: РЕАЛИЗАЦИЯ И ИСПОЛЬЗОВАНИЕ.

3.1 Назначение и область применения программного комплекса.

3.2 Архитектура программного комплекса.

3.3 Методика использования.

3.4 Реализация.

3.4.1 Структура программного комплекса.

3.4.2 Реализация базовых алгоритмов.

3.4.3 Интерфейс прикладного программирования.

ГЛАВА 4 ПРИМЕНЕНИЕ ПРОГРАММНОГО КОМПЛЕКСА.

4.1 Выделение дорожной сети.

4.2 Создание электронной дендрологической карты территории ИНЦ СО РАН на основе топографической карты.

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

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

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

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

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

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

Приведенные примеры обосновывают актуальность моделирования и автоматизации анализа ПРД.

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

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

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

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

Защищаемые положения. На защиту выносятся следующие результаты.

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

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

3. Реализация представленных алгоритмов в виде программного комплекса для представления и анализа ПРД.

4. Решение задачи автоматического выделения дорожной сети населенного пункта, реализованное на основе созданного программного комплекса.

Апробация результатов работы. Основные положения и результаты докладывались на всероссийских и международных конференциях по математике и информатике:

1. Международная конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова, Новосибирск, 2001.

2. Выездное заседание Совета по информатизации СО РАН, Иркутск, 2002 (Отделение Всероссийской конференции).

3. Сибирская региональная ГИС-конференция, Иркутск, 2002.

4. IF AC Workshop Modelling and Analysis of Logic Controlled Dynamic Systems, Irkutsk, Lake Baikal, Russia, 2003.

5. Всероссийская конференция "Математические и информационные технологии в энергетике, экономике, экологии", Иркутск, 2003.

6. Всероссийская конференция "Инфокоммуникационные и вычислительные технологии и системы", Улан-Удэ - Байкал, 2003.

7. Семинар "Ляпуновские чтения & Презентация информационных технологий ", Иркутск, 2002.

8. Школа-семинар молодых ученых России "Проблемы устойчивого развития региона", 2001, Улан-Удэ.

9. Школа-семинар "Математическое моделирование и информационные технологии", Иркутск, 2002.

Внедрение. Программная система внедрена в Институте географии СО

РАН.

Практическая значимость. Программный комплекс может использоваться для реализации подсистем векторизации и анализа представления ПРД. В частности, такие подсистемы применимы для подготовки данных о структуре дорожной сети при решении транспортных и других задач, выделения классов объектов ПРД с заданными свойствами, генерализации карт и т.д. Программный комплекс апробирован на задачах выделения дорожной сети населенного пункта, создания дендрологической карты территории ИНЦ СО РАН.

Публикации. По теме диссертации опубликовано 10 печатных работ [9, 10, 11, 34, 39, 40, 41, 42, 51, 56] по списку литературы, три из которых опубликованы в жестко рецензируемых журналах. Программный комплекс зарегистрирован в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ), № 2003611851.

Личный вклад соискателя и других. Из совместных с соавторами [9, 10, 11, 40, 41, 42, 51, 56] результатов (по списку литературы) в диссертационную работу включены только реализация блоков построения диаграммы и скелета диаграммы Вороного, интерпретатора Пролог-программ, осуществленных в неделимом соавторстве с к.т.н. А.Е. Хмельновым. Все остальные результаты и положения диссертации получены лично автором.

Благодарности. Автор благодарит д.т.н. Бычкова И.В. за руководство диссертационной работой и помощь в подготовке рукописи, к.т.н. Хмельнова А.Е. за сотрудничество и помощь в разработке ряда блоков программного комплекса, к.т.н. Черкашина Е.А. за помощь при подготовке рукописи, а также чл.-к. РАН Васильева С.Н. за критические замечания и предложения.

Структура и объем работы. Диссертация изложена на 130 страницах. Она состоит из введения, 4 глав, заключения, списка литературы и приложения.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Реализация представленных алгоритмов в виде программного комплекса для представления и анализа ПРД.

4. Решение задачи на основе созданного программного комплекса автоматического выделения дорожной сети населенного пункта.

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

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин —М.: Наука, 1970. -384 с.

2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы, М.: Изд. дом "Вильяме", 2000.

3. Бадд. Т. Объектно-ориентированное программирование в действии, Спб.: Питер, 1997.

4. Баскакова Л.В., Журавлев Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // Журнал вычислительной математики и математической физики. —1981. -т. 21,№5.-С. 1264-1275.

5. Братко И. Программирование на языке Пролог для искусственного интеллекта, М.: Мир. —1990.

6. Бычков И.В., Васильев С.Н., Кузьмин В.А., Ступин Г.В. Проект интегрированной геоинформационной системы ИНЦ СО РАН для поддержки фундаментальных исследований // Вычислительные технологии. —1998. —том 3, №5. —С. 11-18.

7. Бычков И.В., Кухаренко Е.Л. Разработка распределенной ГИС ИНЦ СО РАН // Вычислительные технологии. —1998. —том 3, №5. —С. 18-22.

8. Бычков И.В., Кухаренко Е.Л., Ступин Гр. В. WWW-доступ к ресурсам ГИС Mapinfo // Программные продукты и системы. —1999. —№2. —С. 20-23.

9. Бычков И.В., Федоров Р.К., Хмельнов А.Е. Автоматическое выделение дорожной сети на крупномасштабной карте городских территорий // Материалы Международной конференции "ГИС для устойчивого развития территорий", Новороссийск Севастополь. —2003. —С. 266270.

10. Толстых В., Толстых И. Аппроксимация склеивающими функциями. Режим доступа:http://multicriterion.tripod.corn/approximationbyglue2.htm.

11. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов "Кора"// Алгоритмы обучения распознаванию образов. —М.: Сов.радио. -1973,-С. 8-12.

12. М.Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука.-1979. -448 с.

13. Горбачев В.Г. Что такое "топологические" отношения в цифровой картографии или для чего топологические отношения нужны в геоинформатике?. Режим доступа: http://www.integro.ru/metod/toporelations.htm.

14. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений // Сб. "Дискретный анализ". -Выпуск 7, Новосибирск, ИМ СО АН СССР. -1966. -С. 3-11.

15. Донской В.И. Алгоритмы обучения, основанные на построении решающих деревьев // Журнал вычислительной математики и математической физики. —1982. —т. 22, №4. —С. 963-974.

16. Дуда Р., Харт П. Распознавание образов и анализ сцен. —М.: Мир. -1976. -511 с.

17. Дюкова Е.В. Алгоритмы распознавания типа "Кора": сложность реализации и метрические свойства // Распознавание, классификация, прогноз (матем. методы и их применение). —М.: Наука. —1989. —вып.2. -С. 99-125.

18. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания // Проблемы кибернетики. —М.: Наука. —1982. -выпуск 39.-С. 165-199.

19. Дюкова Е.В. Об одной параметрической модели алгоритмов распознавания типа "Кора", М.:ВЦ АН СССР. —1988. —23 с.

20. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, М.: Наука. -1978. -вып. 33. -С. 5-68.

21. Журавлев Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение, Ташкент: ФАН. —1974. —119 с.

22. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. —1971. —№3. —С. 111.

23. Кочетков Д.В. Распознающие алгоритмы, инвариантные относительно преобразований пространства признаков // Распознавание,классификация, прогноз: Мат. методы и их применение. М.: Наука. -1988.-выпуск 1,—С. 82-113.

24. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: Наука. —1981. —С. 160.

25. Макаллистер Дж. Искусственный интеллект и Пролог на микроЭВМ. —М.: Машиностроение. —1990. —С. 240.

26. Метод комитетов в распознавании образов, Свердловск: ИММ УНЦ АН СССР.-1984.-С. 165.31 .Минский М., Пейперт С. Персептроны. —М.:Мир. —1971. —С. 262.

27. Новиков Ю.Л. Эффективные алгоритмы векторизации растровых изображений и их реализация в геоинформационной системе. Дисс. на соиск. уч. степ, к.т.н., Томск: Томский гос. Университет, 2002, с. 170.

28. Прэтт У. Цифровая обработка изображений. —М.: Мир. —т. 1,2. —1982.

29. Сираи Й. Анализ массивов интенсивности с использованием знаний о сценах // Психология машинного зрения / Пер. с англ. / Под ред. П. Уинстона. -М.: Мир. -1978. -С. 112-136.

30. Сироджа И.Б. Структурно-аналитический метод машинного распознавания объектов с разнотипными признаками // Теория R-функций и актуальные проблемы прикладной математики. Киев: Наукова думка. —1986. —С. 212-243.

31. Скворцов A.B. Триангуляция Делоне и ее применение. —Томск: Изд-во Том. ун-та. -2002. -С. 128.

32. Тикунов B.C. Моделирование в картографии. —М.: Изд-во МГУ. —1997. -405 с.

33. Федоров Р.К., Хмельнов А.Е. Программа построения осевых линий дорог RALB // Труды 6 Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии", Великий Новгород. —2002. —том 2. —С. 564-568.

34. Федоров Р.К., Хмельнов А.Е. Программа построения осевых линий дорог // Программа и тезисы докладов школы-семинара "Математическое моделирование и информационные технологии". -Иркутск. -2002. -С. 33-34.

35. Фу К. Структурные методы в распознавании образов. —М.: Мир. -1977.

36. Фуку нага К. Введение в статистическую теорию распознавания образов. —М.:Наука. —1979. —367 с.

37. Чегис И. А., Яблонский C.B. Логические способы контроля электрических схем // Труды Матем. ин-та им. В.А.Стеклова АН СССР. -1958.-т. 51.-С. 270-360.

38. Чуй Ч. Введение в вэйвлеты. —М.: Мир.—2001.—412 с.

39. Чэн Ш.-К. Принципы проектирования систем визуальной информации. -М.: Мир. -1994. -408 с.

40. Asada Н., Brady М. The Curvature Primal Sketch // IEEE Transactions on Pattern Analysis and Machine Intelligence. —1986. —vol. 8, No.l. —pp.2 -14.

41. Bezdek J.C. A Review of Probabilistic, Fuzzy, and Neural Models for Pattern Recognition // FUZZY LOGIC AND NEURAL NETWORK HANDBOOK, Chen C.H. eds, ch.2, McGraw-Hill, 1996.

42. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function Algorithms // Plenum Press, New-York. 1981.

43. Bychkov I.V., Fedorov R.K., Khmelnov A.E. Recognition of road network on topographic map using logical inference // Draft Papers of IFAC

44. Workshop "Modelling and Analysis of Logic Controlled Dynamic Systems", 2003. Irkutsk, Russia, pp. 203 209.

45. Canny J. F. A computational approach to edge detection // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, vol. 8, pp. 679-698.

46. Dori D. Liu W. Stepwise Recovery of Arc Segmentation in Complex Line Environments // International Journal on Document Analysis and Recognition, 1998, vol. 1, No.l, pp.62 -71.

47. Dosch Ph., Masini G.,Tombre K. Improving Arc Detection in Graphics Recognition // Proceedings of 15th International Conference on Pattern Recognition, Barcelona (Spain), 2000, vol.2, pp. 243 -246.

48. Dunham J.G. Optimum Uniform Piecewise Linear Approximation of Planar Curves // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, vol.8, No.l, pp.67 -75.

49. Fedorov R.K., Khmel'nov A.E. Road Axial Line Builder // Pattern Recognition and Image Analysis, vol. 13, No 2, 2003, pp. 256-258.

50. Ganster H., Gelautz M., Pinz A., Binder M., Pehamberger H., Bammer M., Krocza J. Initial Results of Automated Melanoma Recognition //Proceedingsof the 9th Scandinavian Conference on Image Analysis, Uppsala, Sweden, June 1995, vol.1, pp. 209-218.

51. Open Source Computer Vision Libraryhttp://www. intel. com/res earch/mrl/res earch/opencv/

52. Rosin P.L.,West G.A.Segmentation of Edges into Lines and Arcs // Image and Vision Computing, 1989, vol.7, No.2, pp. 109-114.

53. Ryazanov V.V. Recognition Algorithms Based on Local Optimality Criteria // Pattern Recognition and Image Analysis, 1994, vol.4. No. 2, pp. 98-109.

54. Sen'ko O.V. A Prediction Algorithm Based on the Procedure of Weighted Voting Using a System of Hyperparallelepipeds in a Multidimensional Feature Space // Pattern Recognition and Image Analysis, 1993, vol.3, no. 3, pp. 283-284.

55. Sklansky J., Gonzalez V. Fast Polygonal Approximation of Digitized Curves // Pattern Recognition, 1980, vol. 12, pp.327-331.

56. Fortune Steve J. A Sweepline Algorithm for Voronoi Diagrams // Algorithmica 2, 1987, pp. 153-174.

57. Wall K., Danielsson P. A Fast Sequential Method for Polygonal Approximation of Digitized Curves // Computer Vision, Graphics and Image Processing, 1984, vol. 28, pp. 220-227.

58. Yachida M., Saburo T. Application of Color Information to Visual Perception // Pattern Recognition, 1971, vol. 3, No. 3, pp.307-323.