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

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

,Г8 ОД -" Б ИЮИ 1999

ЗУЕВ Константин Алексеевич

и

Система идентификации структуры печатных документов

05.13.14 - системы обработки информации и управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва -1999

Работа выполнена на кафедре физики Московского государственного университета леса и в компании ABBYY Software

Научный руководитель: заслуженный деятель науки РФ,

доктор технических наук, профессор Харченко В. Н.

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

доцент Ретинская И.В. кандидат технических наук, с.н.с. Мазо Б.Л.

Ведущая организация: Рос НИИ информационных технологий и

систем автоматизации проектирования.

Защита состоится 14 мая 1999 г. в 1300 часов на заседании диссертационного совета Д 053.31.06 при Московском государственном университете леса по адресу: Мытшци-1, ул. Институтская, д. 1, МГУЛ, ауд. 313.

С диссертацией можно ознакомится в библиотеке МГУЛ.

Автореферат разослан «_»_1999 г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент Дашков A.A.

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

Актуальность темы ______ - ______ ______________________ - -

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

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

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

Цель диссертационной работы

Целью диссертационной работы является разработка системы идентификации

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

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

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

• разработать алгоритм распознавания образа;

• создать средства, позволяющие описывать структуру образа.

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

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

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

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

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

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

2. Разработан метод структурного распознавания образов, не связанный с формой представления распознаваемых данных, свойствами структурных элементов.

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

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

Практическая значимость работы

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

• формы платежного поручения;

• справки о доходах физического лица.

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

• более чем в 30 государственных и коммерческих банках, в том числе в 9 отделениях Сбербанка;

• в налоговых службах РФ.

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

Достоверность

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

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

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на 4-ой Международной конференции по анализу и распознаванию документов ICDAR (Forth International Conference on Document Analysis and Recognition, Ulm, Germany, 1997 г.), Международной научной конференции "Перспективные технологии автоматизации" (г. Вологда, 1998 г.), Отраслевой конференции по документообороту DOCFLOW (г. Москва 1998 г.).

На защиту выносятся

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

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

3. Язык структурных описаний как средство описания образа для его последующего распознавания предложенным методом структурного распознавания.

4. Методика инверсии отношений, позволяющая априорно вычислить дополнительные ограничения на выделяемые структурные элементы.

Публикации

По теме диссертации опубликовано 8 статей и докладов на конференциях. Структура и объем диссертации

Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы и 4 приложений. Общий объем 153 стр., в том числе 137 стр. основного текста, 20 рисунков, 5 таблиц, 93 наименования списка литературы.

Основное содержание работы

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

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

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

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

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

• существуют ограничения на абсолютное и относительное расположение структурных элементов;

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

• структурные элементы могут быть необязательными или пропадать в процессе сканирования.

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

Другой подход ориентируется на документы, обладающие табличной структурой. Он позволяет анализировать широкий класс обычных документов, в частности выделять реквизиты научных статей. Системы такого типа разрабатываются, например, в институте ГКЯ1А (Франция), в исследовательском центре CEDAR (Center of Excellence in Document Analysis and Recognition) университета Ныо-Йорка (США).

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

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

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

• декларативное описание анализируемого вида документов;

• модель структуры документа и предметные алгоритмы распознавания структурных элементов;

• метод структурного распознавания образов, сопоставляющий описание и

изображение.

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

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

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

1. Абстрагированное представление структурных элементов, в частности параметрическое.

2. Иерархичность и вариантность описания образа.

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

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

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

С учетом данных требований разработана общая структура модели, в которой выделены три основные сущности - описание, гипотеза и генератор: <Д Н, g>

Описание И является декларативной компонентой, описывающей структуру распознаваемого образа. Описание включает как терминальные, т.е. примитивные структурные элементы, для которых указываются необходимые параметры распознавания: Т> = Р; х ... х Рм, так и нетерминальные, например составные элементы, для которых указаны их составляющие подэлементы и отношения между

ними: 2)с = Т>1 х ... х Дм х Д. В частности, весь образ является, как правило, составным элементом верхнего уровня.

Гипотеза Н является вариантом распознавания структурного элемента. Гипотеза обладает множеством атрибутов, достаточным для идентификации варианта распознавания. Гипотезе соответствует также число, определяющее степень достоверности данного варианта распознавания: Н= А]Х ... х Ам х б-

Генератор g является абстракцией алгоритма распознавания соответствующего типа структурных элементов. Пользуясь описанием, т.е. параметрами распознавания, и исходными данными, т.е. изображением в том или ином представлении, генератор выдвигает гипотезы о расположении структурного элемента (рис. iy.g-.Dx Н

Рисунок 1: Общая структура модели

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

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

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

I Исходные | данные

Гипотеза

и

тем универсального типа элементов - составного элемента. Структура модели,

конкретизированная для составного элемента, представлена на рисунке 2.

Рисунок 2: Структура модели для составного элемента

Гипотеза, соответствующая составному элементу, в качестве своих атрибутов имеет гипотезы своих подэлементов: Ис~ И} х ••■ х Нм х (). Генератор составного элемеша на основании выдвинутых гипотез подэлементов формирует ишотезу составного элемента: Ос х (/// х ... х Ни) Не- При этом образуется так называемое дерево перебора, узлы которого соответствуют гипотезам подэлементов, а каждый путь от корня к листьям - одной из гипотез распознаваемого составного элемента. Задача состоит в том, чтобы построить пути с лучшей оценкой качества, что осуществляется с помощью стандартного алгоритма А*, позволяющего управлять перебором.

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

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

Представлена грамматика основных конструкций языка структурных описаний в нотаций Бэкуса-Науэра, которые были разработаны с учетом возможности синтаксического анализа на основе ЬЦ1) разбора:

<описание образа> ::= <описание составного элемента> | Сописание ИЛИ элемента>

<описание составного элемента> ::=

составной_элемент <имя элемекта>

{<инициализация параметра распознавания;»;}* элементы:

(<описание подэлемента>)*

[

отношения:

{Слогическое выражение>;}*

]

конец_составного_элемешга

«Сописание ИЛИ элемента> ::=

или_элемент <имя элемента>

{Синициализация параметра распознаваниям}* варианты:

{Сописание подэлемента>}*

[

отношения:

{<логическое выражением}*

]

конец_или_элемента

Ссплсание подэлемен-ха> ::= . _. _ . . . .. .

<списакяе терминального элемента;» I <описание составного элемента>

: <описаиие ИЛИ элемента>

<олксакие терминального злемента> : <г;-:г. элемекта> <икл элемента>

{<инициализация параметра распознавания:»; } *

отношения :

«

{Логическое зыражение>;}*

]

конец_злемента

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

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

• декларативности и простоты описания.

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

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

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

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

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

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

С^ ~ р(ф), где I - структурный элемент, а I - изображение.

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

На основании вероятностной интерпретации оценки достоверности имеем:

где р(1,|1) - вероятность ¡-го подэлемента составного элемента N.

р^Иь-.-Лп) - условная вероятность того, что данный набор подэлементов образует составной элемент N.

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

д-оись..^

где ~ р(^|1) - оценка достоверности ¡-го подэлемента составного элемента N

(<!к~ рСЬ^ь...,^) - оценка отношений

Величина р(Ы|11,...,1п) соответствует отношениям 0г<, которые ограничивают подэлементы в составном элементе. Таким образом, отношения должны моделировать функцию условной плотности вероятности р(К|1ь...,1п). Для решения

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

операция 'л' по формуле: А л В а 4 Ь; операция V по формуле: ЛуВ а + Ь- а* Ь; операция по формуле: пА-) 1 - а.

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

Рисунок 3: Моделирование функции условной плотности вероятности примитивным предикатом

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

Методика адаптации включает в себя следующие действия:

• определение типов используемых сгру ктурных элементов;

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

• создание алгоритмов распознавания структурных элементов;

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

• определение специализированных отношений.

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

• горизонтальная или вертикальная разделительная линия;

• цепочка символов из заданного множества;

• ключевое слово;

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

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

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

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

Для цепочки символов:

• основной набор символов, например - «0123456789»;

