Разработка и исследование алгоритмов распознавания изображений на основе определения экстремальных признаков замкнутых контуров с помощью сортировки

• Автор: Рюмин, Олег Германович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Таганрог
• Количество страниц: 285 с. : ил.

СОДЕРЖАНИЕ
Введение
Глава 1. Сортировка как основа схемы распознавания плоских контурных изображений в декартовых координатах

1.1. Сортировка посредством подсчета

1.2. Сортировка методом слияния

1.3. Идентификация экстремумов на основе сортировки

1.4. Обзорное сравнение алгоритма идентификации экстремумов на основе сортировки с существующими методами поиска экстремумов

1.5. Видоизменение алгоритма идентификации экстремумов к параллельному виду

1.6. Фильтрация экстремальных элементов

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

Выводы
Глава 2. Формирование векторов распознавания произвольно
расположенных плоских контурных изображений
2.1. Подход к формированию признаков плоских контурных изображений, инвариантных относительно сдвига, ротации и изменения масштаба
2.2. Идентификация экстремумов замкнутого контура при заданном
порядке обхода
2.3. Фильтрация экстремумов, обусловленных растеризацией
2.4. Алгоритм идентификации экстремумов контуров на растре с взаимно однозначным соответствием фигурам заданного класса
2.5. Использование экстремальных признаков контуров фигур для построения векторов распознавания
2.6. Инвариантность векторов распознавания изображений относительно сдвига, масштабирования и ротации
2.7. О формировании базы эталонов и способе сравнения векторов распознавания с эталонными векторами
Выводы
Глава 3. Программный эксперимент по автоматической идентификации
изображений
3.1. Программный эксперимент со сканированными символами
латинского алфавита

3.2. Устойчивость алгоритма распознавания при искажении изображений
3.3. Параллелизм алгоритма автоматического подбора радиуса окрестности локализации
3.4. Дополнение компонент эталонных векторов и векторов распознавания
для уточнения идентификации при наличии конфликтов
3.5. Сравнение предложенных схем распознавания с известными методами
Заключение
Литература
Приложение 1. Программные реализации некоторых алгоритмов сортировки ...183 Приложение 2. Идентификация арифметических экстремумов в условиях
растеризации
Приложение 3. О выделении наибольшего линейного участка контура
растрового изображения на основе сортировки
Литература к приложению
Приложение 4. Дополнение компонент эталонных векторов и векторов распознавания и анализ участков контура, заключенных между
экстремумами полярного радиуса
Литература к приложению
Приложение 5. Программная реализация алгоритма формирования
координат вектора распознавания
Приложение 6. Программная реализация идентификации изображения по
сформированному вектору распознавания
Приложение 7. Результаты программного эксперимента по формированию
векторов распознавания символов латинского алфавита
Приложение 8. Акты об использовании результатов диссертационной
работы
ВВЕДЕНИЕ

Актуальность проблемы. Распознавание, классификация и идентификация изображений - одно из наиболее актуальных направлений исследования теоретической информатики. Тематика распознавания имеет приложения во многих областях научных, технических, промышленных исследований, а также в области компьютерных и производственных технологий.
Быстродействие и точность идентификации являются важнейшими требованиями, предъявляемыми к распознающим системам. В то же время обработка изображений сопряжена со значительным объемом вычислений, как правило, в условиях искажения поступающей информации.
Многие задачи распознавания необходимо решать в строго ограниченное время, поэтому алгоритмы распознавания должны быть оптимизированы по временной сложности, возможность данной оптимизации может достигаться на основе распараллеливания. Компьютерная реализация таких алгоритмов требует обеспечения высокого быстродействия и практической устойчивости к искажениям. Ограниченность объемов машинной памяти, выделяемой под пространство эталонов, а также требование быстродействия выводят на первый план распараллеливаемые алгоритмы распознавания, инвариантные к сдвигу, масштабированию и ротации распознаваемых изображений.
Здесь и всюду ниже преобразование масштабирования трактуется как равномерное растяжение или сжатие изображения вдоль осей координат, исключающее отражение.
Разновидности изображенпй. Существующие устройства ввода, такие как сканеры, фото и видеокамеры, а также устройства вывода, такие как мониторы и принтеры, обусловливают форму представления визуальной информации в виде изображений [1]; в памяти компьютера обычно используется представление изображения в виде матрицы пикселей /(»?„т2), О < от, < М1 -1, 0 <т2< М2 -1 (растровое изображение) [2]. В зависимости от вида

масштабирования и ротации. Исследование устойчивости к шуму и возможности распараллеливания в существующих схемах не отличается завершенностью.
Цель диссертационной работы состоит в построении метода распознавания и идентификации плоских изображений, ограниченных связным замкнутым контуром, который достигает сравнительного упрощения на основе упорядочения информации при помощи алгоритмов сортировки. Конструируемый метод должен расширить класс детерминированно идентифицируемых изображений в условиях сдвига, ротации и изменения масштаба, достигать устойчивости идентификации за счет итеративности алгоритма и выполнения условий сходимости. Одной из целей исследования является преобразование метода в параллельную форму и выполнение соответственных оценок временной сложности.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
1. Разработать метод распознавания плоских изображений, инвариантный относительно сдвига, ротации и масштабирования, который позволял бы осуществлять устойчивое построение векторов распознавания изображений с произвольными замкнутыми контурами в условиях растеризации и обладал свойством параллелизма.
2. Синтезировать параллельный алгоритм фильтрации искажений контура, который позволял бы устойчиво идентифицировать изображение в условиях помех с минимизацией временной сложности.
3. Построить структуру данных для базы эталонов и схему идентификации изображения путем последовательного сравнения вектора распознавания с эталонными векторами по норме в условиях искажения контура.
4. Синтезировать алгоритм идентификации отличительных особенностей фрагментов контуров по экстремальным отклонениям от хорд.
5. Выполнить программный эксперимент по распознаванию и