Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Идентификация рукописного ввода

Anna | 25.06.2014 | нет комментариев
В данной статье пойдет речь о способе распознавания рукописного ввода путем математического обзора всех точек плоскости и перебора всех допустимых комбинаций с целью разыскать особенно лучшее наложение контрольных точек на ранее описанные фигуры. Поясню.
Рукописный ввод — это рисование мыслимым «пером» определенной фигуры. Рисование в компьютерных системах — это сохранение в графической памяти информации обо всех пикселях графического контекста. «Точка на плоскости» в математике — представление абстрактное. В компьютерной же графике за этим представлением скрывается «пиксель». Данный алгорифм распознавания будет исследовать предоставленный ему комплект точек( пикселей ) и пытаться в нем разыскать особенно допустимую и схожую фигуру. Фигура, в свою очередь, это каркас, содержащий лишь основные( контрольные ) точки, делающие фигуру уникальной.

Матчасть

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

image

A( x1;y1 )
B( x2;y2 )
C( x3;y3 )

расстояния между точками находятся по теореме Пифагора

a^ = b^ c^ — 2*b*c*cos(ALPHA)
cos(BETA) = (b^ c^-a^) / 2*b*c

Зная косинус, величину угла легко дозволено вычислить.

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

  1. Мы берем первую и последнюю точки каркасов фигур. Теснее две есть, осталось разыскать третью ( для нахождения величины угла ).
  2. Поиск третьей осуществляется перебором все последующих точек позже первой. Решение включать точку в полагаемый каркас фигуры принимается на основе 2-х обзоров:
    • Попытка подставить точку в угол( в качестве третьей, заключительной ) и проверить его на соответствие величине того же угла в каркасе реальной фигуры.
    • Проверить отношение сторон получившегося угла с тем же отношением сторон угла в каркасе реальной фигуры.

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

Если, возможен, у нас есть несколько анализируемых каркасов, скажем, «8» и «6». И итог алгорифма распознавания: «8»-80%, «6» — 90%, то решение принимается в пользу той фигуры, в каркасе которой присутствует огромнее контрольных точек, т.е в пользу восьмерки.

Процент сходства комплекта точек с точками в каркасе высчитывается легко: суммируются все точки, которые сошлись с теми же точками в каркасе и находится отношение. Возможен, если в каркасе N контрольных точек, а у нас сошлось M, то процент сходства — M / N * 100

На словах что-то может быть непостижимо. Следственно вот все то же самое, но наглядно( на примере цифры «6» ):

image

Черным обозначены комплекты точек, красным — каркас, в соответствие с которым происходит обзор.

Цифрами обозначены точки углов( начиная с последнего ), если полагать, что шестерку мы рисуем с точки «2» и заканчиваем точкой «1», то первые две точки, с которых начинается обзор каркаса — «1» и «2», после этого происходит поиск точки «3», так, Дабы ее параметры касательно образуемого ею угла совпадали с теме же параметрами в каркасе. Дальше, как мы обнаружили точку «3», ищем точку «4»( теснее опираясь на точки «2» и «3» ) вновь же, в соответствие с реальным каркасом и т.д.

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

(угол 2 ~= углу 2 в каркасе) И ( a/b ~= a1/b1 ) то точка «3» будет включена
(угол 3 ~= углу 3 в каркасе) И ( b/c ~= b1/c1 ) то точка «4» будет включена
и т.д

Изложение алгорифма на этом заканчивается.

Код

Легко сказать, но перед тем, как сказать необходимо отлично подумать, как сделать сказанное…

Что же, я теснее подумал и реализовал придуманный алгорифм с поддержкой C и графической библиотеки OpenGL ( надстройка GLUT). Графическая библиотека применяется для рисования комплекта точек в двумерном пространстве. Кода получилось не так уж и немного, но и не так уж и много. Фактически каждый код разнесен по заголовочным файлам C . План выложен в публичный доступ для всех, кому это хоть немножечко увлекательно. Исходники расположены на Bitbucket тут. План использует систему контроля версий GIT, так что, у тех, кто пожелает выкачать начальные коды плана, сложностей с этим появиться не должно.

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

Подводные камни

Примерно всюду они есть… и данный алгорифм — не исключение. Прямо скажу, что алгорифм допускает периодические осечки в правильном распознавании.
Взять, к примеру, символы «S» и «5», где осечки фактически неотвратимы. Правда, если высококачественно обозначить все контрольные точки, то, скорее каждого, осечек удастся избежать. Также могут появляться осечки при обзоре фигур, которые имеют трудные округлости. Если осечки происходят на непохожих символах( у меня, скажем, была осечка с «6» и «8»: 6 — 100%, 8 — 83% ), то дозволено запрограммировать каркас всякой из фигур вторично( число повторений не ограничено ). Так удастся избежать ошибок в распознавании. И последнее, что необходимо подметить — угол, образованный последней, первой и 2-й точками соотношение его сторон необходимо помнить. Для этого дозволено данный угол «выравнивать» до 90 градусов, как показано в демо ролике ниже.

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

Если у вас будут какие-либо вопросы, то задавайте — я с радостью на них отвечу.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB