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

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

НАГАПЕТЯН Ваагн Эдвардович

МЕТОДЫ РАСПОЗНАВАНИЯ ЖЕСТОВ РУКИ НА ОСНОВЕ АНАЛИЗА ДАЛЬНОСТНЫХ ИЗОБРАЖЕНИЙ

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

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

9 ЯНВ 2314

Москва - 2013

005544468

Работа выполнена на кафедре информационных технологий Российского университета дружбы народов.

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

доктор технических наук, профессор, Хачумов Вячеслав Михайлович

Официальные оппоненты:

доктор физико-математических наук, доцент, заведующий лабораторией теоретических и междисциплинарных проблем информатики СПИИРАН, Тулупьев Александр Львович,

Ведущая организация:

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

Конушин Антон Сергеевич

Институт проблем управления им. В.А. Трапезникова Российской академии наук

Защита состоится «28» февраля 2014 г. в 16 часов 30 минут на заседании диссертационного совета Д212.203.28 при Российском университете дружбы народов, расположенном по адресу: 117419, г. Москва, ул. Орджоникидзе, д. 3, ауд. 110.

С диссертацией можно ознакомиться в научной библиотеке ГОУ ВПО Российского университета дружбы народов (РУДН) по адресу: 117198, г. Москва, ул. Миклухо-Маклая, д. 6.

Автореферат разослан «. и » декабря 2013 г.

Учёный секретарь диссертационного совета Д|\ 1 • Фомин М.Б

Общая характеристика работы

Актуальность исследования. Создание естественных, легких в управлении человеко-машинных интерфейсов для различных приложений является актуальной научной задачей. В настоящее время проводится довольно много исследований по созданию методов распознавания образов, позволяющих бесконтактно взаимодействовать с компьютером посредством жестов рук. К ним можно отнести работы ряда ученых: Алфимцев А.Н., 2008; Оикономидис И. (Oikonomidis I.), 2011; Шаои Ч. (Shaowei С.), 2011; Марака M. (Maraqa M.), 2012; Пижу H. (Pugeault N.), 2011; Шотон Д. (Shotton J.), 2011; Ван Р.У. (Wang R.Y.), 2009; Сана A. (Sanna А.), 2012 и др. На основе разработанных методов созданы немногочисленные практические приложения, наиболее значимые из которых:

1) программные библиотеки Kinect SDK (Microsoft), OpenNI/NITE (PrimeSense), PMD SDK и SoftKinetic IISU для распознавания ключевых точек тела человека посредством применения трехмерных сенсоров;

2) сенсоры компаний LeapMotion, SoftKinetic для распознавания ключевых точек руки человека;

3) компьютерные приложения Flutter, PointGrab HGRS, XTR3D, EyeSight PC для управления компьютером посредством простых жестов рук. Несмотря на отдельные успехи, качество разработанных алгоритмов

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

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

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

— Анализ существующих методов отслеживания и распознавания жестов руки, а также бесконтактного человеко-машинного взаимодействия;

— Исследование и разработка методов описания, извлечения и распознавания конфигураций руки;

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

— Разработка методов распознавания динамических жестов руки на основе анализа траектории движения ладони;

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

На защиту выносятся следующие новые научные результаты:

1. Метод извлечения изображения руки из дальностного изображения человека на основе анализа связанности точек изображения в трехмерном пространстве, со сложностью О(п), где п - количество точек исходного изображения.

2. Метод распознавания позиции кончиков пальцев и точек соединения пальцев с ладонью руки на основе анализа контура изображения руки, со сложностью О(п), где п - количество точек изображения руки.

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

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

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

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

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

3. Разработан и исследован метод распознавания конфигураций руки на основе предложенной меры с обучением по одному прецеденту, который отличается от известных методов высокой надежностью и низкой вычислительной сложностью - 0{n + wm2), где п - количество точек в кадре видеоряда, w- число эталонных жестов, т - максимальное количество вершин многоугольника аппроксимирующего контур фигуры руки.

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

5. Исследованы и разработаны новые методы распознавания статических и динамических жестов Русской ручной азбуки (РРА) и Американской ручной азбуки (ASL- American Sign Language).

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

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

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

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

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

— XII международная научно-практическая конференция «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2011 год);

— 2-ая всероссийская конференция молодых ученых с международным участием «Теория и практика системного анализа» (г. Рыбинск, 16-19 май 2012);

—Международная молодежная конференция «Информационные системы и технологии» (г. Москва, 5-6 сентября, 2012);

— 9-ая Международная конференция «Интеллектуализация обработки информации» (Республка Черногория, г. Будва,. 16-22 сентября 2012);

— Научная сессия НИЯУ МИФИ-2013 (г. Москва, 2013 год);

— Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем (г. Москва, 2013 год);

— XVII ежегодная молодежная научно-практическая конференция SIT-2013 «Наукоемкие информационные технологии» (Переславль-Залесский, апрель 2013 г.);

— 16-ая Всероссийская конференция «Математические методы распознавания образов 2013» (Казань, октябрь 2013 г.);

