Системы распознавания текста или OCR-системы (Optical Character Recognition) предназначены для автоматического ввода документов в компьютер. Это может быть страница книги, журнала, словаря, какой-то документ - все, что угодно, что было уже напечатано, и должно быть преобразовано обратно в электронную форму.

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

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

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

Описание OCR-процедуры

1. Предварительная обработка изображения.

2. Распознание объектов высших уровней.

3. Распознание символов

4. Структурирование гипотез. Словарная проверка.

5. Синтез электронного документа.

Большинство программ оптического распознавания текста (OCR Optical Character Recognition) работают с растровым изображением, которое получено через факс-модем, сканер, цифровую фотокамеру или другое устройство. На первом этапе OCR должен разбить страницу на блоки текста, основываясь на особенностях правого и левого выравнивания и наличия нескольких колонок. Затем распознанный блок разбивается на строки. Несмотря на кажущуюся простоту, это не такая очевидная задача, так как на практике неизбежны перекос изображения страницы или фрагментов страницы при сгибах. Даже небольшой наклон приводит к тому, что левый край одной строки становится ниже правого края следующей, особенно при маленьком межстрочном интервале. Врезультате возникает проблема определения строки, к которой относится тот или иной фрагмент изображения. Например, для букв j, Й, ё при небольшом наклоне уже сложно определить, к какой строке относится верхняя (отдельная) часть символа (в некоторых случаях ее можно принять за запятую или точку).

Потом строки разбиваются на непрерывные области изображения, которые, как правило, соответствуют отдельным буквам; алгоритм распознавания делает предположения относительно соответствия этих областей символам; а затем делается выбор каждого символа, в результате чего страница восстанавливается в символах текста, причем, как правило, в соответствующем формате. OCR-системы могут достигать наилучшей точности распознавания свыше 99,9% для чистых изображений, составленных из обычных шрифтов. На первый взгляд такая точность распознавания кажется идеальной, но уровень ошибок все же удручает, потому что, если имеется приблизительно 1500 символов на странице, то даже при коэффициенте успешного распознавания 99,9% получается одна или две ошибки на страницу. Втаких случаях на помощь приходит метод проверки по словарю. То есть, если какого-то слова нет в словаре системы, то она по специальным правилам пытается найти похожее. Но это все равно не позволяет исправлять 100% ошибок, что требует человеческого контроля результатов.

54. Microsoft Word – мощный текстовый процессор (текст. процессор выполняет более сложные операции чем редакторы - перенос слов, операции форматирования), предназначенный для выполнения всех процессов обработки текста.

В настоящее время наиболее широко распространён. Входит в комплект интегрированного пакета Microsoft Office. Основное назначение–создание и редактирование текстовых документов. Обладает широкими возможностями. Программа удобна для работы с большими документами благодаря имеющимся в ней средствам создания указателей, оглавлений, колонтитулов, иерархических заголовков и т.п.

1.Возможности текстового процессора Word простираются от набора, до проверки орфографии, вставки в текст графики в стандарте *.pcx или *.bmp, музыкальные модули в формате *.wav.,распечатки текста. Размещение в документе графических объектов, таблиц, диаграмм, гиперссылок, автоматизации обработки документов, использование стилей; списков, полей Word; создание макросов; подготовка текста к изданию (создание оглавления, алфавитного указателя, сносок, примечаний); работа над текстом совместно нескольких пользователей, генерация документов методом слияния, использование шаблонов и др. Он работает с многими шрифтами с любым из 21 языка мира. Наличие макетов текстов и шаблонов. Word обеспечивает поиск заданного фрагмента текста, замену его на указанный фрагмент, удаление, копирование во внутренний буфер. Наличие закладки в тексте позволяет быстро перейти к заложенному месту в тексте. Word позволяет включать в текст базы данных. Можно установить пароль. Word позволяет открывать много окон для одновременной работы с несколькими текстами. Microsoft Word (часто - MS Word, WinWord или просто Word) - текстовый процессор, предназначенный для создания, просмотра и редактирования текстовых документов, с локальным применением простейших форм таблично-матричных алгоритмов. Выпускается корпорацией Microsoft в составе пакета Microsoft Office. Первая версия была написана Ричардом Броди (Richard Brodie) для IBM PC, использующих DOS, в 1983 году.

Текстовый редактор – это программа предназначенная для создания и обработки текстов.

Четыре группы редакторов:

1. Редакторы для печати текста.

2. Текстовые процессоры для создания составных документов, т.е. документов составляющих из текстов таблиц, рисунков, графиков.

3. Программы для верстки текстов (в типографском деле)

4. Редакторы для создания научных текстов

Режимы работы редактора Word:

· Обычный режим – используется для печатания текстовой информации

· Режим разметки страницы

· Режим структуры документа – система разбивки документа на части. Предназначен для работы с большими текстами и имеющие ряд заголовков, подзаголовков.

· Режим Web-документ

Ввод и редактирование текста:

1. Не печатать пробел в начале предложения. Пробел считается символом.

2. Нельзя нажимать клавишу ввод для перехода на новую строку. Но обязательно нажимать ввод при новом абзаце.

3. Перед символами « .,:!? » нельзя ставить пробел, после символов обязательно ставить пробел.

4. Нужно сначала выделить текст, а потом лишь выполнять какую-то работу.

Форматирование документа включает:

1. Форматирование страницы

2. Форматирование абзаца

3. Символы

4. форматирование таблицы

5. форматирование рисунка.

Создание документа.

В текстовом редакторе MS Word используется два метода создания нового документа:

1. На основе готового шаблона

2. На основе существующего документа.

Второй метода роще, но первый методически более корректен. При создании документа на основе существующего документа открывают существующий документ, сохраняют его под новым именем, затем выделяют в ем все содержимое и удаляют все, после этого мы имеем пустой документ, имеющий собственное имя и сохраняющий все настройки, ранее принятые для исходного документа.

В состав Word включен широкий набор средств автоматизации, упрощающих выполнение типичных задач. Большинство из них в том или ином виде было представлено и в предыдущих версиях редактора, но теперь возможности автоматизации стали значительно шире. К таким средствам относятся:

Авто-замена, позволяющая автоматически исправлять типичные ошибки при вводе;

Авто-заполнение (или авто-текст), с помощью, которой можно автоматически продолжить ввод слова или фрагмента текста после ввода нескольких первых буки (теперь редактор с самого начала имеет некоторую базу таких заготовок);

Автоматическая проверка правописания включает в себя проверку орфографии и грамматики. Пользователь имеет возможность отключить любой из видов проверки или вообще провести проверку лишь после завершения ввода всего документа;

Microsoft Office

Автоматическое создание и предварительный просмотр стилей;

Авто-формат при вводе, предназначенный для автоматического форматирования документа непосредственно при вводе или после его завершения;

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

Например, если Помощник решит, что вы собираетесь приступить к созданию письма, то он предложит запустить Мастер писем.

В Word имеются средства, упрощающие работу с таблицами, границами (обрамлением) и заливкой:

С помощью мыши можно рисовать таблицы различной формы (отдельные ячейки таблицы могут иметь любую ширину и высоту). Границу ячейки, строки или столбца таблицы легко можно удалить, это дает тот же эффект, что и объединение ячеек. В Word можно объединять любые соседние ячейки как по горизонтали, так и по вертикали;

Содержимое ячеек таблицы можно выравнивать по верхнему или нижнему краю либо по середине ячейки. Текст внутри ячеек можно расположить вертикально (с поворотом на 90 градусов);

В состав Word включено более 150 различных типов границ, которые помогут украсить любой документ и оформить его профессионально;

