Алгоритм распознавания формул

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

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

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

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

В этой области работают коммерческие приложения, но они обладают значительными недостатками. Эти приложения либо не работают с формулами, обладающими сложной структурой, либо работают с изображениями высокого разрешения (~400 dpi). Большинство научной литературы отсканировано в худшем качестве, а формулы, использующиеся в ней, обладают сложной структурой. Под сложной структурой подразумевается наличие дробей, степеней, интегралов, вложенных друг в друга. Поэтому, проведение исследований в этой области актуально.

Общий алгоритм распознавания формул состоит из следующих этапов:

1. Определить области расположения отдельных символов (сегментация).
2. Распознать отдельные символы.
3. Построить структуру формулы.

Для реализации первого этапа была использована библиотека OpenCV без оригинальных доработок.

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

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

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

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

 

 

 

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

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

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

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

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

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

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

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

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

[1] Chao K, Mandyam D. Invariant character recognition with Zernike and orthogonal Fourier-Mellin moments. // Pattern recognition. No. 35, 2002. Pp 143-154.
[2] Josef B. Baker, Alan P. Sexton and Volker Sorge. A Linear Grammar Approach to Mathematical Formula Recognition from PDF // Intelligent Computer Mathematics: 16th Symposium, Calculemus, 2009. Pp. 320 – 344.
[3] Eto Y., Suzuki M. Mathematical formula recognition using virtual link network // Document Analysis and Recognition. Proceedings. Sixth International Conference, Seattle, 2001. Pp. 762 – 767.
[4] Шапиро Л. и Стокман Дж. Компьютерное зрение / Пер. с англ. – М.: БИНОМ. Лаборатория знаний, 2006. – 752 с.
[5] Заенцев И.В. Нейронные сети: основные модели. – Воронеж: Воронежский Государственный университет, 1999 – 74 с.

We propose recognition algorithm for scanned formulas. The task of formula recognition consists from character recognition and formula structure recognition. For character recognition the algorithm uses artificial neuron network with two hidden layers and image Zernike moments as network inputs. Choosing such features allows recognizing rotated characters and determining their angle of rotation. For formula structure recognition we propose method based on character location. The method allows recognition of fractions, integrals and sums with limits, exponentiation, indexes and expressions in brackets. The algorithm was tested on printed formulas and formulas scanned from scientific literature with low resolution. The test results for real scientific literature formulas shows 70 percent accuracy for structure recognition and 50 percent accuracy for formula recognition.