Свойства ocr системы например программы finereader заключающееся. Характеристика OCR, ICR и OMR-методов распознавания документов. Распознавание объектов высших уровней. Бинаризация

Хотя авансы, выданные искусственному интеллекту (ИИ) за последние 50 лет, ни на йоту не приблизили «умные» машины к когнитивным возможностям человека, полностью отрицать успехи в данном направлении было бы несправедливо. Наиболее очевидный и яркий пример - шахматы (не говоря уже о более простых играх). Компьютер пока не может имитировать наше мышление, но он вполне способен компенсировать данный пробел большим объемом специализированной памяти и скоростью перебора. Владимир Крамник охарактеризовал игру победившей его в 2006 г. программы Deep Fritz как «нечеловеческую» в том смысле, что она зачастую противоречила устоявшимся (человеческим) правилам стратегии и тактики.

А чуть более года назад очередное детище IBM, в свое время положившей начало триумфальным шахматным победам компьютеров (знаменитый Deep Blue), под названием Watson совершило новый прорыв, с большим отрывом победив сразу двух чемпионов популярной американской викторины Jeopardy. Показательно, однако, что хотя Watson самостоятельно озвучивал ответы, вопросы ему все же передавались в текстовом виде. Это говорит о том, что успехи во многих сферах приложения ИИ - распознавании речи и образов, машинном переводе - достаточно скромны, хотя это и не мешает нам уже сегодня применять их на практике. Наибольшие же успехи, пожалуй, демонстрируют системы оптического распознавания символов (OCR, Optical Character Recognition), с которыми наверняка так или иначе знакомы почти все пользователи ПК. Тем более, что российские разработки в данной области занимают достойное место в мире - я имею в виду ABBYY FineReader.

Немного истории

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

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

Базовые принципы

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

1. Целостность (integrity) - объект рассматривается как совокупность своих частей и (для зрительных образов) пространственных отношений между ними. В свою очередь и части получают толкования только в составе всего объекта. Этот принцип помогает строить и уточнять гипотезы, быстро отсекая маловероятные.
2. Целенаправленность (purposefulness) - поскольку любая интерпретация данных преследует определенную цель, то и распознавание представляет собой процесс выдвижения гипотез об объекте и целенаправленной их проверки. Система, действующая в соответствии с этим принципом, будет не только экономнее расходовать вычислительные мощности, но и реже ошибаться.
3. Адаптивность (adaptability) - система сохраняет накопленную в процессе работы информацию и использует ее повторно, т. е. самообучается. Этот принцип позволяет создавать и накапливать новые знания и избегать повторного решения одних и тех же задач.

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

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

Такой анализ может проводиться двумя основными способами: сверху-вниз, т. е. от составных элементов к отдельным символам, или, наоборот, снизу-вверх. Чаще всего применяется один из них, но в ABBYY разработали специальный алгоритм MDA (multilevel document analysis, многоуровневый анализ документа), который сочетает оба. Вкратце он выглядит следующим образом: структура страницы анализируется методом сверху-вниз, а воссоздание электронного документа по окончании распознавания происходит снизу-вверх, однако на всех уровнях дополнительно действует механизм обратной связи. В результате резко снижается вероятность грубых ошибок, связанных с неверным распознаванием высокоуровневых объектов.

ADRT

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

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

Именно для этого и была разработана ADRT (Adaptive Document Recognition Technology) - технология анализа и синтеза документа на логическом уровне. В конечном итоге она помогает сделать результат работы FineReader максимально похожим на оригинал. Для этого анализируется изображение всего документа, а распознанные слова объединяются в группы (кластеры) в зависимости от начертания, окружения и местоположения на странице. Таким образом программа как бы видит «логику» разметки документа и в дальнейшем может унифицировать оформление результата.

Благодаря ADRT, FineReader, начиная с версии 9.0, научился обнаруживать, распознавать и воспроизводить следующие структурные части и элементы форматирования документа:

• основной текст;
• верхние и нижние колонтитулы;
• номера страниц;
• заголовки одного уровня;
• оглавление;
• текстовые вставки;
• подписи к рисункам;
• таблицы;
• сноски;
• зоны подписи/печати;
• шрифты и стили.

Процесс распознавания

В соответствии с алгоритмом MDA, собственно распознавание начинается сверху-вниз, с уровня страницы. Понятно, что чем больше неверных решений будет сделано на ранних этапах этого процесса, тем больше будет на следующих. Именно поэтому точность распознавания так сильно зависит от качества оригиналов, но и алгоритмы их предварительной обработки могут иметь существенное значение. Так, по мере роста популярности цветных документов в FineReader появилась процедура адаптивной бинаризации (adaptive binarization, AB ). Если отсканировать сразу в черно-белом режиме документ, где присутствуют водяные знаки либо текст расположен на текстурной или цветной подложке, то на изображении неизменно появится «мусор», который затем будет довольно сложно отделить от «полезного» изображения (т. к. исходная информация о нем уже потеряна). Именно поэтому FineReader предпочитает работать с цветными или полутоновыми изображениями, самостоятельно преобразуя их в черно-белые (этот процесс и называется бинаризацией). Но и это не всё. Поскольку цвета текста и фона могут различаться в пределах страницы и даже отдельных строк, AB выделяет слова с более-менее одинаковыми характеристиками и подбирает для каждого оптимальные с точки зрения качества распознавания параметры бинаризации. Именно в этом и состоит адаптивность алгоритма, который, таким образом, является примером использования обратной связи в MDA. Понятно, что эффективность AB сильно зависит от оформления исходных документов - на тестовой базе ABBYY этот алгоритм обеспечил повышение точности распознавания на 14,5%.

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

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

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

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

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

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

Структурно-дифференциальный классификатор (СДК ) первоначально применялся для обработки рукописных текстов. Его задача состоит в различении таких похожих объектов, как «C» и «G». Таким образом, СДК основывается на признаках, характерных для каждой пары символов, процесс его обучения еще сложнее, чем у ПДК, а скорость работы ниже, чем у всех предыдущих классификаторов.

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

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

* оценка всего первого уровня OCR-алгоритма ABBYY
** оценка для всего алгоритма после добавления соответствующего классификатора

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

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

Не только OCR

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

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

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

Системы распознавания текста или 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);
• Обратном дискретном косинусном преобразовании.

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

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

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

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

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

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

Strong thresholding	Weak thresholding

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

• Если символ лежит на 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.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 .

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

   2.1 Принципы IPA.

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

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

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

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

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

   Технологии распознавания, разработанные компанией 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) .

   
   Вышеприведённое описание весьма и весьма общо. Мы рассмотрели базовые принципы, не осветив собственно процесс распознавания. В рамках следующей главы будут подробно описаны все этапы работы с объектами разных уровней документа вплоть до отдельных символов.
3. Описание 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), затем был успешно применён и для обработки.