— 23я Международная Конференция по Компьютерной Графике и Зрению ГрафиКон'2013 (Владивосток, сентябрь 2013 г.);

— 10-ая Международная научно-техническая конференция «Интерактивные системы: проблемы человеко-компьютерного взаимодействия / ИС-2013» (Ульяновск, сентябрь 2013 г.).

Публикации. Основные результаты диссертационной работы изложены в 12 печатных работах, в том числе три статьи опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ [1-3], пять статей в трудах международных и всероссийских научных конференций [4,5,6,7,8], четыре работы в виде тезисов докладов [9,10,11,12].

Структура и объем работы. Диссертационная работа состоит из оглавления, введения, трех глав, заключения и списка литературы. Содержание работы изложено на 117 страницах. Список литературы включает 93 наименований. Текст работы иллюстрируется 50 рисунками и 10 таблицами. Содержание работы

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

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

В задачах распознавания образов и обработки цифровых изображений часто применяется функция интенсивности вида f(x, у), зависящая от целочисленных координат х и у принадлежащих так называемой растровой решетке W2. Пара (х,у) задает позицию точки изображения в системе координат OXY, началом которой является левый верхний угол решетки.

Функция f(x,y) обычно задает яркость, освещенность, насыщенность, степень поглощения и другие спектральные характеристики в точке (х, у).

Пусть заданы пространственная точка M с координатами (x,y,z) и ее ортогональная проекция m с координатами (х, у) на плоскость наблюдения Z = 0. Под далъностным изображением будем понимать цифровое изображение d{х,у), в каждой точке (х, у) которого d(x,y) принимает неотрицательные целые значения, равные величине расстояния от точки M до точки т.

Дальностное изображение всегда можно преобразовать во множество (облако) точек {(х, y,d(x,y))} в трехмерном пространстве, являющееся моделью наблюдаемого объекта.

Под конфигурацией руки будем понимать установленное положение пальцев и кисти руки.

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

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

2. Распознавание статического жеста руки по эталонным конфигурациям;

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

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

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

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

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

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

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

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

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

Для трехмерных сенсоров (далее сенсор) определено максимальное целочисленное расстояние M от плоскости наблюдения до сцены. В точках, расстояние которых больше M, определяем d(x,y) = 0, таким образом d(x,y)e{0,l,...,M}.

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

h = (h0,hl,h2,....,hM), где А,- - количество точек, для которых d(x,y) = i, точки, для которых d(xty) = 0, игнорируются, причем

hо=0.

Вычислим h' = {h^,h[,tv2,....,h'M), h't= ,

k=о

h" = (/£,hl..., h"M ), ^ = В x (1 - ^/N) x Sg(A/),

(2.1)

м ГО, если а = 0

где 5^(а) = <

