автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели, методы и алгоритмы дешифровки исторических стенограмм

На правах рукописи

Г

Скабин Артём Викторович '

МАТЕМАТИЧЕСКИЕ МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ ДЕШИФРОВКИ ИСТОРИЧЕСКИХ СТЕНОГРАММ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

5 ДЕК 2013

Петрозаводск 2013

005543165

Работа выполнена на кафедре теории вероятностей и анализа данных ФГБОУ ВПО «Петрозаводский государственный университет»

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Доктор технических наук, профессор Рогов Александр Александрович

Жабко Алексей Петрович, доктор физико-математических наук, профессор, заведующий кафедрой теории управления ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Суровцова Татьяна Геннадьевна,

кандидат технических наук, старший преподаватель кафедры прикладной математики и кибернетики ФГБОУ ВПО «Петрозаводский государственный университет»

ФГБУН Санкт-Петербургский институт информатики и автоматизации РАН

Защита состоится «26» декабря 2013г. в 11:00 часов на заседании диссертационного совета Д 212.190.03 на базе ФГБОУ ВПО «Петрозаводский государственный университет» по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

С диссертацией можно ознакомиться в научной библиотеке Петрозаводского государственного университета.

Автореферат разослан «£.!..» ноября 2013 г.

Ученый секретарь диссертационного совета

Р. В. Воронов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования.

Автоматизированное распознавание рукописных текстов востребовано в различных областях человеческой деятельности. Существует большое количество различных разработок для решения данной задачи. Большой вклад в развитие оптического распознавания рукописных символов внесли ученые Н. Д. Горский, В. Л. Арлазаров, А. А. Маса-лович, В. Анисимов.

Существующие системы оптического распознавания (ABBYY FineReader, CuneiForm, Google Tesseract) ориентированы на распознавание современных языков и печатных текстов. Исходными данными для таких систем являются документы хорошего качества, как первоисточник (страницы рукописей, четкие, контрастные снимки, с четко разделенным фоном и символами), так и хорошего написания (строки прямые, без искривлений, отсутствие исправлений и зачеркиваний).

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

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

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

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

Степень разработанности темы исследования.

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

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

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

1. провести анализ существующих информационных систем оптического распознавания символов;

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

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

4. разработать алгоритм поиска схожих символов;

5. построить математическую модель дешифрования символов;

6. разработать численный метод определения параметров математической модели;

7. реализовать разработанные алгоритмы в компьютерной системе.

Научная новизна:

1. описан алгоритм подбора наилучшего метода бинаризации исторических рукописных документов;

2. предложен пороговый метод, основанный на яркостной характеристике с плавающим порогом;

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

Методология и методы исследования: Использованы методы теории вероятностей, математической и прикладной статистики, численные методы кластерного анализа, вычислительной геометрии и обработки изображений.

Положения, выносимые на защиту:

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

2. математическая модель дешифровки стенографических документов, содержащая информацию как о форме и месте символов, так и извлеченную из текстов автора;

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

4. программный комплекс (ИС Шв!^), реализующий предложенный метод выбора бинаризации стенографического документа и использующийся для построения алфавита стенографического текста и дальнейшей дешифровки стенограммы.

Теоретическая и практическая значимость.

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

Степень достоверности.

Достоверность результатов проведенных исследований подтверждена проведением исследований рукописных стенографических записей Сниткиной (Достоевской) Анны Григорьевны — наброски к «Дневнику Писателя» за 1881 г. и «Из воспоминаний А. Г. Достоевской».

Апробация работы.

1. Результаты диссертационного исследования были представлены на следующих конференциях:

2. V Международная научная конференция «Компьютерные технологии и математические методы в исторических исследованиях» (Петрозаводск, 2013);

3. VII Международная научно-практическая конференция «Информационная среда ВУЗа XXI века» (Петрозаводск, 2013);

4. XIV Всероссийская научная конференция «Электронные библиотеки: Перспективные методы и технологии, электронные коллекции 11СЮЬ'2012» (Переславль—Залесский, 2012);

5. Всероссийская научная конференция «Анализ изображений, сетей и текстов АИСТ'12» (Екатеринбург, 2012);

