Формальный подход к задаче идентификации графических образов структурированных документов - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Методика «Рисование по точкам» 1 34.78kb.
Методика "Рисование по точкам" 1 31.54kb.
Об одной задаче идентификации сложных систем 1 53.54kb.
О. М. Брик Т. н. "формальный метод" 1 30.74kb.
Представление структурированных информационных объектов в виде электронных... 1 73.32kb.
Формальный подход м джей роуз 7 1099.68kb.
Мк-26-11 Индивидуальный выбор оптимального количества особенностей... 1 173.15kb.
Галерея образов помещиков 1 129.95kb.
Определение достоверности результатов распознавания символа в системе... 1 175.74kb.
Исследовательская работа «Сопряжения в Архитектуре» 1 102.67kb.
Idpoly- модель полинома "Черного ящика" 1 53.06kb.
Ноудпо цпкиА 3 585.58kb.
Направления изучения представлений о справедливости 1 202.17kb.

Формальный подход к задаче идентификации графических образов структурированных документов - страница №1/1

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

В. В. Постников



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

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

  • идентифицировать тип документа

  • выделить поля ввода информации

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

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

  • нормализовать полученное значение – например, привести дату к необходимому формату

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

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






Два графических образа почтовой карточки/конверта.
В зависимости от постановки прикладной задачи, система автоматизированной обработки форм должна уметь либо объединить подобные экземпляры в один класс документа, либо различить, поставить в соответствие каждому заранее определенную модель документа и произвести обработку в соответствии с идентифицированным типом. Для этого система должна произвести анализ графического образа, выделить фрагменты графического образа, которые могут быть интерпретированы как элементы документа, сопоставить конфигурацию из полученных объектов с моделью того или иного документа и проанализировав результат такого сопоставления принять решение о типе документа и дальнейшей обработке его графического образа.
В литературе (1-18) содержится широкий спектр методов и подходов, позволяющих решать перечисленные задачи в разных вариантах постановки. Общей чертой, просматривающейся в большинстве из приведенных в публикациях методов является двухуровневая организация схем обработки – изображение сегментируется на фрагменты текста, разграфки, и другие типы составляющих, и далее производится попытка интерпретации полученного набора как реализации той или иной стандартизованной формы.
В настоящей работе представлен вариант формализации понятий “модель документа”, “тип документа”, “элемент документа”, “элемент графического образа”, “вариант фрагментации графического образа” и других понятий, необходимых для постановки задач, связанных с идентификацией типа документа и выделением полей ввода.
Формализация
Пусть имеется множество объектов О = {о}, множество типов объектов Т ={t} и фиксирована функция типизации объектовo: ОT, всюду определенная на О. Объекты o1 и o2 для которых выполняется o(o1) = o(o2) будем называть однотипными.
Пусть E ={e} – множество элементов, из которых могут составляться объекты. Множество всех подмножеств Е обозначим B(E). Функция состава объекта s:ОB(E) для каждого из объектов фиксирует множество составляющих его элементов. Заметим, что согласно такому определению, в составе объекта нет одинаковых элементов.
Зафиксируем множество NA которое в дальнейшем будем называть множеством имен атрибутов. Зафиксируем конечный набор множеств D={D,..,Dn}; множества Di будем называть доменами. Введем отображение Dom: NAD. Традиционно, пара , где АNA называется атрибутом с именем А и областью значений Di = Dom A.
Пусть фиксировано некоторое конечное множество атрибутов. Множество типов элементов  ={} – определим как множество конечных слов в алфавите атрибутов. Будем считать, что фиксирована функция типизации элементов

е: Е, всюду определенная на E. Элементы e1 и е2 для которых выполняется e(e1) = e(e2) будем называть однотипными.


Зафиксируем множество NE , которое в дальнейшем будем называть множеством имен элементов. Обозначим как nе:ENE функцию идентификации элементов, которая сопоставляет элементу объекта его имя.

