Распознавание символов
1. Назначение программы
Это программа позволяет распознавать текстовые символы, находящиеся на растровом изображении. Цель данной работы - изучения машинного зрения на основе фильтров теории активного восприятия изображения. Программа написана на языке «C++» с применением технологии «OpenMP 2.0», поэтому для компиляции рекомендуется использовать среду разработки начиная от Visual Studio 2008 и выше.
1.1. Задача распознавания
Задачу распознавания текстовой информации можно определить следующим образом. На вход подаётся изображение текста. Требуется определить его кодированное электронное представление, т.е. произвести его перевод из растрового графического представления в текстовое. Последнее означает, что для каждого изображения буквы текста нужно определить соответствующее кодирующее число. А это означает, что каждый фрагмент исходного изображения, соответствующий букве, должен быть отнесён к одному из классов букв, набор которых задаётся известным алфавитом. Изображения букв разных классов отличаются по начертанию. Выходное текстовое представление рукописи должно содержать весь набор букв, представленный в исходном изображении, в соответствующем порядке их следования. Таким образом, решаемая задача является задачей множественного распознавания изображений букв текста.
1.2. Исходные данные:
- Растровое изображение с буквенными или цифровыми символами.
- Размер изображения может быть любым.
- Шрифт и взаимное расположение символов может быть произвольным.
1.3. Приложение должно выполнять следующие задачи:
- Загрузка изображения в приложение.
- Сегментация содержимого на символы.
- Распознавание символов схожих с эталонами.
1.4. Выходные данные:
- Таблица найденных символов с указанием их расположения и величина, характеризующая их схожесть с эталонами.
2. Структура проекта
| Название файла | Содержимое файла |
|---|---|
| stdafx.h | Подключение стандартных библиотек |
| main.h | Объявление переменных, классов, методов и функций |
| main.cpp | Основной файл проекта, содержит функцию main() |
| Source.cpp | Описание всех методов и функций |
| MatchBase.dat | Данные тренировочной выборки |
3. Теоретические сведения
Рассмотрим процесс распознавания текста в составе точечного графического изображения на примере анализа капчи.
Ка́пча — компьютерный тест, используемый для того, чтобы определить, кем является пользователь системы: человеком или компьютером. На мониторе компьютера мы видим изображение символов букв и цифр (графический образ). Но графический образ еще не является текстовым документом. Человеку достаточно взглянуть на лист бумаги с текстом, чтобы понять, что на нем написано. С точки зрения компьютера, изображение - это набор разноцветных точек, а вовсе не в текстовый документ. Подобные задачи решают с помощью специальных программных средств, называемых средствами распознавания образов. Их называются OCR (Optical Character Recognition — оптическое распознавание символов), и опираются на специально разработанные шрифты, облегчавшие такой подход.
Системы распознавания имеют следующую типичную функциональную схему:
3.1 Входные данные
Входные данные, подлежащие распознаванию, подаются на вход системы и подвергаются предобработке с целью их преобразования в необходимый для следующего этапа вид или для выделения из них необходимых характерных признаков. Далее на этапе принятия решения над обработанным массивом данных производится ряд вычислений и на основе их результатов формируется ответ, содержащий ожидаемые от системы сведения о входных данных. Содержание входных и выходных данных определяется назначением системы. Система распознавания текста может принимать на вход растровое изображение страницы текста в установленном формате и преобразовывать его в кодовую последовательность составляющих данный текст символов. Кроме описанных этапов функционирования системы распознавания предусматривают свою настройку на множество возможных входных данных;
3.2 Обучение системы
Целью обучения системы является формирование в её памяти набора сведений, необходимых для распознавания предполагаемого класса входных данных. В зависимости от специфики решаемой задачи обучение может быть выражено процедурой однократного ручного задания параметров работы системы её разработчиком, автоматической процедурой определения оптимальных значений параметров в результате проведения учебных циклов распознавания или процессом непрерывной подстройки параметров в результате анализа вырабатываемых системой ответов. Как правило, имеет место комбинация названных подходов.
На этапе предобработки решается задача создания формализованного описания объектов распознавания, пригодного для использования алгоритмами собственно распознавания. Как правило, исходные данные о наблюдаемых объектах представлены в форме, непригодной непосредственно для распознавания. Это могут быть растровые изображения, звуковые файлы, статистические данные (числовые наборы), видео-записи и пр. Некоторые алгоритмы распознавания требуют более высокоуровневого редставления. Это приводит к необходимости произвести одно или более преобразований исходных данных, переходя от кода 0 к коду 1, 2 и т.д. В нашем случае необходимо исследовать растровое изображение любого доступного формата(JPG, PNG и др.)
Для распознавания символов мы используем значение яркости точки. Яркость точки находится по формуле, коэффициенты которой определяются свойствами человеческого зрения:
Y:=0.3*R+0.59*G+0.11*B (1)
Разбиение рассматриваемого множества объектов на классы может быть задано перечислением. Каждый класс задаётся путём прямого указания его членов. Такой подход используется в том случае, если доступна полная априорная информация о всех возможных объектах распознавания, его называют методом сравнения с эталоном. Предъявляемые системе образы сравниваются с заданными описаниями представителей классов и относятся к тому классу, которому принадлежат наиболее сходные с ними образцы. Решение об отнесении поступающих объектов к тому или иному классу принимается на основе меры сходства с эталонами. Решающая функция строится на основе анализа эталонных объектов и априорной информации об их принадлежности разным классам.
3.3. Функция расстояния
При построении правил классификации на основе функций расстояния в качестве предпосылки используется то соображение, что естественным показателем сходства образов является степень близости точек, описывающих эти образы в Евклидовом пространстве.
Рассматривая пример на рисунке, можно интуитивно отнести объект «x» к классу «ω1», исходя из тех соображений, что описывающая его точка располагается ближе к объектам именно этого класса, нежели к объектам класса «ω2». При использовании функций расстояния классы объектов представляются в виде кластеров в параметрическом пространстве. На этапе распознавания используется критерий минимума расстояния между точкой распознаваемого объекта и кластером класса, к которому этот объект должен быть отнесён. Построение правил классификации заключается в построении кластеров оптимальным образом. Следует, однако, заметить, что данная методика эффективна только при наличии кластеризационных свойств у рассматриваемых классов объектов, т.е. когда расстояние между объектами внутри классов существенно меньше расстояния между группами точек, образующих классы.
Рассмотрим действие правил классификации, основанных на функциях расстояния. В некоторых случаях объекты каждого класса группируются вокруг некоторого единичного образа, являющегося типичным или репрезентативным для этого класса. В этом случае говорят, что класс представляется своим единственным эталоном. Например, такое явление наблюдается при распознавании печатных символов. В этой ситуации эффективным оказывается применение критерия минимального расстояния между распознаваемым объектом «x» и каждым из эталонов имеющихся классов «z1»,«z2»,…, «zM».
Расстояние между образом x и одним из эталонов zi в Евклидовом пространстве определяется по формуле 1:
3.4. Фильтры теории активного восприятия изображения**
Условием их применения для распознавания является предварительное выделение символов из исходного изображения. Для получения границ символов воспользуемся одним из фильтров теории активного восприятия(f1):
Под наложением фильтра на изображение или его часть понимается, вычисление значения функции:
.jpg?raw=true "Рис.6. Функция наложения фильтров")
Где:
- k - номер фильтра
- mi,j - суммарная яркость соответствующей подобласти фильтра.
На основании полученных данных о положении экстремумов данной функции, можно строить гипотезы о местонахождении начала и конца каждого символа на изображении. Каждый из отрезков на оси абсцисс между экстремумами может оказаться местоположением символа.
В связи с тем что количество отрезков значительно превышает число символов, для того чтобы более конкретно и точно локализовать положение символов были введены следующие параметры:
- Минимальный интервал;
- Максимальный интервал;
В результате добавились условия сравнения длин отрезков между экстремумами со значениями определяемыми пользователем, как минимальная и максимальная ширина символа. Все отрезки, которые были меньше минимальной или больше максимальной ширины букв в дальнейшем не рассматривались. Это позволило отсеять часть значительную часть интервалов из исследуемого пространства признаков. На оставшиеся отрезки накладываются 16 фильтров теории активного восприятия:
Их наложение также подразумевает под собой, вычисление значения функции 2, рассмотренной выше. Результат этих вычислений - координаты точки в 16-мерном пространстве признаков. По этим координатам находим декартово расстояние (формула 1) между предполагаемым символом и заранее подготовленными эталонами, координаты которых были получены эвристическим способом. Затем сравнив полученные расстояния, выбираем наиболее близкий эталон, символьное значение которого и будем считать значением найденного интервала.
Так как найденные отрезки между экстремумами могут накладываться друг на друга, был введён ещё один параметр – максимальный процент наложения. Из двух отрезков, процент которых превышает максимально допустимый, выбирается тот, что наиболее близок к эталону. В результате остаются только лишь те значения отрезков, процент наложения которых друг на друга строго меньше того, что задаёт пользователь.
4. Компиляция
Особенностью в компиляции данного проекта будет включение поддержки OpenMP. Подробнее об этом можно прочитать в статье Параллельные заметки №2 – инструментарий для OpenMP
5. Работа в программе
После запуска программа просит выбрать один из двух режимов работы.
5.1. Тренировка
Для осуществления тренировки необходимо ввести ширину фильтра и шаг смещения - параметры которые влияют на количество найденных локальных экстремум. Чем уже фильтр и меньше шаг - тем больше локальных минимумов программа обнаружит на изображении в результате наложения фильтра f1.
Далее необходимо ввести границы предполагаемого символа. Если программа находит в данных границах экстремумы, она принимает их за точные границы символа и предлагает сохранить эти значения в базу, обозначив их необходимым символом.
Этот процесс повторяется для всех символов.
5.2. Распознавание
На качество распознавания, помимо ширины фильтра и длины шага смещения, влияют такие параметры, как минимальная ширина символа, максимальная ширина символа, процент наложения. Эти параметры необходимы для того чтобы отсечь как можно большее количество ложных гипотез распознавания. Предполагается что минимальная и максимальная ширина символа известны заранее. Процент наложения определяется расстоянием между символами. Если изображения отдельных символов расположены так, что они не перекрываются то процент наложения равен нолю.
Если все параметры подобраны правильно, то на изображении программа распознает все символы, даже если порядок их изменён.
Но если изменить наклон букв, шрифт или добавить искажения, программа будет выдавать ошибочные значения.
Для того чтобы улучшить качество распознавания, необходимо добавить в тренировочную выборку изображения с теми вариантами начертания букв, которые мы собираемся распознавать.
6. Заключение
Преимуществом данного метода является относительная простота реализации. Основным недостатком является слабая устойчивость к шумам и искажениям в распознаваемых образах. Это связано с характером процесса распознавания: каждый распознаваемый объект попиксельно сравнивается поочерёдно со всеми известными системе эталонами. Кроме того, распознавание линейных трансформаций символов требует определённых усилий на этапе предобработки.
Безусловно, существует множество направлений по развитию данной программы:
- Необходимо обучить систему путём прямого указания изображений всех распознаваемых символов (т.е. путём задания эталонов): А Б В ….. а б в … 1 2 3 ….
- sНеобходимо отметить, что если предполагается распознавание курсивного, полужирного или иного начертания символов шрифта, то при таком подходе будет необходимо представить каждый вариант начертания каждого символа.
Спасибо за внимание!