;=0 [ 1, если а > 0

В этом случае р(х, у) = [ ] принимает целые значения от 0 до В -1, где

В равно количеству градаций полутонового изображения. В настоящей работе В=256. На рисунке 2.1 .Ь представлено полутоновое изображение, полученное на основе дальностного изображения 2.1.а посредством преобразования (2.1).

Рисунок 2.1 — (а) Дальностное изображение в виде облака точек; (Ь) Полутоновое изображение, полученное посредством преобразования (2.1).

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

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

Пусть имеется бинарное изображение с функцией интенсивности ¿{х,у), где g(x,y) принимает значения 0 (для черных точек) и 1 (для белых точек), и дальностное изображение <1 (х, у).

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

Определение 2.1. Точку (х,у) в бинарном изображении назовем изолированной, если существуют более двух соседей другого цвета: \ 8(х,у)~g(x-l,y) \ + \ в(х,у)~8(х + 1,у) \ + \ + + >2

Определение 2.2. В бинарном изображении точка (х\ у') называется связанным соседом точки (х, у), если они соседние и одного цвета.

Определение 2.3. Назовем точки (х0,у0) и (хп, уп) связанными во множестве точек А бинарного изображения, если существует последовательность точек (х0,у0), (х,,^), ..., (хп,уп) принадлежащих А, таких, что (х,.,,_у,_,) и (х,,>',) являются связанными соседями для всех значений ге {1,2,..., и}. Определение 2.4. Множество точек называется связным множеством, если любые пары его точек ((х, у),(х', у')) являются связанными в этом множестве. Определение 2.5. Дискретной фигурой в бинарном изображении назовем связное множество, не являющееся подмножеством другого связного множества.

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

Введем аналогичные понятия для дальностных изображений. Определение 2.7. В дальностном изображении точку (х\ у') назовем г0-связанным соседом точки (х, у), если они соседние и выполняются условия <1( х',у')>0, (1(х, у) > О, I ¿(х\ у') - с1 (х, у) 1< г(|, где г0 - некоторая фиксированная константа.

Определение 2.8. Назовем точки (х0, _у0) и (хп, уп) г0 - связанными во множестве точек А дальностного изображения, если существует последовательность точек (х0,у0), (х,,), ..., (хп,уп) принадлежащих А, таких, что (х;_|,}',_,) и (х;,у,) являются г0-связанными соседями для всех значений ге {1,2,...,и}.

Определение 2.9. Множество точек называется г0 -связным множеством, если любые пары его точек ((х, у),(х', у')) являются г0- связанными в этом множестве.

Определение 2.10. Дискретной фигурой в дальностном изображении назовем 7"0 -связное множество, не являющееся подмножеством другого г0-связного множества.

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

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

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

изображении.

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

1. Вычисление позиции как ключевой точки тела человека;

2. Вычисление позиции посредством показа начального жеста;

3. Вычисление позиции посредством пороговой обработки.

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

Обозначим через dist(a,b) расстояние между точками a,be R" .

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

Пусть имеется распознанная точка ладони (хс,ус) в дальностном изображении d(x, у). Рассмотрим модель наблюдаемого объекта в виде множества пространственных точек {(х, у, d (х, у))}.

1. Создается сфера вокруг точки (xc,yc,d(xc,yc)) с радиусом

, [ С "

Л = - , где С - некоторая константа, зависящая от

d(xc,yc)

характеристик конкретного сенсора (в экспериментах С =80000).

2. Помечаются все точки (х, у) дальностного изображения, для которых (х, у, d(x, у)) не входят в построенную сферу, т.е. отвечающие условию dist( (х, у, d(x, у)), (д:с ,yc,d(xc,yc)))> Л.

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

4. На базе исходного изображения создается новое дальностное изображение с размером (2Л + \)х(2Л + 1), причем, в помеченных точках определяется d(x, у) = 0.

Извлечение изображения руки осуществляется за время, оцениваемое О(п), где п - число точек исходного изображения. Пример результата применения алгоритма представлен на рисунке 2.2.

Рисунок 2.2 — (а) Дальностное изображение человека, распознанная точка ладони и сфера вокруг найденной точки; (Ь) Извлеченное изображение руки. Теорема 2.1. Множество точек {(х, у) I с/ (х, у) > 0}, полученных алгоритмом извлечения изображения руки, является единственной дискретной фигурой (далее фигурой) в извлеченном дальностном изображении.

(Это и последующие теоремы обоснованы в диссертации)

Представим дальностное изображения руки в виде бинарного изображения с функцией интенсивности g{x,y), где

Я(х,у) = \-$8{с1(х,у)) (2.2)

Теорема 2.2. При преобразовании извлеченного дальностного изображения руки ¿(х,у) в бинарное изображение с функцией интенсивности g(x,y) посредством формулы (2.2), множество черных точек полученных в бинарном изображении является дискретной фигурой и совпадает с дискретной фигурой руки в дальностном изображении.

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

1. Сглаживание бинарного изображения (осуществляется путем удаления всех изолированных точек);

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

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

4. Анализ изменения расстояний точек контура относительно точки кисти.

4.1. Обозначим через 5 = {^,^,...,5^.}, =(д:г,у,), г=0,1,...,& полученное упорядоченное множество точек контура фигуры руки (см. пример на рис. 2.3.а).

4.2. Рассмотрим дискретную вещественную функцию расстояний (рис.

2.3.Ы:

дЦ) = е1Ш((х1,у!),(х0,у0)), г = ОД,...,к . (2.3)

Рисунок 2.3 — (а) Контур фигуры руки; (Ь) Поведение функции <?(0 в точках контура фигуры руки.

4.3. Выполним сглаживание функции вида (2.3) методом скользящего окна посредством следующей формулы:

1 ]+т-1

!20') = - У>(0, 7 = 0,1.....£-/я + 1,к>т, (2.4)

где т - количество точек скользящего окна (в программной реализации алгоритма т = 10).

4.4. Осуществим поиск локальных экстремумов функции (2.4). Обозначим через Мх = {т1,т2,..,т1} множество значений номеров точек локальных максимумов и через М1=[п1,п2,~,пр} - множество значений номеров точек локальных минимумов, причем I < 5, р < 4, что определяется естественными ограничениями жеста руки человека.

Имея дальностное изображение с1(х,у), точки контура бинарного изображения руки 5 = {^д,^,...,^}, множества М1 и ДГ,, определим кончики пальцев руки, как точки с позициями (х1,у!,с1(х1,у1)), где = ,

г = 1,2,...,/.

Аналогично точки соединения пальцев с ладонью определим как где {х],у]) = 8П], у = 1,2,...,р.

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

Рисунок 2.4 — Распознанные кончики пальцев руки в виде кругов и точки соединения пальцев с ладонью в виде квадратов.

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

Пусть задано дальностное изображение руки d(x,y). Построим функцию d' -.R2 —» R, интерполирующую d(x,y) следующим образом: d\a,b) = d{x',y') , где (х',у') = arginf dist((x,y),(a,b), (a,b)e R2. Обозначим через G

геометрический скелет фигуры руки в бинарном изображении, которую можно получить посредством аппроксимации контура фигуры многоугольником и построения диаграммы Вороного для этого многоугольника. Скелет фигуры G всегда можно представить в виде плоского графа G = (V,E), где V с R2, EŒV2.

Двумерные скелеты изображения руки не хранят информацию о расстоянии точек руки до сенсора, а криволинейные скелеты трехмерного представления изображения руки не позволяют получить скелет фигуры в реальном времени. Поэтому построим трехмерный скелет G' = (V', Е'), Ус: R3 , Е çzV "следующим образом:

Вход: d\x,y), интерполирующий d(x,y); многоугольник М, аппроксимирующий контур фигуры руки; константа S, определяющая максимальную допустимую длину ребра графа. Шаг 1. Создаем скелет G = (V, Е) многоугольника М. Шаг 2. Создаем пустые множества вершин V' и ребер Е'. Шаг 3. Проверяем длину каждого ребра (и, v) е Е. Если distiu, v) < S, то

