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

На правах рукописи

Шоломов Дмитрий Львович

Синтаксические методы контекстной обработки в задачах распознавания текста.

Специальность 05 13 01 «Системный анализ, управление и обработка информации»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва, 2007

003066197

Работа выполнена в Институте системного анализа РАН в лаборатории 8-1 «Модели экономической и финансовой динамики»

Научный руководитель Член-корреспондент РАН,

доктор технических наук, профессор Арлазаров Владимир Львович Институт системного анализа РАН

Официальные оппоненты Доктор технических наук, профессор

Петровский Алексей Борисович Институт системного анализа РАН

Кандидат физико-математических наук,

Николаев Дмитрий Петрович

Институт проблем передачи информации РАН

Ведущая организация: Институт проблем информатики РАН

Защита состоится «/5"» октября 2007 года в /У2^ часов на заседании диссертационного совета Д 002 086 02 при Институте системного анализа РАН, расположенном по адресу. 117312, Москва, проспект 60-летия Октября, д 9

С диссертацией можно ознакомится в библиотеке Института системного анализа Российской академии наук.

Автореферат разослан «>2.» сентября 2007 года

Ученый секретарь

диссертационного совета Д 002 086 02 доктор технических наук, профессор

А И Пропой

Общая характеристика работы

Актуальность темы исследования

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

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

Основной качественной характеристикой при вводе документов с бумажного носителя является скорость ввода В промышленных системах доля автоматически вводимых полей составляет 70-90% Более высокий процент достигается редко -реальные документы, как правило, имеют дефекты, привнесенные при печати и сканировании, помарки при ручном заполнении полей Для профессионального оператора среднее время, затрачиваемое на проверку поля обычно в 1 5-2 раза больше чем при последовательном чтении и вводе текстового значения В связи с этим, если для подтверждения предъявляется более 50% полей, скорость автоматизированного ввода сравнима с вариантом ручного ввода Учитывая, что вариант автоматизированного ввода использует более дорогостоящие технические средства,

системы с долей автоматической обработки менее 60-70% обычно становятся неэффективными Априорное знание синтаксической структуры поля позволяет существенно сократить количество ошибок распознавания, а также уменьшить число правильно распознанных полей с признаком сомнительности, тем самым увеличивая скорость Таким образом, синтаксические методы контекстной обработки в целом могут существенно повысить эффективность промышленных систем ввода деловых документов, а задача разработки таких методов является весьма актуальной

Предмет работы

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

В рамках диссертации проводится исследование и разработка методологических основ, а также конкретных моделей, методов и средств для решения задач

• моделирования структуры полей ввода на документах с точки зрения задачи распознавания и контекстной обработки,

• автоматической коррекции результатов распознавания с учетом синтаксической и семантической структуры поля,

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

• локализации недостоверных фрагментов распознанного поля,

• нормализации распознанного значения,

• классификации значений полей ввода на формах,

• практической реализации алгоритмов контекстной обработки в рамках систем автоматизированного ввода деловой информации

Цель работы

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

Методы исследования

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

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

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

За счет использования универсальных синтаксических методов Система работает с большим количеством типов полей, структура которых имеет различную степень жесткости Наличие единых средств синтаксического описания при помощи РБв-грамматики и синтаксических диаграмм позволило разработать специальные алгоритмы обработки конкретных типов полей в сжатые сроки При этом процедуры обработки различных полей ввода используют единое алгоритмическое ядро Заложенные в синтаксических алгоритмах идеи по их практической реализации позволяют использовать код повторно и строить галереи стандартных функций отображения синтаксических атомов на результаты распознавания поля, представленные АР-сетями

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

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

• ввод документов персонифицированного учета в Московском и Санкт-петербургском отделениях Пенсионного фонда России,

• ввод платежных документов в Сбербанке РФ и других коммерческих банках,

« ввод отгрузочных разнарядок для ОАО "Сибнефть",

• ввод анкет школьников и студентов, анкет-заявок на изготовление "Социальной карты москвича",

• ввод счетов-фактур, договоров, актов, накладных и товаросопроводительных документов в Магнитогорском металлургическом комбинате

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

• 6-ая Международная конференции «Распознавание образов и анализ изображений новые информационные технологии» Великий Новгород, 2002,

• The International Conference on Machine Learnmg, Technologies and Applications (MLMTA'03), 2003, USA,

• 6Л German-Russian Workshop on Pattern Recognition and Image Understandmg (OGRW-6), 2003,

• The International Conference on Machine Leainmg, Technologies and Applications (MLMTA'04), 2004, USA

Кроме того, подходы, отраженные в работе, неоднократно представлялись на семинарах Института системного анализа РАН и Института проблем информатики РАН

Публикации

По теме диссертации автором опубликовано одиннадцать работ Шесть из них опубликованы в рецензируемых научных изданиях, рекомендуемых ВАК

Структура и объем работы

Диссертация состоит из трех глав, введения, заключения и списка литературы Работа изложена на 121 странице машинописного текста, содержит 42 иллюстрации и 9 таблиц Список литературы включает 136 наименований

Содержание работы

Во введении обосновывается актуальность темы диссертации, ее научная новизна Рассматривается предмет и цели работы, указаны методы исследования и практическая значимость Кроме того, имеется информация о структуре и объеме диссертации

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

• Статистические модели языка (БЬМ-модели),

• Метрические пространства над словами (метрика Левенштейна и Хэмминга),

• Скрытые марковские модели (СММ);

• Искусственные нейронные сети (ИНС),

• Формальные языки и грамматики

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

Наряду с моделями, в главе приведены основные методы, применимые к рассматриваемой задаче Некоторые из методов непосредственно относятся к указанным моделям, например методы сглаживания при использовании БЬМ-моделей, алгоритм Баума-Уэлша обучения скрытых марковских моделей, алгоритм обратного распространения для обучения многослойных ИНС. Отдельное внимание уделено методу динамического программирования поиска оптимального управления для дискретной управляемой системы Динамическое программирование применительно к задаче контекстной обработки, используется для поиска наименьшего расстояния между словами (или множествами слов) Метод проиллюстрирован алгоритмом нахождения минимального расстояния Левенштейна.

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

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

Существующие методы в чистом виде неплохо решают ряд задач контекстной обработки в общей постановке, таких как обработка результатов распознавания с использованием словаря, статистических моделей языка и СММ, хорошо развита тематика обнаружения и коррекции ошибок в тексте Тем не менее, во многих случаях указанные методы работают недостаточно хорошо для решения более специализированных задач, например распознавания полей, синтаксис которых полностью либо частично задается при помощи грамматик Также, следует отметить, что существующие алгоритмы, использующие семантику, носят слишком специальный характер, общая схема алгоритма при этом "заточена" для обработки конкретного поля и не может быть использована для полей других типов Это вызвало потребность разработай универсальных контекстных алгоритмов с единым ядром, применимых к различным полям и допускающих использование семантических связей

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

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

В первой части приводится математическая постановка задачи контекстной обработки, задаются способы описания результатов распознавания и способы задания структуры поля Кроме того, указываются виды возникающих подзадач Вводится понятие языка, грамматики и способов ее описания, определяется РОБ-грамматика, предложенная автором для задания синтаксиса распознаваемых полей Также в главе приведена классификация полей, встречаемых на формах, по типам и указаны методы, используемые для их обработки

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

Второй использует частичное синтаксическое описание поля при помощи РОБ-грамматик Для данных методов указаны алгоритмы их реализации и приведены качественные характеристики.

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

Пусть граф задан парой (У,Е), где V - множество вершин графа, а Е - множество его ребер. Множество вершин V = {у,, у+,у_} занумеровано, включает начальную и конечную вершины у+и у_, соответственно Причем в начальную вершину не ведет ни одного ребра, а из конечной вершины ни одного ребра не выходит Множество Е = {еу} - это множество ребер графа Ребро еу ведет из вершины v, в вершину vJ Путь через ребра е+Л,е№,. -,е,м<*'е<* - обозначим чеРез е,й Каждому ребру е;у приписана оценка рц перехода по данному ребру, при этом =1 Оценку перехода по пути е;[,2 % обозначим через р1)(2 ^ Считаем, что

I

р№ ¡к ,р,4), где Ер - монотонная функция Как правило, в качестве Р

берется произведение, сумма или минимум р^ Наилучший путь е^ % без учета контекстных ограничений тот, у которого оценка перехода р ^ наибольшая Ес-

к

ли ру соответствует вероятностям, то р^ -3Р^) = ПР,1

5=1

