распознавания образов и, в частности, символов. Описание некоторых
решений задачи по выделению признаков символов на основе клеточных
автоматов приводится в разд. 3.2.
До процесса выделения признаков символов необходимо, как указано в
разд.1.1, решить несколько задач: необходимо изображение текста
обработать от шума, привести его в состояние, которое позволяет выполнить
условия алгоритмов распознавания, и выделить из него отдельные
изображения символов.
1.1. Предварительная обработка изображения
Обработка изображения – это задача по изменению характеристик
изображения для того, чтобы алгоритмы, участвующие в распознавании
текста, работали более качественно с меньшим числом ошибок. Кроме того,
для увеличения производительности работы клеточных автоматов,
задействованных в распознавании, очень критичным элементом является
количество состояний клеток (цветов точек) изображения.
В данной работе клеточные автоматы, задействованные в распознавании
символов, функционируют на основе двух состояний клеток,
соответствующих черному и белому цвету пикселей изображения.
В процессе перевода изображения в черно-белое состояние
составляющие символов точки следует выделить среди фона. Для данной
задачи может быть использован клеточный автомат, в котором каждая клетка
соответствует точке изображения, а локальный радиус для клетки равен
нулю. Автомат реализует три правила: переводит цвет каждой точки
изображения в оттенок серого; закрашивает клетку черным, если она темнее
определенного предельного цвета; закрашивает клетку белым цветов, если
она светлее установленной границы. На рис. 13 представлены правила
описанного клеточного автомата, созданные на основе моделирующей
программы,
Рис. 13. Правила автомата перевода изображения текста в черно-белые
цвета: а – перевод цвета точки в оттенок серого, б – закрашивание
клетки черным, если ее оттенок больше предельного цвета, в -
закрашивание клетки белым, если ее оттенок меньше предельного цвета
1.2. Деление текста на символы
Одна из нерешенных на сегодняшний день задач для систем
распознавания текста – его деление на символы [4].
Наиболее часто эта задача решается в подобных системах в комплексе:
производится предварительно разбиение изображения текста на отдельные
изображения символов и после этого определяется зависимость между
разными изображениями с оценкой расстояния между ними. На этапе
распознавания результаты разбиения могут уточняться с целью
дополнительного разбиения или объединения нескольких полученных
изображений. Уточнения могут строиться на основе контекста: если часть
символов хорошо распознаны, они могут указать на нераспознанный, либо
факт уточнения может основываться на плохом распознании получившегося
изображения символа.
Клеточные автоматы могут помочь в предварительном разбиении
изображения текста на изображения символов. В этом случае необходимо
определить два клеточных автомата с метками, правила которых описаны
ниже.
1. Первый автомат ставит метку на каждую черную точку изображения
в виде последовательно генерируемых целых чисел.
2. Второй автомат для каждой черной точки просматривает локальную
окрестность единичного радиуса и саму себя, выставляет у себя метку с
минимальным числом из этой окрестности. При этом старая метка удаляется.
Схемы автоматов, созданных на основе моделирующей программы,
представлены на рис. 14.
а б
Рис. 14. Клеточные автоматы с метками, выделяющие из изображения
текста символы: а – автомат генерации меток – чисел, б – автомат по
поиску метки с минимальным числом
После завершения работы автоматов в изображении текста будут
выделены разными метками разные символы, что позволит вычленять
изображения отдельных символов.
1.3. Выделение признаков символов
Выше было отмечено, что человек воспринимает образы на основе
ассоциации признаков оцениваемых объектов со знакомыми объектами.
Каждый символ текста (русского, английского или другого) имеет свои
уникальные признаки. Данные признаки уникальным образом отличают
символы друг от друга.
Символы текста имеют большое число признаков: положение и наклон
линий, дуг, наличие петель, вертикальных – горизонтальных линий, выступы
и их наклон, пересечения. Основными признаками можно считать выступы,
петли и пересечения, а также их взаимное расположение. На рис. 15
представлено положение элементов этих трех видов в символах русского
алфавита. На рисунке не представлены символы, являющиеся объединением
нескольких несвязанных элементов. Это символы «Ё», «Й» и «Ы». В
настоящей роботе данные символы не расматриваются, для их распознавания
в алгоритмах должны присутствовать дополнительные специальные блоки.
Рис. 15. Положение петель, концов и пересечений в символах
русского алфавита
Решение задачи выделения признаков символов на основе клеточных
автоматов решается в разд. 2.
1.4. Об этом говорит сайт https://intellect.icu . Классификация и обучение
На предыдущем шаге процесса распознавания текста выделяются
признаки символов. После этого предполагается процесс классификации,
который на основании полученных признаков определит название символа.
Классификация, как было отмечено в разд. 1.2, наиболее часто
основывается на нейронных сетях. Кроме того, для этой цели применимы
статистические методы, которые на основе накопленной информации о
признаках могут определить символ.
Система распознавания предполагает наличие блока обучения. Обучение
системы напрямую связано с классификацией, оно позволяет изменять и
поправлять коэффициенты на основе ассоциации результата классификации с
названием символа. Для нейронных сетей и статистических методов
обучение производится различными способами [5, 22].
Клеточные автоматы также могут участвовать в процессе классификации
признаков. Идеей классификации может служить создание характерного
клеточного автомата для каждого признака и его коррекция с учетом
определенных признаков в процессе обучения. Данная концепция требует
изучения и дальнейших исследований.
2. Клеточные автоматы в процессе выделения свойств текста
Рассмотрим характеристики клеточных автоматов в процессе распознавания текста. Разбиение процесса
распознавания текста на этапы предполагает использование разных
клеточных автоматов для выполнения различных задач. Определение
характеристик символов и выделение их признаков требует разработки
комплекса правил, на основе которых это становится возможным.
В разд. 1 описано, что основными элементами символов являются
петли, пересечения, положение концов. По этим элементам возможна
идентификация изображения, соотнесение с конкретным символом.
Возможно, что человек подсознательно пользуется именно этими признаками
в процессе чтения текста.
Существует множество стратегий выделения описанных признаков на
основе клеточных автоматов. Ниже описаны две таких стратегии, которые
используют клеточные автоматы с метками.
2.1. Первая стратегия выделения концов и петель символа
Первая стратегия состоит в том, что от верхнего края символа вдоль
точек, составляющих данный символ, пускается «волна». Эта «волна» может
разделяться на составляющие, повторяя контур изображения символа. В
определенный момент составляющие «волны» могут встретиться или
затухнуть на конце символа. На рис. 16 показано направление движения
«волны» вдоль изображения символа «А» и показаны места старта «волны»,
затухания на концах символа и в месте встречи ее двух составляющих.
Рис. 16. Направление распространения «волны» вдоль символа «А» с
отмечанием позиций концов символов и петель
В понятие «волны» в данном алгоритме вкладывается несколько
составляющих. «Фронт волны» – точки символа, которые передвигаются от
одного конца изображения символа к другому. «Шлейф волны» – это точки
изображения, в которых в предыдущий момент времени находился «фронт
волны». «Точки пройденного пути» – это точки изображения, где
присутствовал «фронт волны», а затем и «шлейф волны», в этих точках
процесс не возобновляется.
В начальный момент времени все точки символа не помечены метками.
Первая точка волны помечается, и алгоритм начинает свою работу.
Алгоритм основан на идее, что в процессе прохождения волны в какой-
то момент «фронт волны» угаснет, в то время как шлейф все еще будет
присутствовать. Данное событие может случиться только на конце символа
либо на месте встречи двух составляющих волны. Позиция шлейфа волны в
этот момент запоминается.
Дополнительно, событие встречи двух составляющих волны
регистрируется на основании факта, что шлейфы двух составляющих волны
в момент встречи не связаны между собой. Таким образом, запоминается
позиция петли символа.
Схема работы последовательности клеточных автоматов представлена
на рис. 17. В овальных блоках указаны клеточные автоматы.
Рис. 17. Блок -схема работы последовательности клеточных автоматов для
первого алгоритма выделения признаков символов
Приведем описание алгоритма на основе последовательности клеточных
автоматов с метками. Кроме клеточных автоматов в последовательности
присутствуют дополнительные управляющие элементы. Состояние клетки
определяется ее цветом. Кроме цвета, клетка может содержать одну или
более меток, которые разделяются между собой цветами.
Шаг 1. На вход последовательности клеточных автоматов поступает
изображение символа.
Шаг 2. Верхняя левая черная клетка изображения помечается красной
и серой метками.
Шаг 3. Автомат «создание шлейфа»: красная метка заменяется синей
меткой.
Шаг 4. Автомат «создание фронта»: черные клетки без серой метки
рядом с клетками с серой меткой помечаются серой и красной метками.
Шаг 5. Одна клетка рядом с красной меткой заменяет синюю метку
зеленой.
Шаг 6. Автомат «проход по шлейфу»: все клетки рядом с клетками с
зелеными метками заменяют синие метки зелеными.
Шаг 7. Автомат «проход по фронту»: все клетки с красной, но без
зеленой метки, находящиеся рядом с клетками с зеленой меткой,
помечаются зеленой меткой; если клетка с красной и зеленой меткой
находится рядом с клеткой с синей меткой, то данная клетка
помечается оранжевой меткой.
Шаг 8. Если, начиная с шага 5, автоматы не изменили состояния ни
одной клетки, то перейти на шаг 9, иначе перейти на шаг 5.
Шаг 9. Автомат «удаление зеленых меток»: все зеленые метки у клеток
удаляются.
Шаг 10. Если, начиная с шага 3, автоматы не изменили состояния ни
одной клетки, то перейти на шаг 11, иначе перейти на шаг 3.
Шаг 11. Верхняя левая черная клетка изображения помечается синей
меткой.
Шаг 12. Автомат «удание нижних лишних меток»: если над клеткой с
синей или оранжевой меткой находится клетка с такой же меткой, то в
данной клетке эту метку удалить.
Шаг 13. Автомат «удаление лишних меток справа»: если слева от
клетки с синей или оранжевой меткой находится клетка с такой же
меткой, то в данной клетке эту метку удалить.
Шаг 14. Если, начиная с шага 12, автоматы не изменили состояния ни
одной клетки, то завершить последовательность, иначе перейти на шаг
12.
На выходе алгоритма некоторые клетки изображения помечены
метками. Синяя метка означает, что в данном месте символа находится конец
символа, а оранжевая метка означает у символа петли.
В процессе работы алгоритма клетки с красными метками могут быть
проинтерпретированы как фронт волны, синие клетки – как шлейф волны, а
серые клетки – как клетки пройденного пути.
Ниже приведены формальные правила переходов клеточных автоматов с
метками. Для описываемых клеточных автоматов определены пять
различных меток: красного, синего, серого, зеленого и оранжевого цветов.
Это означает, что состояние клетки состоит из шести составляющих: цвета и
наличия/отсутствия пяти меток.
Номер правила обозначается шестью числами, которые означают
состояние клетки и присутствие/отсутствие метки. Позиция каждой метки в
номере определяется на основе приведенного выше списка.
Некоторые правила автоматов в схемах содержат вместо цвета символа
штрихи – это означает набор правил со всевозможными комбинациями
цвета/наличия меток клетки.
1. Автомат «создание шлейфа» имеет окрестность N радиуса ноль – на
состояние клетки влияет только сама клетка. Автомат содержит только одно
правило: 3 : 2 : 1 : 1 : 0 : 0. Схема правила указана на рис. 18.
Рис. 18. Схема правила клеточного автомата «создание шлейфа»
Рис. 19. Схемы правил клеточного автомата «создание фронта»
2. Автомат «создание фронта» имеет локальную окрестность с радиусов
в одну клетку и содержит несколько правил. Схемы правил представлена на
рис. 19.
3. Автомата «проход по шлейфу» основан на окресности из соседей
единичного радиуса и содержит восемь правил, схемы которых представлены
на рис. 20.
Рис. 20. Схемы правил клеточного автомата «проход по шлейфу»
4. Схемы автомата «проход по фронту» представлены на рис. 21,
автомат содержит 12 правил.
Рис. 21. Схемы правил клеточного автомата «проход по фронту»
5. Автомат «удаление зеленых меток» аналогично автомату «создание
шлейфа» содержит одно правило и имеет радиус локальной окресности –
ноль. Схема правила автомата показана на рис. 22.
Рис. 22. Схемы правил клеточного автомата «удаление зеленых меток»
Рис. 23. Схемы правил автомата «удаление нижних лишних меток»
6. Схемы правил клеточного автомата «удаление нижних лишних
меток» показана на рис. 23.
7. Схемы правил автомата «удаление лишних меток справа» показана на
рис. 24.
Рис. 24. Схемы правил клеточного автомата «удаление лишних меток
справа»
2.2. Вторая стратегия выделения пересечений, концов и петель
символа
Вторая стратегия представляет собой усовершенствованную первую и
развивает ее. В процессе распространения «волны» в момент, когда
определяется клетка конца символа или клетка встречи двух составляющих
«волны», генерируется ответная «волна» – «эхо» вдоль уже пройденных
клеток. «Эхо» проходит путь в обратном направлении и отмечает клетки, в
которых начальная волна была разделена на составляющие. Это должно
позволить найти позиции пересечений отрезков, из которых состоят
символы.
Вторая стратегия позволяет определить позиции пересечений линий в
изображении символа. Распространение волны можно увидеть на рис. 25.
Рис. 25. Направление распространения «волны» вдоль символа «А» с
отмечанием позиций концов символов и петель, а также
распространение «эхо» с отмечанием позиции пересечений
Схема работы последовательности клеточных автоматов показана на
рис. 26.
Рис. 26. Блок Схема работы последовательности клеточных автоматов для
второго алгоритма выделения признаков символов
Приведем неформальное описание второго алгоритма на основе
последовательности клеточных автоматов с метками.
Шаг 1. На вход последовательности клеточных автоматов поступает
изображение символа.
Шаг 2. Верхняя левая черная клетка изображения помечается красной
и серой метками.
Шаг 3. Автомат «создание шлейфа»: красная метка заменяется синей
меткой.
Шаг 4. Автомат «создание фронта»: черные клетки без серой метки
рядом с клетками с серой меткой помечаются серой и красной метками.
Шаг 5. Одна клетка рядом с красной меткой изменяет синюю метку
зеленой.
Шаг 6. Автомат «проход по шлейфу»: все клетки рядом с клетками с
зелеными метками заменяют синие метки зелеными.
Шаг 7. Автомат «проход по фронту»: все клетки с красной, но не с
зеленой меткой, находящиеся рядом с клетками с зеленой меткой,
помечаются зеленой меткой; если клетка с красной и зеленой метками
находится рядом с клеткой с синей меткой, то данная клетка
помечается оранжевой меткой.
Шаг 8. Если, начиная с шага 5, автоматы не изменили состояние ни
одной клетки, то перейти на шаг 9, иначе перейти на шаг 5.
Шаг 9. Автомат «удаление зеленых меток»: все зеленые метки у клеток
убираются.
Шаг 10. Если у одной из клеток присутствует синяя метка, то перейти
на шаг 11, иначе на шаг 20.
Шаг 11. Автомат «создание эха»: синюю метку клеток заменить
коричневой и голубой, к красной метке символов добавить коричневую
метку.
Шаг 12. Автомат «создание шлейфа эха»: коричневая метка заменяется
желтой меткой.
Шаг 13. Автомат «создание фронта эха»: черные клетки с серой меткой,
но без фиолетовой метки рядом с клетками с фиолетовой меткой
помечаются фиолетовой и коричневой метками.
Шаг 14. Одна клетка рядом с коричневой меткой меняет желтую метку
малиновой.
Шаг 15. Автомат «проход по шлейфу эха»: все клетки рядом с клетками
с малиновыми метками заменяют желтые метки малиновыми.
Шаг 16. Автомат «проход по фронту эха»: все клетки с коричневой, но
не с малиновой меткой, находящиеся рядом с клетками с малиновой
меткой, помечаются малиновой меткой; если клетка с коричневой и
малиновой метками находится рядом с клеткой с желтой меткой, то
данная клетка помечается пурпурной меткой.
Шаг 17. Если, начиная с шага 14, автоматы не изменили состояния ни
одной клетки, то перейти на шаг 18, иначе перейти на шаг 14.
Шаг 18. Автомат «удаление малиновых меток»: все малиновые метки у
клеток убираются.
Шаг 19. Если, начиная с шага 12, автоматы не изменили состояния ни
одной клетки, то перейти на шаг 20, иначе перейти на шаг 12.
Шаг 20. Если, начиная с шага 3, автоматы не изменили состояния ни
одной клетки, то перейти на шаг 21, иначе перейти на шаг 3.
Шаг 21. Верхняя левая черная клетка изображения помечается синей
меткой.
Шаг 22. Автомат «удание нижних лишних меток»: если над клеткой с
синей или оранжевой меткой находится клетка с соответственно синей
или оранжевой меткой, то в данной клетке эту метку удалить.
Шаг 23. Автомат «удание лишних меток справа»: если слева от клетки с
синей или оранжевой меткой находится клетка с соответственно синей
или оранжевой меткой, то в данной клетке эту метку удалить.
Шаг 24. Если, начиная с шага 22, автоматы не изменили состояния ни
одной клетки, то завершить последовательность, иначе перейти на шаг
22.
Второй алгоритм может показаться, на первый взгляд, громоздким, но,
на самом деле, он содержит в себе две составляющих, аналогичных первому
алгоритму. Правила автоматов данного алгоритма аналогичны правилам
автоматов первого алгоритма по выделению признаков символов.
Достоинством второго алгоритма можно считать выделение большего
количества признаков символов, чем с помощью первого алгоритма. Однако,
второй алгоритм выполняет больше шагов и поэтому работает дольше.
Таблица 1 – Сравнение систем распознавания символов
Таблица 2. Скоростные характеристики моделирующей программы
Невысокие характеристики работы определяются моделирующим характером разработанной программы. Используемые алгоритмы требуют оптимизации и доработки.
Комментарии
Оставить комментарий
Распознавание образов
Термины: Распознавание образов