Структурное распознавание бинарных изображений с использованием скелетов

• Автор: Быстров, Максим Юрьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Петрозаводск
• Количество страниц: 131 с. : ил.

ВВЕДЕНИЕ

ГЛАВА 1. НЕКОТОРЫЕ МАТЕМАТИЧЕСКИЕ МЕТОДЫ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ

1.1 Распознавание изображений

1.1.1 Постановки задачи

1.1.2 Методы сегментация изображений.

1.1.3 Методы распознавания.

1.1.4. Задача поиска в коллекциях графических документов.

1.2 Скелет бинарного изображения

1.2.1 Бинарные изображения.

1.2.2 Непрерывное представление скелета

1.2.3 Дискретный скелет

1.3 Скелетизация непрерывных фигур
1.3.1 Аппроксимация границ.
1.3.2 Скелетизация многоугольника.
1.3.3 Регуляризация скелета
1.4 Скелетизация дискретных фигур..
1.4.1 Алгоритмы топологического утончения.
1.4.2 Скелетизация на основе дистанционной карты.
1.5 Структурные методы распознавания
1.5.1 Выбор непроизводных элементов
1.5.2 Структурное распознавание
1.5.3 Синтаксические методы распознавания
ГЛАВА 2. СТРУКТУРНЫЙ МЕТОД ПОИСКА В ЭЛЕКТРОННЫХ КОЛЛЕКЦИЯХ БИНАРНЫХ ИЗОБРАЖЕНИЙ ПРИ ПОМОЩИ СКЕЛЕТОВ.
2.1 Постановка задачи.
2.2 Получение скелета
2.2.1 Алгоритм ЗонгаСуня.
2.2.2 Постобработка скелета.
2.2.3 Эффективность метода
2.3 Регуляризация скелета
2.3.1 Обоснование необходимости регуляризации.
2.3.2 Восстановление фигуры по скелету
2.3.3 Описание алгоритма регуляризации
2.4 Аппроксимация скелета
2.4.1 Цель аппроксимации
2.4.2 Обзор методов аппроксимации.
2.4.3 Аппроксимация ребер скелета отрезками прямых линий
2.4.4 Минимальная описанная окружность
2.5 Получение цепочки примитивов.
2.5.1 Цепочка примитивов
2.5.2 Описание алгоритма
2.5.3 Свойства цепочек
2.6 Сравнение цепочек примитивов.
2.6.1 Алгоритм сравнения цепочек
2.6.2. Сравнение цепочек частями
ГЛАВА 3. ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ СТРУКТУРНОГО ПОИСКА В КОЛЛЕКЦИИ БИНАРНЫХ ИЗОБРАЖЕНИЙ.
3.1 Некоторые особенности реализации метода структ урного поиска
3.1.1 Прослеживание скелета.
3.1.2 Восстановление фигуры и регуляризация.
3.1.3 Получение цепочек примитивов
3.2 Описание программного комплекса
3.3 Исследование метода построение скелета.
3.3.1 Устойчивость метода к масштабированию и поворотам
3.3.2 Оптимизация выполнения
3.4 Апробация программног о комплекса
3.4.1 Описание предметной области.
3.4.2 Подбор параметров алгоритма.
3.4.3 Оценка скорости и эффективности работы.
3.5 Возможности применения алгоритма для других коллекций бинарных изображений.
3.5.1 Произвольная коллекция бинарных изображений
3.5.2 Рекомендации по подбору параметров алгоритма.
3.6 Анализ алгоритма
3.6.1 Общие преимущества и недостатки
3.6.2 Сравнение с другими методами .
3.6.3 Двухуровневый поиск
Выводы,
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Также приводится сравнение алгоритма Зонга-Суня с другим методом топологического утончения, и указываются его преимущества. Смысл этапа регуляризации заключается удалении шумовых ребер скелета, которые не являются существенными при описании общей формы фигуры []. Предлагается алгоритм регуляризации, основанный на процедуре восстановления исходной фигуры по. Для аппроксимации скелета прямыми линиями вычисляется кривизна каждого ребра. Если ребро сильно искривлено, то оно аппроксимируется двумя или более отрезками прямых, иначе проводится отрезок, соединяющий концы ребра. В качестве структурного описания скелета предлагается использовать цепочку примитивов, состоящую из прямых ребер аппроксимированного скелета и углов между ребрами. Для этого делается обход скелета «против часовой стрелки». В результате обхода каждое ребро скелета рассматривается два раза. Такое описание однозначно идентифицирует аппроксимирующий скелет бинарного изображения. Цепочка, записанная в обратном порядке, соответствует зеркальному отображению исходной фигуры. Последним этапом алгоритма поиска является сравнение цепочек примитивов различных фигур между собой. Если цепочки похожи, то значит и скелеты, и фигуры, из которых они получены, также похожи. Приводится метод сравнения, который позволяет сравнивать цепочки примитивов, как целиком, так и частями. Третья глава посвящена программному комплексу для структурного поиска в коллекции бинарных изображений. В начале главы содержится описание реализации некоторых наиболее сложных алгоритмов обработки, которые необходимы для создания программного комплекса. В частности, подробно рассматриваются задачи прослеживания,дискретного скелета, восстановления фигуры по скелету и получения цепочек примитивов. С помощью разработанного программного комплекса были проведены исследования метода построения скелетов Зонга-Суня. Выявлено устойчивое поведение алгоритма при масштабировании и повороте изображений. Рассмотрен вариант оптимизации выполнения алгоритма. В зависимости от размеров прирост скорости составил 3- раз. Описанный во второй главе алгоритм структурного поиска в коллекции бинарных изображений с использованием скелетов был полностью реализован в виде программного комплекса. Апробация разработанного программного комплекса структурного поиска происходила Fia коллекции изображений петроглифов Карелии. Для тестирования были отобраны 0 черно-белых изображений. Для коллекции петроглифов Карелии были подобраны оптимальные значения параметров работы алгоритма. Также выработаны рекомендации по подбору данных параметров для других коллекций бинарных изображений. Приводится информация о средней скорости работы алгоритма, а также оценка эффективности работы алгоритма. В конце главы сделан обзор основных преимуществ и недостатков разработанною метода. Также приведено сравнение алгоритма структурного поиска с другим методом и показаны его преимущества. ГЛАВА 1. Задача распознавания изображений относится к классу интеллектуальных задач распознавания образов [, 8, , ]. Целью задачи распознавание образов является классификация объектов (образов) по нескольким категориям или классам с помощью выделения существенных признаков []. Как отдельная дисциплина данная задача выделилась в -х годах прошлого века. Определение 1: Образ в теории распознавания образов - объект, описываемый конечной совокупностью основных характеристик (признаков, свойств) []. Определение 2. Класс - группа образов, объединенных по некоторому набору признаков. В теории распознавания образов считается, что существует конечное число классов []. Определение 3. Прецедент - это образ, правильная классификация которого известна []. Считается, что все объекты универсально множества (образы) можно отнести к тому или иному классу. Каждый класс содержит конечное число известных объектов - прецедентов. Задача распознавания образов заключается в том, чтобы отнести новый распознаваемый образ к какому-либо классу. Определение 4. Признак - это количественное описание произвольной характеристики объекта [].