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

• Автор: Федоров, Роман Константинович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Иркутск
• Количество страниц: 144 с. : ил.

Содержание
ВВЕДЕНИЕ.
ГЛАВА 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 Создание электронной дендрологической карты территории ИНЦ СО РАН на основе топографической карты
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Из совместных с соавторами [9, , , , , , , ] результатов (по списку литературы) в диссертационную работу включены только реализация блоков построения диаграммы и скелета диаграммы Вороного, интерпретатора Пролог-программ, осуществленных в неделимом соавторстве с к. А.Е. Хмельновым. Все остальные результаты и положения диссертации получены лично автором. Благодарности. Автор благодарит д. Бычкова И. В. за руководство диссертационной работой и помощь в подготовке рукописи, к. Хмельнова А. К.Т. Н. Черкашина Е. А. за помощь при подготовке рукописи, а также чл. РАН Васильева С. Н. за критические замечания и предложения. Структура и объем работы. Диссертация изложена на 0 страницах. Она состоит из введения, 4 глав, заключения, списка литературы и приложения. Программный комплекс решает задачи обработки растровых изображений, сегментации и аппроксимации, распознавания образов. В данном обзоре рассмотрим существующие подходы к их решению. Для дальнейшего изложения приводится ряд основных определений и обозначений. Точки р = (х,у), р е Я2, с помощью которых задаются объекты ПРД, будут называться базовыми. Множество базовых точек обозначим как Р, количество базовых точек — Ыр = ||Р|. Для заданной точки Р, ? Диаграммой Вороного заданного множества точек Р называется совокупность всех многоугольников Вороного этих точек. Для внутренних точек множества ячейки диаграммы Вороного являются ограниченными многоугольниками, а для точек, лежащих в вершинах его выпуклой оболочки, границы между ячейками уходят на бесконечность. Отрезок или луч, разделяющий две соседние ячейки диаграммы, будем далее называть ребром, а точку на конце такого отрезка — вершиной. Для представления лучей в число вершин включается специальная псевдоточка, обозначающая бесконечность. Вороного обозначим за Е, количество ребер диаграммы Вороного за Ые. Вершиной назовем точку на конце ребра. Множество вершин обозначим за V. Далее будем обозначать диаграмму Вороного как 0=й{Р,Е,У). Триангуляцией называется планарный граф, все внутренние области которого являются треугольниками []. Выпуклой триангуляцией называется такая триангуляция, для которой минимальный треугольник, охватывающий все треугольники, будет выпуклым []. Говорят, что триангуляция удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции. Триангуляция называется триангуляцией Делоне, если она является выпуклой и удовлетворяет условию Делоне []. Функцией уровня яркости серого изображения называется неотрицательная и ограниченная действительная функция двух переменных Дд;,у), 0 < /О,у)<Ь []. Одной из задач, решаемых в программном комплексе, является сегментация изображения. Цель сегментации - разделить изображение на однородные области, на такие которые имеют общие свойства. Ожидается, что области изображения имеют гомогенные свойства (характеристики) (т. Математически сегментация может быть определена следующим образом []. Л = и*,. Д,р) Rj = 0 для V/, у, где / * У. К изображениям, содержащим шум или текстуру, которые затрудняют обработку, могут быть применены различные фильтры. Опишем некоторые из них. Усредняющий фильтр [], который относится к фильтрам нижних частот (НЧ). Он предназначен для фильтрации высокочастотного шума, и его работа сопровождается размытием изображения. Значение каждого пиксела вычисляется как сумма значений окрестных пикселей с весовыми коэффициентами. Весовые коэффициенты образуют маску. Значение каждого весового коэффициента маски равно 1/МЫ, где М и N — размеры маски (количество строк и столбцов). Фильтр Гаусса [] также относится к НЧ фильтрам. В отличие от усредняющего фильтра, он в меньшей мере размывает обрабатываемое изображение. Маска фильтра такова, что центральный элемент маски имеет наибольшее значение, он соответствует пику распределения Гаусса. Значения остальных элементов уменьшаются по мере удаления от центрального элемента. Уменьшение происходит в соответствии с распределением Гаусса.