Математическая модель распознавания символов

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

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РАСПОЗНАВАНИЯ СИМВОЛА

Обозначим через          последователь ность стенографических символов. К сожалению, очень часто стенографические символы определяются неоднозначно. Для символа xk обозначим через         множество его воз можных распознаваний. Каждому распознанному символу определяются его возможные трактовки         . Тогда распознанный текст примет вид         . Ставится задача найти такой набор индексов, чтобы вероятность правильного распознавания была максимальной.

P ( y;* - y 2) = max P ( берется по всем

y ^{1 i 1} … y ^{ni n} , где максимум j 1             j n

' <  m . .

n          ni_n .

‘ 1 <  ‘ 1 , - j 1 - m l 1 , ^— , Оценим вероятность

P ( y j - y 1: ) .

На основании формулы Байеса она равна

P ( y j 1 - y j) = P ( y j ) - P V.

ni _n j_n

n -1 l <

⁽    ) n-1

jn - 1

. (1)

Оценка k -го ( k > 3) сомножителя в правой части формулы (1) имеет вид:

P y k^k j

¹ ‘ 1      y ⁽ t ^{- 1 )} i k—1

)

= aP (xk ) +

A

+ ( 1 — a ) P у t tk I

y ⁽ k ^{3 )} it - 3     y ⁽ k ^{- 1 )} ‘ k-1

^jt - 3          ^jt - 1      у

.

Оценка t -го сомножителя при t <  3 производится аналогично. Коэффициент a настраивается в зависимости от качества распознавания стенограммы.

ОЦЕНКА ПЕРВОГО СЛАГАЕМОГО МАТЕМАТИЧЕСКОЙ МОДЕЛИ

Первое слагаемое в правой части формулы (2) характеризует точность распознавания стенографического символа. Оно вычисляется как:

P ( x ^k ) = e - ^а ‘ ^{р ( x} k ’ y) ⁹ ‘,                      (3)

где P ( x_i ^k , y_i ) – это расстояние от текущего символа до ^k эталона y_i класса символов. Для каждого класса находим ρⁱ _точ – минимальное расстояние от эталона класса до элементов из другого класса и ρⁱ _пол – максимальное расстояние от эталона класса до элементов класса. На наших данных оказалось, что ρⁱ _точ <  ρⁱ _пол . Параметры формулы (3) подбираются как решение следующей системы:

.

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

Таблица 1

Расчет коэффициентов для символов обучающей выборки

Символ			α	β
г	400	1200	0,001766	0,907297
	400	1000	0,00059	1,08782
	500	1000	0,000053	1,4380

ОЦЕНКА ВТОРОГО СЛАГАЕМОГО МАТЕМАТИЧЕСКОЙ МОДЕЛИ

Второе слагаемое математической модели (2) является вероятностью появления данного фрагмента в тексте. Она оценивается как

P y k k j

y ( ^k"^ - 3 _ y ( ^k - 1 ) i k-1 jk - 3          jk - 1      у

N ( У ( k ^- 3^{)i k - 3} •" yj "k k )

N ( У ⁽ k ^{- 3 ) i k} - ³ У ⁽ k ^{- 1 )} ' ^k — ¹ ) + 1

где N ( y ^{- 3 ) i k - 3} _ y k*^ ^k )

– частота появления фраг-

(k 3) ik-3         k мента текста yjt3   ••• yjt . Данные числовые

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

Для вычисления оценки вероятности (4) строились пятерки слов yjk-5)'k-5 • ykkk, так как они дают более точное указание авторства, нежели пары или тройки. Для вычисления таких вероятностей необходимо было построить матрицы вероятностей встречи данного слова после всех возможных четверок слов в данных произведениях. Учитывая, что общее количество слов порядка 80 тысяч, оценок значений вероятностей включения данных четверки и пятерки в тексте будет порядка 512 триллионов. Однако, несмотря на то что большое количество из всех возможных пятерок слов не встречаются в тексте и матрица пятерок будет сильна разреженной, ее хранение и построение довольно трудозатратно.

Для построения данной матрицы использовался следующий алгоритм:

• 1.    Пронумеровать все слова, используемые в тексте, так, чтобы они получили следующие координаты: идентификатор текста, в котором встречается данное слово, порядковый номер предложения в тексте, содержащего данное слово, и порядковый номер слова в данном предложении. В нашем случае была использована база знаний Smalt [2], в которой данная операция была произведена раньше.

• 2.    Далее строятся всевозможные пятерки слов N ( y ^{( k - 3 )} ' ^{k - 3} • y ^{ki k} ) с таким условием, что у слов в данном словосочетании равны идентификаторы текста и предложения, а порядковые номера в словосочетании идут по возрастанию.

• 3.    Из полученных пятерок выбираются уникальные и высчитывается количество включения их в текст. В 28 рассматриваемых произведениях из 80 тысяч слов было составлено порядка 69 тысяч уникальных пятерок слов.

• 4.    Для тех пятерок, которые не были построены, можно считать, что вероятность включения их в текст равна 0.

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

Таблица 2

Частота и вероятность появления пятерок слов

Пятерка слов	Частота появления	Оценка вероятности
Не смотря на то что	11	0,8461
Ни съ того ни съ	3	0,75
Корпорація студентовъ какъ особое званіе	2	0,66
Теплѣй человѣчеству нежели отъ словъ	2	0,66
Этихъ ошибокъ этихъ примѣровъ всякаго	2	0,66

РЕАЛИЗАЦИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ В ИНФОРМАЦИОННОЙ СИСТЕМЕ

Разрабатываемая информационная среда для дешифровки исторических стенограмм будет предлагать различные варианты распознавания текста. Более подробно о разрабатываемой системе и ее отдельных модулях говорится в работах [1], [4], [5]. После того как пользователь системы выделил символы, система разбила их на строки, выделив надстрочные и подстрочные символы, происходит расшифровка стенограммы согласно следующему алгоритму.

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

• 2.    Пусть k – количество символов левее искомого в рассматриваемой строке. Если k < 5, то при расшифровке используется группа символов из k . Иначе рассматриваются пятерки слов.

• 3.    Обозначим у¹, y² , ..., у / - возможные расшифровки символа S_i . Исходя из всех возможных комбинаций расшифровок { y jк , у²^ + 1 ,-, y j } вероятность появления данного фрагмента в тексте рассчитывается по формуле (4).

• 4.    Используя все вероятности, полученные в пункте 3, и оценки вероятностей, полученных в пункте 9, находим максимальную вероятность правильной расшифровки по формуле (2), умножив при этом второе слагаемое на вероятность того, к какому типу (основной, подстрочный, надстрочный) относится данный символ.

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

ЗАКЛЮЧЕНИЕ

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

• *    Работа выполнена при поддержке Программы стратегического развития ПетрГУ в рамках реализации комплекса мероприятий по развитию научно-исследовательской деятельности на 2012–2016 гг.

MATHEMATICAL MODEL OF CHARACTER RECOGNITION