Древовидное распознавание нормализованных символов

,

ДРЕВОВИДНОЕ РАСПОЗНАВАНИЕ НОРМАЛИЗОВАННЫХ СИМВОЛОВ

АННОТАЦИЯ

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

ВВЕДЕНИЕ

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

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

Помимо этого, отсканированное изображение печатного символа зависит и от условий реализации этого изображения. Под условиями реализации понимаются прежде всего дефекты при сканировании, а также тип печатной техники и другие факторы, влияющие на качество печати. Таким образом, множеством возможных изображений символа a будем называть множество I(a, T,G), где T - множество параметров шрифтов, с помощью которых осуществляется реализация изображения, а G - условия реализации. Под множеством параметров шрифтов мы понимаем множество T=<F, K>, где F - множество типов шрифтов и K - множество размеров шрифтов. В статье не рассматриваются вопросы, связанные с условиями реализации, а лишь имеется ввиду, что даже при фиксированном типе шрифта и фиксированном размере шрифта существует множество вариаций печатных изображений одного символа.

Системы распознавания печатных символов можно разбить на два класса: шрифтозависимые системы и шрифтонезависимые (омнифонтовые) системы.

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

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

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

Более точно эту задачу можно сформулировать следующим образом.

Пусть A - множество символов алфавита некоторого языка, F - множество типов шрифтов и K - множество размеров шрифтов. Пусть заданы aÎA, fÎF и kÎK. Обозначим через I(a, f,k) - множество изображений символа a, соответствующих шрифту типа f и размера k.

Множеством изображений символа a будем называть множество .

Отображение j, ставящее в соответствие изображению x(a) символа a некоторый бинарный растр j(x(a)), назовем сканированием, а сам бинарный растр будем называть графическим образом (или просто образом) символа a.

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

Будем обозначать через G(a, f,k) - множество графических образов j(I(a, t,k)) символа a с типом шрифта t и кеглем k. Аналогично, через G(a, t) обозначим множество графических образов j(I(a, t)) символа a с типом шрифта t, а через G(a) - множество всех графических образов j(I(a)) символа a.

Процедурой автоматического распознавания символов назовем процедуру , которая обладает следующим свойством. Пусть G(A, f,k) - некоторое множество графических образов символов алфавита A, представленных в виде суммы непересекающихся множеств , где fÎF - тип шрифта, а kÎK - его размер или кегль. Тогда на основании информации T(G(A, f,k)) о множествах G(an, f,k) процедура ставит в соответствие произвольному графическому образу t символ an, такой, что . Множество G(A, t,k) будем называть обучающим множеством.

Заметим, что, согласно этому определению, информация T(G(A, f,k)), вообще говоря, зависит от конкретных значений типа шрифта и его размера, хотя процедура осуществляет распознавание для любых значений fÎF и kÎK.

Процедура распознавания будет называться кегленезависимой, если обучающее множество G(A, f) представлено в виде разбиения , а сама процедура на основании информации T(G(A, f)) о множестве G(an, f) ставит в соответствие произвольному образу t символ an, такой, что . Здесь информация, которую использует процедура , уже не зависит от конкретного размера шрифта.

Наконец, назовем процедуру распознавания шрифтонезависимой, если обучающее множество G(A) представлено в виде разбиения , а сама процедура на основании информации T(G(A)) о множествах G(an) ставит в соответствие произвольному графическому образу t символ an, такой, что . В этом случае информация, используемая процедурой , не зависит уже ни от типа шрифта, ни от его размера.

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

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

1. Основные определения

Определение 1. Назовем растром целочисленную матрицу , где m и n - количество строк и столбцов в матрице, а - целые неотрицательные числа для всех i= и j=. (Для удобства такой растр будем называть серым).

Определение 2. Растр , где i= и j=, будем называть бинарным, если каждый элемент может принимать только два значения - 0 или 1.

Пример бинарного растра, который изображает символ “т”, показан на рис.2.

Рис.2. Бинарный растр символа “т”

Определение 3. Назовем точкой растра , где i=, j=, пару чисел (i, j), где i и j - значения индексов элемента . Будем обозначать ее P(i, j). Назовем значением растра в точке P(i, j).

Определение 4. Два растра R1(m1, n1) и R2(m2, n2) называются равновеликими, если m1= m2 и n1= n2.

Определение 5. Пусть R1(m, n)= и R2(m, n)= - два равновеликих растра. Будем говорить, что растр R1(m, n) вложен в растр R2(m, n) и обозначать это как R1(m, n)ÍR2(m, n), если выполнено условие для всех i=, j=.

Из этого определения, в частности, следует, что если R1(m, n) и R2(m, n) - бинарные растры, и для всех i=, j= выполнены условия:

, ,

то R1(m, n)ÍR2(m, n).

2. Операции над растрами

Сумма растров. Пусть S - произвольное множество равновеликих растров S=, где k=, i= и j=. Тогда суммой этих растров назовем растр R (m, n)= такой, что

.

Бинаризация растра. Пусть (m, n)= - произвольный растр, где i= и j=, а b - любое положительное число. Отображение Y((m, n), b) в бинарный растр R(m, n)= назовем бинаризацией растра (m, n) по порогу b, если

.

Замечание: Выбор того или иного значения порога b влияет на степень искажения графического образа. Представляется естественным в качестве порога бинаризации для растров размера m´n выбрать среднее значение элементов растра:

, (1)

где - элемент бинаризуемого серого растра.

Сжатие растра. Пусть - бинарный растр. Тогда преобразование растра в растр R(m, n) называется сжатием растра и формально определяется следующим образом.

, где l=, k= и i=, j=.

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

Сначала выполним преобразование по следующему правилу:

, где m(l-1) < p £ ml и n(k-1) < q £ nk.

Затем определим .

После этой операции отобразим полученный серый растр R(m, n) в бинарный растр с помощью операции бинаризации.

Замечание: В процедуре распознавания использовалось сжатие растра произвольного размера к растру размера 16´16.

Пересечение растров и замыкание растров. Пусть S=- множество равновеликих бинарных растров, N - количество растров этого множества, k=, а R(m, n) - сумма всех растров этого множества. Тогда бинарный растр Z(m, n)=Y(R(m, n), b), полученный бинаризацией растра R(m, n) по порогу b, назовем пересечением растров или скелетным образом множества S, если b=N-a, где aÎ[0; N). Растр Z(m, n) назовем замыканием растров или расширенным образом множества S, если b=g, где gÎ[1; N) [1]. В дальнейшем для удобства скелетный образ будет обозначаться как SKEL(S, a)=, а расширенный - как COVER(S, g)=.

Теорема 1. Пусть S=- множество равновеликих бинарных растров, |S|=N и B(m, n) - произвольный растр из множества S. Тогда выполняется соотношение SKEL(S,0)ÍB(m, n)ÍCOVER(S,1).

Доказательство. По определению скелетного образа растр SKEL(S,0) получается из растра бинаризацией по порогу N, то есть элемент растра SKEL(S,0) равен 1 в том и только в том случае, если соответствующие элементы всех растров множества S равны 1, а иначе он равен 0. Отсюда, если некоторый элемент растра B(m, n) равен 0, то соответствующий элемент скелетного образа тем более равен 0. Следовательно, выполняется вложение SKEL(S,0)ÍB(m, n).

С другой стороны, согласно определению расширенного образа, растр COVER(S,1) получается из растра бинаризацией по порогу 1. Это означает, что элемент растра COVER(S,1) равен 0 в том и только в том случае, если соответствующие элементы всех растров множества S равны 0. Следовательно, если некоторый элемент растра B(m, n) равен 1, то соответствующий элемент расширенного образа тем более равен 1. А это означает выполнение вложения B(m, n)ÍCOVER(S,1).Теорема доказана.

Инверсия растра. Пусть дан бинарный растр R(m, n)= , где i= и j=. Тогда его инверсией назовем растр (m, n)= такой, что

.

3. Процесс обучения

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

Прежде всего рассмотрим задачу формирования эталонных образов.

3.1. Построение базы эталонов

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

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

Для каждого символа anÎA построим его скелетный образ SKEL(G(an),an) и расширенный образ COVER(G(an),gn), где an и gn - пороговые параметры, выбираемые при выполнении операций пересечения и замыкания растров, результатами которых являются скелетный и расширенный образы. Пара этих растров и является эталонами символа an. Множество таких эталонов для всех anÎA образует базу эталонов.

Следует отметить, что пороговые параметры an и gn, выбираемые при формировании базы эталонов, могут быть различными для различных символов an. Однако, если положить an=0 и gn=1 для всех n, то для любого растра RÎG(an) согласно теореме 1 будет выполнено вложение SKEL(S,0)ÍRÍCOVER(S,1). Это соотношение позволяет сделать вывод, что обучающее множество G(A), в некотором смысле, полностью представлено базой эталонов, сформированной при указанных значениях пороговых параметрах. При других значениях пороговых параметров аналогичное соотношение может не выполняться.

3.2. Построение бинарных деревьев

Рассмотрим обучающее множество , где A - множество символов алфавита языка.

Пусть по обучающему множеству уже построена база эталонов, представляющая собой совокупность двух множеств: множества скелетных образов S= и множества расширенных образов C=, где = - скелетный образ символа an, = - расширенный образ символа an, а a и g - параметры. Очевидно, что если |A|=N, то и |S|=|C|=N.

Построим по множеству скелетных образов бинарное дерево TS следующим образом.

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

Предположим, что уже построено дерево, состоящее из n вершин, где n³1. Рассмотрим произвольную вершину V дерева, еще не имеющую потомков. Согласно построению, ей соответствует некоторое подмножество символов A(V)ÍA. Построим для нее две вершины-потомка Vleft и Vright. Для этого выберем произвольную точку растра P(iV, jV). Поставим в соответствие вершине Vleft множество символов

, (2)

а вершине Vright - множество символов

. (3)

То есть левому потомку вершины V будем ставить в соответствие символы, скелетные образы которых в точке P(iV, jV) принимают значения 0, а правому потомку - символы, скелетные образы которых принимают в этой точке значения 1. Точку P(iV, jV) будем называть точкой ветвления в вершине V.

Концевой вершиной или «листом» дерева будем считать любую вершину Vk, для которой соответствующее ей множество символов A(Vk) нельзя разбить на два непустых подмножества, удовлетворяющих условиям (2) и (3).

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

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

. (4)

В этом случае, если |A|=N, то это число не превосходит log2N+1. Очевидно также, что с помощью построенного дерева для любого скелетного образа SKEL(G(an),a)= не более чем за log2N проверок значения этого образа в точках ветвления можно найти тот лист дерева, которому поставлен в соответствие символ an. Для этого мы в очередной вершине V дерева TS, начиная с его корневой вершины, вычисляем значение растра в точке ветвления для этой вершины. Если это значение равно 0, то переходим к вершине-потомку Vleft, а если оно равно 1, то к вершине-потомку Vright. Из описания процесса построения дерева TS ясно, что в конце концов мы придем в некоторую вершину Vk, такую, что anÎA(Vk). В этом смысле можно сказать, что бинарное дерево TS представляет множество скелетных образов.

Таким же образом можно построить бинарное дерево TC для множества расширенных образов C= с аналогичными свойствами.

В действительности, при построении деревьев TC и TS такой точки ветвления, которая бы удовлетворяла условию (4), может и не найтись. Поэтому точнее условие выбора для вершины V точки ветвления P(iV, jV), обеспечивающее максимальную дихотомию при разбиении множества символов, можно описать как поиск минимума

. (5)

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

4. Неполное распознавание

Определение. Пусть g(an) - произвольный графический образ символа anÎA. Для корневой вершины V дерева TS вычисляем значение растра g(an) в точке ветвления P(iV, jV). Если это значение равно 0, переходим к вершине Vleft, а если оно равно 1, к вершине Vright. Повторяем этот процесс для вершины, к которой перешли, и продолжаем его до тех пор, пока не дойдем до некоторой концевой вершины Vk. Ставим в соответствие растру g(an) множество символов A(Vk).

Описанный процесс установления соответствия будем называть неполным распознаванием графического образа g(an) по дереву TS.

Определение. Неполное распознавание называется правильным, если anÎA(Vk).

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

В качестве значений параметров при формировании базы эталонов возьмем a=0 и g=1, то есть база эталонов будет состоять из множества скелетных образов S= и множества расширенных образов C=.

Тогда справедлива следующая теорема.

Теорема 2. Пусть - обучающее множество, S=- множество скелетных образов и C=- множество расширенных образов. И пусть при построении бинарного дерева TS по множеству скелетных образов точка ветвления P(iV, jV) для вершины дерева V выбирается так, что выполняются следующие условия:

A1(V)¹Æ, Q1(V)¹Æ, |A1(V)|+|Q1(V)|=|A(V)|=N(V), (6)

где A(V) - множество символов anÎA, соответствующее вершине V;

A1(V)=;

Q1(V)=.

Тогда неполное распознавание любого графического образа g(an)ÎG(A) по дереву TS является правильным. (Напомним, что растр является инверсией растра .)

Для доказательства этой теоремы докажем сначала следующую лемму.

Лемма. Пусть A0(V)= и Q0(V)=. Тогда при выполнении условий теоремы 2 справедливы равенства: A1(V)= Q0(V), A0(V)= Q1(V).

Доказательство. Из определения множеств A0(V), A1(V), Q0(V), Q1(V) следует выполнение равенств:

, , (7)

, . (8)

Из теоремы 1 о вложении следует, что для любого an, если =1, то , а, значит . Отсюда вытекает, что

A1(V)ÍQ0(V). (9)

Из равенств (8) следует

|Q0(V)|+|Q1(V)|=N(V). (10)

Отсюда

|Q0(V)|=N(V)-|Q1(V)|. (11)

Но из равенства (6) следует, что

|A1(V)|=N(V)-|Q1(V)|. (12)

Из (11) и (12) получаем

|A1(V)|=|Q0(V)|. (13)

Из последнего равенства, учитывая вложение (9), можем сделать заключение, что

A1(V)=Q0(V). (14)

Используя равенства (8), (9) и (14), получаем

A0(V)=A(V)\A1(V)= A(V)\Q0(V)= Q1(V). (15)

Таким образом, равенства (14) и (15) показывают, что лемма верна.

Доказательство теоремы 2. Обозначим бинарный растр, представляющий графический образ g(an), через R(m, n)=. Для доказательства теоремы достаточно доказать, что если для некоторой вершины V дерева TS в точке ветвления P(iV, jV) =0, то и =0, а если =1, то и =1. Тогда, согласно алгоритму построения дерева TS и алгоритму распознавания графического образа по этому дереву, при распознавании g(an) переход от вершины V всегда будет происходить к той вершине-потомку, которой при построении дерева был поставлен в соответствие символ an.

Итак пусть =0. Тогда по теореме 1 о вложенных множествах =0.

Пусть теперь =1. Тогда по теореме 1 =1, откуда =0. Но из леммы следует, что Q0(V)=A1(V). Значит, =1. Теорема доказана.

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

Как видно из теоремы 2, выполнение условия (6) при выборе точки ветвления обеспечивает правильность неполного распознавания по бинарному дереву. Однако, как уже отмечалось при описании алгоритма построения бинарного дерева, для того, чтобы обеспечить максимальную дихотомичность при построении дерева, к этому условию при выборе точки ветвления для вершины V следует добавить требование минимальности выражения .

Теорема 3. Если P(iV, jV) - точка ветвления для вершины V бинарного дерева, то она не может быть точкой ветвления ни для какой другой вершины поддерева, начинающегося в вершине V.

Доказательство. Рассмотрим бинарное дерево TS, построенное для скелетных образов. По определению точки ветвления множество A(V) символов, соответствующих вершине V, разделяется на два непустых непересекающихся подмножества A(Vleft)= и A(Vright)=.

Рассмотрим произвольную вершину поддерева, начинающегося в вершине Vleft. Ей соответствует некоторое подмножество множества A(Vleft), поэтому для всех символов этого подмножества выполняется равенство =0. Следовательно, это подмножество не может быть разделено на две непустые части со значениями =0 и =1. Значит, точка P(iV, jV) не является точкой ветвления для рассматриваемой вершины.

Такой же вывод можно сделать и для любой вершины поддерева, начинающегося в вершине Vright, поскольку для всех символов множества A(Vright) выполняется равенство =1.

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

Из этой теоремы вытекает очевидное следствие.

Следствие 1. Рассмотрим произвольную ветвь бинарного дерева. Все точки ветвления для вершин этой ветви являются различными.

Следствие 2. Любая ветвь бинарного дерева конечна.

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

5. Мера близости между распознаваемым и эталонным образами

Пусть - обучающее множество, где A - множество символов алфавита языка. Как уже отмечалось, эталонные символы, построенные по обучающему множеству, представляются в виде скелетных и расширенных образов = и =, где i= и j=.

Распознаваемый символ представлен в виде уже сжатого и бинаризованного растра R(16, 16)= , где i= и j=.

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

. (16)

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

Теорема 4. Пусть имеется множество A символов алфавита и множество G(A) графических образов этих символов , причем все образы имеют размер 16´16. Тогда определяемое по формуле (16) расстояние между произвольным графическим образом g(an)ÎG(an) и эталонными образами SKEL(G(an),a) и COVER(G(an), g), где a=0, g=1, будет равняться нулю.

Доказательство. Достаточно рассмотреть только те слагаемые суммы в формуле для вычисления меры близости, которые могут быть равны 1.

Однако из теоремы 1 следует, что, если в некоторой точке графического образа SKEL(G(an), 0) стоит 1, то в этой же точке образа g(an) стоит тоже 1, а если в точке графического образа COVER(G(an),g) стоит 0, то в этой же точке образа g(an) тоже стоит 0. Таким образом, даже эти слагаемые равны нулю. Теорема доказана.

6. Распознавание символов по бинарному дереву

Приведем описание полного процесса распознавания произвольного графического образа.

Прежде всего этот графический образ предварительно нормализуется. Процесс нормализации основан на определенной выше операции сжатия, причем растр сжимается до размера 16´16. Так как при выполнении операции сжатия происходит бинаризация серого растра, то эта бинаризация выполняется при двух различных значениях порога. Одно из значений вычисляется по формуле (1), другое равняется 1. В результате после завершения операции сжатия для одного графического образа получаются два бинарных растра. Обозначим первый из них через B(16,16)=, а другой через W(16,16)=. На рис.3 изображен пример нормализации символа по двум различным порогам.

Рис.3. Пример построения нормализованных образов

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

Аналогично происходит неполное распознавание бинарного растра W(16,16) по дереву расширенных образов и определяется символ, эталонный образ которого наиболее близок к этому растру. В итоге получаются два символа, из которых выбирается тот, для которого соответствующее расстояние оказалось меньшим.

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

7. Экспериментальная проверка метода распознавания

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

Рис.4. Образцы шрифтов.

Необходимо заметить, что результаты тестирования, приведенные в таблицах, отражают качество распознавания при использовании только лишь процедуры, описанной в пункте 6. На самом деле при построении деревьев в концевые множества часто попадают группы близких по начертанию символов: {н, и, п}, {е, с}, {з, э} и т. п. В связи с этим на этапе определения эталонного символа, ближайшего к распознаваемому, часто происходит неправильный выбор символов из таких групп. Но с этой проблемой успешно справляются другие методы, описанные в [2], поэтому результаты, приведенные ниже, можно значительно улучшить при подключении более точных методов определения близости.

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

Таблица 1

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

Таблица 2

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

Таблица 3

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

Таблица 4

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

8. Определение близости шрифтов

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

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

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

Таблица 5

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

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

1.  Если эталонные и распознаваемые символы имеют близкие по начертанию типы шрифтов, то неправильно распознанные символы не могут иметь большие штрафы, в отличие от случая, когда типы шрифтов отличаются по начертанию.

2.  При распознавании символов с типами шрифтов, близкими к эталонным, на гистограмме можно выделить явно выраженный локальный максимум в пределах отрезка [0; 30], а для далеких типов шрифтов локальные максимумы нечетки и «размазаны» по отрезку [0; 40].

3.  Для близких типов шрифтов процент выброса не принимает значений больше единицы, а для далеких типов процент выброса значительно больше единицы.

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

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

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

ВЫВОДЫ

Рассмотренный метод древовидного распознавания нормализованных символов был встроен в шрифтозависимую систему “Tiger”, в результате чего эта система стала кегленезависимой. Сравнительные результаты работы исходной системы и модифицированной приведены в табл.6.

Таблица 6

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

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

СПИСОК ЛИТЕРАТУРЫ

1.  Браверман методы обработки эмпирических данных. - М.: Наука, 1983.

2.  , Славин распознавания и технологии ввода текстов в ЭВМ. //Информационные технологии и вычислительные системы, 1996 N1.