Построение модели структурированных документов на основе машинного обучения

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Построение модели структурированных документов на основе машинного обучения

С.В. Голубев

Аннотация

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

Введение

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

Преобразование информации с бумажных носителей в электронную форму осуществляется системами оптического распознавания символов. Однако часто посимвольное преобразование является недостаточным, и для перевода информации в электронное представление требуется распознавание логической структуры документа. В настоящее время среди методов распознавания структурированных документов наибольшей гибкостью и точностью обладают методы, основанные на структурном распознавании образов [Farrow et al., 1995], [Hirayama, 1996]. В этих методах используется та или иная модель структуры документа. При распознавании модель сопоставляется и изображением документа, в результате чего определяется локализация его реквизитов. Наибольшее распространение получила графовая модель, в которой текстовые блоки и разделительные линии образуют узлы графа, а дугам графа соответствуют отношения между ними. В этом случае проблема анализа геометрической, а значит и логической структуры, сводится к задаче сравнения двух графов - графа описания документа и графа, полученного по изображению [Yuan, 1995].

К этой же группе методов относится технология распознавания структурированных документов ABBYY FlexiLayout. В этой системе используется специализированная модель документа (структурное описание), позволяющая достичь большей гибкости по сравнению с простыми графовыми моделями [Зуев, 1999]. Модель состоит из описаний структурных элементов, соответствующих реквизитам документа. Для каждого элемента задаются его характеристики, позволяющее локализовать структурный элемент на изображении. Т.о. в отличие от графовых моделей, где для построения графа изображения требуется априорное выделение структурных элементов, в системе FlexiLayout выделение структурных элементов происходит в процессе распознавания на основе описания документа и учитывает особенности конкретного типа документа. Помимо внутренних характеристик структурных элементов в описании могут быть заданы различные отношения между элементами.

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

1. Система распознавания форм на основе машинного обучения

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

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

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

В задаче обучения на примерах можно выделить два основных этапа: этап построения модели на основе примеров и этап использования полученной модели для решения поставленной задачи (распознавания, предсказания, классификации и т.п.). В данном случае в качестве модуля распознавания применяется система ABBYY FlexiLayout. Т.о. моделью является структурное описание документа, принятое в этой системе (подробнее о структурных описаниях можно прочесть в работе [Зуев, 1999]). Однако на этапе обучения работать непосредственно с моделью FlexiLayout не очень удобно, поэтому желательно использовать более простую модель документа. В качестве такой модели используется граф документа с метрическими отношениями между элементами. После построения графовой модели на основе примеров (обобщения) граф преобразуется в структурное описание FlexiLayout, при этом сохраняются метрические и бинарные отношения между структурными элементами, заданные в графе в виде ребер. Полученное описание FlexiLayout затем используется для распознавания документов. Далее рассмотрим более подробно промежуточную модель документа и метод ее обобщения.

2. Модель документа

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

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

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

Буква > Слово > Строка > Фрагмент текста

Фрагмент разделительной линии > Разделительная линия

Фрагмент рисунка > Рисунок.

В качестве промежуточного представления структуры документа используется графовая модель. Это позволит опираться на уже известные методы работы с данными, представленными графами [Cook et al., 2006], [Kuramochi et al., 2002], [Yan et al., 2002]. Модель документа при этом должна позволять описывать как конкретное изображение (экземпляр документа) так и его обобщенную структуру. В первом случае будем говорить о графе документа, а во втором - о шаблонном графе или обобщенном графе.

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

DG = (V, E, L_V, L_E, f_V, f_E),

где V - множество вершин,

E - множество ребер,

L_V, L_E - множества меток вершин и ребер соответственно,

f_V, f_E - отображения, сопоставляющие вершины и ребра с метками.

Вершины графа имеют метки вида

l_V = (id, description),

где id - идентификатор объекта или структурного элемента, определяющий его логическую роль в документе, который может принимать значения из множества {R, S, F1, F2, …, FN},

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

R - метка текстового объекта.

S - метка разделительной линии.

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

Object - множество, состоящее из одного графического объекта.

Phrase Set - множество фраз из одного или нескольких слов. Описание имеет вид: (phrase₁, …, phrase_N,), где phrase_i - символьные строки.

Alphabetic String - множество строк, состоящих из символов заданного алфавита или нескольких алфавитов: (alphabet₁, …, alphabet_N), где alphabet_i=({a₁,a₂…,a_N},P), a_i - символы, P- максимальная доля символов алфавита в строке.

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

Separator - множество разделительных линий с определенными размерами, описание при этом имеет вид (MaxSpace, MaxOrthogonalSpace, Length), где MaxSpace - допустимый пробел между фрагментами линий в направлении вдоль сепаратора, MaxOrthogonalSpace - допустимый пробел между фрагментами в направлении поперек сепаратора, Length - длина, заданная в виде интервала.

Ребра графа имеют метки вида: l_E = (vertDistamce, horDistance), где vertDistance, horDistance - расстояние между прямоугольниками по вертикали и горизонтали в виде интервала. Расстояние может быть как положительным, так и отрицательным, и зависит от порядка вершин, т.е. ребра являются направленными.

3. Обобщение модели документа

Введем следующее определение. Будем считать, что граф документа G_D описывается шаблонным графом G_T, если существует отображение:

X:V(G_T) > V'(G_D),

где такое, что для любых вершин v и u и их образов v' и u' выполняются условия:

