Синтаксический подход к задачам пост-обработки нечетко распознанного текста - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Коммуникативный подход к лингвистическому комментированию художественного... 1 43.19kb.
Для обработки нижеследующего текста с использованием команды Поиск... 1 99.89kb.
«Перспектива и развитие» 1 80.96kb.
Учебный стенд для обработки звука 1 77.94kb.
[1]анализ методов обработки текста 3 1 Регулярные выражения 3 10 819.03kb.
[1]анализ методов обработки текста 3 1 Регулярные выражения 3 10 807.73kb.
Интегрированный урок русского языка и литературы в 9 классе (2 часа) 1 72.83kb.
Кредо №79 (февраль 2002 г.) 9 613.62kb.
Пост до полудня 8 Янв 2013 Вт Уход Шри Девананды Пандита Пост Сапхала... 1 100.17kb.
Пост до полудня 8 Янв 2013 Вт Пост Сапхала Экадаши 1 46.69kb.
Пост. Пр-ва РФ №18 от 10. 01. 09г. (отмененные) Пост. Пр-ва РФ №395... 1 25.15kb.
Концепции понимания правоотношений в Интернет 1 80.25kb.
Направления изучения представлений о справедливости 1 202.17kb.

Синтаксический подход к задачам пост-обработки нечетко распознанного текста - страница №1/1

Синтаксический подход к задачам пост-обработки нечетко

распознанного текста
Шоломов Д.Л.

В работе рассматривается синтаксический подход к задачам интерпретации и нормализации синтаксических текстовых конструкций на стадии пост-обработки распознанного текста. Такого рода задачи возникают при распознавании текстовых полей ввода на формах и структурированных документах. В работе рассматривается постановка задачи интерпретации нечетко распознанного текста, область применения синтаксического подхода, приводятся примеры реализации алгоритмов в системах оптического распознавания. Качественные оценки синтаксических алгоритмов приводятся на примере задачи распознавания почтового адреса.
1. Введение
В настоящее время в сфере информационных технологий широко используются системы идентификации и распознавания структурированных документов и форм [1], [8], [10], [14]. Формы состоят из постоянных (статических) элементов и элементов, меняющихся от формы к форме. Линии, статические тексты и картинки относятся к постоянным элементам, текстовые поля ввода, чекбоксы, печати, штрих коды – к меняющимся. Часто поля ввода имеют определенную синтаксическую структуру, например Почтовый адрес, Наименование организации, дата рождения и т.д. Работы [6], [7], [8], [10], [11] непосредственно посвящены распознаванию определенных типов полей. Синтаксическая структура полей может иметь различную степень жесткости. В зависимости от этого структура может быть описана различными способами и применяются различные методы контекстной пост-обработки [12]. Часто обычные алгоритмы распознавания 'гладкого' текста дают неудовлетворительные результаты при распознавании текстовых полей ввода из-за таких факторов как широкий алфавит, большое количество пунктуации, специфические сокращения и акронимы. Наряду с этим требования к качеству и надежности распознавания полей ввода в реальных задачах ввода форм довольно высокие и не могут быть удовлетворены обычными алгоритмами. Таким образом необходимо использовать подходы, в которых алгоритм располагает информацией о структуре поля. В данной работе описан так называемый синтаксический подход, в котором структура поля задается посредством синтаксических диаграмм. Данный подход применим к широкому кругу полей частично либо полностью описываемых синтаксическими диаграммами.
2. Задача пост-обработки
Процесс распознавания формы обычно состоит из следующих этапов:

  1. Предварительная обработка изображения формы и выделение графических примитивов [17]

  2. Автоматическое определение шаблона формы и локализация текстовых полей ввода [16], [17]

  3. Сегментация полей ввода и распознавание символов [6], [13], [15]

  4. Специфическая пост-обработка результатов распознавания поля.

В некоторых OCR системах стадии 3 и 4 выполняются одновременно, сегментация текста и распознавание символов производится под управлением

контекстно-зависимого интерпретатора [6].

