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

• Федоров, Роман Константинович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Федоров, Роман Константинович

ВВЕДЕНИЕ.

ГЛАВА 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. Решение задачи на основе созданного программного комплекса автоматического выделения дорожной сети населенного пункта.

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

Список литературы диссертационного исследования кандидат технических наук Федоров, Роман Константинович, 2005 год

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.