В Word предлагается набор графических средств, с помощью которых можно обогатить и украсить текст и рисунки путем добавления объема, теней, текстурных и прозрачных заливок, авто-фигур.

Графический редактор Microsoft Office предоставляет большой набор инструментов для рисования. Для украшения текста и рисунков предлагается более 100 настраиваемых авто-фигур, 4 вида заливки (многоцветная градиентная, узорная, прозрачная и рисунком), и также добавление тени и объема.

Перечень возможностей Microsoft Word

Редактирование текста осуществляется с помощью следующих функций:

§ выделение, копирование и вставка нужного фрагмента текста;

§ вставка объектов, не являющихся текстом в формате Microsoft Word (например, включение в текст графических изображений, электронных таблиц и графиков, звуков, видеоизображений и т.д.);

§ вставка в документ номеров страниц, даты и времени, сносок, специальных символов и пр.;

§ возможность нахождения, перехода, замены нужного слова текста, строки, раздела, страницы и пр.;

§ возможность повтора или отмены последнего действия, произведенного с текстом;

§ расширенные возможности форматирования документа. В отличие от Word Pad, Word допускает выравнивание документа по обоим краям, многоколоночную верстку;

§ использование стилей для быстрого форматирования документа.

Кроме перечисленных возможностей программа предлагает некоторый набор сервисных функций, таких как:

§ проверка орфографии и грамматики, в том числе фоновая - по мере введения текста;

§ подбор синонимов слов (пункт меню «Тезаурус»);

§ расстановка переносов в тексте документа;

§ определение статистических данных документа (число символов, слов, строк, абзацев, страниц);

§ работа с макросами и шаблонами документов.

Также в программе имеется большой набор функций по работе с таблицами и графикой, объемная система помощи (справочная система) и многое, многое другое.

Похожая информация.

Хотелось бы провести сравнение методов, и показать , почему мы выбрали определенный, но практически - это сложно. На различных изображениях у определенных методов есть свои преимущества и свои недостатки, «в среднем» лучшего решения тоже нет, посему в Imago OCR мы спроектировали стек фильтров, каждый из которых может применяться в определенных случаях, а выбор результата будет зависеть от метрики качества.

К преимуществам метода можно отнести:

Довольно высокую скорость работы;
Параметризуемое качество результата;
Отсутствие размывания в ходе работы, и как следствие, «чуткость» к деталям;
И главная интересная особенность - нормализация локальных уровней освещенности.

Последнее свойство отлично иллюстрируется изображением из статьи, а важным для распознавания оно является из-за возможной неоднородности освещения объектов при съемке (листок бумаги, повернутый к источнику света так, что свет падает неравномерно):

Поверхностное описание алгоритма:

Локальной пороговой фильтрации изображения (laplacian threshold) с порогом T;
Дискретном косинусном преобразовании полученного изображения;
Фильтрации высокочастотных характеристик и решении специального уравнения для низких и средних частот (Retinex Equation);
Обратном дискретном косинусном преобразовании.

Сам алгоритм довольно чутко зависит от параметра T, но мы использовали его адаптацию:

Считаем Retinex(T) для T=1,2,4,8
Выполняем попиксельную медианную фильтрацию между результатами Retinex

Чем поможет OpenCV: есть готовая функция вычисления дискретного косинусного преобразования:
void dct(const Mat& src, Mat& dst, int flags=0); // flags = DCT_INVERSE for inverse DCT
И она по скорости работает не хуже, чем аналогичная из libfftw, хоть и не берусь утверждать это в общем случае (тестировалось на Core i5, Core Duo).

Для исходной картинки вышеописанный метод дает довольно приятный результат:

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

Здесь и далее : по факту, конечно есть множество других параметров (например, те самые, «магические» T=1,2,4,8), но, дабы «не забивать голову», не будем про них говорить сейчас. Их много, упоминания про них всплывут в разделе о машинном обучении, но конкретику я опущу, дабы не перегружать изложение количеством параметров.

Уровень растра: бинаризация

Следующим шагом является получение черно-белого изображения, где черный будет отвечать наличию «краски», а белый - ее отсутствию. Делается это потому, что ряд алгоритмов, например получение контура объекта, конструктивно не работают с полутонами. Одним из самых простых способов бинаризации является пороговая фильтрация (выбираем t в качестве порогового значения, все пиксели с интенсивностью больше t - фон, меньше - «краска»), но в силу ее низкой адаптивности чаще используется otsu threshold или adaptive gaussian threshold.

Несмотря на адаптивность более продвинутых методов, они все равно содержат пороговые значения, определяющие «количество» выходной информации. В случае более жестких порогов - часть элементов может быть потеряна, в случае «мягких» - может вылезти «шум».

Strong thresholding	Weak thresholding

Можно пытаться точно угадать пороги для каждого изображения, но мы пошли другим путем - использовали корреляцию между полученными изображениями с различными адаптивными порогами бинаризации:

Считаем strong и weak бинаризацию (с заданными порогами t1 и t2);
Разбиваем изображения на набор связных попиксельно областей ();
Удаляем все «слабые» сегменты, имеющие корреляцию с соответствующими сильными, меньше заданной (cratio);
Удаляем все «слабые» сегменты небольшой плотности (пропорции черных/белых пикселей меньше заданной bwratio);
Оставшиеся «слабые» сегменты - результат бинаризации.

В результате в большинстве случаев получаем изображение, лишенное шума и без потерь в детализации:

Описанное решение может выглядеть странно, в свете того, что мы хотели «избавиться» от одного параметра, а ввели целую кучу других, но основная идея в том, что корректность бинаризации теперь обеспечивается, в случае, если «настоящий» порог бинаризации попадает в интервал, заключенный между выбранными нами t1 и t2 (хотя мы не можем «бесконечно» увеличивать этот интервал, на разницу t1 и t2 тоже есть ограничение).

Идея вполне жизнеспособна при применении с различными методами пороговой фильтрации, а OpenCV «помогла» наличием встроенных функций адаптивной фильтрации:
cv::adaptiveThreshold(image, strongBinarized, 255, cv::ADAPTIVE_THRESH_GAUSSIAN_C, CV_THRESH_BINARY, strongBinarizeKernelSize, strongBinarizeTreshold); cv::threshold(image, otsuBinarized, otsuThresholdValue, 255, cv::THRESH_OTSU);
Если итоговое изображение вообще не содержит сегментов, то вероятно, произошла ошибка фильтрации и стоит рассмотреть другой предварительный фильтр («обратная связь»; «те самые» голубые стрелки в изображении структуры движка).

Уровень примитивов: векторизация

Следующим шагом в процессе распознавания является преобразование наборов пикселей (сегментов) в примитивы. Примитивами могут быть фигуры - окружность, набор сегментов, прямоугольник (конкретный набор примитивов зависит от решаемой задачи), или же символы.

Пока мы не знаем к какому классу отнести каждый объект поэтому пытаемся векторизовать его различными способами. Один и тот же набор пикселей может быть успешно векторизован и как набор сегментов и как символ, например «N», «I». Или же окружность и символ - «O». На данном этапе нам не нужно знать достоверно, какой класс имеет объект, но необходимо иметь определенную метрику схожести объекта с его векторизацией в определенном классе. Обычно это решается набором распознающих функций.

Например для набора пикселей мы получим набор следующих объектов (не думайте о конкретных числах метрики, они приведены для изображения того, чего мы хотим от процесса распознавания, но сами по себе пока не имеют смысла):