Пусть задан алфавит А = {а,} и каждой вершине V, соответствует символ а, из алфавита А. В этом случае вершины АР-сети соответствуют альтернативам распознавания символов, а ребра - оценкам перехода от одной альтернативы к другой АР-сеть содержит информацию как о сегментации текстового поля, так и об оценках распознанных символов Каждый путь е ,к, проходящий через АР-сеть, соответствует некоторому текстовому значению аг[ , полученному конкатенацией символов &ч, соответствующих вершинам сети, через которые лежит путь е'ю 'к' Пример АР-сеш приведен на рисунке 1.

Описание предварительных результатов распознавания в виде АР-сети допускает возможность последующего неоднозначного выбора окончательного текстового результата распознавания в зависимости от дополнительной контекстной информации

Рисунок 1 Пример АР-сети

В случае печатного или рукопечатного распознавания текст сегментируется на символы достаточно хорошо Это позволяет представлять результаты распознавания в виде так называемой АР-цепи - АР-сети особого вида Множество вершин АР-цепи разделено на группы Каждая группа соответствует знакоместу Вершины одной группы соответствуют альтернативам распознавания символа на одном знакоместе Удобным представлением АР-цепи является АР-матрица Столбцы матрицы соответствуют знакоместам Ячейка АР-матрицы содержит пару <а,р>, где а - код символа, р - оценка распознавания данной альтернативы

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

• восстановление текстового значения,

• классификация текстового значения,

• приведение распознанного значения к нормальной форме,

• оценка степени надежности распознанного значения,

• локализация ненадежных фрагментов,

• нахождение опорных фрагментов

Подходы, предложенные во второй главе, используются для решения задач в каждой из перечисленных постановок

Первый подход называется синтаксическим При распознавании таких полей, как "Почтовый адрес", "Наименование организации", "Сумма прописью" на банковских документах удобно и оправданно использовать синтаксическое описание поля Синтаксический подход использует описание поля при помощи порождающей КС-грамматики в форме синтаксических диаграмм (СД) Задача контекстной обработки, в данном случае, заключается в нахождении оптимального пути в АР-сети, который в то же время соответствует синтаксису поля, заданному при помощи СД Процедура нахождения оптимального пути является сложной оптимизационной задачей АР-сеть и синтаксическая диаграмма могут состоять из сотен вершин, среди которых встречаются "тяжеловесные" словарные вершины Например,

такие вершины как "Улицы " и "Города" состоят из десятков тысяч элементов Поэтому алгоритмы должны удовлетворять разумным требованиям к скорости В предложенной реализации алгоритма используется ряд оптимизационных методов, таких как итеративная сегментация АР-цепи и кэширование результатов отображения вершин СД на АР-цепь Блок-схема верхнего уровня алгоритма изображена на рисунке 2

Начало

Инициализация тяжеловесных вершин

СД и разметка АР-цепи Инициализация необходима для уменьшения количества слов-кандидатов в словарных вершинах

Выбор допустимых точек разрезания АР-цепи

Поиск оптимального пути через АР-цепь, одновременно укладывающегося в СД (ОП процедура) ОП алгоритм базируется на технике динамического программирования с одновременным проходом по АР-цели и СД

^ Конец

Рисунок 2 Блок-схема верхнего уровня процесса синтаксической обработки

Основной стадией алгоритма является поиск оптимального пути через АР-цепь (ОП-процедура) Она базируется на методе динамического программирования и состоит в следующем

Пусть и,, ,пк - множество вершин СД. Обозначим начальную и конечную вершины п1,пк, символами п+ и и_, соответственно Ребро из вершины и, в вершину п] обозначим еу Произвольный путь в СД из вершины п+ в п_ представим последовательностью вершин пц, , п^ Оптимальным путем является путь пч, , в СД, отображающийся на АР-цепь с наилучшей оценкой Такое отображение обозначается последовательностью позиций АР-цепи р0,рх,

Перераспознавание некоторых вершин

СД на урезанном алфавите Пере распознавание числовых вершин СД существенно улучшает качество распознавания

Получение финального нормализованного

текстового значения из фрагментов, соответствующих вершинам СД Финальная оценка надежности

О = ри < р. <... < рч=1, где I - длина АР-цепи. При этом каждая вершина в отображается на интервал с позиции ргЛ по позицию рт. разбивая АР-цепь на 5 непересекающихся интервалов [0 = /VР2]'•*•> 1Л-1>Л = ']-