На стадии специфичной пост-обработки предварительные результаты распознавания уже получены и расположены в так называемой Сети Альтернатив Распознавания (АР-сети). Пример АР-сети изображен на Рис. 1. Наличие предварительных результатов распознавания с возможностью последующей неоднозначной трактовки означает то, что текст распознан нечетко.



Рис 1. Пример АР-сети.
Вершины АР-сети соответствуют альтернативам распознавания символов; ребра соответствуют оценкам перехода от одной альтернативы к другой. Начальная и конечная вершины обозначаются плюсом и минусом соответственно. АР-сеть содержит информацию о сегментации текстового поля и об оценках распознанных символов. Каждый путь через АР-сеть соответствует некоторому текстовому значению, полученному конкатенацией символов соответствующих вершинам сети, принадлежащим данному пути. Наша задача сводится к нахождению оптимального пути в АР-сети с точки зрения оценок распознавания символов и соответствия структуре поля. Часто необходимо привести распознанный текст к нормальной форме. Практически всегда необходимо оценить степень надежности распознанного значения и локализовать его ненадежные фрагменты. Синтаксический подход допускает OCR, ICR распознавание.
3. Синтаксический подход в целом
Известные подходы контекстной пост-обработки включают статистические методы [2], [3], [4], такие как N-грамы и СММ, лингвистические методы и методы, использующие нейронные сети. Нередко такого рода методы не подходят для распознавания полей, которые не являются словарными или текстом на естественном языке, где структура либо слишком жесткая, либо излишне свободная. В подходах использующих выделение лексических признаков с дальнейшей классификацией при помощи нейронной сети недостаточное внимание уделяется синтаксису поля, порядку слов и взаимосвязями между ними.


Рис 2. Синтаксическая диаграмма даты.

При распознавании таких полей, как Почтовый адрес, Наименование организации и Сумма прописью на банковских документах удобно и оправданно задавать синтаксис поля при помощи синтаксических диаграмм СД, см. Рис.2, или грамматик в форме Бэкуса-Наура [5].

Подходы такого рода используются в распознавании речи и технике компилирования [5]. Действительно, задачи схожи – имеется линейный объект, такой как речевой поток или строка текста, интерпретируемый в соответствии с определенной грамматикой. В случае пост-обработки распознанного текста потоком является линейная АР-сеть или АР-цепь – набор знакомест с альтернативами распознавания (Рис. 3). Грамматика задается синтаксической диаграммой. Т.к. при печатном и рукопечатном распознавании текст хорошо сегментируется, результаты распознавания хорошо представимы АР-цепью.



Рис 3. Пример АР-цепи.
Удобно представлять АР-цепь в виде АР-матрицы (см. Рис. 4), Ячейки матрицы содержат альтернативы символов вместе с оценкой распознавания символа. Подразумевается, что любые две ячейки в соседних столбцах соединены ребром перехода. Оценка перехода содержится в правой ячейке.



Рис 4. Пример АР-матрицы
Задача пост-обработки заключается в нахождении оптимального пути в АР-сети, который в то же время соответствует синтаксической диаграмме. Процедура нахождения оптимального пути – довольно сложная задача оптимизации. АР-сеть и синтаксическая диаграмма могут состоять из сотен вершин, среди которых могут встречаться тяжеловесные словарные вершины. Например, такие словарные вершины, как Улицы и Города могут состоять из десятков тысяч элементов. Поэтому алгоритмы должны удовлетворять разумным требованиям к скорости. В нашей реализации алгоритма использует ряд оптимизационных методов, таких как итеративная сегментация АР-цепи и кэширование результатов отображения вершин СД на АР-цепь.

Синтаксическая пост-обработка проводится в соответствии со следующей блок-схемой (см. Рис 5):





Рис 5. Синтаксической пост-обработка

(Блок-схема верхнего уровня)