Элементы, для которых функция ne определена будем называть идентифицированными. Объекты e1 и e2, для которых ne(e1)= ne(e2) будем называть одноименными.


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

  1. e1E, e2E: ne(e1)= ne(e2)  e(e1) = e(e2) - одноименными могут быть только однотипные элементы

  2. oO e1s(o), e2s(o): ne(e1)  ne(e2) - в рамках одного объекта не может быть одноименных элементов.

Если все элементы объекта o корректно идентифицированы, имя элемента однозначно определяет элемент. Функцию разыменования, обратную функции идентификации будем обозначать : O x NE  E {}. Будем считать что значение  функция принимает в тех и только тех случаях, когда для объекта o нет элемента с именем n. В противном случае будем говорить, что для объекта o для имени n функция разыменования указана или элемент с именем n в объекте o присутствует.
Пусть Ot - множество однотипных объектов, все элементы которых корректно идентифицированы. Пусть х = 1, n2,..,nk> - кортеж из набора имен элементов. Пусть для объекта о из Ot функция разыменования указана для каждого из имен – элементов кортежа. Тогда можно определить y(o, x) = 1, e2,..,ek> = <(o,n1),(o,n2),...,(o,nk)> - кортеж из элементов o с соответствующими именами. Пусть p(o,x) = p(y(o,x)) – некоторое высказывание над атрибутами корректно идентифицированных элементов объекта o. Построим на основе p(o,x) высказывания P0 и P1 над объектами из Ot, параметризованное кортежем имен элементов, определенное как p(o,x) когда все элементы с именми из х присутствуют в o, и определенное как 0 или 1 для P0 и P1 соответственно – если какие-либо из элементов с именами из х в объекте отсутствуют:

P0(x) = oOt [(o,x1)  )&((o,x2)  )&...&((o,xk)  )] & p(o,x)

P1(x) = oOt [(o,x1)  )&((o,x2)  )&...&((o,xk)  )]  p(o,x)

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


Пусть Ot - множество однотипных объектов, все элементы которых корректно идентифицированы функцией идентификации ne. Пусть Х  NE - множество имен элементов объектов из Ot. Пусть P - множество ограничений, построенных на кортежах, параметризованных именами элементов из X и выполняющихся (постулированных) на объектах из Ot. Определим модель объекта типа t как mt = t, ne, P>. Про объекты будем говорить что они соответствуют модели (при заданном способе идентификации).
Пусть задана модель mt = t, ne, P>. Переопределим функцию идентификации элементов, произведя произвольную перестановку имен в рамках однотипных элементов. Такую операцию назовем переименованием. Если существует объект из Ot для которого существует переименование, при котором все ограничения из P продолжают выполняться, модель mt будем называть нестрогой. В противном случае, для строгой модели функция идентификации реализует единственно возможную комбинацию имен элементов, удовлетворяющую P.
Пусть фиксировано множество элементов Ео на котором требуется выделить подмножество, составляющее объект o и задана функция вытеснения :ЕоB(Ео), которая вводит ограничение на функцию состава объекта следующим образом: если элемент е включается в объект, любой из элементов множества (e) не может быть включен в o. Множество объектов, которые могут быть сконструированы при заданных ограничениях будем называть вариантами конструирования объекта. Приведем пример: пусть одним из типов элементов являются отрезки на плоскости, другим – точки («вершины»), которые могут являться началом или концом отрезка, и имеется отрезок АD, точки В и С ему принадлежат.

А В С D
Определяя функцию вытеснения как

(AB)={AD}, (CD)={AD}, (AD)={AB,CD}

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


Для иллюстрации, в продолжение приведенного примера с отрезками, приведем два фрагмента изображения с рис. 1, в одном из которых имеет место сплошная линия разграфки (AD), во втором – две сонаправленные линии на одном уровне (AB и CD).





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


