Разработка алгоритмов распознавания текста на основе клеточных автоматов Автор: Суясов Д. И. Руководитель: Шалыто А. А., д.т.н., профессор

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ2 Фильтрация изображения. Сегментация изображения текста на изображения символов. Выделение характеристик / признаков символов из их изображений. Классификация этих признаков. Постановка задачи Этапы распознавания текста: Задача: Исследование подзадач процесса распознавания текста и принципов их решения на основе клеточных автоматов.

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ3 Клеточные автоматы с метками G – дискретное метрическое множество, гарантирующее конечность расстояний между клетками; M – конечное множество меток; Z – конечный набор состояний клеток; N – конечное множество, определяющее окрестность клетки; f – правила клеточного автомата. {G, M, Z, N, f}

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ4 Последовательности клеточных автоматов Логика системы основана на последовательностях клеточных автоматов. Клеточные автоматы в последовательности содержат простой набор правил. Последовательность может содержать дополнительную функциональность. Последовательность позволяет индивидуально настраивать клеточные автоматы.

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ5 Алгоритмы фильтрации и сегментации ФильтрацияСегментация 1. Все точки переводятся в оттенки серого. 2. Темные точки перекрашиваются в черные. 3. Светлые точки перекрашиваются в белые. 1. Черные точки помечаются индексом. 2. Для каждой черной точки индекс переписывается на минимальный из соседних или самой точки

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ6 Принцип выделения признаков символов Фронт волны Встреча двух волн Затухание волны (отсутствие фронта) Точки пройденного пути Шлейф волны

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ7 Алгоритмы выделения признаков символов Алгоритм 1 фиксирует концы и петли символа: выбирается начальная точка; запускается волна; фиксируются точки концов символов; фиксируются точки встречи составляющих волны.

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ8 Алгоритмы выделения признаков символов Результаты выделения признаков первым алгоритмом: выделенные признаки практически уникальны; время работы алгоритма: 16 символов – 6 секунд;

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ9 Алгоритмы выделения признаков символов Алгоритм 2 фиксирует концы, петли и пересечения: выбирается начальная точка; запускается волна; во время фиксации концов и пересечений запускается волна- эхо; фиксируются точки концов символов и встречи составляющих волны.

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ10 Алгоритмы выделения признаков символов Результаты выделения признаков вторым алгоритмом: выделенные признаки уникальны; время работы алгоритма: 16 символов – 15 секунд;

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ11 Моделирующая программа Сознание клеточных автоматов и последовательностей. Запуск автоматов в пошаговом и автоматическом режимах. Обучение и распознавание текста на основе шаблонов. Возможность добавления других модулей работы с клеточными автоматами.

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ12 Таблица сравнения Тестовые данные Моделирующая программа Курсовая работа (на основе нейронных сетей) FineReader Время работы, с. Процент ошибок Время работы, с. Процент ошибок Время работы, с. Процент ошибок Изображение слова «документирование», размеры: 236 х 30 64%29%9%10% Изображение русского алфавита без букв «й», «ё» и «ы» 133%411%13% Изображение русского текста (76 символов), размеры: 561 х %517%31% Изображение страницы текста (742 символа) 8312%4016%72%

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ13 Результаты Исследован процесс распознавания текста. Показана применимость теории клеточных автоматов в распознавании. Введено понятие клеточного автомата с метками и последовательности клеточных автоматов. Разработан алгоритм фильтрации и сегментации изображений на основе клеточных автоматов. Разработаны и исследованы алгоритмы выделения признаков символов. Создана моделирующая программа. Расширяется область применения клеточных автоматов. Для качественного распознавания необходимо комбинировать несколько разных методов.

РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТА НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ14 Спасибо за внимание