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

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

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

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

Логическая структура документа — структурное представление содержимого документа в виде определённых элементов, которое учитывает их роль в документе, логические взаимосвязи между ними, порядок чтения документа пользователем и т. д. [Зуев, 1999], [Song, 2003], [Зуев, 1996].

Для исследования логической структуры документов, прежде всего, выделим основные элементы, которые составляют логическую структуру. Устройство логической структуры можно представить следующим образом: документ делится на потоки. Как правило, существует один основной поток (рис. 1). Помимо него могут встречаться дополнительные потоки: сноски, врезки, колонтитулы, подписи, и т. д. Текст потоков состоит из абзацев, абзац — из строк, строка — из символов.

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

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

Таким образом, логическая структура документа представлена в виде дерева, корнем дерева является сам документ, далее идёт ветвление: секция -> поток -> абзац -> строка. Подобное представление структуры является иерархическим и может быть изображено в виде дерева, корнем дерева является сам документ. Рис. 2 показывает дерево логической структуры, построенное для примера страницы, изображенной на Рис. 1. Деление на абзацы и строки для упрощения схемы показано только на примере первой сноски, для остальных потоков оно аналогичное. Каждый колонтитул или сноска является отдельным потоком.

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

Рис. 1. Элементы логической структуры

программный текстовый разметка Основное представление о логической структуре можно получить из графических характеристик тех или иных элементов документа [Rangoni, 2006], [Hu, 1993].

Такие графические характеристики могут быть:

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

содержать шрифтовое оформление (гарнитура, размер, тип, начертание и т. д.);

связаны с текстовой составляющей элементов логической структуры (ключевые слова, такие как «Рисунок», «Формула», «Глава»; символы из ограниченного словаря, такие как номера страниц, дата, знак «§», и т. п.).

Рис. 2. Дерево логической структуры

Характерные ошибки при распознавании логической структуры документа.

Задача системы распознавания подобрать разметку документа таким образом, чтобы сгенерированный документ как можно меньше отличался от оригинала (документа на изображении). Чтобы иметь возможность сравнивать распознанный документ с оригиналом, для каждого документа, который используется для тестирования системы, вручную создаётся эталонная разметка. Любое несоответствие логической структуры, полученной при распознавании образца, и структуры эталонной разметки расценивается, как ошибка.

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

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

В левой колонке таблицы 1 приведены ошибки, которые используются в системе ABBYY Fine Reader для оценки качества распознавания логической структуры документа, с добавлением ещё двух видов ошибок, которые исправили недостатки существовавшего подхода (были добавлены ошибки «разрыв колонтитула» и «неверная роль потока»).

Табл. 1.

Ошибки были разделены на три группы по степени сложности и в соответствии с группой им были назначены веса 0,5, 1 и 1,5. Сложность ошибки оценивалась на основе времени, которое понадобится пользователю на её исправление, время оценивалось с помощью количества простых действий пользователя при исправлении ошибки.

Распределение весов для каждой ошибки показано в правой колонке таблицы 1. Вес для каждой группы увеличивается примерно пропорционально увеличению количества операций, необходимых для исправления ошибки. Выбранная оценка монотонна и аддитивна. Ошибка «разрыв колонтитула» специально была вынесена в отдельную группу, т.к. является не существенной. Дело в том, что при экспорте в текстовый редактор, например Word, две части колонтитула будут соединены в один нижний или верхний колонтитул, поэтому на этапе экспорта результатов эта ошибка исчезнет.

Были проведены эксперименты, заключающиеся в оценке результатов распознавания для двух версий Fine Reader — 9 и 11. В экспериментах участвовало 20 документов различного типа (отрывки из книг и журналов разного вида), различного размера (от 3 до 44 страниц) со сложной логической структурой, общее количество проанализированных страниц — 315. Документы выбирались таким образом, чтобы в них обязательно присутствовали в большом количестве разные виды дополнительных потоков. Ниже приведена таблица 2 распределения ошибок для двух вариантов распознавания разными версиями Fine Reader’а на примере документа, содержащего 20 страниц из книги с большим количеством врезок и колонтитулов.

Табл. 2.

Как видно из таблицы 2, Fine Reader 11 совершил больше ошибок при распознавании, но в целом документ оказался распознанным лучше, чем 9-ой версией Fine Reader’а.

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

Данная оценка не очень удобна для сравнения, насколько сложена логическая структура того или иного документа, если сравнивать приходится документы с разным количеством страниц. Хотя в целом структура большого документа (например, книги) может быть гораздо проще, чем структура короткого (например, журнала), из-за большого количества страниц книга может получить оценку намного большую, чем журнал.

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

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

Например, чтобы оценить качество нахождения секций документа, суммируется количество ошибок «Потерянна секция» и «Найдена лишняя секция» и делится на количество секций в эталонной разметке документа. Таким образом, этот вид оценки помогает более детально оценивать изменения, происходящие в системе распознавания от версии к версии. В нижних строках таблицы 2 отображены все виды оценок для двух вариантов распознавания.

Для более достоверного сравнения качества распознавания логической структуры двумя версиями системы сравнение следует проводить не на одном документе. Поэтому для эксперимента были отобраны 20 разных документов, общее количество страниц — 315. Сравнение проводилось для суммарного количества ошибок каждого типа. Общий результат качества приведён в таблице 3.

Табл. 3.

Эксперименты показали, что 11-ая версия программы справляется с распознаванием логической структуры значительно лучше 9-ой. Из таблицы хорошо видно, что в Fine Reader 11 произведены улучшения по каждому показателю, но также можно отметить, что, например, ошибок связанных с нахождением секций, хотя и стало меньше, но их по-прежнему очень много. Так же система ещё довольно часто ошибается при распределении текста по потокам определении их роли.

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

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

Табл. 4.

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

• 1. Зуев К. А., Технология анализа документа // Компьютерная хроника, 1996 г.
• 2. Зуев К. А., Система идентификации структуры печатных документов // Дис. канд. тех. наук. — М.: МГУЛ, Москва, 1999.
• 3. Hu T., Ingold R. A mixed approach toward an efficient logical structure recognition from document images // ELECTRONIC PUBLISHING, VOL. 6(4), 1993.
• 4. Rangoni Y., Belaid A. Document Logical Structure Analysis Based on Perceptive Cycles // Springer-Verlag Berlin Heidelberg, 2006.
• 5. Song M., Rosenfeld A., Kanunugo T. Document Structure Analysis Algorithms: A Literature Survey // Proc. SPIE Electronic Imaging, VOL. 5010, 2003.