Пример: На рисунке 3 изображена АР-матрица (Ь), соответствующая распознан* ной дате "2Т^ипе/1990" (а). ¡Оптимальный путь п+щп2плп$п(1п_ через СД показан толстыми стрелками. Этот путь отображается на АР-цепь как /Л>ЩР\РгР-$Р<\> разделяя ее на 7 интервалов (вершины л, ,п отображаются на [р(),р0) и [р^р5]}-Отображение показано изогнутыми стрелками в верхней части рнсунка 3.

Ь\ I I 1 ®

нг п. пА я, лй п_

* -—

2 1 1 1 4 Г1 е / 1 9 9 0

5 1 / 1 и и с 1 / 3 0

! 4 I

01 2 Э а 5 Б 7 6 9 ю Т1 13

» р[ /'1 Г! Р1 Р,

(ПОГИГ! уви

Рисунок 3. Рукопечатная дата (а) АР-матрица, соответствующая распознанной дате (Ь) Синтаксическая диаграмма даты (с)

ОП-нроцедура использует так называемую матрицу отображения (ММ), см. рисунок 5. ММ является матрицей размера к х /, где к - количество вершин СД, а / -длина (количество знакомест) АР-цепп. Ее столбцы соответствуют позициям АР-цепи, а строки - вершинам СД. Ячейка содержит наилучший путь из вершины п: в вершину п, и информацию об отображении этого пути па интервал [0, /] АР-цепи. Если ГЦ - наилучший путь в СД, а --р,} - его отображение

на интервал [0, Д то ячейка (/, /) содержит оценку отображения ¿. , а также ссыпки на предыдущую вершину СД н предыдущую позицию АР-цепи {пргп, ррг^) = (пг тРг) ■110 этим ссылкам наилучший путь может быть рекурсивно восстановлен.

Пусть обозначает матрицу отображения ММ размера к у. I и пусть Мы представляется следующими тремя матрицами: - матрицей опенок }, М -

матрицей ссылок на предыдущие позиции АР-цепи {рргп} и м^- матрицей ссылок

на предыдущие вершины СД Пусть С - множество разрезов, которое является подмножеством позиций АР-цепи ОП-процедура заключается в расчете матрицы отображения по следующему алгоритму, см рисунок 4

мм-сомритщ М4„,, С, 80)

1 // очистить матрицу отображения

2 fory <- 1 to / // по всем знакоместам АР-матрицы

3 if j<tC then // если позиция не является точкой разрезания

4 continue

5 for i 0 toj -1 // по всем знакоместам АР-матрицы до позиции }

6 if leC then // если 1 не точка разрезания

7 continue

8 for all «„ M,[v,i] > 0 // по всем вершинам СД Пу с оценкой Яу > 0

9 for all rtw 3ew // по всем вершинам СД П^ со соединенным с й„

10 if REJECT-BY-LOCATION(

11 continue

12 ■f S,(i,j) = 0 // если П№ отобразилась на [у] с нулевой оценкой

13 continue

14 S<-M,{v,«]+S„(»,y) // рассчитать новую оценку

15 if M5[w,y]<S then // если новая оценка выше предыдущей

16 // сохранить новую оценку

17 // сохранить ссылку на предыдущее знакоместо

18 M„[w,y]<- n. // сохранить ссылку на предыдущую вершину СД

19 endif

20 endfor

21 endfor

22 endfor

23 endfor

24 return

Рисунок 4. Алгоритм расчета матрицы отображения

После того, как расчет ММ завершен, клетка (к,Г) содержит оценку наилучшего пути В случае если ды= 0, синтаксическая диаграмма не отображается на АР-цепь В противном случае, как наилучший путь пц. л^, так и отображение р0. р, восстанавливаются рекурсивно по ссылкам пргеу,ррге„ на предыдущую вершину

СД и позицию АР-цепи

На рисунке 5 в качестве примера, показан расчет матрицы для даты '21/|ипе/1990' СД даты и АР-цепь показаны на рисунке 3, оптимальный путь в СД п+пхп1пап%пьп_ помечен жирными стрелками Он отображается на АР-цепь следующим образом 0,0,2,3,7,8,12,12

Финальная оценка оптимального пути - 1125 Как можно увидеть на рисунке 5, оптимальный путь выигрывает у двух альтернативных путей в клетках (4,7) и (8,12) Эти альтернативные пути не участвуют в дальнейших вычислениях

0123456789 10 11 12

И1 «К ^85

»2 135^ 4255

п з

«4 390 > ^590

«5

"6 Ч; —, К 25

«7 ^55

ч| 88! 1

Рисунок 5. Расчет матрицы отображения

Синтаксический подход был использован при распознавании поля "Почтовый адрес" на анкетах Пенсионного фонда России (форма АДВ-1) Для анализа допустимого синтаксиса почтового адреса была использована база данных Государственной налоговой службы РФ, а также анализировалась 15 тысячная выборка из примерно 10 ООО ООО реальных адресов в текстовом формате Полученное синтаксическое описание представляет собой довольно большой граф, состоящий из 45 вершин и 5 диаграмм, вложенных друг в друга в 2 уровня СД содержит "тяжеловесные" словарных вершин, такие как "Улицы" - 49 042 наименований, "Населенные пункты" - 11449 наименований и "Города" - 1156 наименований Все словари содержат элементы в морфологически нормализованной форме.

Множество из 3674 заполненных образцов формы АДВ-1 было разделено на 2 части - обучающее множество ^ и тестовое множество 52 состоящих из 1260 и 2414 изображений соответственно

Таблица 1 содержит качественные характеристики синтаксического подхода при обработке рукопечатного адреса Столбец БА соответствует распознаванию с использованием синтаксического подхода, столбец СЛ - распознаванию без контекстной обработки

Из таблицы видно, что качество распознавания почтовых адресов на пенсионных анкетах увеличилось с -55% до -90% (считая правильно распознанные поля) Благодаря этому общее время обработки документа значительно сократилось Синтаксический подход универсален и позволяет получать хорошие результаты без использования специальных знаний, таких как база данных адресов РФ и т д При

этом алгоритм отображения синтаксической диаграммы на АР-цепь достаточно гибок и позволяет использовать такого рода семантическую информацию Таблица 1 Экспериментальные данные

^(1387 адресов) SA CR

Адресов на этапе контекстной обработки Правильно распознанных Правильно распознанных без сомнения Правильно распознанных с сомнением Неправильно распознанных Неправильно распознанных с сомнением Неправильно распознанных без сомнения 1375 (100%) 1223 (88,9%) 717 (52,1%) 918 (66,8%) 293 (21,3%) 305 (22,2%) 424 (30,8%) 152(11,0%) 658(47,9%) 135 (9,8%) 492 (35,8%) 17 (1,2%) 166 (12%)

52 (2718 адресов) SA CR

Адресов на этапе контекстной обработки Правильно распознанных Правильно распознанных без сомнения Правильно распознанных с сомнением Неправильно распознанных Неправильно распознанных с сомнением Неправильно распознанных без сомнения 2689 (100%) 2314(86,1%) 1562(58,1%) 1694 (63,0%) 752 (28,0%) 620(23,1%) 810(30,1%) 375(13,9%) 1127(41,9%) 330 (12,3%) 775 (28,8%) 45 (1,7%) 352 (13,1%)

Среднее время обработки адреса на компьютере Pentium IV 1500 MHz составляет менее 0 16 секунды

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

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

Пример, Центральный банк РФ предъявляет ряд требований к заполнению поля "Назначение платежа" на платежных поручениях Например, требуется указать налог на добавленную стоимость (НДС) Поэтому большинство полей содержат текстовую конструкцию типа "В том числе НДС-18% - 1140-00" либо "НДС не облагается", причем форма записи может существенно меняться от поля к полю Также, текстовые конструкции типа "По договору №1267/99 от 18 01 99г " довольно часто присутствуют в данном поле из-за того, что платеж, как правило, связан с некоторым договором

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

Необходимость создания РОБ-грамматики была вызвана отсутствием удобного стандартного языка описания синтаксиса полей. Использование таких метаязыков, как нотация Бэкуса-Наура (БНФ), регулярных выражений в чистом виде не очень удобно Синтаксическое описание при использовании БНФ слишком громоздко, например, из-за того, что в этом случае каждый раз необходимо заново определять такие нетерминалы, как число и слово. Регулярные выражения более компактны, но при этом они хуже визуально воспринимаются человеком И в том и в другом случае осложнена работа со словарями - весь список значений приходится задавать прямо в грамматическом описании. РОБ-грамматика определяется посредством но-

тации Бэкуса-Наура следующим образом

i <DIGIT> "0" | | "9"

2- <LETTER> = "a" | | V

3- <РШСТ> \\ H | H^tt | n w | Ц ц | \\ " 1

4 • <CHARACTER> = <DIGIT> | <LETTER> | <PONCT>

5: <NUMBER> = <DIGIT>+

6 <WORD> = <LETTER>+-

7 <STRING> 3S£ <CHABACTER>+

8 <RANGE> = <NUMBER> <MUMBER>

9 <ЕЫШ> = <NUMBER> ("," <NUMBER>) *

10: <LEN_RESTRXCT> = <RANGE> | <ENÜM>

11 <LEXICON_ID> = <LETTER> <STRING>

12 <CTEXT_NODE> = <STRING> | <STRING>

13 <LEX_NODE> = »<" <LEXICON_ID> ">"

14. <NUM~NODE> = <#> | "<#" <LEN_RESTRICT>

15 <WORD_NODE> = <$> | "<$" <LEN~*RESTRICT>

16 <chrsEq_node> = "<*" <STRINB> ">" | »<*{" <LEN RESTRICT> ">" <STRING> ">"

17 <START_NODE> =

18 <FINISH_NODE> • =

19- <TEBM> = CCTEXT NODE> | <LEX NODE> | <*ЮМ NODE> 1

<WORD NODE> | -CCHRSEQ NODE> | <START HODE> 1

<FINXSH NODE>

20 <OR_EXPR> <TEBM> ( <BRK EXPR> | <OR EXPR> " 1" <OR EXPR>

21- <BRK_EXPR> = "(" <CAT EXPR> ")" | " (" <OR EXPR> ")" |

" (" <BRK EXPR> ») "

22 <CAT_EXPR> <OR EXPR> " " <OR EXPR>

23 <PDS~EXPR> = <CAT_EXPR> I <OR_EXPR> | <BRK_EXPR>

При этом определяются следующие основные типы синтаксических примитивов

статический текст, слово из определенного словаря, число, слово, последователь-

ность символов, начало и конец гголя. Например, PDS-выражение <+Х#1-2> <MONTH> I <#2> <#2, 4><-> определяет дату.

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

1. отображение статического текста и словарных вершин,

2. отображение чисел, слов и последовательностей символов,

3. отображение PDS-выражений,

4. поиск оптимального пути на АР-цепи,

5. получение финального текстового значения.

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

I Наилучшие альтернативы Г I Ключевые слова EXS1 Числа ШШ PDS выражения

по сч * 0103.11 f. сумма . <#2>\ 20

шшшммшмн ^^ш^^шшя^щшшяшш

"з" "карта m tl 1313 иг 0 а.-11.00 Сумма 2325 00 В. Т.Ч. НДС J0% 35Î-50

Fl Г В • " "I Ejl EU ЕЕ23Э LUJ BSS^SSD :.___' " " «¡е53--!П FFT] I----; Г--i i

¡За картридж по сч. 1313 от 08.11.00 Сумма 2325-00 а т.ч. НДС(20%) - 387-50 Рисунок 6. Оптимальный путь

В таблице 2 приведены результаты сравнения качества распознавания PDS алгоритма при использовании словаря (PDS+L), без использования словаря (PDS) и результатов OCR распознавания без контекстной обработки (CK).

Из таблицы видно, что при использовании PDS+L количество правильно распознанных полей увеличивается 40%. В то же время PDS+L работает хуже на неправильно распознанных полях без сомнения (2,4%). Качественная оценка PDS близка к PDS+L. Полей распознанных правильно без сомнения больше у PDS+L, зато неправильных и без сомнения меньше у PDS. Предпочтительнее использование PDS+L т.к. он даст допустимое количество ошибок, при этом количество правильных и надежных полей повышается существенно (на -6%).

Для сравнения синтаксического и PDS подходов было использовано поле "Почтовый адрес" на анкетах Пенсионного фонда РФ (форма АДВ-1). Данное иоле имеет довольно свободный синтаксис и в то же время может быть описано синтаксическими диаграммами полностью. Результаты эксперимента показали, что синтаксический подход превосходит PDS подход на 4-S%. 11ри этом разработка и настройка

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

Таблица 2. Результаты PDS алгоритма полученные при обработке поля "Назначение платежа"

S (758 полей) PDS+L PDS CR

всего форм 758 (100%)

непривязанных форм 14 (1,8%)

полей распознано 709 (93,5%)

полей распознанных правильно 503 (71%) 489 (69%) 432 (61%)

правильно / без сомнения 361 (51%) 319 (45%) 174 (25%)

правильно / с сомнением 142 (20%) 170 (24%) 258 (36%)

полей распознанных неправильно 206 (29%) 220(31%) 277 (39%)

неправильно / без сомнения 17 (2,4%) 13 (1,8%) 7 (1,0%)

неправильно / с сомнением 189(27%) 207 (29%) 270 (38%)

символов распознанных правильно 98,1% 97,6% 94,3%

символов распознанных неправильно 1,9% 2,4% 5,7%

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

Пример. Будем называть множество учебных заведений города Москвы объектами У каждого объекта есть множество вариантов его написания, например, объект "Средняя Общеобразовательная Школа № 9 г. Москвы" может быть написан, как "Школа 9", "Московская Средняя Школа 9", "СОШ № 9 Волгоградского р-на Москвы " и не может быть написан как "Школа №11"

Формально задача классификации определяется следующим образом Пусть задана пятерка >, где

• О - множество образцов,

• С - множество классов С = {С,}, если все классы известны заранее, либо С = {С,,С*}, где С - неизвестный класс, будем считать, что в случае если образец не принадлежит ни одному из классов С„ он принадлежит С*,

• Wcй- обучающая выборка образцов,

• "^г с Л - тестовая выборка образцов,

• - "экспертный" классификатор - функция \¥ и —> р'с', где

л

Р" = { р е Я" р = (ри , рп),р, € Я, £р, = 1}, « - число классов опреде-

ляется человеком (экспертом), который указывает - к каким классам и с какой вероятностью (либо оценкой) принадлежат образцы из выборок и \¥т

Требуется найти функцию классификации (классификатор) / О -» Р'с', который "наилучшим образом" приближает / на тестовой выборке \¥т Приближение оценивается различными способами, например, при помощи функции ошибки е(/) = гДе /"(/и/г) - заданная метрика В простейшем слу-

чае, когда классификация однозначна, т е

Л®) = (0, ,0,1,0, 0), а И(/Х(т\ /») = Ц ^ ,

[0, /,(©) = /2(а>)

е(/) является числом ошибочных классификаций на тестовой выборке Оптимальным классификатором является тот, для которого функция е(/) минимальна

В терминах данного определения в описанном примере множество учебных заведений Москвы соответствует множеству классов С = {С,} Множество образцов О. = {со} состоит из АР-цепей, полученных в результате распознавания текстового поля с алфавитом, состоящим из букв русского языка, цифр и знаков препинания

В работе построен первичный классификатор следующим образом Пусть задано множество признаков А = {а]} и функции выделения признаков из образца а] (со), которые выдают вероятность нахождения признака а] в образце со Пусть обучающая выборка содержит образцы >У = {со}, и функция /5 задана как

