2. Задача пост-обработки
Скачать 160.51 Kb.
|
| Синтаксический подход к задачам пост-обработки нечетко распознанного текста Шоломов Д.Л. В работе рассматривается синтаксический подход к задачам интерпретации и нормализации синтаксических текстовых конструкций на стадии пост-обработки распознанного текста. Такого рода задачи возникают при распознавании текстовых полей ввода на формах и структурированных документах. В работе рассматривается постановка задачи интерпретации нечетко распознанного текста, область применения синтаксического подхода, приводятся примеры реализации алгоритмов в системах оптического распознавания. Качественные оценки синтаксических алгоритмов приводятся на примере задачи распознавания почтового адреса. 1. Введение В настоящее время в сфере информационных технологий широко используются системы идентификации и распознавания структурированных документов и форм [1], [8], [10], [14]. Формы состоят из постоянных (статических) элементов и элементов, меняющихся от формы к форме. Линии, статические тексты и картинки относятся к постоянным элементам, текстовые поля ввода, чекбоксы, печати, штрих коды – к меняющимся. Часто поля ввода имеют определенную синтаксическую структуру, например Почтовый адрес, Наименование организации, дата рождения и т.д. Работы [6], [7], [8], [10], [11] непосредственно посвящены распознаванию определенных типов полей. Синтаксическая структура полей может иметь различную степень жесткости. В зависимости от этого структура может быть описана различными способами и применяются различные методы контекстной пост-обработки [12]. Часто обычные алгоритмы распознавания 'гладкого' текста дают неудовлетворительные результаты при распознавании текстовых полей ввода из-за таких факторов как широкий алфавит, большое количество пунктуации, специфические сокращения и акронимы. Наряду с этим требования к качеству и надежности распознавания полей ввода в реальных задачах ввода форм довольно высокие и не могут быть удовлетворены обычными алгоритмами. Таким образом необходимо использовать подходы, в которых алгоритм располагает информацией о структуре поля. В данной работе описан так называемый синтаксический подход, в котором структура поля задается посредством синтаксических диаграмм. Данный подход применим к широкому кругу полей частично либо полностью описываемых синтаксическими диаграммами. 2. Задача пост-обработки Процесс распознавания формы обычно состоит из следующих этапов:
В некоторых OCR системах стадии 3 и 4 выполняются одновременно, сегментация текста и распознавание символов производится под управлением контекстно-зависимого интерпретатора [6]. На стадии специфичной пост-обработки предварительные результаты распознавания уже получены и расположены в так называемой Сети Альтернатив Распознавания (АР-сети). Пример АР-сети изображен на Рис. 1. Наличие предварительных результатов распознавания с возможностью последующей неоднозначной трактовки означает то, что текст распознан нечетко.  Рис 1. Пример АР-сети. Вершины АР-сети соответствуют альтернативам распознавания символов; ребра соответствуют оценкам перехода от одной альтернативы к другой. Начальная и конечная вершины обозначаются плюсом и минусом соответственно. АР-сеть содержит информацию о сегментации текстового поля и об оценках распознанных символов. Каждый путь через АР-сеть соответствует некоторому текстовому значению, полученному конкатенацией символов соответствующих вершинам сети, принадлежащим данному пути. Наша задача сводится к нахождению оптимального пути в АР-сети с точки зрения оценок распознавания символов и соответствия структуре поля. Часто необходимо привести распознанный текст к нормальной форме. Практически всегда необходимо оценить степень надежности распознанного значения и локализовать его ненадежные фрагменты. Синтаксический подход допускает OCR, ICR распознавание. 3. Синтаксический подход в целом Известные подходы контекстной пост-обработки включают статистические методы [2], [3], [4], такие как N-грамы и СММ, лингвистические методы и методы, использующие нейронные сети. Нередко такого рода методы не подходят для распознавания полей, которые не являются словарными или текстом на естественном языке, где структура либо слишком жесткая, либо излишне свободная. В подходах использующих выделение лексических признаков с дальнейшей классификацией при помощи нейронной сети недостаточное внимание уделяется синтаксису поля, порядку слов и взаимосвязями между ними.  Рис 2. Синтаксическая диаграмма даты. При распознавании таких полей, как Почтовый адрес, Наименование организации и Сумма прописью на банковских документах удобно и оправданно задавать синтаксис поля при помощи синтаксических диаграмм СД, см. Рис.2, или грамматик в форме Бэкуса-Наура [5]. Подходы такого рода используются в распознавании речи и технике компилирования [5]. Действительно, задачи схожи – имеется линейный объект, такой как речевой поток или строка текста, интерпретируемый в соответствии с определенной грамматикой. В случае пост-обработки распознанного текста потоком является линейная АР-сеть или АР-цепь – набор знакомест с альтернативами распознавания (Рис. 3). Грамматика задается синтаксической диаграммой. Т.к. при печатном и рукопечатном распознавании текст хорошо сегментируется, результаты распознавания хорошо представимы АР-цепью.  Рис 3. Пример АР-цепи. Удобно представлять АР-цепь в виде АР-матрицы (см. Рис. 4), Ячейки матрицы содержат альтернативы символов вместе с оценкой распознавания символа. Подразумевается, что любые две ячейки в соседних столбцах соединены ребром перехода. Оценка перехода содержится в правой ячейке.  Рис 4. Пример АР-матрицы Задача пост-обработки заключается в нахождении оптимального пути в АР-сети, который в то же время соответствует синтаксической диаграмме. Процедура нахождения оптимального пути – довольно сложная задача оптимизации. АР-сеть и синтаксическая диаграмма могут состоять из сотен вершин, среди которых могут встречаться тяжеловесные словарные вершины. Например, такие словарные вершины, как Улицы и Города могут состоять из десятков тысяч элементов. Поэтому алгоритмы должны удовлетворять разумным требованиям к скорости. В нашей реализации алгоритма использует ряд оптимизационных методов, таких как итеративная сегментация АР-цепи и кэширование результатов отображения вершин СД на АР-цепь. Синтаксическая пост-обработка проводится в соответствии со следующей блок-схемой (см. Рис 5):  Рис 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. Экспериментальные данные
Результаты показывают, что Синтаксический подход существенно улучшает качество распознавания. Из сравнения результатов распознавания множеств и можно сделать вывод о стабильности алгоритма. Таблица 2 показывает, что полученная синтаксическая диаграмма адреса довольно полная, т.е. всего около 10% адресов не удовлетворяют ее синтаксису.Таблица 2. Полнота СД адреса
На компьютере 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
 | Осаго (утв пост. Президиума рса от 31. 08. 2006, пр. №3, в редакции пост. Президиума рса от 27. 10. 2011, пр. №6; от 14. 02. 2013,... |  | Перед нами стоит не управленческая, а чисто информационная задача, а если быть точнее задача информационных технологий |
| Типовая информационная технология сбора, передачи, обработки и выдачи информации в централизованных системах обработки данных 17 | | Ректор фгбоу впо “Саратовский государственный университет имени Н. Г. Чернышевского” |
| Программа автоматизированной обработки результатов фото-видеофиксации нарушений Правил дорожного движения | | ... |
| Правительства Российской Федерации от 15. 09. 2008 №687 «Об утверждении Положения об особенностях обработки персональных данных,... | | Категории обрабатываемых персональных данных, источники их получения, сроки обработки и хранения. 3 |
| Вешняков подтвердил намерение претендовать на пост председателя цик на новый четырехлетний срок 39 | | Постановлением Правительства Российской Федерации от 15. 09. 2008 №687 «Об утверждении Положения об особенностях обработки персональных... |