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

На правах рукописи

Пономарев Дмитрий Иванович

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

Специальность 05.13.17-Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

005543952 1 2 ДЕК 2013

МОСКВА-2013

005543952

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Московский физико-технический институт (государственный университет)».

Научный руководитель: кандидат физико-математических наук, доцент,

Кухаренко Борис Георгиевич Официальные оппоненты: доктор технических наук,

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук Защита диссертации состоится «26» декабря 2013 года в 13 ч. 00 мин. на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук по адресу: 119333, г.Москва, ул.Вавилова, д.40. С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан «22» ноября 2013 года Ученый секретарь диссертационного совета

Кольцов Петр Петрович,

заместитель директора НИИСИ РАН по науке.

кандидат технических наук, Выголов Олег Вячеславович,

начальник лаборатории ФГУП «Государственный научно-исследовательский институт авиационных систем» (ФГУП

ГосНИИАС").

Д 002.017.02, д.ф.-м.н., профессор

В.В. Рязанов

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

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

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

2. выявление на основе моделей требуемых характеристик вычислительных алгоритмов и комплексов программ;

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

Методы исследования. В работе используются: линейная и нелинейная Байесовская фильтрация, фильтр Калмана, скрытая Марковская модель, EM-алгоритм, спектральный метод Прони, алгоритм динамического искажения времени, алгоритмы поиска повторяющихся последовательностей, алгоритм Mueen-Keogh Motif Discovery, абстракция данных, алгоритм k-means, k-means++, алгоритмы поиска повторяющихся эпизодов, анализ независимых компонент, кластеризация на основе ЕМ-алгоритма.

Научная новизна полученных результатов. Научная новизна диссертационного исследования состоит в следующем:

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

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

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

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

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

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

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

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

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

4. Метод сокращения размерности временных рядов на основе анализа независимых компонент при поиске паттернов в результате абстракции данных.

Апробация работы. Основные результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих конференциях: 53, 54, 55 научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2010,2011, 2012), научных семинарах институтов РАН.

Доклады на 53 и 54 научных конференциях МФТИ, как лучшие в секции, были отмечены дипломами победителя.

Публикации. Основные положение работы отражены в 16 публикация, в том числе 7 [2-3,5-9], в журналах из списка, рекомендованного ВАК РФ.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка использованных источников, включающего 73 наименования. Общий объём работы составляет 107 страниц.

Краткое содержание работы

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

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

Во второй главе рассматривается задача фильтрации управляющих сигналов манипулятора и ее решение при помощи нелинейной Байесовской фильтрации. Приводится обзор существующих методов решения данной задачи, а также их основные достоинства и недостатки. Показано, что наибольший вклад в шум управляющего сигнала манипулятора вносит процесс физиологического дрожания руки оператора, получены амплитудные и частотные характеристики шума. Также показано, насколько существенным является решение данной задачи для работы такого класса манипуляторов. Для решения задачи фильтрации применяется нелинейная фильтрация по Калману. При построении фильтра Калмана задается нелинейная модель динамической системы. В настоящей работе используется ЕМ-алгоритм (Expectation-Maximization algorithm) для оценки параметров нелинейной динамической модели фильтра Калмана. Это позволяет не задавать модель априори, а оценивать ее параметры на основе реальных данных.

В фильтре Калмана дискретная линейная динамическая система (ЛДС) описывается

динамической системы осуществляется алгоритмом ожидания и максимизации правдоподобия (Expectation Maximization (ЕМ) algorithm).

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

x[4 + l] = F[fc + l]x[/t] + w[A] у[А] = Н[Л]х[А] + v[A].

Оценка параметров линейной

L = log />( {x}, {y}) ■=Д(у [*] •- Hx[*])r R"1 (y [*] - Hx[*]))

4-1 2

-^log IRI (-i(x[A] - Fx[A - l])r Q-' (x[k}~ Fx[k -1]))

2 i=2 2

_ log IQI - I(x[l] - тг[1])г V[l]"' (x[l] - яП])

-^g|vmi-M£±íllog2,

где R - ковариационная матрица шума измерений, Q - ковариационная матрица шума динамической модели.

E-шаг, рассматриваемого ЕМ-алгоритма, предполагает вычисление ожидаемого логарифма правдоподобия L = £[log/>({*KO'})l ÍJ'}] - Для этого при помощи сглаживающего фильтра Калмана вычисляются следующие математические ожидания: £'[x[¿]|{y}], Е[х[к](х[к])т |{у}], £[хМ(х[*-1])г |{у}].

Опишем М-шаг. Параметры линейной динамической системы F,H,R,Q,jr[l],V[l]

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

II " = (£ у[*](ВД)г )(£ 1ВДГ1. R"™ = ^-5>Г*](УМ)г - Н"~х[*](у[*])г),

4.1 4.1 " 4.1

F~ = (£ 1>М)(£Щ-1])-', Q"~ = ВД-F-V[k-l][i]),

