3086-1 (662787), страница 2
Текст из файла (страница 2)
Модели описания структуры текстовых и табличных документов
Модель описания структуры текстовых документов - дерево регулярного ортогонального чередования разбиений.
Традиционной для текстовых документов является следующая древовидная структура листа: лист разбит на текстовые блоки, называемые колонками, колонки разбиты на параграфы, параграфы состоят из слов, слова - из символов, символы - из одной или нескольких компонент связности.
Используемая в системе CRIPT структура описания листа представляет собой обобщение традиционной древовидной схемы. Существенными являются следующие особенности реального графа описания формата листа:
Рис. 2. Дерево колонок, соответствующее структуре листа, схематически изображенного на рис. 1a.
Для каждого нетерминального объекта (т.е. объекта, имеющего "дочерей"), сохраняется информация об относительном взаимном расположении его дочерей на листе, что позволяет в случае необходимости сохранить в выходном документе то же взаимное расположение структурных элементов текста в пределах иерархического блока более высокого уровня, что и в исходном документе. Предусмотрены, в частности, следующие варианты взаимного расположения объектов: упорядочение по горизонтали, упорядочение по вертикали, матричный порядок, индексный порядок (одна из дочерей является индексом другой), неупорядоченное расположение.
Рис.1 Последовательные шаги расщепления листа на колонки по методу "сверху вниз"
Колонки образуют иерархическую структуру, т.е. каждая колонка может быть разбита на подколонки, причем на соседних уровнях ориентация разделяющих колонки линий меняется на ортогональную (так, например, если на некотором уровне колонки могут быть разделены горизонталями, то на следующем уровне они разделяются вертикалями). Именно поэтому такая модель описания структуры документов была названа деревом регулярного ортогонального чередования разбиений. На рис. 1 приведена схема, поясняющая данную модель. На рис. 1,a схематически показано расположение колонок на листе, на рис. 1,b-d - последовательные шаги расщепления, на рис. 2 - построенное "дерево регулярного ортогонального чередования разбиений"
Рис. 3. Примеры таблиц иерархической структуры: a) Таблица с горизонтальной иерархией; b) Таблица с вертикальной иерархией; c) Таблица с горизонтальной и вертикальной иерархией; d) Таблица с двумя уровнями горизонтальной иерархии.
Строки могут быть разбиты на подстроки, различающиеся какими-то свойствами (например, шрифтом).
Объекты иерархической структуры могут иметь дочерей как на следующем по порядку иерархическом уровне (например, дочерьми параграфа могут быть строки), так и на более низком иерархическом уровне (например, дочерьми колонки могут быть символы).
Модель описания структуры табличных форм - обобщенная модель связанных ортогональных иерархий;
Рассмотрим особенности табличных структур, определяющие необходимость использования специальной модели для их описания:
Правильное понимание таблицы читателем невозможно без учета информации о взаимном расположении строк, колонок и ячеек таблицы. Поэтому при автоматизированном распознавании табличных форм необходимо в выходном документе сохранить то же взаимное расположение этих структурных табличных элементов, что и в исходной таблице.
Строки и колонки таблиц могут иметь иерархическую структуру (рис. 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.
6.M. Thaller. The Processing of Manuscripts, Images and Manuscripts in Historical Computing, Goettingen, 1992; T. Kruyt, J. van der Voort van der Kleij. Converting the Historical Dictionary of Dutch to Electronic Form, Optical Character Recognitionin The Historical Discipline., Goettingen, 1993; 22. L. Borodkin, V. Lazarev, E. Zlobin, Applications of OCR in Russian Historical Sources: a Comparison of various programs, Optical Character Recognition in The Historical Discipline, Goettingen, 1993.
7.V. Klyahzkin, E. Shchepin, K. Zingerman. Application of hierarchical methods of cluster analysis to the printedtext structure recognition, Shape, Structure, and Pattern Recognition, Dov Dori and Alfred Bruckstein, Eds. World Scientific, 1995; V. Klyahzkin, E. Shchepin, K. Zingerman. Hierarchical analysis of multi-column texts, Pattern Recognition and Image Analysis, Vol.5, No.1, 1995, Interperiodica,pp. 1-12; В.М. Кляцкин. Иерархический кластер- анализ многоколонных текстов, Одесса, 1994, Труды V Международной конференции (Статистический и дискретный анализ данных и экспертные оценки), Изд-во Одесского политехнического университета, стр. 132-134.
8.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
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
