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

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

Сапаров Алексей Юрьевич

АНАЛИЗ И МОДЕЛИРОВАНИЕ СТРУКТУРЫ РАСТРОВЫХ ИЗОБРАЖЕНИЙ РУКОПИСНЫХ МАТЕМАТИЧЕСКИХ ФОРМУЛ С ЦЕЛЬЮ ИХ АВТОМАТИЧЕСКОГО РАСПОЗНАВАНИЯ

Специальность: 05.13.01 — Системный анализ, управление и обработка информации (в науке и технике)

Автореферат

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

Ижевск — 2014

5 ©Н 2074

005549811

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

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

доктор физико-математических наук, профессор

Официальные оппоненты: Кучуганов Валерий Никонорович

доктор технических наук, профессор, ФГБОУ ВПО «Ижевский государственный технический университет имени М.Т. Калашникова», заведующий кафедрой «Автоматизированные системы обработки информации и управления»

Яшин Александр Данилович

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

Ведущая организация: Институт программных систем «УГП имени

А.К. Айламазяна», г. Переславль-Залесский

Защита состоится «26» июня 2014г. в 12:00 час на заседании диссертационного совета Д 212.065.06 в ИжГТУ имени М.Т. Калашникова по адресу: 426069, г. Ижевск, ул. Суденческая, 7.

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

С диссертацией и авторефератом можно ознакомиться в научной библиотеке ФГБОУ ВПО ИжГТУ и на официальном сайте университета — http://istu.ru. Автореферат разослан « » _2014г.

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

кандидат технических наук, доцент В.Н. Сяктерев

Общая характеристика работы

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

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

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

Таким образом, задача распознавания текстов с математическими формулами в настоящее время является актуальной.

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

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

Степень разработанности проблемы. Исследования в области анализа и распознавания текстов рассматривали в своих работах H.S. Baird, Н. Saiga, N. Matsakis, K.-F. Chan, D.-Y. Yeung, M. Suzuki, Садыков C.C., Самандров И.Р., Салюм Сайд Салех, A. Belaid, J.P. Haton, R.H. Anderson, Фу K.C., Исупов Н.С., Кучуганов A.B., Костюк Ю.Л. и др.

В настоящее время существуют следующие приложения, распознающие математические формулы: Math input panel, InftyReader, GOCR. Math input panel является системой динамического распознавания рукописных формул, поэтому не может быть применена к обработке сканированных текстов. InftyReader и GOCR предназначены для распознавания печатных текстов с растровых изображений. Требуемое качество не достигается при сканировании изображений, поэтому точность распознавания не высокая. Ни одна из существующих систем не распознает сканированные рукописные формулы.

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

Предметом исследования являются методы анализа изображений и построения моделей изображений формул.

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

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

щие задачи, связанные с распознаванием текстов.

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

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

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

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

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

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

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

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

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

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

Практическая полезность.

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

2. Разработан алгоритм построения шаблона формулы в виде двумерно ориентированных и двухуровневых графов.

3. Проанализирована структура математических формул с точки зрения их широкого разнообразия и возможности их структурной классификации.

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

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

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

ния с точки зрения соответствия языку математических выражений. На защиту выносятся.

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

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

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

4. Результаты экспериментальных исследований.

Работа включает следующие области исследований:

1. Методы и алгоритмы структурно-параметрического синтеза и идентификации сложных систем.

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на научных конференциях: XXXIX итоговая студенческая научная конференция, УдГУ, г.Ижевск, 2011г.; 4-я международная конференция «Системный анализ и информационные технологии» — САИТ-2011, с.Абзаково, 2011г.; Всероссийская научная конференция с международным участием «Технологии информатизации профессиональной деятельности (в науке, образовании и промышленности)» — ТИПД-2011, г.Ижевск, 2011г.; 3-я международная научно-техническая конференция студентов и молодых ученых «Современные информационные технологии в образовании и научных исследованиях» — СИТОНИ-2012, г.Донецк, 2012г.; 6-я Всероссийская мультиконференция по проблемам управления — МКПУ-2013 «Управление в интеллектуальных, эрга-тических и организационных системах» — УИнтЭргОС-2013, с.Дивноморское, 2013г.

Публикации. Результаты работы отражены в 7 публикациях, в том числе в 2 изданиях, рекомендованных ВАК.

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

Краткое содержание работы

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

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

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

Статический метод основывается на распознавании текста только с использованием его растрового изображения. Математическая модель растрового изображения рассматривается в виде: f(i,j) : {0,..., N — 1} х {0,..., М — 1} —> {0,..., L - 1}, где N х М — размер изображения, а L — число возможных цветов. При L = 2 исходное изображение может содержать только цвета, условно обозначаемые 0 (фон) и 1 (фрагмент текста). Фактически, изображение представлено прямоугольной матрицей, элементы которого принимают значение 0 и 1, поэтому / называется матрицей изображения. Основным критерием при распознавании является сходство фрагментов растрового изображения (фрагмента матрицы) с некоторым шаблоном из базы.

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

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

В качестве существующих систем распознавания текстов, рассматриваются системы ABBYY FineReader, Math input panel, InftyReader и GOCR. Основным направлением ABBYY FineReader является распознавание обычных печатных текстов. Math input panel распознает рукописные формулы онлайновым методом по последовательности записи. InftyReader распознает только печатные формулы и только с высоким качеством исходного изображения с использованием определенного набора шрифтов. GOCR в настоящее время рассматривается больше как система распознавания обычных печатных текстов, а не математических формул, как было на этапе ее создания. Учитывая тот факт, что ни одна из рассматриваемых систем не распознает сканированные руко-

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

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

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

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

Определение. Граф Р = (5, [/) называется двухуровневым, если множеством его вершин 5 является множество графов = (Х^ Т^) £ Б, г =

1,2,3,____ При этом Р считается графом первого уровня, а его вершины —

графами второго уровня.

Определение. Граф .Р = (5, и) называется двумерно ориентированным, если для каждого ребра щ € II задана последовательность векторов V* = = £ О С К2, ] = 1,2, ...,п; п е М+}. При этом число

п называется коэффициентом сегментации ребра, а множество О — базой

Рис. 1: Пример графа изображения формулы ориентации. Если п = 1, то ребро называется несегментированным.

Определение. Двумерно ориентированный граф называется ориентированным по «сторонам света», если базой ориентации данного графа является множество ({—1; 0; 1; } х {-1;0; 1; })\{(0,0)}.

Определение. Графом изображения формулы называется двухуровневый ориентированный по «сторонам света» связный граф Р = (5, {/) без циклов с несегментированными ребрами С/ и одним началом, где вершины Si = (Х1: 6 5, г = 1,2,..., п так же ориентированы по «сторонам света».

Для примера можно рассмотреть изображение формулы для интеграла: /'х2 (1х. Граф изображения формулы для нее изображен на рис. 1, на котором направления ребер указаны буквами 'п', 'в', 'и/' и 'е' и их комбинациями, которые означают направления в соответствии с направлениями сторон света.

Решение задачи распознавания рукописных математических текстов сводится к решению задачи построения модели изображения формулы, представленной графом изображения формулы. Для решения этой задачи используются понятия отображения символа и отображения класса формулы. Отображением символа называется отображение гс : С —> Р из множества всех символов С в множество двумерно ориентированных графов Р. Отображением класса формулы называется отображение if : Ь —>• Г из множества классов формул Ь в множество графов изображений формул Р. Для работы с наиболее часто используемыми типами формул достаточно рассмотреть классы степенных формул, формул с нижними индексами, интегралы, корни, дроби и строчные формулы.

©

©

Рис. 2: Граф Функции возведения в степень

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

»/(/) = (5(»7(/1))и5(»7(/2)), [/(г/(/1))иУ(г/(/2))и(еь 52)(1л>), где (еь 52)(1>1)

содержит одно ребро, соединяющее первый подграф со вторым.

Пример. /1 = "2", /2 = "х". / = "2х". На рис. 2 приведены графы изображения формулы для /1 = "2", /2 = "х" и / = "2х". Отображение для / имеет

Рассматривается обратная задача, а именно задача определения класса формулы по имеющемуся графу. Пусть (Б, 17) — граф изображения формулы /, необходимо определить класс формулы /. Для решения задачи требуется найти обратное отображение к г/, которое обозначается через г1((5', 17)). По определению обратного отображения должно быть выполнено равенство г/-1 ((5,17)) = /. Считается, что все содержащиеся в тексте символы уже распознаны по отдельности и уже построено дерево изображения для исходной формулы. Рассматриваются только такие деревья, у которых вершины имеют не более одного исходящего ребра в каждом направлении базы ориентации.

Пусть р = (в, и) € Р — граф изображения формулы. Правило для отображения г/~1(р) выглядит следующим образом: г/-1 ((с с>/ '(№,^2))^ где с — начало графа р, а з2 — начало графа (¿з2,1/2).

Пример. Пусть р = ('2' и 'х\ 2х(1Л)). По описанному правилу получается соответствие: с = '2', = 'х', 172 = 0, (с, в2)(1,1) = Тогда искомое

отображение примет вид: г/-1 (/>) = г/-1('2*, 0)*' ' х = 2х.

вид: г/("2х") = ({гс('2'), гс('х')}, {2х(1,1)}).

хЧ ^

Рис. 3: Пример изображения формулы

Несложно доказать, что отображение г/-1 является обратным к отображению г/, через доказательство равенства г/(г/-1(р)) = р.

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

Простейшие компоненты обозначаются согласно их значениям следующим образом: х, 2, +, у, 3. На первом этапе выполняется попытка соединения компонент ж и 2. Согласно их взаимному расположению находится соответствие шаблону степенной формулы (а;2). Далее выполняется попытка соединения компонент х и + (я+). Но вариант соединения х+ не находит дальнейшего развития, так как при дальнейшей попытке соединения х+ и 2 не найдено подходящего шаблона. Соединение же компонент х2 и + возможно в виде линейной формулы х2+. При попытке соединения у и 3 найдено сразу два соответствия шаблонам простейших формул, так как однозначно нельзя сказать, что это линейная формула или формула возведения в степень. В этом случае оба варианта рассматриваются дальше, но определяются соответствующие веса. Например, вероятность того, что это степенная функция будет равна 60%, а вероятность того, что линейная — 40%. Тогда в конечном итоге будут построены два шаблона х2 + у3 и х2 +- уЗ с весами § и | соответственно.

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

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

Регулярное выражение определяется как пустое слово или слово, состоящее из одной буквы, а также слово, полученное из других регулярных выражений, применением к ним конечного числа регулярных операций. Пусть а и Ъ некоторые регулярные выражения, а А и В соответственно порождаемые ими регулярные множества. Объединение регулярных выражений (о|6) порождает объединение множеств (А U В), конкатенация выражений (ab) — конкатенацию множеств (AB), итерация выражения (а*) — итерацию множества (А*).

Например, для задания множества простейших арифметических выражений можно воспользоваться следующим регулярным выражением: а(\ + |\ — |\/|\*)а, где а -выражение, описывающее переменную. В качестве а может быть, например, использовано выражение, порождающее все непустые слова, состоящие из букв х, у, z: (x\y\z)(x\y\z)*. Запись (\ + |\ - |\/|\*) означает, что в этом месте выражения находится один из знаков бинарной операции. Запись (а;|у|,г)* означает повторение символов сколь угодно большое число раз.

Пусть рукописный текст содержит п неделимых компонент (букв, цифр, математических знаков и т.д.). И пусть каждая компонента имеет U (г = 1,... ,п) вариантов распознавания. Каждая компонента записывается в следующем виде: Si = (сх|сг|... |cfi). Результат распознавания можно представить в виде: S = G(sb ..., s„) = G ((cu|... Icith),..., (cn4l... I cnU)) , где G представляет некоторый граф изображения формулы, составленный из набора вершин si,..., s„. Используя методы линеаризации, результат записывается в виде регулярного выражения: S = (ci,i|... |cWl)... (c^i|... |с„,4„).

Аналогично задаются шаблоны классов математических формул Аi = 1,..., т. Для выбора наиболее правильного варианта распознавания в S необходимо найти совпадения с шаблонами А{. Для решения новой задачи можно воспользоваться теоремами о делении множества слов слева на символ и о пересечении множеств, заданных регулярными выражениями.

Теорема 1.

а X (е1(е2) = (а X в1|а X е,), а X (е,в2) = ( fХ ^ Х ^ 6 6 61 ,

[ ((aXei)e2), 6 £ ех

а X е* = (а X е)е*, а X а = б,

о X е = 0, а X Ь = 0, афЬ.

где В X А означает деление множества слов А на множество слов В слева и

определяется следующим образом: В X А = {ги|3г> е В , ую е А}. ,к , к Теорема 2. ( £ • С) П А = £ (ЬДС П (6, X Л))).

41=1 ' 1=1

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

Можно записать исходную необработанную строку в виде: 5 = ((Р1,ъС1,1)|...|(рМ1,сМ1)) ... ((р,м,с„л)|... |(р„,(„,с„.е„)^, что получено заменой всех с^- на пару (р1ь,, су). Добавленный параметр называется весом и равен вероятности того, что г-й символ строки должен быть распознан как символ су. В связи с этим рассматриваются такие понятия, как взвешенные регулярные множества, каждый элемент которого является парой из строкового значения и некоторого числового веса, выражающего предпочтение одного элемента над другими. Взвешенные регулярные множества порождаются взвешенными регулярными выражениями. Теоремы 1 и 2 применимы к взвешенным регулярным множествам. Взвешенные операции определяются следующим образом:

1. Взвешенное объединение:

б • VI и <5 • У2 = {(е • а + 5 ■ Ь) ■ и|а • у 6 Ц или Ь • у е где е + 3 = 1.

2. Взвешенная конкатенация:

{¿Лтл^и^ тг, е У2}

3. Взвешенная итерация:

со со

К' = £ сцУ*. где £ О; = 1, > 0), V0 = {""}, Vя = у V... V (п раз).

1=0 1=0

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

1. 0, {б}, {а} — взвешенные регулярные множества для любого а из V;

2. Если 5 и Т — взвешенные регулярные множества, то взвешенными регулярными множествами являются множества полученные применением взвешенных операций объединения (б • 5 и 6 ■ Т), конкатенации ((5Т)) и итерации

где |>4 = 1иУг(а;>0)^. Определение. Класс взвешенных регулярных выражений над конечным алфавитом V определяется следующим образом:

1. 0, б, а — взвешенные регулярные выражения для любого а из V;

2. Если Я и 5 — взвешенные регулярные выражения, то взвешенными являются

Рис. 4: Пример изображения формулы синуса регулярные выражения, полученные применением конечного числа взвешенных операций объединения ((е • R)|(<$ • S)), произведения ((R)(S)) и итерации ((Я)*, где |> = 1иУг(а^0)).

4 ¿=0 е-

Деление взвешенного множества слева определяется следующим ооразом: Определение. Делением взвешенного множества слов на взвешенное множество слов слева называется: В X А = {7 • w|3a • v в В ,/3 • и е А, и = vw} -= {71 -101,72 .......... -wm,...}, где выполнено условие: Vi,j(yt/lj =

( Е <*k-0,)/( Е <**•/?«))■

{¡t,i|utre,=Hl} {W|l*Uj=Ul}

Значения весов можно вычислить по следующей формуле: Г = {7^1 = 1,2,. ..д-..} = { Е ак-р1\г=1,2,...,т,...}.

{fc,í|utrr¿=U¡>

Пример. В = {la, Щ, А = {\af, \bg, \ch, \ ад}. В\А = {¿а, ¿6} X {\а/,\Ьд,\ск,\ад} = {ъ/,129}. X = {хг,х2}. И = И = *2 = И + 1.1 = 1 ^ =_£!_ = A = i 72 = = TÍT = I В\А = {5/, §у}.

2 4 4- ц+и J l¿ x¡+xt i+j i

Пример. На рис. 4 приводится пример изображения формулы. Пусть получены следующие неопределенности: символ 's' имеет варианты распознавания '5' и V, а 'п' имеет варианты распознавания 'п' и 'г'. Результат можно представить в виде следующего взвешенного выражения: «(|-5||-s)(i)(|-n|3-r)(x)».

Шаблон синуса задается в виде следующего регулярного выражения: «sin.», где точка означает один любой символ. Требуется найти пересечение регулярного выражения результата с шаблоном. Согласно теореме: I = (| • 5|§ • s) (») (| • п|| • г) (1) П sin. = (| • 5) h\ (I ■ 5) h, где h = (г) (I • "Is • г) (х) П (| • 5) X sin., 12 = (г) (| ■ п|| • г) (х) П (| • s) X sin.. Далее требуется вычислить Д. Для этого находится левое деление (| • 5)\sm. Очевидно, что 1\ = 0- Это следует из того, что строки, удовлетворяющие шаблону sin. не могут начинаться с цифры 5.

Тогда I = (1 • s) h. Далее вычисляется /2- Для этого находится левое деление (| • s) X sin. После применения теоремы о делении слева получается

Рис. 5: Пример скелета символа (| • ,s) X sin. = т.. Тогда /2 = (г) (§ • п|| • г) (х) П т.. Далее снова применяя теоремы о пересечении и о делении получается конечный результат I = (1 ■ s) (i) (1 - n) (х) или I — 1 ■ sinx. Множество результатов содержит только один элемент и вес этого элемента равен единице, поэтому с уверенностью можно сказать, что полученный вариант является наиболее приоритетным среди всех ранее имевшихся.

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

Алгоритм распознавания отдельных символов основывается на построении графа символа.

Пример. На рис. 5 изображен пример символа. В левой части приведен скелет символа. В центре пронумерованы критические точки (точки пересечения кривых и крайние точки) в порядке увеличения горизонтальной координаты. Справа пронумерованы критические точки циркуляционным методом.

Так как точка пересечения только одна, то за ней закрепляется номер 1. Для каждой крайней точки выполняется поиск критической точки, связанной с текущей через промежуточные точки. В результате найдены три пары: (2,1), (3,1) и (4,1). Далее вычисляются вектора, соединяющие эти точки. Набор векторов сортируется по часовой стрелке. Минимальным направлением считается направление, соответствующее 9 часам. Согласно такой сортировке минимальным элементом является пара (3,1). Таким образом, за точкой 3 закрепляется номер 2, а за точками 2 и 4 закрепляются номера 3 и 4 соответственно.

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

точки. С учетом самих критических точек 1 и 2 длина кривой составляет 24 точки. Для описания ребра кривая делится на 8 равных частей. Первому фрагменту соответствует северо-западное направление (пги). Второму фрагменту соответствует северное направление (п). Полностью первое ребро примет вид: 12(пги,п,п,п, е,е,е,е). Аналогично вычисляются два оставшихся ребра 13(е, е, е, е, е, е, е, е) и 14(5, 5, в, 5е, пе, е, е, е).

При сопоставлении выбираются только те шаблоны, в которых такое же количество вершин и такая же схема ребер, т.е. ребра соединяют вершины с теми же номерами. Шаблоны составлены с учетом возможных вариантов написания каждого символа. Шаблон буквы Е представлен графом: ({1,2,3,4}, {12(п, п, п, п, е, е, е, е), 13(е, е, е, е, е, е, е, е), 14(5,5, .5,5, е, е, е, е)}). Необходимо сравнить соответствующие наборы (пгу, п, п, п, е, е, е, е) и (п, тг, тг, п, е, е, е, е). В результате сравнения получена величина, равная 750 = 50+100+ 100 + 100+100+100+100+100, так как только первые фрагменты полностью не совпадают. Аналогично сравниваются другие два ребра, в результате чего получены величины 800 и 700. Итоговая сумма равна 2250. Таким образом, процент соответствия с шаблоном буквы Е составляет = 93,75% (так как всего 3 ребра и каждое состоит из 8 фрагментов).

Алгоритм построения дерева строки основывается на сопоставлении шаблонного графа изображения формулы и графа изображения формулы, построенного для текущих входных данных. Шаблоны построены согласно имеющимся данным о возможных иерархических структурах в изображениях наиболее распространенных классов формул. На начальном этапе имеется множество графов, соответствующих отдельному символу, т.е. их число равно числу символов в формуле. Требуется объединить все графы при помощи ребер таким образом, чтобы получился один связный граф. На каждом шаге алгоритма объединяются два графа согласно их взаимному расположению таким образом, чтобы полученный граф соответствовал классу формулы. Граф задается в виде списка вершин и списка ребер. В свою очередь каждая вершина задается некоторым идентификатором и списком ребер, а каждое ребро задается списком векторов направлений и идентификаторами начальной и конечной вершин. Вводятся вспомогательные функции. Рс ■ в —> {0,1} равно единице, если значением вершины является константа и равно нулю, если вершина может

быть заменена графом другого класса формулы. Ff/ : 5 —> 1/т возвращает множество ребер, выходящих из текущей вершины. Р] : 5 —>• V возвращает ребро, входящее в текущую вершину. Р^тя : 5" —> 5ТЛ возвращает текст, хранящийся в вершине графа. ^ : I/ —> О возвращает направление текущего ребра. Функция Рти : ит х 11т —> {0,1} будет проверять соответствие множества ребер одного графа с множеством ребер другого графа: ' 1, VI £ Ь Зг € 11 Рл{1) = ^(г)

FTU{L,R)

• О, 31 € L Vr е R Fd(l) Ф Fd(r) Функция возвращает единицу, если для каждой вершины одного из множеств найдется вершина из другого множества, у которых совпадают направления. Функция Ft : S х S —> {0,1} будет определять, соответствует ли вершина текущего графа вершине шаблонного графа и может ли она быть на нее заменена:

1, Fc(r) и FSTp(l) = FSTR(r) и Ftu(Fu(1), Fv{r)) 1, ~>Fc(r) и Ftu(Fu(1), Fu(r)) О, в остальных случаях Функция возвращает единицу, если есть взаимно однозначное соответствие между ребрами, выходящими из вершин, и если в шаблонной вершине установлено условие обязательной константы при условии, что в текущей вершине хранится нужная константа, либо в любом другом случае при отсутствии условия обязательной константы.

Алгоритм проверки соответствия / и р состоит из следующих шагов:

1. Выбрать вершину е\ из / и е2 из р (если ранее не происходило выбора, то в качестве е\ берется начало /, а в качестве е2 — начало р).

2. Если нет элементов для выбора ej и нет элементов для выбора е2, то графы соответствуют друг другу. Завершить выполнение алгоритма.

3. Если выбрана е2 и нет элементов для выбора еь то графы не соответствуют друг другу. Завершить выполнение алгоритма.

4. Если выбрана е.\ и нет элементов для выбора е2, то в графе р последовательно заменяя вершину соответствующую L(Fi(e1)) на графы р„ выполнить данный алгоритм для графа / и новых графов р. Если не найдена замена, дающая положительный результат, то графы не соответствуют друг другу. Если замена найдена, то графы соответствуют друг другу. Завершить выполнение алгоритма.

GlA a-fr | a-A

Рис. 6: Пример изображения формулы сложной дроби

5. Если ->Fr(ei, е2), то / не соответствует р. Завершить выполнение.

6. Перейти к пункту 1.

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

Пусть 13 = ({с, с, с}, Vh) — шаблон линейной формулы из трех компонент, /7 = ({с, с, с, с, с, с, с}, Vh) — шаблон линейной формулы из 7 компонент. Числитель соответствует графу /3, знаменатель — графу /7. Пусть /гас — граф простейшей дроби. Таким образом исходный граф состоит из вершины - и двух подграфов 91 = ({<?, I, A}, Vi) и q2 = ({a, G, |, a, •, A}, V2), с которыми связана вершина - по верхнему и нижнему направлениям соответственно. Такой граф соответствует только графу дроби frac\д. Тогда основа шаблона сложной дроби будет состоять из графа frac = /raci,i = ({-, с, с}, Ufrac), где с — формула, состоящая из одного символа. Но так как верхний и нижний подграфы не соответствуют формуле из одного символа, то выполняется поиск соответствующих шаблонов. Для подграфа qi таким шаблоном служит граф Z3, а для чг — граф 17. Тогда получен шаблон frac = ({-,¿3,k},Ujrac) = /гас3,7. Полученному шаблону полностью соответствует граф обрабатываемого изображения, значит результат распознавания выглядит следующим образом:

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

Пусть S — регулярное выражение результата, А — шаблон. Необходимо найти пересечение множеств, заданных регулярными выражениями S и А.

Для представления всех форм регулярных выражений вводится перечисление Туре, со значениями empty, constant, union, multiplication, iteration (сокра-

щенно е, с, и, т, г). Регулярное выражение представляется в виде объекта класса RegExpr, состоящего из следующих полей type (тип выражения), left (вложенное регулярное выражение), right (вложенное регулярное выражение), string (символ константы) (сокращенно t, I, г, s). Поля заполняются в зависимости от типа операции. Тогда регулярные выражения S и Л можно представить в виде объекта RegExpr. Функция создания нового регулярного выражения определяется следующим образом: FR : RE х RE х Т —>• RE, где RE — пространство объектов класса RegExpr, а Т — пространство классов операций. Через 0 обозначается как пустое регулярное выражение, так и пустая последовательность выражений. Тогда функция Fr выглядит следующим образом: {о, {I, г}, "" }, о = multiplication или о = union,

{iteration, {1}, "" }, о = iteration, {constant, 0,1.string}, о = constant,

{empty, 0, "" }, о = empty.

Деление слева Fp : RE x RE —> RE определяется следующим образом:

Fp(l, r,o)= <

fh(l,r) =

r.type = e, r.type = с и I = r, r.type = с и l ф r, r.type = i, u,

{е,0, "" }, {с,0, ""}, {е,0, ""},

Рв(Рв(1,г.1е/г),Е0(1,г.НдМ),и), гЛуре ■ Ер(Ег)(1,г.1е/^,г.НдМ,тп), гЛуре = тпи "" ^

г./е/«), т),

Р0{1,г.НдЫ),и), гЛуре = та "" €

Кроме того, вводится дополнительная функция ^г (^г : —> Л), которая по объекту Ги^Ехрг будет возвращать ее классическое представление в виде строки. Для нахождения пересечения двух регулярных множеств вводится функция^/ : RE х RE —» RE:

I, 11 = с и /.в € ^г(г),

{е,0, ""}, И = сн1.8фРт{г),

Рц(1.1,Р1(1.1,Р0{1.1.з,г)),т), 1Л = т и = с,

*>(*,г) = ^(ЗД/.-РЖсД "" },^о(/.г.5,г-)),т),

{с, 0, "" }, т), г), и), и = и,

FRiFRil.ll, Ы1.г, г)), т),

FIiFRil.l.r,l.r,m),r),u), 1Л = т.

Рис. 7: Пример изображения формулы

Пример. На рис. 7 приведен пример изображения формулы. Исходная распознанная формула имеет вид: а|„Ь <=> Vp^Vrc^ofp"!« => РП|Ь)- Так как в результате имеются несбалансированные скобки, то логично проверить ее на соответствие шаблону, содержащему сбалансированные скобки. Шаблон имеет следующий вид: «.*\(.*\).*».

Результат принимает следующий вид: «(a)(\|)(b)(<)(=)(0.55->|0.45-\))(\forall) (p)(\forall)(n)(0.52.\[|0.48-\0(p)(\l)(a)(=)(>)(p)(\l)(b)(\))».

После применения функции Fj к шаблону и регулярному выражению текущего результата получается следующее взвешенное регулярное выражение: «0.55-(a\|b<=>\forallp\foralln\(p\|a=>p\|b\))| 0.45-(a\|b<=\)\forallp\foralln\(p\|a=>p\|b\))».

В качестве верно распознанного результата берется первая часть выражения так как ей соответствует больший вес. Уточненный результат принимает вид: а|„6 <=> Vp<1/Vn^0(pn|a => р"|Ь).

В четвертой главе приводятся основные результаты испытаний разрабатываемого алгоритма. При выполнении экспериментов были соблюдены следующие правила к написанию текста: фон белый, цвет текста темно синий или черный, символы не наезжают на соседние символы. Сканирование выполнялось с разрешением 200 dpi в цветном режиме. Формулы от обычного текста отделялись ручным способом. Результаты проведенных исследований при определении точности распознавания классов формул при использовании различных почерков приведены в таблице 1. Каждому классу формулы соответствует по 10 испытаний для каждого из почерков. Рассматриваются классы простейших формул, называемых формулами первого типа сложности. Также рассматриваются формулы второго типа сложности, т.е. такие формулы, которым соответствуют графы изображений формул с рекурсивной заменой вершин с вложенностью равной единице. Сами формулы называются формулами первого уровня, а вложенные — формулами второго уровня. В таблице (в колонке «Шаблон формулы») использованы следующие обозначения: а, 6, с — любые отдельные символы; к — цифра либо латинская буква; /ь /2, /з — формулы первого типа сложности, являющиеся формулами второго уровня; Ч—

Таблица 1: Результаты исследований на различных классах формул

№ Класс Шаблон Число Число Точность

формулы формулы испытаний ошибок (%)

1 Отдельный символ с 100 6 94

2 Линейная формула ab 100 7 93

3 Линейная формула а + Ь 100 6 94

4 Степень аь 100 8 92

5 Нижний индекс ак 100 6 94

6 Дробь а h 100 6 94

7 Интеграл J х dx 100 5 95

8 Интеграл Ь $ х dx а 100 7 93

9 Корень у/а 100 3 97

10 Линейная формула hfl 100 10 90

11 Линейная формула fl+h 100 6 94

12 Степень ff 100 6 94

13 Нижний индекс au 100 11 89

14 Дробь L h 100 7 93

15 Интеграл J h dx 100 9 91

16 Интеграл h ff3 dx h 100 11 89

17 Корень Vfr 100 7 93

символ операции (например: +, —, х); х — латинская буква.

При распознавании корней и интегралов первого типа сложности получены наивысшие точности, несмотря на то, что структура этих формул сложнее, чем у линейных формул и индексов. Это связано с тем, что применение регулярных выражений и шаблонов классов простейших формул позволяет использовать больше параметров при сопоставлении. К таким параметрам можно отнести наличие спецсимволов, характерных только для этих классов формул. Формулы вида а + Ь распознаются лучше, чем формулы вида аЬ. Это связано как с наличием спецсимвола в первом, так и с неэффективностью задания шаблона для формул вида аЪ, не привязанного к конкретному символу. Если рассматривать различные почерки, то ошибки в основном связаны с наличием в тексте символов с ранее неизвестным способом начертания и с нарушением правил взаимного расположения символов в конкретных классах формул.

Скриншот программы приведен на рис. 8. К основным функциональным возможностям программы относятся возможность открытия графического фай-

BIOS

«Л, >«_ с«« CW

Ht) , I^X.X?) и ( г , t j - решение [ MJ^,

!ТСЯ такое k , что , h. > 0 . и дня любого х° , iporo h.|x°- х. , выполнено ЦМ]^ .

ШЛОЯЕНИЕ 2.2. Если Vi.» íoL- iV + ß. • x'\ . h < \> .

í_Распознать

□

Pt»ni ¡цаавгеяя

<¿¡ BbCCrtWÜ ФОС»^ГЫ О Клраимш О Явепж

Рис. 8: Скриншот программы ла (форматы bmp, jpg, png), сохранение графического файла (формат bmp), создание нового изображения, выделение фрагментов изображения как фрагментов рукописных формул с помощью указателя, редактирование изображения с помощью инструментов карандаш и ластик, распознавание отдельных выделенных фрагментов, распознавание всего изображения, обучение распознаванию новых символов, сохранение результатов в формате Т^Х.

Заключение

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

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

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

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

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

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

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

Научные публикации по теме диссертации

Статьи в изданиях, рекомендованных ВАК РФ:

1. Сапаров А. Ю., Бельтюков А. П. Математическое моделирование изображений формул с целью их распознавания // Вестник Удмуртского университета. Сер. 1, Математика. Механика. Компьютерные науки. — 2013. — Вып.

1. - С. 153-167.

2. Сапаров А. Ю., Бельтюков А. П. Применение регулярных выражений в распознавании математических текстов // Вестник Удмуртского университета. Сер. 1, Математика. Механика. Компьютерные науки. — 2012. - Вып. 2. — С. 63-73.

Прочие публикации:

3. Сапаров А. Ю., Бельтюков А. П. Распознавание текстов с математическими формулами // 6-я Всероссийская мультиконференция по проблемам управления, с.Дивноморское, 30 сентября-5 октября 2013 г. // Материалы муль-тиконференции: в 4 т. Т.1./ — Ростов-на-Дону: Изд-во ЮФУ, 2013. — С.80-84.

4. Сапаров А. Ю., Бельтюков А. П. Распознавание математических текстов регулярными выражениями // Современные информационные технологии в образовании и научных исследованиях (СИТОНИ-2012): 3 междунар. науч,-техн. конф. студентов и молодых ученых, 4-5 окт. 2012 г., г. Донецк: сб. науч. тр. студентов, магистрантов, аспирантов и преподавателей. — Донецк: Изд-во ДонНТУ, 2012. - С. 108-116.

5. Сапаров А. Ю. Распознавание рукописных математических текстов. // Системный анализ и информационные технологии (САИТ-2011) труды IV Международной конференции (Россия, Абзаково, 17-23 августа 2011 г.). Том

2. — Челябинск: Изд-во Челяб. гос. ун-та, 2011. — С. 196-201.

6. Сапаров А. Ю. Распознавание текстов с математическими формулами // Технологии информатизации профессиональной деятельности (в науке, образовании и промышленности) - ТИПД-2011: тр. 3 Всерос. науч. конф. с междунар. участием, Ижевск, 8-12 нояб. 2011 г. — Ижевск: Удмурт, ун-т, 2011. — [Т.1].-С. 78-79.

7. Сапаров А. Ю. Статическое распознавание математических текстов II XXXIX итоговая студенческая научная конференция: материалы конф. (апр. 2011 г.) — Ижевск: Удмурт, ун-т, 2011. — С. 42-43.

Авторская редакция

Отпечатано с оригинал-макета заказчика

Подписано в печать 23.04.14. Формат 60x84 "Лб. Тираж 100 экз. Заказ № 783.

Типография ФГБОУ ВПО «Удмуртский государственный университет» 426034, Ижевск, ул. Университетская, 1, корп. 2. Тел. 68-57-18

ФГБОУ ВПО «Удмуртский государственный университет»

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

АНАЛИЗ И МОДЕЛИРОВАНИЕ СТРУКТУРЫ РАСТРОВЫХ ИЗОБРАЖЕНИЙ РУКОПИСНЫХ МАТЕМАТИЧЕСКИХ ФОРМУЛ С ЦЕЛЬЮ ИХ АВТОМАТИЧЕСКОГО РАСПОЗНАВАНИЯ

Специальность: 05.13.01 Системный анализ, управление и обработка информации (в науке и технике)

П/.*5П4 ¿¿ГИ 4 /. У"Т4.и 1 1 1 Т

Сапаров Алексей Юрьевич

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

Научный руководитель д.ф.-м.н., проф. А.П. Бельтюков

Ижевск — 2014

Оглавление

Введение 4

1 Обзор методов и систем автоматического распознавания текстов 15

1.1 Обзор методов........................................................15

1.1.1 Статический метод..........................................15

1.1.2 Динамический метод........................................16

1.2 Подходы к распознаванию различных видов текстов............18

1.2.1 Распознавание сплошного текста..........................19

1.2.2 Распознавание текста, содержащего структурированные элементы (таблицы, диаграммы, рисунки)................20

1.2.3 Распознавание математических формул....................22

1.3 Методы, применяемые при различных способах ввода текста . 23

1.3.1 Распознавание печатного текста............................24

1.3.2 Распознавание последовательности записи................26

1.3.3 Распознавание сканированного рукописного текста ... 28

1.4 Обзор систем распознавания текстов..............................29

1.4.1 ABBYY FineReader..........................................29

1.4.2 Math input panel..............................................32

1.4.3 InftyReader....................................................34

1.4.4 GOCR ........................................................36

1.5 Выводы по главе......................................................37

2 Задача распознавания математических текстов 40

2.1 Описание задачи......................................................40

2.2 Описание метода распознавания математических текстов .... 47

2.2.1 Скелетизация изображения..................................49

2.2.2 Вертикальное и горизонтальное проектирование .... 53

2.2.3 Разбор структуры символа..................................57

2.2.4 Построение и анализ дерева строки........................61

2.2.5 Уточнение с помощью регулярных выражений..........80

2.2.6 Построение математических выражений..................93

2.3 Описание метода адаптации (обучения)............................96

2.3.1 Адаптация к конкретному тексту..........................99

2.3.2 Использование предыдущих результатов распознавания 101

2.3.3 Адаптация к пользователю..................................103

2.4 Описание форматов представления математических формул . . 105

2.4.1 Формат TeX..................................................106

2.4.2 Формат MathML..............................................108

2.5 Методы распознавания «смешанных» текстов....................111

2.5.1 Рукописные формулы в рукописном тексте................113

2.5.2 Рукописные формулы в печатном тексте..................115

2.6 Выводы по главе......................................................117

3 Описание алгоритма 119

3.1 Описание алгоритма распознавания математических текстов . . 119

3.2 Описание алгоритма обучения......................................135

3.3 Выводы по главе......................................................140

4 Экспериментальные исследования разработанного алгоритма 143

4.1 Эксперименты на различных типах формул ......................143

4.2 Эксперименты на текстах с подобными формулами..............145

4.3 Эксперименты с разными почерками..............................148

4.4 Сравнительный анализ с существующими системами............152

4.5 Выводы по главе......................................................155

Заключение 158

Литература 159

Введение

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

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

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

Таким образом, задача распознавания текстов с математическими формулами в настоящее время является актуальной.

Под задачей распознавания текстов подразумевается задача автоматического определения классов всех объектов, содержащихся в исходном изображении по конечному набору свойств и признаков этих объектов [1], [2], [3]. Основная сложность автоматического распознавания формул состоит в сложности их иерархической структуры и их большом разнообразии. Для анализа сложной структуры предлагается использование ориентированных графов, на основе которых будет построена модель изображения формулы. Так как все люди имеют уникальный почерк, то каждый символ имеет множество вариантов

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

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

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

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

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

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

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

Зададим шаблоны простейших классов математических формул в виде графов изображений формул. К таким классам можно отнести формулы следу-

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

Для определения класса формулы требуется найти соответствующий ему шаблон. Очевидно, что при распознавании простейших формул соответствующий шаблон найдется среди базовых. При обработке более сложных формул требуется построение новых шаблонов. Так как используемые графы это позволяют, то могут быть определены классы формул любой сложности, в которых на каждом уровне иерархии используются только классы известных простейших формул. Построение новых шаблонов производится рекурсивно с перебором всех вариантов шаблонов простейших формул, одновременно с сопоставлением уже имеющихся частей шаблона со структурой входных данных. Если по какой-то причине находится несоответствие шаблона и исходных данных, например, отсутствует какой-либо обязательный символ, то дальнейшее построение по данной ветви рекурсии прекращается. В конечном итоге будут получены большие шаблоны соответствующие структуре входных данных, среди которых выбираются наиболее подходящие согласно процентам совпадений с шаблонами низших уровней, а также с использованием регулярных выражений. Таким образом, графы изображений формул дают мощный механизм при анализе различных образов [4], [5], [6], который может быть использован при решении других подобных задач.

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

Рассмотрим небольшой пример. Пусть имеется изображение формулы cos (ж).

Допустим, по каким-либо причинам в результате распознавания буква о имеет сразу два варианта распознавания. Очевидно, что этими вариантами являются сама буква о и цифра 0. Пусть процент совпадения шаблона буквы с изображением в формуле равен 50%, а процент совпадения с цифрой 0 — равен 70%. Тогда, следуя принципу выбора максимально похожего символа, в результате будет получена формула: cOs(x), что, конечно же, является неправильным решением данной задачи.

Рассмотрим другой вариант решения данной задачи. Учитывая то, что неопределенность имеется только при распознавании символа 'о', можем однозначно сказать, что правильным решением является либо cos (ж), либо cOs(x). Зададим шаблон формулы в виде строки cos(x). Тогда наиболее приоритетным будем считать тот вариант распознавания, который соответствует шаблону формулы. В этом случае, вариант распознавания cos(:c) полностью соответствует шаблону cos(x) и значит, является правильным решением данной задачи, хотя по отдельности совпадений символов с шаблонами больше в варианте cOs(rc).

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

Пусть теперь в исходных данных аргумент х заменили на у, т.е. имеется изображение формулы cos (у). Для такой формулы уже совпадения с шаблоном не будет, так как в шаблоне cos(x) явно прописано, что аргумент должен быть х, а не у. Для возможности распознавания такой формулы при наличии неопределенностей следует ввести шаблон cos(y). Но сложность формулы не ограничивается всего лишь такими незначительными изменениями, так как могут быть еще формулы cos(z), cos(2:r), cos(a:+^) и т.д. Таким образом, становится практически невозможным выделение какого-либо конечного множества шаблонов, чтобы возможно было распознавать все используемые формулы.

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

принадлежат множеству, порождаемому данным регулярным выражением, так как х, у, ъ, 2х, х+у являются строками с длиной больше нуля.

Представим результат распознавания с наличием неопределенности в виде следующего регулярного выражения: с(о|0)з\(х\), где (о|0) говорит о том, что в данном месте может быть любой из символов, разделенных вертикальной чертой. Таким образом, были получены два множества, одно из которых порождается регулярным выражением с(о|0)з\(х\), а другое — регулярным выражением С08.+. Очевидно, что первое множество является конечным, точнее содержит 2 элемента, а второе — является бесконечным. Не трудно предположить, что для решения данной задачи необходимо найти общие элементы двух этих множеств, т.е. найти пересечение этих множеств. Задача легко решается обычным перебором, если оба множества являются конечными и содержат сравнительно небольшое число элементов. Но в данном случае одно из множеств является бесконечным, следовательно, такой метод не подходит и требуется другой подход к решению задачи.

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

(¿6,-с) ПА = Е(Ь<(СП(Ь,ХА))).

4=1 7 г=1

По условию теоремы одно из регулярных выражений должно быть конечным и представлено в виде конкатенации объединений, т.е. чередованием вариантов выбора. Этому условию полностью соответствует выражение с(о|0)з\(х\), где чередуются с, (о|0), в, \(, х, \) и каждый элемент представлен вариантом выбора, в частном случае вариантом выбора из одного элемента.

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

а X (е^ег) = (а X е\\а X е2), а X б = 0,

( ((аХе1)е2|аХе2), б е е: [ ((аХе 1)е2), б £ е1

а X е* = (а X е)е*, а X Ъ = 0, а фЪ,

где В \ А означает деление множества слов А на множество слов В слева (в

частном случае деление на символ слева) и определяется следующим образом:

B\A = {w\3v е в ,vw £ А}.

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