Содержание к диссертации
Введение
ГЛАВА 1. Обзор использования таблиц в информационных системах 7
1.1. Таблица и ее функции 7
1.2. Использование таблиц
1.3. Модели таблиц 18
1.4. Основные выводы обзора 29
ГЛАВА 2. Модель табличного документа 32
2.1. Концептуальная модель таблицы 32
2.2. Математическая модель таблицы 36
2.2.1. Модель носителей визуального представления таблицы 36
2.2.2. Информационные функции 38
2.2.3. Матричная модель таблицы 41
2.2.4. Модели визуализации и содержание таблицы. 44
2.2.5. Табличный информационный объект 58
2.3. Обработка таблиц 66
2.4. Выводы 69
ГЛАВА 3. Методы решения задач оптического ввода табличных документов 70
3.1. Анализ графического образа страницы документа при потоковом вводе табличных документов 70
3.1.1. Особенности задачи сегментации образа страницы при потоковом вводе табличных документов 70
3.1.2. MST-KD алгоритм быстрого построения минимального остова на множестве точек в псевдометрическом k-мерном пространстве 74
3.1.3. Построение минимального остовного дерева на множестве МОП компонент связности... 80
3.1.4. Сегментация изображения на основе MST, построенного на множестве МОП компонент связности 86
3.2. Компонента вычисления и проверки табличных документов 89
3.2.1. Формальная модель обработки событий 90
3.2.2. Граф зависимостей обработки событий 94
3.3. Выводы 95
Глава 4. Система массового ввода табличных документов 97
4.1. Программные компоненты решения типовых задача обработки таблиц 97
4.1.1. Типовые технологические линии обработки табличных документов 97
4.1.2. Оптический ввод табличных документов 103
4.1.3. Редактирование таблиц 109
4.2. Система ввода документов cognitive forms 113
4.2.1. Общее описание и основные модули технологической линии 113
4.2.2. Пример применения системы Cognitive Forms для решения задач массового ввода документов 116
Заключение 119
Список использованных источников
- Использование таблиц
- Модель носителей визуального представления таблицы
- Особенности задачи сегментации образа страницы при потоковом вводе табличных документов
- Типовые технологические линии обработки табличных документов
Введение к работе
Компактное и наглядное представление информации в табличной форме настолько
прочно вошло в нашу повседневную жизнь, что представляется естественным и простым
для восприятия. Таблицы встречаются на страницах газет и журналов, многие
стандартные формы документов содержат таблицы или являются полностью табличным.
Бухгалтерские, финансовые и статистические документы, научная и справочная
литература - все они содержат таблицы. При ручном вводе операторы выполняют
однообразную последовательность действий: бросают взгляд на очередную страницу,
находят и читают текст заполнения, а потом быстро набирают его на клавиатуре. По
сравнению с обычными формами таблицы могут содержать на порядок больше полей.
Монотонная структура текста, а так же необходимость соблюдения и воспроизведения
этой структуры при вводе - все это требует дополнительного напряжения от оператора,
приводит к быстрой утомляемости и ошибкам. Как альтернатива ручному вводу
существуют технологии автоматизированного ввода документов.
Начавшийся несколько десятков лет назад процесс замены бумажных документов
электронными продолжается и по сей день, при этом наиболее жизнеспособными и
эффективными показали себя смешанные системы. Возможность простого перехода от
физического представления к информационному и обратно на различных этапах
жизненного цикла документа позволяет использовать естественные преимущества
каждого из типов представления. Большую роль в функционировании таких смешанных
систем играют системы автоматического и полуавтоматического ввода бумажных
документов, предоставляющие альтернативу ручному вводу. Подобные технологии
обладают рядом явных преимуществ: современные модели сканеров позволяют вводить
до 200 страниц в минуту, а программы оптического распознавания текста круглосуточно
"читают" без устали по несколько сотен символов в секунду.
К настоящему времени накопились огромные объемы бумажных документов,
перевод которых в цифровой вид при помощи технологий сканирования и распознавания
позволяет выиграть в стоимости и качестве по сравнению с ручным вводом. Другим
существенным преимуществом распознавания является возможность организации доступа
к образу оригинала: корректно идентифицированный поток документов, включающий
распознанную информацию и графические образы, может составлять основу электронного
5 архива, представляющего функции быстрого поиска документа, извлечения, пересылки и печати графического образа документа (по качеству не уступающего ксерокопии). Развитие глобальных компьютерных сетей упрощают организацию удаленного доступа к таким архивам, что выдвигает это технологическое преимущество на первый план.
Все активнее просматривается тенденция к объединению систем бумажного и электронного документооборота в единые комплексы, где ввод и ввод табличных документов играет главенствующую роль. Актуальной задачей построения комплексных систем работы с табличными документами является построение единого подхода к таблице во всех ее представлениях и создание модели, позволяющей описывать табличные документы во всех процессах обработки.
Предметом данной работы является анализ систем обработки табличных документов, для выявления общности, обеспечивающей конструктивную основу решения задач ввода/вывода и распознавания таблиц в рамках различных систем. В работе проводится исследование и разработка методологических основ, а также конкретных моделей, методов и средств для решения следующих задач:
моделирования таблиц как информационных объектов, а так же рассмотрения этой модели с точки зрения различных задач ввода/вывода и распознавания,
автоматизации логического контроля достоверности ввода и сохранения целостности табличного документа;
автоматической идентификации, восстановления структуры и распознавания таблиц в задачах ввода документов.
Целью данной работы является построение формальной модели таблицы, которая бы позволяла описать основные процессы ввода/вывода таблиц и органично связать с построением методов идентификации и определения структуры табличных объектов на изображениях документов в рамках разработанной концепции таблицы.
Задача состоит в построении модели, которая позволяет описывать табличные документы в процессах:
ввода/вывода таблиц на дисплей монитора;
автоматического (полуавтоматического) распознавания таблиц и верификации результатов распознавания;
табличных расчетов;
вывода таблиц на бумагу.
Новизна предложенного в работе подхода состоит, в разработке универсальной структурно ориентированной модели таблицы, используемой для решения различных задач и абстрагированной от конкретных методов обработки. В отличие от существующих подходов, как правило, ориентированных либо на реляционное представление данных, либо на представление в экранном или бумажном виде, предложенная модель позволяет отражать в структуре таблицы исходную модель предметной области, а построение и анализ плоских представлений табличной информации производить уже с учетом этой структуры. Такой подход позволяет адекватно описывать множественность представлений при инвариантности внутренних структур и данных, а так же объединять процессы ввода/вывода. Ориентированность модели на базовые логические структуры таблицы при независимости модели от формы представления и особенностей конкретных методов обработки обеспечивает ее открытость для разработки, расширения и специализации.
В рамках построения системы ввода табличных документов предложена эффективная реализация анализа изображения в задачах сегментации образов структурированных документов. Кроме того, предложен подход к реализации объектно-событийной системы с прогнозируемым поведением для редактирования таблиц.
Основные результаты данной работы доложены, обсуждены и получили одобрение специалистов на XLIX научной конференции МФТИ (Долгопрудный, 2006 г.), научных семинарах кафедры прикладной экономики МФТИ в 2003-2006 гг., лаборатории методов искусственного интеллекта ИСА РАН в 2003-2007 гг., отдела систем математического обеспечения ВЦ РАН в 2007 г. а также на научно-технологических семинарах в компании ООО "Когнитивные технологии" 2003-2007 гг.
По теме диссертации опубликовано три работы, одна из них в соавторстве ([1]-[3]).
Использование таблиц и по
Перекрестные ( :№.ч;;4аЪ отчеты (Рисунок І.И).6} ВЛІЄІОТ табличную структуру, арл-чем заранее неизвестно, сколько етров. н столбцов будет содержать таблица. Значения ас-лей БД :OCJ:U JSь; у«JTCК ДДЙ формирования заголовков сірок ЇЇ столбцов. Возможно определение составйьж загодовхож Стандартной ло можноотыо является добайгіеїте опционально шц;тргшнйшмх строк/столбцов аро.межутотеьгх итогов.
Ограниченность чшяа стандартных иарвангоа табличных отчетов и саязаешая с ; гим необходвмость низкоуровневого программировании нестандартны?; форм является распространенным ограничением систем генерации отчетон. Поиски рентний приво.здт к различит! подходам. Оярелеление абстрактных ш к:окоуроьне?шх онераний над матрицами \5\\ позволяет оннеатв пронесе преобразования результата «ыоорки т ЬД к требуемому виду. Другим вариантом решения является представления всего отчета в виде сложной объектной сущности [52].
Обратная выводу задача ввода информации решается программными средствами класса OCR. За последние годы сканирующее оборудование стало стандартным элементом офисного или домашнего компьютера. Сфера применения систем оптического распознавания непрерывно расширяется, охватывая все больше различных областей человеческой деятельности. Рост вычислительных возможностей персональных компьютеров и разработка новых алгоритмов позволяют обрабатывать все более сложные типы документы. Выделение структурированной информации из электронных документов так же используется для ввода. Исходным носителем таблицы в процессе распознавания и разбора таблиц являются изображения, текстовые файлы (ASCII), HTML, PDF и прочие электронные документы
Основная задача широко распространенных программ распознавания [53]-[55] состоит в восстановлении размещения и содержания текста на странице, после чего результаты экспортируются в формат текстового или табличного процессора. Считается, что чем ближе внешний вид результатов распознавания к исходному документу, тем лучше работает программа.
Для правильной интерпретации структурированных документов необходимо сначала выделить элементы структуры (колонки и блоки в публикациях, графы, строки и ячейки в таблицах) и только после этого распознавать отдельные символы этих элементов [56]. Если извлеченная информация далее обрабатывается как структурированная, то результаты распознавания обязательно требуют дополнительной интерпретации.
Лежащая в основе OCR системы модель таблицы играет ключевую роль, так как именно она явно или неявно определяют границы применимости системы. Отсутствие общих подходов к разбору таблиц приводит к тому, что решения по вводу данных с помощью распознавания [57], [58], [59] получаются узкоспециализированные и могут обрабатывать только заданный тип документов.
Большая доля ранних исследований в области использования таблиц посвящена либо формированию таблиц, либо извлечению табличных данных из отсканированных изображений и текстовых файлов. В настоящее время интерес сместился в сторону унифицированной обработки как бумажных, так и электронных документов [60]-[64]. Развитие Интернета и публикация больших объемов информации в различных форматах (HTML, XML) снова обострили проблему интерпретации и обработки сложно структурированных данных.
Модели таблиц
Наиболее общим способом визуального представления структурированной информации являются формы [4], а таблицы являются важным их элементом или типом. Теоретическая проблема корректного перевода сложных структур на плоские носители, а также ввод и вывод документов в зарубежной литературе рассматривается достаточно примитивно и узконаправленно в рамках конкретных прикладных задач. В отечественных теоретических работах данная проблема рассматривается более полно и теоретически обоснованно [65]-[68].
Современная теория описания таблиц [69]-[72] выделяет не менее двух уровней описания: физически и логический. Физическая структура таблицы описывает расположение частей таблицы на носителе (изображение, текстовый файл, документ). Логическая структура таблицы определяет типы этих частей, их назначения и соотношения. Наиболее абстрактный уровень логического описания определяет структуру представленных в таблице данных и способ доступа к ним.
Вариант размещения данных таблицы на носителе будем называть макетом таблицы. Макет определяет взаимное расположение отдельных элементов таблицы (упорядочиванием) и типографические атрибуты. Упорядочивание элементов передает логическую структуру таблицы. Типографические атрибуты таблицы определяют форматы всех элементов таблицы, а так же дополнительные графические элементы, например, линии. Разграфка, выравнивания, отступы и другие особенности вывода используются для визуализации структуры таблицы. Детальный обзор работ по проблемам формирования и печати таблиц приведен в [69].
Модель носителей визуального представления таблицы
Рассмотрим особенности вывода на бумагу, которая является примером статического конечного носителя. Конечный статический носитель характеризуется ограниченными размерами и статичностью изображения. На один и тот же носитель таблица может быть выведена только один раз. Если таблица не может быть полностью выведена на один носитель, то невозможно динамически менять отображаемый фрагмент таблицы, поэтому для вывода на статический конечный носитель используется разбиение таблицы на фрагменты, каждый из которых отображается на своей странице. Расширим координаты прямоугольных объектов за счет добавления номера страницы nPAGE RECT(xL,yT,xR,yB,nPA0E). (2.19)
Ограничение по размеру, которое задается прямоугольником области вывода, реализуется следующим образом: все прямоугольники лежащие полностью вне области вывода не отображаются, все пересекающиеся с областью вывода прямоугольники отображаются в пределах области вывода.
Детальное изучение дополнительных ограничений, вариантов постановки и методов решения задачи вывода таблицы на конечный статический носитель выходит за рамки диссертации и далее рассматриваться не будет.
Информациоппые функции
Для дальнейших рассуждений воспользуется теорией информационных функций [6]. Будем говорить, что информационный объект описывается значениями информационных переменных. Переменные характеризуются своими обозначениями и своими множествами значений. Значениями информационных переменных могут быть не только числа, но и текст, произвольные последовательности символов, графические образы.
Значение скалярной переменной является неделимой информационной сущностью и рассматривается как атомарный объект. Далее информационные переменные будем обозначать буквами греческого алфавита с нижними индексами. Для обозначения значения переменной rj будем использовать верхний скобочный индекс г), . В качестве индекса произвольного значения будем использовать символ "звездочка" (то есть записывать Tjj ). Для выделения допускающих текстовое представление значений переменных будем использовать курсивный шрифт Courier. Совокупность значений переменной состоит из всех значений, принимаемых информационной переменной для заданного ИО. В отличие от множества значений, которое будем обозначать Y(r,), совокупность значений может содержать повторяющиеся значения и обозначается так же, как и сама переменная. Принадлежность значения переменой совокупности значений определим так ГІ } є n, = Зі є N: л! = п!и (2-20) В этих обозначениях для скалярной переменной т совокупность значений может быть записана, например, следующим образом =( ni2,,rf), (2.21) где л{ = Иванов г2) = Петров Г3 = Сидоров (2.22) В то же время для пола указанных сотрудников справедливо ті,0= (муж,муж,муж) ї(гі0) = {муж}. (2.23)
Значение переменной, которое допускает разложение на информационно подобные элементы, назовем множественным. Если переменная может принимать множественное значение, то будем называть саму переменную множественной. Множественная переменная может быть множеством или списком (т.е. запрещать или допускать наличие повторяющихся значений среди элементов разложения на информационно подобные элементы), при этом сама переменная рассматривается как скалярная переменная. Будем называть присоединенной переменную, содержащую скалярные значения, составляющие многозначное значение. Значение множественной переменной составляется из значений присоединенной переменной.
Кортеж, элементами которого являются информационные переменные, будем называть векторной информационной переменной и обозначать следующим образом I =у(л,5Л2 ) = {ЛнЛ2 г13)- (2-24)
Между векторной переменной и переменными-компонентами существует отношение типа вектор - компоненты. Множество значений векторной переменной суть множество кортежей значений компонент, при этом не все комбинации кортежей значений компонент обязаны присутствовать в множестве значений векторной переменной. Например г2 є (Алексей, Дмитрий,Петр) (2-25) т3 (Андреевич,Васильевич) (2.26) 4, = {[Иванов, Алексей, Васильевич), {Петров, Дмитрий, Андреевич-), (2.27) {Сидоров, Петр, Ва силь евичу)
Информационная функция определяет связи между информационными переменными. Совокупность значений переменных, над которыми определена функция, образуют область определения функции. Информационная функция может быть определена как явная зависимость одной переменной от набора других Л,=Ґ(Л2,-,ПКДР-ДМ)- (2-28) При неявной форме задания функции будем использовать следующую форму записи Р(л,,...,лД,-Дм)- (2-29)
Для общности будем считать, что в вырожденном случае информационная функция одной переменной определяет совокупность значений этой переменной.
Явная форма информационной функции вида (2.28) может рассматриваться как кортеж следующего вида {Пі,П2 -, .1І5-Лм} = {т1рТІ2.-!Лм.Лі,р-,і1ш1,-,тімда)- (2-30) Тогда множество значений явной информационной функции соответствует отношению в реляционном смысле.
Именование переменных является особым случаем информационной функции. С некоторой информационной переменной может быть связана именующая переменная, которая содержит именование идентифицируемой переменной. Идентифицируемую переменную будем называть существенной переменной, а именующую идентификатором. Идентификатор может быть определен только для любой переменной, и только взаимно однозначным образом.
Особенности задачи сегментации образа страницы при потоковом вводе табличных документов
На первых этапах оптического распознавания документов [123], [124] изображение "чистится", определятся угол наклона графического образа, привнесенного при сканировании, и производится сегментация. "Чистка" изображения может заключаться в удалении шума, мелких объектов или определении истинных границ страницы на изображении. Существенно, что "чистка" должна быть согласована с дальнейшими этапами.
После чистки производятся определение угла наклона и сегментация графического образа отсканированной страницы. Сегментация состоит в выделении на исходной матрице пикселей символов, слов, строк, абзацев, колонок и других элементов, из которых состоит распознаваемый документ. Выделенные объекты - текстовые фрагменты -являются входными данными для задач распознавания абзаца, строки и, наконец, распознавания символа. Далее результаты распознавания могут логически интерпретироваться (например, посредством поиска распознанных слов в словаре) и служить основой для форматирования финального электронного документа или поиска на документе специальных значимых частей, полей ввода данных. Процесс может носить многопроходный итеративный характер.
Итак, чтобы распознать документ нужно из нескольких миллионов пикселей, упорядоченных в строки и столбцы выделить однородные фрагменты, соответствующие абзацам, которые можно разрезать по горизонтали на строки, которые, в свою очередь, можно по вертикали разрезать на символы. Рассматриваемая проблема имеет почти пятидесятилетнюю историю, и за это время был предложен не один подход к решению задачи. Многие из методов могут с успехом применяться на одних классах документов и плохо применимы на других. Мы столкнулись с этой проблемой на практике, когда возникла необходимость программной реализации метода сегментации для распознавания стандартных форм документов. Двухпроходное заполнение, короткие строки, пересечения с линиями разграфки, штампы, печати, подписи, пометки на полях, бледная подсохшая лента матричного принтера, небольшой люфт в процессе протягивания страницы через автоподатчик и другие особенности усложняют задачу и представляют серьезную проблему для многих существующих методов. При этом может требоваться высокая точность: ведь полученный в результате сканирования графический образ такого делового документа подается на автоматическую обработку, где цена ошибочного распознавания реквизита документа весьма высока (например, при распознавании бухгалтерский или банковских документов).
Рассмотрим для сравнения пример образов стандартного бланка счета-фактуры (Рисунок 3.1.а) и страницы научно-популярной книги (Рисунок 3.1.6). На страницах книг и журнальных статей текст, как правило, сгруппирован в абзацы и колонки, а отдельно стоящие надписи скорее являются исключением. Разные типы документов и даже экземпляры одного типа могут существенно отличаться по наличию таких крупных структурных элементов. Практические исследования показали, что многие алгоритмы, показывающие хорошие результаты на плотно заполненных страницах, ведут себя неустойчиво или просто неприменимы к изображениям с редким заполнением, и наоборот. Книги и журналы чаще всего печатаются типографским способом, что позволяет при сканировании получить четкие изображения.
Жизнь бумажного документа подчинена собственным законам и к моменту сканирования на нем могут появиться дополнительные печати, штампы, подписи и надписи. Многие документы содержат фотографии, подписи и штампы, положение которых не всегда фиксировано или заранее определено. Так же возможно смазывание документа и появления на нем всевозможных загрязнений, пятен, и прочих дефектов. Изображения подобных документов содержат большое количество элементов не являющихся текстом или линиями разграфки, что может существенно усложнить задачу ввода.
Спектр применяемых для создания бумажных документов печатающих устройств достаточно широк. Одна и та же форма может быть полностью напечатана на матричном, струйном или лазерном принтере, печатной машинке или специализированном печатном устройстве (Рисунок 3.2 а-в, ж-и). Возможны варианты, когда в бланк типографского исполнения значения полей впечатываются одним из вышеперечисленных устройств. Наконец, любой документ может быть отксерокопирован или передан по факсу перед сканированием (Рисунок 3.2 г-е).
Типовые технологические линии обработки табличных документов
В рамках создания системы автоматического контроля ввода предложен метод формализации правил в терминах множеств событий (инициирующих и порождаемых). Опирающийся на такое описание, анализ графа зависимостей позволяет выявлять потенциально опасные места еще на этапе проектирования системы контроля логики заполнения документа. Выявленные потенциальные циклы могут быть проанализированы более, тщательно для принятия решения о пересмотре правил. Так же на основании этой модели можно строить безопасные системы интерактивного ввода информации с прогнозируемым поведением.
Описанные методы сегментации и анализа изображения, а так же методика обеспечения прогнозированного поведения объектно-событийной системы контроля правил заполнения нашли свое применение в системе распознавания табличных документов Cognitive Forms, которая будет описана в следующей главе. CMCT&WB массового ззеда табличнихдокументов 4Х Программные ШІШІЄЙШ pens шва ГНКОЗДЇХ задача обработки тя&ши В предыдущих главах работы рассматривались .вопросы мітделїфиьанкяг табличных ДОКУМЙІТЇЇЙ, методы нх рз лш:шаізз;пія и аерифвхашя. Праьткч йказ реализация перечисленных eospoco» таїш очражтше о системе массового ййода документов Cognitive І-огггн; [Ї21]. рафаботаккоя ари участий амора.
Тниоаме технологические ЛЇШШІ ііГіработки ТЙЇЇЛНЧИЬЇХ документов Рассмотрим несколько тшоаш ГЄХНОЛОПІЧЄСІЙЇХ .ІІЇАЇШЙ обработки табличних докумеитоь. Структура ЇЙ&ІІШЬІ »рв форм НРОІІЙ шш ЇЗҐШЗЧИОИ ЧЛІ:;И отчета (Рисунок 4.2} определяйся Еїйзиачелием разрабатываемого отчета и структуро!; ш;форм;щти мторая должна быт;.- к таблице аре.аетайдека. Si--. С помощью утилиты импорта схема БД загружается в экранный редактор для создания структуры табличного ИО, и переменные связываются с полями БД. На основании структуры в редакторе печатного макета пользователь определяет макет вывода и, если необходимо, дополнительную обработку данных в рамках модели таблицы. Зависимости и правила позволяют определить вычислимые данные и условное форматирование элементов отчета. Так же макет вывода может содержать указания о правилах формирования многостраничных таблиц в соответствии с заданной структурой. После завершения редактирования макета генератор табличной части отчета извлекает данные из указанных источников, связывается их и выводит по описанному шаблону для формирования таблицы. При необходимости производится разбиение на страницы, а идентифицирующие надписи, заголовки строк и столбцов повторяются. После завершения генерации табличная часть отчета может дополнительно редактироваться с помощью экранного редактора в специальном режиме.
Использование таблиц при формировании отчетов имеет следующие особенности: таблица может быть как самостоятельной формой, так и элементом составного отчета; пользователю важен набор средств визуального представления таблицы; формирование плоского представления должно гибко настраиваться с учетом особенностей устройства вывода (экран, ПУ) и носителя (ограниченность, многостраничность); объектом манипуляций пользователя является в первую очередь макет таблицы, который несет структурную информацию и дополняется описанием информационных связей, после формирования отчета редактирование таблицы возможно на уровне плоского представления средствами генератора отчета. Задача ввода в ИС большого объема документов является стандартной задачей бизнес систем [120],. С помощью систем массового ввода могут сокращаться расходы на организацию обработки следующих классов табличных документов: бухгалтерские документы (первичные и отчетные); статистические формы (первичные и отчетные); табличные анкеты исследований (маркетинг, медицина); стандартизованная нормативная документация.
Типичная организация технологической линии массового ввода табличных документов следует общей схеме ввода структурированных документов [120],[121] н представлена на следующем рисунке (Рисунок 4.3).
Похожие диссертации на Разработка моделей, методов и средств обработки табличных документов в информационных системах
