Распознавание рукописного ввода
Введение
В данной статье пойдет речь о методе распознавания рукописного ввода путем математического анализа всех точек плоскости и перебора всех возможных комбинаций с целью отыскать наиболее лучшее наложение контрольных точек на ранее описанные фигуры. Поясню.
Рукописный ввод — это рисование мыслимым «пером» определенной фигуры. Рисование в компьютерных системах — это сохранение в графической памяти информации обо всех пикселях графического контекста. «Точка на плоскости» в математике — понятие абстрактное. В компьютерной же графике за этим понятием скрывается «пиксель». Данный алгоритм распознавания будет анализировать предоставленный ему набор точек (пикселей) и пытаться в нем отыскать наиболее возможную и похожую фигуру. Фигура, в свою очередь, это каркас, содержащий лишь основные (контрольные) точки, делающие фигуру уникальной. Матчасть
Вообще говоря, сердце алгоритма — всем известная со времен школы Теорема Косинусов, являющаяся обобщенной теоремой Пифагора. Зная координаты трех точек плоскости и их порядок «появления» на ней, мы можем с легкостью определить угол, описанный этими точками (Вершина угла — вторая по счету точка): 
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
Зная косинус, величину угла легко можно вычислить.
Среди набора точек, которые подаются на вход алгоритма, необходимо «подставить» точки во всевозможные каркасы фигур (о них выше) и выбрать наилучшее решение среди найденных. Делается это следующим образом: Мы берем первую и последнюю точки каркасов фигур. Уже две есть, осталось отыскать третью (для нахождения величины угла).
Поиск третьей осуществляется перебором все последующих точек после первой. Решение включать точку в предполагаемый каркас фигуры принимается на основе двух анализов: Попытка подставить точку в угол (в качестве третьей, заключительной) и проверить его на соответствие величине того же угла в каркасе реальной фигуры.
Проверить отношение сторон получившегося угла с тем же отношением сторон угла в каркасе реальной фигуры.
Если эти два условия выполняются, то алгоритм принимает решение о включении точки из набора точек в мыслимый каркас (при этом увеличиваем величину похожести на текущую анализируемую фигуру).
Если, допустим, у нас есть несколько анализируемых каркасов, например,»8» и »6». И результат алгоритма распознавания:»8»-80%,»6» — 90%, то решение принимается в пользу той фигуры, в каркасе которой присутствует больше контрольных точек, т.е в пользу восьмерки.
Процент сходства набора точек с точками в каркасе высчитывается просто: суммируются все точки, которые сошлись с теми же точками в каркасе и находится отношение. Допустим, если в каркасе N контрольных точек, а у нас сошлось M, то процент сходства — M / N * 100 Читать дальше →