Процесс синтаксической пост-обработки состоит из следующих этапов:



  1. Инициализация тяжеловесных вершин СД, таких, как словарные вершины для уменьшения числа слов-кандидатов. Остаются только те слова, которые отображаются на АР-цепь с положительной оценкой. Также производится разметка АР-цепи, информация о разметке сохраняется в специальном хранилище.

  2. Выбор разрезов в АР-цепи. Обычно начальный набор разрезов соответствует пробелам, пунктуации и символам, распознанным с низкой оценкой. Это позволяет получить значительный выигрыш по времени в случаях хорошей сегментации.

  3. Поиск оптимального пути в АР-цепи (ОП-процедура). Оптимальный путь должен укладывается в СД. ОП-процедура основана на технике динамического программирования и имеет сложность , где N – число разрезов, I – число ребер SD, С – верхняя оценка времени отображения вершины СД на фрагмент АР-цепи. Алгоритм ОП-процедуры рассмотрен подробнее в следующем параграфе. В случае, если путь не найден на данном множестве разрезов, множество разрезов расширяется и оптимальный путь ищется на этом расширенном множестве.

  4. Перераспознавание некоторых вершин СД принадлежащих оптимальному пути на урезанном алфавите. Это значительно улучшает качество и надежность распознавания. Например, если неправильно распознать лишь одну цифру номера дома в почтовом адресе, письмо не попадет к адресату. Перераспознавание часто используется на числовых вершинах СД, предварительно распознанных на смешанном численно-буквенном алфавите.

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

На самом деле, в существующих реализациях алгоритмов ОП-процедуры ищется несколько путей- кандидатов с наилучшими оценками. Решение о том, какой путь в действительности наилучший выносится на финальной стадии пост-обработки. Например, когда получены пути-кандидаты для почтового адреса, мы можем проверить каждого кандидата в базе данных адресов и выбрать корректный. Корректный кандидат может и не иметь максимальную оценку после ОП-процедуры. Для простоты ОП-процедура, описанная ниже находит только один оптимальный путь.
4. ОП-процедура
В данной секции ОП-процедура описана в деталях. Алгоритм применим когда результаты распознавания описываются АР-цепью. Как было замечено ранее, результаты распознавания хорошо представимы АР-цепью в случае печатного и рукопечатного распознавания, т.к. текст достаточно хорошо сегментируется.

Пусть - множество вершин СД. Обозначим начальную и конечную вершины , символами соответственно. Ребро из вершины в вершину обозначим . Произвольный путь в СД из вершины в представим последовательностью вершин . Нашей задачей является нахождение такого пути в СД, который отображается на АР-цепь с наилучшей оценкой. Такое отображение будем обозначать последовательностью позиций АР-цепи , , где l – длина АР-цепи. При этом каждая вершина отображается на интервал АР-цепи с позиции по позицию . Таким образом АР-цепь разбивается на s непересекающихся интервалов ,,..., .

На Рис.6 изображена АР-матрица (b), соответствующая распознанной дате “21/june/1990” (a). Также синтаксическая диаграмма даты изображена в части (c) рисунка. Оптимальный путь сквозь СД показан толстыми стрелками и контурами вершин синтаксической диаграммы. Этот путь отображается на АР-цепь как - , разделяя ее на 7 интервалов (при этом вершины , отображаются на [] и [] соответственно). Отображение наглядно показано изогнутыми стрелками в верхней части Рис.6 (b).

ОП-процедура использует так называемую Матрицу отображения (MM), см. Рис.8. MM является матрицей размера , где k - количество вершин СД, а l - длина АР-цепи:



Столбцы MM соответствуют позициям АР-цепи, а строки MM – вершинам СД. Ячейка матрицы содержит наилучший путь внутри СД из вершины в вершину , а также информацию об отображении этого пути на интервал [0,j] АР-цепи. Если - наилучший путь в СД, а - отображение этого пути на [0,j], тогда ячейка содержит оценку отображения вместе со ссылками на предыдущую вершину СД и предыдущую позицию АР-цепи =. По этим ссылкам наилучший путь может быть рекурсивно восстановлен.


Рис.6 (a) Рукопечатная дата

(b) АР-матрица распознанной даты