4=2 4-2 " -1 4.2 4=2

я[1Г" =x[l],V[ir" =P[l]-x[l](x[l])T .

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

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

х[* +1] * f (х[А], u[k]) + F-(i| ■ (x[i] - x w) + wW,

_ . Функции fug определяются на основе

У W » иВД) + Gi|t, • (x[A]~ x[t]) + v[i]

/

радиальных базисных функций: z = ]Th[i] p, (x) +A-x + B u + b +w, где w- Гауссов шум с

(=i

нулевым средним значением и ковариационной матрицей Q, р, (х) - радиальная базисная функция. Радиальная базисная функция имеет вид:

д (х) = |27tS[/]|~"2 ехр(-1(х-ф])Г (S[i])~' (x-c[i])j. Предполагается, что:

/>(x,z,u) = —^<рДх,г)<5(и-и[/']). Логарифм правдоподобия для одного измерения:

J i

-i(z-z, (x,u)) Q4 (z-z, (x,u))-ilog|Q[+c. Значения {x,z} не определены, поэтому

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

minjz J J4 (*•z)'[z~г< (х> u)f Q"' (z(х-"))сЫг + JIo§|Q||•

Используя обозначения: 0 = [h[l],...,h[/],A,B,b] и Ф = [р, (х),...,р, (x),xr,ur,lj .получаем выражение для задачи минимизации: min jtr^Q~'^|(z-8®)(z-6®)ry j + yiog|Q||.

Приравнивая производные по 9 нулю, получим линейные уравнения относительно в и Q. Для повышения эффективности нелинейной Байесовской фильтрации сигнала удаленного манипулятора необходимо увеличить размерность наблюдаемой последовательности. Это достигается добавлением к наблюдаемой последовательности у ее первой разности Ду. Двумерный временной ряд Y = {у; Ду} обеспечивает Байесовскую нелинейную фильтрацию при размерности пространства состояний L = 4. В качестве критерия близости компонент, определенных в результате нелинейной Байесовской фильтрации, к исходному сигналу используется их кросс-корреляция без запаздывания. Применяемый в данной работе алгоритм фильтрации приведен в таблице 1.

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

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

2. Построение двумерного вектора на основе одномерного Y = {у; Ау}г с использованием первой разности

3. Оценка параметров линейной динамической системы при помощи ЕМ-алгоритма, которые будут использованы как начальные значения при оценки параметров нелинейной динамической модели. Обучение модели происходит на двумерном векторе данных Y = {у; Ду}г

4. Оценка параметров нелинейной динамической системы при помощи ЕМ-алгоритма

5. Фильтрация данных при помощи расширенного фильтра Калмана (Extended Kaiman filter), модель для которого была построена на шаге (4).

Приводятся результаты фильтрации сигналов манипулятора полученные при помощи нелинейной Байесовской фильтрации (рис.1).

Рис.1. Пример фильтрации сигналов. Слева показан исходный сигнал, в центре первая разность, справа результат фильтрации.

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

9

Предполагается, что существует скрытая последовательность, z = каноническое

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

Вероятность перехода: Г*„ = р(.л: |тгу) = р(ф, \ ф^р(т/ |гу). Распределения вероятности

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

Для оценки параметров модели используется алгоритм ожидания и максимизации правдоподобия (EM-алгоритм). На Е-шаге используется алгоритм прямой и обратной рекурсии. На М-шаге оцениваются параметры модели. Логарифм правдоподобия К наблюдаемых временных рядов, х', задается выражением: LpsL + P, где L - логарифм правдоподобия в скрытой Марковской модели, и вычисляется посредством алгоритма прямой и обратной рекурсии, Р - логарифм правдоподобия отвечающий за априорные ограничения наложенные на модель. Выражения для составляющих логарифма правдоподобия:

L = £ ilog Р{я,) + ± log 4, tf I z) + ± log 71 ],

i-l 4 1.1 i-2 У

p s - )2+Z bgo« I {??*})+log ой. I {??;}).

j=\ A-l

Обозначим через S общее число возможных состояний, тогда ожидаемый полный логарифм правдоподобия:

< If >„= P + ±±rUtyogT0l + ±±±rk,Woi>A,tf\z)+...

к=I s=l 1 i=l 1=1

К S S N '

А=1 т-1 i=2

где T0ks = р(л, = s), y'(i) и ¿¡¡,.(0 ~~ условные вероятности, определенные посредством алгоритма прямой и обратной рекурсии. Оценки значений параметров модели получаются взятием производных по данным параметрам от математического ожидания логарифма правдоподобия и приравниваем их к нулю.

Сигналы, получаемые от двух независимых акселерометров, прошли процедуру выравнивания при помощи Марковской модели непрерывного профиля (рис. 2).

2 1 8 1.6 1.1 1 2 1

500 1000 1500 2000 2500 3000

Рис. 2. Записи управляющих сигналов, полученных при помощи двух независимых акселерометров.

После обучения модели при помощи алгоритма ожидания и максимизации правдоподобия произведена синхронизация сигналов при помощи алгоритма Витерби. Результат синхронизации сигналов изображен на рис. 3.

1.8 -

I

Рис. 3. Результат синхронизации управляющих сигналов.

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

временных рядах, являющимися записями управляющего сигнала манипулятора. Одним из

основных моментов при решении задачи обнаружения паттернов временного ряда является

11

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

Считается, что полный временной ряд имеет постоянный интервал

дискретизации времени. Для простоты приводимых формул этот интервал дискретизации времени &1 = 1. Последовательные сегменты фиксированной длины М « N « Л^ имеют

вид у,|\лг] = х£(Лф-1)+1),№^,1 = 1,гоипс1(Л'0/Л') (1). Таким образом, считается, что анализируемые сегменты имеют длину гораздо больше, чем длина паттернов, присутствующих в полном временном ряду Декомпозиция Прони сегмента (1) (для

краткости индекс сегмента / = 1,гоиги1(Лг0/Лг) ниже опускается) имеет вид:

я*]=1>и(-[/]Г=Ш .(2) /=1

где р — число определяемых полюсов сегмента временного ряда; г[/] = ехр(<?[/]+_/2л-/|7]),/ = \,р - полюса, которые определяются для сегмента (1), где <5[/] и У[/] соответственно, фактор демпфирования (логарифмический декремент) и частота; г[/] = а[/]ехр(Л?[/]),' = 1,р - вычеты в этих полюсах, где а[Г\ и <р[1\ - соответственно,

амплитуда и фаза; = - аддитивный шум. То есть метод Прони использует модель

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

тренд в переходном сегменте (1), в его декомпозиции (2) представляется

составляющими с низкими частотами порядка ДГ"1. После удаления среднего значения

у = — T.o.>{/t],ir = l.N -» (>'[&]->') Д = 1,ЛГ, либо удаления линейного или

нелинейного тренда y(iàt) в результате регрессии

jt(>'[']->'('A/))2 —> min

и преобразования у[к\к = \JÎ ^>(y{ï\-y(j&t)),k = \,N, для преобразованного сегмента y^Ûv] по методу Прони может быть определена одночастотная аппроксимация. Она соответствует минимальному числу р = 2 полюсов в (2). Частота /[1] = Imlog(r[l]) (и /[2] = -/[1]) определяет характерный период M = \//[\],(М « N « N0) колебательного изменения преобразованного сегмента Оцененный по всем последовательным

сегментам полного временного ряда jc[l,./V0], этот период А/ « Na дает временной масштаб при обнаружении совпадающих временных последовательностей (паттернов) временного ряда x[l,Ar0J.

Для обнаружения паттернов в оцененном временном масштабе используется алгоритм Mueen-Keogh (МК) Motif Discovery. Это алгоритм реализует поиск наиболее похожих последовательностей в наборе последовательностей D, представляющей собой неупорядоченный набор временных последовательностей одинаковой длины Dt = st, где k = l,2,..,N0-M + \.

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

13

последовательностей. Имеется также модификация данного алгоритма работающего в режиме реального времени. Алгоритм МК Motif Discovery, работающий в режиме реального времени, является основой программы, реализованной на языке С++, для поиска паттернов в управляющих сигналах манипулятора. Данная программа считывает данные, получаемые от манипулятора, через равные промежутки времени. Далее используется скользящее временное окно заданной длины L. Для сигнала в выбранном окне вычисляется одночастотная аппроксимация по методу Прони, результатом которой является характерный временной масштаб для поиска паттернов. Далее запускается версия алгоритма МК реального времени для поиска паттернов с вычисленным значением длины паттерна. Данная программа используется для выделения характерных жестов, которые формируются у оператора при управлении курсором компьютерной мыши, посредством разрабатываемого манипулятора. Желаемое перемещение курсора на экране компьютера приводит к поиску оператором необходимого жеста, его формированию и запоминанию для повторения. Алгоритм работы программы приведен в таблице 2. Программа выделяет наиболее часто встречаемые паттерны, возникающие при управлении данным манипулятором. На рис. 4 показаны примеры найденных паттернов.

Таблица 2. Разработанный алгоритм поиска паттернов в одномерных управляющих сигналах манипулятора.

1. Считывание новых данных x[Ni]

2. Формирование сегмента данных = +

3. Удаление линейного тренда из полученного сегмента данных

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

5. Поиск паттернов в полученном временном масштабе при помощи онлайн версии алгоритма МК Motif discovery.

Характерный вид паттерна Описание жеста

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

І і і Быстрое горизонтальное движение руки справа налево, с возвратом руки в исходное положение

Наклон руки влево, с возвратом в исходное положение

«. о * я » » ш

/ V / \ Наклон руки вправо,с возвратом в исходное положение

• 1>|»ХаЯХв«»Я

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

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

• Обнаружение повторяющихся эпизодов в полученной одномерной последовательности.

Рассмотрим решение задачи кластеризации при помощи ЕМ-алгоритма. Имеется набор данных {х[1],х[2],...,х[ЛГ]} состоящих из N наблюдений М-мерной случайной величины х .Требуется разбить набор входных данных на К кластеров.

Будем считать, что {х[н]} - выборка для смеси Гауссовых распределений. Если предположить, что вектор наблюдения х[и] принадлежит кластеру к, тогда функция

плотности вероятности для х[л] будет нормальным распределением со средним и

ковариационной матрицей R[¿]:

Р(*М I к, ц[*], R[*]) = — "JTTJ" IЩЧ Г"2 ехр{- 1(х[и] - ц[*])г К[*Г1 (*[п]" й[*])} ■ (2я-) 2

