crypt of decay - про распознавание strokes (хуй знает, как это поточней перевести) [entries|archive|friends|userinfo]
ketmar

[ userinfo | ljr userinfo ]
[ archive | journal archive ]

про распознавание strokes (хуй знает, как это поточней перевести) [Sep. 26th, 2013|08:40 pm]
Previous Entry Add to Memories Tell A Friend Next Entry
как я уже когда-то писал, есть у меня библиотека для распознавания методом DTW. распознаёт, конечно, зверски, но и тормозит примерно так же. к тому же математика внутри (хорошо, что её самому писать не пришлось, а удалось красиво спиздить). и данных хранит дохуя. несомненный плюс — даже по одному образцу, как выше сказано, зверь-машина.

есть ещё распознавалка по методу Олега Доперчука: на основе dot product (как это будет на вашем… а! скалярное произведение, вроде бы). в принципе, распознаёт, но таки хочет, чтобы рисовали поточнее. со сложными фигурками типа буквы «пси» или пентаграммы у неё плоховато.

также игрался с $1 recognizer: неплох. правда, одиночные линии не умеет вовсе. даже на одном шаблоне распознаёт достаточно неплохо, но лучше ей нарисовать по нескольку шаблонов на stroke.

ну, и совсем недавно таки накарябал protractor. ему вместо 64 опорных точек вообще достаточно 16. также ему не надо укладывать stroke в квадратик, поэтому он теоретически способен понимать прямые линии (на практике, правда, он что горизонтальную, что вертикальную — обе считает одним и тем же). а ещё он не елозит туда-сюда по stroke, поэтому если ему скормить много-много шаблонов, то он будет значительно быстрее $1. и кода в нём поменьше.

правда, статью про то, как этот protractor толком работает, я не одолел, поэтому нихуя не понимаю, что у него получается на выхлопе. опытным путём установлено, что stroke более-менее сложной формы стоит принимать «на веру», если выхлоп больше четырёх. и вообще: чем больше, тем лучше попадание.

на практике protractor разрывает всех по совокупности параметров «количество байт на шаблон / скорость / точность». то есть, за счёт того, что для одного шаблона нужно всего 16*2*sizeof(float) и скорости можно хранить дохуя и ещё чуть-чуть шаблонов, что сильно повысит точность распознавания.

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

ах, да: $1 и protractor могут насрать на ориентацию stroke в пространстве (и по-умолчанию срут). лично я считаю это скорее недостатком. для DTW же придётся или понять математику, которая там внизу, потом охуеть и всё равно попытаться «покрутить» stroke руками, чтобы они более-менее одинаково были расположены. предыдущие два, кстати, тоже stroke крутят, но не очень навязчиво.

в общем, для большинства практических применений советую protractor. если будете брать код со страницы $1, то не забывайте, что для protractor'а совершенно не надо масштабировать накарябаное: ему плевать. а лучше почитайте псевдокод, который даёт автор статьи, и транслируйте его в любимый язык — в этом псевдокоде ещё и простой метод обрубить независимость от ориентации дан. нужны вам будут sqrt, sin, cos, atan2, просто atan, а также acos.
Linkmeow!

Comments:
[User Picture]
From:[info]polytheme
Date:September 26th, 2013 - 09:34 pm
(Link)
а что такое stroke ? я только знаю, что это инсульт
ты капчу ломаешь, или файнридер переплюнуть хочешь ?
[User Picture]
From:[info]ketmar
Date:September 26th, 2013 - 09:41 pm
(Link)
можешь читать как glyph.
[User Picture]
From:[info]polytheme
Date:September 26th, 2013 - 09:42 pm
(Link)
символ что ли, блядь !!!???
[User Picture]
From:[info]ketmar
Date:September 26th, 2013 - 09:44 pm
(Link)
слушай, тебе сложно набрать в гугле «$1 recognizer» и тыцнуть в первую ссылку?
[User Picture]
From:[info]polytheme
Date:September 27th, 2013 - 01:52 am
(Link)
а нахуя ? хочешь жесты в няшечку добавить ?
[User Picture]
From:[info]ketmar
Date:September 27th, 2013 - 04:51 am
(Link)
ну, если начинать издалека, то подобные распознавалки у меня больная тема ещё с начала двухтысячных. я тогда наткнулся на программку «sensiva» под винду, которой на сетке 32x32 рисовались глифы, а потом их можно было — зажав почку мыши — намалевать на экране, софтина распознавала — и что-то там делала. ну, то, что сейчас easystroke делает для никсов, только хуже, конечно. (кстати, алгоритм DTW упёрт именно из easystroke).

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