1. Включаем и = (хи, уи,d\xu, уи)) и v =(xv,yv,d'(xv,yv)) в V', где u = (xu,yuXv = (xv,yv).

2. Включаем (и',v') в Е'.

иначе

3. Разбиваем ребро (м,у) на равных частей

4. Включаем полученные вершины и ребра в V' и Ё аналогично пунктам 3.1 и 3.2. конец если конец Шаг 3

Выход: Трехмерный скелет G' = (V', Е').

Утверждение 1. Вычислительная сложность алгоритма скелетизации составляет O(wlogn), где п - число вершин многоугольника аппроксимирующего контур фигуры.

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

1. Нормализация скелетов;

2. Развертка скелетов;

3. Поиск сопоставляемых точек разверток и вычисление расстояний между ними посредством известного алгоритма DTW (Dynamic Time Warping).

Рассмотрим вершины (xmax,y„Zl), (xmin, y2,z2), (х3,утах,г3), (х4, у™п,г4), (л5'У5.гт!п)е V, для которых xm,n<x<xm3X, утт <у< утах, zmin<z, V(x,у,z)eV. Введем следующие обозначения: qx = lAx^ -х^),

Нормализованный скелет представим графом С" = (VЕ"), вершины у" = (х", у", г") е V" которого определяются следующим образом: х" = дх(х -сх), у" = ду(у' -су), г" = (г - ) для всех у'= (х,/, г') е V', при этом (м',у')е Е" тогда и только тогда, когда соответствующая дуга (м',у')е Е'.

Развертка скелета осуществляется по часовой стрелке, начиная с самой нижней вершины скелета (рис. 2.5). Результат развертки представляет собой упорядоченное множество вершин графа {у*,^,—.^}, где п = 2\Е"\, которое можно описать в виде дискретных функций у" = (/Х(Г),/у(¿)> 17(0),

г = 1,2,...,« (рис. 2.5.Ь-2.5.с1).

Чу =1/(3'max -^min)' сх = Отах + *min )1 2 > = (Утах +>'min)/2-

max

Начало

R

N (Ь)

к к

N (О N да

Рисунок 2.5 — развертки. (Ь), (а) Развертка скелета, где стрелками показано направление (с) и (с!) показывают поведение функций /х, /у и fz

соответственно.

Пусть имеются развертки двух разных скелетов {У],У2,..., } и

{щ,и2,...,ип}, где V, у,м,г,м). « = 1,2,...,т и и,. = (*<">, у <и\г<">), у = 1,2,...,и .

Детализируем шаги алгоритма ЭТУ/ применительно к решению задачи сравнения разверток.

Обозначим через Ле Лтх" матрицу расстояний между вершинами разверток на метрике Манхеттена:

аи = I х^ - х<а) I +1 уУ 1 + 1 ^ - ¿р 1. (2.5)

Найдем последовательность элементов {(/^, ^ )}£=], /г > т, к > п, к < т + п в матрице А, которая удовлетворяет следующим условиям:

1 • (¿1, Л ) = (1Д) и (гА, ) = (т, п),

2- <Л+1 =4 +1 и Л+1 = Л) ^ (4+1=4 +1 и Л+1 = к +1) или (4+1 =4 и Л+1 = ]к +1). £ = 1,2,...,/1-1,

и

3. Сумма значений элементов £ аа ; ) минимальна для матрицы Л.

*=1 * *

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

л

Найденное минимальное значение суммы £ аа,, ¡ь) является мерой сходства

4=1 * к

скелетов.

Утверждение 2. Вычислительная сложность сравнения трехмерных скелетов С = (У,Е) и С = (У, £") составляет 0(1 Я I х I £" I).

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

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

- управлять курсором мыши посредством жестов пальца руки,

- взаимодействовать с трехмерными моделями объектов посредством нескольких пальцев,

— распознавать и переводить в текстовый вид жесты ручных азбук русского РРА и американского АБЬ языков глухонемых,

— рисовать на экране компьютера посредством динамических жестов руки,

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

