Московский государственный университет имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Магистерская программа «Программное обеспечение вычислительных сетей»

Магистерская диссертация

Распознавание жестов и обмен данными между

мобильными устройствами

Работу выполнил:

студент Пестов Евгений Александрович Научный руководитель:

с.н.с. к.ф.-м.н Намиот Дмитрий Евгеньевич Подпись научного руководителя:

Москва 2013 Аннотация Развитие мощностей мобильных устройств позволяет предвосхитить появление новых интерфейсов взаимодействия пользователя и устройства. Одним из таких новых вариантов взаимодействия является управление функциями мобильного устройства с помощью движения им в пространстве.

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

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

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

Содержание Аннотация

Введение

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

1. Обзор известных методов и средств решения проблемы

1.1 uWave

1.1.1 Описание работы алгоритма

1.2 Алгоритмы, используемые в областях распознавания

1.3. Выводы

2. Исследование и построение решения

2.1 Скрытые Модели Маркова

2.1.1 Цепи Маркова

2.1.2 Определение скрытой модели Маркова

2.1.3 Выбор модели для акселерометра

2.1.4 Задача оценки

2.1.5 Задача декодирования

2.1.6 Задача обучения

2.2 Распознавание жестов с использованием метода опорных векторов......... 2.2.1 Разбиение жеста на фреймы

2.2.2 Характеристики одного фрейма

2.2.3 Классификация с использованием метода опорных векторов............. 2.3 Устранение погрешностей акселерометра

2.3.1 Метод средних значений

2.3.2 Фильтрация данных

2.4 Выводы

3. Описание практической части

3.1 Особенности реализации скрытых моделей Маркова

3.1.1 Первоначальные оценки

3.1.2 Топология модели слева-направо

3.1.3 Представление вероятностей

3.1.4 Моделирование продолжительности

3.2 Реализация приложения

3.2.1 Технические средства

3.2.2 Модуль распознавания жеста

3.2.3 Результаты тестирования

3.4 Дальнейшее развитие

Заключение

Библиография

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

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

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

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

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

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

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

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

Под словосочетанием «движение устройством» в контексте данной работы следует понимать физическое перемещение устройства в пространстве. Под термином «жест» - заранее предопределенное движение (например, движение по кругу по часовой стрелке), которое подлежит детектированию.

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

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

В пределах исследования необходимо:

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

2. Рассмотреть основные сложности задачи распознавания, найти оптимальные способы решения.

3. Реализовать мобильное приложение способное распознавать жесты мобильным устройством.

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

1. Обзор известных методов и средств решения проблемы Помимо поиска известных средств решения задачи, был произведен поиск приложений, хотя бы частично решающих поставленную задачу. Таких приложений найдено не было.

1.1 uWave uWave – алгоритм распознавания движения разработанный ЧиЯнгом Ли, Чен Вангом и Лин Чонгом, сотрудниками Инженерного Департамента университета в Хьюстоне. Алгоритм использует только показания акселерометра[1], поэтому может быть реализован на любом устройстве с этим датчиком. Подход, описанный в статье [2], по словам авторов алгоритма, позволяет с точностью до 98% детектировать совершённый жест. Авторы выделили восемь жестов (Рис.1.) и собрали библиотеку данных воспроизведения (свыше 4000 записей) этих базовых жестов разными людьми в течение продолжительного периода.

1.1.1 Описание работы алгоритма Работа алгоритма uWave состоит из трех этапов: квантование данных акселерометра, поиск соответствующего шаблона движения и адаптация шаблонов (Рис. 2.).

Работа алгоритма начинается с этапа квантования, в пределах которого данные акселерометра подвергаются фильтрации и квантованию. Таким образом, резко уменьшается количество обрабатываемых данных, что позволяет производить вычисления в условиях ограниченных ресурсов, как в случае с мобильным устройством. Авторы используют 32 уровня квантования, причем применена нелинейная схема распределения уровней. Так для колебаний в диапазоне от до g выделено 10 уровней квантования, для диапазона от g до 2g выделено уровней, значения большие 2g находятся на одном уровне. Такое распределение авторы объясняют высокой частотой возникновения значений акселерометра в диапазоне от 0 до g и очень низкой частотой появления значений в районе 2g и больших.