векторизация в виде символа «H» с значением метрики (расстояния) в 0.1 (возможно это именно H) ;
векторизация в виде символа «R» с значением метрики в 4.93 (маловероятно, но возможно это и R) ;
векторизация в виде трех сегментов "|", "-", "|" с значением метрики в 0.12 (вполне возможно, что это три сегмента) ;
векторизация как прямоугольник с размерами сторон x, y с значением метрики в 45.4 (совсем не похоже на прямоугольник) ;
векторизация как окружности с значением метрики +inf (гарантировано не является окружностью) ;

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

Распознавание набора сегментов

Обычно растровая область векторизуется в набор сегментов следующим образом:

Готового thinning фильтра в OpenCV нет, но реализовать его совсем не трудно . Разбиения на сегменты (decorner) тоже, но это и вовсе тривиально: выкидываем из области все точки, у которых больше двух соседей. А вот аппроксимация точек как набора сегментов в OpenCV присутствует, ей мы и воспользовались:
cv::approxPolyDP(curve, approxCurve, approxEps, closed); // approximation of curve -> approxCurve
Важным параметром является допуск аппроксимации (approxEps ), при увеличении которого в качестве результата мы получим большее число сегментов, а при уменьшении - более грубое приближение, и, как следствие, большее значение метрики. Как правильно его выбирать?

Во-первых он достаточно сильно зависит от средней толщины линии (интуитивно - чем больше толщина линии, тем меньше детализация; рисунок нарисованный острым карандашом может быть значительно более детализован, чем нарисованный маркером), что мы и использовали в нашей реализации:
approxEps = averageLineThickness * magicLineVectorizationFactor;
Во-вторых, с учетом вышеописанного подхода к классификации объектов есть возможность пытаться векторизовать сегменты с разными approxEps (с определенным шагом) и уже на этапе анализа логической структуры выбрать «более подходящий».

Распознавание окружностей

Довольно просто:

Ищем центр окружности (среднее по координатам точек) - (x,y);
Ищем радиус (среднее расстояние точек от центра) - r;
Считаем погрешность: среднее расстояние по точкам до окружности с центром (x,y) и радиусом r и толщиной averageLineThickness;
Считаем дополнительный штраф за разрывы окружности: magicCirclePenalty * (%разрывов).

После подбора magicCirclePenalty с этим кодом совершенно не было проблем, как и с похожим на него распознаванием прямоугольников.

Распознавание символов

Значительно более интересная часть, т.к. это challenge problem - нет ни одного алгоритма, претендующего на «самые оптимальные» показатели распознавания. Есть совсем простые методы, опирающиеся на , есть более сложные, например с использованием , но никакие не гарантируют «хорошего» качества распознавания.

Поэтому довольно естественным казалось решение использовать несколько подсистем распознавания символов и выбора агрегатного результата: если p1 = метрическое значение того, что алгоритмом 1 область A распознается как символ s, а p2 = метрическое значение того, что алгоритмом 2 область A распознается как символ s, то итоговое значение p = f(p1,p2). Нами было выбрано два алгоритма, обладающие удобно сравниваемыми значениями, высокой скоростью и достаточной стабильностью:

распознавание на базе дескрипторов Фурье;
маски квадратичного отклонения точек.

Распознавание символов на базе дескрипторов Фурье

Подготовка:

Получение внешнего контура объекта;
Преобразование координат точек контура (x;y) в комплексные числа x+iy;
Дискретное преобразование Фурье набора этих чисел;
Отбрасывание высокочастотной части спектра.

При выполнении обратного преобразования Фурье мы получаем набор точек, описывающий исходную фигуру с заданной степенью аппроксимации (N - количество оставленных коэффициентов):

Операция «распознавания» заключается в вычислении дескрипторов Фурье для распознаваемой области и сравнение их с предопределенными наборами, отвечающими за поддерживаемые символы. Чтобы получить метрическое значение из двух наборов дескрипторов необходимо выполнить операцию, называющуюся сверткой: d = sum((d1[i]-d2[i])*w[i], i=1,N), где d1 и d2 - наборы дескрипторов Фурье, а w - вектор весов для каждого коэффициента (мы получали его машинным обучением). Значение свертки инвариантно относительно масштаба сравниваемых символов. Кроме того, функция устойчива к высокочастотному шуму (случайных пикселях, не меняющих «геометрию» фигуры).

OpenCV довольно сильно помогает в реализации этого метода; есть готовая функция получения внешних контуров объектов:
cv::findContours(image, storage, CV_RETR_EXTERNAL);
И есть функция вычисления дискретного преобразования Фурье:
cv::dft(src, dst);
Остается только реализовать свертку и промежуточные преобразования типов, сохранение набора дескрипторов.

Метод хорош для рукописных символов (пожалуй наверное потому, что на него фоне другие дают менее качественные результаты), однако плохо пригоден для символов небольшого разрешения из-за того, что высокочастотный шум, то бишь «лишние» пиксели становятся большими по отношению к изображению целиком и начинают влиять на те коэффициенты, которые мы не отбрасываем. Можно пытаться уменьшить количество сравниваемых коэффициентов, но тогда становится сложнее делать выбор из схожих небольших символов. И поэтому был введен еще один метод распознавания.

Распознавание символов на базе масок квадратичного отклонения

Это довольно-таки интуитивное решение, которое, как оказалось, прекрасно работает для печатных символов любых разрешений; если у нас есть два черно-белых изображения одинакового разрешения, то можно научиться сравнивать их попиксельно.

Для каждой точки изображения 1 считается штраф: минимальное расстояние до точки изображения 2 того же цвета. Соответственно, метрика - это просто сумма штрафов с нормализующим коэффициентом. Такой метод будет значительно более устойчив на изображениях небольшого разрешения с наличием шума - для изображения с длиной стороны n отдельные пиксели в числе до k процентов не «испортят» метрику более чем k * n в худшем случае, а в практических - не более чем на k, ибо в большинстве случаев прилегают к «правильным» пикселям изображения.

Минусом метода, в том изложении как я описал, будет являться низкая скорость работы. Для каждого пикселя (O(n 2)) мы считаем минимальное расстояние до пикселя того же цвета другой картинки (O(n 2)), что дает O(n 4).

Но это довольно легко лечится предвычислением: построим две маски penalty_white(x,y) и penalty_black(x,y) в которых будут храниться предвычисленные значения штрафов за то, что пиксель (x,y) оказывается white или black соответственно. Тогда процесс «распознавания» (то есть вычисления метрики) укладывается в O(n 2):
for (int y = 0; y < img.cols; y++) { for (int x = 0; x < img.rows; x++) { penalty += (image(y,x) == BLACK) ? penalty_black(y,x) : penalty_white(y,x); } }
Остается только хранить маски (penalty_white, penalty_black) для каждого написания каждого символа и в процессе распознавания их перебирать. OpenCV в реализации этого алгоритма нам практически не поможет, но он тривиален. Но, как я уже говорил, сравниваемые изображения должны быть одинакового разрешения, поэтому чтобы привести одно к другому возможно потребуется функция:
cv::resize(temp, temp, cv::Size(size_x, size_y), 0.0, 0.0);
Если вернуться к общему процессу распознавания символов, то в результате прогона обоих методов мы получаем таблицу метрических значений:

Значение распознавания - не один элемент, а вся таблица, из которой мы знаем, что с самой большой вероятностью - это символ «C», но возможно это «0», или «6» (или «O», или «c», которые не влезли на экран). А если это скобка, то с большей вероятностью открывающая, нежели закрывающая. Но пока мы даже не знаем, символ ли это вообще…

Уровень примитивов: сепарация