вот с тех пор я периодически смотрю на состояние дел в этой области и ностальгически мечтаю: «ах, мне бы в то время эти алгоритмы…»

ну и да: есть планы по привинчиванию на няшечку чего-то вроде easystroke, но попроще, на си и без буста. правда, тут проблема отсутствия хотя бы двух почек — как удобно начинать глиф, я не придумал. если «долго подержать палец/стилус на одном месте» — это раздражает, потому что глиф удобно использовать именно в режиме «хуяк-пиздык-поехали». а других методов особо и нет. думаю.
[User Picture]
From:[info]ketmar
Date:September 27th, 2013 - 04:51 am
(Link)
э… в смысле, sensiva хуже, чем easystroke, а не наоборот.
From:(Anonymous)
Date:September 27th, 2013 - 04:09 pm
(Link)
> поточней перевести)
секунд десять выставляла правильное ударение пытаясь постичь дзен, блеать.
From:[info]phantom
Date:September 28th, 2013 - 12:40 am
(Link)
А символы юникода может распознавать?
[User Picture]
From:[info]ketmar
Date:September 28th, 2013 - 06:47 am
(Link)
(удивлённо) какие stroke ей в память натолкаешь — такие и распознаёт. при чём тут «символы юникода»? это не распознавалка текста, а распознавалка жестов. в данном случае — «мышиных жестов» в 2d-пространстве.
From:[info]phantom
Date:September 28th, 2013 - 11:34 am
(Link)
Ну, символ получается тоже как несколько жестов в 2д с убранной динамической информацией. Методы, соответственно, должны быть похожими.

С юникодом проблема в том, что символов десятки тысяч. Конкретно меня интересует может ли тулза твоя работать как http://shapecatcher.com/ ? Т.е. скриптом напихать туда таблицу символов и распознавать статическую картинку?
[User Picture]
From:[info]ketmar
Date:September 28th, 2013 - 11:40 am
(Link)
это не распознавалка картинок, никогда не была и никогда не будет. это совсем другие алгоритмы.
[User Picture]
From:[info]ketmar
Date:September 28th, 2013 - 11:42 am
(Link)
это, проще говоря, проверка на то, насколько похожи две кривые.
[User Picture]
From:[info]ketmar
Date:September 28th, 2013 - 11:43 am
(Link)
p.s. о чём ты мог бы и сам догадаться, если бы поскал по словам «dynamic time warping», оно же DTW.
From:[info]phantom
Date:September 28th, 2013 - 12:43 pm
(Link)
Да я поскакал, ага. Но кривые можно сравнивать и как функции от времени, и как просто геометрические фигуры. В последнем случае и strokes, и символы должно распознавать.
[User Picture]
From:[info]ketmar
Date:September 28th, 2013 - 12:46 pm
(Link)
ты собрался вдобавок приделывать качественный векторизатор растра? круто. на мелочи не размениваемся, в булочную — не меньше, как на космическом лайнере! %-)
[User Picture]
From:[info]ketmar
Date:September 28th, 2013 - 12:48 pm
(Link)
p.s. да луркай ты по простейшим нейронным распознавателям. есть мнение, что этого будет достаточно в большинстве случаев. сбросил картинке резкость, чтобы узловые точки выпятились, почистил — и в нейронку её.