Приводятся алгоритмы отслеживания позиций кончиков пальцев руки, распознавания статических жестов А8Ь, поиска коартикуляций во время показа динамических жестов РРА. Доказывается утверждение 3.1, на основе которого вычисляются асимптотические сложности последующих алгоритмов. Утверждение 3.1. Вычислительная сложность алгоритма распознавания статических жестов составляет СКп + ют1), где п - количество точек в кадре видеоряда, то - максимальное количество вершин многоугольника аппроксимирующего контур фигуры руки, ж - количество эталонных скелетов.

Рассмотрим основные результаты распознавания жестов руки.

Тестовая база содержала 800 изображений жестов цифр и 1920 изображений жестов букв двух разных людей. Эталонная база состояла из 34 скелетов, по одному для каждого класса жестов. Скорость распознавания жестов в разработанной системе составляет меньше 30 миллисекунд, что позволяет увидеть результат распознавания жеста сразу же после его показа.

В таблицах 3.1 и 3.2 приведены характеристики распознавания статических жестов ручной азбуки АБЬ, где точность распознавания определяется как доля жестов действительно принадлежащих данному классу относительно всех жестов, которые были отнесены к этому классу. Полнота распознавания определяется как доля найденных классификатором жестов принадлежащих классу относительно всех жестов этого класса в тестовой выборке.

Таблица 3.1 - Характеристики качества распознавания жестов букв А5Ь

Характеристики качества распознавания Тестовая выборка

А в С О Е Р в Н I К Ь м N О Р 0 я Б Т и V X У

Точность 0.81 0.79 0.87 0.95 0.86 0.97 0.85 1 0.81 1 0.6 14 1 1 1 1 0.9 0.5 0.5 0.73 0.87 0.77 1 1

Полнота 0.6 0.6 1 0.9 0.9 0.8 0.8 1 0.9 0.9 1 13 0.5 0.45 1 1 0.85 1 0.38 0.75 Э.85 1 1 1

Таблица 3.2 - Характеристики качества распознавания жестов цифр А5Ь

Характеристики качества распознавания Тестовая выборка

0 1 2 3 4 5 6 7 8 9

Точность 1 0.83 0.83 0.97 0.7 1 0.5 1 0.97 0.97

Полнота 0.55 1 0.88 0.73 0.98 0.98 0.98 0.33 0.9 0.93

Таким образом, средние точность и полнота распознавания для букв и цифр А8Ь составили соответственно 84% и 81.2%, 87.7% и 82.6%.

16

В отличие от языка АБЬ в русской ручной азбуке используется много динамических жестов руки. По этой причине каждая буква РРА рассматривается в виде совокупности конфигурации руки (таблица 3.3) и типа движения (таблица 3.4).

Таблица 3.3 - Конфигурации (формы) руки, используемые в РРА

Таблица 3.4 - Движения пальцев и кисти руки, используемые в РРА

Обозначение Шо ш, ггь т3 гщ т5 Шб ш7

Тип движения • О / 3 I Г

Результаты распознавания ключевых характеристик жестов РРА приведены в таблице 3.5 и З.б.

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

Конфигурации 52 ¿3 «4 510 5,, 5,3 •^17 ^19 ^20 ¿21 ¿23 524 *25 526

Точность 1 1 .61 1 .61 .88 .9 .49 .61 0.8 .95 1 1 1 .91 .78 .78 .59 .74 .95 .43 .95 .71 1 1 1

Полнота .95 .4 .95 .2 .95 .75 .9 .95 .95 0.6 .9 .8 .95 .5 .5 .7 .9 .95 .85 .95 .8 .95 .6 .65 .85 .5

Таблица 3.6 -Результаты классификации движений пальцев и кисти руки, используемые в РРА__

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

Тип движения то Ш] ПЪ т3 пц т5 т« т7

Точность .86 .95 .86 1 1 1 .95 1

Полнота .95 .9 .9 .95 .95 .95 1 1

Средняя точность и полнота распознавания классификаторов конфигурации и движения руки составили соответственно 83.4% и 76.7%, 95.25% и 95%.

На основе рассмотренного подхода был разработан алгоритм распознавания динамических жестов руки. Алгоритм опробован на 12 жестах (рис. 3.2)._

12345 А

6^890 □

_Рисунок 3.1 — Выбранные эталонные жесты._

Тестовая база включала описание 2400 динамических жестов двух человек, показывающих цифры от нуля до девяти и две геометрические фигуры -квадрат и треугольник. В качестве эталонных жестов из тестовой базы произвольным образом были выбраны 12 образцов, по одному для каждого класса. Результаты распознавания приведены в таблице 3.7.

Таблица 3.7 - Характеристики качества распознавания

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

Тип жеста 0 1 2 3 4 5 6 7 8 9 Д □

Точность 0.75 0.83 1 1 0.79 0.82 0.81 1 1 0.73 0.88 0.95

Полнота 0.88 0.98 0.86 0.9 1 0.76 1 1 0.7 0.64 1 0.7

Для динамических жестов средняя точность и полнота составили соответственно 88% и 87%.

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

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

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

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

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

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

