Создание программы, осуществляющей распознавание жестов мыши и выполняющей ассоциированные с ними действия
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
штаба.
Таким образом, входной информацией используемой нейронной сети являются косинусы углов наклона отрезков, соединяющих наиболее значимые точки пути мыши.
2.2.1Упрощение ломаной
Для упрощения ломаной, т.е. уменьшения числа точек, соединяющих ее звенья, используется классический алгоритм аппроксимации Дугласа-Пеккера, который широко применяется в компьютерной графике и картографии.
Основным понятием, использующимся при работе алгоритма, является близость вершины к отрезку ломаной. Алгоритм функционирует сверху вниз, начиная с предположения о том, что упрощенная ломаная состоит из одного отрезка, соединяющего ее первую и последнюю вершину. Далее вычисляется близость оставшихся вершин к этому отрезку. Если обнаружены вершины, расстояние до которых больше порогового, то наиболее удаленная вершина включается в упрощенную ломаную. Затем выдвигается новое предположение, и процесс продолжается рекурсивно для каждого отрезка ломаной до тех пор, пока расстояние от всех точек не будет находиться в заданных пределах [11].
Таким образом, в качестве начальной аппроксимации ломаной используется прямая линия, соединяющая две ее крайние вершины. Последующая аппроксимация определяется путем вычисления расстояний от всех промежуточных вершин до этого отрезка прямой. Если все найденные расстояния меньше порогового, то аппроксимация достаточно хороша. Однако если какое-то расстояние превышает допустимое, то аппроксимация еще не завершена. В этом случае выбирается точка, наиболее удаленная от отрезка, в качестве новой вершины, разделяющей исходную ломаную на две части. Этот процесс показан на рисунке 2.2.
Рисунок 2.2 - Суть алгоритма упрощения
Процедура рекурсивно повторяется для выделенных двух частей ломаной. Если на определенном этапе все расстояния меньше порогового, оставшиеся точки исключаются из ломаной. Последовательные шаги этого процесса показаны на рисунке 2.3 [12-15].
Рисунок 2.3 - Процесс упрощения ломаной
Алгоритм Дугласа-Пеккера упрощения ломаной можно записать в псевдокоде следующим образом:: tol = пороговое расстояние
? = {V0,V1,...,Vn-1} ломаная, состоящая из n звеньев
//Пометить вершины, которые будут включены в упрощенную ломанную
Initially Mark V0 and V1
//Рекурсивно упростить ломаную(tol, ?, 0, n)
//Включить помеченные вершины в упрощенную ломанную
for (i = m = 0; i <= n; i++)
{(Vi is marked)
{
//Добавить к ?
Wm = Vi
m++
}
}
Outupt: ? = {W0,W1,...,Wm-1} упрощенная ломаная, состоящая из m звеньев
//Рекурсивная процедура упрощения ломаной
simplify(tol, ?, j, k)
{(k <= j + 1) //упрощение закончено
//проверить расстояние от промежуточных вершин до отрезка Vj:Vk
Sjk = Vj:Vk
maxd = 0 //расстояние от наиболее удаленной вершины до Sjk= j //индекс наиболее удаленной от Sjk вершины(i = j + 1; i < k - 1; i++) //для каждой промежуточной вершины
{= d(Vi, Sjk) //расстояние от Vi до Sjk
if (dv <= maxd)//расстояние не больше текущего максимального= dv //новое максимальное расстояние= i
}(maxd > tol) //расстояние до вершины превысило пороговое
{
//разделить ломаную на две частиVmaxi //пометить вершину для включения в упрощенную ломаную
//рекурсивно упростить каждую из двух частей
simplify(tol, ?, j, maxi)(tol, ?, maxi, k)
}}
2.2.2Вычисление расстояния от точки до отрезка
Основной операцией в ходе выполнения упрощения ломаной является вычисление расстояния от точки до отрезка.
Для эффективной реализации этой операции можно воспользоваться параметрическим уравнением задания прямой. Для прямой, заданной двумя точками и , с направляющим вектором уравнение можно записать в виде:
,(2.8)
где - параметр (вещественное число).
Из уравнения следует, что , и при - точка, принадлежащая отрезку, ограниченному точками и . Параметр равен отношению расстояния от до к расстоянию от до :
.(2.9)
Рисунок 2.4 - Параметрическое задание прямой
Чтобы вычислить расстояние от произвольной точки P до прямой L заданной параметрическим уравнением, необходимо опустить перпендикуляр из точки P на прямую L. Пусть P(b) - основание перпендикуляра и пусть параметрическое уравнение прямой определено в виде: P(t)= P0+t(P1-P0). Тогда вектор P0P(b) является проекцией вектора P0P на отрезок P0P1, как показано на рисунке 2.5.
Рисунок 2.5 - Расстояние от точки до прямой
Таким образом, при и
(2.10)
И
,(2.11)
где - единичный направляющий вектор прямой .
При вычислении расстояния от точки до отрезка необходимо учитывать, что основание перпендикуляра может не лежать на самом отрезке, а находиться на его продолжении. В этом случае кратчайшим расстоянием является расстояние от точки до одной из крайних точек отрезка (рисунок 2.6).
Рисунок 2.6 - Расстояние от точки до отрезка
Чтобы выбрать наиболее близкую точку отрезка, необходимо определить, лежит ли основание перпендикуляра на продолжении отрезка. Для этого можно рассмотреть величины углов между отрезком и векторами и . Если один из этих углов равен , то соответствующая точка является основанием перпендикуляра . Если углы не прямые, то основание лежит на продолжении отрезка слева или справа от него в зависимости от того, является угол тупым или острым. Эти условия легко проверяются путем вычисления скалярного произведения векторов и проверки результата, ко