Введем скрытые переменные у[п]. Пусть {у[и]} - последовательность из N

дискретных независимых и одинаково распределенных случайных величин, с функцией

А"

распределения Р{у[п] = к} = л[к], где к = 1,...,К и = 1. Случайная величина у[п\

k= 1

показывает к какому кластеру принадлежит вектор наблюдения х[я], а вес п\К\ - это вероятность того, что выборка {х[и]} для смеси Гауссовых распределений представляет кластер к.

Функция плотности для вектора наблюдения х[я] имеет вид:

Pim 10) = z ТгВтГ I RW Гш ехр{- i(x[n] - ц[*])г R[*]-' (х[л] - |Х[А])Ь »=i Ця) 2

где вектор параметров распределения 8 = |>r[l],(i[l],R[l],...,/r[Ä'],(i[.K],R[Ä']].

На E-шаге алгоритма оценивается апостериорное распределение вероятностей скрытых

параметров:

г[п\к] = р(у[п] = к IX = х[и], б) =

-^L|R[A]|-"2 exp{-|(x[«]-ri*])rR[*r,Wn]-|i[ft])} (3)

(2л-) 2

На М-шаге максимизируется логарифм прадоподобия наблюдаемых данных, при фиксированном распределении скрытых параметров. Запишем выражение для ожидаемого логарифма правдоподобия наблюдаемых данных: ¿(8) = £-[logp(X,r|8)] =

¿ г[п- к] login Trär i rM Г"2 exP{- t(xW - f R[*r1 (*["] - ц[*])}) =

4.] (¿я) 2.

к N \ M (4)

£ £ Лъ *]{logM*]) - ilog(| R[*] |) -—log(2;r)

л.1 2 2

-1 Wn] - mf Щ*Г' №1 - MM)}

На М-шаге вектор параметров 0 повторно оценивается. Для этого берутся частные производные от ожидаемого логарифма правдоподобия (4), приравниваются к нулю и решаются аналитически полученные уравнения. Приведем полученные выражения:

№ = -• -я-. = -С)

!>[«;*] ЦФ«*]

1Г=1 П=1

Для того, чтобы получить соответствие между векторами наблюдений {х[л]} и кластерами, к которым они относится, необходимо вычислить логарифмы правдоподобия для каждого вектора наблюдений х[п], в предположении, что данные представляют собой

выборку для модели смеси гауссовых распределений с набором параметров Д[і], К[£], п[к]:

L[n-k] = log