6. IV Международная научная конференция «Информационные технологии и письменное наследие ЕГМапшспр!—2012» (Петрозаводск, 2012);

7. VI Международная научно-практическая конференция «Информационная среда ВУЗа XXI века» (Куопио, Финляндия, 2012);

8. V Международная научно-практическая конференция «Информационная среда ВУЗа XXI века» (Петрозаводск, 2011);

9. Международная конференция «Компьютерные технологии и математические методы в исторических исследованиях» (Петрозаводск, 2011);

10. XIV Всероссийская конференция «Интернет и современное общество» (Санкт—Петербург, 2011);

Проведенные исследования производились в рамках гранта Российского гуманитарного научного фонда на тему «Автоматизированная система распознавания и дешифровки стенограмм XIX — начало XX вв.» № 11-01-12026 (руководитель Рогов А. А.). Программы для ЭВМ, входящие в состав программного комплекса, были зарегистрированы в Объединённом фонде электронных ресурсов «Наука и образование» (ОФЭР-НиО) № 19509 от 23.09.2013. По теме исследования опубликовано 11

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

Структура и объём диссертации. Диссертация состоит из введения, трёх глав, заключения, библиографического списка использованной литературы (107 наименований), имеет объём 101 страницу машинописного текста, содержит 41 рисунок и 8 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

неравномерно: центр светлее, чем края документа;

2. плохое состояние исходных документов:

a. наличие механических повреждений;

b. зачеркивание и исправления в тексте;

c. просвечивание записей с обратной стороны;

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

3. большое количество шума (черных пикселей, не относящихся к символам записи) после бинаризации документа (более 30%).

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

Использование порогового метода для бинаризации заключается в выборе порога по какой-либо из цветовых характеристик таким

образом, чтобы разделить пиксели изображения на два класса: те пиксели значение цветовых компонент которых меньше заданного порога, принадлежат к классу символов, а те, у которых больше,— к классу фона. Проведены эксперименты со стенографическими документами, как видно на рисунке 1, ни одна из компонент цветовых схем RGB и HSB не даёт явного разделения на два класса.

красный

I

0481423 3241 50596877 6695105 118 131 14« 1S7 170 183 196 209 222 235 248

ш

0481423 3241 50596877 8695105 118 131 144 157 170 183 196 209 222 235248

насыщенность

с» Л10» Ч

0481423 3241 ЕО 59 6877 8695105 118 131 144 157 170 183 196 209 222 235 248

и

t't'OJ3241 Ю»>68</ 84>>106 118 I}' 14« 1£7Т{ 1M1G

б.

Рисунок 1. Гистограммы RGB (а) и HSB (б)

Для обработки данных стенографических документов в диссертационном исследовании предложен пороговый метод, основанный на яр-костной цветовой компоненте, с выбором порога, основываясь на плотности текста (модифицированный пороговый метод — МПМ). Бинаризация выполняется по цветовому свойству — яркость. Порог бинаризации выбирается в зависимости от плотности текста. В рассматриваемых стенографических документах плотность текста составляла 13% пикселей от общей площади текста.

На рисунке 2 продемонстрированы результаты работы некоторых методов бинаризации: методы Отцу, Бернсена, Эйквеля, Ниблэка, пороговый метод, основанный на яркостной цветовой компоненте (МПМ), фрагмент предобработанный гауссовским размытием, бинаризованный МПМ.

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