4) метод сравнения трехмерных скелетов, включающий нормализацию скелета; развертку скелета; вычисление меры различия скелетов со сложностью 0(т2), где т- максимальное количество ребер сравниваемых скелетов.

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

4. Разработаны алгоритмы распознавания ручных азбук глухонемых РРА и ASL. Точность и полнота распознавания конфигураций руки в обоих случаях составила больше 80%.

5. Разработаны методы распознавания динамических жестов руки и поиска коартикуляций жестов при непрерывном показе жестов русской ручной азбуки за время, оцениваемое как 0(n + wm2+k), посредством анализа ключевых характеристик последних к дальностных изображений руки, где п- количество точек в кадре видеоряда, m - максимальное количество вершин многоугольника аппроксимирующего контур фигуры руки, w - количество эталонных конфигураций. Качество и полнота распознавания превышают 85%.

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

Демонстрационные видео ролики и исходные коды разработанных программ опубликованы на сайте www.tiptep.com.

Список работ, опубликованных по теме диссертации Статьи в рецензируемых изданиях, рекомендованных ВАК РФ:

1. Нагапетян В.Э. Обнаружение пальцев руки в дальностных изображениях // Искусственный интеллект и принятие решений, №1,2012.— с. 90-95

2. Нагапетян В.Э. Распознавание жестов ручной азбуки ASL // Вестник Российского университета дружбы народов. Серия: математика, информатика, физика, №2. М.: 2013,— с. 105-113

3. Нагапетян В.Э, Хачумов В.М. Автоматическое преобразование жестов русской ручной азбуки в текстовый вид // Искусственный интеллект и принятие решений, №3, 2013. — с.59-66

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

4. Нагапетян В.Э. Человеко-машинное взаимодействие с помощью жестов пальца руки // XII международная научно-практическая конференция "Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности". Сборник статей. В 3 томах. Т.З, часть 1. — Санкт-Петербург: 2011. — с. 122-125

5. Нагапетян В.Э. Распознавание простейших жестов и положения руки в пространстве // 2-ая всероссийская конференция молодых ученых с международным участием "Теория и практика системного анализа", (г. Рыбинск, 16-19 май 2012). Сборник трудов. В 2 томах. Т.1.— Рыбинск: 2012. — с.153-158

6. Нагапетян В.Э. Распознавание динамических жестов руки посредством обработки дальностных изображений человека // 23-я Международная Конференция по Компьютерной Графике и Зрению, ГрафиКон'2013 (16-20 сентября, 2013 Владивосток, Россия). Труды конференции. — Владивосток: 2013,— с. 118-121

7. Нагапетян В.Э., Хачумов В.М. Распознавание жестов руки по дальностным изображениям // 9-ая Международная конференция «Интеллектуализация обработки информации» (Республка Черногория, г. Будва,. 16-22 сентября 2012). Сборник докладов. — М.: 2012. — с. 445-447

8. Nahapetyan V.E., Human-computer multi-touch interaction using depth sensors // Interactive Systems: Problems of Human - Computer Interaction. Collection of scientific papers. - Ulyanovsk: USTU, 2013. — p. 225-232

9. Нагапетян В.Э., Система распознавания динамических жестов человека // Международная молодежная конференция «Информационные системы и технологии» (г. Москва, 5-6 сентября, 2012). Сборник тезисов. — М.: 2012. — с. 90-91

10. Нагапетян В.Э. Сурдоперевод на основе автоматического анализа геометрического скелета руки // НАУЧНАЯ СЕССИЯ НИЯУ МИФИ-2013. Аннотации докладов. В 3 томах. Т.2. Интеллектуальные системы и технологии. — М.: НИЯУ МИФИ, 2013. — с. 334

11. Нагапетян В.Э. Построение скелетов объектов дальностного изображения // Информационно-телекоммуникационные технологии и Математическое Моделирование Высокотехнологических Системах. — М.: 2013. — с. 130-132

12. Нагапетян В.Э. Распознавание жестов ручных азбук глухонемых // 16-ая Международная конференция «Математические методы распознавания образов» (г. Казань,. 6-12 октября 2013). Тезисы докладов. — М.: 2013. — с. 63 Личный вклад соискателя. В совместно опубликованных работах [3,7] автору принадлежат разработанные методы сглаживания контура ладони руки и идентификации статического жеста посредством скелетного представления дальностного изображения руки.

Нагапетян В.Э.

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

Введены необходимые определения, метрики и формализации. Доказаны теоремы о том что:

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

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

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

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

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

Nahapetyan V.E.

Hand gesture recognition methods based on the analysis of depth images

Abstract

The necessary definitions, metrics, and formalizations are introduced. The following statements are established:

the set of nonzero points obtained after the hand image extraction is a discrete figure in a depth image;

the discrete figure obtained after the conversion of a hand" s depth image into a binary image by the introduced formula matches with the hand figure in the depth image;

