Многопроходная схема распознавания документов с обучением - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Установка системы распознавания документов Cognitive Scanifyapi 1 27.19kb.
Определение достоверности результатов распознавания символа в системе... 1 175.74kb.
Адаптивное распознавание символов В. Л. Арлазаров 1 279.44kb.
Методы распознавания грубых объектов О. А. Славин, Г. В. Корольков, П. 1 267.62kb.
Пояснительная записка к курсовому проекту по курсу «Схемотехника... 1 351.27kb.
Присутствовали на уроке: 12 Тема урока: Системы оптического распознавания... 1 30.19kb.
Гистограммный и полигональный способ оценивания плотности вероятности 1 16.2kb.
Н. В. Котович, О. А. Славин 1 172.66kb.
Алгоритмы распознавания казахского слова как целого 8 1029.41kb.
Лабораторная работа «Задачи распознавания образов» 1 152.14kb.
Блок-схема предоставления государственной услуги 1 14.68kb.
Схема работы ОАО банк зенит с клиентами, направленными mr group (дду) 1 61.04kb.
Направления изучения представлений о справедливости 1 202.17kb.

Многопроходная схема распознавания документов с обучением - страница №1/1

Многопроходная схема распознавания документов с обучением.
Кляцкин В.М., Котович Н.В., Славин О.А.
В статье описаны средства распознавания текстовых документов с обучением особенностям использованных при печати шрифтов. Описаны алгоритмы, как обучения, так и комбинированного распознавания текстовых строк после обучения. Уделено внимание особенностям процесса кластеризации образов символов, уже прошедших первичную классификацию.
Многопроходная схема, применяемая в программах оптического распознавания документов, состоит в последовательной классификации одних и тех же текстовых строк сначала с помощью шрифтонезависимых алгоритмов распознавания символов, а затем – алгоритмов, использующих особенности шрифтов, примененных при печати документа. Целью многопроходной схемы распознавания с обучением является адаптация к особенностям образов символов, находящихся в распознаваемой странице. При этом на количество и характеристики используемых шрифтов не накладывается существенных ограничений.

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

Обучающая выборка готовится первым проходом распознавания, который с помощью шрифтонезависимого алгоритма распознавания символов 1 (например, «грубые» методы [6]). Алгоритм 1 предоставляет коллекции альтернатив (варианты распознавания с оценками) символов, соответствующих распознанным образам, и атрибуты символов, таких как, курсивность, серифность и жирность (см. рис. 1).


Рис. 1. Примеры атрибутов шрифта

Еще одним признаком символов является кегль (стандартный размер) образа, определенный базовыми линиями. Кроме этого первый проход обеспечивает валидацию образов, то есть пометку надежно распознанных символов, с помощью следующих двух механизмов



  • учет оценок альтернатив, сформированных алгоритмом с монотонными оценками

  • словарное или контекстное подтверждение достаточно длинного слова,

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

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

Термин кластерный анализ (впервые ввел Tryon, 1939, [1]) в действительности включает в себя набор различных методов и алгоритмов классификации. Всякий раз, когда необходимо классифицировать большие массивы информации по приемлемым для дальнейшей обработки группам, кластерный анализ оказывается весьма полезным и эффективным.

Многократные попытки классификации самих методов кластерного анализа приводят к десяткам, а то и сотням разнообразных классов [2-4,8]. Такое многообразие порождается большим количеством возможных способов вычисления расстояния между отдельными объектами, не меньшим количеством функций вычисления расстояния между кластерами в процессе кластеризации и многообразными оценками оптимальности конечной кластерной структуры.

Наибольшее распространение получили две группы методов кластерного анализа: иерархические агломеративные методы и итеративные методы группировки.

Среди итерационных наиболее популярным является метод k-средних Мак-Кина. В отличие от иерархических алгоритмов сам пользователь должен задать искомое число конечных кластеров, которое обычно обозначается как k. Как и в иерархических методах кластеризации, при этом можно выбрать тот или иной тип метрики. Разные алгоритмы метода k-средних отличаются также способом выбора начальных центров задаваемых кластеров. Поскольку мы заранее не знаем, сколько шрифтов находится на странице, использование метода k-средних в нашем случае представляется затруднительным.

В агломеративно-иерархических алгоритмах (agglomerative hierarchical algorithms) первоначально все объекты рассматриваются как отдельные, самостоятельные кластеры, состоящие всего лишь из одного элемента. Процедура кластеризации состоит в постепенном объединении объектов в достаточно большие кластеры, используя некоторую меру сходства или расстояние между объектами. Типичным результатом такой кластеризации является иерархическое дерево. На первом шаге, когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Однако когда связываются вместе несколько объектов, возникает вопрос, как следует определить расстояния между кластерами?

Существует много способов объединения кластеров, перечислим некоторые из них.



  • Одиночная связь (метод ближайшего соседа). В этом случае расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах.

  • Полная связь (метод наиболее удаленных соседей). В этом случае расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями").

  • Невзвешенное попарное среднее. В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них.

  • Взвешенное попарное среднее. Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента.

  • Невзвешенный центроидный метод. В этом случае расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.

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

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

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

В нашей программе для кластеризации мы использовали алгоритм цепной развертки, рекомендованный Щепиным Е.В., алгоритм относится к группе методов одиночной связи. Алгоритм кластеризации, базирующийся на расстоянии Хаусдорфа и приведенный в [5] качественно отличается от широко известных методов, прежде всего, из-за структуры информации, подлежащей классификации во время обучения и целей кластеризации. Минимизация числа кластеров, быстродействие и другие вопросы классической кластеризации имеют для нас важное, но не первостепенное значение.

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

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



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

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

  • уничтожение кластера, то есть вывод ненадежно распознанного кластера из рассмотрения

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

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

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




О0 (русская «О» и ноль)

АA (русская и латинская «А»)

3З (русская «З» и три)

Рис. 2. Неразличимые (О,0 и А, A) и сходные по начертанию (З,3) шрифтоонезависимыми алгоритмами образы
В то же самое время в пределах одного шрифта, как правило, некоторые из символов алфавита и родственных символов различимы геометрически, наличие же нескольких шрифтов на странице может как затруднить, так и упростить распознавание близких символов. После завершения этапа анализа кластеров, исследующего подобные возможные конфликтные ситуации, становится известным, насколько хорошо построенные эталоны могут разрешать коллизии родственных символов и символов с одинаковым начертанием в различных шрифтах. Информация об этом содержится в перечне групп разноименных родственных символов и в списке расстояний между неразличимыми символами. Близкие символы с рис. 2. a priori должны попасть в достаточно далекие друг от друга кластеры, что обеспечит их дальнейшее разделение.

Из обработанных кластеров может быть извлечено множество эталонных скелетных и расширенного образов, мера близости к которым обеспечивает достаточные характеристики качества распознавания. Возможно представление эталонов, состоящее из трех объектов:



  • скелетное подмножество SKEL, содержащее значения растра кластеров в границах истинного скелетного образа

  • расширенное подмножество COVER, содержащее нули в границах истинного расширенного образа, очевидно, COVER SKEL

  • описание штрафа, зависящего от расстояния до ближайшей точки скелетного или расширенного образа, вычисляемое с помощью функций Pen(i, j, M), аргументами которой являются координаты точки и множество M.

Каждое из подмножеств является матрицей того же размера, что и стандартизованные растры, подлежащие кластеризации, и зависят от объема и иных характеристик кластера. Наложение, то есть вычисление меры близости произвольного образа и эталона E=||eij|| происходит в несколько этапов, первым из которых является центрирование образа. Для отцентрированного, то есть стандартизованного, образа R =||rij|| подсчитывается сумма покомпонентных произведений значений растров R и E

(R,E) = (rij=1 eij>0) eij

Pen(i,j,SKEL(S,))( (rij=0  eij>0) –

Pen(i,j,COVER(S,))( (rij=1  eij<0)

которая включает в себя как положительные произведения точек растра, попавших в скелетную область, так и отрицательные компоненты точек, не попавших в расширенную область, и штраф за недостаток точек в скелетной зоне (см. рис. 3). В этом выражении присутствуют как положительные значения суммы растров, составивших кластер, так и отрицательные штрафные значения. Таким образом вычисленная близость отвечает на вопрос о том, насколько хорошо распознаваемый образ соответствует распределению данного кластера, то есть улучшает вероятностные свойства оценок наложения. Разумеется, не следует забывать не только об эвристических штрафах, не обладающих вероятностной природой, но и об объеме кластера, порождающего скелетную область, так как образование малых кластеров не является чем-то исключительным для большинства страниц с печатным тестом неидеального качества. Вклад штрафов в общую сумму также улучшает оценки при условии оптимизации штрафов за удаление от границы расширенного образа. Результатом наложения является альтернатива



(S(E), W(R,E))

где S(E) - код символа кластера с растром E



W - масштабный коэффициент для получения оценок,

Рис. 3. Иллюстрация кластерного наложения

а) скелетная (черный) и расширенная(серый) зоны

б) накладываемый образ

в) точки суммирования скелетной зоны (черный) и

штрафные (серый) точки

при этом наследуются свойства кластера (кегль, атрибуты шрифта).

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

Рис.4. Искажения символа, не меняющие и меняющие центр стандартизованного растра
Отметим, что вычисление достаточно трудоемких оценок наложения может быть ускорено прерыванием подсчета суммы в ситуации набора значительного числа штрафов. Значительная разница в размерах растров R и E позволяет принять решение об отказе наложения данного эталона, это соображение в совокупности с фильтрацией по атрибутам эталонов также ускоряют алгоритм наложений.

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

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


  • наименьшее расстояние достигнуто на эталоне, далеком от других эталонов

  • наименьшее расстояние достигнуто на эталоне, попавшем в группу близких разноименных эталонов

  • проверка близости не может быть произведена из-за отсутствия эталонов с данным кодом символа.

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

Ожидаемое отсутствие ряда эталонов (прежде всего, для редко встречаемых заглавных букв) предполагает комбинирование результатов шрифтонезависимого алгоритма и алгоритма кластерного наложения, адаптивного к символам в распознаваемой странице. Схема комбинирования строится в предположении, что значительная часть (80-90%) страницы уже распознана без ошибок, вследствие чего для оставшейся доли дораспознаваемых символов возможно применение достаточно трудоемких алгоритмов распознавания символов. Это означает, что комбинировать кластерное наложение целесообразно с алгоритмом, точность которого превышает точность алгоритма 1 распознавания символов на первом проходе. Комбинирование с более точным алгоритмом (например, с нейронной сетью [7]) обеспечивает как сохранение кластерных оценок в случае успешно распознанных обоими алгоритмами образов и разрешенных конфликтов, так и сохранение точности алгоритма 1 с одновременным снижением его оценок в случае не подтверждения его результатов надежными кластерами. Это улучшает и точность, и монотонность оценок. Использование шрифтонезависимого алгоритма позволяет распознавать и выставлять оценки символам, для которых не собрались подтверждающие эталоны. Недостатком описанного комбинирования является получение оценок различной природы: как шрифтонезависимых, так и кластерных, сопоставление которых в общем случае затруднительно. Начальные параметры схемы комбинирования, в первую очередь относятся порогов оценок, по которым принимается решение о надежности распознавания, могут изменяться после завершения кластеризации, за счет чего происходит дополнительная адаптация к результатам первого прохода распознавания страницы.



Рис. 5. Пример результатов сегментации на разных проходах

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

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

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

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

Схема с дораспознаванием страниц, организованная в виде обучения по результатам распознавания строк на первом проходе алгоритмом 1, и распознаванием на втором проходе адаптивным алгоритмом 2, существенно улучшает характеристики качества по отношению к однопроходной схеме с алгоритмом 1. Например, в классе печатных документов хорошего качества точность распознавания символов (без различия на стоящие отдельно и сегментированные) возрастает с 99.1% до 99.6-99.7%.

При этом второй проход занимает примерно 25% по отношению к времени первого прохода, несмотря на то, что быстродействие алгоритма 2 как минимум в 2 раза ниже быстродействия метода 1.


Литература

1. Tryon R.C. Cluster Analysis. New York: McGraw-Hill. - 1939.

2. Sokal R., Sneat P. Principles of Numerical Taxonomy. San Francisco: W.H. Freeman, 1963.

3. Мандель И.Д. Кластерный анализ. - М.: Финансы и статистика, 1988. – 176 с.

4. Классификация и кластер. / Под ред. Дж. Вэн Райзина. - М.: Мир, 1980, -390 с.

5. Арлазаров В.Л., Астахов А.Д., Троянкер В.В., Котович Н. В. Адаптивное распознавание символов. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 39-56

6. Славин О.А., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов. В сб. "Развитие безбумажных технологий в организациях", 1999, с. 290-311

7. Мисюрев А.В. Использование искусственных нейронных сетей


для распознавания рукопечатных символов. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с.122-127

8. Кляцкин В.М. Использование методов вычислительной геометрии для синтеза быстрых алгоритмов автоматической классификации. В сб. "Геометрия, топология и приложения", М.:МВиССО, Московский инст-т приборостроения. Межвуз. сб.науч. трудов.-1990.-С.46-53.




Только несказанное и стоит запомнить. Дон-Аминадо
ещё >>