Распознавание рукописных математических выражений

    Здравствуй, Хабр!

    В этой статье я хочу поделиться опытом распознавания рукописных математических выражений. Хотя уже и существуют такие средства распознавания рукописных формул как «Панель математического ввода» mip.exe в Windows7, разнообразие подходов к решению данной проблемы не может не впечатлять. Об одном из таких подходов я и собираюсь рассказать.





    Небольшое введение


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

    В он-лайн распознавании рукописного математического выражения обычно выделяют следующие стадии:
    1. Сбор и предварительная обработка данных:
    2. Разделение выражения на символы (сегментация выражения):
    3. Рапознавание отдельных символов:
    4. Распознавание структуры математического выражения:

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

    Сбор и предварительная обработка данных


    Первым шагом является сбор и предварительная обработка данных. Обучающее множество для конкретного класса символов состоит из множества символов. Символ является упорядоченным набором росчерков, а росчерк является упорядоченным набором пар (x,y), где первая пара соответствует точке касания пера, а последняя — точке отрыва. Каждый символ рисуется определенным количеством росчерков в определенном порядке.

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

    Масштабирование, сдвиг и изменение количества опорных точек
    Каждая точка каждого росчерка сдвигается так, что начальная точка является верхним левым углом ограничивающей рамки символа. После этого все точки масштабируются с сохранением отношения ширины к высоте так, что символ помещается внутри квадрата. Далее, набор точек каждого росчерка изменяется так, чтобы точки располагались равноудаленно (передискретизация по длине дуги методом линейной интерполяции). Количество точек фиксировано и равно 36/N, где N – количество росчерков в символе (36 делится на 1, 2, 3 и 4, где 4 — максимальное количество росчерков в одном символе).
    В завершение, координаты точек собираются в единый вектор из 72 элементов, где первые 36 элементов представляют координаты по x, а последние — координаты по y.



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

    На самом деле, размерность вектора можно уменьшить в несколько раз, при этом не потеряв практически никакой информации. Алгоритм этот назвается «Метод главных компонент».

    В итоге было создано следующее нечто для обучения классификатора:



    Сегментация и распознавание отдельных символов


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

    Предположим, что введенные росчерки упорядочены по времени, то есть при вводе символа, состоящего из трех росчерков, последовательно вводятся росчерки данного символа. Например, не допускается ставить точку над символом i после написания символов, которые следуют после i. С учетом данного предположения, для определения символов, состоящих из нескольких росчерков, необходимо последовательно рассматривать группы росчерков, размером от 1 до N (N в нашем случае равно 4). Если символ из нескольких росчерков распознается классификатором с ошибкой, меньшей определенного порога, то отдается предпочтение данному символу. При этом количество рассматриваемых комбинаций равняется F(N)=O(kN). В случае, если ни один из результатов классификации не превосходит порогового значения, пороговое значение увеличивается и шаг повторяется, либо возникает ошибка распознавания.

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

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



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

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

    Теперь, наконец, перейдем к распознаванию структуры выражения :-)

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


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



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

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



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



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



    Доминирование символов и доминирующая базовая линия
    Доминирование определяется следующим образом: символ s доминирует над символом a, если a лежит в области s, а s не лежит в области a. Однако, оба символа могут лежать в областях друг друга. В итоге, вычисление функции dominates(s,a) производится следующим образом (каждый последующий шаг выполняется, если на предыдущем не удалось определить, какой символ доминирует над каким):
    1. Проверка геометрического расположения символов.
    2. Проверка класса символа. Например, символ дроби будет доминировать над символом цифры.
    3. Проверка относительных размеров символа

    Если имеется упорядоченный список символов L, то можно определить крайний левый доминирующий символ в списке путем выполнения следующей рекурсивной процедуры:
    getDominantSymbol(L):
    1. Пусть n = length(L) — количество символов в списке.
    2. Если n==1, вернуть s(n)
    3. Если s(n) доминирует над s(n-1) , удалить s(n-1) из L, иначе удалить s(n)
    4. Вернуть getDominantSymbol(L).

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

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

    Тогда дерево базовых линий этого выражения будет иметь следующий вид:


    Доминирующую базовую линию Db конструируем с помощью следующей функции:
    constructDominantBaseline(Db,L):
    1. Если Db пусто, то Db = addSymbol(Db,getDomninantSymbol(L))
    2. s = getLastSymbol(Db)
    3. Создать список Hs = getRightNeighbors(s,L) символов из L, которые являются правыми горизонтальными соседями символа s
    4. Если Hs пуст, выйти
    5. Найти доминирующий символ среди символов из Hs, sd = getDominantSymbol(Hs)
    6. Db = addSymbol(Db,sd)
    7. Рекурсия: constructDominantBaseline(Db,L)


    Дерево базовых линий создается рекурсивным нахождением доминирующих базовых линий в выражении, описанном упорядоченным списком символов L.
    ConstructBaselineTree(L):
    1. Если L пуст, выход
    2. Инициализация Db
    3. constructDominantBaseline(Db,L)
    4. Обновить Db, сгруппировав символы, определяющие имена функций и операторов
    5. Для каждого символа s из Db создать новые списки символов с потомками, в зависимости от того, каким пространственным отношениям они удовлетворяют, и создать ссылки на эти списки
    6. L = Db
    7. Для каждого символа использовать рекурсию, применяя процедуру constructBaselineTree к каждому из списков-потомков, полученных на шаге 5


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

    Что из этого всего получилось


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


    И может распознавать, хоть иногда и не без ошибок, вот такие формулы (а кто первый найдет ошибку распознавания символа — тот молодец :-)



    Эпилог


    Вот и закончилась моя первая статья на Хабре. Надеюсь, она не была очень занудной, и будет кому-то полезной! Благодарю за внимание!

    Литература:
    1. Nicholas Matsakis. Recognition of handwritten mathematical expressions. Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA, May 1999.
    2. Ernesto Tapia: Understanding Mathematics: A System for the Recognition of On-Line Handwritten Mathematical Expressions, Berlin, 2004
    3. Eva Gallardo Perez: 2D Grammar Extension of the CMP Mathematical Formulae On-line Recognition System, Research Reports of CMP, Czech Technical University in Prague, No. 3, 2009
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 77
    • +3
      Сразу вспомнил ТБВ.
      • +5
        Спасибо, это было очень интересно узнать.
        • +2
          Спасибо, было интересно узнать, что вам было интересно это узнать.
      • +17
        Вот и закончилась моя первая статья на Хабре. Надеюсь, она не была очень занудной

        Не была! Спасибо за интересный материал!
        • +1
          Интересно!

          Только надо было картинку вставить из «операции Ы»:

          www.youtube.com/watch?v=Gd3B_93FAJY&t=1956

          :)
          • +26
            Нажал на вашу ссылку и пол фильма посмотрел. Как-то затянуло…
            • +2
              да, вы правы, затягивает.
            • 0
              В той серии ТБВ, насколько я помню, они именно распознаватель формул делали и на скрине изображен процесс тестирования.
              • 0
                Если точно, то их система должна была решать сложные диффуры.
                • 0
                  Не столько именно решать, находить соответствие с табличными, уже известными дифурами.
                  • 0
                    Ну я примитивно выразился. Находить решения она должна была не для табличных, а специфических, часто используемых в теорфизе. Например, уравнение Шрёдингера.
                    • 0
                      Какое конкретно уравнение Шрёдингера? Для разных систем это разные классы уравнений.

                      И решают конкретный класс уравнений, а не «общее уравнение Шрёдингера».
                      • 0
                        Какое конкретно уравнение Шрёдингера?
                        Извините, но в сериале об этом ни слова.
                        • +2
                          Вы что, оставили комментарий основываясь на сериал?

                          Там же были практически все виды уравнений — от Бесселя (сферических и цилиндрических) и Ганкеля до уравнений разрешимых в элементарных функциях.
                          • 0
                            Вы что, оставили комментарий основываясь на сериал?
                            Так и разговор как раз о том, для чего делалось приложение в сериале.
                  • 0
                    А если быть точнее, то распознавать и решать?
                    • +1
                      А если совсем точно, то даже не решать, а подставлять значения в уже известное решение :)
              • 0
                Школьники, наверное, давно мечтали о такой программе!
                Будущее уже сегодня :-)
                • 0
                  Спасибо за статью, познавательно.

                  У вас 1 хорошо распознается. Почему-то в егэ заставляют писать 1 как l. Я думал, чтобы не компьютер не спутал с 7кой?
                  Интересно какой алгоритм распознавания используется в егэ.
                  • 0
                    1 путает с 9кой иногда, но очень редко, а с семеркой не путает, потому что обучен тому, что семерка состоит из двух росчерков — с палочкой посередине.
                    • +2
                      Кстати, в Японии и Корее принято писать 7 без второй перечеркивающей черточки, как в печатных шрифтах. И наши ребята часто ошибаются и при чтении — путают с единицей, — и при написании — заграничные друзья и их компьютеризированные распознавалки не понимают, что это за плюсик с хвостом.
                      Может, еще где-то принято такое написание, но мне об этом не известно.
                      • –1
                        Лол, а как же 七?
                        • –1
                          あまり使えません
                          • –1
                            でも、時々に使っています。とにかく、伝統の書き方は重要です。どう思いますか、ワイルさん?
                    • 0
                      как раз в примере спутал.
                    • +6
                      Ошибка тут: {9} over {x}. Должно быть {1} over {x}. Спасибо за статью :)
                    • 0
                      и что дальше намерены с софтом делать?
                      • +8
                        Диплом защищать :-) Это же тестовое, учебное приложение. Конкурент mip.exe из него не получится. Если перечислять, что еще должно быть сделано кроме рефакторинга кода, получится примерно такой список:
                        1. написать более совершенный классификатор (использующий SVM)
                        2. научить распознавать разные стили письма
                        3. реализовать более совершенный алгоритм сегментации
                        4. воспринимать xml-подобный формат электронных чернил для возможности загрузки сторонних баз
                        5. научить распознавать матрицы
                        6. спроектировать годный интерфейс
                        и так далее.
                        • +3
                          А исходники открывать не планируется?
                          • +5
                            Предполагаю, что если я их открою, большое количество программистов умрёт от разрыва сердца. Хотя, если доведу до ума в течение года-двух, то почему бы и нет :-)
                            • +21
                              Убей конкурентов, открой исходный код!
                              • +4
                                Очень жалко. А то обычно, желая довести до ума, через месяцок — другой забивают и вообще не выкладывают…

                                Судя по скриншотам — запущено под Linux, что вдвойне заинтересовало. Есть — ли под Linux аналоги?

                                Мне, в общем-то, нафиг не нужно, но побаловаться интересно было-бы.

                                А на чем пишите, кстати?
                              • +1
                                Мне кажется, проект очень даже стоящий. Под linux вообще мало средств для распознавания рукописного текста… Думаю, желающие помочь с кодом найдутся.
                            • +1
                              ИМХО, при полной проработке тянет на кандидатскую
                              • –1
                                Эээ… а что именно тянет-то?
                                Разве автор предложил что-то новое?
                                Распознавание символов — нейронной сетью. Сегментация — по ретроспективе росчерков, а значит не годится для распознавания изображений (что, кстати, кардинально отличет даный проект от ТБВ). То, что индекс стоит выше символа — как бы и так понятно. А больше ничего и нет…
                                • +3
                                  Новизна не всегда означает, что автор взял и создал из ничего новый метод. Большинство работ — это применение уже существующих методов и алгоритмов в новой области. Конечно, что-то новое в работе безусловно должно быть, но как правило новая идея — это хорошо забытая старая. Вот у меня в работе, например, куча новых алгоритмов, хотя если приглядеться, то подобные алгоритмы уже где-то кем-то когда-то были использованы.
                          • +2
                            следующий этап портируйте на andoid и iphone)
                            • +14
                              чтобы заработать на подводную лодку…
                              • +2
                                так и представляю учеников и студентов, фотографирующих задания на контрольных и экзаменах =)
                                • +1
                                  Это вы еще на ЕГЭ не были.
                                  • +1
                                    а что там на ЕГЭ, расскажите по подробнее
                                    • 0
                                      Откуда-то ведь в интернете появляются слитые варианты с Дальнего Востока :)
                                      Так что, вполне ухитряются.
                                      • –1
                                        В этом году один вариант появился за день до экзамена. Фоткают все, кому не страшно и не лень, и выкладывают тут же в интернет с просьбами решить. Дальневосточные регионы выкладывают задания, чтобы западные успели ознакомиться с ними.
                                        • 0
                                          На дольнем востоке минимальный процент сдавших?
                                          • 0
                                            *дальнем
                                            • +1
                                              Слишком велик шанс получить на своем ЕГЭ вариант, отличный от дальневосточного. Разве что типы заданий оценить. Преимущество не очень большое в итоге.
                                              • –1
                                                Для этого и фоткают. А еще чтобы решили.
                                                • 0
                                                  Да ладно :) Некоторые в том году делали очень просто — в 4 утра в день ЕГЭ скачивали варианты с Дальнего Востока, шли к репетитору, с ним быстро прорешивали и шли на экзамен уже очень неплохо подготовленные, т.к. между вариантами почти всегда разница только в числах.
                                                  • 0
                                                    Так а я о чем?)
                                                    Разница в числах только в регионе, а между регионами задания немного разные.
                                                    • 0
                                                      Не туда ответил, хотел на уровень повыше =)
                                                      В том году особой разницы не заметил. Ну или она критична разве что для совсем несоображающих «абитуриентов»
                                                      • 0
                                                        Да нет, я имел возможность сравнить. Типы заданий были похожи.
                                        • 0
                                          На ЕГЭ задания фоткают только если организаторы, у детей эту возможность исключил на 99%!
                                          • 0
                                            Очень странное заявление, учитывая что только сегодня я смотрел пару фоток КИМов в плохом качестве, выложенных экзаменуемыми. Все зависит от организаторов, а среди них есть и не совсем бдительные.
                                            • 0
                                              Ну если только сами организаторы косячат…
                                              Вот сами посмотрите:
                                              1- пришли на пункт сдачи телефоны сдали,
                                              2- (не сдали и ладно) в аудитории сидит 2 наблюдателя + ходят независимые проверяющие,
                                              3-выносить ни работу ни черновики «в туалет» нельзя,
                                              4-если и каким то чудом все ответственные куда то делись\отвлеклись и ты сфотографировал то у твоих оставшихся 14 «товарищей по несчастью» есть право подать жалобу с последующими последствиями для тебя (есть такие справедливые)
                                              Я все таки имею непосредственное отношение к проведению ЕГЭ 11…
                                              • +2
                                                > 1- пришли на пункт сдачи телефоны сдали,
                                                У нас никто не сдавал. Да и не просили.

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

                                                > 3-выносить ни работу ни черновики «в туалет» нельзя,
                                                Зато можно взять с собой из дома чистый листок и его вынести.

                                                > 4-если и каким то чудом все ответственные куда то делись\отвлеклись…
                                                Все заняты решением. А кто не занят, тот тоже списывает. Хотя от места еще зависит.
                                                • +2
                                                  Мне друг позвонил во время ЕГЭ из туалета и продиктовал задачу. Через 20 минут перезвонил и получил ответ.
                                                  • +1
                                                    ходят независимые проверяющие

                                                    Эти независимые проверяющие при должной сноровке местных преподов и наличии коньяка становятся очень лояльными.
                                                  • 0
                                                    Знаю много случаев, когда «всем пофиг» было — и наблюдателям, которые почти не следили или смотрели сквозь пальцы, и уж тем более другим экзаменуемым. У самого при сдаче в прошлом году была возможность почти не напрягаясь сфотографировать варианты, отослать кому-нибудь и потом скатать решения, но лень было заморачиваться.
                                                    • 0
                                                      Ну это как всегда в России идея хорошая, а реализация и халатность портит все начинания.
                                                      • 0
                                                        Да и идея то по сути хорошая только при сильном ее обобщении, т.е. она хороша где-то на уровне «надо оценивать способности более объективно»
                                                        • +2
                                                          Это ЕГЭ то идея хорошая? =))) Все эти «запреты на списывание» и «бдительность» — бред полнейший.
                                                          Я программирую и верстаю профессионально уже 3 года, но всё-равно регулярно лажу в шпаргалку, чтобы посмотреть какое-нибудь тег, функцию на php или метод из Js. Хотя я с ними работаю ежедневно.
                                                          У учителей не халатность, а понимание. Только мудаки могут реально ходить и издеваться над детьми, тщательно проверяя, не списывают ли они.
                                                      • 0
                                                        Вот тут статья про ЕГЭ от учителя: scepsis.ru/library/id_3023.html, тоже имеющего отношение к ЕГЭ.
                                                        Видно, что меры эти ни к чему не приводят.
                                                    • 0
                                                      Кто исключил?
                                                      • 0
                                                        на егэ не фоткают, а шепчут http://abiturient.pro/talk/discussion/2/ (11 в.)
                                                      • 0
                                                        Эта софтинка с фотками не работает.
                                                    • 0
                                                      Я ни черта не смыслю в программировании (надеюсь поправить в скором времени), но то, что Вы сделали — это круто.
                                                      • +1
                                                        Вы оценивали точность распознавания символов?
                                                        • 0
                                                          Нет, не оценивал. Основное внимание уделил стадии структурного анализа. Вообще, для хорошего распознавания с высокой точностью необходим более совершенный классификатор. К сожалению, не хватило времени его написать.
                                                          • +1
                                                            >> передискретизация по длине дуги методом линейной интерполяции

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

                                                            P.S. Надо заметить, что если по задумке автора сеть не будет переобучаться пользователем, то такой подход является выигрышным.
                                                        • 0
                                                          Глядя на иллюстрацию с обучением классификатора, вспомнил, как на работе бились над задачей различения оценок «Н» и «4» (при распознании информации из ведомостей успеваемости), которые преподаватели пишут так, что даже на глаз, зачастую, определить тяжело. Проблема решилась на 60% увеличением базы образцов для обучения и на 35% надписью «Пожалуйста, пишите аккуратней!». Но ошибки всё равно иногда бывают.
                                                          • 0
                                                            Хм… Вот бы нам это в виде онлайн сервиса скрестить с видеолекциями по математике…
                                                            lektorium.tv/subject/?id=2884

                                                            … ушёл думать…
                                                            • +1
                                                              Хорошо было бы записывать распознанные формулы в разных форматах — LaTeX, OpenOffice, Microsoft Equation…
                                                              Работа превосходная, тянет даже на несколько дипломов. Хотя бы бинарники покажете?
                                                              • +3
                                                                Мне кажется, что вы у корня про циферки забыли, т.е. бывают корни не только второй степени.
                                                                • +1
                                                                  Знаю, а еще и матрицы, например… Но целью было продемонстрировать рабочий подход, а не создать супер приложение, которое может все формулы на свете :-) Тут было мнение, что ничего нового нет — я с этим согласен. Повторюсь — цель — рассказать об одном из алгоритмов решения описанной проблемы.
                                                                  • +1
                                                                    <зануда>Просто примеры корней в статье есть (а матриц нет), а корни не доработаны.</зануда> :)
                                                                    Но статья, конечно же, отличная! Большое спасибо за неё! Добавил в закладки. Как раз надо будет курсач написать на тему распознавания рукописных символов.

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

                                                                Самое читаемое