Хотелось бы провести сравнение методов, и показать , почему мы выбрали определенный, но практически - это сложно. На различных изображениях у определенных методов есть свои преимущества и свои недостатки, «в среднем» лучшего решения тоже нет, посему в 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). Ее можно сравнить с определенным порогом, и запретить коррекцию, если она его превосходит. Но как выбрать этот порог?

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

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

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

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

Глава 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.

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

Точное распознавание символов в печатном тексте в настоящее время возможно только если доступны чёткие изображения, такие как сканированные печатные документы. Точность при такой постановке задачи превышает 99%, абсолютная точность может быть достигнута только путем последующего редактирования человеком.

Для решения более сложных проблем в сфере распознавания используются как правило интеллектуальные системы распознавания, такие какискусственные нейронные сети.

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

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

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

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

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

Страница, расположенная с нарушением границ или перекосом, создает немного искаженные символьные изображения, которые могут быть перепутаны OCR.

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

Работа с OCR-системами, как правило, не должна вызывать особых затруднений. Большинство таких систем имеют простейший автоматический режим сканируй и распознавай (Scan&Read). Кроме того, они поддерживают и режим распознавания изображений из файлов. Однако для того, чтобы достигнуть лучших из возможных для данной системы результатов, желательно (а нередко и обязательно) предварительно вручную настроить ее на конкретный вид текста, макет бланка и качество бумаги.

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

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

FineReader кроме того, что знает огромное количество форматов для сохранения, включая PDF, имеет возможность прямого распознавания из PDF-файлов. Новая технология Intelligent Background Filtering (интеллектуальной фильтрации фона) позволяет отсеять информацию о текстуре документа и фоновом шуме изображения: иногда для выделения текста в документе используется серый или цветной фон. Человеку это не мешает читать, но обычные алгоритмы распознавания текста испытывают серьезные затруднения при работе с буквами, расположенными поверх такого фона. FineReader умеет определять зоны, содержащие подобный текст, отделяя текст от фона документа, находя точки, размер которых меньше определенной величины, и удаляя их. При этом контуры букв сохраняются, так что точки фона, близко расположенные к этим контурам, не вносят помех, способных ухудшить качество распознавания текста. Даже таблицы распознаются с максимальной точностью, сохраняя при этом все возможности для редактирования.

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

OCR CuneiForm способна распознавать любые полиграфические и машинописные гарнитуры всех начертаний и шрифтов, получаемые с принтеров, за исключением декоративных и рукописных. Также программа способна распознавать таблицы различной структуры, в том числе и без линий и границ; редактировать и сохранять результаты в распространенных табличных форматах. Существенно облегчает работу и возможность прямого экспорта результатов в MS Word и MS Excel (для этого теперь не нужно сохранять результат в файл RTF, а затем открывать его с помощью MS Word).

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

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

OmniPage11 - программа практически со 100% точностью распознает печатные документы, восстанавливая их форматирование, включая столбцы, таблицы, переносы (в том числе переносы частей слов), заголовки, названия глав, подписи, номера страниц, сноски, параграфы, нумерованные списки, красные строки, графики и картинки. Есть возможность сохранения в форматы Microsoft Office, PDF и в 20 других форматов, распознавания из файлов PDF, редактирование прямо в формате PDF. Система искусственного интеллекта позволяет автоматически обнаруживать и исправлять ошибки после первого исправления вручную. Новый специально разработанный модуль Despeckle позволяет распознавать документы с ухудшенным качеством (факсы, копии, копии копий ит.д.). Преимуществами программы являются возможность распознавания цветного текста и возможность корректировки голосом.

Любой современный человек, постоянно работающий с документами, время от времени задает себе злободневный вопрос: зачем повторно набирать текст, если ранее это уже кто-то сделал? У многих пользователей такая регулярно повторяющаяся задача вызывает раздражение с примесью обиды за то, что приходится бессмысленно дублировать чью-то работу. Естественно, разработчики программного обеспечения не могли остаться равнодушными к столь типичной ситуации, ликвидация которой к тому же обещала солидные прибыли. Так были созданы системы известные в России как системы оптического распознавания текста , а в англоговорящих странах - как OCR .

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

Давайте кратко пройдемся по всем основным на рынке OCR -системам и выделим главные и характерные для них особенности.

