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

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

КУГАЕВСКИХ Александр Владимирович

МОДЕЛИ И МЕТОДЫ РАСПОЗНАВАНИЯ ИЕРОГЛИФИЧЕСКИХ ТЕКСТОВ НА ПРИМЕРЕ ДРЕВНЕЕГИПЕТСКОГО ЯЗЫКА

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

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

АВТОРЕФЕРАТ

005043678

Тюмень - 2012

005043678

Работа выполнена на кафедре информационных систем Института математики, естественных наук и информационных технологий ФГ'БОУ ВПО Тюменский государственный университет.

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

Ивашко Александр Григорьевич

Официальные оппоненты: Захаров Александр Анатольевич,

доктор технических наук, профессор, Тюменский государственный университет, заведующий кафедрой Информационной безопасности

Конушин Антон Сергеевич,

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

Ведущая организация: ФГБОУ ВПО Новосибирский государственный университет экономики и управления «НИНХ»

Защита диссертации состоится «31» мая 2012 г. в «15:00» часов на заседании диссертационного совета Д 212.274.14 при Тюменском государственном университете по адресу 625003, г. Тюмень, ул. Перекопская. 15А, ауд. 410.

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

Автореферат разослан «28» апреля 2012 г.

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

/¿и

А. А. Ступпиков

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

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

Решение проблемы распознавания иероглифических текстов наиболее актуально для групп историков, работающих в Берлино-Бранденбургской академии наук (Германия), Центре египтологических исследования РАН (Россия), Утрехтском университете (Нидерланды), Королевском колледже (Оксфорд, Великобритания).

К настоящему времени накоплена достаточная база методов сегментации изображений и их распознавания. В области распознавания образов известны результаты научных школ Загоруйко Н.Г. (Институт математики им. С.Л. Соболева), Л. Бреймана (университет Беркли), Дж. Фридмана (Стэндфордский университет), Я. Лекуна (Университет Нью-Йорка), К. Фукушимы (университет Kansai, Осака, Япония). Задачей распознавания иероглифических текстов занимаются научная школа А.Л. Шамиса (компания ABBYY), фирма NJStar Software Corp и научная школа Фей Йина (Институт автоматизации Китайской Академии Наук).

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

Для компьютерной обработки древнеегипетских текстов в 80-е годы XX века европейские исследователи из Центра по автомати-

зации египтологических исследований (CCER) разработали стандарт Manuel de Codage (MdC). Решению проблем автоматического преобразования изображений текстов, полученных с исторических артефактов, в цифровой код были посвящены работы французских исследователей Д. Арриваля и Н. Ричарда (D. Arrivault, N. Richard), которые не дали практически значимых результатов. В тоже время историки до сих пор не имеют в своем арсенале инструментальных средств, позволяющих автоматизировать обработку древнеегипетских текстов.

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

Задачи исследования.

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

2. Разработка нейросети распознавания структурных элементов и синтаксических параметров иероглифических текстов и алгоритмов обучения.

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

4. Проведение вычислительных экспериментов с целью проверки адекватности предложенных методов и алгоритмов.

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

Предметом исследования являются методы сегментации и распознавания текстов.

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

На защиту выносится следующее:

Пункт 1. Разработка новых математических методов моделирования объектов и явлений.

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

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

3. Метод нейросетевого распознавания синтаксических элементов древнеегипетских текстов (групповых структур и картушей) и представления текста в формате М/С.

Пункт 4. Разработка, обоснование и тестирование эффективных численных методов с применением ЭВМ.

4. Авторская модификация алгоритма обучения Д. Хебба для нейросети распознавания синтаксических элементов древнеегипетских текстов.

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

5. Архитектура программного комплекса работы с древнеегипетскими текстами, реализующая математические модели распознавания иероглифов и способы визуализации текстов, кодированных в стандарте Мс/С.

Научная новизна заключается в следующем:

1. Предложена математическая модель описания иероглифических текстов, включающая структурные элементы текста (иероглифы и рамки картушей) и синтаксические параметры согласно стандарту кодирования Мс1С.

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

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

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

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

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

Реализация и внедрение результатов. Программный комплекс поддержки деятельности египтолога апробирован в системе TLA Берлино-Бранденбургской Академии Наук (Германия).

Апробация работы. Основные результаты докладывались на международной конференции ГрафиКон-2010 (Санкт-Петербург, 2010 г.), научной сессии НИЯУ МИФИ (Москва, 2010 г.), всероссийской конференции Нейроинформатика-2010 (Москва, 2010 г.).

По результатам исследований опубликовано 13 печатных работ, из которых в рекомендованных ВАК РФ периодических изданиях -1, получены 3 свидетельства о регистрации программ для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации составляет 117 страниц, содержит 45 рисунков, 6 таблиц. Библиографический список включает 99 наименований работ российских и зарубежных авторов.

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

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

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

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

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

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

^ = ,Е (1)

где х1,у! — координаты верхней левой точки прямоугольника, - ширина и высота прямоугольника, описанного вокруг сегмента, Я; - угол поворота прямоугольника, т( - направление письма символа внутри сегмента, г/, - степень повреждения сегмента, Е - набор классов иероглифов, нераспознанных иероглифов и рамок картушей, / - индекс сегмента.

На этапе выделения синтаксических элементов текста происходит формирование описания текста по стандарту М/С. Части текста, представленные в строковом и колоночном виде, распознаются как разные тексты, хотя они и расположены в одном манускрипте. Поэтому цифровое представление манускрипта Т является множеством отдельных текстов Г, каждый из которых содержит совокупность строк или столбцов 1:

t = ({le},M,R,L),

(2)

где М - общее направление письма всего текста, Я - общий размер элементов текста, Ь - вид организации текста (в строки или в столбцы), £ - индекс строки.

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

1 = {Не,Се,Се), (3)

Множество иероглифов Н характеризуется набором синтаксических параметров:

н = {{К'гп^п, ап,тп, </„)}, (4)

где Л„ - класс иероглифа, г„ - размер иероглифа, - цвет иероглифа, ап - угол наклона иероглифа, тп - направление письма иероглифа, с1п - повреждение иероглифа, п - индекс иероглифа.

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

Н^л,'^)}. (5)

где RsJ - размер группы, ^ - степень повреждения группы, у -индекс группы.

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

С = {{Мт^т^т,Мт^т)}, (6)

где гт - размер картуша, - цвет картуша, с1т - степень повреждения картуша, Мт - направление письма картуша, /т - тип рамки картуша, т - индекс картуша.

Этап распознавания структурных элементов текста осуществляется с применением модифицированной нейросетевой модели К. Фукушимы и представляет собой 10-слойную нейронную сеть.

Нейросетевая модель К. Фукушимы была дополнена слоем сегментации. Сегментация осуществляется через выявление границ сегментов, основанное на перепаде яркости на границе. Слой сегментации основан на применении фильтра Габора. На вход слоя подается массив яркостей пикселей и0, при этом на выходе получаем массив степеней граничности:

влияния соседних пикселей, в - ориентация параллельных возбуждающих и тормозящих зон, к,1 — позиция светового импульса в рецептивной области, х' = ксоъв + 15тд, у' = -к$тв + 1со§6, Я - количество параллельных возбуждающих и тормозных зон в рецептивном поле, т,п- позиция центра рецептивного поля.

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

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

Каждый нейрон слоя ио получает связи от нейронов слоя (УС1, осуществляющего распознавание признаков символа. Чем меньше активация соответствующих нейронов слоя С/С1, тем выше вероят-

где = шах(х,0) - пороговая функция, Аа - размер области

ность повреждения символа в соответствующей четверти. Поэтому передаточной функцией является функция Хевисайда, при которой нейрон будет активироваться только при положительном сигнале. Ответом каждого нейрона IIв будет значение степени повреждения:

ив (т) = <р

2 2 ав(у)иС1(п + у,к,а)

1-

/с=1 М <А„

вг

(8)

где иС1 (п + у,к,а) - выход нейрона распознавания признака символа, Ав - размер области поиска повреждения, ав (у) - сила постоянных возбуждающих связей, вв - порог чувствительности.

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

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

Шаг 1. Обучение слоев распознавания.

Шаг 2. Начальным значениям а0 (у) присваиваются соответствующие значения а51 (у).

Шаг 3. На вход нейросети подается поврежденный образ элемента.

Шаг 4. Расчет изменения веса

Аав (у) = qDuD (т)иС1 (п + у, к, а) . (9)

Шаг 5. Переход к следующему нейрону и возврат на шаг 4.

Шаг 6. Если не конец обучающей выборки - возврат на шаг 3, иначе - выход.

После выявления и распознавания всех элементов древнеегипетского текста производится процедура распознавания синтаксических параметров текста.

Показателем для определения типа организации текста Ь служат выходы нейронов С/С4 (и,6846,90), отвечающих за распознавание вертикальных линий.

Общая высота элементов текста Я определяется как максимальная высота сегмента 5 в пикселях. Высота каждого отдельного элемента гп определяется как ранжированная высота й, соответствующего сегмента по отношению к Л.

Общее направление текста М определяется как наиболее часто встречаемое направление письма элементов текста т1.

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

Для выделения групп С разработана специфическая нейронная сеть. На вход этой нейросети подаются параметры А,. Сеть состоит из 2 слоев.

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

к

(10)

где Я - общая высота текста, Кы- порог активации нейрона,

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

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

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

1-в

-<р

2 +

Н<4г_

2 авг(у)ЛГ(/ + у) + 1

-К;

щ

(11)

где А^ - размер области активации нейрона, а^ (у) - сила возбуждающих связей, вj - показатель чувствительности нейрона, Кнк ~ П0Р0Г активации нейрона, у - индекс связи между нейронами у и /'.

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

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

Шаг 1. Задать начальные значения а^ (у), зависящие от предполагаемого размера группы и выхода нейронов входного слоя

( ) = 1-аг(|+у)ся(*,у) а*КУ) ■ (12)

Шаг 2. Подать на вход нейросети образ группы

Шаг 3. При необходимости изменить распознанную группу и скорректировать веса

IN (i + v) Ng (j)

Шаг 4. Если не конец обучающей выборки - возврат к шагу 2, иначе - выход.

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

Комплекс состоит из трех подсистем: иероглифический текстовый редактор, подсистема распознавания текстов и модуль хранения текстов. Каждая подсистема может функционировать отдельно от других (рис. 1).

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

Texts

Модуль хранения текстов Рис. 1. Архитектура программного комплекса

Иероглифический текстовый редактор

Иероглифический текстовый редактор позволяет визуализировать иероглифический текст, кодированный по стандарту MdC, и представляет собой WYSIWYG-редакгор с полным функционалом создания и обработки текстов, согласно этому стандарту. Иероглифы и структурные элементы языка хранятся в векторном формате WMF.

Подсистема распознавания состоит из двух компонент: модуля распознавания структурных элементов Neocognitron и модуля распознавания синтаксических параметров Restoration. Посредством библиотеки CUDA Runtime API были реализованы параллельные вычисления выходов нейросети.

Модуль хранения текстов представляет собой клиент-серверное приложение, использующее СУБД MS SQL Server 2008R2. Каждый текст представляет собой набор строк, которые характеризуются MdC-кодом, транслитерацией и переводом. На каждую строку ведется история правок с сохранением времени правки и данных пользователя, осуществившего правку. Механизм поиска представляет собой полнотекстовый поиск с использованием метаданных на каждый текст и основан на применении векторной модели поиска. Для ускорения работы поисковой системы все тексты индексируются с помощью алгоритма SPIMI, необходимая информация заносится в координатный инверсный индекс. Индекс в памяти организован в виде 5+-дерева.

Программный комплекс разработан на языке С# в среде Visual Studio 2010. Средства организации параллельных вычислений на видеокартах разработаны с помощью CUDA SDK на языке С.

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

Проверка адекватности построенной модели и применяемых алгоритмов проводилась в три этапа. Для каждого этапа была составлена тестовая выборка.

Тестовая выборка для проведения экспериментов по качеству распознавания текстов составила 358 изображений текстов. Тесто-

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

Таблица 1

Результаты проверки качества распознавания текстов

Материал Кол-во текстов Качество распознавания

Папирус, холст, кожа 32 82,1%

Камень 294 84,6%

Керамика 7 80,3%

Дерево 25 81%

Итого 358 82%

Для оценки качества распознавания разработанной нейронной сети обучающая выборка формировалась путем предъявления ней-росети для распознавания эталонных изображений иероглифов из базы символов Hieroglyphica 2, с добавлением зеркальных отражений символов и символов, повернутых на углы а£[0,тг] с шагом 15°. Общая численность изображений составила 164280 отдельных изображений символов древнеегипетского языка. На обучающей выборке нейронная сеть показала качество распознавания в 99%.

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

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

О 10 20 30 40 50 60 70 80 90 100

Степень повреадения

Рис. 2. Зависимость качества распознавания символов от степени повреждения

Для проверки качества выделения групп иероглифов была сформирована обучающая выборка из 38 образов эталонных групп иероглифов. Тестовая выборка была составлена из выделенных изображений групп иероглифов из набора текстов, хранящихся в системе TLA. Общее число текстов составило 39, общее число групп иероглифов - 168. Результаты проверки для каждого из 15 типов приведены в таблице 2. Оценка качества распознавания групп составила 76%.

Таблица 2

Результаты проверки качества выделения групп

Тип группы Кол-во групп Качество выделения Тип группы Кол-во групп Качество выделения

I 5 70% IX 16 79%

II 4 70% X 9 76%

III 7 73% XI 5 77%

IV 8 73% XII 27 80%

V 9 74% XIII 18 78%

VI 15 74% XIV 13 79%

VII 5 78% XV 14 79%

VIII 13 76%

Степень повреждения изображения группы может существенно повлиять на качество ее распознавания (рис. 3)._

Степень повреждения

Рис. 3. Зависимость качества выделения групп от степени повреждения

Для оценки времени обучения и функционирования нейронной сети использовалась следующая аппаратная конфигурация: Intel Core 2 Duo 3GHz, 8Gb DDR2, GeForce 9800 GTX (128 ядер, частота ядра 675MHz). За счет применения технологии CUDA время обучения снизилось в 4 раза с 90 часов на процессоре до 22 часов на видеокарте. Время, требуемое на распознавание 1 символа, удалось снизить в 5 раз с 78 секунд на процессоре до 14 секунд на видеокарте.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

3. Модифицирован алгоритм обучения нейросети сегментации изображения с учетом степени повреждения элементов текста.

4. Разработана нейросетевая модель распознавания синтаксических элементов древнеегипетских текстов и их кодирования в стандарте М/С. Предложенная модель позволяет выделять группы иероглифов и картуши.

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

6. Разработана архитектура программного комплекса, взаимодействие между компонентами которой реализовано на обмене данными в формате М/С. Предложенная архитектура позволяет работать как с изображениями иероглифических текстов, так и с текстами, переведенными ранее в формат Мс1С.

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

8. Произведено распознавание изображений текстов с 358 исторических артефактов, выполненных в пергаменте, папирусе, керамике и камне. Тексты включали 240 тысяч иероглифов, 50 тысяч картушей и групп иероглифов, выполнены в виде строк и колонок, включающих тексты с инверсным направлением письма. Среднее качество распознавания синтаксических элементов составило 82%, что подтверждает адекватность разработанных методов и моделей распознавания иероглифических текстов.

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

Публикации в периодических изданиях, рекомендованных ВАК

1. Кугаевских A.B., Ивашко А.Г. Возможность применения искусственных нейронных сетей «неокогнитрон» для распознавания древнеегипетских иероглифов // Вестник Тюменского Государственного Университет, 2009. №6. - Тюмень: Изд-во ТюмГУ, 2009.-С. 209-214.

Публикации в трудах международных конференций

2. Кугаевских A.B. Агломеративный метод сегментации иероглифического текста // Труды конференции ГрафиКон-2010. Санкт-Петербург: СПбГУ ИТМО, 2010. С. 181-187.

Публикации в тезисах всероссийских и международных конференций

3. Кугаевских A.B. Возможность применения ИНС «неокогнитрон» для распознавания древнеегипетских иероглифов // Ней-роинформатика-2010. Тез. докл. XII всероссийской научно-технической конференции. Москва: НИЯУ МИФИ, 2010. С. 15.

4. Кугаевских A.B. Возможность применения ИНС «неокогнитрон» для распознавания древнеегипетских иероглифов // Тез. докл. Научная сессия НИЯУ МИФИ-2010. Том 2. Москва: НИЯУ МИФИ, 2010. С. 244.

5. Кугаевских A.B. Система распознавания древнеегипетских иероглифов на базе ИНС «неокогнитрон» // Телекоммуникации и новые информационные технологии в образовании. Тез. докл. XIV выставки-конференции. Москва: НИЯУ МИФИ, 2010. С. 112-113.

6. Кугаевских A.B. Возможность применения ИНС «неокогнитрон» для распознавания древнеегипетских иероглифов Н Труды научной сессии НИЯУ МИФИ-2010. Том 3. Москва: НИЯУ МИФИ, 2010. С. 215-218.

7. Кугаевских A.B. Разработка комплекса утилит для историка-египтолога // Информационно-вычислительные технологии и

их приложения: Тез. докл. VI международной научно-технической конференции. Пенза: РИО ПГСХА, 2007. С. 106-108.

8. Кугаевских A.B. Программный комплекс поддержки деятельности египтолога // Региональный конкурс студенческих научных работ 2007 г.: Тез. докл. Тюмень: ТГИМЭУП, 2008. С. 254-256.

9. Кугаевских A.B., Коломиец И.И. Иероглифический текстовый процессор «Thoth» // Безопасность информационного пространства: Тез. докл. VI межвузовской научно-практической конференции студентов, аспирантов и молодых ученых. Тюмень: ТюмГУ, 2007. С. 175-178.

10. Кугаевских A.B. Реализация иероглифического текстового процессора как инструмент автоматизации деятельности египтолога // Дистанционные образовательные технологии: опыт применения и перспективы развития: Тез. докл. Тюмень: ТюмГУ, 2008. С. 186-191.

Свидетельства о регистрации программ для ЭВМ

11. Кугаевских A.B. Свидетельство об официальной регистрации программы для ЭВМ № 2007614348. Иероглифический текстовый процессор Thoth, 12.10.2007.

12. Кугаевских A.B. Свидетельство об официальной регистрации программы для ЭВМ № 2010612687. Модуль сегментации изображения Thoth-Segmentation, 19.04.2010.

13. Кугаевских A.B. Свидетельство об официальной регистрации программы для ЭВМ № 2010612688. Модуль распознавания иероглифов Thoth-Recognition, 19.04.2010.

Подписано в печать 25.04.2012. Тираж 100 экз. Объем 1,0 уч.-изд. л. Формат 60x84/16. Заказ 286.

Издательство Тюменского государственного университета 625003, г. Тюмень, ул. Семакова, 10. Тел./факс (3452) 45-56-60; 46-27-32 E-mail: izdatelstvo@utmn.ru

61 12-5/3646

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кугаевских Александр Владимирович

МОДЕЛИ И МЕТОДЫ РАСПОЗНАВАНИЯ ИЕРОГЛИФИЧЕСКИХ ТЕКСТОВ НА ПРИМЕРЕ ДРЕВНЕЕГИПЕТСКОГО ЯЗЫКА

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

программ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

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

Тюмень - 2012

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

Оглавление

Введение...................................................................................................................2

Глава 1. Состояние вопроса и задачи исследования............................................7

1.1 Современное состояние вопроса компьютерного представления древнеегипетского текста....................................................................................7

1.2 Обзор методов распознавания текстов......................................................14

1.3 Выводы..........................................................................................................36

Глава 2. Модель распознавания древнеегипетского текста..............................37

2.1 Модель идентификации структурных элементов текста.........................37

2.2 Модель определения синтаксических параметров текста.......................51

2.3 Выводы..........................................................................................................57

Глава 3. Программный комплекс поддержки деятельности египтолога.........58

3.1 Архитектура программного комплекса.....................................................58

3.2 Описание иероглифического текстового редактора.................................65

3.3 Описание модуля хранения текстов...........................................................68

3.4 Описание использования технологии параллельных вычислений.........79

3.5 Выводы..........................................................................................................84

Глава 4. Описание вычислительных экспериментов.........................................86

4.1 Описание механизма тестирования системы распознавания..................86

4.2 Пример распознавания.................................................................................93

4.3 Выводы..........................................................................................................95

Выводы по диссертационной работе...................................................................96

Список источников и литературы........................................................................98

Приложение 1.......................................................................................................106

Приложение 2.......................................................................................................107

Приложение 3.......................................................................................................108

Приложение 4.......................................................................................................109

Приложение 5.......................................................................................................115

Введение

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

Решение проблемы распознавания иероглифических текстов наиболее актуально для групп историков, работающих в Берлино-Бранденбургской академии наук (Германия), Центре египтологических исследования РАН (Россия), Утрехтском университете (Нидерланды), Королевском колледже (Оксфорд, Великобритания).

К настоящему времени накоплена достаточная база методов сегментации изображений и их распознавания. В области распознавания образов известны результаты научных школ Загоруйко Н.Г. (Институт математики им. СЛ. Соболева), JI. Бреймана (университет Беркли), Дж. Фридмана (Стэндфордский университет), Я. Лекуна (Университет Нью-Йорка), К. Фукушимы (университет Kansai, Осака, Япония). Задачей распознавания иероглифических текстов занимаются научная школа АЛ. Шамиса (компания ABBYY), фирма NJStar Software Corp и научная школа Фей Йина (Институт автоматизации Китайской Академии Наук).

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

Для компьютерной обработки древнеегипетских текстов в 80-е годы XX века европейские исследователи из Центра по автоматизации египтологических исследований (CCER) разработали стандарт Manuel de Codage (MdC). Решению проблем автоматического преобразования изображений текстов, полученных с исторических артефактов, в цифровой код были посвящены работы французских исследователей Д. Арриваля и Н. Ричарда (D. Arrivault, N. Richard), которые не дали практически значимых результатов. В тоже время историки до сих пор не имеют в своем арсенале инструментальных средств, позволяющих автоматизировать обработку древнеегипетских текстов.

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

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

2. Разработка нейросети распознавания структурных элементов и синтаксических параметров иероглифических текстов и алгоритмов обучения.

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

4. Проведение вычислительных экспериментов с целью проверки адекватности предложенных методов и алгоритмов.

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

Предметом исследования являются методы сегментации и распознавания текстов.

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

На защиту выносится следующее: Пункт 1. Разработка новых математических методов моделирования объектов и явлений.

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

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

3. Метод нейросетевого распознавания синтаксических элементов древнеегипетских текстов (групповых структур и картушей) и представления текста в формате МйС.

Пункт 4. Разработка, обоснование и тестирование эффективных численных методов с применением ЭВМ.

4. Авторская модификация алгоритма обучения Д. Хебба для нейросети распознавания синтаксических элементов древнеегипетских текстов.

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

5. Архитектура программного комплекса работы с древнеегипетскими текстами, реализующая математические модели распознавания иероглифов и способы визуализации текстов, кодированных в стандарте Мс1С.

Научная новизна заключается в следующем:

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

рамки картушей) и синтаксические параметры согласно стандарту кодирования MdC.

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

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

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

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

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

Реализация и внедрение результатов. Программный комплекс поддержки деятельности египтолога апробирован в системе TLA Берлино-Бранденбургской Академии Наук (Германия).

Апробация работы. Основные результаты докладывались на международной конференции ГрафиКон-2010 (Санкт-Петербург, 2010г.), научной сессии НИЯУ МИФИ (Москва, 2010г.), всероссийской конференции Нейроинформатика-2010 (Москва, 2010г.).

По результатам исследований опубликовано 13 печатных работ, из которых в рекомендованных ВАК РФ периодических изданиях - 1, получены 3 свидетельства о регистрации программ для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации составляет 117 страниц, содержит 45 рисунков, 6 таблиц. Библиографический список включает 99 наименований работ российских и зарубежных авторов.

Глава 1. Состояние вопроса и задачи исследования

1.1 Современное состояние вопроса компьютерного представления

древнеегипетского текста

Для проведения исследования древнеегипетского текста его обычно переносят с оригинала, так как сам оригинал либо слишком масштабен (стены храмов или гробниц, рис. 1), либо слишком хрупок (папирусы или керамика, рис. 2). Это требует высокого уровня художественного мастерства, так как иероглифы представляют собой сложный вид рисуночного письма, а сам текст осложнен грамматическими конструкциями, отличными от современных языков [1-2, 4].

■■и

—1

НИННЯНМНР

^а

ШШШШШШШШШШШШ

■■—ия^^—иа

ШШШшШ^Ш

яяшшяшшшяяя

■■■

Рис. 1. Фрагмент стены храма Карнак с текстом мирного договора между

Рамсесом II и Хаттусили III

Рис. 2. Глава 125 Книги Мертвых

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

Общий алфавит древнеегипетского иероглифического письма составляет 6845 иероглифов. Иероглиф является сложным объектом для распознавания. У него большое количество признаков, а в некоторых случаях отличатся друг от друга они могут максимум двумя, например иероглифы А21 иА21А, изображенные на рисунке 3.

Рис. 3. Иероглифы А21 (слева) и А21А (справа)

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

Нередки случаи поворота изображений символов на определенный градус, их зеркальное отражение или изменение размера (рис. 4).

Рис. 4. Пример поворота, уменьшения размера и отражения символа А1.

Еще одна особенность, затрудняющая распознавание текста, это так называемые группы иероглифов. Строка иероглифического текста делилась на так называемые «квадраты», т. е. на части, каждая из которых плотно заполнялась иероглифическими знаками (рис. 5). Горизонтальная строка имела определенную высоту, вертикальная — ширину. Знаки не выходили за пределы строки [4].

Картуши (рис. 6) и серекхи (рис. 7) - это формы обозначения королевского сана. Во время Раннего Царства (ок. 3120 - 2686 гг. до н.э.) применялись серекхи. С установления Древнего Царства и вплоть до завоевания арабами применялись картуши. Семантически они одинаковы, со временем изменялось лишь начертание [2]. Графически представляют собой особые рамки, внутри которых могли содержаться любые элементы древнеегипетского языка.

Рис. 5. Примеры групп иероглифов

Рис. 6. Картуш фараона Тутмоса I

Рис. 7. Серекх фараона Нармера

Ям^-включения представляют собой специальную рамку, обводящую написанные иероглифы (рис. 8). В этом случае при чтении этого детерминатива к иероглифам добавляется приставка «хэт» или «хат». Необходимо оно для сокращения записи [2]. Такая рамка заменяет набор иероглифов, представленный на рисунке 9.

Рис. 8. Пример Яи^-включения

Рис. 9. Набор иероглифов, заменяющий рамку /wi-включения

Древнеегипетские писцы применяли две краски для письма. Черной краской писался основной текст, а красной показывалось начало нового абзаца [1].

В 80-е года XX века европейские исследователи из Центра по автоматизации египтологических исследований начали решать проблему компьютерного представления иероглифических текстов. Был разработан стандарт Manuel de Codage (MdC) [3], обеспечивающий полную поддержку всех грамматических особенностей древнеегипетского языка. На базе этого стандарта был разработан ряд программ для работы с текстами, сравнение которых представлено в таблице 1. В настоящее время стандарт MdC является общепризнанным способом кодирования древнеегипетских текстов.

Так как многие тексты уже повреждены, для описания степени повреждения любых элементов текста в MdC введено понятие «затенение символа» [3] (рис. 10).

Рис. 10. Штриховка символа А1

Для отображения степени повреждения символа, в рамках стандарта М(1С изображение символа разбивается на равные четверти, в каждой из которых может быть зафиксировано повреждение.

Таблица 1

Сравнение иероглифических текстовых процессоров.

1п8спЬе Атапиеше \VinGlyph Н1еп^1урЫса

Текущая версия 5.7 20048Е 4.0 1-28 1.0.4.3

Год издания 2012 2009 2004 2001 2010

Состояние Нет данных Прекращен Прекращен

База иероглифов 6845 3000 4700 6845 4675

Список картушей фараонов + + +

Изменение цвета иероглифов + + + + +

Текст по колонкам + + + + +

Набор текстов + + - + -

Разные + + + + +

ориентации текста

Информация об иероглифе + + +

Группировка иероглифов + + + + +

Серекхи и Ути включения + + +

Штриховка + + + + +

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

Помимо иероглифических текстовых редакторов, служащих для ввода текста, египтологи также используют словари-тезаурусы по древнеегипетскому языку. Для этого в Берлино-Бранденбургской Академии наук был запущен проект TLA (рис. 11). Thesaurus Linguae Aegyptiae (TLA) — это платформа, объединяющая ряд программ по оцифровке египетских текстов, которая возникла на базе проекта "Древнеегипетский словарь" Берлинско-Бранденбургской Академии наук. Задача TLA — создание нового инструмента для лексикографического изучения египетского языка, "виртуального словаря". В основу положен оцифрованный Берлинский словарь, который обновляется за счет индексирования египетских текстов, переводимых участниками TLA в машиночитаемую форму (в транслитерации).

щ ■ «ж-щ^ eggen; (Nahrung) zuführen VVb 5,513,15-514,3

x

□ DAi (r) kr»®®-* (etwas) essen (idiom.) VVb 5, 514.1-3

DAi XÄJ4 (Arm) ausstrecken; zuwenden; (sich) entgegenstellen VVb 5, 514.4-515.4

Г i ОД/(a) XÄ-Ai sich feindlich entgegenstellen VVb 5, 514.4-6

□ DAi (mAa г) sich wenden nach VVb 5, 514.13

ег^Ёга Л f

□ DAi (Иг) I sich vergnügen (idiom.) VVb 5, 514.10-12

X

□ DAi (tA r) 1 (etwas) unternehmen (gegen/für) (idiom.) VVb 5, 513.11-12

3 DAi überqueren; durchziehen; (jmdn.) übersetzen (über/nach) VVb 5, 511-513.14

□ 1 DAi (s.t) (etwas) fortbringen (nach) VVb 5, 513.10

Рис. 11. Пример окна тезауруса TLA.

В настоящее время TLA пополняется литературными сочинениями Среднего царства (Саксонская Академия наук), списками Книги мертвых (Академия наук земли Северный Рейн-Вестфалия), демотическими текстами (Академия языка и литературы, Майнц) и разными материалами, обрабатываемыми непосредственно в Берлинско-Бранденбургской Академии наук. Всего на сегодняшний день в TLA проиндексировано 900 ООО слов.

В состав TLA входит не только сам Берлинский словарь, но и его оцифрованная картотека (Das digitalisierte Zettelarchiv - DZA) [58, 59]. Создание системы оптического распознавания текстов могло бы значительно ускорить процесс создания тезауруса.

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