Пусть фиксировано множество типизированных элементов и функция вытеснения, ограничивающая варианты конструирования объекта o. Функция типизации объекта не определена, функция идентификации элементов не задана. Фиксировано множество моделей М. Требуется определить каким моделям может соответствовать данный объект и определить способы идентификации элементов, при которых объект соответствует той или иной модели. Будем называть задачи такого типа идентификацией модели. Если задача последовательно решается над объектами из некоторого упорядоченного множества и множество моделей на очередном этапе некоторым образом зависит от результатов идентификации, полученных на предыдущих этапах, будем говорить о потоковой идентификации моделей.
В задачах идентификации модели и потоковой идентификации моделей множество М было некоторым образом фиксировано. Качество решения этой задачи во многом зависит от того, каким образом были определены (построены, заданы, постулированы...) модели из M. Под качеством решения подразумевается однозначность идентификации и ее адекватность (с внешней точки зрения, не редуцированной до формализма моделей). Пусть задано множество типизированных объектов, состоящих из типизированных и идентифицированных элементов. Требуется построить множество моделей, наиболее подходящее для решения задачи идентификации модели или потоковой идентификации моделей. Задачи такого типа будем называть конструированием моделей.
В рамках данной работы рассматриваются объекты двумерной природы, представляемые оцифрованными изображениями – матрицами пикселей.
Определим графический образ g как множество его пикселей P={p}. Подмножество пикселей f графического образа будем называть фрагментом графического образа. Под вариантом фрагментации  графического образа будем понимать некоторое множество его фрагментов. Заметим, что согласно такому определению, в рамках варианта фрагментации пиксель может принадлежать нескольким фрагментам одновременно.
Определим функцию интерпретации фрагмента графического образа как элемента некоторого типа I: F x   E x R, которая сопоставляет паре (фрагмент, тип элемента) числовую оценку качества такой интерпретации и заполняет значения атрибутов элемента.
Элементам объектов соответствуют определенные участки на изображениях. Будем обозначать w функцию, устанавливающую соответствие элемента объекта фрагменту графического образа w:EF . В задачах конструирования моделей эта функция может быть элементом входа, в задачах идентификации эта функция на входе не известна.
Будем говорить что установлено соответствие объекта о графическому образу g если фиксирован вариант фрагментации  и фиксирована функция соответствия элементов w.
Пусть на графическом образе g фиксирован некоторый вариант фрагментации . Пусть имеется функция интерпретации I, определяющая множество элементов Ео, которые могут быть получены в результате интерпретации фрагментов из . Пусть о - некоторый объект - подмножество элементов Ео, удовлетворяющее ограничениям функции вытеснения . На основе отображения, обратного функции I на множестве элементов построенного объекта, можем определить функцию w, определяющую какому графическому фрагменту соответствует элемент объекта. Таким образом, используя функцию интерпретации и функцию вытеснения установлено соответствие объекта графическому образу. Далее, пусть имеется модель объекта m, которому соответствует объект о (т.е. фиксирован некоторый способ идентификации элементов, удовлетворяющий ограничениям модели). Таким образом установлено соответствие между графическим образом и моделью объекта и можно говорить о задаче идентификации или потоковой идентификации модели объекта, соответствующего данному графическому образу, а также о конструировании моделей, подходящих для решения этих задач.
Изложенная последовательность действий по установлению соответствия между графическим образом и идентифицированными в рамках модели объекта элементами в общем случае не однозначна:

  • имеется множество возможных вариантов фрагментации

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

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

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

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



  • является ли найденное решение единственно возможным

  • если существуют другие варианты решения, то могут ли они быть проигнорированы (как “существенно менее правдоподобные”)

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

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



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

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

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

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

Пусть Q(g,o, , w) – функция оценки качества установленного соответствия, принимающая значения из множества действительных чисел. Эта функция в дальнейшем будет использоваться для решения двух типов задач оптимизации:



  • для оптимального выбора модели и

  • для поиска оптимального варианта комбинации соответствия элементов (функции именования элементов) при фиксированной модели.

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

  • функция интерпретации фрагмента графического образа как элемента некоторого типа, а также

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

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

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



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

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



