NeoNN May 28 2011 at 18:11

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

7 min

23K

Algorithms*

+226

Comments 77

Greteon May 28 2011 at 18:13

Сразу вспомнил ТБВ.

AgentSmith May 28 2011 at 21:26

Спасибо, это было очень интересно узнать.

TheShock May 28 2011 at 21:59

Спасибо, было интересно узнать, что вам было интересно это узнать.

Tibr May 28 2011 at 18:36

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

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

0lympian May 28 2011 at 18:49

Интересно!

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

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

:)

cbone May 28 2011 at 19:44

Нажал на вашу ссылку и пол фильма посмотрел. Как-то затянуло…

laxmer May 28 2011 at 20:25

да, вы правы, затягивает.

TheShock May 28 2011 at 22:01

В той серии ТБВ, насколько я помню, они именно распознаватель формул делали и на скрине изображен процесс тестирования.

Tibr May 29 2011 at 00:50

Если точно, то их система должна была решать сложные диффуры.

darkfrei May 29 2011 at 01:18

Не столько именно решать, находить соответствие с табличными, уже известными дифурами.

Tibr May 29 2011 at 01:54

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

davinchi May 29 2011 at 17:13

Какое конкретно уравнение Шрёдингера? Для разных систем это разные классы уравнений.

И решают конкретный класс уравнений, а не «общее уравнение Шрёдингера».

Tibr May 29 2011 at 19:07

Какое конкретно уравнение Шрёдингера?

Извините, но в сериале об этом ни слова.

davinchi May 29 2011 at 19:37

Вы что, оставили комментарий основываясь на сериал?

Там же были практически все виды уравнений — от Бесселя (сферических и цилиндрических) и Ганкеля до уравнений разрешимых в элементарных функциях.

Tibr May 29 2011 at 19:40

Вы что, оставили комментарий основываясь на сериал?

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

TheShock May 29 2011 at 06:36

А если быть точнее, то распознавать и решать?

Tibr May 29 2011 at 12:25

А если совсем точно, то даже не решать, а подставлять значения в уже известное решение :)

perevedko May 28 2011 at 18:51

Школьники, наверное, давно мечтали о такой программе!
Будущее уже сегодня :-)

marseny May 28 2011 at 18:54

Спасибо за статью, познавательно.

У вас 1 хорошо распознается. Почему-то в егэ заставляют писать 1 как l. Я думал, чтобы не компьютер не спутал с 7кой?
Интересно какой алгоритм распознавания используется в егэ.

NeoNN May 28 2011 at 18:57

1 путает с 9кой иногда, но очень редко, а с семеркой не путает, потому что обучен тому, что семерка состоит из двух росчерков — с палочкой посередине.

w23 May 31 2011 at 16:52

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

Halt May 31 2011 at 19:11

Лол, а как же 七?

w23 May 31 2011 at 19:44

あまり使えません

Halt May 31 2011 at 22:10

でも、時々に使っています。とにかく、伝統の書き方は重要です。どう思いますか、ワイルさん？

iambot May 28 2011 at 19:08

как раз в примере спутал.

monkegoist May 28 2011 at 18:54

Ошибка тут: {9} over {x}. Должно быть {1} over {x}. Спасибо за статью :)

NeoNN May 28 2011 at 18:55

Правильно :-)

tzlom May 28 2011 at 18:59

и что дальше намерены с софтом делать?

NeoNN May 28 2011 at 19:06

Диплом защищать :-) Это же тестовое, учебное приложение. Конкурент mip.exe из него не получится. Если перечислять, что еще должно быть сделано кроме рефакторинга кода, получится примерно такой список:

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

и так далее.

seriyPS May 28 2011 at 19:19

А исходники открывать не планируется?

NeoNN May 28 2011 at 19:23

Предполагаю, что если я их открою, большое количество программистов умрёт от разрыва сердца. Хотя, если доведу до ума в течение года-двух, то почему бы и нет :-)

darkfrei May 28 2011 at 19:29

Убей конкурентов, открой исходный код!

seriyPS May 28 2011 at 20:28

Очень жалко. А то обычно, желая довести до ума, через месяцок — другой забивают и вообще не выкладывают…

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

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

А на чем пишите, кстати?

NeoNN May 28 2011 at 20:30

ninacarrot May 29 2011 at 09:51

Мне кажется, проект очень даже стоящий. Под linux вообще мало средств для распознавания рукописного текста… Думаю, желающие помочь с кодом найдутся.

orionll May 28 2011 at 22:32

ИМХО, при полной проработке тянет на кандидатскую

BigObfuscator May 29 2011 at 10:02

Эээ… а что именно тянет-то?
Разве автор предложил что-то новое?
Распознавание символов — нейронной сетью. Сегментация — по ретроспективе росчерков, а значит не годится для распознавания изображений (что, кстати, кардинально отличет даный проект от ТБВ). То, что индекс стоит выше символа — как бы и так понятно. А больше ничего и нет…

orionll May 29 2011 at 10:15

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

isergeymd May 28 2011 at 19:04

следующий этап портируйте на andoid и iphone)

Yakhnev May 28 2011 at 19:12

чтобы заработать на подводную лодку…

mr_smith May 28 2011 at 19:17

так и представляю учеников и студентов, фотографирующих задания на контрольных и экзаменах =)

zodiac May 28 2011 at 19:41

Это вы еще на ЕГЭ не были.

mr_smith May 28 2011 at 19:47

а что там на ЕГЭ, расскажите по подробнее

Roler May 28 2011 at 20:00

Откуда-то ведь в интернете появляются слитые варианты с Дальнего Востока :)
Так что, вполне ухитряются.

zodiac May 28 2011 at 20:00

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

darkfrei May 28 2011 at 20:18

На дольнем востоке минимальный процент сдавших?

darkfrei May 28 2011 at 20:19

*дальнем

greshilov May 28 2011 at 21:19

Слишком велик шанс получить на своем ЕГЭ вариант, отличный от дальневосточного. Разве что типы заданий оценить. Преимущество не очень большое в итоге.

zodiac May 28 2011 at 21:26

Для этого и фоткают. А еще чтобы решили.

WingedFlame May 28 2011 at 21:47

Да ладно :) Некоторые в том году делали очень просто — в 4 утра в день ЕГЭ скачивали варианты с Дальнего Востока, шли к репетитору, с ним быстро прорешивали и шли на экзамен уже очень неплохо подготовленные, т.к. между вариантами почти всегда разница только в числах.

zodiac May 28 2011 at 21:54

Так а я о чем?)
Разница в числах только в регионе, а между регионами задания немного разные.

WingedFlame May 28 2011 at 22:04

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

Roler May 28 2011 at 22:19

Да нет, я имел возможность сравнить. Типы заданий были похожи.

lex89 May 28 2011 at 21:20

На ЕГЭ задания фоткают только если организаторы, у детей эту возможность исключил на 99%!

greshilov May 28 2011 at 21:30

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

lex89 May 28 2011 at 21:37

Ну если только сами организаторы косячат…
Вот сами посмотрите:
1- пришли на пункт сдачи телефоны сдали,
2- (не сдали и ладно) в аудитории сидит 2 наблюдателя + ходят независимые проверяющие,
3-выносить ни работу ни черновики «в туалет» нельзя,
4-если и каким то чудом все ответственные куда то делись\отвлеклись и ты сфотографировал то у твоих оставшихся 14 «товарищей по несчастью» есть право подать жалобу с последующими последствиями для тебя (есть такие справедливые)
Я все таки имею непосредственное отношение к проведению ЕГЭ 11…

zodiac May 28 2011 at 21:48

> 1- пришли на пункт сдачи телефоны сдали,
У нас никто не сдавал. Да и не просили.

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

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

> 4-если и каким то чудом все ответственные куда то делись\отвлеклись…
Все заняты решением. А кто не занят, тот тоже списывает. Хотя от места еще зависит.

