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

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

□03058434 Полевой Дмитрий Валерьевич

РАЗРАБОТКА МОДЕЛЕЙ, МЕТОДОВ И СРЕДСТВ ОБРАБОТКИ ТАБЛИЧНЫХ ДОКУМЕНТОВ В ИНФОРМАЦИОННЫХ СИСТЕМАХ

Специальность 05 13 18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Москва - 2007

003058434

Работа выполнена на кафедре экономики Московского физико-технического института (государственного университета)

Научный руководитель:

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

Официальные оппоненты:

доктор физико-математических наук, профессор Серебряков Владимир Алексеевич

кандидат физико-математических наук Николаев Дмитрий Петрович

Ведущая организация-

Институт проблем информатики Российской академии наук (ИЛИ РАН)

Защита состоится "25 "мая 2007 г в час (0 мин

на заседании диссертационного совета К 212 156 02 при Московском физико -техническом институте (государственном университете) по адресу 141700, Московская обл, г Долгопруд ный, Институтский пер, 9, ауд 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ

Автореферат разослан " ^ Ь " апреля 2007 г

Ученый секретарь диссертационного совета К 212 156 02

Федько О С

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

Актуальность проблемы

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

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

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

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

• в области хранения и манипулирования данными - СУБД,

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

• в области ввода - системы оптического распознавания

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

Цель работы, задачи исследования

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

В соответствии с поставленной целью основными задачами являются

1 Исследование существующих подходов и моделей обработки таблиц

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

3 Реализация разработанных модели и технологии в комплексе программ для обработки табличных документов

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

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

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

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

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

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

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

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

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

Предложенные в диссертационной работе модели и методы реализованы в комплексе программ Cognitive Forms, зарегистрированном в Роспатенте (№2003610606) Этот комплекс программ предназначен для промышленного ввода документов и имеет внедрения в ряде федеральных, производственных и коммерческих структур На его основе были реализованы и введены в эксплуатацию проекты по автоматизации ввода

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

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

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

Положения, выносимые на защиту

На защиту выносятся следующие основные положения

1 математическая модель табличного информационного объекта и табличного документа,

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

3 реализация предложенных модели, методов и технологии в комплексе программ в среде ОС Windows

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

Научные и практические результаты диссертации доложены, обсуждены и получили одобрение специалистов на XLIX научной конференции МФТИ (Долгопрудный, 2006 г), научных семинарах кафедры прикладной экономики МФТИ в 2003-2006 гт, лаборатории методов искусственного интеллекта ИСА РАН в 2003-2007 гг, отдела систем математического обеспечения ВЦ РАН в 2007 г а также на научно-технологических семинарах в компании ООО "Когнитивные технологии" 2003-2007 гг

Публикации

По теме диссертации опубликовано три работы, две из списка изданий, рекомендованных ВАК РФ

Структура работы

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

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

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

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

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

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

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

1 модель табличного информационного объекта (ИО), описывающая классы допускающих плоское представление ИО и предоставляющая

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

с формализацию допустимых операций над экземпляром таблицы

2 модель плоского представления, определяющая а модель носителя,

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

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

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

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

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

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

В работе таблица рассматривается, как часть документа Модель документа Моос =(МС,М1,М%) состоит из моделей содержания М„, взаимодействия М, и визуализации Мч

Модель содержания Мс =(В5,Т5,К8) определяет кортеж уникальных

документа Т5 = / в'1' 11 е раничения общности уникальные

атрибуты можно считать элементарными (несоставными) объектами, определяющими типы и ограничения данных Табличный атрибут является составным и представляется кортежем VI е!^ В('' = (Т(|',В^,ВЦК)\,

содержащим табличный информационный объект Т*'', идентификационный

атрибутов документа

и кортеж табличных атрибутов

атрибут в',1^ и информационный В^РО атрибут Табличный информационный объект определяет множество элементарных атрибутов Т(,) = |в,и) | ^ Множество бинарных отношений К5 = {К8<,)|1| определяет отношения пар

атрибутов, например "атрибут-заголовок" или "таблица-заголовок таблицы" Табличный информационный объект соответствует множеству реляционных отношений, а его структура рассматривается ниже

Визуальное представление ЕЕ/1' элементарного атрибута В(,), называется элементом документа, содержит текст тх'1' и вписывается в прямоугольник носителя ЯС*'' в соответствии с параметрами форматирования ш'1', то есть Е^'^ТХ^.КС^РК^ Модель визуализации Му =(Е5, ЕЯ) определяет

макет документа как множество элементов документа Е8 = |еь'''| и множество ЕК = ^ея"1 | геометрических непротиворечивых бинарных

отношений между прямоугольниками этих элементов

Модель взаимодействия М[ Мп —> Му определяет связь модели содержания и модели визуализации Модель визуализации, а следовательно, и модель взаимодействия при фиксированной модели содержания определяется неоднозначно

Для описания табличного информационного объекта воспользуемся

информационными функциями явного т|,=£(г|2, .ЛяДр Дм) и неявного Р(г|,, ,1м) виДа Аргументами функций являются существенные

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

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

Общая схема (Рис 1 а) экземпляра плоского представления табличного ИО в документе состоит из областей следующих типов

1 идентификационная зона,

2 угловая заголовочная зона,

3 горизонтальная заголовочная зона,

4 вертикальная заголовочная зона,

5 врезанная заголовочная зона,

6 матричное ядро,

7 информационная зона

идентификационная зона

угловая заголовочная зона горизонтальная заголовочная зона

вертикальная заголовочная зона 1 |

м.ириинлр

янрп

1

врезанная заголовочная зона

вертикальная заголовочная зона 1 1

матрйчнЛ^

информационная зона

6)

Заголовок 1

заголовок 1 1 заголовок 1 1 1 заголовок 1 1 2 заголовок 1 2 Заголовок 2 Г)

Заголовок группы 1

тема 1

тема 2

Заголовок группы 2

тема 3

Заголовок группы 3

а)

Рис 1 Пример а) общей схемы макета таблицы, вертикальной заголовочной зоны типа б) матрица, в) Т-иерархия, г) М-иерархия, г) Г-иерархия

Рассматриваются вертикальные заголовочные зоны 4-х типов матрица (Рис 1 б), Т-иерархия (Рис 1 б), М-иерархия (Рис 1 в) и Г-иерархия зоны (Рис 1 г) Для горизонтальной заголовочной зоны допустимые типы матрица, Т-иерархия и Г-иерархия Логически заголовочная зона представляется лесом деревьев, в которых пути от корня до вершин (м б внутренних) определяют уникальный для зоны ключ, состоящий из значений ячеек заголовочной зоны Тело таблицы в общем случае представляется матричной таблицей, которая согласована с заголовочными областями геометрически Врезка является способом компактного размещения одного или нескольких старших уровней заголовков вертикальной зоны Идентификационная и информационная зоны содержат общую неструктурированную таблично информацию (название, сноски)

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

Рассмотрим множество непересекающихся прямоугольников = |1,УКк,К, =0} Пересечения и объединения будем

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

Я* =ЯЕСТ пипЯ х, ,1шпИ, ут.тахЯ, хк,тахЯ, уп

* г" I I

В*

« I

В!

К*

ГШ

у фк 1

й Р2

а) б) в) ^ г) д)

Рис 2 а) охватывающий прямоугольник Я*, б) отношение родитель - ребенок для прямоугольников, в) корневой прямоугольник, г) отношение брат - брат, д) продолжение родителя детьми

Прямоугольники Я0 и Я, находятся в отношении родитель - ребенок (Рис 2 б), что обозначим 110 или если

ХИ = К1ХЬ

• Ут

Уп^1 Ув

Определим дополнительный прямоугольник Я™0' ЯГ00' соблюдением следующих условий к™' ут = Я* ут

Кг„о1ув = К.ув

Я'"" Я*

КС

Множество = УЯи{Кго"'| назовем расширением исходного множества Расширение и множество отношений на нем определяют граф

хЯ* (Рис 2 в) с

наследования Г = (9Г,К

>(1>"с' который является деревом

Будем говорить, что прямоугольники К) и Я-, находятся в геометрическом отношении старший брат - младший брат (Рис 2 г) и записывать 11,^11, или г'в>в'(К0Д|), если справедливо соотношение

Ув^з Ут

Рассмотрим множество детей ЭТСП(К0) = |К1|1 для

прямоугольника К0 Будем говорить, что дети полностью продолжают родителя и записывать 110 < 9?сп (Я0), если справедливо соотношение

Ут = коУт

я1у„ = к1+1ут

КнУв = КоУв

Будем говорить, что прямоугольники множества Ь^еЗ? образуют Т-иерархическое покрытие, если они плотно покрывают охватывающий

я, ¿-и,.,

прямоугольник К' = Д.К, ■ и лля каждого из них родитель определен единственным образом 3' К, € ЧЛ+: К^К, Последнее условие

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

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

[ и и, [^Ке^ГЗКеЗГЯ )

1 I 1 1 с:- 1 (. н \

*

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

! 1епустая угловая зона может содержать значения только несущественных переменных и должна быть согласована с вертикальной и/или горизонтальной заголовочной зоной. Угловая зона Играет для вертикальной или горизонтальной заголовочной зоны ту же роль, что и заголовочная зона для тела, поэтому согласование идет по аналогичным правилам. Основными типами непустых угловых зон являются матрица (Рис.3.а) и Т-иерархия (Рис.3.5). Одновременное согласование угловой зоны с обеими заголовочными зонами возможно для косою (Рис.з.в) и матричного (Рис З.Г) типа.

||||| I I г^т

а) 6) в) г)

Рис.з Макет угловой заголовочной зоны типа а) матрица, й) Т-иерархия, в) косая симметрия, г") матричная симметрия.

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

1. плоское представление, которое не содержит заголовочных зон; 2 плоское представление, которое содержит одну заголовочную зону;

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

Класс I - многомерный табличный информационный объект Tn,N>1 представляется кортежем TN = где вектор измерений

V е I = х определяет подпространство в котором вектору

Av=(5 iVieполного адресного пространства

Д = 1£х Д1 =|s|Vri-|^8i^i^j|VV[i]eI1| по закону из множества функций

0 = jfv(Xvj| Velj сопоставляется скалярная зависимая переменная

v\iv = fv (Xv) из множества зависимых переменных Ч* = j\|/v | V е ij Важным частным случаем является количество измерений N = 2 тз = (vP ч = fp q (ЧЛч) JrJc^rA^rc^rc) >

для которого измерения IR,IC и адресные подпространства ДК,ДС называются строковыми и столбцовыми, соответственно Закон К определяет способ перехода от общего вида к плоскому

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

1 JNDIM(lJ,Injo,N) - объединить измерения I, G jdioin с j в одно новое

2 DNDIM^j,!™^"14-) - разделить измерение е I на несколько

I,eIDJH,NcI

3 ADDF^S, х tj - добавить новую функцию ft ^ измерения I,

4 DELFTS, - удалить функции f, i f измерения I,

5 DELVES, 1 ,8^,) - добавить значение , функции ft N t измерения

I,

6 DELv|st Vt,S[\> t j - удалить значение 8|\',, функции f1%1] измерения

I,

7 SUBV(S(vv^VvA'v'r) ~ заменить значение й^1, функции f,

измерения I, на новое Класс II табличных ИО являются объекты следующего вида Т = (Ф), где функции множества функций

Ф = {р0(с),р1(^)|.л=у(л11> = ,<к))и{р0(;)} согласованы

по числу аргументов N

Для таких табличных объектов определены следующие операции

1 АЭОР^Р, добавить новую функцию Р,

2 ЭНЬГ^Р, (£,)) - удалить существующую функции Р,

3 ЛОО\'|р, - добавить значение функции Р,

4 ОЕ1Л^Р,(5«)ДГ') - удалить значение функции Р,

В работе показывается эквивалентность табличных ИО класса I множеству реляционных отношений Класс II табличных ИО в общем случае не имеет прямого реляционного представления

Макет плоского представления описывается таблицей, подобной экземпляру, в ячейках которой содержатся переменные Дополнительно задается иерархия и способ упорядочивания по значениям переменных Если упорядочивание значений не возможно задать аналитически, макет и представление совпадают Плоское представление табличных ИО класса I имеет не менее одной заголовочной зоны, содержащей значения

а) б)

Рис 4 Общая схема макетов вывода плоских представлений табличных ИО а) первого класса, б) второго класса

Плоское представление табличных ИО класса II либо вообще не имеет заголовочной зоны, либо заголовочная зона содержит значения идентификационных переменных (Рис 4 б)

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

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

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

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

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

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

Предложенный метод сегментации использует минимальное остовное дерево, построенное на компонентах связности изображения структурированного документа Минимальный охватывающий прямоугольник компоненты связности является точкой (xl,yl,x2,y2)e34 четырехмерного псевдометрического пространства Расстояние между двумя прямоугольниками определяется следующим образом w(a,b) = | dx | +1 dy |, где |dx | = max (max (а х 1 - b х2,0), max (b х 1 - а х2,0)), |dy | = max (max (а у 1 - b у 2,0), max (b у 1 - a y2,0))

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

• процедура выбора удаляемых ребер менее тривиальна, чем удаление наиболее длинных,

• полученные в результате фрагменты могут быть не полными объектами, а лишь фрагментами объектов

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

Существенным вопросом реализации стала вычислительная сложность построения минимального остовного дерева, так как для документов низкого качества (например, рассыпанный матричный принтер) количество вершин графа может достигать порядка 10-20 тысяч Оценки сложности реализации

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

Пусть S - некоторое конечное множество, элементы которого мы называем точками данных, и на котором определена некоторая функция расстояния w S хS -»R удовлетворяющая условиям Va,beS w(a,b) >0 w(a,a) = 0 w(a,b) = w(b,a) w(«, •) г const

Заметим, что w не является метрикой, поскольку не соблюдается w(a,b) = 0 о а=Ь и w(a,b)< w(a,c) +w(b,c), Va, b, ceS

Пусть можно определить функцию расстояния между точками и множествами точек w(a,S) таким образом, что

1 расстояние от точки до любого подмножества исходного множества не меньше расстояния от точки до исходного множества, Va е S, VS, с S, с S -» w(a,S[) < w(a,S2)

2 расстояние между двумя точками совпадает с расстоянием между любой их этих точек и одноточечным множеством, содержащим вторую точку, Vas S, VS^JbjcS-» w(a,S[) = w( a, b )

Расстояние от некоторой точки до объединения множеств не превышает расстояния от точки до каждого из подмножеств w(a,S, uS2)<w(a,S!), w(a,S,uS2)<w(a, S,) и обращается в ноль на элементе множества VaeS,cS vv(a,S,)=0

Если для любых точек и множеств Va е S VS, е S операция вычисления расстояния между точкой и множеством w(a,S,) имеет сложность порядка сложности вычисления расстояния между точками w(a,b), то возможно построение вспомогательной структуры данных для эффективного решения задачи поиска k-ближайших соседей некоторой точки

Рассмотрим семейство S|N| разбиений исходного множества точек S = sj!' на непересекающиеся подмножества

Sp = |s'pq' | q е QP, Vql ^q2-> S(pq,) nS(pq2) =0|, образующих полное покрытие

исходного множества VpeNN U Sp(|) = S и обладающих свойством

qeQp

вложенности Vs(pq),|s(pq,|>l 3ijpq,|jrq|>l S(pq) = U S(j|, Полное семейство

II JeJP4

разбиений имеет вид s'N' = {Sp | p e Nn }u{S0 = S}

Будем говорить, что между множествами Бр,1' е и Бр,2' е установлено отношение родитель-ребенок Бр,1'хБ^2', если Р2 = Р1 + 1 и 8р|'' з Бр? Множество пар вида Бр,1' >- Бр? определяет ребра дерева разбиений Г ^б'^ДМ Для поиска ближайшего соседа точки ае8

организуем очередь с приоритетом О1, хранящую пары вида в

порядке возрастания \у|а,5р'| Далее применим следующий алгоритм

1 На первом шаге поместим в очередь вершину дерева разбиений Г,

«^(Ца^А,)

2 Далее до завершения на каждом шаге будем вынимать из очереди верхний элемент О—^лл^а^'р,1'^^

а Если Бр,1'! = 1, то вынутая вершина Яр1/' является ближайшим

соседом и задача решена Ь В противном случае у текущей вершины б'?,1' есть потомки б'Д, , до которых следует вычислить расстояния и поместить соответствующие в очередь У)еЛр1ч1 Перейти к следующему шагу

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

соединяющих ее со свободными вершинами, =

доопределим 7с[у] = 0 = <х>

Безопасное ребро (у,тг[у]) для каждой вершины V остова хранится в очереди с приоритетом О в порядке возрастания длины ребра Алгоритм состоит в следующем

1 Инициализируем счетчик свободных вершин числом таких вершин

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

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

а если вынутое ребро (у, я [у]) безопасное, то добавим вершину тф'] и само ребро к остову А, уменьшим счетчик свободных вершин на единицу, вычислим новые безопасные ребра для обоих концов ребра V и л [у], а также добавим новые ребра в очередь Перейдем к следующему шагу Ь если вынутое ребро (у,7г[у]) перестало быть безопасным, то вычислим новое безопасное ребро для вершины у и добавим его в очередь Перейдем к следующему шагу

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

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

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

После определения события е, обработчика событий и очереди обработки Q при последовательной обработке событий формально показывается, что зацикливание обработки события (обработка очереди продолжается бесконечно долго) возможно тогда и только тогда, когда в очереди появляется событие, порождающее само себя 3t BeeQ, 3N eeMNe

Ориентированный граф обработки событий отражает возможные зависимости попадания событий в очередь Е0 = {Е0,А0}, где Ес, -множество событий, Ае - множество зависимостей

a=(u,v)eAG -> u,veE0, (u,v)eAc>, означает, что при обработке и в

очередь попадет v

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

Ar = {(u,v) ueE",ve E"ut}

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

Ac=UAr

reR

и множество событий для документа

EG=UE'rnUUErUt

reR reR

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

Mje = [J E?ul

reR сеЕ|."

Таким образом, состояние очереди событий описывается в терминах графа зависимостей событий Mne = {qeEG Зпуть в EG длинной п между q и е},

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

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

технологические линии массового ввода стандартизованных форм документов Модули комплекса устанавливаются на компьютерах, соединенных в локальную вычислительную сеть, и, взаимодействуя между собой, организуют конвейер обработки данных, позволяющий вводить до 10 ООО и более страниц за сутки Комплекс функционирует на платформе \Vin32, включает 14 исполняемых модулей (основных и вспомогательных) и 95 динамически подгружаемые библиотеки Основная часть комплекса реализована на языке С++

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

1 контейнер - хранилище и доступ к данным таблицы,

2 редактор электронного (экранного) представления таблицы,

3 компонента вычислений и проверки данных таблицы,

4 редактор печатного макета таблицы,

5 генератор табличной части отчета (печать),

6 выделитель таблиц на изображении,

7 редактор разметки изображений таблиц (создание, контроль и просмотр разметки изображений и электронных представлений),

8 анализатор структуры и восстановления табличного ИО,

9 утилиты (конверторы и т д )

Общая схема обработки документов (Рис 5) состоит из двух этапов

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

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

предварительным этап

подготовка . описаний таблиц V

основной этап

1 сканирование документов — ► распознавание таблиц

выгрузка результатов

Рис 5 Общая схема системы ввода табличных документов

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

В заключении сформулированы основные результаты диссертационной работы.

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

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

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

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

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

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

Публикации по теме диссертации:

1 Полевой Д В Анализ обработки событий в объектно-событийной модели документа // Труды института системного анализа Российской академии наук (ИСА РАН) Документооборот Концепции и инструментарий -М Эдиториап УРСС, 2004 - С 83-91

2 Полевой Д В, Постников В В, Усков А В Алгоритм быстрого построения минимального охватывающего дерева для множества точек в конечномерном псевдометрическом пространстве // Труды института системного анализа Российской академии наук (ИСА РАН) Интеллектуальные информационные технологии Концепции и инструментарий Т 16 -М КомКнига, 2005 -С 130-145

3 Полевой Д В Таблицы в системах обработки документов - М Издательство ЛКИ, 2007 48 с

Полевой Дмитрий Валерьевич

Разработка моделей, методов и средств обработки табличных документов в информационных системах

Автореферат

Подписано в печать 16 04 2007 Уел Печ JI 1 2 Тираж 80 экз Заказ № 376

Московский физико-технический институт (государственный университет) НИЧМФТИ

Печать на аппаратуре Rex-Rotary Copy Printer 1280

141700, Московская обл , г Долгопрудный, Институтский пер , 9

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР ИСПОЛЬЗОВАНИЯ ТАБЛИЦ В ИНФОРМАЦИОННЫХ СИСТЕМАХ.

1.1. Таблица и ее функции.

1.2. Использование таблиц и ПО.

1.3. Модели таблиц.

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

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

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

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

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

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

2. автоматизации логического контроля достоверности ввода и сохранения целостности табличного документа;

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

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

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

• ввода/вывода таблиц на дисплей монитора;

• автоматического (полуавтоматического) распознавания таблиц и верификации результатов распознавания;

• табличных расчетов;

• вывода таблиц на бумагу.

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

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

Основные результаты данной работы доложены, обсуждены и получили одобрение специалистов на XLIX научной конференции МФТИ (Долгопрудный, 2006 г.), научных семинарах кафедры прикладной экономики МФТИ в 2003-2006 гг., лаборатории методов искусственного интеллекта ИСА РАН в 2003-2007 гг., отдела систем математического обеспечения ВЦ РАН в 2007 г. а также на научно-технологических семинарах в компании ООО "Когнитивные технологии" 2003-2007 гг.

По теме диссертации опубликовано три работы, одна из них в соавторстве ([1]-[3]).

Заключение

В диссертации получены следующие основные результаты.

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

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

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

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

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

1. Полевой Д.В. Анализ обработки событий в объектно-событийной модели документа // Сб. тр. /ИСА РАН-М.: Эдиториал УРСС, 2004. С. 83-91.

2. Полевой Д. В., Постников В.В., Усков А.В. Алгоритм быстрого построения минимального охватывающего дерева для множества точек в конечномерном псевдометрическом пространстве // Сб. тр. / ИСА РАН, М. КомКнига 2005 г. Т. 16. С. 130-145.

3. Полевой Д. В. Таблицы в системах обработки документов. М.: Издательство ЛКИ, . 2007.48 с.

4. Арлазаров В. J1., Емельянов Н. Е. От баз данных к базам знаний (объекты, формы, содержание) // Сб. тр. / ИСА РАН, М.: КомКнига, 2006 г. С. 6-17.

5. Емельянов Н.Е. Проблемы автоматизации программирования документного интерфейса с базами данных: Дис. доктора тех. наук. М., 1987. - 319с.6., Иванов Ю.Н. Теория информационных объектов и системы управления базами данных. М.: Наука, 1988. - 232с.

6. Иванов Ю.Н., Емельянов Н.Е., Сотникова Р.А. Документы: типы, описания Препринт. /ВНИИСИ- М„ 1987.-62 с.

7. ГОСТ 2.105-95 ЕСКД Общие требования к текстовым документам.

8. Елисеева И.И., Юзбашев М.М Общая теория статистики 2-е изд. / Под ред. И.И.Елисеевой. - М.: Финансы и статистика, 1996. - 368 с.

9. The Chicago Manual of Style, 14th ed. The University of Chicago Press, 1993.-921 p.

10. Publication Manual of the American Psychological Association, 4th ed. // АРА, 1994. -439 p.

11. Handbook of Style and Usage // Asian Development Bank, 2002. http://www.adb.org/Documents/Handbooks/StyleUsage/HSU.pdf

12. Wright P., Hull A. J., Lickorish A. Psychological factors in reading tables // In Proceedings of XXIII International Congress of Psychology, Mexico, 1984. P. 194

13. Vanthienen, J., Wets G. Restructuring and optimizing knowledge representations // In Proceedings of the Sixth International Conference on Tools with Artificial Intelligence, 1994.-P. 768-771.

14. Миллер Дж.А. Магическое число семь плюс или минус два. О некоторых пределах нашей способности перерабатывать информацию // Психология памяти. / Под ред. Ю.Б. Гиппенрейтер и В.Я. Романова. М.: ЧеРо, 2000. - С. 564-582.

15. Dalgleish D. Excel Pivot Tables Recipe Book: A Problem-Solution Approach. APRESS, .2006.335 p.

16. Gerald J. O'Brien and W. David Wilde. Australian managers' perceptions, attitudes and use of information technology // Information and Software Technology, 1996. V. 38 P. 783789.

17. George E. Vlahos and Thomas W. Ferratt. The use of information technology by managers of corporations in greece to support decision making. In Proceedings of the conference on Computer Personal Research, ACM, 1992. P. 136-151.

18. Clermont M., Hanin C., Mittermeir R. A Spreadsheet Auditing Tool Evaluated in an Industrial Context // In Spreadsheet Risks, Audit and Development Methods, 2002. V. 3. -P. 35-46.

19. Clermont M. A Scalable Approach to Spreadsheet Visualization PhD thesis, Universitat Klagenfurt, Austria, 2003. 202 p.

20. Butler R. Is This Spreadsheet a Tax Evader? How H. M. Customs & Excise Test Spreadsheet Applications // In Proceedings of the 33rd Hawaii International Conference on System Sciences, 2000. V. 4. P. 400-407

21. Nunez F. An extended spreadsheet paradigm for data visualization systems and its implementation. M.Sc. dissertation, University of Cape Town, 2000. 156 p.

22. Tukiainen M. Developing a New Model of Spreadsheet Calculation: A Goals and Plans Approach. PhD dissertation, University of Joensuu, 2001. 121 p.

23. Spenke M., Beilken C. A spreadsheet interface for logic programming // In Proceedings of ACM CHI'89 Conference on Human Factors in Computing Systems, 1989. P. 75-80.

24. Kunstmann, Т., Frisch M., Muller R. A declarative programming environment based on constraints // In Proceedings of the 11th international IEEE Symposium on Visual Languages, 1995. P. 120.

25. Judith G. Hays and Margaret M. Burnett. A guided tour of Forms/3. Technical Report TR 95-60-6, Oregon State University, Computer Science Department, June 1995. (Revised Janurary 1997). - 35 p.

26. Cervesato I. NEXCEL a Deductive Spreadsheet // The Knowledge Engineering Review, 2006. http://theory.stanford.edu/~iliano/papers/ker06.pdf

27. Kassoff M., Zen L., Garg A., Genesereth M. PrediCalc: a logical spreadsheet management system // In Proceedings of the 31st international Conference on Very Large Data Bases, 2005.-P. 1247-1250.

28. Johnson S. D. A tabular language for system design. Technical Report 485, Indiana University Computer Science Department, 1997. - 6 p.

29. Sam 0., John R., Natarajan S. Analyzing Tabular And State-Transition Requirements Specifications in PVS. Technical Report. UMI Order Number: NASA-97-cr201729, NASA Langley Technical Report Server. - 30 p.

30. Janicki R., Wassyng, A. Tabular Expression and Their Relational Semantics // Fundamenta Informaticae, 2005. V. 67. № 4. P. 343-370.

31. Scott E. Hudson. User interface specification using an enhanced spreadsheet model. ACM Transactions on Graphics, July 1994. V. 13. № 3. P. 209-239.

32. Myers B. A. Graphical techniques in a spreadsheet for specifying user interfaces // In Proceedings of ACM CHI'91 Conference on Human Factors in Computing Systems, 1991.1. P.243-249.

33. Anupam V., S. Dar, T. Leibfried, and E. Petajan. DataSpace: 3-D visualizations of large databases // In Proceedings of the Symposium on Information Visualization '95, 1995. -P. 82-88,144,145.

34. Wijke J.J., Hyperslice R.L. Visualization of scalar functions of many variable // In i Proceedings of IEEE Visualization Conference '91, Los Altimos, CA, 1991. P. 119-125.

35. Kobsa, A. User Experiments with Tree Visualization Systems // IEEE Symposium Information Visualization (INFOVIS 2004), 2004. P. 9-19.

36. Spenke M., Beilken C. Visualization of trees as highly compressed tables with InfoZoom // Unpublished entry in InfoVis 2003 Contest, held at IEEE Symposium on Information

37. Visualization. http://www.cs.umd.edu/hcil/InfovisRepository/.

38. Spenke M, Beilken C., Berlage T. FOCUS: the interactive table for product comparison and selection // In Proceedings of the 9th annual ACM symposium on User interface software and technology, 1996. P. 41-50.

39. Chi E. H. A Framework for Information Visualization Spreadsheets. PhD thesis, Department of Computer Science, University of Minnesota, March 1999. - 146 p.

40. Chi E.H., Riedl J., Barry P., Konstan J.A., Principles for information visualization spreadsheets // IEEE Computer Graphics and Applications, 1998. V. 18, № 4, - P. 30-38.

41. Marchionini G., Hert C., Liddy L., Shneiderman B. Extending understanding of federal statistics in tables // In Proceedings on the 2000 Conference on Universal Usability, 2000. -P. 132-138.

42. Chen W., Chung K. A Table Presentation System for Database and Web Applications // In Proceedings of the 2004 IEEE international Conference on E-Technology, E-Commerce and

43. E-Service (Eee'04), 2004. P. 492-498.

44. Соловьев A.B. Разработка методов и средств взаимодействия объектно-ориентированных систем управления базами данных с электронными издательскими комплексами: Дис. канд. тех. наук М., 2000. - 131 с.

45. CrystalReports // http://www.businessobjects.com/products/reporting/crystalreports/default.asp

46. Oracle Reports // http://www.oracle.com/technology/products/reports/index.html

47. FastReport // http://fast-report.com/ru/

48. QuickReport // http://www.qusoft.com/

49. Rennhackkamp M. Oracle7 Release 7.3 // DBMS Magazine, 1996. V. 9. № 13. P. 53-54.

50. Chen W., Chung K. A Table Presentation System for Database and Web Applications // In Proceedings of the 2004 IEEE international Conference on E-Technology, E-Commerce and E-Service (Eee'04), 2004. P. 492-498.

51. Тарасенко В.Ф., Бухарова M.C. Технология «The Reporter» для построения отчетов по базам данных // Вестник ТГУ, апрель, 2002. № 275. С. 167-176.

52. CuneiForm http://www.cuneiform.ru/

53. Abbyy FineReader http://www.abbyy.ru/finereader/

54. OmniPage http://www.nuance.com/omnipage/

55. Кляцкин B.M. Иерархический кластер-анализ многоколонных текстов // Труды V Международной конференции (Статистический и дискретный анализ данных и экспертные оценки), Одесса, 1994. С. 132-134.

56. Arias, J.F., Chhabra A., Misra, V. Efficient interpretation of tabular documents // In Proceedings of the 13th International Conference on Pattern Recognition, 1996. V. 3. -P. 681-685.

57. Green E., Krishnamoorthy M. Model-based analysis of printed tables // In Proceedings of International Conference on Document Analysis and Recognition (ICDAR), 1995. P. 214j 217.

58. Tubbs К. M., Embley D. W. Recognizing records from the extracted cells of microfilm tables // In Proceedings of the 2002 ACM Symposium on Document Engineering, ACM Press, New York, NY, 2002. P. 149-156.

59. Douglas S., Hurst M., Quinn D. Using natural language processing for identifying and interpreting tables in plain text // In Proc. Fourth Ann. Symp. Document Analysis and Information Retrieval, Las Vegas, Nevada, 1995. P. 535-546.

60. Hurst M. Layout and language: exploring text block discovery in tables using linguistic resources // In Proceedings of Sixth International Conference on Document Analysis and Recognition, 2001. P. 523-527.

61. Pivk A., Cimiano P., Sure Y. From tables to frames // Journal of Web Semantics, V. 3 № 2, Oct. 2005.-P. 132-146.

62. Hu J., Kashi R., Lopresti D., Wilfong G. A system for understanding and reformulating tables // In Fourth ICPR Workshop on Document Analysis Systems, Rio De Janeiro, Brazil, December 2000.-P. 361-372

63. Hu J., Kashi R., Lopresti D., Wilfong G. Medium-independent table detection // In SPIE Document Recognition and Retrieval VII, San Jose, CA, 2000. P. 291-302.

64. Богачева A.H., Емельянов H.E., Романов А.П. Генерация информационных систем по формам входных и выходных документов. // PC Magazine. 1993. №1. С. 85-89.

65. Годунов А.Н., Емельянов Н.Е., Романов А.П. Управление выводом сообщений в ! системе ИНЕС // Программирование. 1984. №6. С. 52-57.

66. Емельянов Н.Е. Виды представления структурированных данных // Теоретические основы информационной технологии / Сб. тр. Вып. 22. — М/.ВНИИСИ, 1988. С. 4246.

67. Емельянов Н.Е., Жаринов А.Н. Вывод документов в системе ИНЕС: Учебн. пособие. -IМ.: МИСиС, 1990.-69 с.

68. Wang X. Tabular Abstraction, Editing, and Formatting. PhD thesis, University of Waterloo, Waterloo, Ontario, Canada, 1996. - 184 p.

69. Silberhorn H. TabulaMagica An Integrated Approach to Manage Complex Tables // In Proceedings of the 2001 ACM Symposium on Document Engineering, ACM Press, 2001.1. P. 68-75.

70. Haralick R.M. Document image understanding: geometric and logical layout // In Proceedings of the 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 1994. P. 385-390.

71. Nagy G. Twenty years of document image analysis in PAMI // In IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 22, Issue 1, Jan 2000. P. 38-62.

72. Lesk M.E. Tbl A Program to Format Tables // Computing Science Technical Report, 1976. No.49.-P. 35-51.

73. Кнут Д.Е. Все про ТЕХ. / Пер. с англ. Протвино: АО RDTEX, 1993. 592 с.

74. Biggerstaff T.J., Endres D.M., Forman I.R. Table: Object oriented editing of complex ; structures // In Proc. of the 7th International Conference on Software Engineering, 1984. P.334.345.

75. HTML 4.01 Specification W3C Recommendation 24 December 1999. http://www.w3 .org/TR/1999/REC-html401 -19991224

76. OpenDocument vl.l specification.http://www.oasis-open.org/committees/tchome.php?wgabbrev=office

77. Document Object Model (DOM) Level 3 Core Specification http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407.

78. Extensible Markup Language (XML) 1.0 (Third Edition) W3C Recommendation, 04 February 2004. // http://www.w3.org/TR/2004/REC-xml-20040204.

79. Engelbart C., English W. K. A research center for augmenting human intellect // AFIPS Conference Proceedings of the 1968 Fall Joint Computer Conference 1968. V. 33. P. 395410.

80. Quint V., Vatton I. Grif: an Interactive System for Structured Document Manipulation // In Proceedings of the International Conference on Text Processing and document Manipulation, Cambridge University Press, 1986. P. 200-213.

81. Kieninger, Т., Dengel, A. An Approach towards Benchmarking of Table Structure Recognition Results // In Proceedings of the Eighth international Conference on Document Analysis and Recognition, 2005. P. 1232-1236.

82. Hurst M. A Constraint-based Approach to Table Structure Derivation // In Proceedings of the Seventh International Conference on Document Analysis and Recognition, 2003. P.911.915.

83. Hu J., Kashi R., Lopresti D., Nagy G., and Wilfong G. Why table ground-truthing is hard // In Proceedings of the Sixth International Conference on Document Analysis and Recognition, September 2001. P. 129-133.

84. Zanibbi R. A Language for Specifying and Comparing Table Recognition Strategies // PhD , thesis, Queen's University Kingston, Ontario, Canada , December 2004.

85. J. Hu, R.S. Kashi, D. Lopresti, and G.T. Wilfong. Evaluating the performance of table processing algorithms. Int'l J. Document Analysis and Recognition, 2002. V. 4. P. 140— 153.

86. Wang Y. Document analysis: table structure understanding, and zone content classification: Ph.D. Thesis, University of. Washington, Seattle, WA, 2002. 161 p.

87. Wang Y., Haralick R. M., Phillips I. T. Automatic Table Ground Truth Generation and a Background-Analysis-Based Table Structure Extraction Method // In Proceedings of the

88. Sixth International Conference on Document Analysis and Recognition, 2001. P. 528-532.

89. Liang J. Document Structure Analysis and Performance Evaluation: Ph.D thesis, Univ. of Washington, Seattle, WA, 1999. 168 p.

90. Phillips I. Т., Chhabra A. K. Empirical Performance Evaluation of Graphics Recognition Systems // IEEE Transactions on Pattern Analysis and Machine Intelligence, Sept., 1999.1. V. 21, №9, P. 849-870.

91. Codd, E. F. A relational model of data for large shared data banks // In Communications of the ACM, 1970. V. 13. №6, P. 377-387

92. Date C.J. An Analysis of Codd's Contribution to the Great Debate // Intelligent Enterprise, May 11, 1999, V. 2,№. 7.

93. Дейт К. Введение в базы данных. : Пер. с англ. 6-е изд. - К.: Диалектика, 1998. -784 с.

94. Miller R.J., Ioannidis Y.E., Ramakrishnan R. The Use of Information Capacity in Schema Integration and Translation // In 19th International Conference on Very Large Data Bases (VLDB'93), 1993.-P. 120-133.

95. Ziegler P., Dittrich K. R. Three Decades of Data Integration All Problems Solved? // 18th ' IFIP World Computer Congress (WCC 2004), 2004. V. 12. - P. 3-12.

96. Fagin R., Vardi M. Y. The Theory of Data Dependencies An Overview // In Proceedings of the 11th Colloquium on Automata, Languages and Programming (1СALP 1984), 1984. -P. 1-22.

97. Vincent M. W., Liu, J., Liu, C. Strong functional dependencies and their application to normal forms in XML // ACM Trans. Database Syst. (Sep. 2004). V. 29, №3. P. 445-462.

98. Hull R., King, R. Semantic database modeling: survey, applications, and research issues -ACM Comput. Surv. (Sep. 1987). V. 19. №3. P. 201-260.

99. Thalheim B. An overview on semantical constraints for database models // 6th International Conference on Intellectual Systems and Computer Science, Moscow, Russia, December 110,1996.

100. Thalheim B. Foundations of Entity-Relationship Modeling // Annals of Mathematics and Artificial Intelligence, 1993. V. 7, P. 197-256.

101. Dong G., Libkin L., Su J., and Wong L. Maintaining transitive closure of graphs in SQL // Int. Journal of Information Technology, 1999.

102. Вартазарян Т. Иванов Д. Хранение XML-документов в реляционной СУБД // Программист, 2002. №3. С.36-40

103. Wagner S. A Data Warehouse for Cross-Species Anatomy // MSc Dissertation. Heriot-Watt University, 2002.

104. Kuper G.M. The logical data model: a new approach to database logic. PhD thesis, Stanford University, 1985.

105. Abiteboul S., Cluet S,, Milo T. Correspondence and Translation for Heterogeneous Data // In Proceedings of the International Conference on Database Theory (ICDT), 1997. P. 351-363.

106. Binh N.T., Tjoa A M., Mangisengi O. MetaCube-X: An XML Metadata Foundation for ; Interoperability Search among Web Warehouses // Proceedings of the International

107. Workshop on Design and Management of Data Warehouses (DMDW'2001), 2001. P. 8.

108. Jagadish H., Lakshmanan L., Srivastava D., and Thompson K. TAX: A Tree Algebra for XML // In Proceedings of The International Conference on Database Programming Languages (DBPL), 2001. P. 149-164.

109. Paparizos S., Al-Khalifa S., Jagadish H. V., Niemann A., Wu. Y. A physical algebra for XML // Technical report, University of Michigan, 2002.

110. Johnson Т., Lakshmanan V. S., Raymond T. N. The 3W Model and Algebra for Unified Data Mining // In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB), 2000. P. 21-32.

111. Eriksson-Bique S. An Algebraic Theory of Multidimensional Arrays // Dissertation, University of Joensuu, 2002.

112. Kimball R., Ross M. The Data Warehouse Toolkit The Complete Guide to Dimensional Modeling. - Wiley, 2002.

113. Abell'o A., Samos J., Saltor F. Understanding Facts in a Multidimensional Object-Oriented Model. // In Proc. of the 4th Int. Workshop on Data Warehousing and OLAP (DOLAP). ACM, 2001. P. 32-39.

114. Nguyen T.B., Tjoa A M., Wagner R.R. Conceptual Multidimensional Data Model Based on MetaCube // Proceedings of the 2001 ACM symposium on Applied computing, 2001. -P. 295-300.

115. Bezenchek, A., Rafanelli, M., Tininini, L. A Data Structure for Representing Aggregate Data // In Proceedings of the Eighth International Conference on Scientific and Statistical Database Management 1996. P. 22-31.

116. Арлазаров B.B. Структурирование визуальных представлений информационной среды и методы определения надежности распознавания: Автореферат дис. канд. тех. наук М., 2004.24с.

117. Емельянов Н.Е. Введение в СУБД ИНЕС. М.: Наука, 1988. - 256 с.

118. Годунов А.Н., Емельянов Н.Е. и др. Система НИКА // В книге «Системы управления базами данных и знаний» / М.: Финансы и статистика, 1991, С. 209 - 248.

119. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -: М.: МЦНМО, 2001.-960 с.

120. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1985. - 455 с.

121. Арлазаров В. В., Постников В.В., Шоломов Д.Л. Cognitive Forms система массового ввода структурированных документов // Сб. тр. / ИСА РАН. - М.: Эдиториал УРСС, 2002. С. 35-46.

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

123. В. Липский Комбинаторика для программистов М.:Мир, 1988. - 200 с.

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

125. Арлазаров В. Л., Логинов А.С., Славин О.А. Характеристики программ оптического распознавания текста // Сб. тр. / ИСА РАН М.: Эдиториал УРСС, 2001. С. 5-10

126. O'Gorman L. The Document Spectrum for Page Layout Analysis // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. V. 15. №11. P. 1162-1173

127. Dias A.P. Minimum Spanning Trees for Text Segmentation // In Proc. of the Fifth Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, Nevada, 1995.-P. 61-65.

128. Ittner D. Automatic Inference of Textline Orientation // In Proc. of the Second Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, Nevada, 1993. -P. 123-133

129. Zlatopolsky A.A. Automated document segmentation // Pattern Recognition Letters, July 1994. V. 15. №7. P. 699-704.

130. Дуда P., Харт П. Распознавание образов и анализ сцен./ Пер. с анг. М.: Мир, 1976. -511 с.

131. Comer D. Ubiquitous B-tree // ACM Computing Surveys, June 1979. V. 11. №2. P. 121-137.

132. Dobkin D., Lipton R.J. Multidimensional searching problems // SIAM Journal of Computing, 1976. V. 5. №2. P. 181-186

133. Friedman J.H., Bently J.L., Finkel R.A. An algorithm for finding best matches in logarithmic expected time // In ACM Transaction on Mathematical Software, 1977. V. 3. -P. 209-226.

134. Tsaparas P. Nearest Neighbor Search in Multidimensional Spaces Depth Oral Report, June 10,1999.-50 p.

135. Agarwal P.K., Edelsbrunner H., Schwarzkopf 0., Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs // Proc. 6th ACM Symp. Сотр. Geom., 1990, P. 189201.

136. Yianilos P.N. Data structures and algorithms for nearest neighbor search in general • metric space // In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete

137. Algorithms (SODA '93), 1993. P. 311-321.

138. Katayama N., Satoh S. The RS-tree: An index structure for high-dimensional nearest neighbor queries // In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1997. V. 26. №2. P. 369-380.

139. Sarnak N., Tarjan R.E. Planar point location using persistent search trees. // Commun. ACM, 1986. V. 26.-P. 669-679.

140. Berchtold S., Keim D.A., Kriegel H.-P. The X-tree: An index structure for high-dimensional data // In VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, 1999. P. 28-39.

141. Beckmann N., Kriegel H.P., Shneider R., Seeger B. The R*-tree: An efficient and robust access method for points and rectangles // In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1990. P. 322-331.

142. White D.A., Jain R. Similarity indexing with SS-tree // In Proceedings of the 24th International Conference on Very Large Data Bases, VLDB, 1998. P. 194-205.

143. Hjaltson G.R., Samet H. Ranking in spatial databases // Lecture Notes in Computer Science, 1995. V. 951 P. 83-95.

144. Joyce E. Endres The Total Systems Approach to Forms Automation // ЬПр://етефпзе.state.wi.us/static/forms/whitejiaper.htm