Если бы мы жили в идеальном мире сверхпроизводительных (квантовых?) компьютеров, то скорее всего этот шаг не был бы необходим: у нас есть набор некоторых объектов, для каждого из которых есть таблица «вероятностей», определяющая, что именно это. Перебираем все элементы в таблице для каждого объекта, строим логическую структуру, и выбираем самую вероятную (по сумме метрик отдельных объектов) из валидных. Делов-то, кроме разве что экспоненциальной сложности алгоритма.

Но на практике обычно требуется определить тип объекта по-умолчанию. То есть выбрать некоторую готовую трактовку объектов на изображении, а затем, возможно незначительно ее изменить. Почему мы не могли выбрать тип объектов на предыдущем шаге (векторизации)? У нас не было достаточно статистической информации о всех объектах, и если трактовать определенный набор пикселей изолированно от всей картинки, то достоверно определить его смысл становится проблематично.

Это один из самых важных вопросов распознавания структурной информации. У человека с этим все обстоит значительно лучше, чем у машины, ибо он просто не умеет видеть пиксели по отдельности. И одним из начальных этапов разочарования в построении OCR системы является попытка алгоритмизировать вроде бы человеческий подход «по шагам» и получение при этом неудовлетворительных результатов. Кажется что вот-вот уже, стоит немного улучшить алгоритмы распознавания примитивов, чтобы они «не ошибались», и мы получим более качественные результаты, но всегда находится несколько картинок, которые «ломают» любую логику.

И вот, мы спрашиваем человека, что это -
Конечно, это просто изогнутая линия. Но если нужно причислить ее либо к символам, либо к набору сегментов прямой линии, то что это? Тогда это, скорее всего, либо буква «l», либо две прямые линии под углом (просто угол нарисован скругленным). Но как выбрать правильную трактовку? Примерную задачу могла решать и машина на предыдущем шаге, и решить ее верно с вероятностью 1/2. Но 1/2 это полный крах для системы распознавания структурной информации, мы просто испортим структуру, она не пройдет валидацию, придется исправить «ошибки», которые по счастливой вероятности могут не совпасть с истинной проблемой. Мы можем получить все что угодно.

Но если мы посмотрим на соседние объекты, то многое может стать понятным:

И пусть вы даже не сталкивались с структурными формулами в химии никогда, но из этой картинки почему-то становится очевидно что это связь (линия, прямая или две прямых с скругленным углом). Мы видим изображение трех символов, видим какие они аккуратные, оцениваем примерный их размер, понимаем что «скругленная штука» - не символ.

Есть и другой вариант:

Мы увидели линию, которая является абсолютно прямой, увидели стоящий рядом «идеальный» символ, наш объект похож по размеру, хотя и отрисован менее качественно. Здесь сложнее сказать наверняка, но если мы знаем, что связи должны соединять объекты, а в направлении концов нашего объекта ничего нет - то он вряд ли связь. А если вспомнить, что «Cl» (хлор) вполне вероятное сочетание символов в нашей предметной области, то да, это все-таки символ «l».

Здесь я практически и изложил в свободном стиле наброски алгоритма сепарации. А теперь более формально.

Пороговая часть:

Если в таблице метрик для объекта только одно значение является «хорошим» (близким к нулю), а все остальные отличаются минимум на константу C, то маркируем его соответствующим классом.

Это здорово, но так бывает не всегда.

Для оставшихся объектов прибегаем к статистическому анализу:

Определение среднего размера потенциальных символов и отклонения от него;
Определение средней длины потенциальных линий, отклонение от него;
Определение средней кривизны потенциальных линий;
Определение средней толщины линий, символов;
И другие статистические критерии, например hu moments (которые кстати OpenCV умеет считать).

Мы все еще не знаем, для каждого объекта - какой класс он имеет, просто смотрим в таблицу метрик, и выбираем наиболее близкий по значению к нему объект - это я и вкладываю в понятие "потенциальный ".

Затем строим дерево классификации, в узлах которого могут стоять следующие условия: (если высота объекта лежит в диапазоне от средняя_высота_символа-1 до средняя_высота_символа+2, при этом обладает кривизной превосходящей 3*средняя_кривизна_линии и его длина менее 0.5*средняя длина линий), то он маркируется как символ. Метод построения деревьев классификации хорошо описан , и я позволю себе не повторять.

После прохождения статистической части некоторые объекты будут промаркированы предположительными классами. В большинстве практических случаев - почти все объекты. Если нам не удалось промаркировать хотя бы половину объектов, то скорее всего, что-то у нас пошло не так (и такое часто бывает для рукописных картинок). Но не будем «отчаиваться» и просто выберем половину объектов с наименьшими метрическими значениями и промаркируем их без учета статистической информации (для этой странной загогулины из примера - просто посмотрим в таблицу расстояний, и если к «l» она ближе, то назначим ее символом «l». Какие при этом могут возникать проблемы я уже описал, но это вынужденное решение).

Для оставшихся объектов применим локальный анализ:

Найдем всех соседей для выбранного объекта;
Если часть соседей уже имеет выбранный класс, то выберем из таблицы вероятности локальных конфигураций более вероятную;
Дополнительно: если в направлении концов объекта не стоит стоит других объектов, то он символ.

Для оставшихся объектов класс выберем «по умолчанию» - тот что по метрическому значению ближе.

В результате всех мучений мы можем разделить изображение к набор объектов, предположительно являющихся символами и часть, отвечающую за структуру.

Структурный уровень

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

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

Обработка графа структуры

Первым важным шагом, является собственно получение этого графа. После векторизации, все что мы имеем - набор разрозненных сегментов, у каждого из которых есть «начало» и «конец», которые я на изображении структуры промаркировал окружностями:

Статистически мы определяем средний радиус возможной склейки, и «собираем» отрезки, концы которых лежат в этом радиусе в вершины графа:

Радиус можно определить так - для каждой вершины посчитать минимальное расстояние до соседей и найти пик гистограммы. В случае, если этот пик дает радиус, больший среднего размера символа, то можно считать, что все отрезки не связаны.

Затем удаляем слишком короткие ребра:

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

Вышеописанные пункты будут полезны и при распознавании таблиц, к примеру. А у нас есть еще поиск кратных ребер, нахождение «мостов» (планарного изображения непересекающихся ребер), нахождение изображения «стрелок». Все это значительно удобнее делать, работая с структурой графа, а не с промежуточными результатами распознавания - не стоит добиваться «идеальной» векторизации.

Сборка и обработка меток

Для символов необходимо выполнить объединение в группы и здесь применяется решение, аналогичное «сборке» графа. Каждую собранную метку необходимо распознать, а поскольку могут присутствовать верхние и нижние индексы - задача становится интереснее.
Для начала вычисляется «базовая линия» метки:

Это прямая (по сути просто определенное значение baseline_y), над которой лежат заглавные символы метки, а под которой - индексы. Для определения baseline_y нам поможет статистика:

определение среднего размера заглавного символа (у большинства символов написание заглавных и прописных различаются);
при анализе каждой конкретной метки выбираем среднее значение координаты y для всех символов, размер которых находится в пределах среднего.

Почему мы берем среднее, а не максимум (линия же должна идти под символами метки)? Так стабильнее; если мы ошиблись с трактовкой символа как заглавного, мы можем ошибочно причислить индекс к заглавным, провести под ним черту, и соответственно «индексов у нас больше не будет». Выбор среднего же с одной стороны не значительно меняет значение baseline_y в хороших случаях, а с другой - цена ошибки неправильного выбора заглавных символов падает.

Затем распознаем символы, один за другим. Для каждого символа вычисляем:

