Содержание к диссертации
Введение
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 Формат ТБХ 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
Литература
- Подходы к распознаванию различных видов текстов
- Обзор систем распознавания текстов
- Уточнение с помощью регулярных выражений
- Эксперименты с разными почерками
Введение к работе
Актуальность работы. В настоящее время существует множество текстовых документов в бумажном виде, содержащих вписанные от руки математические формулы. Это в основном тексты, напечатанные ранее на пишущих машинках, либо на компьютерах до появления программ набора математических формул. Это связано с тем, что компьютеры появились сравнительно недавно, а история науки, так или иначе связанной с математикой, включает уже много веков. С развитием информационных технологий рано или поздно требуется перевод документов в электронный формат.
Уже существуют системы, которые с достаточно высокой точностью распознают обычные печатные тексты со сканированных изображений. Систем, распознающих сканированные математические формулы, пока не существует. Для перевода таких текстов в электронный формат требуется использовать ручной способ ввода формул. Если текст содержит много формул, то эта работа является достаточно трудоемкой. Учитывая то, что большинству пользователей с трудом удается вводить даже самые простые формулы, то для этой работы нужны специально подготовленные люди.
С постепенной автоматизацией многих процессов в различных сферах, более приоритетным является обучение компьютера распознаванию формул, а не подготовка специально обученных людей. Ввод формул в компьютер является достаточно сложной задачей, поэтому в качестве основной цели рассматривается не только возможность автоматического распознавания сканированных рукописных формул, но и облегчение процесса ручного ввода формул.
Таким образом, задача распознавания текстов с математическими формулами в настоящее время является актуальной.
Основная сложность автоматического распознавания формул состоит в сложности их иерархической структуры и их большом разнообразии. Для анализа сложной структуры предлагается использование ориентированных графов, на основе которых будет построена модель изображения формулы. Так как все люди имеют уникальный почерк, то каждый символ имеет множество вариантов написания. Кроме того, распечатанные на бумаге тексты со временем могут потерять свое качество из-за влияния внешних факторов. Следовательно, сканированное изображение будет иметь некоторые дефекты, свя-
занные с появлением шумов или потерей фрагментов текста. В связи с этим при распознавании отдельных символов могут быть получены некоторые неопределенности, т.е. такие ситуации, в которых однозначно нельзя определить класс символа, к которому относится та или иная компонента изображения. Для выбора наиболее правильного варианта в данном случае предлагается использовать специальные текстовые шаблоны, называемые регулярными выражениями.
Степень разработанности проблемы. Исследования в области анализа и распознавания текстов рассматривали в своих работах H.S. Baird, Н. Saiga, N. Matsakis, K.-F. Chan, D.-Y. Yeung, M. Suzuki, Садыков С.С, Самандров И.Р., Салюм Сайд Салех, A. Belaid, J.R Haton, R.H. Anderson, Фу КС, Исупов Н.С., Кучуганов А.В., Костюк Ю.Л. и др.
В настоящее время существуют следующие приложения, распознающие математические формулы: Math input panel, InftyReader, GOCR. Math input panel является системой динамического распознавания рукописных формул, поэтому не может быть применена к обработке сканированных текстов. InftyReader и GOCR предназначены для распознавания печатных текстов с растровых изображений. Требуемое качество не достигается при сканировании изображений, поэтому точность распознавания не высокая. Ни одна из существующих систем не распознает сканированные рукописные формулы.
Объектом исследования являются растровые изображения текстов, с содержащимися в них рукописными математическими формулами.
Предметом исследования являются методы анализа изображений и построения моделей изображений формул.
Цель работы — разработка и исследование средств анализа изображений со сложноструктурированными объектами и автоматического распознавания рукописных математических формул со сканированных изображений, в которых одновременно могут находиться как рукописные формулы, так и обычный печатный текст.
Для достижения этой цели требуется решить следующие основные задачи: 1. Выполнить подробный анализ проблем, возникающих при обработке изображений со сложноструктурированными объектами, с целью выявления возможных вариантов их решения. Исследовать существующие системы, решаю-
щие задачи, связанные с распознаванием текстов.
-
Разработать метод анализа графических изображений со сложной иерархической структурой на основе ориентированных графов. Построить модель изображения математической формулы. Разработать алгоритм распознавания иерархической структуры изображения математической формулы.
-
Разработать метод использования регулярных выражений для уточнения результатов обработки текстов при наличии в них неопределенностей. Разработать алгоритм нахождения пересечения множеств, заданных регулярными выражениями. Рассмотреть варианты адаптации алгоритма к различным условиям с целью повышения точности распознавания.
-
Произвести экспериментальные исследования предложенных алгоритмов.
Методы исследования. Теоретические исследования выполнены с использованием методов теории множеств, теории графов, теории алгоритмов и теории искусственного интеллекта. При решении практической части использовалась технология объектно-ориентированного программирования.
Достоверность и обоснованность полученных в работе результатов подтверждается корректностью построенных моделей, полным доказательством используемых теорем при использовании регулярных выражений, положительными результатами при выполнении экспериментальных исследований.
Научная новизна.
-
Предложен новый способ описания изображений сложноструктурированных текстов. Для этого используется понятие двумерно ориентированного графа, в котором ребра могут задавать не только общую информацию о наличии связи между вершинами, но и характер этой связи с точки зрения направления на плоскости. Кроме того, направление может задаваться сразу целым набором двумерных векторов, что позволяет более детально описывать траекторию движения от одной вершины до другой.
-
Разработан метод построения графа любой сложности, удовлетворяющего текущему языку математических формул. Метод основан на использовании графов изображений формул в качестве базисных графов.
-
Предложен новый способ задания множества возможных вариантов распознавания текста, который позволяет учитывать вероятности тех или иных исходов как всего выражения, так и отдельных фрагментов и символов. Для
этого вводится понятие взвешенных регулярных выражений, порождающих взвешенные регулярные множества, отличающиеся от обычных регулярных множеств тем, что каждому элементу задается некоторый числовой вес, отражающий превосходство одних элементов над другими. Результат распознавания задается взвешенным регулярным выражением.
4. Разработан метод нахождения пересечения множеств, заданных регулярными выражениями, который применяется для проверки соответствия результата распознавания используемому языку. Предложенный метод позволяет использовать словарь с бесконечным числом элементов, который задается в виде регулярного выражения.
Практическая полезность.
-
Проанализирована иерархическая структура изображений рукописных математических формул. Построена наглядная и понятная человеку модель изображения формулы с использованием понятия графа изображения формулы.
-
Разработан алгоритм построения шаблона формулы в виде двумерно ориентированных и двухуровневых графов.
-
Проанализирована структура математических формул с точки зрения их широкого разнообразия и возможности их структурной классификации.
-
Обоснована целесообразность использования регулярных выражений в качестве шаблонов формул для уточнения результатов распознавания. Исследована возможность представления промежуточного результата распознавания с наличием неопределенностей в виде регулярного выражения и последующего нахождения пересечения множества возможных вариантов распознавания с бесконечным множеством шаблонов формул.
-
Разработан алгоритм нахождения пересечения множеств, заданных регулярными выражениями. Разработан алгоритм нахождения пересечения множеств, заданных взвешенными регулярными выражениями, позволяющими упорядочивать элементы порождаемого множества по некоторым признакам с учетом особенностей как всего выражения, так и каждой компоненты по отдельности.
-
Проведены экспериментальные исследования предложенных алгоритмов. В результате использования графов становится возможным автоматическое распознавание иерархической структуры изображения формулы. Алгоритм применения регулярных выражений позволяют проверять результат распознава-
ния с точки зрения соответствия языку математических выражений. На защиту выносятся.
-
Результаты исследований сложноструктурированных текстов и особенности их обработки. Результаты исследований существующих систем распознавания математических формул.
-
Новые понятия, основанные на ориентированных графах, и методы построения модели формулы. Модели формул, построенные с использованием графов изображений формул. Методы построения шаблонов сложных формул на основе нескольких базовых с использованием текущего результата распознавания и алгоритм сопоставления результатов распознавания с шаблонным графом изображения формулы.
-
Новые понятия, основанные на регулярных выражениях, и теоремы, связанные с этими понятиями. Алгоритм нахождения пересечения множеств, заданных регулярными выражениями. Алгоритмы пересчета числовых параметров алгоритма при адаптации к конкретным условиям.
-
Результаты экспериментальных исследований.
Работа включает следующие области исследований:
-
Методы и алгоритмы структурно-параметрического синтеза и идентификации сложных систем.
-
Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации.
Реализация результатов работы. Теоретические и практические результаты работы используются на кафедре теоретических основ информатики ФГБОУ ВПО УдГУ. Кроме того, теоретические результаты работы планируется применять для решения задачи распознавания химических формул и для решения задачи автоматизированной проверки решений математических задач.
Личный вклад автора. Автором лично предложен метод решения поставленной задачи; строилась модель изображений формул на основе ориентированных графов; проводилось описание новых объектов, основанных на регулярных выражениях, с обоснованием целесообразности их применения в текущей задаче; разрабатывалась система автоматического распознавания сканированных рукописных формул; подготавливалась база шаблонов и анализировались полученные результаты.
Апробация работы. Основные результаты работы докладывались и обсуждались на научных конференциях: XXXIX итоговая студенческая научная конференция, УдГУ, г.Ижевск, 2011г.; 4-я международная конференция «Системный анализ и информационные технологии» — САИТ-2011, с.Абзаково, 2011г.; Всероссийская научная конференция с международным участием «Технологии информатизации профессиональной деятельности (в науке, образовании и промышленности)» — ТИПД-2011, г.Ижевск, 2011г.; 3-я международная научно-техническая конференция студентов и молодых ученых «Современные информационные технологии в образовании и научных исследованиях» — СИТОНИ-2012, г.Донецк, 2012г.; 6-я Всероссийская мультиконференция по проблемам управления — МКПУ-2013 «Управление в интеллектуальных, эрга-тических и организационных системах» — УИнтЭргОС-2013, с.Дивноморское, 2013г.
Публикации. Результаты работы отражены в 7 публикациях, в том числе в 2 изданиях, рекомендованных ВАК.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения. Содержит 168 страниц машинописного текста с таблицами и изображениями. Список литературы включает 105 наименований.
Подходы к распознаванию различных видов текстов
Сплошной текст — это текст, написанный на человеческом языке, который может содержать только слова из некоторого словаря (обычно это словарь какого-то конкретного языка или нескольких языков, если текст многоязычный), цифры, знаки препинания, а также другие знаки, используемые при оформлении (например, скобки). Такие тексты имеют строгую строчную структуру, т.е. цепочки символов находятся на условных прямых, параллельных друг другу. Подробнее о структуре таких текстов и методах распознавания можно ознакомиться в других работах, например в [17].
Исходя из структуры текста, наиболее правильным подходом для распознавания такого текста является метод последовательного разделения изображения на отдельные составляющие, т.е. последовательного выделения строк, слов и букв. Выделение таких фрагментов осуществляется на основе анализа промежутков между темными областями изображения. Для достижения этой цели используются алгоритмы горизонтальной и вертикальной сегментации. Горизонтальная выделяет строки, а вертикальная соответственно отделяет слова и при возможности буквы друг от друга.
Для выделения строк обязательным условием является «строго» горизонтальное расположение строк на листе. «Строго» в данном случае означает, что величина наклона каждой строки должна быть такой, чтобы была возможность между любых двух строк провести горизонтальную прямую, которая не пересекает ни одну из них. Данный параметр напрямую зависит от длины строк и межстрочного интервала. Чем длиннее строка, тем больше вертикальная разница между началом и концом строки. Чем меньше межстрочный интервал, тем меньше пространство для проведения прямой линии.
Условия при вертикальной сегментации аналогичные. Но в данном случае решающую роль играют не длины строк и интервалы между ними, а высота букв, пробелы и расстояния между отдельными буквами одного слова.
Так как рассматриваемые методы распознавания в основном касаются сканированных текстов, то основной причиной невозможности применения алгоритмов сегментации может послужить человеческий фактор, а именно неаккуратность при сканировании листа бумаги, т.е. если лист в сканере располагался под некоторым уклоном. В таких случаях применяются алгоритмы предобработки исходного изображения, направленные на улучшения качества изображения, которые включают как этапы выравнивания строк, так и фильтрацию от шумов, повышение резкости и контрастности.
На этапе выделения отдельных символов текста могут быть получены некоторые неточности. Это является следствием сканирования изображения в низком качестве, которое приводит к объединению соседних символов или наоборот разделению одного символа на несколько составляющих. В данном случае используются алгоритмы нечеткого разделения слов на буквы, которые заключаются в рассмотрении нескольких возможных вариантов разделения и принятии окончательного решения на последнем этапе обработки.
Заключительным этапом является классификация всех символов, полученных на этапе сегментации, с последующим объединением полученных результатов в слова определенного словаря, а в более сложных ситуациях — в целые словосочетания.
Описанные этапы являются лишь базовой составляющей при распознавании сплошных текстов. Сами же алгоритмы вертикальной и горизонтальной сегментации, выравнивания строк, фильтрации и классификации могут быть совершенно различными. Отметим, что при динамическом распознавании рукописных текстов так же используются рассмотренные базовые пункты, но алгоритмы достижения поставленных целей отличаются коренным образом. Например, для выделения строки нет необходимости требовать «строго» горизонтального расположения строк, если учитывать, что все буквы записываются в строгой последовательности, а последовательность записи известна.
Рассмотренный тип текста наиболее простой в практическом использовании и, соответственно, для распознавания. Но очень часто в практике требуется работать с текстами с более сложными структурами, для распознавания которых, конечно же, не достаточно рассмотренных этапов обработки.
С усложнением структуры представления информации на листе усложняются методы извлечения соответствующей информации [21]. К наиболее распространенным сложным объектам относятся такие структурные единицы, как таблицы, диаграммы, рисунки. Рассмотрим основные этапы обработки изображений при распознавании текстов с прямоугольными таблицами.
Так как таблицы внутри себя могут содержать печатный текст, то процесс их распознавания содержит все этапы распознавания сплошных текстов. Но к ранее рассмотренным методам извлечения информационных признаков добавляются новые, а именно, методы анализа табличной структуры. Рассмотрим два основных метода поиска таблиц в исходном изображении: метод белых прямоугольников и метод горизонталей и вертикалей.
Основу первого метода составляет поиск максимальных прямоугольников, внутри которых не содержится закрашенных пикселей. Под максимальными подразумеваются такие прямоугольники, все стороны которых касаются компонент текста, т.е. закрашенных частей растра. На основании всех найденных белых промежутков между компонентами текста делается вывод о структуре имеющейся таблицы. Таким образом, вся задача приводится к задаче нахождения максимальных белых прямоугольников, алгоритм решения которой рассматривается в работе [18]. Перед применением данного метода считается, что расстояния между колонками и строками таблицы всегда больше расстояний между строками обычного текста и между соседними словами. Если же это условие не выполнено, то для более точного выделения структуры таблицы требуются дополнительные исследования, а в некоторых случаях задача становится неразрешимой без вмешательства человека (ручной сегментации).
В основе метода горизонталей и вертикалей лежит метод поиска прямых линий в исходном изображении и соединение этих линий в прямоугольники, ограничивающие элементы таблицы. Задача поиска вертикальных и горизонтальных линий может решаться разными способами, среди которых наиболее распространенными являются метод поиска компонент связности, образующих прямые линии [19] и метод скелетизации исходного изображения с последующим нахождением точек пересечения и линий их соединяющих [20].
Отметим, что при динамическом распознавании анализ структуры таблицы не является сложной задачей, так как в этом случае линии, ограничивающие таблицу, представлены набором точек на плоскости, одна из координат которых является постоянной величиной (или изменяется незначительно).
Обзор систем распознавания текстов
Одно из основных отличий в методике распознавания математических формул от методов распознавания обычных текстов прослеживается на этапе сборки набора отдельных символов в целые смыслообразующие выражения [62], [63]. Если для обычных текстов всегда соблюдается правило записи слева на право (или в некоторых случаях справа налево, например, в арабских текстах) и все символы находятся строго на одной линии, то для математических формул такого сказать нельзя. Для их записи используются правила, требующие соблюдения некоторой иерархии частей. Таким образом, символы не располагаются на одной прямой линии, а распределяются на плоскости согласно принятой иерархии каждого конкретного класса формул [67]. Так, например, при записи формул с дробями одни символы находятся строго над другими, при записи степеней, одни символы находятся правее и выше других, при записи нижних индексов эти индексы всегда располагаются правее и чуть ниже предыдущего символа и т.д. Это лишь малая часть того, как могут быть расположены компоненты формулы друг относительно друга. Еще более сложную структуру имеют интегралы, системы и матрицы.
Дополнительную сложность при анализе структуры расположения частей формулы друг относительно друга составляет тот факт, что для этого не достаточно анализировать взаимное расположение только отдельных символов. Рассмотрим небольшой пример. Пусть имеется рукописная запись формулы с двойным возведением в степень: у = xz . В данном случае не сложно определить, что z находится правее и выше, чем х, а 2 — правее и выше, чем z, поэтому не составляет большого труда восстановление полной картины взаимного расположения частей формулы.
Рассмотрим более сложную формулу с точки зрения структуры расположения символов: ж2. В данном примере практически невозможно определить характер взаимного расположения отдельных частей без учета смыслового содержания формулы из-за некоторой возникшей неопределенности. Так однозначно нельзя сказать, что дробь находится правее и выше чем х, или -расположен над степенной формулой х2. Если же учесть, что в данном случае выражение - не имеет никакого смыслового значения и составлено неправиль но, то правильную последовательность разбиения получить все-таки удается. В качестве еще более сложного примера можно рассмотреть следующую х и_ формулу: (j)vv
В этом случае сложность не только в определении взаимного расположения дробей находящихся в степени и их отношения к основной части, но и в определении того, к чему относятся скобки, хотя и на первый взгляд все довольно просто. Сложность в том, что разные классы символов могут взаимодействовать с другими классами совершенно по-разному. Исходя их этого, можно сделать некоторые предварительные выводы, а именно о том, что при анализе взаимного расположения отдельных компонент формулы нужно предусмотреть выполнение нескольких важных правил: 1. Необходимо учитывать расположение не только отдельных символов, но и взаимное расположение целых фрагментов к отдельным символам, а также взаимное расположение двух фрагментов. 2. При возможности учитывать семантическую составляющую распознаваемой формулы. 3. Учитывать возможные варианты распознавания отдельных символов для выявления неправильных связей с точки зрения соблюдения правил построения математических формул.
Для соблюдения перечисленных правил будем рассматривать такое математическое понятие, как граф изображения формулы [58]. Ее преимуществом над графами в обычном понимании является то, что они являются двухуровневыми. Это означает, что ее вершинами так же являются графы, которые называются графами второго уровня, тогда как сам граф считается графом первого уровня. Такая структура данных позволяет анализировать как отдельные символы, так и всю формулу целиком. Но главным назначением такой структуры является то, что она предоставляет хороший механизм для совместного распознавания символов и всей формулы с возможностью мониторинга динамического изменения входящих в формулы математических символов. Это позволяет рассматривать все варианты распознавания в тех случаях, когда в результате получены некоторые неопределенности, появление которых обусловлено теми или иными факторами. Еще не менее важным достоинством графа изображения формулы является то, что графы обеих уровней являются двумерно ориентированными. Это означает, что каждое ребро задается номерами вершин, которые оно соединяет, и набором векторов направлений на плоскости, которые описывают взаимное расположение двух вершин. Такой способ задания ребер позволяет описывать структуру как отдельных символов, так и взаимосвязи между различными символами. Таким образом, рассматриваемый объект является моделью исходного изображения формулы.
Рассмотрим основные понятия, связанные с графом изображения формулы. Определение. Граф F = (S,U) назовем двухуровневым, если множеством его вершин S является множество графов Lt = [X Vi) Є S, і = 1,2,3, При этом F будем считать графом первого уровня, а его вершины — графами второго уровня.
Определение. Граф F = (S,U) назовем двумерно ориентированным, если для каждого ребра щ Є U задана последовательность векторов Vt = {vij\vij = (xi,j] Vi,j) D С M2, J = 1, 2,..., щ п Є N+}. При этом число п назовем коэффициентом сегментации ребра, а множество D — базой ориентации. Если п = 1, то ребро называется несегментированным. Такие ребра обозначаются указанием вершин графа, которые они соединяют, и в скобках указывается последовательность векторов: ху( Ху;1}11=1). Пара, обозначающая вершины графа, является упорядоченной, так как граф ориентированный (ху ф ух). Если не требуется указывать направление, то ребро обозначается только указанием вершин. Если не требуется указания вершин, то ребро может обозначаться одной буквой.
Уточнение с помощью регулярных выражений
Данная теорема непосредственно может быть использована при решении задачи нахождения пересечения множеств, заданных регулярными выражениями, для этого достаточно в качестве ( bi С) взять наше регулярное выражение S, а в качестве Л любой из шаблонов математических формул А;ь. Использование этой теоремы избавляет от необходимости перебора всех вариантов и позволяет на каждом шаге быстро исключать те варианты, которые заведомо не могут быть взяты в качестве верно распознанных. В конечном итоге в исходном множестве останутся только те элементы, которые имеют совпадения с шаблонами. Среди этих элементов уже нужно будет выбрать один наиболее подходящий. В идеальном случае остается только один элемент, который и является решением исходной задачи распознавания математических формул. Учитывая то, что в результате применения данной теоремы будет исключено большая часть лишних элементов, то дальнейший выбор правильного варианта при наличии более одного элемента может быть произведен любым подходящим методом.
Запишем исходную необработанную строку в виде следующего выражения: S = ((рі,і,сід) ... \(pi,tl, chtl)j ... [(рп,і,спЛ)\ ... \(Pn,tn,cn,tn)j, которая получается заменой всех atj на пару (pij,Cij). Добавленный параметр p,tj является числом и равен вероятности того, что г-й символ строки должен быть распознан как символ QJ. Вероятность вычисляется как степень сходства исследуемого компонента рукописного ввода с некоторым эталоном. Очевидно, U что Yl pi j = 1, для всех г = 1, 2,..., п, т.е. при расчете вероятностей учиты ваются сразу все символы, у которых степень сходства текущего элемента с эталонами не нулевая. Назовем параметр pij весом элемента QJ.
Для расчета вероятностей всех порождаемых исходным регулярным выражением строк, необходимо перемножить соответствующие веса элементов, из которых строится результирующая строка. Таким образом, очевидно, что наиболее правильным результатом распознавания должна служить та строка, для которой итоговая вероятность (или вес строки) является максимальной. Но выбор наиболее вероятного исхода таким методом является неэффективным, если учитывать, что некоторым числовым весом так же обладают и сами математические конструкции. Например, конструкция sin х имеет некоторое предпочтение над конструкцией Ъгпх. Для решения этой проблемы рассмотрим метод совмещения технологии уточнения регулярными выражениями и метода вычисления вероятностей.
Рассмотрим такие понятия, как взвешенные регулярные множества [60]. Данные множества отличаются от регулярных множеств в обычном понимании тем, что каждый элемент множества является парой из строкового значения и некоторого числового веса, выражающего предпочтение одних элементов над другими. Наряду с взвешенными регулярными множествами рассматриваются и взвешенные регулярные выражения, порождающие их. Для уточнения с помощью взвешенных регулярных выражений достаточно применить теорему о пересечении множеств, заданных регулярными выражениями, к взвешенным регулярным множествах. Несмотря на значительное отличие структуры обычных и взвешенных регулярных выражений, сама теорема остается полностью такой же. Единственным отличием служит то, что каждое обозначение является взвешенным регулярным выражением, которое построено с использованием взвешенных регулярных операций объединения, конкатенации и итерации. Взвешенные операции отличаются от обычных тем, что при их использовании требуется пересчитывать веса согласно следующим условиям:
Основным отличием применения доказанных выше теорем для взвешенных регулярных выражений является отличие деления обычного множества от деления взвешенного множества слева. Деление взвешенного множества слева определяется следующим образом:
Эксперименты с разными почерками
Так как способ записи обычного текста полностью отличается от способа записи математических формул, то наиболее важным критерием при сегментации изображения должна послужить геометрическая форма отдельных символов. Обычный текст был распечатан при помощи принтера либо печатной машинки, в результате чего все символы условно имеют одинаковый размер, а символы одного и того же класса полностью идентичны. Сходство отдельных символов рукописных формул практически не может быть достигнуто, так как человек не обладает машинной точностью.
Рассмотрим основные признаки, по которым так или иначе можно производить сегментацию исходного изображения. К ним относятся:
Интервалы. В печатных текстах интервалы между словами, символами и строками постоянны. В рукописных математических формулах интервалы могут сильно отличаться друг т друга.
Форма отдельных символов. Печатные символы характеризуются наличием точек пересечения кривых под прямым углом, изгибов кривых под прямым углом, постоянной толщиной линий, в некоторых случаях наличием засечек. Все перечисленные характеристики отсутствуют в рукописных текстах, соответственно не относятся к математическим формулам.
Четкость выделения строк в тексте. В обычном тексте в большинстве случаев текст располагается строго построчно, длины строк примерно одинаковые, высота строк одинаковая и равна размеру шрифта. В математических формулах символы располагаются не последовательно, а согласно некоторой иерархии, определяемой классом формулы.
Наличие основной линии. В каждой горизонтальной проекции обычного текста четко определяются две основные линии, т.е. линии, имеющие наибольшие длины. В математических формулах число таких линий обычно равно числу уровней, при этом не всегда удается точно определить основную линию каждого уровня.
Наличие заглавных букв. Предложения в обычном тексте начинаются с большой буквы и заканчиваются точкой, т.е. размер первого символа больше, чем последующих.
Наличие спецсимволов. В обычных текстах редко используются некоторые знаки, например математические операции, поэтому для уточнения схемы сегментации можно выполнить предварительное распознавание отдельных символов с целью выявления среди них математических конструкций.
Язык текста. Если задача заключается в распознавании русского текста, то при первоначальном распознавании можно выполнить поиск символов на кириллице. Так как в формулах чаще всего используются латинские символы, то логично предположить, что символы кириллицы будут содержаться в фрагментах обычного текста.
Достаточно широкий набор рассматриваемых признаков позволяет использовать автоматические методы выделения математических формул в исходном изображении текста. После отделения фрагменты обычного печатного текста могут быть обработаны в любой системе распознавания печатных текстов, например в ранее упоминавшейся Abbyy FineReader. Учитывая то, что статическое распознавание печатных текстов выполняется уже на достаточно высоком уровне в отличие от статического распознавания рукописных текстов, в дальнейшем большую часть внимания будем уделять именно к рукописным формулам, вписанным в печатный текст.
Математические формулы рассматриваются не как готовые смыслообразу-ющие математические выражения, а как любая конструкция, которая может частью целого. Такой подход исключает необходимость строгого описания классов формул, и позволяет рассматривать любые конструкции, полученные в результате соединения нескольких фрагментов в один либо при разделении исходной формулы на несколько частей.
Приводится формальное описание задачи распознавания математических формул, в котором основной упор делается на совместное распознавание отдельных символов и целых формул. Описание сводится к тому, что наибольшей точности распознавания можно добиться, только учитывая особенности строения всей формулы при распознавании отдельных символов, а также учитывая все варианты распознавания отдельных символов при анализе структуры всей формулы.
Для решения поставленной задачи рассматриваются как стандартные методы решения отдельных подзадач, используемые при решении множества других задач распознавания, так и новые методы, ранее не применяемые при решении подобных задач. Стандартными методами решаются такие задачи, как нахождение скелета изображения, выделение строк и символов при помощи горизонтального и вертикального проектирования, построение графа символа при помощи анализа критических точек и соединяющих их кривых. К новым методам относятся главным образом уточнение с помощью регулярных выражений и моделирование изображений формул. Первый позволяет проверять полученные результаты на соответствие некоторым шаблонам формул, одновременно исключая необходимость перебора всех возможных вариантов распознавания. Второй позволяет строить дерево строки, содержащее всю необходимую информацию о структуре содержащейся формулы, что дает возможность сопоставления результата со структурами всех известных классов формул. Возможность рекурсивного описания новых классов формул исключает необходимость создания слишком большой базы эталонов.