• символы, которые графически могут походить на заданные, например -«ОЗЧТ» - такие символы допускаются с дополнительным штрафом при оценке гипотезы;

• максимальное расстояние между символами.

Для ключевого слова:

• варианты ключевого слова, например - «Сумма» или «почтой]'телеграфом|электронный»;

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

Для фразы:

• «пословное» регу^шрное выражение, для задания текста фразы, например -«Банк плателылика!плат|пл-щика»;

• допустимое количество ошибок на слово относительно его длины - каждое слово фразы сравнивается нечетко;

• максимальное расстояние между словами;

• минимальное и максимальное количество строк во фразе;

• среднее расстояние между строками.

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

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

Зысе: Элемент, Диапазон

Ниже: Элемент, Диапазон

Левее: Элемент, Диапазон

Правее: Элемент, Диапазон

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

относительно других элементов описания. Фрагмент описания формы платежного нору чення представлен ниже:

Фраза Банк_плателыцика

Текст: "ЕАКК ПЛАТ2ЛЬ1Д/КА! ЛЛ-СИКА" ; Наказание_за_пропуск: 0; Необязателен: 0.94, 0.94; отношения:

Выше: Разделитель_банк_плат;

Ниже: Разделитель_плат_получ - 2 * см;

Выше : Разделитель_плат_получ.Bottom + высота_строки / 2;

Левее: Большой_верт_разделитель; хонец_составного_элемента

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

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

Lt[R(ti,... ,t„, t)] - локализация отношения R(ti,... ,tn, t)

R(ti,...,tr., t) - отношения для текущего элемента t с выделенными ранее

элементами tj.....tn

Lt[R(ti.....t„,t)] = {t|R(tj.....tn, t)>0 >

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

LiAft) л Bffll = { 11 (A(t) л B(t)) > 0 } = { 11 A(t) > 0 } a { 11 B(t) > 0 } = = ЫАЩ1дШШ]

ШЬсЖШ = {11 (A(t) v B(t)) > 0 } = { 11 A(t) > 0 } V { 11 B(t) > 0 } =

= UA(X)] V LiBft)]

ЬЬАЩ] = {11 (-,A(t)) > 0 } = -,{ 11 A(t) > 0 } =

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

Таким образом, методика инверсии отношений при компиляции описания образа заключается в следующем:

• вводится тип данных - локализация;

• компилируется исходный текст отношений;

• при этом логические операции заменяются на операции с локализацией;

• примитивные предикаты заменяются па соответствующие функции, вычисляющие отношения.

В приложении представлена полная грамматика языка структурных описаний.

полный список параметров, атрибутов и отношений, фрагменты описаний формы

платежного поручения и справки о доходах физического лица в ГНИ.

Выводы

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

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

связывающих структурные элементы образа.

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

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

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

Публикации:

1. Зуев К.Д.. Бинаризация изображений печатных документов /У Компьютерная хроника, 1996 г., Лга2, стр. 95-99.

2. Зуев К.А., Технология анализа документа // Компьютерная хроника, 1996 г., №3, стр. 53-59.

3. Zuyev К.A., Table Image Segmentation // Proceedings of the Forth International Conference on Document Analysis and Recognition (ICDAR), 1997, Ulm, Germany, Vol. II, pp 705-708.

4. Зуев K.A., Система распознавания штрих-кода // Тезисы VII Международной научно-технической конференции «Оптические, радиоволновые, тепловые методы и средства контроля природной среды, материалов и промышленных изделий», 1997 г., г. Череповец, стр. 146.

5. Зуев К.А., Язык структурных описаний // Международная научная конференция "Перспективные технологии автоматизации", 1998 г., г. Вологда.

6. Зуев К.А., Метод выделения полей при распознавании форм // Труды МГУЛ, 1999 г., вып. 302.

7. Зуев К.А., Язык структурных описаний для систем распознавания образов // Труды МГУЛ, 1999 г., вып. 302.

8. Zuyev К.А., Structural Approach to Form Image Understanding // to be published in Proceedings of the Fifth International Conference on Document Analysis and Recognition (ICDAR) 1999.

/' • ,/ , п п м / , /

/65 6-X

