Структурные методы распознавания сложноорганизованных исторических табличных форм (стр. 2 из 3)

В работе А. Маквейг рассмотрены вопросы, связанные с автоматизированным чтением таблиц, содержащих статистическую информацию о семейном положении людей в различных районах Ирландии в XIX-XX вв [17]. Обработка изображений выполнялась OCR-системой ProLector. Полученный в результате работы OCR текстовый файл подвергался дополнительной программной обработке с целью выявления ошибок (такая обработка оказалась возможной, поскольку таблицы содержали контрольные суммы), затем эти ошибки исправлялись вручную и осуществлялся ввод исправленной информации в базу данных. Исходные таблицы имеют сложную иерархическую структуру, столбцы этих таблиц имеют различную ширину и разделены вертикальными линиями. Строки, содержащие контрольные суммы, выделены горизонтальными линиями. Автор отмечает, что разделительные линии имели неодинаковую толщину, что приводило к дополнительным затруднениям при их удалении средствами системы ProLector: после удаления линий оставались помехи. Автор указывает также на проблемы, связанные с сохранением структуры таблицы в текстовом файле, сформированном OCR-системой.

В работе М. Олсена рассмотрено применение OCR к обработке списка налогообложения начала XX века в одном из городов провинции Нью-Брунсвик (Канада) [18]. На рис. 2 этой статьи приведено изображение страницы исходного документа, а в табл. 3 - результаты обработки изображения системой Kurzweil (после дополнительной корректировки). Как видно из рис. 2, исходная таблица имеет простую структуру, колонки ее разделены вертикальными линиями, имеющими многочисленные разрывы. Автор отмечает, что OCR-система Kurzweil испытывает некоторые трудности при обработке вертикальных линий, вследствие чего возникают ошибки, связанные с неправильным размещением данных в колонках.

Авторы всех вышеупомянутых работ по применению OCR при выполнении исторических проектов отмечают, что использование OCR-систем для автоматизированного ввода в ЭВМ документов, содержащих таблицы, позволило значительно сэкономить время по сравнению с ручным вводом данных в ЭВМ (перенабивкой). Вместе с тем, значительные усилия потребовались для поиска и исправления ошибок. Одной из причин появления ошибок явилось отсутствие достаточно мощных средств описания и распознавания структуры таблиц в использованных OCR- системах.

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

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

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

Используемая в системе 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) подсистемы постобработки.