% его высоты, лежащей под базовой линией;
отношение к средней высоте заглавных символов.

Довольно неудачным было бы пороговое решение относительно этих параметров: если под базовой линией находится минимум 30% символа - то он индекс. А если 29? Вообще весь процесс распознавания как нельзя лучше можно описать идеей duck test. Если что-то похоже на индекс, то скорее всего - оно индекс. А похоже оно на индекс, если на что-то другое оно похоже еще меньше.

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

Если символ лежит на k% ниже базовой линии, то метрика для его трактовок как нижнего индекса уменьшается в f(k) раз;
Если символ на n% меньше по высоте, чем средняя высота, то метрика для его трактовок как символ a..z уменьшается в g(n) раз.

Соответственно в процессе распознавания, после применения всех правил мы просто выбираем трактовку с наименьшим значением метрики - это победивший символ, самый похожий. Но мы все еще не будем «забывать» остальные трактовки.

Валидация меток

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

Пусть наша метка состоит из двух символов: {c1, c2}
Причем c1 - это «Y» с значением метрики 0.1 и «X» с значением метрики 0.4;
c2 - это «c» с значением метрики 0.3 и «e» с значением метрики 0.8
Я бы просто мог написать, что наша метка - Yc . Но метка Yc не валидна. Чтобы получить валидную метку мы можем перебрать возможные альтернативы и выбрать валидную. Среди валидных ту - у которое суммарное значение метрик минимально.
В данном случае из всех 4 вариантов, валиден только один "Xe ", дающий итоговую метрику 1.2.

Вроде бы мы решили проблему, теперь значение метки валидное. Но как быть, если именно «Yc» и хотел использовать автор картинки, вопреки корректности. Для того чтобы это понять, мы вычитаем новое значение метрики (1.2) из старого (0.4), и трактуем полученную разницу (0.8). Ее можно сравнить с определенным порогом, и запретить коррекцию, если она его превосходит. Но как выбрать этот порог?

Машинное обучение

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

Решение подобных проблем можно частично поручить машине - выполнять случайные изменения параметров и выбирать те, которые дают в среднем лучший результат. Случайные изменения можно систематизировать, используя модификацию

OCR&ICR Technology White Paper

Введение.

1.1 OCR и ICR -системы. Критерии оценки систем распознавания.

Современные системы оптического распознавания символов (optical character recognition , OCR) могут быть условно разделены на две категории. Собственно OCR-системы решают ставшую классической задачу распознавания печатных символов, нанесенных на бумагу при помощи принтера, плоттера или пишущей машинки (при этом подразумевается, что любая система распознавания работает с электронным изображением документа, обычно получаемым при помощи сканера). Кроме того, выделяют класс ICR -систем (intelligent character recognition), в задачи которых входит обработка документов, заполненных печатными буквами и цифрами от руки, или, иначе говоря, распознавание рукопечатных символов.

В обоих случаях качество функционирования системы распознавания может быть оценено по ряду параметров. Однако наиболее важным параметром системы любого типа является точность распознавания, обычно выражаемая процентным соотношением

A REC = 100% * N OK / N 0 ; (1.1)

где N OK и N 0 есть количество верно распознанных символов и общее количество символов документа соответственно. Вполне естественно, что производители OCR\ICR-систем в первую очередь фокусируют внимание на оптимизации используемых алгоритмов с точки зрения точности распознавания.

1.2 Технологии ABBYY.

На протяжении последних шести лет на мировом рынке присутствуют OCR\ICR-системы, построенные на базе технологий компании ABBYY. На сегодняшний день они хорошо известны и пользуются стабильным спросом. В частности, программное ядро (engine) OCR -системы ABBYY FineReader лицензировано и успешно эксплуатируется такими известными компаниями, как Cardiff Software, Inc., Cobra Technologies, Kofax Image Products, Kurzweil Educational Systems, Inc., Legato Systems, Inc., Notable Solutions Inc., ReadSoft AB, Saperion AG, SER Systems AG, Siemens Nixdorf, Toshiba Corporations.

В рамках данного документа будут описаны базовые принципы технологий ABBYY, и, кроме того, будут подробно рассмотрены процедуры распознавания печатных (OCR) и рукопечатных (ICR) символов, реализованные в продуктах ABBYY .

Базовые принципы технологий распознавания текста ABBYY.
2.1 Принципы IPA.

Преобразование документа в электронный вид выполняется OCR-системами поэтапно: сканирование и предварительная обработка изображения, анализ структуры документа, распознавание, проверка результатов, затем производится реконструкция (воссоздание исходного вида) документа, и экспорт. Методы, применяемые при распознавании, весьма разнообразны.

Но, как известно, лучшие в мире системы оптического распознавания конструирует природа. Устройство участков нервной системы, доставляющих и обрабатывающих сигналы органов зрения, настолько сложно, что задача моделирования живых «распознавателей» в общем виде до сих пор не решена наукой. Однако базовые принципы их функционирования изучены хорошо и могут быть использованы на практике. Их насчитывают три:
Технологии распознавания, разработанные компанией ABBYY, построены именно на этих принципах. Вместо полных названий принципов часто употребляют аббревиатуру IPA , составленную из первых букв соответствующих английских слов. Очевидно, что система распознавания, работающая в соответствии с принципами IPA , будет функционировать максимально гибко и точно, на грани осмысленного действия.

Компания ABBYY , опираясь на результаты многолетних исследований, реализовала принципы IPA в рамках своих технологий оптического распознавания символов. ABBYY FineReader – единственная в мире OCR -система, которая действует в соответствии с вышеописанными принципами на всех этапах обработки документа.

В частности, на этапе распознавания фрагмент изображения, согласно принципу целостности , будет интерпретирован как некий объект (символ), только если на нём присутствуют все структурные части этого объекта, и эти части находятся в соответствующих отношениях. Поэтому ABBYY FineReader не пытается принимать решение, перебирая тысячи эталонов в поисках наиболее подходящего. Вместо этого выдвигается ряд гипотез относительно того, на что похоже обнаруженное изображение, затем каждая гипотеза целенаправленно проверяется. Причём проверять, верна ли выдвинутая гипотеза, система будет, используя принцип адаптивности , опираясь на накопленные ранее сведения о возможных начертаниях символа в распознаваемом документе.

2.2 Многоуровневый анализ документа. MDA.

На этапе анализа и предварительной обработки изображения перед любой OCR -системой стоят две основных задачи: во-первых, подготовить изображение к процедурам распознавания, во-вторых, выявить структуру документа – с тем, чтобы в дальнейшем иметь возможность воссоздать её в электронном виде. Процедуры предварительной обработки будут рассмотрены в следующей главе, сейчас же обратимся к задаче анализа структуры.

Наибольшее распространение получили так называемые методы анализа иерархической структуры документа. При анализе структуры в рамках этих методов обычно выделяют несколько иерархически организованных логических уровней. Объект наивысшего уровня только один – собственно страница, на следующей ступени иерархии располагаются таблица, текстовый блок и картинка, и так далее (рис.1). Понятно, что любой объект может быть представлен как набор объектов более низкого уровня.

Рис.1. Иерархическая структура документа
Большинство современных OCR-систем ведёт анализ документа в соответствии с одним из следующих принципов: top - down («сверху вниз») либо bottom - up («снизу вверх»). Анализ документа по принципу top - down , как следует из названия, ведётся в направлении сверху вниз. Система делит страницу на объекты, их, в свою очередь – на объекты низших уровней, и так далее, вплоть до символов. Системы, в основу которых положен второй принцип, напротив, начинают анализ с поиска одиночных знаков. Затем формируется представление о том, как найденные символы были сложены в слова, и так далее, вплоть до формирования полного электронного аналога страницы.

Для принятия решений относительно того или иного объекта нередко используется механизм так называемого «голосования», voting. Суть данного метода заключается в параллельной выработке нескольких гипотез относительно объекта и передаче их «эксперту», логическому блоку, выбирающему одну из них.

Такой метод широко практиковался на протяжении последнего десятилетия; в частности, существуют OCR-системы, буквально составленные из двух или более независимых механизмов распознавания с общим «экспертом» на выходе. Впрочем, как показала практика, подобное построение хорошо именно в тех случаях, когда OCR-программа использует «чужие», лицензированные механизмы распознавания. В ситуации, когда информация обо всех тонкостях работы каждого распознавателя недоступна производителю программы, такое решение оказывается наиболее удобным. Если же производитель разрабатывает распознаватели своими силами, то качество распознавания можно улучшить более эффективными способами. Именно о них и пойдет речь в данном документе.

Разработчики компании ABBYY создали уникальный алгоритм многоуровневого анализа документа – его называют MDA (multilevel document analysis) – позволяющий объединить преимущества обоих вышеописанных принципов. В рамках MDA структура страницы рассматривается подобно тому, как это делается по методу top - down , а воссоздание документа в электронном виде по окончании распознавания ведётся «снизу вверх», аналогично методу bottom - up . При этом в алгоритм добавлен механизм обратной связи, охватывающей все уровни анализа, что позволило резко понизить вероятность грубых ошибок, связанных с неверным распознаванием объектов высоких уровней.

Возможности нового алгоритма оказались существенно шире, чем у прототипов. Заметим, что объекты любого уровня OCR -системы ABBYY распознают в полном соответствии с принципами IPA : в первую очередь выдвигаются гипотезы относительно типов обнаруженных объектов, затем они целенаправленно проверяются. При этом учитываются найденные ранее особенности данного документа, а также сохраняется вся вновь поступающая информация.

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

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

Мы кратко рассмотрели основные принципы технологий оптического распознавания символов ABBYY. Как упоминалось, распознавание любого документа производится поэтапно, при помощи усовершенствованной процедуры многоуровневого анализа документа (MDA) . Деление страницы на объекты низших уровней, вплоть до отдельных символов, распознавание символов и «сборку» электронного документа ABBYY FineReader проводит, опираясь на принципы целостности , целенаправленности и адаптивности (IPA) .

Вышеприведённое описание весьма и весьма общо. Мы рассмотрели базовые принципы, не осветив собственно процесс распознавания. В рамках следующей главы будут подробно описаны все этапы работы с объектами разных уровней документа вплоть до отдельных символов.

Описание OCR-процедуры.

3.1 Предварительная обработка изображения.

Обработка документа начинается с получения графического образа (изображения) страницы. Современные OCR-системы поддерживают оба основных способа получения изображений, из файла и от сканера. Взаимодействие со сканером обычно осуществляется средствами универсального протокола TWAIN. Так или иначе, входными данными для OCR-программы служит цветное (глубина цвета 24 бит) либо полутоновое (глубина цвета 8 бит) изображение документа.

3.2 Распознавание объектов высших уровней. Бинаризация.

Прежде, чем приступить к структурированию страницы, выделению и идентификации блоков, OCR -система производит бинаризацию , то есть преобразование цветного или полутонового образа в монохромный (глубина цвета 1 бит). Однако современные документы часто содержат такие элементы дизайна, как фоновые текстуры или изображения. После типовой процедуры бинаризации любая текстура оставит большое количество «лишних» точек, расположенных вокруг символов и резко снижающих качество распознавания. Бинаризация фоновых изображений приводит к аналогичным последствиям. Поэтому способность системы правильно отделять текст от «подложенных» текстур и картинок очень важна.

Рис.2. Обработка процедурой IBF документа с фоновой текстурой.

Иллюстрацией последнего тезиса может послужить пример, показанный на рис.2. Как показывают многочисленные эксперименты, OCR-система, начинающая обработку этой или похожей страницы с типовой процедуры бинаризации, показывает крайне низкий результат. В среднем точность на страницах подобного вида составляет для разных систем от 31,1% до 62,7%, что фактически равносильно отказу от распознавания .

Однако ABBYY FineReader вполне корректно обрабатывает подобные документы; как показывают эксперименты, средняя точность распознавания страниц такого вида равна 98,7% . Успешно разрешить вышеописанную проблему позволяет процедура интеллектуальной фильтрации фоновых текстур, (intelligent background filtering , IBF ). Запускаемая при необходимости, в зависимости от результатов предварительного анализа страницы, эта процедура позволяет уверенно отделять текст от сколь угодно сложного фона. Более того, и выделение объектов высших уровней – текстовых блоков, таблиц, и т.п. – на страницах сложной структуры после обработки процедурой IBF выполняется значительно точнее.

Однако наличие фоновых изображений или текстур – далеко не единственная особенность документа, способная понизить качество распознавания. Например, страница, показанная на рис.3, не содержит явно выраженных фоновых элементов. Однако попытка обработки ее средствами большинства OCR -систем приведет к недопустимо низким результатам. Причиной тому невысокая контрастность оригинала, а также наблюдаемое на протяжении большинства строк заметное изменение яркости фона. Обычная OCR -система, подобрав параметры бинаризации для одного участка документа, не сможет уверенно выделить объекты на соседних участках – они окажутся либо «засвеченными», либо «зачерненными».

Рис.3. Без обработки процедурой адаптивной бинаризации этот документ распознается плохо.

Технологии, разработанные специалистами ABBYY , позволяют решить и эту проблему. Процедура адаптивной бинаризации (adaptive binarization , AB ) способна гибко выбирать оптимальные для данного участка (фрагмента строки или даже слова) параметры бинаризации. Прибегнув к адаптивной бинаризации, ABBYY FineReader исследует яркость фона и насыщеность черного цвета на протяжении всей строки и подберет оптимальные параметры преобразования для каждого фрагмента по отдельности. В результате, как строки, так и отдельные слова будут выделены правильно, что повысит общую точность распознавания A REC .

Весьма показательны результаты сравнительного исследования, проведенного на базе изображений, подобных показанному на рис.3. Методика тестирования подробно описана в , результаты представлены в нижеприведённой таблице.

Таблица 1.
Повышение качества распознавания
за счёт применения адаптивной бинаризации.

Как видно из таблицы, применение адаптивной бинаризации позволяет существенно повысить точность распознавания. С точки зрения технического исполнения, идея AB , являющейся частью усовершенствованного алгоритма MDA , заключается в использовании обратной связи для оценки качества преобразования того или иного участка. Обобщённая блок-схема алгоритма процедуры адаптивной бинаризации приведена на рис. 4.

Рис.4. Обобщённая блок-схема алгоритма процедуры адаптивной бинаризации.

3.3 Распознавание символов. Классификаторы.

Деление строки на слова и слов на буквы в программном ядре ABBYY FineReader выполняется так называемой процедурой линейного деления. Процедура завершается по достижении конца строки и передаёт для дальнейшей обработки список гипотез, выдвинутых относительно возможных вариантов деления. При этом каждой гипотезе приписывается определённый вес; по смыслу эта величина соответствует численному выражению уверенности. Соответствующий каждой из гипотез набор графических объектов уровня «символ» поступает на вход механизма распознавания символов. Последний представляет собой комбинацию ряда элементарных распознавателей, называемых классификаторами .

Рис.5. Упрощённая схема работы классификатора.

В общем виде работу классификатора иллюстрирует схема рис.5. Как показано, по окончании обработки классификатор порождает список гипотез относительно принадлежности очередного изображения к тому или иному классу, либо – в том случае, когда входные данные уже представляют собой список – соответствующим образом изменяет веса имеющихся гипотез, подтверждает или опровергает их. Выходной список всегда ранжирован по весу (уверенности).

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

Кроме того, среди важных характеристик классификатора называют точность по первому варианту распознавания, быстродействие, простоту реализации, а также устойчивость к различным искажениям, встречающимся в реальных документах (разорванные, залитые, сильно изменившие свою форму символы).

В системах распознавания, построенных на технологиях ABBYY , применяются следующие типы классификаторов: растровый, признаковый, признаковый дифференциальный, контурный, структурный и структурный дифференциальный. Рассмотрим свойства и особенности каждого из них.

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

Этот классификатор прост в реализации, работает быстро, устойчив к случайным дефектам изображения, однако имеет относительно невысокую точность. Широко используется в современных системах распознавания символов. В системе ABBYY FineReader на начальном этапе распознавания для быстрого порождения предварительного списка гипотез задействована одна из разновидностей растрового классификатора. Точность этого распознавателя , оцененная по первым трём позициям списка, составляет 99,29% 97,57% .

Признаковый классификатор.
Принцип действия: изображению ставится в соответствие N-мерный вектор признаков. Собственно классификация заключается в сравнении его с набором эталонных векторов той же размерности. Тип и количество признаков в немалой степени определяют качество распознавания. Формирование вектора (вычисление его координат в N -мерном пространстве) производится во время анализа предварительно подготовленного изображения. Данный процесс называют извлечением признаков. Эталон для каждого класса получают путём аналогичной обработки символов обучающей выборки.

Рис.6. Блок-схема работы признакового классификатора.

Сравнение каждой пары векторов заключается в вычислении оценки, характеризующей расстояние между точками в N-мерном пространстве (точка – геометрическое представление такого вектора). Пример, иллюстрирующий данный метод, приведён на рис.7; для наглядности в этом примере мы полагаем N=2, то есть вектора находятся в обычном двумерном пространстве. Координаты X0, Y0 вектора-эталона вычислены заранее, при обучении классификатора, тогда как X1, Y1 получены на этапе извлечения признаков. Понятно, что чем меньше оказывается значение оценочной величины |L|, тем точнее анализируемое изображение соответствует данному эталону, следовательно, тем более высокий вес будет присвоен классификатором этой гипотезе. В общем виде зависимость, по которой определяется |L|, записывается таким образом:

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

Точность работы признакового классификатора сильно зависит от качества выбранных признаков. Под качеством в данном случае понимается их способность максимально точно, но не избыточно, охарактеризовать начертание символа. Чётких правил отбора признаков не существует, поэтому классификаторы от разных разработчиков оперируют различными наборами признаков.

Этот тип классификаторов весьма популярен у разработчиков OCR -систем. В системе ABBYY FineReader используется признаковый классификатор с числом признаков N=224. Его назначение – то же, что у растрового классификатора – быстрое порождение списка предварительных гипотез. Точность используемой разновидности по первым трём вариантам списка гипотез составляет 99,81% , точность по первому варианту 99,13% .

Контурный классификатор.
Обособленная разновидность признакового классификатора. Отличается от последнего тем, что для извлечения признаков использует контуры, предварительно выделенные на изображении символа. Принципы функционирования, основные достоинства и недостатки совпадают с названными выше.

Этот классификатор предназначен для распознавания текста, набранного декоративными шрифтами (например, стилизованного под готический, старорусский стиль, и т.п.). Работает несколько медленнее обычного признакового классификатора. Точность контурного классификатора по первым трём вариантам 99,30% , точность по первому варианту 95,10% .

Признаковый дифференциальный классификатор.
Предназначен для различения похожих друг на друга объектов, таких, например, как буква « m » и сочетание « rn ». Анализирует только те области изображения, где может находиться информация, позволяющая отдать предпочтение одному из вариантов. Так, в случае с « m » и « rn » ключом к ответу служит наличие и ширина разрыва в месте касания предполагаемых букв.

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

В процессе обучения этого классификатора производится анализ изображений из обучающей базы. Вычисляемые при этом значения признаков интерпретируются как координаты точки в N-мерном пространстве. Соответственно, для двух различных символов получается два «облака» точек, расположенные на некотором удалении друг от друга. Когда накоплена информация о достаточном количестве точек, выполняется вычисление координат гиперплоскости. Она должна разделить пространство таким образом, чтобы «облака» оказались по разные стороны и примерно на одном расстоянии от гиперплоскости.

Рис.8. Упрощённая геометрическая модель обучения
дифференциального классификатора.

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

Входными данными для ПДК служит не только изображение, но и список гипотез, сформированный на ранней стадии распознавания. От того, в каком полупространстве и на каком расстоянии от гиперплоскости окажется точка, зависит, вес какой гипотезы будет увеличен классификатором. Сам ПДК не выдвигает новых гипотез, но изменяет веса уже имеющихся в списке, в том случае, если среди представленных в списке имеются пары гипотез, для которых существуют эталоны. При этом используется алгоритм так называемой пузырьковой сортировки. Гипотезы перебираются с конца списка и последовательно « всплывают » после сравнения с менее вероятными, при этом производится корректировка веса. Такой алгоритм гарантирует, что правильная гипотеза окажется на первом месте тогда и только тогда, когда дифференциальное сравнение со всеми вышестоящими гипотезами даёт положительный результат.

Точность ПДК не может быть вычислена методом, применявшимся для вышеописанных видов, однако может быть оценена косвенно. На рис.9 представлена схема распознавателя, использующегося в системах ABBYY. Растровый (РК) и признаковый (ПК) классификаторы используются для быстрого порождения предварительного списка гипотез. В том случае, если уверенность гипотезы с наибольшим весом P 1 не превышает заданного порогового значения P порог, контурный классификатор (КК) выдвигает ряд дополнительных гипотез. Список поступает на вход ПДК, который производит сортировку. Столь сложная схема запуска классификаторов позволяет оптимизировать соотношение качества и скорости распознавания. Точность этого распознавателя по первым трём вариантам составляет 99,87% , точность по первому варианту 99,26% .

Рис.9. Обобщённая блок-схема алгоритма распознавания (первый уровень).

Структурно-дифференциальный классификатор.
Был разработан и первоначально применялся для обработки рукописных текстов. Как и п ризнаково-дифференциальный, этот классификатор решает задачи различения похожих объектов. Входными данными для структурно-дифференциального классификатора (СДК) также являются ранжированный список гипотез и изображение символа.

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

Например, для различения C и G классификатор анализирует область изображения, соответствующую нижнему правому углу символа. Одним из индивидуальных для данной пары признаков будет наличие (или отсутствие) двух горизонтальных отрезков, расходящихся от конца обращённой книзу дуги. Сама эта дуга, как несложно видеть, присутствует в обоих символах.

Структурно-дифференциальный классификатор работает медленнее, чем все вышеназванные, а процесс его обучения ещё более трудоёмок, чем для ПДК. Поэтому СДК используется в основном для обработки тех пар символов, которые не удалось хорошо различить признаковым дифференциальным классификатором. Важным преимуществом СДК является его весьма высокая точность. Аналогично ПДК, этот классификатор использует алгоритм пузырьковой сортировки списка. Устойчив почти ко всем случайным искажениям формы символа, за исключением запечатывания.

Применяется только в системах распознавания компании ABBYY . Точность распознавателя (рис.9) при добавлении на выходе структурно-дифференциального классификатора увеличивается до 99,88% по первым трём вариантам и до 99,69% по первому варианту .

