Создание программы, осуществляющей распознавание жестов мыши и выполняющей ассоциированные с ними действия

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

Перечень условных обозначений, символов, единиц, сокращений и терминов

Введение

1 Анализ проблемной области и постановка задачи

1.1 Нейроны

1.2 Машинное моделирование искусственных нейронов

1.3 Искусственные нейронные сети

1.4 Контролируемое обучение

1.5 Постановка задачи

2 Описание методов и алгоритмов

2.1 Структура нейронной сети

2.2 Входная информация

2.2.1 Упрощение ломаной

2.2.2 Вычисление расстояния от точки до отрезка

2.2.3 Преобразование отрезков в косинусы углов наклона

2.3 Выходная информация

2.4 Обучение сети

3 Описание разработанной программной системы

3.1 Перечень функций

3.2 Описание интерфейса

3.3 Список поддерживаемых жестов

3.4 Системные требования

3.5 Инсталляция программы

3.6 Запуск программы

3.7 Ассоциация действий

3.8 Завершение программы

4 Система защиты информации

5 Анализ исследовательской эксплуатации и возможных применений

Выводы

Перечень ссылок

Приложение А Бизнес-план

Приложение Б Безопасность жизни и деятельности человека

Приложение В Слайды презентации.

Приложение Г Электронные документы

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ, СОКРАЩЕНИЙ И ТЕРМИНОВ

ООП-объектно-ориентированное программирование;

ПП-программный продукт;

ИНС-искусственная нейронная сеть;

ПК-персональный компьютер;

ПО-программное обеспечение;

БЖДЧ-безопасность жизни и деятельности человека;

ЧМС-человек-машина-среда.

ВВЕДЕНИЕ

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

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

Таким образом, пользователям становится доступным более эффективное и дружественное взаимодействие с компьютером. В ближайшем будущем это приведет к появлению новых интерфейсов с возможностями, несравнимыми со всеми существующими устройствами ввода.

Исследования в области ИНС пережили три периода активизации. Последний начался с начала 80-х годов. ИНС вновь привлекли интерес исследователей, это было связано с энергетическим подходом Хопфилда [2] и алгоритмом обратного распространения для обучения многослойного персептрона (многослойные сети прямого распространения), впервые предложенного Вербосом [3] и независимо разработанного рядом других авторов. Алгоритм получил известность благодаря Румельхарту [4] в 1986 году. Андерсон и Розенфельд [5] подготовили подробную историческую справку о развитии ИНС.

Большое внимание к нейронным сетям обусловлено их сходством с биологическими системами, обладающими высокими способностями к идентификации и адаптации. Параллельный характер сетей позволяет существенно повысить скорость выполнения вычислений. Благодаря наличию нелинейных передаточных функций, нейросеть способна аппроксимировать нелинейное поле с любой степенью точности. Тот факт, что параметры сети настраиваются лишь на основе данных о входе и выходе, дает возможность использования сетей как адаптивных или обучающихся систем в условиях неопределенности. Благодаря этим довольно привлекательным характеристикам, искусственные нейронные сети показали невероятно высокие результаты в задачах распознавания образов, в проблемах оптимизации, идентификации и управления нелинейными объектами при наличии структурных сбоев. В частности, для распознавания образов, в сложных административных системах, в банках и на биржах для прогнозирования курсов валют, где модели носят нелинейный характер и требуют идентификации и управления в реальном времени [6].

Одним из перспективных способов ввода информации является ввод жестов, применяемый во многих современных карманных компьютерах. Этот метод возник и получил свое применение еще в 70-х годах. С тех пор многочисленные приложения использовали похожие интерфейсы, позволяя пользователям выполнять сложные операции с использованием устройства ввода. К современным программам, использующим распознавание жестов мыши, можно отнести такие известные Web-браузеры, как Opera и Mozilla.

К примеру, Mozilla использует такой алгоритм распознавания жестов. После записи жеста каждая последующая его точка сравнивается с предыдущей и генерируется одно из 4-х возможных направлений, причем одинаковые направления объединяются в одно. Далее выполняется поиск полученной последовательности в таблице жестов. Если искомый образец не найден, производится дополнительный ряд упрощений жеста, после чего поиск повторяется [7].

В данном дипломом проекте делается достаточно удачная попытка применения теории искусственных нейронных сетей к задаче распознавания жестов.

1 АНАЛИЗ ПРОБЛЕМНОЙ ОБЛАСТИ И ПОСТАНОВКА ЗАДАЧИ

За последние пять лет было написано несколько книг, в которых теория и общее приложение нейронных сетей излагались ясным способом: Wasserman, 1989; Caudill и Butler, 1989 и 1992: Hecht-Nielsen, 1990: Maren, Harston и Pap, 1990; Simpson, 1990; Nelson и Illingsworth, 1990. Эти книги и обширное количество конференций и периодической технической литературы: Proceedings of the International Neural Network Society Meetings с 1987 по 1994; Journal of Neural Computing; Neural Networks; IEEE Transactions for Neural Networks; и Neural Computing ; охватили фундаментальные концепции и технологию нейронных сетей и их потенциальное приложение к многочисленным полям.

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

К задачам, успешно решаемым ИНС на данном этапе их развития, относятся:

- распознавание зрительных, слуховых образов (от распознавания текста и целей на экране радара до систем голосового управления);

- ассоциативный поиск информации и создание ассоциативных моделей: синтез речи и формирование естественного языка;

- формирование моделей и различных нелинейных и трудно описываемых математических систем; прогнозирование развития этих систем во времени: применение на производстве, прогнозирование развития циклонов и других природных процессов; прогнозирование изменений курсов валют и др. финансовых процессов;

- системы управления и регулирования с предсказанием: управление роботами;

- разнообразные конечные автоматы: системы массового обслуживания,

телекоммуникационные системы;

- принятие решений и диагностика, исключающие логический вывод, особенно в областях, где отсутствуют четкие математические модели: в медицине, криминалистике.

1.1 Нейроны

Нейрон (биологический) - одна из 1015 клеток мозга, способная генерировать электрический импульс, в случае, когда суммарный потенциал превысит критическую величину. Соединяясь, друг с другом, нейроны образуют сеть, по которой путешествуют электрические импульсы. Контакты между нейронами (синапсы), могут менять эффективность передачи сигналов (вес связи) от нейрона к нейрону. Самая популярная на сегодняшний день гипотеза основана на том, что именно нейронные сети мозга обрабатывают информацию. При этом «обучение» сети и запоминание информации базируется на настройке значений весов связей между нейронами [8].

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

Нейрон простой процессор, который получает и комбинирует сигналы от других нейронов до входных путей называемых дендритами. Если объединенные сигналы от всех дендритов достаточно сильны, нейронные вспышки производят сигнал вывода по пути называемому аксоном. Разбиения аксона, соединяясь с сотнями или тысячами дендритов вводят пути других нейронов через синапсы (соединения, содержащие жидкость нейромедиатора управление потоком сигналов) расположенный в дендритах. Передача сигналов поперек синапсов электрохимическая по своей природе, и величины сигналов зависят от синоптических сил синапсов. Сила или проводимость (инверсия сопротивления) синоптического соединения изменяются, поскольку мозг "учится". Синапсы основные "модули памяти" мозга, и регулирование этих синапсов составляет обучение [9].

Каждый нейрон характеризуется своим текущим состоянием по аналогии с нервными клетками головного мозга, которые могут быть возбуждены или заторможены. Он обладает группой синапсов - однонаправленных входных связей, соединенных с выходами других нейронов, а также имеет аксон - выходную связь данного нейрона, с которой сигнал (возбуждения или торможения) поступает на синапсы следующих нейронов. Общий вид нейрона приведен на рисунке 1.1. Каждый синапс характеризуется величиной синоптической связи или ее весом w_i.

Рисунок 1.1 - Общий вид нейрона

нейронная сеть мышь распознавание программа

Текущее состояние нейрона определяется, как взвешенная сумма его входов:

.(1.1)

Выход нейрона есть функция его состояния:

y = f(s).(1.2)

Нелинейная функция f называется активационной и может иметь различный вид, как показано на рисунке 1.2. Одной из наиболее распространенных является нелинейная функция с насыщением, так называемая логистическая функция или сигмоид (т.е. функция S-образного вида):

.(1.3)

Рисунок 1.2 - а) функция единичного скачка; б) линейный порог (гистерезис); в) гиперболический тангенс; г) сигмоид - формула (1.3)

При уменьшении сигмоид становится более пологим, в пределе при =0 вырождаясь в горизонтальную линию на уровне 0.5, при увеличении сигмоид приближается по внешнему виду к функции единичного скачка с порогом T в точке x=0. Из выражения для сигмоида очевидно, что выходное значение нейрона лежит в диапазоне [0,1].

1.2 Машинное моделирование искусственных нейронов

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

Если функция преобразования типа непрерывна нелинейного (или линейного) отношения, вывод непрерывная функция объединенного ввода. Обычно используется функция преобразования типа сигмоидальная функция, которая изменяется гладко от нуля (для больших отрицательных значений) до единицы (для больших положительных значений) со значением 1/2 для нулевого ввода. Аксон вывода элементарного процессора выделяется и становится вводом для многих других элементарных процессоров. Эти сигналы проходят через связи (синоптические соединения) которые соответствуют синоптической силе нейронных связей. Входные сигналы на элементарный процессор изменяются весом подключения до подведения итогов элементарным процессором [10].

1.3 Искусственные нейронные сети

Искусственная нейронная сеть может быть определена как вычислительная система обработки, состоящая из многих элементарных процессоров, соединенных вместе в структуру, похожую на структуру мозга. Эти элементарные процессоры обычно организовываются в последовательности уровней, с полными связями между уровнями. Как правило, имеется три (или больше) уровней: входной уровень, где данные представлены в сеть через входной буфер, уровень вывода с буфером который отвечает за вывод на данный ввод, и один или большее количество промежуточных или "скрытых" уровней. Искусственная нейронная сеть возводит в степень два процесса: обучение и повторный вызов. Обучение - процесс приспосабливания весов связей в ответ на внешние стимулы, представленные во входном буфере. Сеть " учится" в соответствии с узнающим правилом, управляющим регулированием весов связей в ответ на обучение примеров, находящихся в буферах вводов и вывода. Повторный вызов процесс принятия ввода и создания ответа, определенного геометрией и синоптическими весами сети.

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

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

За структурой нейронные сети можно разделить на неполносвязные и полносвязные, со случайными и постоянными (регулярными) связями, симметричными и несимметричными связями (рисунок 1.3).



Рисунок 1.3 - Классификация нейронных сетей

Неполносвязные нейронные сети (описываются неполносвязным ориентированным графом и названы персептронами) делятся на однослойные (простые персептроны) и многослойные с прямыми, перекрестными и обратными связями.

В нейронных сетях с прямыми связями нейроны j-ого слоя на входах могут соединяться только с нейронами i-ых слоев, где j > i, то есть с нейронами слоев, которые лежат ниже.

В нейронных сетях с перекрестными связями припускаются связи внутри одного слоя, то есть приведенная выше неравенство заменяется на j и.

В нейронных сетях с обратными связями используются связи j-ого слоя на входах с i-ым при j < i. Кроме того, за видом связей различают персептроны с регулярными и случайными связями.

За сигналами, которые подаются на входы и выходы, нейронные сети можно разделить на аналоговые и бинарные.

За моделированием времени - на сети с беспрерывным и дискретным временем. Для программной реализации применяется, как правило, дискретное время.

По способу подачи информации на входы нейронной сети различают:

- подачу сигналов на синапсы входных нейронов;

- подачу сигналов к выходам входных нейронов;

- подачу сигналов в виде веса синапсов входных нейронов.

По способу снятия информации из выходов нейронной сети различают:

- снятия из выходов исходных нейронов;

- снятия с синапсов исходных нейронов;

- снятия в виде значений веса синапсов исходных нейронов.

По способу организации обучения разделяют обучение нейронных сетей с учителем (supervised neural networks) и без учителя (nonsupervised).

По способу представления примеров различают представление одиночных примеров и "страницы" примеров. В первом случае изменение состояния нейронной сети (обучения) происходит после представления каждого примера. Во втором - после представления "страницы" (множества) примеров на основании анализа сразу всех их.

По специфике особенностями модели нейрона, различают нейроны с разными нелинейными функциями.

Разные модели ИНС с целью сравнения можно характеризовать такими свойствами (некоторые из них связанные с вышеуказанной классификацией нейронных сетей):

- структура связей между нейронами;

- тип входных сигналов;

- тип исходных сигналов;

- тип передающей функции;

- особенности функционирования в случае распознавания (тестирования);

- особенности алгоритма обучения;

- емкость сети - количество образов (классов), которые может запоминать и распознавать сеть.

Различают такие архитектуры ИНС:

а) с учителем:

1) двунаправленная ассоциативная память (ДАП) (ассоциативная память, распознавание образов);

2) многослойный персептрон (распознавание образов, классификация);

3) однослойный персептрон (распознавание образов, классификация);

4) Хемминга (распознавание образов, классификация, ассоциативная память);

5) Аутстар (распознавание образов, классификация);

6) Инстар (распознавания образов);

7) Макснет (совместно с сетью Хемминга, в составе нейросетевых систем распознавания образов);

8) нейросетевой гауссов классификатор (распознавание образов, классификация);

9) вероятностная НС (классификация);

10) обобщенно-регрессионная (задачи регрессии);

11) Хопфилда;

12) линейная сеть.

б) без учителя:

1) сеть адаптивной резонансной теории 1 (АРТ-1) (распознавание образов, кластерный анализ);

2) сеть Хемминга (распознавание образов, классификация, ассоциативная память, надежная передача сигналов в условиях помех);

3) сеть Кохонена.

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

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

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

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

1.4 Контролируемое обучение

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

Обычно с искусственной нейронной сетью используются несколько различных видов изучения. Возможно наиболее обычный так называемое контролируемое обучение. Прежде, чем процесс обучения начинается, все веса установлены в маленькие случайные значения. Тогда обучающийся ввод применяется к входному уровню, размножается через сеть и производит вывод. Этот вывод в отличие от желательного вывода, производит сигнал ошибки, который, в свою очередь, является вводом к процессу корректировки веса. Используются различные алгоритмы изучения, чтобы корректировать веса с приращением. Когда ввод применяется снова на входной буфер, производится приращение вывода, который снова в отличие от желательного вывода производит второй сигнал ошибки. Этот итеративный процесс продолжается, пока вывод искусственной нейронной сети существенно не равен желательному выводу, и неприводимому минимуму. В этой точке, сеть, как считают, "обучается”. Через различные алгоритмы изучения, сеть постепенно конфигурирует себя, чтобы достичь желательных отношений ввода - вывода или "отображения". Контролируемое обучение часто осуществляется с методикой, называемой backpropagation, наиболее общий метод изучения; однако, неконтролируемое обучение, которое осуществлено в сетях Кохонена, также используется во многих ситуациях [8].

Бывают ситуации, когда сеть не может научиться. Это происходит в том случае, когда на определенном этапе обучения исчерпываются дальнейшие возможности поиска закономерностей между учебными параметрами и результатами.

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

Для обучения ИНС можно выделить две большие группы алгоритмов - градиентные (основанные на вычислении частных производных функции ошибки по параметрам сети) и стохастические (поиск минимума функции ошибки ведется случайным образом). Среди градиентных различают алгоритмы первого и второго порядков.

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

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

Алгоритмы обучения разделяют на алгоритмы обучения "с учителем" и "без учителя". Алгоритм называется алгоритмом обучения "с учителем", если при обучении известные и входные, и исходные векторы сети. Есть пары вход+выход - известные условия задачи и решения. В процессе обучения сеть изменяет свои параметры и учится давать нужное отображение XY. Сеть учится предоставлять уже известные нам результаты. За счет способности к обобщению сетью может быть получены новые результаты, если подать на вход вектор, который не встречался при обучении (рисунок 1.4).

Рисунок 1.4 - Схема обучения нейронной сети "с учителем"

Алгоритм относится к обучению "без учителя", если известно только входные вектора, и на их основе сеть учится придавать наилучшее значение выходов (рисунок 1.5).

Рисунок 1.5 - Схема обучения "без учителя"

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

1.5 Постановка задачи

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

Она должна обладать следующими характеристиками и выполнять такие функции:

а) эффективное распознавание жестов мыши, не зависящее от масштаба и скорости ввода;

б) ассоциация действий с любым из поддерживаемых жестов, которыми могут быть запуск программ, открытие документов, вызов функций и т. д.;

в) удобный графический интерфейс пользователя, позволяющий интерактивно создавать и удалять ассоциации;

г) сохранение ассоциированных действий в файле конфигурации;

д) выполнение в фоновом режиме: ввод жестов доступен при работе любого приложения.

Разработать экономическое обоснование и вопросы охраны труда.

2 ОПИСАНИЕ МЕТОДОВ И АЛГОРИТМОВ

2.1 Структура нейронной сети

Нейроны могут объединяться в сети различным способом. Самым распространенным видом является многослойный персептрон. Сеть состоит из произвольного количества слоев. Нейроны каждого слоя соединяются с нейронами предыдущего и последующего слоев по принципу «каждый с каждым». Первый слой называется сенсорным или входным, внутренние слои называется скрытыми или ассоциативными, последний (самый правый) - выходным или результативным. Количество нейронов в слоях может быть произвольным. Обычно во всех скрытых слоях одинаковое количество нейронов.

Обозначим количество слоев и нейронов в слое. Входной слой: N_I нейронов; N_H нейронов в каждом скрытом слое; N_O выходных нейронов; X - вектор входных сигналов сети, Y - вектор выходных сигналов.

Входной слой не выполняет никаких вычислений, а лишь распределяет входные сигналы.

Обозначим через N_L полное кол-во слоев в сети, считая входной.

Работа многослойного персептрона (MLP) описывается формулами:

S_jl=w_ijlx_ijl,(2.1)

где S_jl - сигнал S j - го нейрона в слое l;

i номер входа, j - номер нейрона в слое, l - номер слоя;

x_ijl i -й входной сигнал j-го нейрона в слое l;

w_il весовой коэффициент i-го входа нейрона номер j в слое l.

Yjl=F(Sji-jl),(2.2)

где Yjl выходной сигнал нейрона;

_jl пороговый уровень нейрона j в слое l.

Xij(l+1)=Yil,(2.3)

где X_ij - вектор входных сигналов сети.

Введем обозначения w_ijl вектор-столбец весов для всех входов нейрона j в слое l, W_l - матрица весов всех нейронов слоя l. В столбцах матрицы расположены вектора w_jl. Аналогично x_jl - входной вектор-столбец слоя l. Каждый слой рассчитывает нелинейное преобразование от линейной комбинации сигналов предыдущего слоя. Отсюда видно, что линейная функция активации может применяться только для тех моделей сети, где не требуется последовательное соединение слоев нейронов друг за другом. Для многослойных сетей функция активации должна быть нелинейной, иначе можно построить эквивалентную однослойную сеть, и многослойность оказывается ненужной. Если применена линейная функция активации, то каждый слой будет давать на выходе линейную комбинацию входов. Следующий слой даст линейную комбинацию выходов предыдущего, а это эквивалентно одной линейной комбинации с другими коэффициентами, и может быть реализовано в виде одного слоя нейронов.

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

Обучение сети базируется на правильном выборе веса связей между элементами. Избирается такой вес связей, чтобы суммарная среднеквадратичная ошибка для элементов учебной выборки была минимальной. Достичь этого проще, чем помощь разных методов. После обучения персептрона проводится процедура тестирования, которое разрешает оценить результаты работы. Для этого учебную выборку разделяют на две части. Одна часть используется для обучения, а вторая, для которой результат есть известным, задействованная в процессе тестирования. Процент правильных результатов работы сети на этапе тестирования есть показателем качества работы персептрона. Ошибкой сети можно считать Es= ||ds- ys|| для каждого пара (xs, ds). Чаще за все для оценки качества обучения выбирают суммарную квадратичную ошибку:

.(2.4)

Реже используется средняя относительная ошибка:

.(2.5)

Ее преимущество в том, что она дает значения, которое не зависит направления ни от количества примеров в учебном множестве, ни от размерности исходного вектора, и имеет удобное для восприятие человеком значения в интервале от 0% до 100%.

Общий алгоритм решения задачи:

определить, какой смысл вкладывается в компоненты входного вектора х; входной вектор должен содержать всю информацию, необходимую для получения ответа;

выбрать выходной вектор у таким образом, чтобы его компоненты содержали полный ответ поставленной задачи;

выбрать вид нелинейности в нейронах (функции активации), при этом желательно учесть специфику задачи, т.к. удачный выбор сократит время обучения;

выбрать число слоев и нейронов в слое;

задать диапазон изменения входов, выходов, весов и пороговых уровней, учитывая множество значений выбранной функции активации;

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

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

подать на вход сети условия задачи в виде вектора x, рассчитать выходной вектор y, который и даст формализованное решение задачи.

Многослойный персептрон может рассчитывать выходной вектор y для любого входного вектора x, т.е. давать значение некоторой векторной функции y=f(x). Следовательно, условие любой задачи, которая может быть поставлена персептрону, должно являться множеством векторов {x ¹... x ^S} с N _I компонентами каждый: x ^s=(x₁ ^s ... x _{N I} ^s).

Решением задачи будет множество векторов {y¹...y^S}, каждый вектор y^s с N_O компонентами; y^s = f (x^s), где s =1..S номер предъявленного образа.

Все, что способен сделать персептрон это сформировать отображение X Y для X x. Данное отображение мы не можем "извлечь" полностью из персептрона, а можем только посчитать отображение произвольного количества точек:

.(2.6)

где множество векторов x1...xS формализованное условие задачи;

множество y1... yS - формализованное решение.

Задача формализации, т.е. выбора смысла, которым наделяются компоненты входного и выходного векторов, пока решается только человеком на основе практического опыта.

Архитектурой нейронной сети, положенной в основу программы, является многослойный персептрон. Используемая ИНС схематически изображена на рисунке 2.1.

Рисунок 2.1 - Структура нейронной сети

Нейронная сеть имеет следующую структуру:

- число входов - 32;

- число выходов - 29;

- число скрытых слоев - 1;

- число нейронов в скрытом слое - 32.

В качестве активационной функции каждого нейрона сети используется сигмовидная функция, которая имеет следующий вид:

,(2.7)

где - сетевая функция нейрона, .

2.2 Входная информация

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

а) упрощении ломаной, а именно выделении из нее 17 наиболее значимых точек;

б) преобразовании 16 отрезков, соединяющих 17 наиболее значимых точек, в 32 косинуса их углов наклона относительно осей координат.

Упрощение ломаной дает возможность выделить точки, количество которых соответствует числу входов сети.

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

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

2.2.1 Упрощение ломаной

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

Основным понятием, использующимся при работе алгоритма, является близость вершины к отрезку ломаной. Алгоритм функционирует сверху вниз, начиная с предположения о том, что упрощенная ломаная состоит из одного отрезка, соединяющего ее первую и последнюю вершину. Далее вычисляется близость оставшихся вершин к этому отрезку. Если обнаружены вершины, расстояние до которых больше порогового, то наиболее удаленная вершина включается в упрощенную ломаную. Затем выдвигается новое предположение, и процесс продолжается рекурсивно для каждого отрезка ломаной до тех пор, пока расстояние от всех точек не будет находиться в заданных пределах [11].

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



Рисунок 2.2 - Суть алгоритма упрощения

Процедура рекурсивно повторяется для выделенных двух частей ломаной. Если на определенном этапе все расстояния меньше порогового, оставшиеся точки исключаются из ломаной. Последовательные шаги этого процесса показаны на рисунке 2.3 [12-15].

Рисунок 2.3 - Процесс упрощения ломаной

Алгоритм Дугласа-Пеккера упрощения ломаной можно записать в псевдокоде следующим образом:

Input: tol = пороговое расстояние

Л = {V₀,V₁,...,V_n-1} ломаная, состоящая из n звеньев

//Пометить вершины, которые будут включены в упрощенную ломанную

Initially Mark V₀ and V₁

//Рекурсивно упростить ломаную

simplify(tol, Л, 0, n)

//Включить помеченные вершины в упрощенную ломанную

for (i = m = 0; i <= n; i++)

{

if (V_i is marked)

{

//Добавить к Щ

W_m = V_i

m++

}

}

Outupt: Щ = {W₀,W₁,...,W_m-1} упрощенная ломаная, состоящая из m звеньев

//Рекурсивная процедура упрощения ломаной

simplify(tol, Л, j, k)

{

if (k <= j + 1) //упрощение закончено

return

//проверить расстояние от промежуточных вершин до отрезка V_j:V_k

S_jk = V_j:V_k

maxd = 0 //расстояние от наиболее удаленной вершины до S_jk

maxi = j //индекс наиболее удаленной от S_jk вершины

for (i = j + 1; i < k - 1; i++) //для каждой промежуточной вершины

{

dv = d(V_i, S_jk) //расстояние от V_i до S_jk

if (dv <= maxd)

continue //расстояние не больше текущего максимального

maxd = dv //новое максимальное расстояние

maxi = i

}

if (maxd > tol) //расстояние до вершины превысило пороговое

{

//разделить ломаную на две части

Mark V_maxi //пометить вершину для включения в упрощенную ломаную

//рекурсивно упростить каждую из двух частей

simplify(tol, Л, j, maxi)

simplify(tol, Л, maxi, k)

}}

2.2.2 Вычисление расстояния от точки до отрезка

Основной операцией в ходе выполнения упрощения ломаной является вычисление расстояния от точки до отрезка.

Для эффективной реализации этой операции можно воспользоваться параметрическим уравнением задания прямой. Для прямой, заданной двумя точками и , с направляющим вектором уравнение можно записать в виде:

,(2.8)

где - параметр (вещественное число).

Из уравнения следует, что , и при - точка, принадлежащая отрезку, ограниченному точками и . Параметр равен отношению расстояния от до к расстоянию от до :

.(2.9)

Рисунок 2.4 - Параметрическое задание прямой

Чтобы вычислить расстояние от произвольной точки P до прямой L заданной параметрическим уравнением, необходимо опустить перпендикуляр из точки P на прямую L. Пусть P(b) - основание перпендикуляра и пусть параметрическое уравнение прямой определено в виде: P(t)= P₀+t(P₁-P₀). Тогда вектор P₀P(b) является проекцией вектора P₀P на отрезок P₀P₁, как показано на рисунке 2.5.

Рисунок 2.5 - Расстояние от точки до прямой

Таким образом, при и

(2.10)

И

,(2.11)

где - единичный направляющий вектор прямой .

При вычислении расстояния от точки до отрезка необходимо учитывать, что основание перпендикуляра может не лежать на самом отрезке, а находиться на его продолжении. В этом случае кратчайшим расстоянием является расстояние от точки до одной из крайних точек отрезка (рисунок 2.6).

Рисунок 2.6 - Расстояние от точки до отрезка

Чтобы выбрать наиболее близкую точку отрезка, необходимо определить, лежит ли основание перпендикуляра на продолжении отрезка. Для этого можно рассмотреть величины углов между отрезком и векторами и . Если один из этих углов равен , то соответствующая точка является основанием перпендикуляра . Если углы не прямые, то основание лежит на продолжении отрезка слева или справа от него в зависимости от того, является угол тупым или острым. Эти условия легко проверяются путем вычисления скалярного произведения векторов и проверки результата, который определяет, необходимо ли находить расстояние до точки или , или длину перпендикуляра [16].

Алгоритм вычисления расстояния от точки до отрезка можно записать в псевдокоде следующим образом:

distance(Point P, Segment P0:P1)

{

v = P1 - P0

w = P - P0

if ((c1 = w·v) <= 0)

return d(P, P0)

if ((c2 = v·v) <= c1)

return d(P, P1)

b = c1 / c2

Pb = P0 + bv

return d(P, Pb)

}

2.2.3 Преобразование отрезков в косинусы углов наклона

Если предположить, что каждый отрезок упрощенной ломаной принадлежит прямой , заданной его начальной точкой и конечной точкой , то косинусы углов наклона отрезка являются координатами направляющего вектора прямой , нормализованного к единичному вектору. Т.е. если - единичный направляющий вектор прямой , то его координаты равны , где - угол наклона отрезка относительно оси , - угол наклона отрезка относительно оси (рисунок 2.7).

Рисунок 2.7 - Наклон отрезка относительно осей координат

2.3 Выходная информация

Число выходов используемой нейронной сети соответствует количеству жестов, поддерживаемых программой, и равно 29. Значения активационных функций нейронов выходного слоя позволяют судить о том, к какому эталонному жесту наиболее близок поданный на вход вектор.

Для того чтобы выходные значения ИНС можно было интерпретировать как вероятности, характеризующие степень соответствия введенного жеста каждому из идеальных жестов, результат нейронной сети пропускается через функцию SOFTMAX, которая имеет следующий вид:

.(2.12)

Среди полученных значений находится максимальное число и соответствующий ему номер выхода ИНС. Если это число превысило порог распознавания, то введенный жест определяется данным номером выхода.

2.4 Обучение сети

Обучающей выборкой в процессе настройки весов нейронной сети служил набор векторов, представляющих собой идеальные (эталонные) жесты.

В качестве алгоритма обучения нейронной сети использовался стандартный алгоритм обратного распространения ошибки, состоящий из следующих шагов:

а) выполнить инициализацию весов связей небольшими случайными значениями, задать максимально допустимую среднеквадратичную ошибку , положить текущее значение среднеквадратичной ошибки ИНС ;

б) подать на вход сети -ый входной вектор ;

в) выполнить распространение сигналов в соответствии с прямыми связями:

,(2.13)

где - номер слоя нейронов, ; - выходной сигнал -го нейрона -го слоя; - веса связей -го слоя;

г) вычислить среднеквадратичную ошибку ИНС:

(2.14)

и ошибку нейронов выходного слоя:

(2.15)

выполнить распространение ошибки в обратном направлении, руководствуясь правилом:

;(2.16)

д) обновить веса связей каждого слоя в соответствии с правилом:

;(2.17)

е) если , то и перейти к пункту 2, иначе перейти к шагу з;

ж) проверить значение ошибки : если , то закончить вычисления, иначе присвоить , и перейти к шагу б.

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

Например, необходимо распознать букву «А», которая наиболее близка эталонному жесту поданного на вход вектор. Изобразим букву в виде точечных изображений (рисунок 2.8).

Рисунок 2.8 - Точечное изображение буквы

Темной клетке-пикселю на изображении отвечает I_ij=1, светлому - I_ij=0. Построим многослойную сеть из N_i* N_j входами, каждому входу отвечает один пиксель x_k=I_ij, k=1,…,N_i*N_j. Как исходные сигналы выберем вероятности того, что предъявленное изображение отвечает данной букве y=(c₁,…,c_M)^T... Сеть рассчитывает выход:

,(2.18)

где выход с₁=0.9 означает, что предъявленное изображение буквы «А» и сеть уверенные в этом на 90%, выход с₂=0.1 - что изображения отвечало букве «Б» с вероятностью10% и т.п.

Есть и другой способ, в котором входы сети выбираются так же, а выход только один, номер m предъявленной буквы. Сеть учится придавать значение m за предъявленным изображением I: I_ij m. Недостатком такой формализации есть то, что буквы, которые имеют близкие номера, но разные изображения, могут быть перепутаны сетью при распознавании.

3 ОПИСАНИЕ РАЗРАБОТАННОЙ ПРОГРАММНОЙ СИСТЕМЫ

3.1 Перечень функций

В рамках данного дипломного проекта создана программа, предназначенная для распознавания жестов мыши и выполнения ассоциированных с ними действий.

Она обладает следующими характеристиками и выполняет такие функции:

- эффективное распознавание жестов мыши, не зависящее от масштаба и скорости ввода;

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

- удобный графический интерфейс пользователя, позволяющий интерактивно создавать и удалять ассоциации;

- сохранение ассоциированных действий в файле конфигурации;

- выполнение в фоновом режиме: ввод жестов доступен при работе любого приложения.

3.2 Описание интерфейса

Разработанная программа является оконным Windows-приложением. В силу своей специфики программа не имеет традиционного главного окна: приложение запускается в фоновом режиме и большую часть времени незаметно для пользователя. Основным средством доступа к программе является значок на панели задач, помещаемый туда после ее запуска. Панель задач при запущенной программе имеет вид, показанный на рисунке 3.1.



Рисунок 3.1 - Значок программы на панели задач

При щелчке правой кнопкой мыши на значке отображается контекстное меню программы (рисунок 3.2), которое позволяет:

открывать основное окно, предназначенное для создания, изменения и удаления

- ассоциаций;

- отображать окно “About”, содержащее краткие сведения о программе (рисунок 3.3);

- завершать работу программы.

Рисунок 3.2 - Контекстное меню программы

Рисунок 3.3 - Краткие сведения о программе

Основное окно также может быть открыто двойным щелчком на значке программы.

Главное окно программы имеет вид, показанный на рисунке 3.4. Оно содержит такие управляющие элементы:

- список, хранящий существующие ассоциации между жестами и определенными действиями. Каждый элемент списка включает в себя изображение жеста и строку, определяющую выполняемое действие;

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

- выпадающий список, позволяющий выбирать жест для ассоциации с новым или уже существующим действием;

- кнопку “Add”, служащую для добавления нового действия;

- кнопку “Delete”, служащую для удаления текущего действия;

- кнопку “OK”, выполняющую сохранение внесенных изменений в файл конфигурации и закрывающую основное окно программы;

- кнопку “Cancel”, закрывающую основное окно программы без сохранения внесенных изменений.

Рисунок 3.3 - Главное окно программы

Созданная программа для сохранения своего состояния использует конфигурационный файл, который является обыкновенным тестовым файлом с именем “exeCute.dat” и должен находиться в одном каталоге с исполняемым файлом программы. Приложение считывает файл конфигурации сразу после своего запуска и записывает в него информацию после нажатия кнопки “OK” в главном окне программы.

Файл конфигурации имеет следующий формат:

символ_жеста1|имя_файла1|[параметры1]

символ_жеста2|имя_файла2|[параметры2]

....

символ_жестаN|имя_файлаN|[параметрыN]

где символ_жеста - символ, соответствующий жесту мыши, имя_файла - путь и имя исполняемого файла или документа, ассоциированного с данным жестом, параметры - необязательный список аргументов программы.

Примером файла конфигурации может быть:

u|winword.exe|

n|excel.exe|

(|calc.exe|

)|winrar.exe|

X|mspaint.exe|

_|C:\Program Files\Borland\Delphi6\Bin\delphi32.exe|

/|C:\Program Files\Winamp\winamp.exe|

\|D:\Video\NetLook\NetLook.exe|

#|iexplore.exe|http://www.sloboda.net

O|explorer.exe|D:\

V|mplayer2.exe|

A|regedit.exe|

@|C:\Program Files\The Bat!\thebat.exe|

Z|rundll32.exe|cuteDll.dll,cuteLogoff

8|rundll32.exe|cuteDll.dll,cuteLock

3.3 Список поддерживаемых жестов

Разработанная программа поддерживает распознавание 29 различных жестов. С каждым жестом связано его небольшое изображение, символ и краткое название. Изображение жеста позволяет наглядно и удобно добавлять и изменять ассоциации действий в основном окне программы. Текстовый символ служит для сохранения информации о жесте в файле конфигурации программы. Определенное соответствие символа жеста его изображению позволяет с легкость редактировать конфигурационный файл вручную. Таблица 3.1 содержит полный список поддерживаемых жестов.

Таблица 3.1 - Список поддерживаемых жестов

Жест	Символ	Название	Жест	Символ	Название
	-	“Вверх”		>	“Стрелка вправо”
	_	“Вниз”		Z	“Зигзаг”
	\	“Влево”		8	“Песочные часы”
	/	“Вправо”		@	“Спираль”
	n	“Вверх-вниз”		~	“Волна”
	u	“Вниз-вверх”		P	“Флаг”
	(	“Влево-вправо”		N	“N”
	)	“Вправо-влево”		W	“W”
	7	“Вверх-влево”		M	“M”
	T	“Вверх-вправо”		O	“Круг”
	J	“Вниз-влево”		#	“Квадрат”
	L	“Вниз-вправо”		^	“Треугольник”
	A	“Стрелка вверх”		X	“Вниз-влево-накрест”
	V	“Стрелка вниз”		Y	“Вниз-вправо-накрест”

3.4 Системные требования

Данная программа разработана для работы под операционной системой класс Microsoft Windows 98/NT/2000/XP/2003 при наличии необходимого программного и аппаратного комплекса, указанного ниже:

а) аппаратные требования:

- минимальные требования - Intel Celeron 400 МГц или совместимый процессор, 64 Мб оперативной памяти, 5 Мб свободного места на жестком диске, VGA видео карта;

- рекомендуемые - Intel Pentium 1000 МГц или аналогичный процессор, 128 Мб оперативной памяти, SVGA видео карта.

б) требования к программному обеспечению:

- операционная система Microsoft Windows 98/NT/2000/XP/2003.

3.5 Инсталляция программы

Разработанное приложение включает в себя единственный исполняемый модуль “exeCute.exe”, имеющий размер 98304 байт, а также файл конфигурации “exeCute.dat”. Программа не требует никакой инсталляции: ее запуск возможен с любого носителя. Для регулярного использования программы достаточно скопировать файлы “exeCute.exe” и “exeCute.dat” в любой каталог жесткого диска компьютера.

3.6 Запуск программы

Запуск программы осуществляется путем запуска исполняемого модуля “exeCute.exe”.

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

Для того чтобы приложение автоматически запускалось при загрузке операционной системы, можно выполнить следующие действия:

- создать ярлык для исполняемого файла программы и поместить его в папку Startup (Автозагрузка) Windows;

- добавить к ключу

[KEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\