Разработка методов наложения формы на графическое изображение документа

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

Введение.

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

Рисунок 1. Пример графического образа распознаваемого бланка и соответствующего ему описания формы.

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

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

Основные предположения.

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

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

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

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

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

Модель фиксированности структуры документа.

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

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

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

Рисунок 2. На изображении выделена часть элементов - линии разграфки. С помощью алгоритма наложения они сопоставляются с линиями, присутствующими в описании формы бланка.

Шаг 1. Строится матрица X[i, j], элементами которой являются численные оценки соответствия i-го реального элемента j-му идеальному.

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

Функция оценки.

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

X[i, j] = Min( F1, F2, F3 )

где

F1 = Min ( len(i)/len(j), len(j)/len(i) ) - мягкий учет соотношения длин реальной (i) и идеальной линии (j);

F2 = (Xi, Xj)/|Xi|*|Xj|,

где X = <x1,x2,x3,x4> - суммы длин сонаправленных линий, лежащих относительно оцениваемой пары слева (1), сверху (2), справа (3) и снизу (4) в описании формы (Xi) и реальном документе (Xj);

F3 = (Yi, Yj)/|Yi|*|Yj|,

где Y = <y1,y2,y3,y4> - суммы длин перпендикулярно направленных линий слева, сверху, справа и снизу в описании формы (Yi) и реальном документе (Yj);

Для форм с фиксированной геометрией можно положить

Xf[i, j] = X[i, j] если X[i, j] > C, иначе 0.

Шаг 2. На матрице X решается задача об оптимальном назначении. Подробный алгоритм решения задачи можно найти, например, в [1]. В результате получается набор пар идеальный-реальный элемент, оптимизирующий в сумме функцию оценки. Пары с оценкой 0 выбрасываются.

Полученные пары будем называть назначениями.

Шаг 3. Для каждой пары назначений A1, А2

< < идеальный1-реальный1 >, <идеальный2-реальный2>>

принимается решение о противоречивости или непротиворечивости (далее, согласованность) назначения А1 при условии назначения А2 (и, наоборот). Для форм с фиксированной геометрией признаком противоречивости может являться критическое отклонение во взаимном расположении, для форм с нефиксированной геометрией проверяется выполнение на элементах <реальный1-реальный2> геометрических связей, постулированных про пару <идеальный1-идеальный2> .

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

В результате получаем согласованное (взаимно непротиворечивое) множество назначений. Если все поля ввода однозначно наложены или ограничены - задача решена, алгоритм завершает работу.

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

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

Шаг 5. Производится коррекция матрицы оценок X: для не наложенных идеальных элементов пересчитываются их ограничения - на основе их связей с уже наложенными,- и для тех пар, у которых расположение реального кандидата противоречит ограничению для идеального устанавливается оценка 0. Далее выполняется Шаг 2.

Реализация.

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

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

Литература.

[1] М. Свами, К. Тхуласираман. "Графы, сети и алгоритмы", Москва, "Мир", 1984 г.