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

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

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

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

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

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

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

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

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

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

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

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

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

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] по списку литературы, три из которых опубликованы в жестко рецензируемых журналах. Программный комплекс зарегистрирован в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ), № 2 003 611 851.

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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