darkfrei May 28 2011 at 23:00

Мне друг позвонил во время ЕГЭ из туалета и продиктовал задачу. Через 20 минут перезвонил и получил ответ.

Sterhel May 29 2011 at 06:10

ходят независимые проверяющие

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

WingedFlame May 28 2011 at 21:51

Знаю много случаев, когда «всем пофиг» было — и наблюдателям, которые почти не следили или смотрели сквозь пальцы, и уж тем более другим экзаменуемым. У самого при сдаче в прошлом году была возможность почти не напрягаясь сфотографировать варианты, отослать кому-нибудь и потом скатать решения, но лень было заморачиваться.

lex89 May 28 2011 at 21:57

Ну это как всегда в России идея хорошая, а реализация и халатность портит все начинания.

WingedFlame May 28 2011 at 22:05

Да и идея то по сути хорошая только при сильном ее обобщении, т.е. она хороша где-то на уровне «надо оценивать способности более объективно»

TheShock May 28 2011 at 22:07

Это ЕГЭ то идея хорошая? =))) Все эти «запреты на списывание» и «бдительность» — бред полнейший.
Я программирую и верстаю профессионально уже 3 года, но всё-равно регулярно лажу в шпаргалку, чтобы посмотреть какое-нибудь тег, функцию на php или метод из Js. Хотя я с ними работаю ежедневно.
У учителей не халатность, а понимание. Только мудаки могут реально ходить и издеваться над детьми, тщательно проверяя, не списывают ли они.

dbf May 31 2011 at 09:29

Вот тут статья про ЕГЭ от учителя: scepsis.ru/library/id_3023.html, тоже имеющего отношение к ЕГЭ.
Видно, что меры эти ни к чему не приводят.

zodiac May 28 2011 at 21:32

Кто исключил?

lukaville May 29 2011 at 12:20

на егэ не фоткают, а шепчут http://abiturient.pro/talk/discussion/2/ (11 в.)

Nashev May 30 2011 at 19:36

Эта софтинка с фотками не работает.

Sterhel May 28 2011 at 19:37

Я ни черта не смыслю в программировании (надеюсь поправить в скором времени), но то, что Вы сделали — это круто.

Ganimede May 28 2011 at 20:03

Вы оценивали точность распознавания символов?

NeoNN May 28 2011 at 20:10

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

manakhovpavel May 29 2011 at 22:21

>> передискретизация по длине дуги методом линейной интерполяции

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

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

temochka May 28 2011 at 20:11

Глядя на иллюстрацию с обучением классификатора, вспомнил, как на работе бились над задачей различения оценок «Н» и «4» (при распознании информации из ведомостей успеваемости), которые преподаватели пишут так, что даже на глаз, зачастую, определить тяжело. Проблема решилась на 60% увеличением базы образцов для обучения и на 35% надписью «Пожалуйста, пишите аккуратней!». Но ошибки всё равно иногда бывают.

yasha_somov May 29 2011 at 02:42

Хм… Вот бы нам это в виде онлайн сервиса скрестить с видеолекциями по математике…
lektorium.tv/subject/?id=2884

… ушёл думать…

Oreolek May 29 2011 at 07:33

Хорошо было бы записывать распознанные формулы в разных форматах — LaTeX, OpenOffice, Microsoft Equation…
Работа превосходная, тянет даже на несколько дипломов. Хотя бы бинарники покажете?

Mansiper May 29 2011 at 13:19

Мне кажется, что вы у корня про циферки забыли, т.е. бывают корни не только второй степени.

NeoNN May 29 2011 at 17:00

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

Mansiper May 29 2011 at 17:33

<зануда>Просто примеры корней в статье есть (а матриц нет), а корни не доработаны.</зануда> :)
Но статья, конечно же, отличная! Большое спасибо за неё! Добавил в закладки. Как раз надо будет курсач написать на тему распознавания рукописных символов.