i rm гш ехр{-і(х[»] - aw)7 ту (х[п] - ту,

• (6)

_(2/г) ' г 2'

Далее необходимо найти максимум логарифма правдоподобия (6) по к = 1..К, при фиксированном п. Значение к, при котором наблюдается максимум (6), является номером класса Е[п\, к которому относится данное наблюдение х[п]: £[«] = arg max L[n\k]. (7)

Таким образом, чтобы получить из последовательности векторов наблюдаемых данных {х[1],х[2],...,х[ЛЧ} последовательность меток кластеров {£[1], £[2],..., £[//]}, выполним следующее:

1. Инициализируем необходимое количество кластеров К

2. Задаем начальные значения параметров R[A], п[к\

3. Выполняем Е-шаг EM-алгоритма (3).

4. Вычисляем ожидаемый логарифм правдоподобия (4)

5. Вычисляем параметр р = ———, где Ls - ожидаемый логарифм правдоподобия

- А

полученный на шагеs. В случае если p<l + d, гдеd-заранеезадаваемый параметр, то принимается решение о прекращении выполнения EM-алгоритма и переходим к шагу 7.

6. Выполняем М-шаг ЕМ-алгоритма (5), в результате получаем оценки параметров А[Л], R[A], ñ[k]

Далее переходим к шагу 3, для выполнения новой итерации алгоритма.

7. Вычисляем L[tr,k\ (6)

8. Получаем последовательность {E[1],£[2],...,£[N]} (7)

В результате многомерный временной ряд дискретно представляется как последовательность событий (l<E¡,t¡),(E1,íl),...,^ENii,tKt^ (N0 - число элементов для

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

В каждом событии (Ent¡),i = \,N0, обозначает тип события, a t, - время, когда происходит событие. Типы событий выбираются из конечного набора.

Последовательность событий упорядочена относительно времени возникновения каждого события, т.е. V/ = 1,jV0-1,/,. </,tl. Эпизод а - триплет (Уа,где Va - набор узлов, <а -частичный порядок на Va, и ga: -> Е - отображение, ассоциирующее каждый узел с типом событий. Интерпретация эпизода в том, что события в ga(Va) должны происходить в порядке, описываемом посредством <а. Размер а, обозначаемый как |а|, является \Уа\. Эпизод а является последовательным, если отношение является полным порядком (т.е., Vu,ve Va, u<av или v<au).

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

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

Данный алгоритм реализован на языке С++ и использован для поиска паттернов в записях трехмерного управляющего сигнала манипулятора. Было показано, что эта классификация временных сечений многомерных временных рядов дает абстракцию исходных данных, при которой синхронные паттерны многомерных временных рядов представляются повторяющимися эпизодами символьных данных - номеров кластеров. На рис. 5 приведена запись управляющего сигнала, содержащая два типа жестов. А на рис. 6 приведен результат кластеризации и обнаруженные паттерны.

Рис.5. Исходная запись ускорений для двух типов повторяющихся жестов

V ;

Рис.6. Обнаруженные повторяющиеся эпизоды

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

В заключении приведены основные результаты работы.

Основные результаты работы

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

2. Разработан драйвер для управления курсором стандартной компьютерной мыши.

3. Разработан загрузчик программ для манипулятора.

4. Разработан ряд программ для записи показаний акселерометра.

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

6. Исследованы свойства сигналов, а также характеристики процесса физиологического дрожания руки.

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

8. Предложен алгоритм фильтрации с использованием нелинейного фильтра Калмана, модель для которого обучается посредством ЕМ-алгоритма.

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

10. Предложен и программно реализован (на С++) метод повышения размерности временных рядов посредством добавления к имеющимся компонентам временных рядов их первых разностей и разностей более высоких порядков.

11. Рассмотрена задача синхронизации сигналов манипулятора.

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

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

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

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

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

17. Использован алгоритм ожидания и максимизации правдоподобия для кластеризации временных сечений многомерных временных рядов.

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

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

Список публикаций автора по теме диссертации

1. Kukharenko B.G., Ponomarev D.I. Bayesian filtering of control signal of telerobotic manipulator with precise accelerometer // Проблемы машиностроения и автоматизации. 2011. № 1. С. 7276.

2. Кухаренко Б.Г., Пономарев Д.И. Нелинейная Байесовская фильтрация многомерных временных рядов // Информационные технологии. 2011. № 6. С.33-39.

3. Пономарев Д.И., Кухаренко Б.Г. Использование алгоритма ожидания и максимизации правдоподобия в Марковской модели непрерывного профиля для синхронизации сигналов манипулятора // Труды МФТИ. 2011. Т.З. № 2(10). С. 112-118.

4. Кухаренко Б.Г., Пономарев Д.И. Дистанционный манипулятор на основе MEMS-акселерометра в качестве чувствительного элемента // Нано- и микросистемная техника. 2012. №2. С.49-54.

5. Кухаренко Б.Г., Пономарев Д.И. Использование метода Прони для оценки временного масштаба при обнаружении паттернов во временных рядах // Информационные технологии. 2012. № 1. С.37-42.

6. Пономарев Д.И. Использование алгоритмов обнаружения паттернов для идентификации жестов оператора в записях управляющего сигнала манипулятора // Труды МФТИ. 2012. Т.4. № 3(15). С. 187-197.

7. Кухаренко Б.Г., Пономарев Д.И. Аппроксимация смесью Гауссовых распределений в модели переключающегося фильтра Калмана для идентификации режимов колебаний временных рядов // Информационные технологии. 2012. № 7. С.2-7.

8. Кухаренко Б.Г., Пономарев Д.И. Обнаружение паттернов многомерных временных рядов на основе абстракции данных // Информационные технологии. 2013. № 4. С.28-34.

9. Кухаренко Б.Г., Пономарев Д.И. Анализ независимых компонент потока векторов для сокращения размерности пространства при кластеризации векторов с целями абстракции данных // Информационные технологии. 2013. № 5. С.2-8.

10. Пономарев Д.И. Использование методов Байесовской фильтрации при обработке сигналов манипулятора // Информационные технологии: Модели и методы. Сборник научных трудов. М.: МФТИ. 2010. С.65-72. ISBN.

11. Кухаренко Б.Г., Пономарев Д.И. Применение нелинейной байесовской фильтрации при обработке сигналов трехмерного манипулятора // Труды 53-й Научной конференции

МФТИ "Современные проблемы фундаментальных и прикладных наук". Ч. VII. Управление и прикладная математика. Т.2. Москва-Долгопрудный. 2010. С.41-44.

12. Пономарев Д.И. Использование алгоритма ожидания и максимизации правдоподобия для фильтрации сигналов трехмерного манипулятора // Труды 53-й Научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". Ч. VII. Управление и прикладная математика. Т.2. Москва-Долгопрудный. 2010. С.41-44.

13. Кухаренко Б.Г., Пономарев Д.И. Использование метода Прони для оценки временного масштаба при обнаружении паттернов во временных рядах // Труды 54-й Научной конференции МФТИ "Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе". Управление и прикладная математика. Том 2. Москва-Долгопрудный. 2011. С.12-13.

14. Пономарев Д.И. Использование алгоритма ожидания и максимизации правдоподобия в Марковской модели непрерывного профиля для синхронизации сигналов манипулятора // Труды 54-й Научной конференции МФТИ "Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе". Управление и прикладная математика. Том 2. Москва-Долгопрудный. 2011. С.52-54.

15. Кухаренко Б.Г., Пономарев Д.И. Обнаружение паттернов многомерных временных рядов на основе абстракции данных // Труды 55-й Научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных наук в области физики и астрономии». Управления и прикладная математика. Том 2. Москва-Долгопрудный-Жуковский. 2012. С.116-117.

16. Пономарев Д.И. Методы ускорения вычислений при обнаружении паттернов многомерных временных рядов на основе абстракции данных // Труды 55-й Научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных наук в области физики и астрономии». Управления и прикладная математика. Том 2. Москва-Долгопрудный-Жуковский. 2012. С.121-122.

Подписано в печать: 21.11.13

Объем: 1,0 п.л. Тираж: 100 экз. Заказ № 160 Отпечатано в типографии «Реглет» г. Москва, Ленинский проспект, д.2 (495) 978-66-63, www.reglet.ru

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

04201454414

На правах рукописи

Пономарев Дмитрий Иванович

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

Специальность 05.13.17 «Теоретические основы информатики»

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель

кандидат физико-математических наук, Б.Г.Кухаренко

МОСКВА-2013

СОДЕРЖАНИЕ

Введение.......................................................................................................................4

Актуальность темы.................................................................................................................4

Цель работы............................................................................................................................4

Методы исследования............................................................................................................5

Практическая значимость исследования..............................................................................6

Положения, выносимые на защиту.......................................................................................6

Глава 1. Проблемы разработки драйвера дистанционного манипулятора на

основе МЕМБ-акселерометра и задачи анализа данных.........................................7

Глава 2. Использование ЕМ-алгоритма в Байесовской фильтрации

управляющих сигналов манипулятора....................................................................14

Линейная динамическая система с дискретным временем..............................................17

Сглаживающий фильтр Калмана........................................................................................18

ЕМ-алгоритм.........................................................................................................................19

ЕМ-алгоритм для ЛДС с дискретным временем...............................................................21

Использование ЕМ-алгоритма для обучения нелинейной динамической системы с

дискретным временем..........................................................................................................23

Нелинейная Байесовская фильтрация управляющих сигналов манипулятора..............31

Глава 3. Использование ЕМ-алгоритма в Марковской модели непрерывного

профиля для синхронизации сигналов манипулятора...........................................35

Марковская модель непрерывного профиля......................................................................35

Обучение модели посредством ЕМ-алгоритма.................................................................37

Синхронизация сигналов манипулятора............................................................................39

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

оператора....................................................................................................................43

Аппроксимация сегментов временных рядов по методу Прони.....................................45

Использование алгоритмов сокращения размерности пространства поиска для

обнаружения паттернов временного ряда..........................................................................48

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

прецизионным акселерометром..........................................................................................53

Использование алгоритма для обнаружения паттернов.........................................61

Глава 5. Использование ЕМ-алгоритма для абстракции данных при обнаружении синхронных паттернов - жестов оператора в трехмерных

управляющих сигналах манипулятора....................................................................66

Алгоритм /С-средних в оптимизационной постановке.....................................................70

Алгоритм К-теап$++...........................................................................................................72

Кластеризация данных на основе ЕМ-алгоритма..............................................................73

Алгоритмы поиска последовательных эпизодов...............................................................76

Обнаружение паттернов управляющего сигнала дистанционного манипулятора на

основе абстракции данных..................................................................................................82

Ускорения вычислений при обнаружении паттернов многомерных временных рядов с

использованием ЫУЮ1АСийА...........................................................................................88

Анализ главных компонент.................................................................................................90

Анализ независимых компонент.........................................................................................95

Заключение.................................................................................................................99

Список использованных источников.....................................................................101

Введение

Актуальность темы

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

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

Для этого решаются следующие задачи:

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

2. выявление на основе моделей требуемых характеристик вычислительных алгоритмов и комплексов программ;

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

В работе используются: линейная и нелинейная Байесовская фильтрация, фильтр Калмана, скрытая Марковская модель, алгоритм ожидания и максимизации правдоподобия, спектральный метод Прони, алгоритм динамического искажения времени, алгоритмы поиска повторяющихся последовательностей, алгоритм Mueen-KeoghMotiffii sco very, абстракция данных, алгоритм k-means, k-means++, алгоритмы поиска повторяющихся эпизодов, анализ независимых компонент, кластеризация на основе алгоритма ожидания и максимизации правдоподобия.

Научная новизна полученных результатов

Научная новизна диссертационного исследования состоит в следующем:

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

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

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

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

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

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

Положения, выносимые на защиту

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

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

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

4. Метод сокращения размерности временных рядов на основе анализа независимых компонент при поиске паттернов в результате абстракции данных.

Глава 1. Проблемы разработки драйвера дистанционного манипулятора на основе MEMS-акселерометра и задачи анализа данных

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

В качестве чувствительного элемента устройства, предназначенного для отслеживания движений руки оператора в пространстве, используется MEMS-акселерометр. Это устройство используется как дистанционный манипулятор, например, для управления курсором стандартной компьютерной мыши [1-2]. Внешний вид манипулятора показан на рис. 1.1 (1 и 2, соответственно, две кнопки управления, которые используются как левая и правая кнопка компьютерной мыши, 3 - крепление, при помощи которого это устройство фиксируется на руке оператора).

Рис. 1.1. Внешний вид манипулятора.

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

3

Рис. 1.2. Блок схема устройства.

Основная электронная часть устройства реализована на одной печатной плате (рис. 1.3).

Рис.1.3. Электронная часть манипулятора.

Чувствительным элементом манипулятора (номер 4 на рис. 1.3) является МЕМ8-акселерометр ММА7260()[3]. Данные от акселерометра

оцифровываются при помощи АЦП (номер 2 на рис. 1.3) и далее обрабатываются в микроконтроллере (номер 1 на рис. 1.3). В микросхеме используется преобразователь напряжения (номер 5 на рис. 1.3), т.к. напряжение питания элементов схемы составляет 3.3 В, а напряжение питания от USB - 5 В. Номер 6 на рис. 1.3 - кварцевый генератор, а 3 - мультиплексор. Устройство подключается к компьютеру через разъем microUSB (номер 7 на рис.1.3).

Акселерометр MMA7260Q компании FreescaleSemiconductor имеет три чувствительные оси и способен работать в различных диапазонах ускорений: ±1.5g, ±2g, ±4g, ±6g. Функциональная блок-диаграмма акселерометра показана на рис. 1.4.

g-Selectt о-g-Select2 о-

Sieep Mode с

G-Cell Sensor

Oscillator

Clock Generator

С to V Conve-ter

Gain

Filter

X-Temp Comp

Control Logic EEPROM Trim Circuits

Y Temp Comp

Z-Temp Comp

Х01Л

O Yqut

-О ZouT

Vss

Рис. 1.4. Функциональная диаграмма акселерометра ММА7260().

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

чувствительность для диапазона ± 1.5g составляет 800

мВ

g

, a VcdRU =1.655.

Типичная схема подключения данного акселерометра показана на рис. 1.5а. Выходы акселерометра подключаются к входам АЦП через ЯС фильтр для минимизации шума тактового генератора. Акселерометр позволяет измерять ускорения по трем взаимно перпендикулярным направлениям (рис. 1.56).

POWER SUPPLY

V»

Sleep Mod«

g-Se!ec11 9-Se!«t2

Ж I

YOUI

Zout

—0-

—4Ш-

Vrh %>

PO vss

Pi S

п g

"О* e a

s

М>ц

a)

Рис.1.5. Схема подключения МЕМ8-акселерометра и его чувствительные

оси.

Сигнал МЕМБ-акселерометра в состоянии покоя содержит аддитивный шум [4, 5]. Кроме того, на уровень шума сигнала, получаемого микроконтроллером, оказывают влияние электрические шумы в цепи питания акселерометра, а также шумы АЦП-преобразования. Рис. 1.6 пунктиром показывает график фактических значений сигнала, когда МЕМБ-акселерометр расположен статически на жесткой поверхности. Сплошная черная линия показывает отфильтрованные данные, очищенные от ошибок и шума АЦП-преобразования.

900 1000

Рис.1.6. График фактических значений сигнала МЕМ8-акселерометра и

результат фильтрации.

Проблема фильтрации сигнала МЕМБ-акселерометра в состоянии покоя посредством линейного фильтра Калмана рассматривается в [6].

На рис. 1.7 показано, как устройство крепится на руке пользователя.

Рис.1.7. Манипулятор в руке пользователя.

Ниже приведены данные с одной из чувствительных осей акселерометра, снятых с интервалом дискретизации времени 5 мс (рис. 1.8). Ускорение измеряется в единицах g.

Рис.1.8. Записи сигналов с двух чувствительных осей акселерометра, полученные свременным интервалом 5 мс. Ускорение измеряется в

единицах g.

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

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

0.04 003 0.02 0.01 0

-001 -0.02 -0.03 -0.04

I

Рис.1.9. Шум, производимый процессом физиологического дрожания руки оператора. Ускорение измеряется в единицах g.

Анализ записи сигнала на рис. 1.9 показывает, что среднеквадратичное отклонение проекции ускорения на одну из чувствительных осей акселерометра

составляет (8.1 ± 2.3) • 10"2 м/2 • Среднеквадратичное отклонение для монитора с

разрешением в 1280 пикселей составляет величину, равную примерно 8 пикселей. То есть задача фильтрации шума, вызванного процессом физиологического дрожания руки оператора, для рассматриваемого манипулятора является весьма существенной. Как показано в [1, 2], этот шум может быть отфильтрован с использованием линейного фильтра Калмана (рис. 1.10). Использование нелинейного фильтра Калмана при отслеживании движений руки пользователя представлено в [10].

ах

05

0 4 03 0.2 О 1 О -О 1 -0 2 -03 -0 4

___

\

J '1л

I

f 1

10

12

14 15

t,C

Рис.1.10. Временная зависимость проекции ускорения g силы тяжести на чувствительную ось л: акселерометра после линейной фильтрации по Калману.Ускорения измеряется в единицах g.

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

( Stat tiave to S*

Plotter

Patterns

/ ¡1 >7 / _,

а :/ I!

7 / I

2 800 2 850 2 950

Points

Рис.1.11. Рабочее окно программы по отслеживанию жестов руки

оператора.

Разрабатываемое устройство способно отслеживать жесты руки оператора. Отслеживание жестов осуществляется при помощи разработанного программного обеспечения, пример рабочего окна программы показан на рис. 1.11. В левой части рабочего окна программы отображается сигналв режиме реального времени, получаемого от акселерометра, а в правой части -обнаруженные паттерны.

В следующих главах рассматриваются задачи, которые возникают при разработке драйвера такого класса устройств. В главе 2 рассматривается задача фильтрации данных; в главе 3 задача выравнивания и синхронизации сигналов,получаемых от независимых датчиков; в главе 4 задача поиска паттернов в одномерных,а в главе 5 задача пои