МОСКОВСКИЙ ГОСУДАРСТВЕНЫИ УНИВЕРСИТЕТ ЛЕСА

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

ЗУЕВ Константин Алексеевич

Система идентификации структуры печатных документов

Специальность 05.13.14 - систеьш обработки информации и управления

ДИССЕРТАЦИЯ

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

Научный руководитель: заслуженный деятель науки РФ,

доктор технических наук, профессор Харченко В. Н.

Москва - 1999

ОГЛАВЛЕНИЕ

Введение ................................................. 4

Глава 1. Проблемы идентификации логической структуры печатных документов ..................................... 16

1.1 Анализ основных свойств логической структуры документа............................................16

1.2 Особенности графических характеристик печатных форм ......................................................22

1.3 Методы, применяющиеся при идентификации логической структуры печатных документов........................2 8

Глава 2. Метод структурного распознавания образов....... 4 4

2.1 Требования к методу структурного распознавания образов..............................................44

2.2 Общая структура модели...........................52

2.3 Программная реализация модели...................61

2.4 Реализация модели и алгоритма распознавания образа .....................................................65

Глава 3. Разработка языка структурных описаний .......... 71

3.1 Требования к средствам описания структуры образа 71

3.2 Язык структурных описаний........................75

3.3 Средства обработки описания......................87

Глава 4. Вычисление оценки достоверности распознавания . . 91

4.1 Вероятностная интерпретация......................91

4.2 Вычисление оценки составного элемента............92

4.3 Применение нечеткой логики.......................95

Глава 5. Система идентификации логической структуры изображения печатных документов .............................. 100

5.1 Методика- адаптации метода структурного распознавания образов.......................................100

5.2 Система идентификации логической структуры изображений печатных документов.....................102

5.3 Методика вычисления локализации.................117

Заключение.............................................125

Список литературы.........................................128

—

Приложение 1: Примеры изображений печатных форм с нефиксированным расположением полей........................... 138

Приложение 2: Грамматика языка структурных описаний.... 142 Приложение 3: Список атрибутов, параметров, функций и отношений, использующихся при описании печатных документов. 147 Приложение 4: Пример описания формы на языке структурных описаний...............................................150

Введение

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

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

быть в конце концов подтвержден бумажным платежным поручением.

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

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

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

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

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

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

Цель диссертационной работы

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

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

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

• разработать алгоритм распознавания образа;

• создать средства, позволяющие описывать структуру образа.

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

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

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

В диссертации использовались методы теории оптимизации,

элементы теории формальных языков, теории распознавания

образов, теории нечетких множеств и нечеткой логики.

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

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

2.Разработан метод структурного распознавания образов, не связанный с формой представления распознаваемых данных, свойствами структурных элементов.

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

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

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

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

8

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

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

Практическая значимость работы

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

• формы платежного поручения;

• справки о доходах физического лица.

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

• более чем в 3 0 государственных и .коммерческих банках, в том числе в 9 отделениях Сбербанка;

• в федеральном департаменте налоговой полиции.

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

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

Достоверность

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

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на 4-ой Международной конференции по анализу и распознаванию документов ICDAR (Forth International Conference on Document Analysis and Recognition, Ulm, Germany, 1997 г.), 7-ой Международной научно-технической конференции "Оптические, радиоволновые тепловые методы и средства контроля природной среды, материалов и промышленных изделий" (г. Череповец, 1997 г.), Международной электронной научной конференции "Перспективные технологии автоматизации" (г. Вологда, 1998 г.), Отраслевой конференции по документообороту DOCFLOW (г. Москва 1998 г.). .

Публикации

По теме диссертации опубликовано 8 статей и публикации в материалах конференций.

Структура и объем диссертации

Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы и 4 приложений. Общий объем 153 стр., в том числе 137 стр. основного текста, 20 рисунков, 5 таблиц, 93 наименования списка литературы.

Основное содержание работы

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

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

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

структурных элементов и сформулированы основные положения о геометрической структуре документа в терминах структурных элементов.

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

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

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

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

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

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

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

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

базовый язык структурных описаний. Описаны алгоритмы распознавания структурных элементов.

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