the introduced metric for assessing the distance between the two skeletons fulfills all the axioms of a metric except for the triangle inequality.

The problems of the recognition static and dynamic hand gestures in 3D space are formulated.

The algorithms and software implementations are presented allowing human to control computer with bare finger motions, translate gestures used in Russian and American fingerspelling to digital text, and interact with computer via dynamic hand gestures.

Подписано в печать 21.12.2013г.

Усл.п.л. - 1.0 Заказ №17700 Тираж: ЮОэкз.

Копицентр «Чертеж.ру» ИНН 7701723201 107023, г.Москва, ул.Б.Семеновская 11, стр.12 (495) 542-7389 www.chertez.ru

РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

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

НАГАПЕТЯН ВААГН ЭДВАРДОВИЧ

МЕТОДЫ РАСПОЗНАВАНИЯ ЖЕСТОВ РУКИ НА ОСНОВЕ АНАЛИЗА ДАЛЬНОСТНЫХ ИЗОБРАЖЕНИЙ

05.13.17-Теоретические основы информатики

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель доктор технических наук, профессор В.М. Хачумов

Москва - 2013

Оглавление

Введение.......................................................................................................................5

Глава 1. Методы распознавания жестов руки в системах человеко-машинного взаимодействия..........................................................................................................12

1.1. Задача распознавания жестов руки.............................................................12

1.2. Анализ существующих методов распознавания жестов руки на основе анализа внешних признаков жеста.......................................................................15

1.2.1. Распознавание позиции и ориентации с помощью моментов изображения........................................................................................................15

1.2.2. Распознавание движений на основе анализа разностей изображений (МЕ1) 17

1.2.3. Распознавание конфигурации на основе анализа гистограмм направлений.........................................................................................................18

1.2.4. Распознавание конфигурации и позиции с применением цветных перчаток...............................................................................................................19

1.2.5. Распознавание конфигурации и позиции на основе анализа контура изображения руки...............................................................................................21

1.2.6. Распознавание позиции и конфигурации руки методом случайных лесов 22

1.2.7. Распознавание жестов руки с применением искусственных нейронных сетей.................................................................................................24

1.2.8. Распознавание жестов руки с применением скрытых моделей Маркова................................................................................................................25

1.3. Анализ существующих методов распознавания жестов руки на основе анализа трехмерной модели руки.........................................................................27

1.3.1. Распознавание жестов как задача оптимизации....................................28

1.3.2. Распознавание жестов на основе ограниченного количества проекций модели руки.........................................................................................................30

1.4. Ручная азбука и язык глухонемых..............................................................31

2

1.5. Основные выводы.........................................................................................32

Глава 2. Исследование и разработка методов распознавания жестов руки в дальностных изображениях человека.....................................................................36

2.1. Характеристики дальностных изображений................................................36

2.2. Основные определения...................................................................................40

2.3. Извлечение изображения руки......................................................................41

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

2.3.2. Извлечение изображения руки по позиции ладони..............................45

2.4. Распознавание позиций кончиков пальцев и точек соединения пальцев с ладонью руки..........................................................................................................47

2.5. Распознавание конфигурации руки...............................................................54

2.5.1. Скелетизация изображения руки посредством планарного представления дальностного изображения......................................................55

2.5.2. Скелетизация изображения руки посредством пространственного представления дальностного изображения......................................................63

2.5.3. Построение трехмерного скелета дальностного изображения............65

2.5.4. Сравнение трехмерных скелетов руки...................................................67

2.6. Основные выводы...........................................................................................74

Глава 3. Разработка методов бесконтактного управления компьютером и распознавания ручных азбук глухонемых..............................................................77

3.1. Человеко-машинное взаимодействие с помощью жестов пальца руки.... 77

3.2. Человеко-машинное взаимодействие в трехмерном пространстве посредством нескольких пальцев руки................................................................81

3.3. Распознавание жестов глухонемых...............................................................85

3.3.1. Распознавание ручной азбуки А8Ь.........................................................85

3.3.2. Распознавание ручной азбуки РРА.........................................................89

3.4. Человеко-машинное взаимодействие посредством динамических жестов

руки..........................................................................................................................97

3.4.1. Бесконтактное рисование посредством динамических жестов руки.. 97

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

3.5. Оценка качества распознавания предложенных методов.........................102

3.6. Основные выводы.........................................................................................105

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

Литература...............................................................................................................108

Введение

Актуальность исследования. Создание естественных, легких в управлении человеко-машинных интерфейсов для различных приложений является актуальной научной задачей. В настоящее время проводится довольно много исследований по созданию методов распознавания образов, позволяющих бесконтактно взаимодействовать с компьютером посредством жестов рук. К ним можно отнести работы ряда ученых: Алфимцев А.Н., 2008; Оикономидис И. (Oikonomidis I.), 2011; Шаои Ч. (Shaowei С.), 2011; Марака M. (Maraqa M.), 2012; Пижу H. (Pugeault N.), 2011; Шотон Д. (Shotton J.), 2011; Ван Р.У. (Wang R.Y.), 2009; Сана A. (Sanna А.), 2012 и др. На основе разработанных методов созданы немногочисленные практические приложения, наиболее значимые из которых:

1) программные библиотеки Kinect SDK (Microsoft), OpenNI/NITE (PrimeSense), PMD SDK и SoftKinetic IISU для распознавания ключевых точек тела человека посредством применения трехмерных сенсоров;

2) сенсоры компаний LeapMotion, SoftKinetic для распознавания ключевых точек руки человека;

3) компьютерные приложения Flutter, PointGrab HGRS, XTR3D, EyeSight PC для управления компьютером посредством простых жестов рук. Несмотря на отдельные успехи, качество разработанных алгоритмов

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

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

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

— Анализ существующих методов отслеживания и распознавания жестов руки, а также бесконтактного человеко-машинного взаимодействия;

— Исследование и разработка методов описания, извлечения и распознавания конфигураций руки;

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

— Разработка методов распознавания динамических жестов руки на основе анализа траектории движения ладони;

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

На защиту выносятся следующие новые научные результаты:

1. Метод извлечения изображения руки из дальностного изображения человека на основе анализа связанности точек изображения в трехмерном пространстве, со сложностью 0(п), где п - количество точек исходного изображения.

2. Метод распознавания позиции кончиков пальцев и точек соединения пальцев с ладонью руки на основе анализа контура изображения руки, со сложностью 0(п), где п - количество точек изображения руки.

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

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

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

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

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

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

■у

вычислительной сложностью - 0(п + лмт ), где п - количество точек в кадре видеоряда, м>- число эталонных жестов, т - максимальное количество вершин многоугольника аппроксимирующего контур фигуры руки.

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

пальцев и точек соединения пальцев с ладонью руки, независимо от количества и направления пальцев. 5. Исследованы и разработаны новые методы распознавания статических и динамических жестов Русской ручной азбуки (РРА) и Американской ручной азбуки (ASL- American Sign Language). Методы исследования. В работе используются методы теории графов, вычислительной геометрии, математического анализа, теории распознавания образов. Работа несет теоретико-экспериментальный характер. Все разработанные методы реализованы в виде компьютерных программ, большинство из которых опубликованы во всемирной сети в свободном доступе.

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

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

Практическая значимость. На основе разработанных методов созданы

программные приложения, позволяющие управлять курсором компьютера

посредством жестов пальца, взаимодействовать с компьютером посредством

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

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

руки. Разработанные алгоритмы сравнения объектов могут быть использованы

8

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

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

— XII международная научно-практическая конференция «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2011 год);

— 2-ая всероссийская конференция молодых ученых с международным участием «Теория и практика системного анализа» (г. Рыбинск, 16-19 май 2012);

— Международная молодежная конференция «Информационные системы и технологии» (г. Москва, 5-6 сентября, 2012);

— 9-ая Международная конференция «Интеллектуализация обработки информации» (Республка Черногория, г. Будва,. 16-22 сентября 2012);

— Научная сессия НИЯУ МИФИ-2013 (г. Москва, 2013 год);

— Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем (г. Москва, 2013 год);

— XVII ежегодная молодежная научно-практическая конференция 81Т-2013 «Наукоемкие информационные технологии» (Переславль-Залесский, апрель 2013 г.);

— 16-ая Всероссийская конференция «Математические методы распознавания образов 2013» (Казань, октябрь 2013 г.);

— 23я Международная Конференция по Компьютерной Графике и Зрению ГрафиКон'2013 (Владивосток, сентябрь 2013 г.);

1 — 10-ая Международная научно-техническая конференция «Интерактивные

системы: проблемы человеко-компьютерного взаимодействия / ИС-2013» (Ульяновск, сентябрь 2013 г.).

Публикации. Основные результаты диссертационной работы изложены в 12 печатных работах, в том числе три статьи опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ [1-3], пять статей в трудах международных и всероссийских научных конференций [4,5,6,7,8], четыре работы в виде тезисов докладов [9,10,11,12].

Структура и объем работы. Диссертационная работа состоит из оглавления, введения, трех глав, заключения и списка литературы. Содержание работы изложено на 117 страницах. Список литературы включает 93 наименований. Текст работы иллюстрируется 50 рисунками и 10 таблицами. Содержание работы

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

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

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

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

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

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

Глава 1. Методы распознавания жестов руки в системах человеко-машинного взаимодействия

1.1. Задача распознавания жестов руки

Человеко-машинное взаимодействие (Human-computer interaction - HCI) -это междисциплинарное научное направление, изучающее взаимодействие между людьми и машинами. Предметом HCI является изучение, планирование и разработка методов взаимодействия человека с машиной, где в роли машины может выступать персональный компьютер, компьютерная система больших масштабов, система управления процессами и т.д. [13]. Под взаимодействием понимается любая коммуникация между человеком и машиной. Одним из методов HCI, получившим широкое распространение в последние годы, является взаимодействие, основанное на жестах человека [14, 15, 16].

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