Быстрый способ распознавания текста

Предисловие.

Данный проект не претендует на звание первого места в мире и не рассматривается как конкурент FineReader, но надеюсь, что идея распознавания образов  символов используя эйлеровую характеристику будет новой.

Знакомство с эйлеровой характеристикой изображения.

Основная идея состоит в том, что берется черно белое изображение, и считая, что 0 это белый пиксель, а 1 это черный пиксель, тогда все изображение будет представлять из себя матрицу из нулей и единиц. В таком случае, черно-белое изображение можно представить как набор фрагментов размером 2 на 2 пикселя, все возможные комбинации представлены на рисунке:

 Теперь, зная фрагменты, можно посчитать их количество, в результате получится характеристический набор [F0, F1, F2, F3...F15], который будет уникален для любого изображения. Ниже приведен пример алгоритма подсчета фрагментов:

На каждом изображение pic1, pic2,... изображен красный квадрат шага подсчёта в алгоритме, внутри которого один из фрагментов F с рисунка выше. На каждом шаге происходит суммирование каждого фрагмента, в результате для изображения Original получим набор: [8,2,2,2,2,0,2,0,2,2,2,0,0,0,0,0], далее он будет называть эйлеровой характеристикой изображения или характеристическим набором.

ЗАМЕЧАНИЕ: на практике значение F0 (для изображения Original это значение 8) не используется, поскольку является фоном изображения. Поэтому будут использоваться 15 значений, начиная с F1 до F15.

Свойства эйлеровой характеристики изображения.

1. Значение характеристического набора [F1, F2...F15] является уникальным, иными словами не существует два изображения с одинаковой эйлеровой характеристикой.
2. Нет алгоритма преобразования из характеристического набора в исходное изображение, единственный способ - это перебор.

Каков алгоритм распознания текста?

Идея распознания букв заключается в том, что мы заранее вычисляем эйлеровую характеристику для всех символов алфавита языка и сохраняем это в базу знаний. Затем для частей распозноваемого изображения будем вычислять эйлеровую характеристику и искать её в базе знаний.

  

Этапы распознавания:

1. Изображение может быть как черно-белым так и цветным, поэтому первым этапом происходит аппроксимация изображения, то есть получение из него черно белого. 
2. Производим попиксельный проход по всему изображению с целью нахождения черных пикселей. При обнаружении закрашенного пикселя запускается рекурсивная операция по поиску всех закрашенных пикселей прилегающий к найденному и последующим. В результате мы получим фрагмент изображения, который может быть как симвом целиком так и часть его, либо "мусором", которые следует отбросить.
3. После нахождения всех не связанных частей изображения, для каждого вычисляется эйлеровая характеристика.
4. Далее в работу вступает анализатор, который проходя по каждому фрагменту определяет, есть ли значение его эйлеровой характеристики в базе знаний. Если значение находим, то считаем, что это распознанный фрагмент изображения, иначе оставляем его для дальнейшего изучения.
5. Нераспознанные части изображения подвергаются эвристическому анализу, то есть я пытаюсь по значению эйлеровой характеристики найти наиболее подходящее значение в базе знаний. Если же найти не удалось, то происходит попытка "склеить" находящиеся неподалеку фрагменты, и уже для них провести поиск результата в базе знаний. Для чего делается "склеивание"? Дело в том, что не все буквы состоят из одного непрерывного изображения, допустим "!" знак восклицания содержит 2 сегмента (палочка и точка), поэтому перед тем как его искать в базе знаний, требуется вычислить суммарное значение эйлеровой характеристики из обоих частей. Если же и после склейки с соседними сегментами приемлемый результат найти не удалось, то фрагмент считам мусором и пропускаем.

Состав системы:

1. База знаний - файл или файлы изначально созданные мной, либо кем то ещё, содержащие характеристические наборы символов и требуемые для распознования.
2. Core - содержит основные функции, выполняющие распознавание
3. Generator - модуль для создания базы знаний.

ClearType и сглаживание.