Интерпретация
Построим пример, иллюстрирующий введенные понятия.

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




Графический образ заполненной почтовой карточки.


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

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



  • горизонтальные и вертикальные линии разграфки

  • фрагменты статического текста («Кому», «Куда», ...)

  • поля рукописного ввода

  • поля ввода цифр по шаблону

  • поля картинок

Выделим на изображении элементы этих типов и дадим им имена:

Line1..Line12 для горизонтальных линий, Line13..Line15 для вертикальных, Bar1..Bar8 для черных прямоугольников над шаблонами цифр (будем также считать их линиями разграфки), Pict1 – поле картинки, соответствующее месту наклеивания почтовой марки, фрагменты статического текста Static1..Static7, а также поля ввода стилизованных цифр Field1..Field6 и поля рукописного заполнения Field7..Field16. Схема именования перечисленных элементов приведена на следующем рисунке.




Элементы бланка почтовой карточки.


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

  • участвуют в ограничениях модели и

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

Как минимум, для каждого из типов включим в множество атрибутов четверку чисел left, top, right, bottom - прямоугольник фиксирующий расположение элемента и его размеры. Для линий может быть указан стиль – сплошная или пунктирная, для статического текста - строка текста.

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


В качестве ограничений такой модели для каждой пары элементов e1 и e2 зададим множество неравенств типа

|(х1 – х2) – (x’1 – x’2 )| < x

|(y1 – y2) – (y’1 – y’2)| < y

где в качестве x1 подставляются значения атрибутов e1.left или e1.right, в качестве x2 подставляются значения атрибутов e2.left и e2.right, аналогично

в качестве y1 и y2 – атрибуты e1.top, e1.bottom и e2.top, e2.bottom. В качестве переменных x’1,x’2, y’1,y’2 подставляются значения соответствующих атрибутов на одноименных элементах объекта эталонного образца, измеренных на его графическом образе. Для случая e1 = e2 неравенства ограничивают допустимые отклонения размеров размеров элемента от размеров соответствующего элемента образца; для случая e1  e2 неравенства ограничивают изменение относительного расположения элементов. Константы x и y определяются суммой максимальных погрешностей печати, сканирования, а также точностью, с которой функция интерпретации вычисляет значения атрибутов элементов. Поскольку для разных типов элементов и разных атрибутов погрешность вычисления значений может заведомо отличаться, это может учитываться в задании ограничений. Например, для горизонтальной линии разграфки координаты ее концов left и right в общем случае могут быть определены с меньшей точностью чем координаты ее уровня top и bottom - особенно в случаях когда линия плохо пропечатана или в непосредственной близости от ее концов возможно появление других объектов. В данном примере (не претендующем на оптимальность или общезначимость описания, а лишь иллюстрирующем возможный способ задания ограничений) мы ограничились учетом того факта, что погрешности измерений вертикальном и горизонтальном направлении различны – что может быть связано с техникой протяжки листа при печати или сканирования.
В качестве функции внутренней оценки качества варианта установленного соответствия можно задаться суммой двух штрафных функций:

Q = Q1 + Q2

Первую штрафную функцию определим как сумму квадратичных штрафов за отклонения в размерах и расположении элементов по всем парам одноименных элементов эталонного и идентифицируемого объекта:

Q1=cx  ((х1 – х2) – (x’1 – x’2 ))2 + cy((y1 – y2) – (y’1 – y’2))2

Суммирование ведется всем элементам идентифицируемого объекта, для которых в данном варианте соответствия функция именования задана (что позволяет найти одноименный элемент в эталонном объекте) и ограничения модели при этом выполняются. Переменные х1 , х2 , x’1 , x’2 , y1 , y2 , y’1 , y’2 подставляются по тем же правилам, что и в ограниченияхсуммирование ведется по всем парам соответствующих атрибутов; константы cx и cy введены аналогично x и y для дополнительной балансировки штрафов в зависимости от ориентации.

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

qmax=8*N * [max(cx, cy)] *[max(x, y)] 2