/5(со) = (0, ,0,1,0, ,0), если соеС„ те классификация однозначна

1

Введем следующие обозначения

• V/, = (й). й) е С;} - множество образцов из обучающей выборки, которые fs классифицирует, как принадлежащие классу С,,

• = {<ае№ яДг») ^ р' } (р+- константа) - множество образцов обучающей выборки, в которых присутствует признак а] (с вероятностью не меньше р*),

• V/* = {й> е а ¡(со) > р*} - множество образцов из множества V/,, в которых присутствует признак а} (с вероятностью не меньше р+),

• р = ' " ' - вероятность того, что признак aJ принадлежит классу С, Здесь

- мощность множества и считается, что а] (со) вьщеляет признаки однозначно

В случае неоднозначного выделения признаков, полагаем ру =

Пусть Рц (а) = руа] (а) + р1]а] (со), где р = 1 - р - вероятность того, что рбра-

зец а принадлежит С, по признаку а], обозначим Р1 =11^ " вероятность того,

]=1

что образец со принадлежит классу С, (к - число признаков), положим Р = (Р1, ;Р„)- Определим первичный классификатор выражением

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

• классификация в случае, когда не все классы известны заранее,

• классификация с обучением на зашумленной выборке,

• классификация с использованием техники сглаживания,

• классификация с автоматической редукцией зависимых признаков

В работе исследованы различные функции выделения признаков из образца, наилучший результат был получен с функцией наложения текстового значения, соответствующего признаку, на АР-цепь с использованием алгоритма МСШЯ При этом 81 5% образцов было классифицировано правильно, а в 89.7% случаев правильный класс содержался в списке из нескольких наиболее вероятных вариантов

Использование техники сглаживания в условиях недостаточно репрезентативной обучающей выборки при экспериментах с наименованиями учебных заведений дало улучшение 3 7% на,тестовой выборке, состоящей из 935 образцов

Классификатор реализован таким образом, что позволяет обучаться на зашумленной выборке с использованием процедуры поиска эквивалентных словосочетаний Процедура состоит в следующем рассматриваются все пары образцов (а>рю2) из обучающей выборки соответствующих одному классу С, В том случае, когда образцы различаются на некотором небольшом подмножестве слов (1-2 слова), эти подмножества объявляются эквивалентными словосочетаниями В частности, при обучении классификатора на выборке с ошибками распознавания, производилась автоматическая замена словосочетаний на эквивалентные, в тех случаях, когда частота встречаемости последних значительно превосходила частоту встречаемости исходных В работе для частоты встречаемости использован термин "вес словосочетания" Использование классов эквивалентности словосочетаний и процедуры выделения зависимых признаков дало улучшение порядка 5% на той же выборке из 935 образцов наименований учебных заведений

к

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

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

Система массового ввода Cognitive Forms представляет собой программный комплекс, предназначенный для ввода стандартизованных форм документов Система состоит из набора модулей, установленных в локальной сети и взаимодействующих посредством асинхронной передачи пакетов с данными - графическими образами документов и результатами распознавания Система позволяет обрабатывать десятки тысяч документов в сутки В зависимости от объема потока документов Система устанавливается в различных сетевых топологиях и с различным количеством рабочих станций Пример топологии системы по вводу документов пенсионного страхования в Московском пенсионном фонде приведен на рисунке 8

Cognitive Forms предназначена для использования на платформе Win32, кроме того ее ограниченный вариант портирован на Power Macintosh и Linux Система включает 39 основных и вспомогательных исполняемых модулей (ехе) и 216 динамически подгружаемых библиотек (till)

Схема обработки документов системой Cognitive Forms состоит из двух основных технологических стадий

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

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

Важной составной частью системы Cognitive Forms является реализованная автором подсистема контекстной обработки Она предназначена для улучшения качества распознавания полей ввода В частности, подсистема формирует финальное текстовое значение по предварительным результатам распознавания, выносит решение о надежности распознавания, преобразует AP-сеть исходя из контекстных соображений, производит отбраковку поля в случае, если результаты распознава-

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

Подсистема распознавания документа Cognitive Fonns

■i ' мздабд

-

THE

'УЖ

'К-

Интерфейс

sbw5 .дар1 "WW л

i» - RfS-s? Jf-",-' 5it;

.. _ .--■¿."•sib- ~ „ глжя '^ЭдГ.'

Модули контекстной обработки

;3 ¿.»--{¿лейest - ейктавдй^евй-. f описаиййг!-:' втобран^^йяз;

ESX

¿egg»"«

Служебные модули

ii»CHSR ;

Подсистема контекстной обработки полей ввода

Рисунок 7. Структура подсистемы контекстной обработки

1. Уровень интерфейса. Модуль RCX принимает запросы на контекстную обработку полей ввода В системе Cognitive Fonns запросы поступают непосредственно от модуля OFR, осуществляющего распознавание страницы. На вход RCX получает описание поля и результаты распознавания в виде АР-цепи

2. Модули контекстной обработки. К ним относятся модули SA, PDS, ESX, а также пользовательские модули В зависимости от класса контекста, описанного в свойствах обрабатываемого поля, модуль RCX вызывает один или несколько модулей второго уровня, непосредственно осуществляющих контекстную обработку Модуль SA реализует алгоритм, основанный на синтаксическом описании поля при помощи набора синтаксических диаграмм, PDS - алгоритм, основанный на частичном синтаксическом описании шля, ESX - классификацию распознанного текстового значения.

3. Служебные модули. К служебным модулям относится MCHSR, осуществляющий поиск текстового фрагмента в АР-цепи, VCB реализующий работу с подключаемыми словарями и справочниками, а также другие специальные модули

В заключительной части третьей главы рассмотрены примеры внедренных проектов по массовому вводу структурированных документов, реализованных на базе системы Cognitive Forms, созданной при непосредственном участии автора Общий перечень проектов составляет несколько десятков и включает в себя внедрения в

широком спектре организаций - от крупных корпоративных структур до небольших банков, больниц и т д Среди внедренных проектов отметим следующие 1 Ввод документов пенсионного страхования. Одним из наиболее массовых по объему обработанных документов, реализованных на базе программного комплекса Cognitive Forms, является проект по вводу документов государственного пенсионного страхования Изначально, проект был внедрен в Московском отделении пенсионного фонда РФ, впоследствии разработанная технология была адаптирована и внедрена в Санкт-Петербургском отделении и в ряде региональных центров в Беларуси. К настоящему времени, годовой объем ввода документов пенсионного страхования составляет более 3 миллионов Схема организации системы по вводу документов пенсионного страхования приведена на рисунке 8 Синтаксические подходы предложенные автором были использованы при распознавании анкет Пенсионного фонда РФ - форм АДВ-1, СЗВ-1, СЗВ-1а, СЗВ-16

Рисунок 8 Схема модулей системы и организации технологии массового ввода документов в МПФ РФ

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

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

3. Ввод банковских документов. Платежные поручения, платежные требования, инкассовые поручения и мемориальные ордера являются широко распространенными документами в бухгалтериях организаций и банках, производящих расчеты между организациями На базе системы Cognitive Forms было реализовано коробочное решение Cognitive Forms Bank, организующее потоковый ввод банковских документов Система внедрена и работает в нескольких десятках коммерческих банков, среди которых Сбербанк России и Газпромбанк. Синтаксические алгоритмы, предложенные в работе, существенно увеличивают скорость ввода перечисленных документов

4. Ввод отгрузочных разнадядок в ОАО "Сибнефть". В 2001 году на базе системы Cognitive Forms был реализован программно-аппаратный комплекс по вводу отгрузочных разнарядок для ОАО "Сибнефть" В рамках данного проекта в подсистеме контекстной обработки были реализованы функции повышающие качество распознавания полей ввода, а кроме того, функции определения типа поля по его значению на этапе привязки шаблона формы исходя из контекстных соображений

5. Ввод счетов-фактур на Магнитогорском металлургическом комбинате. Одним из недавних внедрений системы массового ввода документов с использованием синтаксических методов контекстной обработки является программный комплекс по вводу счетов-фактур на ОАО "ММК" Комплекс был запущен в промышленную эксплуатацию в 2005 году. Для ОАО "ММК" объем ежегодного оборота счетов-фактур составляет порядка 300 000 документов, при пиковой нагрузке в конце года, объем поступающих документов превышает 2 000 в день Синтаксиче-

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

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

Основные результаты работы

1 Формализована задача контекстной обработки, выделен ряд характерных подзадач Предложены методы описания структуры результатов распознавания в виде сетей и матриц

2 Предложены методы описания полей ввода при помощи порождающих КС-грамматик Хомского в виде синтаксических диаграмм Предложен метаязык синтаксического описания (PDS-грамматика), применимый для описания полей, структура которых определена частично

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

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

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

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

Список работ, опубликованных по теме диссертации

1 Арлазаров В В, Постников В В , Шоломов Д JI. Cognitive Forms - система массового ввода структурированных документов II Сб. «Управление информационными потоками», Москва, Едиториал УРСС, 2002 стр 35-46. .

2 Шоломов ДЛ. Интерпретация нечетко распознанных текстовых конструкций // Сб трудов 6-ой Международной конференции «Распознавание образов и анализ изображений новые информационные технологии». Великий Новгород, 2002

3. Sholomov D.L. Syntactical Approach to Post-Processing of Fuzzy Recognized Text. // Proc of The International Conference on Machine Learning, Technologies and Applications, CSREA Press, pp 115-121,2003, USA

4 Postnikov VV, Sholomov D.L, Marchenko A.E FlexiDocs: The Template Dnven Document Recognition Technology // Proc of the 6th German-Russian Workshop on Pattern Recognition and Image Understanding (OGRW-6), 2003

5 Sholomov D L, Interpreting the Indistinctly Recognized Textual Constructions. //Pattern Recognition and Image Analysis, 2003, vol 13, no 2, pp 353-355

6. Постников В В Марченко АЕ Шоломов ДЛ Разбор структурированного документа в модели с нечеткой логикой И Сб. трудов ИСА РАН "Документооборот Концепции и инструментарий ", Москва, Едиториал УРСС, 2004, стр 71-82

7 Vassih V Postnikov, Dmitry L Sholomov Post-processing of OCR Results Using Automatically Constructed Partially Defined Syntax // Proc of The International Conference on Machine Learning, Technologies and Applications, CSREA Press, pp 814-820, 2004,, USA

8 Шоломов Д Л Синтаксический подход к пост-обработке нечетко распознанного текста Н Сб трудов ИСА РАН "Документооборот. Концепции и инструментарий.", Москва, Едиториал УРСС, 2004, стр. 193-207

9 Шоломов Д Л Постников В В Марченко А А Усков А В Пост-обработка результатов OCR распознавания использующая частично определенный синтаксис // Сб трудов ИСА РАН "Интеллектуальные информационные технологии Концепции и инструментарий.", 2005, Том 16, стр 146-163

10 Шоломов Д Л Коррекция распознанного текста с использованием методов классификации // Сб трудов ИСА РАН, 2007, Том 17, стр 352-366

11 Шоломов Д Л. Постников В В Никольский Н Н Рынок систем обработки деловых документов Перспективы и направления развития // Сб трудов ИСА РАН, 2007, Том 17, стр 181-191

Подписано в печать 11 09 2007 Исполнено 12 09 2007 г Печать трафаретная

Заказ № 696 Тираж 100 зкз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, (495)975-78-56 www autoreferat ru

ВВЕДЕНИЕ.

Актуальность темы исследования.

Предмет работы.

Цель работы.

Методы исследования.

Практическая ценность и апробация работы.

Публикации.

Структура и объем работы.

1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ КОНТЕКСТНОЙ ОБРАБОТКИ.

1.1. N-граммы.

1.2. Динамическое программирование.

1.2.1. Дискретный процесс управления.

1.2.2. Метод динамического программирования.

1.2.3. Алгоритм Левенштейна.

1.2.4. Обзор работ.

1.3. Скрытые марковские модели.

1.3.1. Определение СММ.

1.3.2. Обзор работ.

1.4. Нейронные сети.

1.5. Методы коррекции и валидации текстов.

1.5.1. Словарные методы.

1.5.2. Вероятностные методы.

1.5.3. Техника похожих ключей.

1.5.4. Сравнение методов.

1.6. Классификационные методы.

1.7. Методы синтаксического анализа.

1.7.1. Формальные языки. Компилирование.

1.7.2. Естественные языки. Компьютерная лингвистика.

1.8. Выводы.

2. СИНТАКСИЧЕСКИЕ МЕТОДЫ КОНТЕКСТНОЙ ОБРАБОТКИ.

2.1. Представление результатов распознавания. AP-сеть, АР-цепь, АР-матрица.

2.2. Формальные языки и грамматики, синтаксические диаграммы.

2.2.1. Язык.

2.2.2. Понятие грамматики. ГрамматикаХомского.

2.2.3. Нотация Бэкуса-Наура.

2.2.4. Синтаксические диаграммы.

2.2.5. PDS грамматика.

2.3. Классификация типов полей на формах.

2.3.1. Словарное поле.

2.3.2. Текст на естественном языке.

2.3.3. Поле с заданным синтаксисом.

2.3.4. Поле, описываемое синтаксисом частично.

2.3.5. Поле с нефиксированным текстовым представлением.

2.3.6. Поля со специальными ограничениями.

2.4. Постановка задачи контекстной обработки.

2.4.1. Восстановление текстового значения.

2.4.2. Классификация т екстового значения.

2.4.3. Приведение распознанного значения к нормальной форме.

2.4.4. Оценка степени надежности распознанного значения.

2.4.5. Локализация ненадежных фрагментов.

2.4.6. Нахождение опорных фрагментов.

2.5. Поиск заданного текстового фрагмента в АР-цепи. Алгоритм MCHSR.

2.5.1. Структура результатов распознавания.

2.5.2. Описание алгоритма MCHSR.

2.6. Синтаксический подход.

2.6.1. О подходе.

2.6.2. Основная алгоритмическая схема.

2.6.3. ОП-процедура.

2.6.4. Эксперименты и результаты.

2.7. Подход с использованием частично-определенного синтаксиса.

2.7.1. Предпосылки создания.

2.7.2. Схема алгоритма.

2.7.3. Эксперименты и результаты.

2.7.4. Выводы.

2.8. Классификация полей с нефиксированным текстовым представлением.

2.8.1. Признаки и функции выделения признаков.

2.8.2. Построение первичного классификатора.

2.8.3. Сравнение функций выделения признаков.

2.8.4. Задача с неизвестными классами.

2.8.5. Сглаживание.

2.8.6. Проблема зависимости признаков.

2.8.7. Реализация и выводы.

2.9. Выводы.

3. ВНЕДРЕНИЯ И ОСОБЕННОСТИ ТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ.

3.1. Система массового ввода структурированных документов.

3.1.1. Обзор системы.

3.1.2. Стадии технологической цепочки ввода документов.

3.1.3. Основные компоненты системы.

3.2. Подсистема контекстной обработки.

3.2.1. Назначение подсистемы.

3.2.2. Структура подсистемы.

3.2.3. Процесс создания функций контекстной обработки.

3.3. Внедренные проекты и особенности технической реализации.

3.3.1. Ввод документов пенсионного страхования.

3.3.2. Ввод анкет школьников и студентов.

3.3.3. Ввод банковских документов.

3.3.4. Ввод отгрузочныхразнадядок в ОАО "Сибнефть ".

3.3.5. Ввод счетов-фактур в Магнитогорском Металлургическом Комбинате.

Актуальность темы исследования

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

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

Основной качественной характеристикой при вводе документов с бумажного носителя является скорость ввода. В промышленных системах доля автоматически вводимых полей составляет 70-90%. Более высокий процент достигается редко - реальные документы, как правило, имеют дефекты, привнесенные при печати и сканировании, помарки при ручном заполнении полей. Для профессионального оператора среднее время, затрачиваемое на проверку поля обычно в 1.5-2 раза больше чем при последовательном чтении и вводе текстового значения. В связи с этим, если для подтверждения предъявляется более 50% полей, скорость автоматизированного ввода сравнима с вариантом ручного ввода. Учитывая, что вариант автоматизированного ввода использует более дорогостоящие технические средства, системы с долей автоматической обработки менее 60-70% обычно становятся неэффективными. Априорное знание синтаксической структуры поля позволяет существенно сократить количество ошибок распознавания, а также уменьшить число правильно распознанных полей с признаком сомнительности, тем самым увеличивая скорость. Таким образом, синтаксические методы контекстной обработки в целом могут существенно повысить эффективность промышленных систем ввода деловых документов, а задача разработки таких методов является весьма актуальной.

Предмет работы

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

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

• моделирования структуры полей ввода на документах с точки зрения задачи распознавания и контекстной обработки,

• автоматической коррекции результатов распознавания с учетом синтаксической и семантической структуры поля,

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

• локализации недостоверных фрагментов распознанного поля,

• нормализации распознанного значения,

• классификации значений полей ввода на формах,

• практической реализации алгоритмов контекстной обработки в рамках систем автоматизированного ввода деловой информации.

Цель работы

Целью диссертации является разработка универсальных синтаксических методов и алгоритмов контекстной обработки полей ввода на структурированных документах и анализ их качественных характеристик. Также целью является комплексное рассмотрение задачи контекстной обработки - классификация типов полей ввода, изучение, построение и сравнение методов, пригодных для улучшения качества их распознавания. Практическая цель работы заключается в реализации подсистемы контекстной обработки, использующей алгоритмы и методы, предложенные в работе, к решению практических задач автоматизированного ввода деловой информации в рамках системы Cognitive Forms [АПШ02], далее по тексту - Системы.

Методы исследования

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

Научная новизна

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

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

Практическая ценность и апробация работы

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

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

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

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

• ввод документов персонифицированного учета в Московском и Санкт-петербургском отделениях Пенсионного фонда России,

• ввод платежных документов в Сбербанке РФ и других коммерческих банках,

• ввод отгрузочных разнарядок в ОАО "Сибнефть",

• ввод анкет школьников и студентов, анкет-заявок на изготовление "Социальной карты москвича",

• ввод счетов-фактур, договоров, актов, накладных и товаросопроводительных документов в Магнитогорском металлургическом комбинате.

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

• 6-ая Международная конференции «Распознавание образов и анализ изображений: новые информационные технологии». Великий Новгород, 2002;

• The International Conference on Machine Learning, Technologies and Applications (MLMTA'03), 2003, USA;

• 6th German-Russian Workshop on Pattern Recognition and Image Understanding (OGRW-6), 2003;

• The International Conference on Machine Learning, Technologies and Applications (MLMTA'04), 2004, USA.

Кроме того, подходы, отраженные в работе, неоднократно представлялись на семинарах Института системного анализа РАН и Института проблем информатики РАН.

Публикации

По теме диссертации автором опубликовано одиннадцать работ. Шесть из них опубликованы в рецензируемых научных изданиях, рекомендуемых ВАК.

Структура и объем работы

Диссертация состоит из трех глав, введения, заключения и списка литературы. Работа изложена на 121 странице машинописного текста, содержит 42 иллюстрации и 9 таблиц. Список литературы включает 136 наименований. Работа организована следующим образом:

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

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

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

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

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

Основные результаты, изложенные в диссертации, опубликованы в работах [АПШ02], [Шол02], [PSM03], [Sho03a], [Sho03b], [PS04], [ПМШ04], [Шол04], [ШПМ05], [Шол07а], [Шол07Ь]. В период с 2002 по 2007 годы результаты неоднократно докладывались и обсуждались на международных научных конференциях в России и за рубежом. Помимо этого методы синтаксической обработки были представлены автором на ряде семинаров Института Системного Анализа РАН и Института Проблем Информатики РАН.

Заключение. Выводы.

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

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

2. Предложены методы описания полей ввода при помощи порождающих КС-грамматик Хомского в виде синтаксических диаграмм. Предложен метаязык синтаксического описания (PDS-грамматика), применимый для описания полей, структура которых определена частично.

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

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

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

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

1. АВ95. J.C. Anigbogu and A. Belaid, Hidden Markov Models in Text Recognition, HIJPRAI, Vol.9, No.6, pp. 925-958,1995

2. Arn94. D.J. Arnold, Lorna Balkan, Siety Meijer, R.Lee Humphreys and Louisa Sadler Machine Translation: an Introductory Guide. HBlackwells-NCC, London

3. ASU86. Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools, //N.Y., Addison-Wesley, 1986.

4. BDS92. Peter F. Brown and Vincent J. Delia Pietra and Peter V. deSouza and Jennifer C. Lai and Robert L. Mercer. Class-Based n-gram Models of Natural Language. I I Computational Linguistics, vol. 18, no. 4, pp. 467-479,1992.

5. BGS97. Djamel Bouchaffra and Venu Govindaraju and Sargur N. Srihari. Postprocessing of Recognized Strings Using Nonstationary Markovian Models. I/IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21 no. 10, pp. 990-999,1997.

6. BGS98. D. Bouchaffra and V. Govindaraju and S. Srihari A Methodology for Determining Probability of Correctness of Recognizer Scores UProc. IEEE Conf. Computer Vision and Pattern Recognition, Santa Barbara, Calif., June 1998

7. Bis95. Christopher M. Bishop Neural Networks for Pattern Recognition // Oxford University Press (1995).

8. BJG03. Steven Beitzel, Eric Jensen and David Grossman. A Survey of Retrieval Strategies for OCR Text Collections. UProc. of2003 Symposium on Document Image Understanding Technology, April 2003

9. Blul. Michael Blumenstein and Brijesh Verma. A Neural Network for Real-World Postal Address Recognition.

10. BRR02. Anja Brakensiek, Jorg Rottland and Gerhald Rigoll. Handwritten Address Recognition with Open Vocabulary Using Character N-grams. UProc. of 8th International Workshop on Frontiers in Handwriting Recognition (IWFHR), 2002.

11. CC95. C.L.A. Clarke and G.V. Cormack. On the use of regular expressions for searching text. //Technical Report CS-95-07, Department of Computer Science, University of Waterloo, February 1995

12. CDD97. C. Cracknell, A. C. Downton, L. Du. An Object-Oriented form Description Language and Approach to Handwritten Form Processing. H4th International Conference Document Analysis and Recognition (ICDAR '97) Volume I and Volume II. 1997. pp. 180.

13. CFM92. Casey, D. Ferguson, K. Mohiuddin, and E. Walach, "Intelligent forms processing system," Machine Vision and Applications, vol. 5, no. 3 pp. 1443-1455,1992

14. CG98. Stanley F. Chen, Joshua Goodman. An empirical study of smoothing techniques for language modeling //Technical Report TR-10-98, Computer Science Group, Harvard University, 1998

15. CGM+98. F. Cesarini, M. Gori, S. Marinai, and G. Soda, "INFORMys: A Flexible InvoiceLike Form-Reader System" //IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 7, pp. 730-745, July 1998

16. СКР92. Doug Cutting, Julian Kupiec, Jan Pedersen, Penelope Sibun, A practical part-of-speech tagger, HProc. of the third conference on Applied natural language processing, March 31-April 03,1992, Trento, Italy

17. CMM99. David Y. Chen, Jianchang Mao, K. Mohiuddin. An Efficient Algorithm for Matching a Lexicon with a Segmentation Graph. //Fifth International Conference on Document Analysis and Recognition, India, September 1999.

18. CV89. Cherkassky, V., and Vassilas, N. Back propagation networks for spelling correction. //Neural Networks 1, 3 (July), 166-173,1989

19. Dam90. Damerau. F. J. Evaluating computer-generated domain-oriented vocabularies. //Inf. Process. Manage. 26, 6, pp 791-801.1990

20. Dav62. Davidson, L. Retrieval of misspelled names in an airline passenger record system. //Community A CM 5,169-171,1962

21. DEG90. Deffiier, R, Eder, K, and Geiger, H. Word recognition as a first step towards natural language processing with artificial neural nets. //In Proceedings of KONNAI-90. 1990

22. DHS01. R. 0. Duda, P. E. Hart and D. G. Stork, Pattern Classification (2nd ed.), //John Wiley and Sons, 2001

23. Doul. Shona Douglas. Customising Grammar and Style Checker Rules //Centre for Cognitive Science University of Edinburgh

24. Elt88. Elliot, R. J. 1988. Annotating spelling list words with affixation classes. //AT&T Bell Labs Int. Mem. Dec. 14.

25. ESS96. Emelyanov N.E., Solovyev A.V., Schelkacheva I.V. Classification of Structured Data Representations ПProceedings of the Third International Worbhop on Advances in Databases and Information Systems./ MEPhI Publishing, Vol. 2,1996

26. For73. G. D. Forney. The Viterbi algorithm. //Proceedings of the IEEE 61(3):268-278, March 1973

27. FYBOO. C.O. de Almendra Freitas, A. El Yacoubi, F. Bortolozzi, R. Sabourin. Brazilian

28. Bank Check Handwritten Legal Amount Recognition. HProc. of the XIII Brazilian Symposium on Computer Graphics and Image Processing.

29. GI01. Luis Gravano, Panagiotis G. Ipeirotis and oth. Using q-grams in a {DBMS} for Approximate String Processing //IEEE Data Engineering Bulletin, Vol.24 No.3 pp. 2834, 2001

30. GMW97. Dafydd Gibbon, Roger Moore, Richard Winski. Spoken Language System Assessment (Handbook of Stnadards and Resources for Spoken Language Systems) HMouton de Gruyter, 1997.

31. Har72. Harmon L.D. Automatic recognition of print and script. HProc. IEEE 60, (Oct.), p.p.l165-1176,1972.

32. HHS91. Т. К. Ho and J. J. Hull and S. N. Srihari. Word Recognition with Multi-Level Contextual Knowledge. HProc. of the lstlnt'l Conference on Document Analysis and Recognition, October 1991, pp. 905-915.

33. HPR1. Young-Sook Hwang, Bong-Rae Park, Hae-Chang Rim. A Contextual Postprocessing Model for Korean OCR using Synthesized Statistical Information

34. HS82. Hull J. J., Srihari S. N. Experiments in text recognition with binary n-gram and Viterbi algorithms. //IEEE Trans. Patt. Anal. Machzne Intell. PAMI-4, 5 (Sept.), pp.520-530,1982

35. Hul92. J. Hull, "A Hidden Markov Model for Language Syntax in Text Recognition,"

36. HI 1th IAPR Int 7 Conf. Pattern Recognition, The Hague, The Netherlands, 1992, pp. 124-127.

37. Hul96. Incorporating Language Syntax in Visual Text Recognition with a Statistical Model //IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, No. 12, 1996

38. JDM02. Anil K. Jain and Robert P. W. Duin and Jianchang Mao. Statistical Pattern Recognition: A Review. //IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 1, pp. 4-37, 2002.

39. Kem93. Kempe, A. (1993). A stochastic Tagger and an Analysis of Tagging Errors.

40. HInternal paper. Institute for Computational Linguistics, University of Stuttgart.

41. Kim99. Dong Kyue Kim. Efficient Algorithms for Approximate String Matching with Swaps HJ. Complexity Vol.15 pp. 128-147,1999

42. KMC95. Andras Kornai, K.M. Mohiuddin, Scott D. Connell. An HMM-Based Legal Amount Field OCR System for Checks HIEEE International Conference on Systems, Man and Cybernetics, Vancouver ВС, October 1995, 2800-2805,1995

43. KPB87. Kahan, S , Pavlidis, T, Baird. H. S. On the recognition of characters of any font size. //IEEE Trans Patt. Anal. Machine Intell. PAMI-93 9, 274-287,1987

44. Kuk88. Kukich, K. Variations on a back-propagation name recognition net. //In Proceedings of the Advanced Technology Conference, vol 2

45. Kuk92. Kukich K. Techniques for automatically Correcting Words in Text. IIACM computing survey Computational Linguistics, vol. 24, no. 4, pp. 377-439,1992

46. S95. V.V. Lam, L. Javanbakht, and S. X. Srihari, "Anatomy of a form reader," Proc. 2nd Int'l Conf. on Document Analysis and Recognition, pp. 287-292,1995

47. G95. E. Lethelier, M. Leroux, and M. Gilloux, "An Automatic Reading System for

48. Handwritten Numeral Amounts on French Checks," UProc. Third Int 7 Conf. Document Analysis and Recognition, pp. 92-97,1995.

49. Lowrance, R., Wagner, R. 1975. An extension of the strmg-to-strmg correction problem. HJ. ACM22, 2 (Apr.), 177-183.

50. Mai97. Michael H. Mailburg. Comparative Evaluation of Techniques for Word Recognition Improvement by Incorporation of Syntactic Information. H4th International Conference Document Analysis and Recognition (ICDAR '97) August 1997, pp784.

51. Mis99. Misyurev A.V., Hand-Printed Character Recognition by Neural Networks. UProc. of the 5th German-Russian Workshop on Pattern Recognition and Image Understanding (GRWS98), 1999.

52. MM89. E. W. Myers and W. Miller. Approximate matching of regular expressions. HBulletin of Mathematical Biology, pages 7-37,1989.

53. MNROO. Andrew K. McCallum and Kamal Nigam and Jason Rennie and Kristie Seymore Automating the Construction of Internet Portals with Machine Learning HJ. Information Retrieval vol.3 no.2pp. 127-163, 2000

54. МР43. McCulloch, W. S. and Pitts, W. H. A logical calculus of the ideas immanent in nervous activity. //Bulletin of Mathematical Biophysics, 5:115-133,1943.

55. MS99. C. D. Manning, H. Schutze. Foundations of Statistical Natural Language //Processing. MIT Press, 1999

56. Mye95. E. W. Myers. Approximately Matching Context-Free Languages //Proceedings of the 2nd South American Workshop on String Processing pp. 38-52,1995

57. NavOl. Gonzalo Navarro. A Guided Tour to Approximate String Matching. ПАСМ Computing Surveys, Volume 33, Issue 1, Pages: 31-88, 2001

58. Neu75. D. Neuhoff. The viterbi algorithm as an aid in text recognition. I/IEEE Trans. Information Theory, 21:222-226,1975.

59. Nik03. Nikolaev D.P. Segmentation-based binarization method for color document images. //Proceedings of 6th Open Russian-German Workshop on Pattern Recognition and Image Understanding, Novosibirsk 2003, pp. 190-193.

60. NSG96. D. Niyogi, S.N. Srihari, and V. Govindaraju. Analysis of printed forms. HH.Bunke and P.S.P. Wang, editors, Handbook on Optical Character Recognition and Document Image Analysis. World Scientific Publishing Co., Singapore, 1996.

61. Oku76. Okuda, Т., Tanaka, E., Kasai, T. A method of correction of garbled words based on the Levenshtein metric. I/IEEE Trans. Comput., 1976.

62. Pos99. Postnikov V.V., Flexible forms identification. HProc. of the 5th German-Russian Workshop on Pattern Recognition and Image Understanding (GRWS98), 1999.

63. PSM03. Postnikov V.V., Sholomov D.L., Marchenko A.E. FlexiDocs: The Template Driven Document Recognition Technology. //Proceedings of the 6th German-Russian Workshop on Pattern Recognition and Image Understanding (OGRW-6), 2003.

64. PZ83. Pollock J. J., Zamora A. Collection and characterization of spelling errors in scientific and scholarly text. HJ. Amer. Sot. Inf. Sci. 34,1, 51-58,1983

65. Rab89. L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. //Proceedings of the IEEE 77(2):257-286, February 1989.

66. RenOl. J. Rennie Improving multi-class text classification with naive bayes. //Master's thesis, Massachusetts Institute of Technology, 2001

67. RH74. E. Riseman and A. Hanson. A contextual postprocessing system for error correction using binary n-grams. I/IEEE Trans. Computer, 23:480-493,1974.

68. RHW86. Rumelhart D. E., Hinton G. E., Williams R. J. Learning representations by back-propagating errors //Nature (London). N323. p. 533-536., 1986

69. RJ86. L. Rabiner and B. Juang. An Introduction to Hidden Markov Models. IIIEEE ASSP Magazine, pages 4-16,1986.

70. Ros58. Rosenblatt, F. The perceptron: A propabilistic model for information storage and organization in the brain. I I Psychological Review 65,1958

71. SA93. Gerard Salton and James Allan. Selective Text Utilization and Text Traversal. //Hypertext'93 Proceedings, November 14-18,1993, Seattle, Washington, USA

72. Sch78. J. Schuermann. A Multifont Word Recognition System for Postal Address Reading. UIEEE Transactions on Computers, C-27, 8, August 1978, 721-732. 9.

73. Sch94. Helmut Schmid. Part-of-speech tagging with neural networks //Proceedings of the 15th conference on Computational linguistics Vol. 1 pp. 172-176,1994

74. Seb99. Fabrizio Sebastiani Machine learning in automated text categorisation: a survey. //Pisa, IT, 1999

75. Seg03. Ilya Segalovich. A fast morphological algorithm with unknown word guessing induced by a dictionary for a web search engine. HMLMTA- 2003. Las Vegas, 2003

76. Sho03a. Sholomov D.L. Syntactical Approach to Post-Processing of Fuzzy recognized Text. UProc. of The International Conference on Machine Learning, Technologies and Applications, CSREA Press, pp. 115-121. June 2003, USA

77. Sho03b. Sholomov D.L., Interpreting the Indistinctly Recognized Textual Constructions. 11 Pattern Recognition and Image Analysis, 2003, vol. 13, no. 2, pp. 353-355.

78. Sit61. Sitar E.J. Machine recognition of cursive script: The use of context for error detection and correction. I'/Bell Labs Tech. Mem, 1961.

79. SK83. Sankoff, D., Kruskal, J. B. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. HAddison-Wesley, Reading, Mass. 1983.

80. SN98. M. SchuJ31er and H. Niemann. A HMM-based System for Recognition of Handwritten Adress Words. Uln 6th Int. Workshop on Frontiers in Handwriting Recognition (IWFHR), pages 505-514, Taejon, Korea, 1998.

81. SRG04. Speech Recognition Grammar Specification Version 1.0 W3C Recommendation 16 March 2004 http://www.w3.org/rR/2004/REC-speech-grammar-20040316/

82. Sri97. Sargur N. Srihari. Document image understanding. UProc. of1986fall joint computer conference on Fall joint computer conference, November 1997. pp. 87-96

83. SS02. Sari, Т.; Sellami, M. MOrpho-LEXical analysis for correcting OCR-generated Arabic words (MOLEX) //Frontiers in Handwriting Recognition, 2002. Proceedings. Pp. 461-466

84. SSR1. Sargur Srihari and Yong-Chul Shin and Vemulapati Ramanaprasad and Dar-Shyang Lee. A System to Read Names and Addresses on Tax Forms.

85. St90. L. Stringa. "A New Set of Constraint-Free Character Recognition Grammars"

86. EE Transactions on Pattern Analysis and Machine Intelligence. December 1990 (Vol. 12, No. 12)pp.: 1210-1217.

87. TC96. Teahan. W. J. & Cleary, J.G. The entropy of English using PPM based models. UProc. Data Compression Conference. IEEE Society Press, 53- 62,1996.

88. TIC98. Teahan, W.J., Inglis, S., Cleary, J.G. & Holmes, G. Correcting English text using PPM models //In Proceedings DCC'98, edited by Storer, J.A. & Cohn, M., IEEE Computer Society Press, 1998.

89. TJ05. Huihsin Tseng, Daniel Jurafsky, Christopher Manning. Morphological features help POS tagging of unknown words across language varieties. //Fourth SIGHAN Workshop on Chinese Language Processing, 2005.

90. Tou78. Toussaint, G. T. The use of context in pattern recognition I I Pattern Recognition 10, pp. 189-204,1978

91. Tru99. A. Trujillo, Engines: Translation Engines: Techniques for Machine Translation l/Springer-Verlag, London, 1999.

92. Ueb93. Joerg P. Ueberla. The Generalized NPOS Language Model for Speech Recognition, IICMPTTR 93-09,1993.

93. Vit67. Andrew J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. HIEEE Transactions on Information Theory 13(2):260~ 269, April 1967.

94. Vou03. Atro Voutilainen (2003): "Part-of-speech tagging". Hln: Ruslan Mitkov, editor: "The Oxford Handbook of Computational Linguistics", pp. 219- 232. Oxford University Press.

95. Wag74. Wagner, R. A. Order-n correction for regular languages. I I Community ACM 17, 5 (May), 265-268,1974.

96. WCh76. Wong, С. K. Cnandra, A. K. Bounds for the string editing problem. HJ. ACM23,1 (Nov.), 13-16,1976.

97. Web99. A. Webb, Statistical pattern recognition, HOxford University Press Inc., New York, 1999

98. WF74. Wagner, R. A., Fisher, M.J. The string-to-string correction problem. HJ. ACM21, l(Jan.), 168-178,1974.

99. WHD95. Lars WiedenhGfer Hans-Giinther Hein Andreas Dengel. Post-Processing of OCR Results for Automatic Indexing I/ICDAR Proceedings of the Third International Conference on Document Analysis and Recognition Vol. 2 p. 592,1995

100. WHS92. P. K. Wong and Т. К. Ho and S. N. Srihari. Firm Name Recognition for Automatic Address Interpretation. UProc. of the 5th {USPS} Advanced Technology Conference, November 1992pp. pp. 757-770.

101. XF03. XForms 1.0, W3C Recommendation 14 October 2003. http://www.w3.org/TR/2003/REC-xforms-20031014/

102. АБМ05. Андреев A.M., Березкин Д.В., Морозов B.B., Симаков K.B. Автоматическая классификация текстовых документов с использованием нейросетевых алгоритмов и семантического анализа. НИнтелтек изд-во, 2005.

103. АЕ02. Арлазаров В. Л., Емельянов Н. Е.Системы обработки документов. Основные компоненты. Направление информационными потоками" Сборник трудов Института системного анализа РАН/ М., УРСС. 2002 г.

104. AKC00. Арлазаров В. JL, Куратов П. А., Славин О. А. Распознавание строк печатных текстов. "Методы и средства работы с документами". //Сборник трудов Института системного анализа РАН/М., УРСС. 2000 г.

105. АПШ02. Арлазаров В.В, Постников В.В., Шоломов Д.Л. Cognitive Forms система массового ввода структурированных документов. ИВ сб. «Управление информационными потоками», Москва, Едиториал УРСС, 2002. стр. 35-46

106. Арл02. Арлазаров В. В. Управление информационными потоками в системе автоматического ввода документов. I/"Управление информационными потоками", Сборник трудов Института системного анализа РАН./М., УРСС, 2002 г.

107. АС96. Арлазаров B.JL, Славин О.А. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. IIИнформационные технологии и вычислительные системы 1996, No 1., стр. 48-54.

108. АУ78. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. ИМ.: Мир, 1978

109. БЕОЗ. Богачева А.Е., Емельянов Н.Е. Семантическая Модель документа.

110. ПСистемные исследования. Ежегодник/ М„ УРСС. 2003 г. с.:360-375.

111. БелбО. Беллман Р. Динамическое программирование. ИМ.: Изд-во иностранной литературы, I960.

112. ГМ06. М.В. Губин А.Б. Морозов. Влияние морфологического анализа на качество информационного поиска IIТруды RCDL'2006, Суздаль 2006

113. Еме88. Емельянов Н.Е. Виды представления структурированных данных.

114. Теоретические основы информационной технологии. Сб. тр. Вып. 22. -М.-.ВНИИСИ, 1988

115. Зал80. Зализняк А.А. Грамматический словарь русского языка. ИМосква, Русский язык, 1980

116. Кар02. Ю.Г.Карпов. Методы построения трансляторов. 2002 г

117. ККС02. Кляцкин В. М., Котович Н. В., Славин О. А. Многопроходная схема распознавания документов с обучением. //"Управление информационными потоками" Сборник трудов Института системного анализа РАН М., УРСС. 2002 г.

118. Кну78. Д.Кнут. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. Перевод с англ. ИМ: Изд. "Мир", 1978.

119. Кул87. Кулагина О.С. Об автоматическом синтаксическом анализе русских текстов. //Препринт ИПМ им. М.В. Келдыша, АН СССР, № 205,1987 г.

120. Лев65а. Левенштейн В.И., Двоичные коды с исправлением выпадений, вставок и замещений символов, //Докл. АН СССР, 163, 4,1965, 845-848.

121. Лев65Ь. В.И.Левенштейн, Двоичные коды с исправлением выпадений и вставок символа \,//Пробл. перед, информ., 1,1,1965,12-25.

122. Мер05. Мерков А.Б. Основные методы, применяемые для распознавания рукописного текста. http://fornit2005 .narod.ru/papers/methods.ps

123. МерОб. Мерков А.Б.О статистическом обучении.http://www.recognition.mccme.ru/pub/RecognitionLab.html/slt.pdf

124. Пен04. Пентус А. Е., Пентус М. Р. Теория формальных языков: Учебное пособие. ИМ.: Изд-во ЦП И при механико-математическом ф-те МГУ, 2004

125. ПМШ04. Постников В.В. Марченко А.Е. Шоломов Д.Л. Разбор структурированного документа в модели с нечеткой логикой ИСб. тр. ИСА РАН "Документооборот. Концепции и инструментарий.", Москва, Едиториал УРСС, 2004, стр. 71-82.

126. Пос01. Постников В.В., Автоматическая идентификация и распознавание структурированных документов ПДисс. На соискание уч. степ. Канд. Технич. наук, Москва, 2001.

127. Пос98. Постников В.В., Разработка методов наложения формы на графическое изображение документа. ИВ сб. «Интеллектуальные технологии ввода и обработки информации», Москва, 1998

128. Пос99а. Постников В.В., Формальный подход к задаче идентификации графическихобразов структурированных документов, ИВ сб. «Развитие безбумажных технологий в организационных системах», Москва, 1999

129. СКБ99. Славин О.А., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов. И В сб. "Развитие безбумажных технологий в организациях", 1999, с. 290-311

130. Уос92. Ф.Уоссермен, "Нейрокомпьютерная техника.", ИМ.: Мир, 1992

131. ФрОЗ. Дж. Фридл. Регулярные выражения. IIИздательство Питер, 2003 г., 464 стр.

132. Хай05. Хайкин С. Нейронные сети, полный курс, //Изд. "Вильяме, 2005

133. Хол1. А.Б. Холоденко. О построении статистических языковых моделей для систем распознавания русской речи //Журнал Интеллектуальные системы

134. Чер98. Черноусько Ф.Л. Динамическое программирование ИСОЖ, 1998, No 2, с. 139144.

135. Шенбб. Шеннон К. Работы по теории информации. ИМ.: Изд-во иностранной литературы, 1966.

136. Шол02. Шоломов Д.Л. Интерпретация нечетко распознанных текстовых конструкций. И Сборник трудов 6-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии». Великий Новгород, 2002.

137. Шол07а. Шоломов Д.Л. Коррекция распознанного текста с использованием методов классификации. И Сб. трудов ИСА РАН, 2007, Том 17, стр. 352-366

138. Шол07Ь. Шоломов Д.Л. Постников В.В. Никольский Н.Н. Рынок систем обработки деловых документов. Перспективы и направления развития. И Сб. трудов ИСА РАН, 2007, Том 17, стр. 181-191.

139. Шол04. Шоломов Д.Л. Синтаксический подход к пост-обработке нечетко распознанного текста. НСб. трудов ИСА РАН "Документооборот. Концепции и инструментарий. ", Москва, Едиториал УРСС, 2004, стр. 193-207