Содержание к диссертации
Введение
ГЛАВА 1 Обзор подходов и существующих алгоритмов в задачах обработки пространственно - распределенных данных 10
1.1 Основные определения и обозначения 10
1.2 Основные подходы и алгоритмы 12
1.2.1 Методы обработки растровых изображений 12
1.2.2 Методы сегментации и аппроксимации графических примитивов 15
1.2.3 Логические методы распознавания , 28
1.3 Возможности популярных пакетов программ векторизации, первичного
распознавания и анализа пространственно - распределенных данных 38
ГЛАВА 2 Алгоритмическое обеспечение программного комплекса 43
2.1 Графовая модель ПРД 47
2.2 Построение графовой модели ПРД 49
2.2.1 Предварительная обработка исходных данных 49
2.2.2 Построение диаграммы Вороного и скелета диаграммы Вороного 55
2.2.3 Выделение линейно-площадных объектов 59
2.2.4 Выделение вероятных локальных разрывов 63
2.2.5 Сегментация 66
2.2.6 Выделение признаков сегментов 67
2.3 Классификация сегментов на основе логического вывода 78
2.3.1 Формальная логическая модель ПРД 80
2.3.2 Алгоритмы встроенных в машину вывода предикатов 80
2.3.3 Логический вывод на формальной модели ПРД ...87
ГЛАВА 3 Программный комплекс: реализация и использование 89
3.1 Назначение и область применения программного комплекса 89
3.2 Архитектура программного комплекса 90
3.3 Методика использования 91
3.4 Реализация , 92
3.4.1 Структура программного комплекса 92
3.4.2 Реализация базовых алгоритмов 95
3.4.3 Интерфейс прикладного программирования ПО
ГЛАВА 4 Применение программного комплекса 113
4.1 Выделение дорожной сети , 113
4.2 Создание электронной дендрологической карты территории ИНЦ СО РАН на основе топографической карты 118
Заключение 122
Литература
- Методы сегментации и аппроксимации графических примитивов
- Предварительная обработка исходных данных
- Архитектура программного комплекса
- Создание электронной дендрологической карты территории ИНЦ СО РАН на основе топографической карты
Введение к работе
Актуальность задачи и предмет диссертации. Известно, что значительная часть информации в электронной форме, имеет пространственную привязку. Пространственная привязка может использоваться для интеграции разнородной информации. Эти данные в дальнейшем будем называть пространственно-распределенными (ПРД), а пространственную привязку геометрическим представлением. Существует огромное количество задач, решаемых с использованием ПРД, и разработано большое количество соответствующих программных продуктов; при этом зачастую ПРД выступают более ценным ресурсом, чем само программное обеспечение. Отсутствие ПРД необходимого качества и с нужными характеристиками является сдерживающим фактором, тормозящим развитие перспективных проектов. Рассмотрим некоторые из возникающих здесь проблем.
Разнообразие геометрических представлений элементов ПРД. Существует множество способов геометрического представления объектов ПРД: полигоном, полилинией и т.д. Интересующий объект также может состоять из совокупности других объектов или быть частью комплексного объекта, наследуя некоторые его свойства. Представление объекта в значительной степени влияет на эффективность обработки информации. Практика показывает, что для обеспечения необходимой эффективности обработки ПРД необходимо производить перевод (трансляцию, преобразование) одного представления ПРД в другое.
Разнообразие семантических представлений объекта. Исходные данные, как правило, задаются в системе классификации объектов, отличающейся от требуемой для решения конкретной задачи. Необходимы процедуры преобразования одних классификаций в другие или адаптация процедур обработки ПРД к имеющимся классификациям. Часто процедура преобразования классификации невозможна без анализа геометрического представления объекта.
Нетопологичность представления данных. Для решения конкретных задач обработки ПРД, кроме геометрии объектов, требуется задание топологических отношений между объектами. Примерами топологических отношений выступают отношение соседства объекта с другими объектами, вложенность объектов друг в друга и т.д. Существующие же ПРД, в основном, включают только внутриобъектную топологию, т.е. топологические отношения лишь в пределах тех базовых составных элементов (полилиний, полигонов), которые состоят из примитивов (узлов и отрезков прямых). Отсутствие информации о межобъектной топологии, в частности, не позволяет решить такую задачу как нахождение кратчайшего пути между двумя пунктами на карте автодорог. Задача перевода в данных в топологическое представление не является тривиальной.
Таким образом, при решении разных задач с использованием ПРД и в случае отсутствия необходимого геометрического представления, межобъектной топологии или классификации становится необходимым осуществление преобразования ПРД из одного представления в другое, что, как правило, выполняется вручную.
Примером такой задачи является задача планирования движения автотранспорта. Решение задачи - это путь в графе, представляющем дорожную сеть города. Вершинами графа дорожной сети являются перекрестки и тупики, а ребрами — осевые линии дорог и улиц. Исходные ПРД не содержат топологической информации, представляющей этот граф. Дорожное полотно задается при помощи ограничивающих объектов, например, бордюров. Таким образом, для того, чтобы формализовать исходные данные задачи планирования маршрутов перевозок в городе, необходимо провести анализ ПРД с целью выделения дорожной сети.
Приведенные примеры обосновывают актуальность моделирования и автоматизации анализа ПРД.
Предметом исследования являются способы представления пространственно-распределенных данных, методы и алгоритмы преобразования представлений и алгоритмы классификации объектов на основе топологических отношений.
Цель работы заключается в комплексном исследовании проблемы представления и анализа ПРД, разработке соответствующих моделей ПРД, алгоритмов анализа и обработки ПРД на основе этих моделей и соответствующего программного комплекса. В качестве применения разработанного алгоритмического программного обеспечения рассматривается задача представления и анализа ПРД населенного пункта с целью выделения дорожной сети.
Методы исследования. При выполнении диссертационной работы использовались методы математического моделирования, машинной графики, вычислительной геометрии, математической логики, теории программирования.
Научная новизна. Разработаны новые алгоритмы сегментации ПРД, формирующие структурные особенности дорожной сети, на основе графовой модели ПРД. Впервые предложена логическая модель дорожной сети (база знаний) в языке хорновских дизъюнктов. Реализованы разработанные оригинальные модели и алгоритмы в виде программного комплекса.
Защищаемые положения. На защиту выносятся следующие результаты.
1. Алгоритмы сегментации области ПРД, которые позволяют получить совокупность примитивов и сегментов, описывающие структурные особенности ПРД. Данные алгоритмы выделяют линейно-площадные объекты и возможные разрывы контуров объектов на основе графовой модели ПРД.
Логическая модель и алгоритмы классификации графических примитивов, сегментов и объектов, состоящих из графических примитивов. Алгоритмы классификации включают процедуры логического вывода над формализованными знаниями и оперируют примитивами и сегментами, а также их свойствами и взаимными топологическими отношениями.
Реализация представленных алгоритмов в виде программного комплекса для представления и анализа ПРД.
Решение задачи автоматического выделения дорожной сети населенного пункта, реализованное на основе созданного программного комплекса.
Апробация результатов работы. Основные положения и результаты докладывались на всероссийских и международных конференциях по математике и информатике:
Международная конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова, Новосибирск, 2001.
Выездное заседание Совета по информатизации СО РАН, Иркутск, 2002 (Отделение Всероссийской конференции).
Сибирская региональная ГИС-конфереиция, Иркутск, 2002.
IF AC Workshop Modelling and Analysis of Logic Controlled Dynamic Systems, Irkutsk, Lake Baikal, Russia, 2003.
Всероссийская конференция "Математические и информационные технологии в энергетике, экономике, экологии", Иркутск, 2003.
Всероссийская конференция "Инфокоммуникационные и вычислительные технологии и системы", Улан-Удэ - Байкал, 2003.
Семинар "Ляпуновские чтения & Презентация информационных технологий ", Иркутск, 2002.
Школа-семинар молодых ученых России "Проблемы устойчивого развития региона", 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 глав, заключения, списка литературы и приложения.
Методы сегментации и аппроксимации графических примитивов
Наиболее простым и естественным способом сегментации является сегментация с помощью порога [47]. Сегментация с помощью порога является полезной в различении объектов от фона во многих классах сцен.
Например, некоторое изображение содержит некий объект, который состоит из одного пикселя, который имеет гомогенный уровень серого и фон с отличным уровнем серого. количество пикселей /\ sФОН / \ Объект градации серого Такое изображение обычно обладает бимодальной гистограммой (рис. 1.1). Это изображение может быть разделено на две области простым порогом, который классифицирует все пиксели с уровнем серого больше, чем Т, как объектные пиксели, и пиксели с уровнем серого меньше, чем Т — как фон. Большинство пороговых методов используют информацию о гистограмме изображения. Идеальным случаем является бимодальная форма гистограммы из-за того, что уровень серого во впадине может быть выбран напрямую в качестве порога сегментации, но такие бимодальные гистограммы редко существуют в реальных приложениях. В изображении уровень серого может быть разделен на несколько интервалов, соответствующих объектам. Однако, эти интервалы могут пересекаться, что значительно усложняет процедуру проведения сегментации.
Для нахождения границ объектов на изображении может применяться оператор Дж. Канни [52]. Оператор Дж. Канни работает в несколько стадий.
С начала к изображению применяется фильтр Гаусса. Затем используется 2-D оператор Робертсона к размытому изображению чтобы выделить области изображения с высокой первой пространственной производной. Границы объектов соответствуют гребням в градиентом поле изображения. Алгоритм трассирует вдоль вершины гребней и устанавливает в ноль все пиксели, которые не находятся на вершинах гребней. В результате получаются тонкие линии. Процесс трассирования контролируется двумя порогами: ТІ и Т2, где Т1 Т2. Трассирование начинается с точки, имеющее значение больше, чем ТІ. Трассирование продолжается в обоих направлениях от начальной точки до тех пор, пока значение текущих точек больше, чем Т2.
Алгоритмы линейной аппроксимации осевых и граничных линий
Для преобразования наборов точек в векторную форму требуются алгоритмы линейной аппроксимации, результатом выполнения которых являются ломаные линии и/или многоугольники. В общем виде задачу линейной аппроксимации упорядоченной последовательности точек можно считать задачей оптимизации, так как эту задачу можно сформулировать следующим образом: из последовательности точек, образующей исходную ломаную, необходимо выделить такую последовательность, которая бы аппроксимировала исходную ломаную с заданной точностью, при этом минимизировав число точек в результирующем наборе. В такой формулировке точки результирующего набора часто называют критическими. Классификацию методов аппроксимации выполнили, с одной стороны, по критерию, на основе которого принимается решение об отнесении данной точки из исходного набора к набору критических точек, с другой стороны, по характеристикам алгоритмов просмотра массива точек для принятия решения о критических точках.
Все критерии принадлежности точки к критическому набору можно разделить на следующие три группы. К первой, самой многочисленной группе, относятся критерии, основанные на вычислении расстояния между аппроксимирующей кривой и точками исходного набора. Ко второй группе относятся критерии, основанные на вычислении площади между двумя ломаными — исходным набором точек и аппроксимирующей ломаной. Третья группа образована критериями, основанными на вычислении разностей углов между направлениями на рассматриваемую точку и продолжением очередного сегмента аппроксимирующей ломаной, а также критериями, основанными на вычислении кривизны получаемой аппроксимации.
Предварительная обработка исходных данных
На растровом материале границы объектов представляются с помощью сплошной линии, пунктирной линии, последовательности точек или с использованием специализированных топографических знаков. На векторном материале границы объектов представляются упорядоченным набором отрезков, набором парабол, кривых Безье и т.п. Для работоспособности ПК на всевозможных типах данных необходимо выбрать начальное представление объектов ПРД. Следует учитывать, что границы могут иметь разрывы, пересечения и т.п. Наиболее общим представлением является представление с помощью точек. Так как все рассмотренные представления границ объектов можно аппроксимировать с помощью точек. Что не всегда просто реализовать для других представлений границ объектов. В программном комплексе реализованы два способа ввода исходных данных: - чтение и предобработка векторных файлов; - векторизация растровых изображений с использованием модифицированного алгоритма нахождения границ Дж. Канни [52].
Чтение и предобработка векторных файлов
Исходные векторные данные могут быть считаны из одного или нескольких файлов, представленных в формате SHAPE. Граничные линии в этом формате данных заданы с помощью упорядоченного набора отрезков. В процессе ввода отрезки считываются последовательно. При этом если длина отрезка больше чем Dm3X, отрезок делится на интервалы таким образом чтобы длина каждого интервала была не больше чем тах. Для каждой точки, аппроксимирующей отрезок, производится ее запись в массив точек.
Векторизация растровых изображений с использованием модифицированного алгоритма нахождения границ Дж, Канни
При обработке растровых изображений одной из основных задач является выделение границ между однородными областями изображения. Рассмотрим функцию яркости изображения b = f(x,y), которая является непрерывной и дифференцируемой на множестве X х Y. Если зафиксировать одну из переменных, например у, то график функции яркости на границе двух однородных областей X} и Хк по переменной х можно представить в виде, как на рис.2.1, где JC, EXJ - точка, принадлежащая первой области, х3 =Хк - точка, принадлежащая второй области, хг - базовая точка, разделяющая две области.
С учетом свойств представления растровых изображений далее рассматриваются дискретные значения яркости для функции b- f(i,j), iJcN (рис. 2.2.).
Для получения базовых точек реализован модифицированный алгоритм нахождения границ Дж. Канни. Границы объектов, найденные применением известного алгоритма Дж. Канни, имеют пиловидную форму из-за дискретного представления изображения, что снижает качество дальнейшего анализа изображений. Для получения границ, которые более соответствуют реальным границам объектов, предлагается учитывать практически подтвержденное свойство базовой точки совпадать с точкой перегиба функции изображения. Для нахождения точки перегиба строится аппроксимация функции яркости по дискретным значениям. Так как функция яркости является не линейной, что требует для нахождения точки перегиба сложных вычислений, то для увеличения быстродействия алгоритма предложено следующее упрощение - использование линейной зависимости приращения базовой точки от значений яркостей х,, х2, х3. Рассмотрим два случая расположения базовой точки:
Архитектура программного комплекса
Основной схемой использования программного комплекса является встраивание другие программные системы в качестве подсистемы обработки ПРД. Взаимодействие между системами осуществляется через СОМ интерфейс прикладного уровня.
Исходя из этого и предложенной архитектуры ПК, функциональных возможностей, разработана методика использования программного комплекса. 1. На первом этапе необходимо проанализировать предметную область задачи с целью выявления свойств сущностей, составляющих задачу, свойства и структуру связей между ними. 2. На основе проведенного анализа необходимо произвести выборку тех видов пространственных объектов, которые могут быть использованы для получения промежуточного результата. 3. Если необходимо, чтобы машина вывода получала информацию о семантических свойствах объектов, то следует описать таблицы и поля входных данных, содержащие эту информацию. 4. Для каждой подзадачи необходимо выразить свойства и связи сущностей в виде правил Пролога и определить последовательность целей вывода. 5. Через интерактивный интерфейс пользователя или ИПП производится запуск подсистемы обработки ПРД. При этом вся полученная информация сохраняется в оперативной памяти вычислительного устройства. 6. Сохранение результатов.
Разработанная методика обеспечивает достаточно широкое и гибкое применение ПК для задач, поставленных во введении. Программный комплекс состоит из нескольких функциональных блоков.
Блок ввода/вывода данных осуществляет чтение векторных данных в формате SHAPE и растровых данных в формате BMP. Позволяет одновременно обработку нескольких слоев данных. Также блок предназначен для отображения результатов обработки пользователю и сохранения полученных результатов.
Блок предварительной обработки данных содержит следующие алгоритмы фильтров и детекторов базовых точек на изображении: Перевод цветного изображения в градации серого. Размытие Гауса [47], позволяющее сгладить изображение, тем самым убрать шум. Нахождение границ на цветном изображении. Нахождение границ изображении в градации серого. Граничным является ребро между соседними пикселями, величины яркостей которых разделяются заданным пороговым значением. В контур границы включается средняя точка разделяющего ребра. Построение поля порогов [58]. Вышеописанный алгоритм использует фиксированное пороговое значение. Недостатком его является то, что значения яркостей точек, лежащих по разные стороны границы, могут находиться по одну сторону порога и, следовательно, алгоритмом не вычисляться. Предполагается, что пороговое значение на изображении в точке х,у определяется гладкой функцией fix, у) , которая является непрерывной и дифференцируемой на множестве X х Y . Данная функция в литературе называется полем порогов. Построение этой функции осуществляется с помощью аппроксимации полученных каким-либо другим алгоритмом пороговых значений. Для растровых данных в блоке реализован механизм обработки по сценарию. Последовательность применения различных фильтров и детекторов базовых точек и их параметры можно сохранить в инициализационный файл программного комплекса и затем его выполнять по указанию пользователя.
Блок построения диаграммы Вороного содержит алгоритм заметающей прямой (sweepline algorithm) Стивена Форчуна (Steven Fortune), основанный на преобразовании Форчуна. Алгоритм строит диаграмму с линейной сложностью по числу точек.
Блок построения скелета диаграммы Вороного осуществляет выявление важных ребер диаграммы Вороного. В ходе работы блока используется дополнительная информация из блока предварительной обработки данных.
В блоке сегментации реализуются свойства и методы объектов, алгоритмы нахождения разрывов, алгоритмы нахождения линейно-площадных объектов, алгоритмы сегментации.
Интерпретатор Пролога - это механизм решения задачи при помощи языка Пролог. Помимо интерпретатора содержит редактор для ввода и редактирования правил.
Создание электронной дендрологической карты территории ИНЦ СО РАН на основе топографической карты
В качестве основы дендрологической карты была взята векторная топооснова масштаба 1:2000. При ближайшем рассмотрении обнаружилось, что на карте объекты, представляющие газоны, отсутствуют, так же, как и улицы. В топооснове газоны представлены косвенно, так же как, и дорожная сеть.
Было сделано предположение, что вся область, кроме домов, хозяйственных построек, улиц, дорог и тропинок занята газонами.
Для получения карты газонов использовались полигональные и линейные объекты. Среди полигональных объектов на топооснове имеются такие объекты, как здания, площадки и т.д., которые не принадлежат газонам. В семантике входных данных содержалась информация о типе объектов: ЗДАНИЕ, БОРДЮР, ПЛОЩАДКА и т.д. Для того, чтобы интерпретатор Пролога мог получать информацию о типе объектов, было создано следующее описание данных на языке DDL. Node Domain="Layer name" Value- City lines" File Path="c:\Users\Fedorov\Data\Map2000L.shp" Domain=, Metricsn TypeValue="shp" Date=" 12.04.2003 16:047 Table Domain- Semantics" Value- Месторождения FieId Domain="Object Id" Name="ID" TypeValue="REAL7 FieId Domain="Name" Name="Name" Type Value-" STRING "/ Field Domain="Purpose" Name="name" TypeValue="STRING"/ Field Domain="ObjectType" Name="OTP" TypeValue="STRING7 /Table /Node Node Domain="Layer name" Value- City regions" File Path=,,c:\Users\Fedorov\Data\Map2000R.shp"
Domain= Metrics" TypeVaIue="shp" Date=" 12.04.2003 16:04"/ TabIe Domain="Semantics" Value- Месторождения Field Domain="Object Id" Name="ID" TypeValue="REAL7 Field Domain="Name" Name="Name" TypeValue="STRING ,/ Field Domain="Purpose" Name="name" TypeVaIue="STRING7 Field Domain="Object Type" Name="OTP" TypeValue="STRING"/ /Table /Node В соответствии с предположением, дорожная сеть не принадлежит газонам. Следовательно, необходимо распознавать дорожную сеть с целью исключения ее объектов из совокупностей объектов, являющимися газонами. Для этого в базу знаний включены правила распознавания дорожной сети, а также и использованы цели (см. пункт 4.1). Кроме правил выделения дорожной сети, в базу знаний разработаны и добавлены следующие правила. Объект X является газоном, если он не является объектом, принадлежащим дорожной сети, и не является зданием. is_lawn(X):- getobjflag(X,F), Fol, getinfo(X, Object Type , Т),То ЗДАНИЕ ,To ПЛОЩАДКА .
Выполненная работа посвящена созданию алгоритмического и модельного обеспечения, инструментального средства для поддержки программирования подсистем анализа и обработки ПРД. Полученные результаты могут применяться в системах автоматизированного проектирования и в геоинформационных системах. В рамках диссертации получены и на защиту выносятся следующие результаты.
1. Алгоритмы сегментации области ПРД, которые позволяют получить совокупность примитивов и сегментов, описывающие структурные особенности ПРД. Данные алгоритмы выделяют линейно-площадные объекты и возможные разрывы контуров объектов на основе графовой модели ПРД. Полученные структурные особенности позволяют более эффективно использовать ПРД в решении практических задач.
2. Логическая модель и алгоритмы классификации объектов, состоящих из графических примитивов и сегментов. Алгоритмы классификации включают процедуры логического вывода над формализованными знаниями и оперируют примитивами и сегментами, а также их свойствами и взаимными топологическими отношениями. Данный подход для решения задачи вместо используемого в существующих системах процедурного программирования позволяет пользователю сконцентрироваться на задании отношений и свойств определяемых объектов на языке Пролог.
3. Реализация представленных алгоритмов в виде программного комплекса для представления и анализа ПРД.
4. Решение задачи на основе созданного программного комплекса автоматического выделения дорожной сети населенного пункта.
Дальнейшие исследования планируется вести в направлении расширения класса решаемых задач за счет разработки новых методов обработки сегментов, расширения набора встроенных предикатов и общих правил базы знаний. Перспективным направлением работы является решение задач автоматической векторизации растровых карт и автоматизации процесса генерализации карт, т.е. перехода от подробных, или крупномасштабных, карт к обобщенным, или мелкомасштабным, картам.