Структурный классификатор.
Одна из революционных разработок компании ABBYY. Первоначально был создан и использовался для распознавания рукопечатного текста (ICR), затем был успешно применён и для обработки.

Ввод первичных документов - оцифровка (image-processing, document capture)
В процессе подготовки информации при компьютеризации предприятия, автоматизации бухучета, возникает задача ввода большого объема текстовой и графической информации. Используя программы оптического распознавания текстов, можно оцифровывать текстовую информацию. Современные программно-аппаратные комплексы позволяют автоматизировать ввод больших объемов информации с использованием сетевых сканеров и параллельного распознавания текстов на нескольких компьютерах, одновременно.

OCR – назначение - распознавание
Большинство программ оптического распознавания текста (OCR - Optical Character Recognition) работают с растровым изображением, которое получено через факс-модем, сканер, цифровую фотокамеру или другое устройство. Назначение OCR-систем состоит в анализе растровой информации (отсканированного символа) и присвоении фрагменту изображения соответствующего символа. После завершения процесса распознавания OCR-системы должны уметь сохранять форматирование исходных документов, присваивать в нужном месте атрибут абзаца, сохранять таблицы, графику ит.д. Современные программы распознавания поддерживают все известные текстовые и графические форматы и форматы электронных таблиц, а некоторые поддерживают такие форматы, как HTML и PDF .

Поточный ввод
Для ввода больших объёмов применяется поточное сканирование документов на специальных промышленных документных сканерах. Обработка в таких системах производится в полуавтоматическом режиме с большой производительностью. Поточное сканирование документов оптимально для создания электронного архива большого объема однотипной информации (бухгалтерской документации, отчётов, заключений, научных работ и т.п.). Потоковое сканирование применяется для оцифровки: бухгалтерских и финансовых документов, договорных документов, юридических документов, архивных документов, каталогов библиотек и др.

Средства Image-processing применяются при автоматическом вводе данных в информационные системы из любых видов документов (удостоверяющих личность, бухгалтерских, юридических и т. д.) для создания электронных архивов с возможностью быстрого поиска нужных документов, при обработке больших массивов данных (перепись населения, единый госэкзамен и пр.), а также для перевода отсканированных документов, изображений и PDF-файлов в редактируемые форматы. внедрение современных средств потокового ввода позволяет снизить затраты на обработку документов более чем на 50%, достичь увеличения скорости ввода в информационные системы в 3-10 раз, обеспечить повышение удобства и качества работы с данными (высокий уровень безопасности конфиденциальных данных, сокращение количества ошибок, связанных с человеческим фактором при вводе данных), оптимизировать бизнес-процессы за счет автоматизации рутинной функции ввода данных и освобождения времени сотрудников на решение профильных задач. При этом средняя окупаемость внедрения составляет от трех месяцев до одного года.

Главными потребителями Image-processing в мире являются крупные организации (немногим более половины объема рынка в денежном выражении), на долю средних предприятий приходится около трети, остальное - малый бизнес.

Секреты сканирования на ПК Леонтьев Б К

Глава 16. OCR - системы

OCR - системы

Так называемые системы оптического распознавания символов (Optical Character Recognition - OCR) предназначены для автоматического ввода печатных материалов в компьютер, при этом сам процесс подобного ввода проходит в три этапа:

Сканирование.

Обработка.

Целостное целенаправленное адаптивное распознавание.

Из книги Linux From Scratch автора Бикманс Герард

Глава 5. Подготовка системы LFS Вступление В этой главе мы скомпилируем и установим минимальную Linux-систему. Эта система будет располагать инструментами, необходимыми для сборки окончательной системы LFS в следующей главе.Файлы, скомпилированные в данной главе, будут

Из книги Секреты сканирования на ПК автора Леонтьев Б К

Глава 16. OCR - системы Так называемые системы оптического распознавания символов (Optical Character Recognition - OCR) предназначены для автоматического ввода печатных материалов в компьютер, при этом сам процесс подобного ввода проходит в три этапа: Сканирование. Обработка.

Из книги Собираем компьютер своими руками автора Ватаманюк Александр Иванович

Глава 5 Операционные системы Для чего предназначена операционная система Популярные операционные системы Выбор операционной системы Программное обеспечение

Из книги AutoCAD 2009 для студента. Самоучитель автора Соколова Татьяна Юрьевна

Глава 4 Системы координат Ввод координат Когда программа AutoCAD запрашивает точку, команда ожидает ввода координат какой-либо точки текущего рисунка. В AutoCAD может быть включен контроль лимитов рисунка, осуществляемый командой LIMITS. В этом случае, если введенная точка

Из книги AutoCAD 2009. Начали! автора Соколова Татьяна Юрьевна

Глава 3 Системы координат Ввод координат Ввод координат в AutoCAD может осуществляться двумя способами:? непосредственно с клавиатуры, путем указания численных значений;? с использованием графического маркера (курсора), который движется по экрану с помощью устройства

Из книги SAP R/3 Системное администрирование автора Хагеман Сигрид

Из книги Серверные технологии хранения данных в среде Windows® 2000 Windows® Server 2003 автора Дайлип Наик

Глава 6 Файловые системы Файловая система обеспечивает работу важнейших функций; основные из них перечислены ниже.Поддержка целостности данных и предоставление пользователю необходимых возможностей для создания, удаления, чтения и записи файлов.Предоставление

Из книги Внедрение SAP R/3: Руководство для менеджеров и инженеров автора Кале Вивек

ГЛАВА 3 Выбор ERP-системы Системы SAP для средних и малых предприятий Большинство компаний, которые внедрят системы Планирования ресурсов предприятия (ERP) в новом тысячелетии, будут средними и малыми предприятиями. Средними и малыми предприятиями обычно считаются компании

Из книги Программирование на языке Пролог для искусственного интеллекта автора Братко Иван

Глава 14 Экспертные системы Экспертная система - это программа, которая ведет себя подобно эксперту в некоторой проблемной области. Она должна иметь способность к объяснению своих решений и тех рассуждений, на основе которых эти решения были приняты. Часто от экспертной

Из книги Windows Vista. Трюки и эффекты автора Зозуля Юрий

Глава 10 Администрирование системы Ограничения доступа к файлам и борьба с ними Управление жесткими дисками Средства диагностики системы Новые возможности администрирования с помощью групповой политики Автоматизация выполнения заданий с помощью

Из книги AutoCAD 2009. Учебный курс автора Соколова Татьяна Юрьевна

Глава 12 Восстановление системы Решение проблем, связанных с загрузкой Windows Vista Работа со средствами восстановления на установочном DVD Восстановление системы с помощью образа дискаWindows Vista является достаточно надежной операционной системой, но и она не

Из книги AutoCAD 2008 для студента: популярный самоучитель автора Соколова Татьяна Юрьевна

Глава 4 Системы координат Ввод координат Динамический ввод координат Декартовы и полярные координаты Формирование точек методом «направление – расстояние» Определение трехмерных координат Правило правой руки Ввод трехмерных декартовых координат Ввод цилиндрическихГЛАВА 5: ПРИМЕНЕНИЕ СИСТЕМЫ 1. ОБРАБОТКАПримите решение, что находится в ваших «Входящих».Сколько раз в день разгребать входящие? Творческим личностям

Из книги автора

Глава 12 Мониторинг системы Первоначальная задача администратора - установить систему, правильно распределить права доступа и настроить все необходимые сервисы. После этого многие из них складывают ручки и начинают гонять монстров по коридорам виртуального мира Doom3.