Пусть К – число элементов в данном варианте соответствия которые поименованы. Определим Q2 как

Q2 = (N-K) * qmax

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


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

  • определили типы элементов

  • выделили элементы эталонного объекта

  • на эталонном объекте определили функцию идентификации и разыменования – задали имена элементов

  • заполнили атрибуты элементов эталонного объекта

  • определили ограничения модели.

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

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



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


  1. Michael D. Garris. “Correlated run length algorithm (CURL) for detecting form structure within digitized documents”, in Third Annual Symposium on Document Analysis and Information Retrieval, pp. 415-424, UNLV, April 1994

  2. D.Wang, S.N.Shrihari. “Analysis of form images”, in Int. Journ. of Pattern Recognition and Artificial Intelligence Vol. 8 No 5 (1994) 1031-1052.

  3. H.Makino, “Representation and segmentation of document images”, in Proc. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, 1983, pp. 291-296

  4. J.Toyada, Y.Noguchi, and Y.Nishimura, “Study of extracting Japanese nespaper articles”, in Proc. Sixth Int. Conf. on Pattern Recognition, 1982, pp. 1113-1115.

  5. W.Doster, “Different states of a document’s contents on its way from the Gutenbergian world to the electronic world”, in Proc. Seventh Int. Conf. on Pattern Recognition, 1984, pp. 872-874

  6. H.Kida, O.Iwaki, and K.Kawada, “Document recognition system for office automation”, in Proc. Eighth Int. Conf. on Pattern Recognition, 1986, pp. 446-448.

  7. K.Y.Wong, R.G.Casey, and F.M.Wahl, “Document analysis system”, IBM J.Res. Develop. 26, 6 (1982) 647-656.

  8. I.Masuda, N.Nagita, T.Akiyama, T.Takahashi, adn S.Naito, “Approach to smart document reader system”, in Proc. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, 1985, pp. 550-557.

  9. L.A.Fletcher and R.Kasturi, “A robust algorithm for text string separation from mixed text/graphics images”, IEEE Trans. PAMI 10, 6 (1988) 910-918.

  10. Y.Tsuji, “Document image analisys for generating syntactic structure description”, in Proc. Ninth Int. Conf. on Pattern Recognition, 1988, pp. 744-747.

  11. G.Nagy, S.C.Seth, and S.D.Stoddard, “Document analysis with an expert system”, in Proc. Pattern Recognition in Practice II, Amsterdam, June 1985.

  12. K.Inagaki, T.Kato, T.Hiroshima, and T.Sakai, “MACSYM: A hierarchical parallel image processing system for event-driven pattern understanding of documents”, Pattern Recogn. 17, 1(1984) 85-108

  13. F.Esposito, D.Malerba, G.Semeraro, E.Annese, and G.Scafuro, “An experimental page layout recognition system for office document automatic classification: An integrated approach for inductive generalization”, in Proc. Tenth Int. Conf. on Pattern Recognition, 1990, pp. 557-562.

  14. J.L.Fisher, S.C.Hinds, and D.P.D’Amato, “A rule-based system for document image segmentation”, in Proc. Tenth Int. Conf. on Pattern Recognition, 1990, pp. 567-572

  15. R.G.Casey and D.R.Ferguson, “Intelligent form processing”, IBM Syst. J. 29, 3 (1990) 435-450.

  16. S.N. Srihari and G.W.Zack, “Document image analysis”, in Proc. Eighth Int. Conf. on Pattern Recognition, 1986, pp. 434-436.

  17. T.Pavlidis, Algorithms for Graphics and Image Processing, Computer Science Press, 1982.

  18. D.-S.Lee, S.W.Lam, and S.N.Srihari, “A structural approach to recognize handprinted and degraded machine-printed characters”, in Proc. Int. Assoc. for Pattern Recognition Workshop on Syntactic and Structural Pattern Recognition, 1990, pp. 256-272.





Много ли стоит бич сатиры в руках мазохиста? Влодзимеж Счисловский
ещё >>