1. id(v) = id(v'), т.е. идентификаторы вершин совпадают.

2. Объект, заданный вершиной v', входит в множество объектов, заданное описанием description метки вершины v.

3. Метка l ребра e = (v, u) является обобщением метки l' ребра e' = (v', u'), в том смысле, что интервалы distance метки l входят в интервалы distance метки l'.

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

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

Y:V'(G_T) > V'(G_D),

где , , такое что идентификаторы вершин-образов и вершин-прообразов совпадали. После этого метки вершин из множества V'(G_T) должны быть обобщены с метками вершин из множества V'(G_D) т.о. чтобы заданные метками на вершинах множества графических объектов включали новые объекты, описанные метками на вершинах V'(G_D). Аналогично, интервалы расстояний на ребрах графа G_T должны быть обобщены с интервалами на образах этих ребер из графа G_D.

Очевидно, что может быть построено большое число таких отображений и соответственно шаблонных графов. Необходимо ввести критерий, позволяющий выбирать наиболее подходящий граф. Следует отметить, что рассмотренное отображение вершин представляет собой путь редактирования (Edit Path) [Cook et al., 2006]. В общем случае для оценки пути редактирования может быть применена вероятностная оценка [Neuhaus et al., 2004], однако в данном случае более целесообразным является использование специальной эмпирической оценки, более соответствующей предметной области.

Введем оценку качества отображения вершин и соответствующего обновленного шаблонного графа G_T':

Q = (?Q_V(v_i>u_j))*Q_U(V(G_T)\V'(G_T))*Q_U(V(G_D)\V'(G_D)),

где Q_V - оценка пары вершин из отображения Y, Q_U - оценка вершин из множеств V(G_T)\ V'(G_T) и V(G_D)\ V'(G_D), т.е оставшихся без образа или прообраза. Поскольку при отображении вершин идентификаторы вершин сохраняются, то соответствие между полями документа задано однозначно, поэтому в оценке шаблонного графа следует учитывать только вершины с метками текстовых объектов и разделительных линий.

Q_V(v>u) = Q_V(v') = maxQ_E(e_i) - б*(maxQ_E(e_i) - ?Q_E(e_i)/N_F),

где Q_E(e_i) - оценка i-го ребра, выходящего из вершины v' графа G_T', полученной в результате отображения вершины v графа на вершину u графа G_D; ; N_F - число полей в данном типе документа; б - эмпирический коэффициент, вводящий зависимость оценки не только от оценки наилучшего ребра, но и от средней оценки.

Оценка Q_U зависит от числа вершин в соответствующих множествах и имеет вид: Q_U(V(G)\V'(G)) = U^|V(G)\V'^(G)|, т.е. за каждую неотображенную вершину назначается фиксированный штраф U.

Оценка ребра имеет вид:

Q_E(e_i) =max( 0; ),

где Дx = Width(XDistance)/W, Width(XDistance) - ширина интервала XDistance метки ребра e_i, W - характерная ширина интервала порядка размера страницы; аналогично для Дy. Данная эмпирическая оценка выбрана из следующих соображений. Во-первых, изолинии функции должны быть вогнутыми, т.е. оценка ребра с интервалами шириной (для примера) Дx = 1, Дy = 0 должна быть выше, чем для ребра с интервалами шириной Дx = 1/2, Дy = 1/2. Во-вторых, оценка должна быть близка к 1 для ребра, полученного в результате правильного сопоставления объектов (Дx и Дy при этом существенно меньше 1), и заметно снижаться при приближении значений Дx и Дy к 1. В данном случае изолиниями являются гиперболы вида , . График функции оценки ребра в области представляет собой поверхность, полученную «скольжением» гиперболыпо параболе .

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

Будем последовательно выбирать пары для вершин первого графа, используя дерево перебора. Узел дерева соответствует решению отобразить вершину v_i на вершину u_j, либо оставить вершину v_i без образа.

Для каждого нетерминального узла и соответственно пути в дереве введем частичную оценку Q_P, которая, в отличие от Q не учитывает нерассмотренные вершины первого графа и не имеющие прообраза вершины второго. Т.е. будем учитывать в Q_U(V(G_T)\V'(G_T)) только рассмотренные вершины шаблонного графа, а Q_U(V(G_D)\V'(G_D)) опустим.

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

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

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

Рис. 1. Черный график - полужесткая форма, серый график - гибкая форма.

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

граф печатный документ

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

1. Зуев К.А. Система идентификации структуры печатных документов: дис. канд. тех. наук, М.:, МГУЛ, 1999.

2. Cook D., Holder L. Mining Graph Data, Wiley-Interscience, 2006.

3. Farrow G.S.D. et al, Model Matching in Intelligent Document Understanding, Proc. of ICDAR'95, 1995.

4. Hirayama Y., Analyzing Form Images by Using Line-Shared-Adjacent Cell Relations, Proc. of IAPR'96, 1996.

5. Kuramochi M., Karypis G. An efficient algorithm for discovering frequent subgraphs, Tech. Rep. 02-026 Minneapolis, University of Minnesota, 2002.

6. Neuhaus M. and Bunke H. A probabilistic approach to learning costs for graph edit distance. Proceedings 17th International Conference on Pattern Recognition, 2004, Vol. 3.

7. Yan X., Han J. gSpan: Graph-Based Substructure Pattern Mining, Proc. IEEE International Conference on Data Mining (ICDM'02), Los Alamitos, 2002.

8. Yuan J., Tang Y.Y., Suen C.Y. Four Directional Adjacency Graphs (FDAG) and Their Application in Locating Fields in Forms, Proc. of ICDAR'95, 1995.

Размещено на Allbest.ru