(c) Синтаксическая диаграмма даты.
Пусть обозначает матрицу отображения MM размера и пусть представляется следующими тремя матрицами: - матрицей оценок , - матрицей ссылок на предыдущие позиции АР-цепи и - матрицей ссылок на предыдущие вершины СД. Пусть C - множество разрезов, которое является подмножеством позиций АР-цепи. ОП-процедура заключается в расчете матрицы отображения по следующему алгоритму (см. Рис.7). Комментарии приведены ниже.

1: Обнуление матрицы отображения. Все оценки полагаются равными 0, а все ссылки равными NIL.

2-7: Цикл по всем парам позиций i, j АР-цепи, являющихся разрезами.

8: Цикл по всем вершинам СД для которых

9: Цикл по всем вершинам СД соединенным с вершиной т.е. если существует ребро из вершины в вершину .

10-11: Если положение вершины не удовлетворяет ограничениям на местоположение, вершина пропускается. Для уменьшения времени вычисления описание вершины СД включает значения минимально и максимально допустимой длины, а также допустимый диапазон левой и правой границ вершины.

12-13: Вычисление оценки отображения вершины на интервал [i,j]. В реализации алгоритма описание каждой вершины СД содержит специфичную для данной вершины функцию отображения . Это делает общую схему алгоритма достаточно гибкой для того, чтобы проводить тонкую настройку алгоритма для решения конкретных прикладных задач. Если =0, данная вершина пропускается и продолжается перебор по другим вершинам.

14-19: Вычисление текущей клетки (w, j ) следующим образом:

.



Рис.7 Алгоритм расчета матрицы отображения

Если новая оценка выше предыдущей оценки находящейся в данной клетке, то ссылки заменяется ссылками соответственно.

После того, как расчет MM завершен, клетка (k, l) содержит оценку наилучшего пути. В том случае, если =0, тогда СД никак не отобразилась на АР-цепь. В противном случае как наилучший путь , так и отображение восстанавливаются рекурсивно по ссылкам на предыдущую вершину и позицию в цепи.

На Рис.8 в качестве примера, показан расчет матрицы для даты ‘21/june/1990’. СД даты и АР-цепь показаны на Рис.6, оптимальный путь в СД помечен жирными стрелками. Он отображается на АР-цепь следующим образом: 0,0,2,3,7,8,12,12.





Рис 8. Пример расчета матрицы MM

Вершины и отображаются на интервалы [0,0] и [12,12] соответственно. Финальная оценка оптимального пути - 1125. Как можно увидить на Рис.8, оптимальный путь выигрывает у двух альтернативных путей в клетках (4,7) и (8,12). Эти альтернативные пути не участвуют в дальнейших вычислениях. Такого рода исключение альтернативных путей оправдано принципом оптимальности.

Алгоритм расчета матрицы отображения MM имеет грубую верхнюю оценку сложности , где N – число разрезов, I – число ребер СД, а С – верхняя оценка сложности отображения вершин СД на определенный интервал АР-цепи.
5. Эксперименты
Синтаксический подход был проверен на анкетах Пенсионного фонда России (форма АДВ-1), см. Рис.9. Анкеты сканировались с разрешением 200dpi и сохранялись в формате TIFF с использованием сжатия CCITT Group 4. Анкета АДВ-1 представляет собой форму, разработанную для рукопечатного заполнения. Она содержит ряд полей ввода, имеющих определенную синтаксическую структуру. К ним относятся Почтовый адрес, Даты рождения и заполнения, Паспортные данные и Орган, выдавший паспорт. Поля Почтовый адрес и Орган, выдавший паспорт имеют наиболее сложную структуру - синтаксическая диаграмма состоит из 45 и 29 вершин соответственно. Синтаксический подход показал хорошие результаты в обоих случаях. Рассмотрим результаты алгоритмов пост-обработки поля почтового адреса более подробно. Примеры поля адреса с рукопечатным заполнением приведены на Рис.10.


Рис 9. Пример формы АДВ-1
Для анализа допустимого синтаксиса почтового адреса была использована база данных Государственной Налоговой Службы РФ, а также анализировалась 15 тысячная выборка из примерно 10 000 000 реальных адресов в текстовом ASCII формате. Для построения синтаксической диаграммы адреса и определения допустимого местоположения ее вершин применялась специальная техника с использованием эвристик.

Полученная диаграмма представляет собой довольно большой граф, состоящий из 45 вершин и 5 под-диаграмм, вложенных друг в друга в 2 уровня. СД содержит ряд тяжеловесных словарных вершин, таких как Улицы – 49 042 наименований, Населенные пункты – 11 449 наименований и Города – 1 156 наименований. Все словари содержат элементы в морфологически нормализованной форме. Для отображения вершин СД на интервал АР-сети использовались как специальные, так и общие функции отображения . Быстрая функция отображения словарной вершины была реализована в общем виде и используется в решении смежных проблем.




Рис 10. Пример почтовых адресов

Множество изображений из 3674 форм АДВ-1 было разделено на 2 части – обучающее множество из 1260 изображений и тестовое множество из 2414 изображений. Форма АДВ-1 содержит два поля адреса – Адрес фактического места жительства и Адрес по прописке. Если данные адреса отличаются, тогда в форме оба поля заполнены, иначе заполнен только Адрес по прописке. Таким образом, всего обучающее множество состояло из 1387 адресов, а тестовое - из 2718. Настройка алгоритма проводилась на обучающем множестве. Некоторые адреса были утеряны в процессе наводки формы либо были плохо распознаны и не дошли до этапа пост-обработки.



Полученные результаты приведены в Таблице 1. Столбец SA содержит результаты распознавания с использованием Синтаксического подхода, колонка CR – результаты распознавания без пост-обработки. В последнем случае результат состоит из наилучших альтернатив символов в AR-цепи.

Таблица 1. Экспериментальные данные

(1387 адресов)

SA

CR

общее количество

1387

потерянные адреса на ранних этапах

12

некорректно заполн.

37

распознанных

1375 (100%)

1375 (100%)

правильно распозн.

1223 (88,9%)

717 (52,1%)

правил. без сомнения

918 (66,8%)

293 (21,3%)

правил. с сомнением

305 (22,2%)

424 (30,8%)

неправильн. Распозн.

152 (11,0%)

658 (47,9%)

неправ. С сомнением

135 (9,8%)

492 (35,8%)

неправ. без сомнения

17 (1,2%)

166 (12%)

(2718 адресов)

SA

CR

общее количество

2718

потерянные адреса на ранних этапах

29

некорректно заполн.

59

распознанных

2689 (100%)

2689 (100%)

правильно распозн.

2314 (86,1%)

1562 (58,1%)

правил. без сомнения

1694 (63,0%)

752 (28,0%)

правил. с сомнением

620 (23,1%)

810 (30,1%)

неправильн. Распозн.

375 (13,9%)

1127 (41,9%)

неправ. С сомнением

330 (12,3%)

775 (28,8%)

неправ. без сомнения

45 (1,7%)

352 (13,1%)

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

Таблица 2. Полнота СД адреса








Всего адресов

1375 (100%)

2718 (100%)

удовл синтаксису

90,7%

87,4%

не удовл. синтакс.

8,2%

10,2%

не удовл. синтаксису, но ошибочно отображ. в СД.

1,1%

2,4%

На компьютере Pentium IV 1500 MHz среднее время пост-обработки адреса на множествах и составило примерно 0.16 сек. при средней длине АР-цепи в 47 символов.

6. Заключение
В процессе работы по данной теме был получен ряд эффективных синтаксических алгоритмов пост-обработки. Данные алгоритмы были реализованы в программном комплексе по массовому вводу форм Cognitive Forms [14]. На данный момент обработано более 20 миллионов документов по сотням видов форм. Среди них анкеты, платежные документы, таможенные декларации, накладные и т.д. Синтаксический подход существенно улучшил качество и надежность распознавания полей ввода со сложной структурой. Например, качество распознавания почтовых адресов на пенсионных анкетах увеличилось с ~55% до ~90% правильно распознанных полей. Благодаря этому общее время обработки документа сократилось. Синтаксический подход довольно универсален и позволяет получать хорошие результаты без использования специальных данных, таких как база данных адресов РФ и т.д. При этом алгоритм отображения синтаксической диаграммы на АР-цепь достаточно гибок и позволяет использовать такого рода специальную информацию. В области контекстной пост-обработки Синтаксический подход является довольно оригинальным и перспективным.
Благодарности
Автор хочет поблагодарить к.т.н. Постникова В.В. и коллег из группы научных исследований Cognitive Technologies за полезные советы и участие. Также автор хочет выразить отдельную благодарность чл.-корр. РАН Арлазарову В.Л. за участие, поддержку и финансирование исследований по данной тематике.

Ссылки

[1] D. Niyogi, S.N. Srihari, and V. Govindaraju. Analysis of printed forms. // H. Bunke and P.S.P.Wang, editors, Handbook on Optical Character Recognition and Document Image Analysis. World Scientific Publishing Co., Singapore, 1996.

[2] Djamel Bouchaffra and Venu Govindaraju and Sargur N. Srihari. Postprocessing of Recognized Strings Using Nonstationary Markovian Models. // IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21 no. 10, pp. 990-999, 1997.

[3] Peter F. Brown and Vincent J. Della Pietra and Peter V. deSouza and Jennifer C. Lai and Robert L. Mercer. Class-Based n-gram Models of Natural Language.

// Computational Linguistics, vol. 18, no. 4, pp. 467-479, 1992.

[4] Anil K. Jain and Robert P. W. Duin and Jianchang Mao. Statistical Pattern Recognition: A Review. // IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 1, pp. 4-37, 2002.

[5] Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. // N.Y.: Addison-Wesley, 1986.

[6] Michael Blumenstein and Brijesh Verma. A Neural Network for Real-World Postal Address Recognition.

[7] P. K. Wong and T. K. Ho and S. N. Srihari. Firm Name Recognition for Automatic Address Interpretation. // Proc. of the 5th {USPS} Advanced Technology Conference, November 1992 pp. pp. 757-770.

[8] Sargur Srihari and Yong-Chul Shin and Vemulapati Ramanaprasad and Dar-Shyang Lee. A System to Read Names and Addresses on Tax Forms.

[9] T. K. Ho and J. J. Hull and S. N. Srihari. Word Recognition with Multi-Level Contextual Knowledge.

// Proc. of the 1st Int'l Conference on Document Analysis and Recognition, October 1991, pp. 905-915.

[10] J. Schuermann. A Multifont Word Recognition System for Postal Address Reading. // IEEE Transactions on Computers, C-27, 8, August 1978, 721-732. 9.

[11] C.O. de Almendra Freitas, A. El Yacoubi, F. Bortolozzi, R. Sabourin. Brazilian Bank Check Handwritten Legal Amount Recognition. // Proc. of the XIII Brazilian Symposium on Computer Graphics and Image Processing.

[12] Sholomov D.L., Interpreting the Indistinctly Recognized Textual Constructions. // Pattern Recognition and Image Analysis, 2003, vol. 13, no. 2, pp. 353-355.

[13] Арлазаров В.Л., Славин О.А. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. // Информационные технологии и вычислительные системы N 1, 1996, 6 стр. 48-54.

[14] Арлазаров В.В, Постников В.В., Шоломов Д.Л. Cognitive Forms - система массового ввода структурированных документов. // Сб. «Управление информационными потоками», Москва, Эдиториал УРСС, 2002, стр. 37-49.

[15] Misyurev A.V., Hand-Printed Character Recognition by Neural Networks. // Proc. of the 5th German-Russian Workshop on Pattern Recognition and Image Understanding (GRWS98), 1999.

[16] Postnikov V.V., Flexible forms identification.

// Proc. of the 5th German-Russian Workshop on Pattern Recognition and Image Understanding (GRWS98), 1999.



[17] Постников В.В. Автоматическая идентификация и распознавание структурированных документов. // Дисс. на соискание уч. ст. канд. техн. наук (спец. 05.13.01). Москва, 2001.








Если с первого раза не удалось, попробуйте послушать жену. Роберт Орбен
ещё >>