Перед тем как начать рассмотрение OCR -систем, давайте сначала хотя бы минимально приведем их классификацию для удобства дальнейшего рассмотрения. На данный момент выделяют OCR -системы (Optical character recognition, OCR ) , а также ICR -системы (I ntelligent C haracter R ecognition, ICR ). Несколько упрощая суть отличий между ними, можно считать, что ICR -системы - это следующее поколение в развитии OCR -систем.В ICR гораздо более активно и серьёзно используются возможности искусственного интеллекта, в частности, ICR -системы часто используются для распознавания рукописных текстов, декоративных непостоянных шрифтов, а также, как самый яркий пример, преодолению тех же систем по защите от спам-ботов - каптч (captcha ). Третий, пока ещё только теоретический уровень качества распознавания текста, это IWR (Intelligent word recognition, IWR), в которой считываются и распознаются не отдельные символы/точки, а считываются и распознаются связные фразы целиком.

Существует несколько систем, причисляющих себя к категории ICR . Это, преждевсего, FineReader, OmniPage Professional, Readiris Corporate, Type Reader Desktop. Давайте сравним их всех и рассмотрим возможные альтернативы.

Известные отечественные продукты

Зарубежные продукты

Три других известных продукта, получившие малое распространение на территории СНГ в силу полного отсутствия представителей и маломальского маркетинга на этих бескрайних кириллических территориях, но известные на Западе и достойные хотя бы краткого упоминания, хотя бы потому, что также позиционируют себя как продукты ICR-класса. В нише некириллического распознавания они вполне могут составить здоровую конкуренцию даже лидеру рынка - FineReader.

Первый их них, это пакет от компании I.R.I.S. Group, представляет собой очень серьёзный OCR -продукт. Достаточно сказать, что начиная с c ентября 2006 года технология от компании I .R .I .S . была лицензирована и используется в продуктах Adobe systems . Согласно внутреннему тестированию самой Adobe эта технология оказалось самой удачной из всех рассмотренных на рынке.

Нужно отметить, что это удачное стороннее решение “похоронило” свою собственную разработку Adobe - родного OCR -движка, - которая поставлялась многие годы в рамках решения , и вот теперь новый OCR Adobe доступен в виде отдельного в другие популярные продукты Acrobat . Последняя версия Readiris v12 поддерживает все версии Windows и MacOS X , а всего поддерживается работа с более чем 120 языками.

Следующая крупная разработка от американской компании - . Этот движок разработан в тесном сотрудничестве с Университетом Невада в Лас-Вегасе. Этот движок распространяется по миру сразу во многих формах, начиная от интегрирования его в крупные западные системы документооборота (D ocument I maging M anagement, DIM), и заканчивая участием во многих американских программах по автоматической обработке форм (F orms P rocessing S ervices, FPS).

Например, в 2008 году газета Los Angeles Times после собственного тестирования ведущих мировых OCR выбрала для своего внутреннего использования как раз именно TypeReader. Хочется заметить, что данный продукт доступен как в традиционном десктопном исполнении (Windows , MacOS , Linux ), в виде корпоративного web -сервиса, так и в форме облачного арендуемого приложения, способного обрабатывать любые объемы распознаваемого текста в очень короткие сроки.

Бесплатные OCR-решения

Интересный собственный движок развивает и Google . - это первоначально закрытый коммерческий OCR -движок который создала Hewlett -Packard , работая над ним в промежутке между 1985 и1995 годами. Но после закрытия проекта и прекращения его развития, HP выпустило его код как open source в 2005 году. Разработку сразу подхватила Google , лицензируя уже свой продукт под свободной лицензией Apache . На данный момент Tesseract считается одним из самых точных и качественных бесплатных движков из всех существующих.

Нужно при этом четко представлять, что Tesseract - это классическая OCR для “сырой” обработки текста, т.е. в нем нет ни графической оболочки для удобного управления процессом,ни многих других дополнительных функций. Это обычная консольная утилита (есть версии для Windows , MacOS , Linux ), на вход которой подается изображение в формате TIFF , а на выходе Tesseract выдает “чистый текст”. При этом никакого анализа компоновки текста или стилей оформления здесь не производится, это процесс распознавания в его простейшей форме.

Для большего удобства работы, в качестве графического фронтенда, с этим движком можно использовать многие утилиты, например известные или . Но все же хочется отметить, что качество бесплатного C uneiForm/OpenOCR немного превосходит показатели Tesseract , хотя во многом это полностью аналогичные продукты.

Кроме бесплатного Tesseract ещё стоит упомянуть и . SimpleOCR очень достойное решение для OCR , и хотя оно не развивается уже с 2008 года, но оно как минимум ничем не уступает Tesseract . Продукт бесплатен для любого некоммерческого использования, и поставляется для Windows всех версий. Из сильных минусов - поддержка только двух языков: английского и французского.

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