THE INVARIANT MODEL FOR IMAGE RECOGNITION OF HAND-WRITTEN TEXT

Abstract

The invariant model for segmentation of hand-written text on separate symbols is built. The similarity measures be- tween real and pattern symbols based on hypothesis of compactness are introduced. Classification of different gram- mars for words recognition is discussed. It is necessary to design the probability grammar with fixed strategy defined by structure of nature language.

Full Text

Процесс распознавания изображений рукописно- го текста характеризуется зависимостью не только от типичных факторов шумов, вносимых способом представления информации - двумерных изображе- ний, но и проявляет сильную чувствительность к особенностям почерка того или иного человека. Именно этот факт привел к тому, что до сих пор системы распознавания изображений рукописного текста в режиме off-line демонстрируют низкую точность распознавания. Несмотря на кажущуюся простоту и естественность постановки задачи, автоматическое распознавание изображений руко- писного текста остается сложной технической про- блемой. Пусть на изображении Fk представлена символьная информация, которая в общем случае группируется в виде следующих множеств: Z = {Z1, Z2, …, ZM} - конечное множество эта- лонных образов строчных и прописных букв, цифр, специальных символов; * Пусть f ′: F ® DS - отображение множества F на множество предложений Ds, ш′: DS ® DW - отобра- жение множества DS на множество слов DW, а f′: DW ® DC - отображение множества слов DW на множество ненормализованных образов символов DC. Тогда j′: DC ® DC - отображение множества ненор- * * * * DC = {C1 , C2 , …, CN } - конечное множество мализованных образов символов DC на множество нормализованных образов строчных и прописных букв, принадлежащих выбранному алфавиту, цифр, специальных символов; DC = {C1, C2, …, CN} - конечное множество под- множеств образов строчных и прописных букв, при- надлежащих выбранному алфавиту, цифр, специаль- ных символов, при этом подмножества образов сим- волов Ci включают неограниченные варианты написа- ния конкретных символов; DW = {W1, W2, …} - неограниченное множество слов, принадлежащих различным частям речи и со- ставленных из элементов конечного множества DC, при этом Wj Ê DC; DS = {S1, S2, …} - неограниченное множество предложений, составленных из элементов множества DW. Элементы множества предложений образуют тек- стовые зоны, представленные на изображении. Система распознавания хранит эталонное множест- * ′ * нормализованных образов символов DC , а q : DC ® Z - * отображение множества нормализованных образов символов DC на множество эталонов символов Z. Тогда модель порождения изображения Fk можно * представить в следующем виде. Каждому образу со- ответствует один эталонный объект DCj*, из которого посредством некоторого отображения q: DC ® Z по- рождаются все возможные нормализованные образы * * символов DC , а посредством отображения j: DC ® DC порождаются все возможные ненормализованные образы символов DC. Отображение f: DC ® DW порожда- ет множество слов в соответствии с синтаксическими правилами языка, а отображение ш: DW ® DS порождает множество предложений в соответствии с семантическимиправиламиязыка.Наконец,изображениеFkÎ F порождается в результате отображения f: DS ® F множества предложений на множество изображений Таким образом, каждому элементу множества DCj*Ì во описаний конкретных символов Z = {Z1, Z2, …, ZM}, DC k * соответствует подмножество F Ì F. Причем, на которое должно быть инвариантно как к бесконечно- му разнообразию почерков, так и к параметрам аф- финных преобразований (сдвигов, ориентаций, мас- штабных искажений). Теоретически возможны реали- зации таких систем по методу полного перебора или на базе обучаемых нейронных сетей с обратными свя- зями. Однако в первом случае мы получаем неприем- лемое время принятия решения с заданной погрешно- стью e, а во втором - неприемлемое время обучения с практической возможностью настройки на ограничен- ное количество почерков людей. Следовательно, не- обходимо искать другие решения, которые давали бы практически значимые результаты. В общем случае систему распознавания изображе- ний рукописного текста можно представить в виде трехуровневой структуры: сегментация текстовых зон и отдельных символов, синтаксический и семантиче- ский анализ слов и семантический анализ предложе- ний и фрагментов текста. Поскольку самый высший уровень относится к проявлениям искусственного ин- теллекта, системам понимания и смысловой интерпре- тации, что на сегодняшний день крайне трудно реали- зуемо даже с учетом высокого уровня развития ком- пьютерной техники, остановимся на первых двух эта- пах распознавания. Проанализируем процесс перехода от изображе- ния, на котором представлен рукописный текст, в про- странство признаков эталонов. Пусть F - некоторое множество изображений, на котором задано разбиение множестве F можно задать бинарное отношение экви- валентности, гарантирующее, что в каждом подмно- жестве разбиения (1) отображаются элементы только одного образа [1]. Преобразования q, j, ш, f, и f принято называть прямыми преобразованиями изображений, а q′, j′, ш′, f′, и f ′ - обратными преобразованиями. Цель состоит в том, чтобы на этапе сегментации символов найти од- нозначные правила переходов обратных преобразова- ний, а на этапе распознавания определить правила переходов прямых преобразований (см. рисунок). В работе [1] показано, что модель порождения изобра- жений должна учитывать шумы, возникающие в про- цессе отображения объектов наблюдения на восприни- мающем устройстве. Однако в данной модели такие шумы не являются значимыми, поскольку большую шумовую составляющую вносит многообразие почерка даже одного человека. При необходимости от шумов, вносимых способом представления информации, можно избавиться на этапе предварительной обработ- ки изображений с использованием глобальных или локальных адаптивных фильтраций. Рассмотрим процесс сегментации образов симво- лов рукописного текста. Преобразования f ′: F ® DS и ш′: DS ® DW можно заменить одним преобразованием (fш)′: F ® DW, которое определяет зоны слов на изо- бражении. В качестве такого преобразования можно использовать морфологическую операцию расширения: F Å B = {dw|((B′)d f f f w ∩ F) Í F}, на подмножества V1 , V2 , ..., Vm такие, что которая в данном случае размывает изображения сим- F = V1 Ú V2 Ú ... Ú Vm , Vi ÙVj =Æ при i ¹ j. (1) волов в словах, не оказывая влияния на пробелы меж- f f f f f f f f ду словами и межстрочные интервалы. При этом B Сами подмножества сами данного разбиения. V1 , V2 , ..., Vm назовем клас- представляет собой примитив операции расширения, на основе которого получают центральное отражение относительно его начала координат (B′), а затем сдвиг полученного множества в точку dw. Далее строятся прямоугольники, охватывающие отдельные слова. Здесь необходима операция предварительной норма- лизации текстовых зон относительно системы коор- динат, позволяющая длинную ось прямоугольника расположить параллельно оси OX. В общем случае эту процедуру необходимо провести для всех выделенных слов, однако ее можно упростить, анализируя отдель- ные строки или даже отдельные абзацы, если выясне- но, что направление написания слов не превышает заданного порога расхождения. Операцию «размытия» слов можно выполнить и другими средствами, напри- мер, фильтрацией Гаусса, однако подстройка пара- метров под конкретное изображение рукописного тек- нечным многообразием почерков и написаний. Здесь действуют следующие операторы: ′ оператор усиления центральной части символа Oc(f) ; оператор определения верхней части символа u O (f)′; ′ оператор определения нижней части символа Od(f) ; ′ оператор поиска и анализа предлогов, союзов и т. п. Oa(f) ; ′ адаптивный оператор нахождения символов в слове Os(f) . В качестве оператора усиления центральной части ′ ста будет затруднительна. символа Oc(f) можно использовать морфологическую Однако на данном этапе возникают трудности, свя- занные с определением знаков пунктуации в предло- жениях, поскольку такие знаки (точки, запятые, двое- точия, точки с запятой) можно принять за шум. Со- ставные слова с дефисом также требуют проведения дополнительного анализа на принадлежность к одно- му слову. Поэтому преобразование (fш)′: F ® DW должно включать следующий набор операторов: оператор предварительной нормализации тексто- ′ операцию расширения для размытия образов симво- лов и морфологическую операцию сжатия для суже- ния линий соединения символов: DC Å B = {dс|((B′)dс ∩ DC) Í DC }, DC Ө B = {dс|(B)z Í DC}. Сжатие множества DC по примитиву B определяет- ся как множество всех таких точек dс, при сдвиге в которые множество B целиком содержится во множе- (f)′ вых зон On(fш) ; ′ стве DC. Операторы определения верхней Ou ′ и ниж- оператор расширения Oe(fш) ; ′ оператор категоризации символов Oc(fш) ; ′ оператор нахождения специальных символов Os(fш) . Тогда модель определения текстовых зон на изо- ней Od(f) частей символов необходимы для выявления графологических особенностей написания букв типа «б», «в», «д», «й», «р», «у», «ф» и т. д. кириллическо- го алфавита и «b», «d», «f», «k» и т. д. латинского ал- фавита. Оператор поиска и анализа предлогов, союзов ′ бражении выражается формулой и т. п. Oa(f) необходим для накопления статистики о ′ ′ ′ ′ (fш)′ = <{On(fш) }, {Oe(fш) }, {Oc(fш) }, {Os(fш) }>. Следующим, возможно, самым трудно реализуе- мым этапом в распознавании рукописного текста яв- ляется разделение слов на отдельные символы (преоб- разование f′: DW ® DC), которые отличаются беско- примерном соотношении высоты и ширины символов, характерных для конкретного почерка. Этот оператор функционирует на основании гипотезы о равномерно- сти соотношения высоты и ширины символов руко- писного текста. image image f ′: F ® DS f : DS ® F F F ш′: DS ® DW DS ш: DW D ® DS S f′:DW ® DC DW j′: DC ® DC* DC D f: DC ® DW W j: DC*®DC DC D C * q′: DC* ® Z D C C * q: Z ® D * Z Z а б Модель распознавания рукописного текста: а - обратные преобразования; б - прямые преобразования Адаптивный оператор нахождения символов в сло- ′ Указанные требования к мере сходства легко вы- ве Os(f) подстраивает размеры прямоугольного окна, полняются в метрических пространствах. Если в про- описывающего символ, и выполняет маркировку ис- ходя из гипотезы о пропорциональности символов кириллического и латинского алфавитов. Модель определения отдельных символов на изо- бражении слова выражается формулой странстве изображений введена мера расстояния, то любая невозрастающая функция этого расстояния удовлетворяет изложенным выше требованиям. Так, для эвклидова пространства можно выбрать в качестве меры сходства некоторую функцию Q от расстояния: ′ ′ ′ ′ ′ image f′ = <{Oc(f) }, {Ou(f) }, {Od(f) }, {Oa(f) }, {Os(f) }>. Этап перехода к нормализованным образам от- L(Fс , F z æ ) = Q ç n å i =1 ÷ 2 ö ( fiс - fiz ) ÷ ® min, C дельных символов j′: DC ® D * è ø связан с выделением внешнего контура символа, параметризацией вектор- ного представления контура и нормализацией вектор- ного представления. Если задачи выделения внешнего контура объекта и параметризация его векторного где n - размерность пространства. Также для измере- ния сходства можно использовать упрощенную фор- мулу æ n ö представления исследованы в большом количестве L(Fс , Fz ) = Q ç å image fiс - fiz image ÷ ® min. работ, то нормализация векторного представления (особенно в контексте поставленной задачи) требует дополнительных усилий. Особенностью распознава- ния рукописных символов является наличие не только замкнутых, но и разомкнутых контуров. Поэтому не- è i =1 ø При наличии векторного описания меру близости символа с j-м эталоном Lj(Fk, Fz) можно определить через множество двух признаков: Alphai - угол накло- на и Leni - длину вектора: которые известные методы получения инвариантов для описания контуров, например, спектральные ме- тоды, являются не пригодными для решения данной Lj (Fc , Fz ) = å j ((Alpha , Len ) - (Alpha j , Len j ))2 , i i i i j задачи. Предлагается инвариантность к масштабу обеспечивать приведением суммы длин векторов к единице, а инвариантом выбора начальной точки об- хода контура считать вектор с минимальной длиной. При наличии нескольких векторов с минимальной длиной используются специальные правила выбора начальной точки обхода, реализуемые на этапе обуче- ния системы. Таким образом, модель нормализации образа символа можно представить в виде ′ ′ ′ j′ = <{Oo(j) }, {Ov(j) }, {On(j) }>, ′ ′ где {Oo(j) } - оператор выделения внешнего контура ′ символа, {Ov(j) } - оператор параметризации векторно- го представления контура, {On(j) } - оператор норма- лизации векторного представления. где Alphai - угол наклона и Leni - длина вектора j- го эталона. К сожалению, гипотеза компактности может не выполняться на выбранном пространстве признаков, что требует нахождения дополнительных признаков и перехода в новое пространство, в котором образы лег- ко бы разделялись. Однако иногда в реальных систе- мах эту процедуру компенсируют этапом обучения с целью повышения быстродействия и сокращения объ- ема памяти. Теперь рассмотрим процесс распознавания руко- писного текста в целом. Возможны две стратегии, первая из которых последовательно выполняет про- цесс сегментации и распознавания образов символов и затем в соответствии с лингвистическими правилами * Этап q′: DC ® Z отображения множества нормали- языка корректирует возможные ошибки в отдельных зованных образов символов DC* на множество этало- нов символов Z можно отнести к процессу распозна- вания образов текстовых символов. Здесь можно ис- * пользовать хорошо исследованные меры сходства в метрических пространствах признаков с целью нахо- ждения минимальных различий между образом и эта- лоном. Можно считать, что отображение q′: DC ® Z переводит изображение символа в точку многомерно- го векторного пространства. Тогда в соответствии с гипотезой компактности образов можно сформулиро- вать следующие требования к мере сходства L(Fk, Fz) между изображениями символа и эталона: а) мера сходства должна быть неотрицательной ве- личиной, т. е. L(Fk, Fz) ³ 0; б) мера сходства изображения с самим собой должна быть максимальной L(Fk,Fk) ® max; в) мера сходства должна обладать свойством сим- метрии, т. е. L(Fk, Fz) = L(Fz, Fk); г) мера сходства в случае компактных образов должна быть монотонной функцией удаления точек, соответствующих сравниваемым изображениям. позициях. Вторая стратегия реализует изложенный выше процесс сегментации и распознавания образов символов только в начальных позициях слов, а потом ускоряет процесс распознавания с учетом распознан- ных символов в словах на основе, например, скрытых марковских моделей. Тем не менее, для любой страте- гии необходимы лингвистическая база правил и лин- гвистический словарь языка. Первая стратегия объек- тивно имеет более низкое быстродействие, поскольку не учитываются известные лингвистические конст- рукции языка, а вторая - требует составления и хра- нения моделей множества слов. Компромиссным ва- риантом является построение дерева вывода слова (дерева грамматического разбора), которое позволяет ограничить количество сравнений нормализованных образов символов с эталонными образами при реали- зации преобразования q′. Структурный подход к распознаванию образов да- ет возможность описывать множества сложных изо- бражений, используя небольшой набор непроизвод- ных элементов (в данном случае образов символов) и грамматических правил. Правила конструирования композиций из непроизводных элементов (в данном случае символов) обычно задаются с помощью специ- альных грамматик, называемых грамматиками описа- ния изображения. Грамматическое правило может быть применено любое количество раз. Язык, обеспе- чивающий структурное описание изображений слов в терминах множества непроизводных элементов и кон- струирование композиций этих элементов, называют языком описания изображений. Для рассматриваемой задачи распознавания рукописного текста язык описа- ния изображений эквивалентен естественному лин- гвистическому языку. Отметим, что в естественных языках часто возникает проблема неоднозначности. Одно предложение может иметь несколько различных значений в зависимости от различных способов его грамматического разбора. Порождающая грамматика считается неоднозначной, если существует последова- тельность, имеющая более одного вывода. При этом различными выводами считаются такие последова- тельности, которые нельзя преобразовать друг в друга, изменяя лишь порядок применения правил. Понятно, что при формировании языков описаний стремятся избегать неоднозначности, вследствие чего возникает задача поиска семейства неоднозначных грамматик. Различные виды грамматик различаются формой правил подстановки. Самый широкий класс грамма- тик характеризуется отсутствием каких-либо ограни- чений на вид правил подстановки. Известны бескон- текстные грамматики, представленные в виде выводов предложений или с использованием деревьев вывода. Для описания сильно зашумленных изображений применяются стохастические грамматики, которые отличаются тем, что на множестве правил подстанов- ки вводится некоторое распределение вероятностей. Известны два основных подхода к построению алго- ритмов стохастического синтаксического анализа изо- бражений: стохастический порождающий алгоритм и детерминированный алгоритм возврата. При этом раз- личают два типа стохастических алгоритмов синтак- сического анализа. В алгоритмах первого типа (алго- ритмы с фиксированной стратегией) выбирается пра- вило подстановки с наибольшей вероятностью приме- нения, а в алгоритмах второго типа (алгоритмы со случайной стратегией) правила из списка переходов выбирается случайно, но в соответствии с распреде- лением вероятностей применения на множестве всех правил подстановки из этого списка. Также разрабо- тан метод эталонных последовательностей, основная особенность которого заключается в том, что с помо- щью некоторой грамматики задается не множество распознаваемых изображений, а множество специаль- ным образом подобранных эталонов. Специфика зада- чи распознавания рукописного текста требует разра- ботки стохастической грамматики с фиксированной стратегией, определяемой структурой естественного языка. Существует несколько подходов к реализации сто- хастической грамматики для решения задачи распо- знавания рукописного текста. Укажем основные стра- тегии по мере усложнения: стохастическая грамматика, основанная на вы- числении вероятностей появления отдельных симво- лов в текстовых документах больших объемов; стохастическая грамматика, вычисляющая веро- ятности появления лингвистических единиц (слогов, словосочетаний); грамматика, построенная на методах сокращения поиска в виде интерпретационного дерева. Нельзя сказать, что все три грамматики идеально подходят для решения поставленной задачи. Тем не менее, рассмотрим, каким образом использование грамматики языка повышает достоверность распозна- вания отдельных символов и текста в целом. Первая стратегия не учитывает условной вероятности появле- ния последующих символов в слове. В основе этой грамматики лежит вероятность появления того или иного символа PCj, которая вычисляет по формуле N åCi, j image C P = j =1 , i N где Ci,j - количество появлений i-го символа в j-м сло- ве; N - количество слов. Использование статистической информации о символах заключается в том, что при распознавании текущих символов в слове вначале анализируются такие эталоны символов, у которых вероятность вхо- ждения символа в слово велика, и лишь затем рас- сматриваются остальные эталоны символов. Вторая стратегия является обобщением первого подхода с тем отличием, что элементами анализа ста- новятся слоги и устойчивые словосочетания, прису- щие естественному языку. Здесь можно применить функцию максимального правдоподобия или байесов- ский подход вычисления апостериорной вероятности появления слога при условии существования части распознанного слова r = r1r2…ri, состоящей из i сим- волов. Эффективной формальной моделью третьего вида грамматики может служить скрытая марковская мо- дель (СММ). Ее основными составляющими являются следующие допущения [2]: наличие последовательности случайных пере- менных, каждая из которых условно независима от всех других, кроме предшествующей переменной; каждая случайная переменная характеризуется измерениями, распределение вероятностей которых зависит от состояния. Третий вид грамматики является самым трудоем- ким на этапе обучения и самым ресурсоемким на эта- пе функционирования. Проблематичность построения и хранения СММ отдельных слов в контексте постав- ленной задачи (поскольку начальные символы в слове могут быть распознаны не верно, что приведет к от- рицательному результату) может быть частично снята использованием СММ слогов и устойчивых словосо- четаний. В процессе работы алгоритма распознавания построение моделей отдельных слов производится динамически объединением моделей составных час- тей, входящих в их состав. В то же время модель сло- варя должна содержать вероятности написания слов и, желательно, вероятности взаимных переходов между словами. Задача распознавания рукописного текста ослож- няется тем, что принятие решения о принадлежности изображения рукописного символа определенному образу основывается на неполных данных из-за осо- бенностей почерка. При этом возникает задача нахож- дения оптимального решающего правила, которое может быть построено по методу, близкому к методу максимального правдоподобия. Пусть задано изобра- жение F, имеющее признаки x1, …, xn-k, где k - число недостающих признаков. Тогда для определения при- надлежности этого изображения одному из образов следует воспользоваться следующим правилом: P(V / x , ..., x ) подтверждают высокую эффективность разработан- ной модели распознавания. Для тестирования исполь- зовалась база данных эталонных векторных моделей, включающая 10-15 моделей на каждый символ. Каж- дая модель состоит из 20 векторов, нормализованных по 16 направлениям. В режиме функционирования без обучения система обеспечивает точность распознава- ния 68-75 %. В случае, когда система использует ре- жим обучения на конкретный почерк, точность распо- знавания повышается до 80-95 %, что является вполне допустимым из-за сложности решаемой задачи. В на- стоящее время проводятся работы по расширению программного комплекса и созданию модуля распо- знавания рукописного текста для ввода и обработки документов в системах электронного документообо- F Î Vi, если image i 1 n -k > 1. рота. Планируется разработка и подключение элек- P(Vj / x1 , ..., xn - k ) Принимая во внимание, что для каждого образа тронных лингвистических словарей различной тема- тики (технической, экономической, юридической), что также должно способствовать повышению точности P(V / x , ..., x image ) = p(V ) P(x1 , ..., xn-k /Vi ) , распознавания рукописного текста. i 1 n- k i P(x1 , ..., xn-k )