[0,

Пусть х^ = [ '—пиксельнаконтрольномфрагменте.полученномпри

Г0

бинаризации к—ым методом бинаризации. х(™л = | '— пиксель на эталонном бинаризованном фрагменте, где { = 1, ... , п; ) = 1, ... , т; п,т —

Оригинальный фрагмент

^ *

Метод Бернсена

^ у с

м 'Г у, <м V

Эталонный фрагмент Метод Отсу

ЩШф- штш

Метод Эйквеля Метод Ниблэка

й? '

, ^о —о: / л-о; с

Гауссовское размытие

Гаусс + МПМ

Рисунок 2. Результаты работы некоторых методов бинаризации

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

п т

А, 2-, I ^ ~ х^ал I ш'п (1)

¡=1 ]=1

Для каждого из методов бинаризации рассчитывается точность (2), полнота (3) и Б—мера (Б1—мера) (4) по следующим формулам:

5

V Я

Еп ут Ьк ' ¿=1 У=1

Еп у т „этал -¿=1 Л у=1

(2) (3)

/^-мера = — (4)

р+ч

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

На рисунке 3 представлены результаты эксперимента. Проведённый анализ основанный на Б-мере показал, что чаще наиболее подходящим является МПМ метод бинаризации.

Сравнение результатов работы методов

і

0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 ОД о

Отцу

Бернсена

Эйквеля

Ниблэка

ш

МПМ

Гаусс + МПМ

^Точность

0,8637

0,7362

0,5111

0,4398

0,8165

0,8284

□ Полнота

0,6684

0,7841

0,7228

0,7703

0,7717

0,7433

Я F-мера

0,753602

0,759395

0,598789

0,559917

0,793468

0,783612

Рисунок 3. Сравнение методов бинаризации

Во втором параграфе первой главы рассматриваются методы выделения связных областей на бинарных изображениях, в третьем параграфе — методы поиска схожих символов такие как: логическое сравнение с эталоном, сравнение со скелетом эталона, метод сравнения расстояний, метод моментов, комбинированный метод, метод корзин. Алгоритм метода корзин выглядит следующим образом: Шаг 1. На символе произвольно выбираются 100 пикселей см. рисунок 4-а. Данная операция выполняется для двух сравниваемых символов;

Шаг 2. Для каждого пикселя строится 60 «корзин» см. рисунок 4-Ь; Шаг 3. Для каждого пикселя считается количество пикселей, попавших в каждую из корзин, тем самым получаем 60-ти разрядные вектора для каждого из выбранных пикселей;

Шаг 4. Решается оптимизационная задача нахождения минимального расстояния между векторами, которая в данном диссертационном исследовании решается венгерским методом.

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

Рисунок 4. Построение корзин для вычисления расстояния

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

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

вид Надо найти такой набор индексов, чтобы вероятность

правильного распознавания была максимальной.

р(у"! ...у"'" )= тах р[у"' ■••>'"'"), где максимум берется по всем ].<;,.</,,

На основании формулы умножения вероятностей она равна:

р{Уи.....= .....зЫ (5)

Оценим вероятность р(у''' ...у"'") ■ Оценка сомножителя формулы (5) при 3 < к <5 выглядит следующим образом:

с ( 4

К УА 11. (»-!),„ , V ...у К К (»-1)1, (1-1)1,., у " J ...у " 1

й * >\ ■ 1 у \ 1,-1 '»-I у

Для к < 3, оценка вероятности упрощается. Первое слагаемое формулы (6) оценивает точность распознавания стенографического символа. Второе слагаемое формулы (6) оценивает насколько данный фрагмент текста, принадлежит автору. Коэффициент а настраиваются в зависимости от качества распознавания стенограммы.

Первое слагаемое формулы (6) заключается в оценке точности распознавания символа. Точность распознавания символа рассчитывается

по формуле Д(х^) = е , где — расстояние от теку-

щего символа, до эталонного г1 класса. Т.е. среди всех классов символов, использующихся при записи данных стенографических документов, необходимо найти те, расстояние до которых минимально. Для расчёта данного расстояния необходимо знать коэффициенты /3, и у,.,которые вычисляются исходя из системы уравнений (7).

(— — е-РМ оч)7'

\31 (7)

) 1 = е-йСриЯ

Где р'тт — расстояние, при котором появляется первое вхождение символа не схожего с текущим, р'поп— расстояние при котором вошли все символы из данного класса, схожие с текущим. В диссертационном исследовании расчёт расстояния был произведен при помощи метода корзин. В таблице 1 приводятся расстояния, коэффициенты /3, у для некоторых символов.

Таблица 1

Расстояния, полученные методом корзин

Символ Р точ Р пол /5 У

г 400 1200 0,001766 0,907297

400 1000 0,00059 1,08782

500 1000 0,000053 1,4380

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

строится линия аппроксимации по центрам символов (см. рисунок 5), оценка рассчитывается по следующей формуле: Тк = — оценка вероятности того, что символ является основным,Тк = 1 — е~5Е —

г нвосн

оценка вероятности того, что символ является подстрочным или надстрочным. Где £ — расстояние от центра символа до линии аппроксимации, д — настроечный параметр.

Оценка второго слагаемого формулы (6) заключается в оценки появления данного фрагмента текста и равна:

(8)

(

kL

уи У -г /-'Хы

V 'к-г 4-1 7

N

АГ +1

Рисунок 5. Построение линии аппроксимации

Где ■ ■■yj") частота появления фрагмента текста yjt

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

Для вычисления оценки вероятности (8) строились пятерки слов

yf ■■■Ук'/к ■ Для этого необходимо было построить матрицы количества вхождения данного слова после всех возможных четверок слов в произведениях. Для вычислений использовался словарь программной системы Smalt. В базе данных данной системы находится порядка 80 ООО слов. Расчёт оценок появления пятерок эквивалентен построению сильно разряженной матрицы большой разрядности в таблице 2 представлены наиболее часто встречаемые тройки, четверки и пятёрки слов, с рассчитанной для них оценкой появления в тексте.

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

Таблица 2

Частота встречаемости и оценка вероятности появления в тексте троек, четвёрок, пятерок

Пятерки слов Частота появления Оценка вероятности появления в тексте

Не смотря на то что 11 0,84

Ни сътого ни съ 3 0,75

Корпорація студентовъ какъ особое званіе 2 0,66

Четверки слов

Несмотря на то 12 0,52

И проч и проч 11 0,84

Все болье и бол-ье 10 0,9

Тройки слов

До сихъ поръ 52 0,96

Въ томъ что 27 0,44

Не смотря на 22 0,91

Программный комплекс включает в себя следующие составляющие:

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

1.1 Методы обработки изображений;

1.2 Инструменты поиска схожих символов.

2. Модуль обработки полученных данных, включающий в себя:

2.1 Инструменты редактирования бинарного представления;

2.2 Инструменты редактирования полученных данных.

3. Программа тестирования и подбора методов бинаризации;

4. Информационная система формирования алфавита с возможностью просмотра различных написаний и отображения символов и их расположения на исходном документе;

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

5.1 Инструменты дешифровки символов, с представлением пользователю возможных вариантов трактовок;

5.2 Инструменты редактирования дешифровок стенограмм.

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

б

Выбрать | | |

Редактировать выбранные

6 ННКсд

Файл Распознавание

□ Зачеркнутый символ [~~1 Не стенографический символ Выбрать из базы знаний

Л!

Рисунок 6. Внешний вид модуля обработки стенограммы Основное окно программы представляет собой две области. В левой области находится оригинальное изображение (оригинальная стенограмма), на которой пользователь выделяет необходимый символ. Место выделения отображается на второй области. В данной области находится обработанная стенограмма, т.е. все полученные ранее символы, находящиеся в местах, соответствующих символам в оригинальном изображении. Далее система производит бинаризацию выделенного фрагмента и поиск связных областей. Если сегментов получено несколько, то система предлагает пользователю выбрать, какой сегмент или сегменты соответствуют оригинальному символу. При выборе нескольких сегментов, система производит связывание разорванных «кусков» и предлагает пользователю результат. В случае, когда результат устраивает пользователя, символ записывается в базу знаний и располагается

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

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

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

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

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

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

ЗТЕМОСЛАРНУ

Выход [Скабии] Р Поиск...

Ш: -

Щ а

., Я, ,э .

щш. шШш & й ¿„^ ^

> Ш Н Щ , .- • Щ0ШШ& \

С.": / Щ .<•• . 'ЩШК&, С-..'/-' щф щ щ ■ --о /-'/ с ШМ

С еЖ Г: -ЦУ^*/?) '.р.-

¿'¿1 уУо.у. **. а-

¿К-

V/-

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

Я плохой литератор и может быть написала что-нибудь лишнее, а потону пршу Вас вычеркнуть из неё то,

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

О.О.Ц.Ко поступала в высшей < »гношении книг Дост. Направляемые с этим письма я

факты

доставила управляющему Ком. ~>ного просвящения и образования. Это свидетельствуют

фактами

представленные мною факты. ^

материал

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

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

ЗАКЛЮЧЕНИЕ

Основные результаты диссертационного исследования:

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Рогов А. А. Бинаризация и выделение символов исторической стенограммы / А. А. Рогов, А. В. Скабин // Ученые записки Петрозаводского государственного университета. Серия «Естественные и технические науки». —2013. —№ 4 (133). — С. 110—115.

2. Гиппиев М. Б. Распознавание строк в стенографических документах/М.Б. Гинпиев, A.B. Жуков, A.B. Скабин, A.A. Рогов//Современные проблемы науки и образования. — электрон, ст. — М.: Издательский дом "АКАДЕМИЯ ЕСТЕСТВОЗНАНИЯ, 2013. — № 4. — Режим доступа: http://www.science—education.ru/110—9725.

3. Рогов А. А. Математическая модель распознавания символов / А. А. Рогов, А. В. Скабин // Ученые записки Петрозаводского государственного университета. Серия «Естественные и технические науки». —2013. —№ 6 (135). — С. 73—76.

4. Skabin A. Computerized Recognition System for Historical Manuscripts // Proceedings of 2nd International Workshop on Concept Discovery in Unstructured Data 2012 (Leuven, Belgium — May 2012). — Leuven, Belgium, 2012. — P. 87 — 94.

5. Рогов А. А. О дешифровке рукописных исторических документов / А. А. Рогов, А. В. Скабин, И. А. Штеркель // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды XIV Всероссийской научной конференции RCDL 2012. — С. 111—117.

6. Скабин А. В. Автоматизированная система распознания рукописных исторических документов. / A.B. Скабин, И.А. Штеркель // Доклады всероссийской научной конференции «Анализ Изображений Сетей и Текстов» (АИСТ'12) (Екатеринбург — 2012). — С. 245—254.

7. Рогов А. А. Автоматизированная информационная система распознавания исторических рукописных документов. / A.A. Рогов, А. В. Скабин, И.А. Штеркель // Информационная среда вуза XXI века: Материалы VI международной научной конференции. 4—10 декабря 2012 г. Купио (Финляндия). — С. 127—130.

8. Рогов А. А. О дешифровке рукописных исторических документов / А. А. Рогов, А. В. Скабин, И. А. Штеркель // Информационные технологии и письменное наследие El'Manuscript—2012: материалы IV Международной научной конференции (3—8 сентября 2012). — С. 230—233.

9. Рогов А. А. Автоматизация дешифровки исторических стенограмм / А. А. Рогов, А. В. Скабин, И. А. Штеркель // Информационная среда ВУЗа XXI века: материалы V международной научно—практической конференции (26—30 сентября 2011 г.).— Петрозаводск: Изд—во ПетрГУ, 2011. — С. 164—168.

10. Рогов А. А. Автоматизированная система распознавания рукописных исторических документов / A.A. Рогов, A.B. Скабин // Информационный бюллетень ассоциации «История и компьютер», № 37. Труды международной конференции. Июль 2011 г. — Петрозаводск: Изд—во ПетрГУ, 2011. — С. 92—96.

11. Рогов А. А. Некоторые особенности создания автоматизированной системы дешифровки исторических стенограмм. / А. А. Рогов, А. В. Скабин, А. Н. Талбонен, И. А. Штеркель // Интернет и современное общество: сборник научных статей. Материалы XIV Всероссийской объединенной конференции «Интернет и современное общество». Санкт—Петербург, 12—14 октября 2011 г. — СПб.: Из—во ООО «МультиПрожектСистемСервис», 2011. — С. 132—138.

Подписано в печать 19.11.13. Формат 60x84'/«. Бумага офсетная. Печ. л. 1. Тираж 100 экз. Изд. № 434.

Федеральное государственное бюджетное образовательное учреждение Высшего профессионального образования ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСТИТЕТ

Отпечатано в типографии Издательства ПетрГУ Республика Карелия, 185910, г. Петрозаводск, пр. Ленина, 33.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Петрозаводский государственный университет

На правах рукописи

04201453889

Скабин Артём Викторович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ ДЕШИФРОВКИ ИСТОРИЧЕСКИХ СТЕНОГРАММ

Специальность 05.13.18 - Математическое моделирование, численные методы

и комплексы программ

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель доктор технических наук, профессор А. А. Рогов

Петрозаводск - 2013

Оглавление

ВВЕДЕНИЕ......................................................................................................................5

Глава 1. Извлечение информации из документов......................................................19

1.1 Методы бинаризации изображений..................................................................19

1.1.1. Метод Отсу.................................................................................................19

1.1.2 Метод Бернсена...........................................................................................20

1.1.3 Метод Эйквеля.............................................................................................20

1.1.4 Метод Ниблэка.............................................................................................21

1.1.5 Пороговые методы бинаризации...............................................................22

1.1.6 Метод ISODATA..........................................................................................23

1.1.7 Метод Kapur..................................................................................................23

1.1.8 Метод Cheng-Chen.......................................................................................23

1.1.9 Метод основанный на яркостной характеристике....................................24

1.1.10 Результаты сравнения методов.................................................................25

1.1.11. Алгоритм выбора метода бинаризации..................................................26

1.2 Методы обработки изображений.......................................................................27

1.3 Связные области бинарного изображения........................................................28

1.3.1 Метод «Лесного пожара»............................................................................29

1.3.2. Двухпроходный алгоритм..........................................................................29

1.3.3 Пороговая и мультипороговая сегментация..............................................30

1.3.4 Методы слияния, разбиения связных областей........................................31

1.4 Поиск схожих символов.....................................................................................34

1.5 Модуль получения оригинальной графики символов.....................................39

Глава 2. Дешифровка стенограмм...............................................................................42

2.1 Основные подходы к распознаванию символов..............................................42

2.1.1 Соответствие шаблону.................................................................................42

2.1.2 Статистические методы...............................................................................43

2.1.3 Структурные методы...................................................................................44

2.1.4 Нейронные сети............................................................................................44

2.2 Построение строк рукописного документа......................................................44

2.2.1 Алгоритм распознавания строк методом ближайшего соседа................46

2.2.2 Алгоритм распознавания строк методом построения графа связей.......49

2.3 Алгоритм распознавания подстрочных и надстрочных символов................53

2.4 Математическая модель дешифровки стенограмм..........................................54

2.4.1 Оценка первого слагаемого математической модели..............................55

2.4.2 Оценка второго слагаемого математической модели...............................55

2.5 Реализация математической модели в информационной системе.................58

2.6 Апробация математической модели дешифровки символов..........................59

Глава 3. Информационная система дешифровки исторических стенограмм.........62

3.1 Основные требования к разрабатываемой системе.........................................62

3.2 Функциональные требования.............................................................................63

3.2.1 Описание функции «Дешифровать стенограмму»...................................64

3.2.2 Описание функции «Обработать документ».............................................64

3.2.3 Описание функции «Выделить символы».................................................65

3.2.4 Описание функции «Распознать документ»..............................................66

3.3 Потоки данных....................................................................................................67

3.3.1 Потоки данных функции «Распознать стенограмму»..............................67

3.3.2 Потоки данных функции «Обработать документ»...................................68

3.3.3 Потоки данных функции «Распознать документ»....................................69

3.4 ЕЯ-модель............................................................................................................70

3.5 Реляционная модель............................................................................................74

3.6 Архитектура системы.........................................................................................77

3.7 Спецификация функций.....................................................................................80

3.8 Описание интерфейса системы..........................................................................84

Заключение....................................................................................................................89

Литература.....................................................................................................................90

ВВЕДЕНИЕ

Актуальность темы исследования, новизна и цели работы

Распознавание рукописных текстов востребованы в различных областях человеческой деятельности. Многие компьютерные фирмы разрабатывают программы, которые решили бы эту задачу. Большой вклад в развитие оптического распознавания символов внесли ученые В. В. Александров, В. Анисимов, В. Л. Арлазаров, Н. Д. Горский. Дешифровка стенограмм, частного случая рукописного текста, является актуальной задачей, в результатах которой заинтересованы, прежде всего, филологи и историки. Существующие системы оптического распознавания (ABBYY FineReader [1], CuneiForm [2], Google Tesseract [3]) ориентированы на распознавание современных языков и печатных текстов, что делает невозможным их применение к историческим стенографическим записям. Исходными данными для таких систем являются документы хорошего качества, как первоисточник (страницы рукописей, четкие, контрастные снимки, с четко разделенным фоном и символами), так и хорошего написания (строки прямые, без искривлений, отсутствие исправлений и зачеркиваний).

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

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

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

Степень разработанности темы исследования.

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

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

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

1. провести анализ существующих информационных систем оптического распознавания символов;

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

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

4. разработать алгоритм поиска схожих символов;

5. построить математическую модель дешифрования символов;

6. разработать численный метод определения параметров математической

модели;

7. реализовать разработанные алгоритмы в компьютерной системе.

Научная новизна'.

1. описан алгоритм подбора наилучшего метода бинаризации исторических рукописных документов;

2. предложен пороговый метод, основанный на яркостной характеристике с плавающим порогом;

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

Методология и методы исследования: Использованы методы теории вероятностей, математической и прикладной статистики, численные методы кластерного анализа, вычислительной геометрии и обработки изображений.

Положения, выносимые на защиту:

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

2. математическая модель дешифровки стенографических документов, содержащая информацию как о форме и месте символов, так и извлеченную из текстов автора;

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

4. программный комплекс (ИС Шв!*^), реализующий предложенный метод выбора бинаризации стенографического документа и использующийся для построения алфавита стенографического текста и дальнейшей дешифровки стенограммы.

Теоретическая и практическая значимость.

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

Степень достоверности

Достоверность результатов проведенных исследований подтверждена проведением исследований рукописных стенографических записей Сниткиной (До-

стоевской) Анны Григорьевны — наброски к «Дневнику Писателя» за 1881 г. и «Из воспоминаний А. Г. Достоевской».

Апробация работы

Результаты диссертационного исследования были представлены на следующих конференциях:

1. V Международная научная конференция «Компьютерные технологии и математические методы в исторических исследованиях» (Петрозаводск, 2013);

2. VII Международная научно-практическая конференция «Информационная среда Вуза XXI века» (Петрозаводск, 2013);

3. XIV Всероссийская научная конференция «Электронные библиотеки: Перспективные методы и технологии, электронные коллекции RCDL'2012» (Переславль-Залесский, 2012);

4. Всероссийская научная конференция «Анализ изображений, сетей и текстов АИСТ'12» (Екатеринбург, 2012);

5. IV Международная научная конференция «Информационные технологии и письменное наследие El'Manuscript-2012» (Петрозаводск, 2012);

6. VI Международная научно-практическая конференция «Информационная среда Вуза XXI века» (Куопио, Финляндия, 2012);

7. V Международная научно-практическая конференция «Информационная среда ВУЗа XXI века» (Петрозаводск, 2011);

8. Международная конференция «Компьютерные технологии и математические методы в исторических исследованиях» (Петрозаводск, 2011);

9. XIV Всероссийская конференция «Интернет и современное общество» (Санкт-Петербург, 2011).

Проведенные исследования производились в рамках гранта Российского гуманитарного научного фонда на тему «Автоматизированная система распозна-

вания и дешифровки стенограмм XIX - начало XX вв.» № 11-01-12026 (руководитель Рогов А.А.). Программы для ЭВМ, входящие в состав программного комплекса, были зарегистрированы в Объединённом фонде электронных ресурсов «Наука и образование» (ОФЭРНиО) № 19509 от 23.09.2013.

Оптическое распознавание текста

Распознавание образов является одним из бурноразвивающимся направлением в связи с развитием информационных технологий, как аппаратных, так и программных средств. Выделяют два основных направления распознавания образов [4]:

- Изучение способностей живых существ к распознаванию, объяснение и моделирование данных способностей;

- Создание методов, развитие теории, для создания устройств, предназначенных для решения задач в прикладных целях.

Второе направление получило большое развитие в информационных технологиях, это связано с большим количеством прикладных задач, ориентированных на распознавание образов. Основные методологии распознавания и обработки изображений описаны Мантасом [5]. Данное направление распознавания образов включает в себя обширную область прикладных задач, таких как: распознавание текстов - рукописных [6, 7, 8], рукопечатных [9, 10, 11, 12], печатных [13, 14, 15, 16], как например распознавания цифровых почтовых кодов [17], обработка изображений [18], в том числе и распознавания различных объектов на изображении, например детектирование лиц на изображении [19, 20, 21], автомобильных номеров [22], дорожных знаков [23], распознавание речи [24, 25] и т.д. и т.п. Одним основных направлений распознавания образов стало распознавание текста (optical character recognition,OCR), на ранних этапах задача оптического распознавания была связанна с двумя направлениями [26]: расширение возможностей телеграфа, а так же создание устройств чтения для слепых. Но в дальнейшем возникли проблемы автоматического и автоматизированной обработки текстовой информации. Текст может быть следующего вида: печатный, рукописный, рукопечатный

(текст написанный «от руки» печатными буквами). В зависимости от типа текста, для его распознавания применяются различные методы распознавания. Существует два типа [27] систем оптического распознавания текста (optical character recognition,OCR): - offline системы — системы, которые работают с оцифрованной информацией (отсканированные документы, распечатанный текст и т.п.). Основные методы для offline описаны Суеном [28], Говинданом и Шивапрасадом [29], Стеинхерзом [30], Алессандро [31], Коерич [32], Бортолози [33]. На сегодняшний момент большая часть исследований и разработок, связанное с offline распознаванием, ориентированно на печатные тексты или же на рукопечатные [34], проблема рукописных текстов является трудноразрешимой [35]; - online системы — системы, в которых распознавание основано на динамики написания символов. Online распознание текста [36] стало одним из популярных направлений распознавания текста, описано в [37, 38]. Это связано с появлением большого количества устройств, с сенсорным способом ввода. Данные системы ориентированные на рукописный текст (Graffiti PalmOS и т.д.).

Существует большое количество программных средств, реализующих OCR. Среди систем, поддерживающих русский язык, можно выделить «ABBYY FineReader» [1], «CuneiForm» [2], «Google Tesseract» [3] и другие. Данные системы являются offline системами распознавания текста, ориентированные на печатный и рукопечатный текст. Значительный вклад в развитие оптического распознавания символов внесли: В. В. Александров, Б. В. Анисимов, В. JI. Арлазаров, Н. Д. Горский.

Александров Виктор Васильевич и Горский Николай Дмитриевич, в своих трудах рассматривают проблему обработки изображений [39, 40]. В исследование проблемы offline распознавания текста внёс вклад Арлазаров Владимир Львович [41, 42, 43, 44] под его руководством были разработаны системы OCR, включая «CuneiForm».

Основные проблемы, которые возникают при распознавания текстов:

- Плохого качества исходный материал;

- Искажения при оцифровке, в том числе поворот изображения и строк;

- Зачеркивание и исправление;

- Схожее написание символов, например «о» и «О»

Для качественного распознавания документов, необходимо хорошего качества исходные материалы, высокой четкости с отсутствием каких-либо искажений, шумов и т.п. Но некоторые документы находятся в плачевном состоянии, когда стандартными средствами оцифровки (сканирование, фотографирование) не достичь необходимого качества. Тогда для оцифровки могут быть использованы различные методы и способы, которые существенно облегчат дальнейшую обработку изображения [45] Человеческий глаз может воспринимать на длины волн от 400-700 нм. в то время как более хорошие результаты оцифровки получаются вне данного диапазона: ультрафиолетовый, ультрафиолетовая люминесценция, инфракрасный. Благодаря такой оцифровки не нужна бинаризация или сегментация, которые часто является невозможной задачей [46] для низкоконтрастностной, поврежденной или частично тусклой рукописи [47] В системах OCR возникает проблема с искажением исходного материала при оцифровки. Некоторые из систем успешно борются с искажениями, характерными для сканированных печатных документов: поворот, масштабирование и другие геометрические искажения [48, 49, 50]. Распознавание текстов с другими видами искажений, возникающих при фотографировании источника цифровыми фотоаппаратами, является серьезным препятствием для подобных систем. Так как это ведёт к искажению строк, а одним из главных условий успешного распознавания печатного текста указанными системами, является необходимость прямого горизонтального расположения строк в документе. Но при фотографировании [51], а главным образом при написании документов происходит искривление строк [52].

Стенографическая система записи

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