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

Строки и колонки таблиц могут иметь иерархическую структуру (рис. 3), причем иерархия может быть многоуровневой (рис. 3,d).

Колонки и горизонтальные блоки различных иерархических уровней в таблицах могут иметь заголовки. Ориентация текста в заголовках может быть как горизонтальной, так и вертикальной.

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

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

Чтобы выяснить, какая модель данных может быть использована для представления таблиц, рассмотрим сначала общепринятую в технической документации структуру таблиц. Обычно таблица состоит из шапки, может быть, боковика и так называемого "тела" таблицы (рис. 5), причем как шапка, так и боковик могут иметь иерархическую структуру (рис. 6). Модель такой таблицы может состоять из дерева горизонтальной иерархии, описывающего структуру боковика, дерева вертикальной иерархии, описывающего структуру шапки и связей между деревьями горизонтальной и вертикальной иерархий.

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

Общий алгоритм распознавания таблиц

Система распознавания табличных форм состоит из следующих основных компонент: 1) подсистемы предобработки; 2) табличного структуризатора; 3) подсистемы распознавания символов (OCR-систе-мы); 4) табличного форматизатора; 5) подсистемы постобработки.

OCR-система осуществляет распознавание текстовой информации на изображении (основа метода распознавания рассмотрена в работе[19].

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

Рассмотрим более подробно работу табличного структуризатора. Эта подсистема последовательно выполняет следующие действия: 1)обнаружение и удаление линий на растре; 2)автономную обработку линий; 3)автономную обработку текста; 4)распознавание структуры таблиц; 5)анализ ячеек таблицы.

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

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

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

идентификация горизонтальных линий, ограничивающих шапку;

глобальная контекстно-зависимая фильтрация линий;

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

контекстно-зависимая фильтрация компонент (обрывков линий и шума);

построение вертикальной иерархии (структуры колонок);

оценивание горизонтальной иерархии.

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

Заключение

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

Авторами предложена достаточно универсальная структурная модель связанных иерархий, пригодная для описания широкого класса текстовых документов, табличных форм и бланков. В работе описывается основанная на модели связанных иерархий методология распознавания табличных структур. Данная методология была положена в основу разработанного в рамках OCR-системы Cript универсального текстово-табличного структуризатора.

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

Авторы выражают признательность А.В. Тюленеву и Л.И. Бородкину, благодаря которым во многом и состоялась данная статья.

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

1.OCR (Optical Character Recognition) - оптическое распознавание образов, Cript - одна из эффективных отечественных OCR-систем (Прим. ред.)

2.L. O'Gorman, "The document spectrum for page layout analysis", IEEE Journal on Pattern Analysis and Machine Intelligence, vol. 15, no. 11, p. 1162-1173 ,1993; M. Krishnamoorthy, G. Nagy, S. Seth, M. Viswanathan,"Syntactic segmentation and labelling of digitized pages from technical journals", IEEE Journal on Pattern Analysis and Machine Intelligence, vol.15, no.7, p.737-747, 1993; G. Nagy, S. Seth, M. Viswanathan, A prototype document image analysis system for technical journals, Computer, no.7, p.10-21, 1992.

3.L. O'Gorman, The document spectrum for page layout analysis, IEEE Journal on Pattern Analysis and Machine Intelligence, vol. 15, no. 11, p. 1162-1173 ,1993

4.H.S. Baird, K. Thompson, Reading Chess, Proc. of Workshop on ComputerVision, Washington, 1987.

5.V. Poulian d'Andecy, J. Camillerapp, I. Lemplumey, Kalman Filtering for Segment Detection: Application to Music Scores Analysis, Proc. IAPR 12-th Intern. Conf. on Pattern Recognition, Los Alamos,1994. - v.1.