Итак, на вход мы имеем распозноваемое изображение, и цель из него сделать черно-белое, подходящее для начала процесса распознавания. Казалось бы, чего может быть проще, все белые пиксели считаем за 0, а все остальные остальные 1, но не все так просто. Текст на изображении может быть сглаженным и не сглаженным. Сглаженные символы смотрятся плавными и без углов, а не сглаженные будут выглядеть на современным мониторах с заметными глазу пикселями по контуру. С появлением LCD (жидкокристаллических) экранов были созданы ClearType (для Windows) и другие виды сглаживания, которые пользуясь особенностями матрицы монитора. Меняют цвета пиксели изображения текста, после чего он выглядит намного "мягче". Что бы увидеть результат сглаживания, можно напечатать какую то букву (или текст) к примеру в mspaint, увеличить масштаб, и ваш текст превратилась в какую то разноцветную мозаику.

В чем же дело? Почему на маленьком масштабе мы видим обычный символ? Неужели глаза нас обманываю? Дело в том, что пиксель LCD монитора состоит не из единого пикселя, который может принимать нужный цвет, а из 3 субпикселей 3 цветов, которых хватает для получения нужного цвета. Поэтому цель работы ClearType получить наиболее приятный глазу текст используя особенность матрицы LCD монитора, а это достигается с помощью субпиксельного рендеринга. У кого есть "Лупа" можете, с целью эксперимента, увеличить любое место включенного экрана и увидеть матрицу как на картинке ниже.

 На рисунке показан квадрат из 3х3 пикселей LCD матрицы.

Внимание! Данная особенность усложняет получение черно белого изображения и очень сильно влияет на результат, поскольку не всегда даёт возможность получить такое же изображение, эйлеровая характеристика которого сохранена в базу знаний. Тем самым различие изображений заставляет выполнять эвристический анализ, которые не всегда может быть удачным.

Получение черно-белого изображения.

Найденные в интернете алгоритмы преобразования цветного в черно-белое меня не устроили качеством. После их применения, образы символов  подвергнутых сублепиксельному рендеренгу, становились разными по ширине, появлялись разрывы линий букв и непонятный мусор. В итоге решил получать черно-белого изображения путем анализа яркости пикселя. Черным считал все пиксели ярче (больше величины) 130 единиц, остальные белые. Данный способ не идеален, и все равно приводит к получению неудовлетворительного результата если меняется яркость текста, но он хотя бы получал схожие со значениями в базе знаний изображения. Реализацию можно посмотреть в классе LuminosityApproximator.

База знаний.

Изначальная задумка  наполнения базы знаний была такая, что я для каждой буквы языка подсчитаю эйлеровую характеристику получаемого изображения символа для 140 шрифтов, которые установлены у меня на компьтере (C:\Windows\Fonts), добавлю ещё все варианты типы шрифтов (Обычный, Жирный, Курсив) и размеры с 8 до 32, тем самым покрою все, или почти все, вариации букв и база станет универсальной, но к сожалению это оказалось не так хорошо как кажется. С такими условиями у меня получилось вот что:

1. Файл базы знаний получился достаточно большим (около 3 мегабайт) для русского и английского языка. Не смотря на то, что эйлеровая характеристика хранится в виде простой строки из 15 цифр, а сам файл представляет из себя сжатый архив (DeflateStream), который потом распаковывается в памяти.
2. Около 10 секунд у меня занимает десериализация базы знаний. При этом страдало время сравнения характеристических наборов. Функцию для вычисления GetHashCode() подобрать не получилось, поэтому пришлось сравнивать поразрядно. И по сравнению с базой знаний из 3-5 шрифтов, время анализа текста с базой в 140 шрифтов увеличиволось в 30-50 раз. При этом в базу знаний не сохраняются одинаковые характеристические наборы, не смотря на то, что некоторые символы в разных шрифтах могут выглядеть одинаково и быть схожими даже есть это к примеру 20 и 21 шрифт.

Поэтому пришлось создать небольшую базу знаний, которая идет внутри Core модуля, и даёт возможность проверить функционал. Есть очень серьезная проблема при наполнении базы. Не все шрифты отображают символы небольшого размера корректно. Допустим символ "e" при отрисовке 8 размером шрифта по имени "Franklin Gothic Medium" получается как:

И мало чем похож на оригинал. При этом если добавить его в базу знаний, то это очень ухудшит результаты эвристики, так как вводит в заблуждение анализ символов похожих на этот. Данный символ получался у разных шрифтов для разных букв. Сам процесс наполнения базы знания нужно контролировать, что бы каждое изображение символа, перед сохранением в базу знаний, проверялось человеком на соответствие букве. Но у меня, к сожалению, столько сил и времени нет.

Алгоритм поиска символов.

Скажу сразу, что изначально я недооценил эту проблему с поиском и забыл о том, что символы могу состоять из нескольких частей. Мне казалось, что в ходе попиксельного прохождения я буду встречать символ, находить его части, если таковые имеются, объдинять их и анализировать. Обычный проход выглядил бы так, что я нахожу букву "H" (В базе знаний) и считаю, что все симолы нижие верхней точки и выше нижней точки относятся к текущей строке и должны ализировать в связке:

Но это идеальная ситуация, мне же в ходе распознования приходилось иметь дело с разобрванными изображениями,  которые помимо всего могли иметь и огромное количество мусора, располагаемого рядом с текстом:

На этом изображении слова "yes" попытаюсь объяснить сложность анализа. Будем считать, что это полная строка, но при этом b13 и i6 это фрагменты мусора в результате апроксимации. У символа "y" не хватает точки, и при этом ни один из символов не присутсвует в базе знаний, что бы с уверенностью сказать, что мы имеет дело со строкой текста от "c" до "i" строки. А высота строки нам очень важна, так как для склейки нам нужно знать насколько ближайшие фрагменты стоит "склеивать" и анализировать. Ведь может быть ситуация, что мы нечаянно начнём склеивать символы двух строк и результаты такого распознования будут далеки от идеальных.

Эвристика при анализе образов.

Что же такое эвристика при распозновании изображений? Это процесс, в результате которого характеристический набор, не присутсвующий в базе знаний, получается распознать как правильную букву алфавита. Я долго думал, как можно производить анализ, и в итоге наболее удачным алгоритмом получился такой:

1. Нахожу все характеристические наборы в базе знаний, у которых наибольшее количество значений F фрагментов совпадает с распозноваемым изображением.
2. Далее выбираю только те характеристические наборы, у которых с распозноваемым изображением по не равным значеним F фрагмента, разница не больше чем на +- 1 единицу: -1 < F < 1. И это все подсчитывается для каждой буквы алфавита.
3. Затем нахожу символ, который имеет  наибольшее число вхождений. Считая его резульатом эвристического анализа.

Этот алгоритм даёт не лучшие результаты на маленьких изображений символов (7 - 12 размер шрифта). Но может быть связанно с тем, что в базе знаний присутсвуют характеристические наборы для схожих изображений разных символов.

Пример использования на языке C#.

Пример начала распознования изображения image. В переменной result будет текст:

var recognizer = new TextRecognizer(container);
var report = recognizer.Recognize(image);
 
// Raw text.
var result = report.RawText();
 
// List of all fragments and recognition state for each ones.
var fragments = report.Symbols;

Демо проект.

Для наглядной демонстарции работы я написал WPF приложение. Запускается оно из проекта с именем "Qocr.Application.Wpf". Пример окна с результатом распознования ниже:

Что бы распознать изображение потребуется:

• Нажимает "New Image" выбирает изображение для распознания
• Используя режим "Black and White" можно увидить какое изображение будет подвергаться анализу. Если вы видите крайне низкого качества изображение, то не ждите хороших результатов. Что бы улучшить результаты можете попробовать сами написать конвертер цветного изображения в черно белое.
• Выбираем язык "Language".
• Нажимает распознать "Recognize".

Все фрагменты изображения должны стать помеченными оранжевой или зелёной рамкой.

• 
  Оранжевая рамка говори о том, что в ходе эвристического анализа изображение было распознано, но невсегда результат совпадает с оригиналом.
• 
  Зелёная рамка говорит о том, что данный символ в черно белом режиме был найден в базе знаний и распознан без использования эвристики.

Пример распознования анлоязычного текста:

Скачать исходный код программы написанной на C#: