УДК 004.93'12

МГТУ им. Н.Э. Баумана

izelentsov@gmail.com

Y_philippovich@mail.ru

Введение

В работах [1, 2] предложена методика распознавания древнерусской скорописи XVII в. В её основе лежит структурный метод распознавания букв и слов скорописи, построенный на использовании знаний эксперта в области палеографии. Экспертные знания о структуре начертаний букв и слов скорописи предлагается хранить в формализованном виде в организованной по принципам фреймовой сети базе знаний (БЗ). В работе [3] приводится теоретическое описание структуры БЗ системы на уровне абстрактных объектов распознавания. Описан принцип использования БЗ при распознавании абстрактных образов: он заключается в анализе присутствующих на изображении структурных элементов образов и их сопоставлении с имеющимися в БЗ структурными описаниями. Структура описаний в БЗ позволяет направлять процесс распознавания при помощи выдвижения гипотез относительно наблюдаемых объектов. В той же работе сформулирован алгоритм распознавания абстрактных образов и доказаны его сходимость и корректность.

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

1.   Распознавание букв

1.1      Структурное описание букв

На рисунке 1 приведены примеры начертания букв скорописи, являющиеся объектами распознавания модуля “распознаватель букв” (РБ) системы.

Рисунок 1 - Примеры букв скорописи XVII в.

где       D   = {d ∣ ДетализируемыйУзел(d)} – множество детализируемых узлов;

            E    = {e ∣ Элемент(e)} – множество элементов;

            F    = {f ∣ ВхождениеСвойства(q)} – множество вхождений свойств;

            Q   = {q ∣ ВхождениеЭлемента(q)} ⊆ F– множество вхождений элементов;

            R    = {r ∣ ВхождениеОтношения(r)} ⊆ F – множество вхождений отношений.

Расширим терминологию базы знаний для введения возможности описания структуры распознаваемых букв.

Узлы, описывающие в базе знаний буквы скорописи, имеют тип Буква. Неотъемлемым атрибутом каждого из таких узлов является код представляемой им буквы. Каждая буква имеет по крайней мере один способ начертания. Собственно, начертание буквы и является предметом распознавания в рассматриваемой задаче, поэтому для описания структур начертаний букв вводится тип узлов НачертаниеБуквы, подтип ДетализируемогоУзла. Узлы-Буквы, как будет пояснено в последующих разделах, входят в структуры слов и, следовательно, являются Элементами.

Буква                        ≡ Элемент ⊓ (= 1 имеетКод.Число) ⊓

                     ⊓ (имеетНачертаниеБуквы ⊆ имеетОписание) ⊓

                     ⊓ (≥ 1 имеетНачертаниеБуквы.НачертаниеБуквы);

НачертаниеБуквы   ⊑ ДетализируемыйУзел.

В структурных описаниях начертаний букв потребуется указание относительного расположения элементов на изображении и их относительных размеров. Для этой цели вводится набор отношений с общим надтипом ПространственноеОтношение (подтип ВхожденияОтношения). Для отражения того факта, что один Элемент расположен слева от другого, строится узел типа Слева-Справа, слот слева которого ссылается на ВхождениеЭлемента, расположенного левее, а слот справа — на ВхождениеЭлемента, расположенного правее. Аналогично вводятся узлы типа Выше-Ниже (со слотами выше и ниже), Больше-Меньше-Верт (со слотами больше-верт и меньше-верт) и Больше-Меньше-Гор (со слотами больше-гор и меньше-гор). Последние два типа отношений показывают относительность вертикальных и горизонтальных размеров элементов. При этом каждый узел вхождения пространственного отношения снабжается значением степени данного отношения в диапазоне [0;1], используемым при определении предположительного расположения одного элемента при известном положении другого.

Отношения Выше-Ниже, Больше-Меньше-Верт и Больше-Меньше-Гор определены аналогично отношению Слева-Справа. В данный момент рассмотрения можно сказать, что множество отношений R из выражения (1) можно представить как

где       R_LR– множество вхождений отношений типа Слева-Справа, R_HL– типа Выше-Ниже, R_LSV– типа Больше-Меньше-Верт,            R_LSH– типа Больше-Меньше-Гор.

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

Рисунок 2 - Декомпозиция букв скорописи на отдельные штрихи

Для представления линий во фреймовой сети вводится тип узлов Линия, являющийся подтипом Элемента. Узел этого типа содержит слот путь, хранящий непосредственное значение четкого измерения пути линии в виде строки, а также слот форма, который указывает значение характеристического угла диагонали описывающего прямоугольника линии. Связи типа имеетОписание для узлов-Линий не используются, т.к. в данной методике построения БЗ линии являются наиболее элементарными объектами. Вводится также особый тип узлов для описания ВхожденийЛиний:

Линия                      ≡ Элемент ⊓ (= 1 путь.Строка) ⊓ (= 1 форма.Число);

ВхождениеЛинии    ≡ ВхождениеЭлемента ⊓ ∃индицирует.Линия ⊓

⊓ ∀детализирует.НачертаниеБуквы.

Для описания точек пересечений вводится тип узлов Точка как подтип Элемента. Точки имеют по два слота-значения, отражающих их позицию внутри области содержащих их линий:

Точка                    ≡ Элемент ⊓ (= 1 горПоз.Число) ⊓ (= 1 вертПоз.Число);

ВхождениеТочки  ≡ ВхождениеЭлемента ⊓ ∃индицирует.Точка ⊓

                    ⊓ ∀детализирует.НачертаниеБуквы.

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

Рисунок 3 - Описание пересечения двух линий

ПринадлежностьТочки ≡ ВхождениеОтношения ⊓

               ⊓ (точка ⊆ включаетВхождение) ⊓

               ⊓ (принадлежитЛинии ⊆ включаетВхождение) ⊓

               ⊓ (= 1 точка.ВхождениеТочки) ⊓

               ⊓ (= 1 принадлежитЛинии.ВхождениеЛинии) ⊓

               ⊓ ∀детализирует.НачертаниеБуквы;

СоответствиеТочек   ≡ ВхождениеОтношения ⊓

               ⊓ (соответствующаяТочка ⊆ включаетВхождение) ⊓

               ⊓ (= 2 соответствующаяТочка.ВхождениеТочки) ⊓

               ⊓ ∀детализирует.НачертаниеБуквы.

Теперь можно сказать, что в множество Dиз (1) входят узлы типа НачертаниеБуквы. Множество E составляют узлы типа Буква, Линия и Точка. Содержание множества R расширяется по отношению к (3) узлами ПринадлежностиТочек и СоответствияТочек. Таким образом,

где       D_L – множество узлов-НачертанийБукв, E_L – множество узлов-Букв, E_LN – множество узлов-Линий, E_PT – множество узлов-Точек, Q_LN – множество узлов типа ВхождениеЛинии, Q_PT – множество ВхожденийТочек, R_простр – множество узлов типа ПространственноеОтношение, R_PB – множество узлов типа ПринадлежностьТочки, R_PC – типа СоответствиеТочек.

На рисунке 4 приведён пример фрейма, описывающего начертание буквы ’а’. Под собственно “фреймом буквы” на рисунке подразумевается узел типа НачертаниеБуквы, а также все остальные узлы (с общим надтипом ВхождениеСвойства), кроме узла типа Буква. Узлы с типом ВхождениеСвойства имеют не показанные на рисунке связи типа детализирует с узлом типа НачертаниеБуквы.

Рисунок 4 - Пример фрейма начертания буквы ’а’

На рисунке 5 проиллюстрирован общий принцип построения фреймовых описаний букв. Множество фреймов с корневыми узлами типа НачертаниеБуквы содержат собственные узлы типа ВхоаждениеСвойства, ссылающиеся на набор разделяемых всеми фреймами узлов типа Элемент, т.е. Линии и Точки.

Рисунок 5 - Структурные описания букв и их начертаний

Рассмотрим некоторые количественные характеристики введённых фреймовых описаний начертаний букв. В зависимости от фактического наполнения БЗ может характеризоваться следующими показателями:

Среднее число вхождений линий в начертании (фрейме):

Среднее число вхождений линий различных типов в начертании:

Среднее число вхождений линии данного типа во все начертания БЗ:

Среднее число вхождений линии данного типа в одно начертание буквы БЗ:

Среднее число пересечений линий в начертаниях:

Оценим среднее число узлов-вхождений в описание одного начертания буквы. Оно может быть представлено в виде суммы чисел узлов-вхождений всех типов элементов и отношений. Заметим, что каждая пара узлов типа ВхождениеЛинии связывается четвёркой узлов пространственных отношений и, возможно, группами  узлов, описывающих пересечения линий. Каждое пересечение линий описывает пятёркой узлов: пара узлов типа ВхождениеТочки, пара соответствующих ПринадлежностейТочек и связывающий узел СоответствиеТочек. Итак:

1.2      Весовые функции для фреймов букв

Рассмотрим произвольный фрейм-НачертаниеБуквы a∈D_L. Учитывая, что F(a) = Q(a) ∪ R(a) и выражение (4), введём функцию w_L : F(a) → ℝ над наборами вхождений элементов начертаний букв F(a) следующим образом:

где α_LN, α_PT, α_простр∈ℝ ≤ 0 – весовые коэффициенты вхождений линий, точек и пространственных отношений соответственно, каждый из которых неотрицателен.

Утверждение 1. Функция w_L(F(a)) является функцией веса по определению 1 [3].

Доказательство.

1.          Покажем, что ∀F(a)  w_L(F(a)) ≥ 0. Это утверждение выполняется вследствие того, что все члены произведений в сумме (7) неотрицательны по определению.

2.          Покажем, что F(a₁) ⊆ F(a₂) ⇒ w_L(F(a₁)) ≤ w_L(F(a₂)). Поскольку F(a₁) ⊆ F(a₂),  то будет выполняться

|Q_LN(a₁)| ≤ |Q_LN(a₂)| ∧ |Q_PT(a₁)| ≤ |Q_PT(a₂)| ∧ |R_простр(a₁)| ≤ |R_простр(a₂)|.

Следовательно,

w_L(F(a₂)) - w_L(F(a₁)) = (|Q_LN(a₂)| - |Q_LN(a₁)|) α_LN + (|Q_PT(a₂)| - |Q_PT(a₁)|) α_PT +

+ (|R_простр(a₂)| - |R_простр(a₁)|) α_простр ≥ 0.

3.          Покажем, что F(a₁) = F(a₂) ⇒ w_L(F(a₁)) = w_L(F(a₂)). Это доказывается аналогично предыдущему свойству, исходя из очевидного утверждения

F(a₁) = F(a₂) ⇒  |Q_LN(a₁)| = |Q_LN(a₂)| ∧ |Q_PT(a₁)| = |Q_PT(a₂)| ∧

∧ |R_простр(a₁)| = |Rпростр(a₂)|.

∎

Введём также функцию веса w_L : h → ℝ для гипотезы h относительно НачертанияБуквы.

где S_LN(h) = { s∈S(h)  |  (узелБЗ(s,f) ∪ узелВФ(s,f) ⇒ ВхождениеЛинии(f)) }, а остальные члены определяются по аналогии. Все весовые коэффициента неотрицательны.

Утверждение 2. Функция w_L(h) является функцией веса по определению 2 [3].

Доказательство.

1.          Свойство ∀h w_L(h) ≥ 0 выполняется т.к. все члены произведений в сумме (8) неотрицательны по определению.

2.          S(h₁)⊆S(h₂)  ⇒  w_L(h₁) ≤ w_L(h₂). Доказательство аналогично доказательству свойства 2 для функции w_L (7) с учётом утверждения

S(h₁) ⊆S(h₂) ⇒ |S_LN(h₁)| ≤ |S_LN(h₂)| ∧ |S_PT(h₁)| ≤ |S_PT(h₂)| ∧

∧ |S_простр(h₁)| ≤ |S_простр(h₂)|.

3.          S(h₁) = S(h₂) ⇒ w_L(h₁) = w_L(h₂). Доказательство аналогично доказательству свойства 3 для функции w_L (7) с учётом утверждения

S(h₁) = S(h₂) ⇒ |S_LN(h₁)| = |S_LN(h₂)| ∧ |S_PT(h₁)| = |S_PT(h₂)| ∧

∧ |S_простр(h₁)| = |S_простр(h₂)|.

4.          ∀hw_L(h) = w_L(S^БЗ(h)) = w_L(S^ВФ(h)). Доказательство следует из очевидного факта, следующего из определения проекций схем согласования (4) из [3]:

∀T  |S(h)| = |S_T^БЗ(h)| = |S_T^ВФ(h)|.

∎

Весовые коэффициенты в весовых функциях вводятся для учёта различия значимости соответствующих элементов структурных описаний для процесса согласования фреймов, что будет пояснено в разделе 1.3. Необходимо также определить весовую функцию проверенности. Она используется для вычисления степени проверенности N^пров(h) гипотез [3]. Её задачей является вычисление веса набора узлов с учётом только тех типов узлов фрейма-НачертанияБуквы, которые являются существенными для распознавания. Определим весовую функцию проверенности фрейма-НачертанияБуквы w_LП : F(a)  → ℝ следующим образом:

Данная функция учитывает только количество ВхожденийЛиний в указанном наборе узлов. По свойствам весовая функция проверенности для букв w_LП (9) аналогична весовой функции (7), что не трудно показать.

1.3      Правила согласования элементов букв

В соответствии с правилами согласования узлов БЗ и ВФ, введёнными в [3], ВхожденияЭлементов могут быть согласованы, если они индицируют один и тот же Элемент, а ВхожденияОтношений согласуются только тогда, когда все связываемые ими ВхожденияЭлементов соответственно согласованы. Усилим данные правила, учитывая специфику отношений линий и точек их пересечений в структуре начертания буквы: не имеет смысла согласовывать совпадающие узлы точек пересечения, если линии, которым они принадлежат, не согласованы между собой.

Таким образом, вхождения точек q_PT(d) и q_PT() можно согласовать, если они индицируют одну Точку p и принадлежат уже согласованным линиям:

согласован(q_PT(d),q_PT()) ⇒ индицирует(q_PT(d),p) ∧ индицирует(q_PT(),p) ∧

        ∧ принадлежит(q_PT(d), q_LN(d)) ∧ принадлежит(q_PT(), q_LN()) ∧

        ∧ согласован(q_LN(d), q_LN()).

1.4      Алгоритм распознавания букв

Рассмотрим алгоритм распознавания букв, реализуемый модулем “распознаватель букв“ (РБ) системы распознавания. Данный алгоритм представляет собой спецификацию алгоритма распознавания абстрактных образов, описанного в [3], для описанной выше буквенной структуры БЗ. Он руководствуется принципом выдвижения и проверки гипотез относительно наблюдаемой в конкретный момент времени буквы (точнее, её конкретного начертания). Проверка гипотез осуществляется путём вызова входящего в структуру системы распознавания модуля трассировки изображения.

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

Основу алгоритма составляет процедура согласования линии, выполняющая проверку одной из линий начертания буквы в гипотезе. В начале работы процедуры согласования имеется набор гипотез, одна из которых (h_тек∈H, предполагает(h, a∈D_L)) назначена текущей, и во всех гипотезах фигурирует вхождение согласуемой линии. При этом гарантировано, что в текущей гипотезе вхождение текущей линии q_LN1(a)∈Q_LNв фрейме БЗ согласовано с ВФ, т.е.

∃q_LN1() ∈ Q_LN()  согласован(q_LN1(a), q_LN1(), h_тек).

Отталкиваясь от текущей линии q_LN1(a) (рис. 6), по описанию фрейма aв БЗ можно узнать, какие точки пересечения должна иметь эта линия в наблюдаемой букве. Выполняется перебор этих точек, для каждой из которых выполняется следующее. Для текущей точки q_PT1(a) определяется вид ожидаемой пересекающей линии e_LN2, и эта информация передаётся трассировщику в виде гипотезы. Пусть от него получен ответ в виде линии искомого вида. Если фактически найденная линия не пересекает в ожидаемом месте исходную линию, то это может означать, что изображённая буква либо имеет дефект в виде отсутствия пересечения, либо текущая гипотеза не верна. В этом случае в ВФ добавляется только узел вхождения q_LN2() найденной линии e_LN2. В противном же случае можно считать, что наблюдаемое пересечение неслучайно. В этом случае в ВФ заносятся ещё и вхождения q_PT1() и q_PT2() соответствующих друг другу текущих точек пересечения e_PT1 и e_PT2, вхождения принадлежностей r_PB1() и r_PB2() этих точек своим линиям, а также вхождение отношения их соответствия r_PC(). Для всех указанных узлов строятся отношения согласования с соответствующими узлами вхождений в текущем фрейме БЗ.

Рисунок 6 - Согласование пересекающей линии

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

Алгоритм 1. Распознавание букв.

Начало

1.    Найти на изображении линию известного вида.

2.    Выдвинуть первоначальный список гипотез в соответствии с правилом (5) [3].

3.    Цикл:

4.       Вычислить характеристики всех имеющихся гипотез.

5.       Удалить гипотезы, нарушившие полное условие пригодности У^п.приг (9) [3]

6.       Если не осталось гипотез:

7.          Вернуть ошибку.

8.          Конец алгоритма

9.       Если есть подтверждённые по У^подтв (10) [3] гипотезы и выполняется
              ∄h∈H : У^п.приг(h) ∧ 

10.         Вернуть подтверждённую гипотезу с максимальной N^согл.

11.         Конец алгоритма

12.      Выбрать рабочую гипотезу hпо правилу (11) [3].

13.      Выбрать в фрейме БЗ a∈D_L (предполагает(h,a)) вхождение линии q_l
            из множества Q_LN(a) \ Q_LN^пров(h).

14.      Выполнить Q^пров(h) ← Q^пров(h) ∪ q_l.

15.      Вызвать модуль трассировки для поиска линии, описываемой q_l.

16.      Если линия найдена:

17.         Поместить фактическую информацию о найденной линии в ВФ.

18.         Согласовать новые узлы ВФ во всех гипотезах с учётом правила (8) [3].

19.         При необходимости выдвинуть новые гипотезы.

20.   Конец цикла.

Конец алгоритма

Данный алгоритм отличается от алгоритма распознавания абстрактных образов [3] тем, что операции проверки выполняются над наборами ВхожденийЛиний в структурах начертаний букв. При этом для вычисления характеристик гипотез используются функции (7), (8) и (9) из раздела 1.2.

Как и в случае распознавания абстрактных образов, при добавлении в ВФ очередного узла в фрейме-НачертанииБуквы может найтись более одного элемента, которые могут быть согласованы с новым узлом, что приводит к «расщеплению» соответствующей гипотезы. Если считать, что в среднем начертание содержит  различных линий, каждая из которых входит в структуру начертания в среднем с округлением  раз, то общее число альтернативных гипотез, которые могут быть выдвинуты относительно данного начертания, т.е. общее число возможных согласований данного фрейма начертания с ВФ, равно

Утверждение 3. Алгоритм 1 завершается за конечное число шагов.  

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

Для случая букв можно утверждать, что в среднем

 = |{q∈ Q : индицирует (q, x)}| = .

. Учитывая (10), (5) и (6), выражение (11) можно переписать в виде

∎

Выражение (11) позволяет утверждать, что время выполнения алгоритма 1 пропорционально числу фреймов-начертаний _|DL| в БЗ. На время выполнения алгоритма также значительно влияет среднее количество линий в начертаниях и наличие в начертаниях букв однотипных линий.

Утверждение 4. Если алгоритм 1 завершается успешно, то ответом будет наблюдаемая буква.

Доказательство. Доказательство аналогично доказательству соответствующего утверждения относительно распознавания абстрактных образов в [3].

Стоит только заметить, что, согласно алгоритму 1, в качестве ответа возвращается гипотеза h относительно начертания буквы, удовлетворившая необходимым условиям. Ясно, что собственно код буквы, соответствующей распознанному начертанию, нетрудно получить как:

имеетКод (e∈E_L) : (имеетНачертаниеБуквы(e, d∈D_L) ∧ предполагает(h, d) )

∎

2      Распознавание слов

2.1      Структурное описание слов

На рисунке 7 приведён пример двух строк скорописи, показывающий общий характер начертания слов: расположения слов в строках, взаимного расположения букв в словах.

Рисунок 7 - Пример скорописного начертания слов

Структурные фреймовые описания изображений слов строятся аналогично описаниям изображений букв. Узлы-Слова являются Элементами. Основным атрибутом Слова является строка-последовательность кодов составляющих его букв. Каждое Слово имеет структуру в виде последовательности составляющих его букв. По аналогии с описаниями букв, введём для описания структур слов узлы типа НачертаниеСлова с надтипом ДетализируемыйУзел. В принципе, произвольное слово может иметь множество возможных начертаний. В данной работе количество узлов-НачертанийСлов на каждое Слово ограничивается числом 1, т.к. вариативность начертания букв отрабатывается на уровне распознавания букв, а для описания слова считается достаточным указание только последовательности букв. Элементами слов являются узлы-Буквы, присутствие которых в структуре слова обозначается узлами типа ВхождениеБуквы.

Слово                       ≡ Элемент ⊓ (= 1 слово.Строка) ⊓

                   ⊓ (имеетНачертаниеСлова ⊆ имеетОписание) ⊓

                   ⊓ (≥ 1 имеетНачертаниеСлова.НачертаниеСлова);

НачертаниеСлова  ⊑ ДетализируемыйУзел;

ВхождениеБуквы    ≡ ВхождениеЭлемента ⊓ ∃индицирует.Буква ⊓

                   ⊓ ∀детализирует.НачертаниеСлова;

Отношениями букв являются пространственные отношения Слева-Справа. Эти отношения определяют последовательность расположения изображений букв в изображении слова. Специфика древнерусской скорописи определяет возможность расположения букв слова одна над другой, т.е. некоторые буквы в слове могут появляться над основным рядом букв. Эту особенность можно было бы выразить при помощи отношений типа Выше-Ниже, указывая таким образом буквы, располагающиеся над другими буквами. Однако, правила скорописи [4] не устанавливают чётких условий вынесения буквы в надстрочное положение. Таким образом, целесообразно описывать в БЗ только линейную последовательность букв в слове.

Множества узлов-Слов и узлов-НачертанийСлов в БЗ будут обозначаться соответственно через

Множество узлов-вхождений в фрейме-НачертанииСлова будет записываться как F(b) = {f(b)}, где b ∈ D_W. Из определения пространственного отношения Слева-Справа (2) и из того факта, что в описаниях слов данный тип отношений служит для описания взаимного расположения ВхожденийБукв, следует, что для некоторого вхождения отношения Слева-Справа (r(b))   b ∈ D_W всегда будут верны утверждения

Таким образом, базу знаний (4), дополненную структурными описаниями слов скорописи, можно представить в следующем виде:

где       D = D_W∪ D_L,

            E = E_W∪ E_L∪ E_LN∪ E_PT,

            Q = Q_L∪ Q_LN∪ Q_PT,

            R = R_простр ∪ R_PB∪ R_PC

(D_W – множество узлов-НачертанийСлов, E_W – множество узлов-Слов, Q_L – множество узлов-ВхожденийБукв).

На рисунке 8 приведён пример фреймового описания слова. Под “фреймом слова” понимается узел типа НачертаниеСлова, который раскрывает структуру абстракции Слова “полпуда”. Узлы типа ВхождениеБуквы и Слева-Справа имеют не показанные на рисунке связи типа детализирует с узлом типа НачертаниеСлова. Стоит отметить, что буква ’л’ в приведённом примере начертания является надстрочной. Однако, вхождение этой буквы связано с соседними ВхождениямиБукв отношением Слева-Справа, а не Выше-Ниже. Кроме того, отметим, что в структуре данного слова два узла типа ВхождениеБуквы ссылаются на один и тот же узел типа Буква с кодом ’п’.

Рисунок 8 - Пример фрейма начертания слова “полпуда”

Иллюстрация общего принципа построения фреймовых описаний слов в БЗ приведена на рисунке 9. Каждый узел типа Слово имеет по одному фрейму типа НачертаниеСлова, описывающему структуру данного слова. Узлы типа НачертаниеСлова ссылаются на наборы узлов типа ВхождениеБуквы и Слева-Справа, описывая состав детализируемого слова.

Рисунок 9 -Структурные описания слов в БЗ

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

(b∈ D_W,  F(b) ⊆ F)  =  (b,  Q_L(b) ⊆ Q∪ R_LR(b) ⊆ R).

Рассмотрим количественные характеристики введённых фреймовых описаний слов. В зависимости от фактического наполнения БЗ может характеризоваться следующим показателем:

Среднее число букв в слове:

Среднее число вхождений букв с различными кодами в слове:

Среднее число вхождений буквы с данным кодом во все слова БЗ:

Среднее число вхождений букв с данным кодом в одно слово БЗ:

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

2.2      Весовые функции для фреймов слов

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

Определим функцию w_W : F(b) → ℝ над наборами вхождений элементов начертаний слов F(b), b∈D_W следующим образом:

где α_L, α_LR∈ ℝ ≥ 0 – весовые коэффициенты ВхожденийБукв и пространственных отношений Слева-Справа соответственно, каждый из которых неотрицателен.

Утверждение 5. Функция  является функцией веса по определению 1 [3].

Доказательство. Доказательство аналогично доказательству утверждения 1.

∎

Определим функцию веса w_W: h → ℝ для гипотезы h относительно произвольного начертания слова:

где S_L(h) = { s∈S(h) : (узелБЗ(s, f) ∪ узелВФ(s, f) ⇒ ВхождениеБуквы(f)) },  а второе слагаемой определяются по аналогии для типа узлов Слева-Справа.

Утверждение 6.  Функция w_W(h) является функцией веса по определению 2 [3].

Доказательство. Доказательство аналогично доказательству утверждения 2.

∎

Весовую функцию проверенности гипотез слов w_WП: F(b) → ℝ определим как

Функция (16) аналогична по свойствам введённой ранее функции (9). Её действие заключается в подсчёте узлов-ВхожденийБукв в наборе проверенных узлов.

2.3      Правила согласования элементов слов

Некоторые буквы в начертаниях слов скорописи могут выноситься над строкой. При этом нет чётких правил, в соответствии с которыми можно определить, должна ли конкретная буква в слове иметь надстрочное начертание. Поскольку описания начертаний слов в БЗ содержат информацию о взаимном расположении букв в слове только в терминах “слева-справа”, необходимо предусмотреть возможность согласования надстрочных букв в ВФ со строчными в БЗ.

Для этого введём следующее требование к согласуемым буквам в составе слова. Как и в случае абстрактных ВхожденийЭлементов, два ВхожденияБуквы могут быть согласованы, если они индицируют один и тот же элемент-Букву. Если согласуемый узел слова в БЗ связан пространственным отношением Слева-Справа с ранее согласованным узлом БЗ, то согласуемый узел ВФ должен быть связан с соответствующим ранее согласованным узлом ВФ либо тем же отношением, либо отношением Выше-Ниже, где слот ниже в ВФ соответствует слоту слева в БЗ, а слот выше в ВФ — слоту справа в ВФ. В противном случае согласование не устанавливается.

Отметим, что если буква на изображении имеет надстрочное начертание, то фрагмент слова, находящийся в области основного ряда букв (в строке) будет иметь пропуск. Например, если в фрагменте слова abc буква b будет вынесена над строкой, то в строке останутся буквы ac. В ВФ при этом буквы a и c будут связаны отношением Слева-Справа, которое отсутствует между этими буквами в БЗ (т.к. этим отношением связываются только соседние буквы). В этих условиях по введённому выше правилу при согласованных узлах букв a и b узлы буквы c согласовать не удастся. Поэтому при согласовании следует допустить подмену отношения Слева-Справа в БЗ отношением Слева-Справа⁺ (транзитивным замыканием).

Пространственные отношения могут быть согласованы, если они одинаковым образом связывают согласованные узлы-ВхожденияБукв, причём узел Слева-Справа в БЗ может быть согласован с узлом Выше-Ниже в ВФ, если значения слотов этих узлов соответствуют описанному выше условию.

2.4      Алгоритм распознавания слов

Задачу распознавания слов в рассматриваемой методике распознавания выполняет модуль “распознаватель слов” (РС). Алгоритм его работы, аналогично алгоритму модуля РБ, является спецификацией алгоритма распознавания абстрактных образов [3] для словарной составляющей БЗ.

Приведённый ниже алгоритм 2 описывает действия РС при поиске одного слова на изображении. Общая схема работы алгоритма заключается в попытке отыскания всех букв наблюдаемого слова, где поиск каждой последующей буквы отталкивается от фактического месторасположения найденных ранее букв. За выделение структурных элементов начертаний слов (букв) на изображении отвечает описанный выше модуль РБ. В отличие от модуля трассировки линий изображения, этот модуль, получая от РС запрос на поиск определённой буквы, трактует это указание лишь как “подсказку”, а не как точное задание. Т.е. ответом РБ является фактически найденная буква, даже если она не совпадает с запрашиваемой. В случае, если ни одной буквы найти не удалось, возвращается ошибка. Следует отметить, что из-за возможности надстрочного начертания букв при получения ошибки от РБ выполняется повторная попытка поиска той же буквы, но в надстрочной области слова (см. шаг 13).

Алгоритм можно представить следующим образом:

Алгоритм 2. Распознавание слов.

Начало

1.    Распознать на изображении одну из известных букв.

2.    Выдвинуть первоначальный список гипотез в соответствии с правилом (5) [3].

3.    Цикл:

4.       Вычислить характеристики всех имеющихся гипотез.

5.       Удалить гипотезы, нарушившие полное условие пригодности У^п.приг (9) [3].

6.       Если не осталось гипотез:

7.          Вернуть ошибку.

           Конец алгоритма

8.       Если есть подтверждённые по У^подтв (10) [3] гипотезы и выполняется
              ∄h∈H : У^п.приг(h) ∧

9.          Вернуть подтверждённую гипотезу с максимальной N^{согл}.

           Конец алгоритма

10.      Выбрать рабочую гипотезу h по правилу (11) [3].

11.      Выбрать в фрейме БЗ b∈D_W (предполагает(h,b)) вхождение буквы q_l
           из множества Q_L(a) \ Q_L^пров(h).

12.      Выполнить Q^пров(h) ← Q^пров(h) ∪q_l.

13.      Вызвать модуль РБ для поиска буквы, описываемой q_l (с учётом
           возможности надстрочного начертания).

14.      Если буква найдена:

15.         Поместить фактическую информацию о найденной букве в ВФ.

16.         Согласовать новые узлы ВФ во всех гипотезах с учётом правила (8) [3].

17.         При необходимости выдвинуть новые гипотезы.

18.   Конец цикла.

Конец алгоритма

Как и алгоритм 1, данный алгоритм является спецификацией алгоритма распознавания абстрактных образов [3], причём операции выполняются над наборами ВхожденийБукв в структурах начертаний слов с использованием весовых функций (14), (15) и (16) из раздела 2.2.

Оценим степень «расщепления» гипотез относительно слов при добавлении узлов в ВФ. Пусть в среднем слово содержит  различных букв, каждая из которых входит в структуру начертания слова  в среднем с округлением  раз. По правилам согласования ВхожденийБукв, описанных в разделе 2.3, согласовываться могут узлы букв, соответствующие с известными оговорками по отношениям Слева-Справа⁺ с другими узлами. Можно считать, что в среднем половина повторных вхождений одной конкретной буквы в состав слова не удовлетворяет этим правилам. Тогда общее число альтернативных гипотез, которые могут быть выдвинуты относительно данного начертания, т.е. общее число возможных согласований данного фрейма начертания с ВФ, можно оценить как

Утверждение 7. Алгоритм  завершается за конечное число шагов.

Доказательство.Доказательство аналогично доказательству утверждения 3 в разделе 1.4. Максимальное число узлов, которые необходимо проверить для одной гипотезы относительно начертания слова, выражается как

,

что, с учётом выражений (17), (12), (13), а также утверждение, что в среднем, последнее выражение можно переписать в виде

В соответствии с (18), время выполнения алгоритма 2 пропорционально числу фреймов- начертаний |D_W| в БЗ. Кроме того, алгоритм квадратично зависит от количества букв в слове и факториально — от числа повторяющихся букв.

Утверждение 8. Если алгоритм 2 завершается успешно, то ответом будет наблюдаемое слово.

Доказательство.Доказательство аналогично доказательству соответствующего утверждения относительно распознавания абстрактных образов в [3].

Если в качестве результата работы алгоритма 2 возвращается гипотеза h относительно начертания слова, то кодовую цепочку, соответствующую распознанному слову можно получить двумя способами. Цепочка-эталон, соответствующая согласованному фрейму из БЗ, может быть получена как

слово(e∈E_W) : (имеетНачертаниеСлова(e, d∈D_W) ∧ предполагает(h, d) ).

Реально обнаруженная цепочка, с учётом выносных и, возможно, пропущенных букв, получается склейкой кодов узлов-Букв из набора:

имеетКод(e∈E_L)  ∀e : ∃q∈Q()  индицирует (q, e).

∎

Заключение

В статье рассмотрены методы распознавания букв и слов скорописи XVII в., представляющие собой конкретизированные версии описанной ранее методики распознавания абстрактных образов. Для каждой из этих предметных областей введены особые фреймовые структуры базы знаний, вся совокупность которых составляет единую фреймовую сеть структурных описаний объектов распознавания системы. Исследованы некоторые количественные характеристики данных структур. Введены конкретные весовые функции, которые позволяют в процессе распознавания вычислять характеристики гипотез, выдвигаемых относительно данных структур. На основе данных характеристик принимаются решения относительно отклонения и принятия гипотез, а также относительно выбора наиболее правдоподобной гипотезы на каждом конкретном шаге распознавания. Далее сформулированы правила согласования получаемых из изображения структурных элементов букв и слов с их описаниями в БЗ. Наконец, приведены специализированные алгоритмы распознавания букв и слов. Эти алгоритмы наследуют свои основные свойства от алгоритма распознавания абстрактных образов; в данной работе приведён анализ их характерных специфических свойств.

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

Список литературы

1.             Зеленцов И.А. Метод распознавания древнерусской скорописи // Компьютерная графика и математическое моделирование (Visual Computing): Сб. тез. и докл. науч. школы для молодых учёных. М., 2009. С. 116–131.

2.            Зеленцов И.А. Выдвижение и проверка гипотез в системе распознавания древнерусской скорописи // Информационные технологии и письменное наследие: Материалы междунар. науч. конф. Уфа ‑ Ижевск, 2010. С. 99–101.

3.          Зеленцов И.А., Филиппович Ю.Н. Распознавание образов на основе структурных фреймовых описаний в скорописных текстах XVII в. //http://technomag.edu.ru «Наука и образование: электронное научно-техническое издание» выпуск 12. 2011
//http://technomag.edu.ru/doc/296744.html (дата обращения 30.11.2011).

4.             Черепнин Л. В. Русская палеография. М.: Изд-во политической литературы, 1956. 616 с.