Рис. 2 Схема работы алгоритма uWave.

Ядром алгоритма uWave является другой алгоритм, в английской литературе имеющий название «Dynamic Time Warping» (Динамическая Трансформация Шкалы Времени, перев. авт.)[4][5]. Данный алгоритм позволяет измерить степень похожести двух последовательностей данных, которые могут отличаться друг от друга скоростью изменения данных. С помощью алгоритма DTW, можно выявить схожесть между видеозаписями, в одной из которых человек шагает с одной скоростью, а в другой – в два раза большей. DTW часто используется в распознавании речи, в обработке видео, аудио и другой информации, представимой в виде последовательности сравнимых объектов.

Алгоритм DTW в своей реализации находит расстояние Левенштейна двух последовательностей, в данном случае показателей акселерометра для эталонного жеста и показателей акселерометра для воспроизведенного жеста.

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

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

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

a) Использование вероятностных моделей, описывающих объект распознавания.

b) Извлечение ключевых характеристик входных данных (обучающей выборки) и классификация этих характеристик.

Широкое применение в рассмотренных работах [9][14][15][17] нашли скрытые модели Маркова, позволяющие представлять некоторую обучающую последовательность данных в виде вероятностной модели. Обращаясь к такой «обученной» модели, можно выяснить с какой вероятностью является текущая наблюдаемая последовательность данных «подходящей» для этой модели.

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

Помимо скрытых моделей Маркова, в работах по распознаванию часто используется другой классификатор – метод опорных векторов[20][21]. Суть метода заключается в том, что данные представляются в многомерном пространстве и классифицируются с помощью гиперплоскостей.

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

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

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

2. Исследование и построение решения 2.1 Скрытые Модели Маркова Статистические методы Маркова или скрытые Марковские модели появились и были изучены на стыке 1960-х и 1970-х годов, но стали повсеместно использоваться только в последнее десятилетие. Их популярность объясняется двумя причинами. Во-первых, скрытые модели Маркова имеют богатую математическую структуру, и потому становится возможным сформировать теоретический базис для широкого круга задач. Во-вторых, правильно применённые модели показывают очень высокие результаты на практике.

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

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

задачу оценки, задачу декодирования и задачу обучения.

2.1.1 Цепи Маркова Пусть – последовательность случайных переменных конечного первого порядка, если:

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

То есть, для цепи Маркова первого порядка, уравнение будет иметь следующий вид:

Если отбросить временной индекс, цепь Маркова может быть использована для моделирования событий независимых от времени:

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

2.1.2 Определение скрытой модели Маркова Скрытая модель Маркова – это множество состояний, соединённых переходами.

Каждое состояние характеризуется двумя множествами вероятностей:

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

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

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

Формально, скрытая модель Маркова определяется следующими параметрами:

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

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

перехода из состояния в состояние, т.е.

} – матрица вероятностей для наблюдаемых значений, где – вероятность появления символа из состояния, т.е.

{ } – распределение вероятностей начального состояния, где Так как всё вышеперечисленное – вероятности, то они должны удовлетворять следующим уравнениям:

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

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

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

В выборе непрерывных функций распределения вероятностей главными кандидатами являются функции мультивариативной Гауссовой смеси[11][12][13], благодаря возможности аппроксимации любых функций распределения вероятностей. C использованием распределяющих функций Гауссовой смеси, функция принимает вид:

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

Смесь должна удовлетворять следующему стохастическому ограничению:

Таким образом, функция распределения вероятности нормализована должным образом, т.е.

2.1.3 Выбор модели для акселерометра Практическая модель зависит от источника, который посылает сигнал.

Акселерометр имеет три оси, таким образом, выходное значение предстаёт в виде вектора из трёх значений:

Вектор математических ожиданий:

Ковариационная матрица:

Формула для вычисления определителя матрицы ковариации:

Формула для вычисления обратной матрицы для матрицы ковариации:

2.1.4 Задача оценки Задача – определить – вероятность появления последовательности в 2.1.4.1 Метод прямого и обратного хода Рассмотрим следующую переменную можно найти значение Инициализация:

Индукция:

Решение:

Вообще говоря, для решения проблемы оценки необходима лишь «прямая»

часть метода прямого обратного хода. Однако «обратная» часть используется для решения задачи обучения, поэтому также приведена.

Рассмотрим «обратную» переменную, определённую следующим образом:

т.е. вероятность частичного наблюдения последовательности в состоянии в момент времени для данной модели. Снова применим метод индукции:

Инициализация:

Индукция:

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

максимально соответствующую наблюдению.

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

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

Инициализация:

Индукция:

Решение:

Последовательность:

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

2.1.6.1 Алгоритм Баума-Велша Перед тем как описать процедуру переоценки (итеративного обновления и улучшения) параметров скрытой модели Маркова, необходимо определить – вероятность нахождения модели в состоянии в момент времени, и в состоянии в момент времени, для данной модели и наблюдаемой последовательности, т.е.

знаменатель как раз и даёт искомую вероятность.

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

параметров скрытой модели Маркова:

В непрерывном случае:

2.2 Распознавание жестов с использованием метода опорных векторов Подход к распознаванию жеста с использованием метода опорных векторов[20] заключается в том, чтобы представить жест некоторым набором ключевых классификации. Сначала производится разбиение данных на пересекающиеся отрезки – фреймы[22][23]. Далее из каждого фрейма производится извлечение характеристик, из которых формируется вектор значений, определяющий жест.

После этого происходит классификация жеста с помощью метода опорных векторов.

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

последовательности, количество измерений.

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

перекрывают друг друга одним сегментом.

одного фрейма одноосевого жеста. Чтобы учесть все три оси, нужно объединить представить жест так:

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

2.2.2 Характеристики одного фрейма Согласно теории обработки сигналов, частотные характеристики дают достаточно подробную информацию о сигнале. Поэтому в набор характеристик описывающих фрейм должны быть включены не только временные, но и спектральные характеристики. В качестве определяющего набора[22] были выбраны частотные характеристики: математическое ожидание, энергия и энтропия и две временные характеристики: стандартное отклонение амплитуды и корреляция значений по осям:

Для получения частотных характеристик, необходимо сначала применить дискретное преобразование Фурье на каждый фрейм оси, чтобы получить спектральное представление жеста:

Далее, можно извлекать из данных фрейма три спектральные характеристики:

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

Энергия – это сумма квадратов всех компонентов дискретного преобразования Фурье. Сумма этих компонентов делится на количество компонентов в целях нормализации.

Энтропия – нормализованная информационная энтропия компонентов дискретного преобразования Фурье:

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

Корреляция представляет силу линейной связи между сигналами двух осей:

2.2.3 Классификация с использованием метода опорных векторов Метод опорных векторов – метод классификации, использующий теорию статистического обучения. Данный метод хорошо справляется с задачами нелинейной классификации и регрессии. Метод опорных векторов широко классификация, идентификация лиц, распознавание активности. В условии ограниченного набора обучающих данных, метод опорных векторов обычно превосходит традиционные методы оценки параметров, построенные на законе больших чисел. Первоначально, метод опорных векторов использовался для решения задач бинарной классификации, то есть для поиска максимально удалённой от точек двух классов гиперплоскости, разделяющей эти два класса.

Пусть два типа жестов GTR1 и GTR2 должны быть классифицированы.

Определим набор из n тренировочных данных:

где – вектор характеристик и Разделяющая гиперплоскость записывается так:

Двойственное представление задачи максимизации удалённости плоскости:

что:

классификации имеет вид:

где и - оптимальные решения задачи оптимизации.

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

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

2.3 Устранение погрешностей акселерометра Показания акселерометра на мобильных устройствах подвержены достаточно сильному шуму. Зашумленность порой достигает 0.08g, вследствие этого возникает острая необходимость борьбы с шумом. Ниже будут рассмотрены несколько подходов к сглаживанию и фильтрации данных акселерометра[3].

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

-0, -0, -0, -1, -1, -1, 2.3.1 Метод средних значений Метод средних значений – один из самых простых методов фильтрации шума, суть его такова: на каждом шаге k, значение вычисляется как среднее из n предыдущих значений акселерометра, то есть. Такой метод дает, при средних значениях n, неплохое сглаживание, но имеет один существенный недостаток – достаточно большую задержку в значениях.

-0, -0, -0, -1, -1, -1, 2.3.2 Фильтрация данных Одним из способов борьбы с зашумленными данными является применение фильтра. Задача распознавания движения устройством накладывает одно существенное требование к фильтру – требование производительности достаточной для того, чтобы использовать фильтр в режиме реального времени с минимальными задержками. Конечно, большим плюсом фильтра является приближенность значений к начальным.

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

Самый простой фильтр низких частот описывается следующей формулой:

On = On-1 + (In – On-1), где O – выходное значение сигнала (отфильтрованное), In – входные значения (нефильтрованные), – коэффициент фильтрации, принимающий значения от 0 до 1. При равном 1, выходные значения совпадают с входными.

В качестве примера, ниже приводятся два варианта фильтрованных с помощью фильтра нижних частот данных с коэффициентом = 0.5 и = 0.25, соответственно.

-0, -0, -0, -1, -1, -1, -0, -0, -0, -1, -1, -1, Как видно из примеров меньший коэффициент дает более гладкий результат.

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

2.3.2.2 Модифицированный фильтр низких частот Для уменьшения задержки сглаживания при резких колебаниях необходимо ввести зависимость фильтра от приращения n-го и n-1-го значения сигнала.

фильтруется вышеописанным фильтром нижних частот, иначе – возвращается входное значение.

-0, -0, -0, -1, -1, -1, Показания Акселерометра Оптимизированный Фильтр Низких Частот Как видно из представленного графика, на резких перепадах задержка сведена к минимуму, при этом сглаживание вполне неплохое.

2.3.2.3 Фильтр Калмана Фильтр Калмана часто используется для фильтрации значений различного рода сигналов, его можно встретить в GPS-приемниках, обработчиках показаний датчиков и т.д. Фильтр Калмана является разновидностью рекурсивных фильтров. Для вычисления оценки состояния системы на текущий шаг работы ему необходима оценка состояния (в виде оценки состояния системы и оценки погрешности определения этого состояния) на предыдущем шаге работы и измерения на текущем шаге. Далее под записью будем понимать оценку истинного вектора в момент n с учетом измерений с момента начала работы и по момент m включительно.

Состояние фильтра задается двумя переменными:

— апостериорная оценка состояния объекта в момент k полученная по результатам наблюдений вплоть до момента k включительно;

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

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

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

2.3.2.3.1 Этап экстраполяции Экстраполяция (предсказание) вектора состояния системы по оценке вектора состояния и примененному вектору управления с шага (k1) на шаг k:

Ковариационная матрица для экстраполированного вектора состояния:

2.3.2.3.2 Этап коррекции Отклонение полученного на шаге k наблюдения от наблюдения, ожидаемого при произведенной экстраполяции:

Ковариационная матрица для вектора отклонения (вектора ошибки):

Оптимальная по Калману матрица коэффициентов усиления, формирующаяся на основании ковариационных матриц имеющейся экстраполяции вектора состояния и полученных измерений (посредством ковариационной матрицы вектора отклонения):

Коррекция ранее полученной экстраполяции вектора состояния — получение оценки вектора состояния системы:

Расчет ковариационной матрицы для оценки вектора состояния системы:

Выражение для ковариационной матрицы оценки вектора состояния системы справедливо только при использовании приведенного оптимального вектора коэффициентов.

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

Рассмотрим значения переменных фильтра применительно к данным акселерометра:

F – переменной, описывающей динамику системы присвоится значение 1, что означает, что экстраполируемое значение будет равно значению на предыдущем шаге.

B – переменная, определяющая применение управляющего воздействия, примет значение 0, ввиду отсутствия такового.

H – матрица, определяющая отношение между измерениями и состоянием системы, в случае с данными с акселерометра примет единичный вид.

На графике изображен один из вариантов фильтра Калмана примененный к данным полученным акселерометра.

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

1. Высокая точность распознавания. Точность распознавания обоих алгоритмов колеблется от 90% до 98% [14][22] на небольшом количестве 2. Производительность распознавания скрытых моделей Маркова выше, чем у подхода с использованием метода опорных векторов, в связи с тем, что нет необходимости извлекать дополнительные характеристики сигнала.

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

4. Возможность проводить распознавание в реальном времени присутствует в обоих алгоритмах, однако подход, использующий СММ, обладает большей гибкостью за счёт возможности использования произвольного классификатора статических и динамических наблюдений.

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

3. Описание практической части 3.1 Особенности реализации скрытых моделей Маркова Несмотря на то, что задачи скрытых моделей Маркова рассмотрены, реализовать алгоритм и добиться его корректной работы в том виде, в котором он описан, не представляется возможным. Необходимо прибегнуть к некоторым упрощениям.

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

3.1.2 Топология модели слева-направо Жест – нестационарный во времени сигнал. Каждое состояние СММ имеет возможность отразить квази-стационарный сегмент в нестационарном сигнале движения. Топология «слева направо» является естественным кандидатом моделирования сигнала акселерометра. Каждое состояние в этой топологии имеет переход в само себя, который может использоваться для моделирования похожих элементов движения принадлежащих одному состоянию. Когда квазистационарный сегмент жеста изменяется, переход слева направо позволяет естественно продолжить это изменение. В такой топологии, каждое состояние имеет зависимое от состояния распределение вероятности результирующего значения, которое используется для интерпретации наблюдаемого сигнала. Эта топология является одной из самых популярных структур скрытых моделей Маркова, используемых в системах распознавания речи.

Фундаментальным свойством всех СММ построенных по топологии «слева направо» является то, что коэффициенты переходов между состояниями удовлетворяют следующим требованиям:

т.е. запрещены переходы в предыдущие состояния.

Более того, вероятности начального состояния имеют следующие свойства:

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

В частности, при матрица переходов выглядит так:

Вполне очевидно, что для последнего состояния в модели «слева направо»

коэффициенты переходов имеют вид:

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

Переменная прямого прохода должна быть умножена на коэффициент :

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

Коэффициент для переменной :

Уравнение:

Отмасштабированная промежуточная вероятность :

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

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

3.1.4 Моделирование продолжительности Большим недостатком традиционных скрытых моделей Маркова является отсутствие адекватного представления временной структуры движения. Так как вероятность пребывания в состоянии уменьшается экспоненциально со временем:

вероятность последовательных наблюдений в состоянии – это вероятность прохода по петлевому переходу в -тое состояние раз.

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

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

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

Пусть имеются два мобильных устройства A и B, с установленным приложением, и библиотека скрытых моделей Маркова, каждая из которых имеет название, соответствующее жесту, который она определяет. Общая схема взаимодействия устройств такова:

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

Функциональность описанного приложения может быть разделена на два модуля:

1. Модуль распознавания жеста.

2. Модуль связи с другим устройством.

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

Устройство модуля распознавания будет рассмотрено более подробно.

3.2.1 Технические средства Принципиальных критериев выбора той или иной мобильной платформы для реализации приложения нет, так как средства работы с акселерометром присутствуют во всех современных популярных платформах. Поэтому была выбрана платформа Windows Phone[6], как наиболее знакомая автору.

Проект реализован на языке C#, в среде Visual Studio 2012. Также использованы другие.Net технологии, такие как Silverlight for Windows Phone[25] и Windows Communication Foundation(WCF)[24].

В проекте используется исходный код следующих открытых библиотек математических функций и алгоритмов машинного обучения: AForge.NET [26] и Accord.Net[27].

3.2.2 Модуль распознавания жеста Ниже приведена общая схема работы модуля распознавания жеста:

Массив обработанных векторов (x, y, z) Вероятности того, что движение является жестом Возвращение результата Модуль получает на вход данные акселерометра и в качестве результата возвращает класс жестов, которому соответствуют входные данные, либо ошибку несоответствия.

Первым шагом работы модуля является обработка полученных массивов векторов, с помощью алгоритма фильтрации. Далее, обработанные данные передаются классификатору, который имеет в своём распоряжении список скрытых моделей Маркова, предварительно обученных и соответствующих некоторому классу жестов[16]. Результатом работы классификатора являются вероятностные значения того, что поданный на вход жест соответствует СММ описывающей конкретный класс жестов. Следующий блок, принимая набор вероятностей, в самом простом случае отдаёт предпочтение модели, показывающей наибольшую вероятность, опционально обновляет соответствующую скрытую модель Маркова и возвращает класс жестов, связанный с этой моделью.

Далее приведена краткая UML-диаграмма классов для модуля распознавания жестов:

3.2.3 Результаты тестирования После успешной реализации модуля распознавания жестов, было проведено тестирование точности распознавания. Для тестирования использовались четыре жеста – круговое движение по часовой стрелке, движение квадрат, движение треугольник и движение в форме латинской буквы Z. Обучающая выборка для каждого жеста состояла из 10 повторений сделанных двумя людьми по 5 каждый, с промежутком между повторениями в две минуты.

Во время тестирования помимо указанных жестов было введено «ложное движение» - полукруг по часовой стрелке. Жесты выполнялись по очереди один за другим, всего было проведено 5 таких серий разными людьми, не принимающими участия в обучении.

Успешно было распознано 23 движения из 25. То есть точность распознавания достигла 92%, что вполне соответствует средней точности подхода, использующего скрытые модели Маркова.

Средняя скорость распознавания жеста на таком наборе данных, на мобильном устройстве Nokia Lumia 900, составила примерно 1.2 сек.

3.4 Дальнейшее развитие Хотя полученные характеристики распознавания достаточно неплохие, остаётся большое пространство для их улучшения.

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

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

Заключение Основной задачей работы ставилась задача исследовать возможность распознавания движения мобильным устройством, используя данные акселерометра. При обзоре существующих решений был найден подход решающий эту задачу – uWave. Алгоритм uWave использует только данные акселерометра и основан на нахождении расстояния Левенштейна между двумя последовательностями данных. Хотя, на первый взгляд, алгоритм полностью решает поставленную задачу, в процессе его исследования выявились серьёзные ограничения, что послужило стимулом детального исследования других алгоритмов распознавания в смежных областях.

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

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

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

Работа выполнялась в Лаборатории Открытых Информационных Технологий факультета ВМК МГУ им. М.В. Ломоносова [28] Библиография [1] Liu J. et al. User evaluation of lightweight user authentication with a single triaxis accelerometer //Proceedings of the 11th International Conference on Human-Computer Interaction with Mobile Devices and Services. – ACM, [2] Liu J. et al. uWave: Accelerometer-based personalized gesture recognition and its applications //Pervasive and Mobile Computing. – 2009. – Т. 5. – №. 6. – С.

657-675.

[3] Jang I. J., Park W. B. Signal processing of the accelerometer for gesture awareness on handheld devices //Robot and Human Interactive Communication, 2003. Proceedings. ROMAN 2003. The 12th IEEE International Workshop on. – IEEE, 2003. – С. 139-144.

[4] Berndt D. J., Clifford J. Using Dynamic Time Warping to Find Patterns in Time Series //KDD workshop. – 1994. – Т. 10. – №. 16. – С. 359-370.

[5] Senin P. Dynamic time warping algorithm review //Honolulu, USA. – 2008.

[6] Using the Accelerometer on Windows Phone 7. URL:

http://windowsteamblog.com/windows_phone/b/wpdev/archive/2010/09/08/usi ng-the-accelerometer-on-windows-phone-7.aspx [7] Пестов Е. Распознавание движения мобильного устройства //International Journal of Open Information Technologies. – 2013. – Т. 1. – №. 3. – С. 5-10.

[8] Николенко С. Скрытые марковские модели. URL:

http://www.compsciclub.ru/csclub/sites/default/files/slides/20080420_machine _learning_nikolenko_lecture10.pdf [9] Гефке Д., Зацепин П. Применение скрытых марковских моделей для распознавания звуковых последовательностей //Известия АГУ. – 2012. – №1-2(73).

[10] Borza P. V. Motion-based Gesture Recognition with an Accelerometer :

дис. – Master’s thesis, Babes-Bolyai University, Faculty of Mathematics and Computer Science, 2008.

[11] Vasconcelos N. The Gaussian classifier. URL:

http://www.svcl.ucsd.edu/courses/ece271A-F08/handouts/GC.pdf [12] Gaussian Classifiers. URL: http://luthuli.cs.uiuc.edu/~daf/courses/CSDAF-PS/Lecture%206%20-%20Gaussian%20Classifiers.pdf [13] Gaussian Mixture Models and Expectation-Maximization. URL:

http://crsouza.blogspot.ru/2010/10/gaussian-mixture-models-andexpectation.html [14] Rolin J. et al. Hidden Markov Models and Their Mixtures //DEA Report, Dep. of Mathematics, Universit catholique de Louvain. – 1996.

Borza P. V. Recognizing Physical Exercises : дис. – Master’s thesis, [15] Babes-Bolyai University, Faculty of Mathematics and Computer Science, 2010.

[16] Pettersson G., Tysk J., Vallgren H. Conversion of Hidden Markov Model computation to C#, Uppsala University. – 2013.

[17] Joshi D., Li J., Wang J. Z. A computationally efficient approach to the estimation of two-and three-dimensional hidden Markov models //Image Processing, IEEE Transactions on. – 2006. – Т. 15. – №. 7. – С. 1871-1886.

[18] Liu J., Pan Z., Xiangcheng L. An accelerometer-based gesture recognition algorithm and its application for 3d interaction //Computer Science and Information Systems. – 2010. – Т. 7. – №. 1. – С. 177-188.

Akl A., Feng C., Valaee S. A novel accelerometer-based gesture [19] recognition system //Signal Processing, IEEE Transactions on. – 2011. – Т.

59. – №. 12. – С. 6197-6205.

Лифшиц Ю. Метод опорных векторов. URL:

[20] http://logic.pdmi.ras.ru/~yura/internet/07ia.pdf [21] Patil M. A. R., Subbaraman S. S. A Review On Vision Based Hand Gesture Recognition Approach Using Support Vector Machines.

[22] He Z. Accelerometer based gesture recognition using fusion features and SVM //Journal of Software. – 2011. – Т. 6. – №. 6. – С. 1042-1049.

[23] Wu J. et al. Gesture recognition with a 3-d accelerometer //Ubiquitous intelligence and computing. – Springer Berlin Heidelberg, 2009. – С. 25-38.

[24] Consume WCF service with Windows Phone 7 Application. URL:

http://beyondrelational.com/modules/12/tutorials/382/tutorials/7684/gettingstarted-with-windows-phone-7-part-6-consume-wcf-service-with-windowsphone-7-application.aspx Уилдермут. Ш., Основы Windows Phone 7.5. Разработка приложений [25] с помощью Silverlight. ДМК-Пресс, 2012.

[26] AForge.NET Framework. URL: http://www.aforgenet.com/ [27] Accord.NET Framework. URL: http://accord-framework.net/ Намиот Д., Сухомлин В. О проектах лаборатории ОИТ //International [28] Journal of Open Information Technologies. – 2013. – Т. 1. – №. 5. – С. 18-21.