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

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

Нгуен Тоан Тханг

АЛГОРИТМЫ РАСПОЗНАВАНИЯ ЖЕСТОВ НА ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЯХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

АВТОРЕФЕРАТ

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

г о фев 2014

Томск-2014

005545248

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

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

Спицын Владимир Григорьевич

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

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

Протасов Константин Тихонович, доктор технических наук, старший научный сотрудник, федеральное государственное бюджетное учреждение науки Институт оптики атмосферы им. В.Е. Зуева, лаборатория распространения оптических сигналов, старший научный сотрудник

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

Защита состоится 27 марта 2014 г. в 10.30 на заседании диссертационного совета Д 212.267.08, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (корп. 2, ауд. 102).

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Материалы по защите диссертации размещены на официальном сайте ТГУ: http://www.tsu.ru/content/news/announcement_of_the_dissertations_in_the_tsu.php

Автореферат разослан « 0Г?~ » февраля 2014 г.

Ученый секретарь ^у

диссертационного совета /у' Скворцов

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. В последние годы появилась и начала быстро развиваться тенденция использования жестов как способа взаимодействия с компьютерной системой. Распознавание жестов стало важнейшей частью в области человеко-машинного взаимодействия и привлекает множество исследователей. В числе пионеров в области распознавания жестов и построения интерфейса на их основе можно выделить Kurtenbach G., Hulteen Е., Kendon A., Quek, Mapes D. J„ Moshell M. J., Kobayashi T., Haruyama S., Krueger M., Kanade T., Tomasi C., Petrov S., Triesch J„ Malsburg C„ Rehg J.M., fmagawa K., Baudel T., Beaudouin-Lafon M.

В настоящее время среди различных подходов к решению задачи распознавания жестов, подход на основе компьютерного зрения оказывается доминантной тенденцией благодаря новым достижениям в области компьютерного зрения, повышению производительности компьютеров, и также популярности и высокому качеству недорогих видеокамер. При этом важным является тот факт, что системы распознавания жестов на основе компьютерного зрения обеспечивают естественный канал взаимодействия человека с компьютером. Перспективность данного направления подтверждается результатами исследований таких авторов как Kölsch M., Turk M., Lienhard R„ Maydt J., Rittscher J., Blake A., Bradski G., Viola P., Jones M., Isard M., Davis J., BobickA., Comaniciu D.

Большинство этих подходов воспринимает жест как целую сущность и пытается извлечь соответствующее математическое описание из большого количества обучающих примеров (Campbell L., Kobayashi T., Manresa С., Oka К., Wren С., Wu Y., Yang J.). В результате, эти подходы характеризуются недостаточной скоростью, точностью, надежностью и ограниченным количеством распознанных жестов. В существующих методах также часто требуются специальные условия использования (без других объектов на фоне, постоянное освещение, наличие специальных приборов, и т.д.). Примерами таких систем могут быть «расширенный стол» (Ока и др.), «визуальная панель» (Zhang и др.), HandVu (Kölsch и Turk), Pfinder (Wren и ДР-)-

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

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

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

1. Разработать алгоритм распознавания поз руки (hand posture), способный функционировать в режиме реального времени и инвариантный к аффинным преобразованиям и изменению освещения.

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

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

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

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

Научная новизна.

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

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

3. Разработан новый алгоритм распознавания жестов (hand gesture) на основе детектора Джонса-Виолы, трекера CAM-Shift, предложенных алгоритмов распознавания поз и движения руки, позволяющий распознавать жесты на видеопоследовательностях в режиме реального времени. Особенностью предложенного алгоритма является сочетание возможности распознавания интерактивных и автономных жестов благодаря разбиению жестов на статическую компоненту (позу) и динамическую компоненту (движение руки).

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

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

Реализованная программа Hand Recognitor обеспечивает управление презентациями, навигацию веб-браузера, рисование, управление Windows media center с использованием жестов.

Реализация результатов работы. Способы, алгоритмы и программы, разработанные в диссертационной работе, использовались при выполнении работ по гранту РФФИ № 09-08-00309 «Создание программного комплекса автоматизированной обработки изображений и распознавания образов на основе применения искусственных нейронных сетей, регуляторных сетей и эволюционных алгоритмов» (2007-2009 г.), в проекте «Продвижение и коммерциализация инновационной технологии по обработке изображений на базе эволюционных и нейроэволюционных вычислений», (конкурс «Microsoft Бизнес-Старт» Фонда содействия развитию малых форм предприятий в научно-технической сфере 2009-2011 г.), в проекте «Создание комплексных технологий распознавания объектов на изображениях на основе применения моделей зрительного восприятия и методов вычислительного интеллекта», поддержанном грантом РФФИ № 12-08-00296 (2012-2014 г.).

Степень достоверности результатов проведенных исследований.

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

Внедрение работы. Реализованное в ходе диссертационной работы программное обеспечение для управления презентациями с помощью жестов внедрено в ООО «ARROWHITECH» (г. Ханой, Вьетнам). Созданная программная система Hand Recognitor зарегистрирована в Федеральной службе по интеллектуальной собственности (свидетельство о государственной регистрации программы для ЭВМ № 2012014382 от 16.05.2012).

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

1. Алгоритм распознавания поз руки (hand posture) на видеокадре на основе применения З^Я^дескрипторов, алгоритма ¿-средних, и многослойной нейронной сети.

2. Алгоритм распознавания траектории движения руки (hand motion) в видеопотоке на основе нейронной сети, и также идеи упрощения и передискретизации траектории.

3. Алгоритм распознавания жестов (hand gesture) на видеопоследовательностях в режиме реального времени на основе детектора Джонса-Виолы, трекера CAM-Shift, предложенных алгоритмов распознавания поз и движения руки.

Апробация работы. Основные результаты работы обсуждались и докладывались на следующих симпозиумах, конференциях и семинарах: IV Всероссийская научно-практическая конференция «Научная инициатива иностранных студентов и аспирантов российских вузов» (Томск, 2010); Международная научно-практическая конференция «Интеллектуальные информационно-телекоммуникационные системы для подвижных и труднодоступных объектов» (Томск, 2010); XIX Всероссийский семинар «Ней-роинформатика, ее приложения и анализ данных» (Красноярск, 2011).

Публикации. Основное содержание диссертации отражено в 9 работах, в том числе 4 статьи в изданиях из перечня ВАК, 2 статьи в рецензируемом журнале, 2 доклада на Всероссийских и Международных и конференциях, и одно свидетельство об официальной регистрации программы распознавания жестов для ЭВМ Hand Recognitor.

Личный вклад. Постановка задач диссертационного исследования выполнена автором совместно с научным руководителем, д.т.н., профессором Спицыным В.Г. Основные теоретические и практические результаты, представленные в диссертации, получены лично автором.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 150 наименований. Общий объем работы составляет 147 страниц машинописного текста, иллюстрированного 64 рисунками и 21 таблицами.

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

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

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

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

На втором уровне возможен выбор режима распознавания автономных или интерактивных жестов.

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

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

Для обнаружения руки в видеопотоке в реальном времени предложено применение алгоритма (детектора) Джонса-Виолы, который работает на основе признаков Хаара, интегрального изображения, и каскадного классификатора Аг/аВоояГ.

Признак Хаара представляет собой «шаблон», который указывает координаты областей изображения, а значение признаков Хаара - разность суммарных интенсивностей пикселей под областями, указанными признаком Хаара. Эта разность используется для определения присутствия / отсутствия характерной области объекта на изображении. Понятие «интегрального изображения» позволяет быстро вычислить значение признаков Хаара, независимо от размера изображения. Интегральное изображение Р в точке р(х,у) вычисляется как сумма интенсивности всех точек, находящихся вверху слева от нее. В методе Джонса-Виолы, ряд АйаВооьи классификаторов объединяется в каскадную структуру, каждый из классификаторов отвечает за определенный набор признаков Хаара, характерных

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

Для тренинга руки в видеопотоке в данной работе предложено применение известного метода САМ-БМ^ с использованием цветовой информации руки. Данный алгоритм основан на вычислении «гистограммы вероятности цветов», создании «изображения вероятности», и определении центра масс руки. «Гистограмма вероятности цветов» вычисляется по формуле:

НМ:

Р = min

-SI

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

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

(Wc) =

М)0 м0,

хПх,у), Л/01 У).

х у х у

Здесь (хс,ус) - координаты центра масс; I(х,у) - интенсивность пикселя (х,у) изображения вероятности; М00, М10, Мш - нулевой момент, первый момент по направлению х, первый момент по направлению у, соответственно.

Для распознавания поз руки в диссертации предложен новый алгоритм на основе 5£//?^дескрипторов, алгоритма ¿-средних, и многослойной нейронной сети. Основная идея предложенного алгоритма состоит в том, что изображение рассматривается как текстовый документ, в котором визуальные признаки (характерные точки и области) изображения учитываются как слова, образующие данный документ. Класс документа определяется путем вычисления частоты появления некоторых «ключевых слов». Данная идея была взята из популярной в обработке текстовых документов модели <.<.bag-of-words>> (BOW). Для применения этой идеи в распознавании объекта, характерные признаки выделяются из обучающей выборки изоб-

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

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

1. Обучение классификатора

а. Генерация словаря визуальных признаков:

- Выделение признаков методом SURF.

- Кластеризация методом K-means.

- Генерация словаря из кластеров.

б. Создание дескрипторов и обучение нейронной сети:

- Сопоставление выделенных признаков со словарем.

- Обучение классификатора (нейронной сети).

2. Распознавание

- Выделение признаков методом SURF.

- Сопоставление выделенных признаков со словарем.

- Распознавание в нейронной сети.

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

~La{P,cr) Р,а) LJI\a)

Здесь La(P,a), Р,а), Lxy(P,cr) - свертка второй производной Гаусса с изображением в точке Р.

Разделение признаков на группы осуществляется с применением алгоритма ¿-средних (k-means). При применении алгоритма кластеризации к-means нужно вначале задать количество кластеров (число слов в словаре), которое приблизительно равняется сумме средних чисел признаков всех классов объекта:

м,

N

М,

Здесь К - число кластеров; N - количество классов объектов; м- количество изображений /-ого класса; kfi - число выделенных признаков из j-ого изображения /'-ого класса.

Н(Р,<7) =

Для каждого SURF вектора (дескриптора) вычисляется квадрат расстояний Евклида до каждого из центров масс

N

d(p>q = -а)2 i=i

и среди них выбирается самое короткое расстояние. Здесь d(p,q,.) - расстояние от входного SURF вектора до к-ого центра масс; N - размерность SURF-вектора (64 или 128 в зависимости от выбранного способа описания); р - входной SURF вектор; qt - к-ый центр масс.

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

2 К-\ к

9 = угу sd(h>4j),i*j-

li(K-l) i = l y.f+1

Здесь д - пороговое значение; d{qi,qj)- расстояние между центрами qt и qj\ К — число центров.

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

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

Упрощение и сглаживание траектории движения осуществляется с применением алгоритма Рамера-Дугласа-Пекера (Ramer-Douglas-Peucker). Суть алгоритма состоит в том, что по заданной кривой линии траектории необходимо построить ломаную с меньшим числом точек. Упрощенная кривая состоит из подмножества точек исходной кривой. На Рис. 1 показывается пример упрощения линии траектории.

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

/ /

\ v а \

Рис. 1. Результат упрощения линии алгоритмом Рамера-Дугласа-Пекера

7, = {/>(л,.,х)|г'е[1..т]}, где т - количество точек. При этом необходимым условием является присутствие в траектории N точек. Величина N является фиксированной и соответствует числу входов в нейронную сеть. Для осуществления перехода от т точек к N точкам сначала вычисляется длина траектории L. Величина среднего расстояния между точками передискре-тизируемой траектории определяется соотношением ML/(A4). Среднее расстояние / будет использоваться как условие для добавления/удаления точки из исходной траектории.

Массив точек траектории преобразуется в массив векторов наклона и затем вычисляется синус углов наклона. Массив синусов в дальнейшем будет служить входом для классификатора. Для каждой точки Р„(х„,у„) вычисляется синус угла отклонения а между вектором Рп и осью Ох. В результате передискретизации, количество точек в траектории уже фиксировано и равняется N. Таким образом, получается массив S = {sin(aj| О < п < N], который будет использоваться как дескриптор траектории и может быть передан в виде входных данных в нейронную сеть для осуществления процесса распознавания. Многослойная нейронная сеть с обратным распространением ошибок применяется для распознавания формы траектории.

В третьей главе представлены результаты тестирования разработанного алгоритма распознавания позы. Все эксперименты выполнены на ноутбуке ASUS UL-VT 80 с процессором Intel Core Duo [/7300 1,3 ГГц и 4,0 ГБ оперативной памяти с встроенной камерой.

Первые три эксперимента были выполнены на созданных выборках с четырьмя примитивами поз руки (Рис. 2). Эксперименты включают тестирование на выборке с однородным фоном (табл. 1), тестирование на выборке с присутствием других объектов (табл. 2) и тестирование на сильно зашум-ленной выборке (табл. 3). На рис. 4-6 приведены примеры изображений с однородным фоном, выборки с присутствием других объектов, и сильно зашумленной выборки, соответственно.

ri

Fist Open Palm V-Shape Palm

Рис. 2. Позы для тестирования

Ш 2> У я $ А & I \ 1 3 ^ & -11 Рис. 3. Изображения выборки с однородным фоном

, - ,_____# #

ими/

Рис. 4. Часть тестовой выборки с частично зашум-ленными изображениями

t i i дос

^ Л:

Рис. 5. Часть тестовой выборки с сильно зашум-ленными изображениями

Таблица 1. Результаты тестирования на выборке с однородным фоном

Класс

Fist | Open Palm | Palm | V-Shape

Последовательность размера 120x120 пикселей

Ср. время (мс)1 39 42 39 40

Точность (%) 98,6 99,8 98,8 98,0

Ср. точность 98,8 %

Последовательность размера 100х 100 пикселей

Ср. время (мс) 28 31 29 30

Точность (%) 98,4 99,8 98,6 98,0

Ср. точность 98,7 %

Последовательность размера 80x80 пикселей

Ср. время (мс) 14 16 15 15

Точность (%) 98,0 99,8 98,2 97,8

Ср. точность 98,5 %

Последовательность размера 50x50 пикселей

Ср. время (мс) 14 16 15 15

Точность (%) 88,8 94,0 88,6 88,2

Ср.точность 89,9 %

Таблица 2. Результаты тестирования на частично зашумленной выборке

Класс

Fist Open Palm Palm V-Shape

Ср. время (мс) 31 34 30 32

Точность (%) 94,7 98,3 95,1 93,5

Ср. точность 95,8 %

Таблица 3. Результаты тестирования на сильно-зашумленной выборке

Класс

Fist Open Palm Palm V-Shape

Ср. время (мс) 34 37 34 35

Точность (%) 91,8 96,5 90,3 91,8

Ср. точность 92,6 %

Проведенные эксперименты доказывают, что время обработки (14^0 миллисекунд/кадр) приемлемо для работы в реальном времени и не оказывает заметной задержки при обработке видеопотока. Предложенный алгоритм может достичь высокой точности распознавания (до 98,8%) в «идеальном» случае (один объект на однородном фоне), без учета масштаба и поворота объекта. При минимальном размере кадра 50x50 пикселей точность распознавания существенно уменьшается. Это означает, что алгоритм теряет эффективность при недостаточном числе признаков из-за малого размера объекта.

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

1 Время обработки включает время на выделение SURF дескрипторов, вычисление BOW дескрипторов, и распознавание нейронной сетью

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

Таблица 4. Результаты тестирования на базе изображений Себастьяна Марселя2_

Класс Число изображения Распознано Точность Ср. Время обработки (мс)

(1) (2) (1) (2) (1) (2) (1) (2)

А 58 39 57 35 98,3% 89,7% 27 28

В 61 41 59 40 96,7% 97,6% 27 27

С 65 47 60 40 92,3% 85,1% 27 27

V 57 38 54 30 94,7% 78,9% 27 27

Five 76 58 75 56 98,7% 96,6% 28 29

Point 65 54 63 50 96,9% 92,6% 27 27

Итог

Точность 96,3% | 90,1%

93,2%

В своей работе, Себастьян Марсель разработал модель CGM (Constrained Generative Model) для распознавания статических поз руки на изображениях, точность распознавания которой составляет 93,4-93,8% на однородном фоне и 74,8-76,1% на сложном фоне. Следует отметить, что точность распознавания, полученная в данной работе (96,3% и 90,1%), превосходит результат автора данной базы Себастьяна Марселя. Таблица 5. Результаты тестирования на базе жестов Кембриджского уни-

верситета

Тип освещения Класс Точность (%) Сред. Точность (%)

ВШИ Плоская 95,2

IF1 Растянутая 98,1 95,9

У-образная 94,5

и Плоская 93,4

Растянутая 97,7 94,7

У-образная 93,1

Ш Плоская 93,6

Растянутая 97,9 94,9

У-образная 93,1

ИМ Плоская 94

I я Растянутая 97,5 94,8

^-образная 92,9

нгти Плоская 94,2

Растянутая 98,1 95,4

1 mi У-образная 93,9

Средняя точность 95,1

При проведении сравнения результатов тестирования на данной базе с использованием наиболее известных методов (Support Vector Machine

2 Столбцы (1), (2) - результаты на выборке с однородным фоном и сложным фоном, соответственно.

(SVM), Relevance Vector Machine (RVM), Canonical corrélations (CC), SpatioTemporal CC (ST-CC), Discriminative ST-CC (ST-DCC), Canonical Corrélations of the S1FT Vectors (SIFT-OC) и S1FT ST-CC with the Discriminative Transformations (S1FT ST-DCC)), лучшие результаты получаются с помощью алгоритма SIFT ST-DCC, который обеспечивает точность распознавания 86%. Таким образом, созданный в работе алгоритм распознавания позы руки показал высокую эффективность по скорости обработки и точности распознавания, которая для Кембриджской базы составляет 95,1%.

В данной главе также приведены результаты тестирования разработанного алгоритма распознавания движения. Алгоритм был обучен для распознавания 29 форм траектории (Рис. 6). Эти формы были выбраны в связи с тем, что они были реализованы в некоторых интерфейсах взаимодействия на основе жестов мыши (mouse gesture-based interface), например, в браузере Opéra, и достаточно просты в использовании для пользователя. На Рис. 7 приведены некоторые результаты тестирования алгоритма

о 1 v j ; -

•b u v г3 in

к - < Ci m ч... , • -, ...

nt û -* > ■ t , " '

¿s t a a ' ' v4j! ' ; j • .'■..- : ■ ,-"■,

r v/az

Рис. 6. Классы форм Рис. 7. Часть результатов тестирования алгоритма

траектории пользователями

(1) (2) (3) (4) (5) (6) (1) (2) (3) (4) (5) (6)

О 60 58 1 1 96,7% Nf 60 57 3 95,0%

1 60 59 1 98,3% Û 60 57 3 95,0%

V 60 57 1 2 95,0% - 60 60 0 100,0%

tf 60 57 3 95,0% > 60 58 2 96,7%

J 60 58 2 96,7% 60 57 3 95,0%

ь 60 59 1 98,3% Zî 60 57 1 2 95,0%

60 57 3 95,0% t 60 59 1 98,3%

и 60 58 2 96,7% А 60 58 2 96,7%

Р 60 57 2 1 95,0% а 60 57 3 95,0%

^ 60 56 2 2 93,3% л 60 57 3 95,0%

2. 60 56 1 3 93,3% г 60 57 3 95,0%

60 59 1 98,3% V/ 60 58 1 1 96,7%

< 60 57 3 95,0% А 60 57 3 95,0%

с: 60 58 2 96,7% Z 60 58 2 96,7%

M 60 57 3 95,0%

Итог: 1740 тестов, правильное распознавание - 1670, нераспознанные - 9, неправильно распознанные -61, точность - 96%.

3 (1) - класс, (2) - количество тестов, (3) - правильное распознавание, (4) - нераспознанные, (5) - неправильно распознанные, (6) - точность.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложен и реализован новый алгоритм распознавания позы руки (hand posture) в видеопотоке на основе использования SURF-дескрипторов, алгоритма /с-средних и многослойной нейронной сети.

2. Разработан новый алгоритм распознавания движения руки (hand motion) в видеопотоке с использованием многослойной нейронной сети, и также идеи упрощения и передискретизации траектории.

3. Создан новый алгоритм распознавания жестов (hand gesture) на основе детектора Джонса-Виолы, трекера CAM-Shift, разработанных алгоритмов распознавания поз и движения руки.

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

5. Реализованное в ходе диссертационной работы программное обеспечение для управления презентациями внедрено в ООО «ARROWHITECH» (г. Ханой, Вьетнам).

ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

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

1. Нгуен Т.Т. Алгоритмическое и программное обеспечение для распознавания фигур с помощью Фурье-дескрипторов и нейронной сети // Известия Томского политехнического университета. - 2010. - Т. 317, № 5. -С. 122-125.-0,26 п.л.

2. Нгуен Т.Т., Спицын В.Г. Распознавание формы руки на видеопоследовательности в режиме реального времени на основе SURF-дескрипторов и нейронной сети // Электромагнитные волны и электронные системы.-2012.-Т. 16, №7.-С. 31-39.-0,8/0,4 п.л.

3. Нгуен Т.Т., Болотова Ю.А., Спицын В.Г. Распознавание жестов на видеопоследовательностях в режиме реального времени на основе иерархически-временной сети // Научный вестник Новосибирского государственного технического университета. - 2012. - №. 2. - С. 33—42. -0,5 / 0,2 п.л.

4. Нгуен Т.Т., Спицын В.Г. Алгоритмическое и программное обеспечение для распознавания формы руки в реальном времени с использованием SURF-дескрипторов и нейронной сети // Известия Томского политехнического университета. - 2012. - Т. 320, №. 5. - С. 48-54. - 0,56 / 0,28 п.л.

Свидетельство на программу для ЭВМ:

5. Спицын В.Г., Нгуен Т.Т. Свидетельство о государственной регистрации программы для ЭВМ № 2012612512 «Hand Recognitor» от 16.05.2012 г. // Реестр программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам. Москва, 2012.

Публикации в других научных изданиях:

6. Нгуен Т.Т. Обнаружение руки в режиме реального времени в видеопотоке с помощью признаков Хаара и Adaboost-классификатора // Материалы XIX Всероссийского семинара «Нейроинформатика, ее приложения и анализ данных». - Красноярск, 2011. - С. 76-79. - 0,2 п.л.

7. Нгуен Т.Т. Метод распознавания фигур с использованием фурье-дескрипторов и нейронной сети // Проблемы информатики. - 2011. -№ 5 (спецвыпуск). - С. 64-69. - 0,26 п.л.

8. Нгуен Т.Т. Обнаружение руки в режиме реального времени в видеопотоке с помощью признаков Хаара и Adaboost-классификатора // Проблемы информатики. - 2011. - № 5 (спецвыпуск). - С. 76-80. -0,25 п.л.

9. Nguyen Т.Т. The Lucas-Kanade Method for Optical Flow // Сборник докладов IV Всероссийской научно-практической конференции «Научная инициатива иностранных студентов и аспирантов российских вузов». -Томск: Изд-во ТПУ, 2011.-Р. 295-296.-0,1 п.л.

Подписано к печати 24.01.2014. Формат 60x84/16. Бумага «Снегурочка». Печать XEROX. Усл. печ. л. 1,0. Уч.-изд. л. 0,89. Заказ 43-14. Тираж 120 экз.

Национальный исследовательский Томский политехнический университет Сипема менеджмента качества Издательства Томского политехнического университета сертифицирована в соответствии с требованиями ISO 9001:2008

ИЗДАТЕЛЬСТВ ОрМПУ. 634050, г. Томск, пр. Ленина, 30 Тел./факс: 8(3822)56-35-35, www.tpu.ru

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

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

0^201457809

Нгуен Тоан Тханг

АЛГОРИТМЫ РАСПОЗНАВАНИЯ ЖЕСТОВ НА ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЯХ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Научный руководитель -доктор технических наук, профессор В.Г. Спицын

Томск-2014

ОГЛАВЛЕНИЕ

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

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

1.1. Понятие жеста................................................................................................13

1.2. Походы к решению задачи распознавания жестов.....................................18

1.2.1. Методы на основе внешности................................................................18

1.2.2. Методы с использованием ЗО модели руки.........................................25

1.2.3. Статистический подход..........................................................................27

1.2.4. Синтактический подход.........................................................................34

1.2.5. Методы отслеживания руки...................................................................35

1.3. Обсуждение и постановка задач...................................................................39

1.4. Выводы по главе.............................................................................................45

Глава 2. Метод распознавания жестов на видеопоследовательностях...............46

2.1. Архитектура комплексного алгоритма распознавания жестов.................46

2.2. Обнаружение руки на видеокадре................................................................50

2.1.1. Признаки Хаара.......................................................................................50

2.1.2. Интегральное изображение....................................................................54

2.1.3. Ас1аВоо81-классификатор........................................................................55

2.3. Трекинг руки на последовательных кадрах................................................57

2.4. Предложенный алгоритм распознавание позы руки..................................60

2.4.1. Метод выделения характерных признаков...........................................63

2.4.2. Кластеризация 81ЖГ-дескрипторов и генерация словаря признаков65

2.4.3. Генерация дескрипторов для нейронной сети.....................................67

2.4.4. Обучение и распознавание в нейронной сети......................................69

2.5. Предложенный алгоритм распознавания движения руки.........................71

2.5.1. Алгоритм Рамера-Дугласа-Пекера........................................................73

2.5.2. Передискретизация и преобразование траектории.............................74

2.5.3. Вычисление дескриптора.......................................................................75

2.5.4. Обучение и распознавание в нейронной сети......................................76

2.6. Выводы по главе.............................................................................................77

Глава 3. Численные эксперименты и анализ результатов распознавания

жестов.........................................................................................................................78

3.1. Эксперименты на созданных выборках.......................................................78

3.1.1. Тестирование на выборке с однородным фоном.................................81

3.1.2. Тестирование на выборке с присутствием других объектов..............84

2

3.1.3. Тестирование на сильно зашумленной выборке..................................85

3.1.4. Выводы.....................................................................................................86

3.2. Тестирование на известных открытых выборках.......................................87

3.2.1. Тестирование на базе статических поз руки........................................87

3.2.2. Тестирование на базе жестов Кембриджского университета............89

3.2.3. Сравнение с другими алгоритмами распознавания поз......................92

3.3. Тестирование алгоритма распознавания движения....................................93

3.4. Выводы по главе.............................................................................................96

Глава 4. Программная реализация системы распознавания жестов...................97

4.1. Описание реализуемой программной системы...........................................97

4.1.1. Общее описание......................................................................................97

4.1.2. Средство программирования.................................................................98

4.1.3. Реализованные классы............................................................................99

4.2. Пользовательский интерфейс программы «Hand Recognitor»................106

4.2.1. Главный интерфейс пользователя.......................................................107

4.2.2. Создание нового набора примитивов формы....................................109

4.2.3. Распознавание движения......................................................................118

4.2.4. Управление компьютерной системой с помощью жестов...............121

4.3. Выводы по главе...........................................................................................125

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

Список источников и литературы.........................................................................127

Список публикаций автора....................................................................................142

Приложение.............................................................................................................144

ВВЕДЕНИЕ

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

В качестве одного из способов обеспечения комфортного взаимодействия с компьютером, человеческая рука может быть использована в качестве интерфейса ввода [3, 71, 131]. Жесты являются мощным каналом связи, который формирует основную часть передачи информации в нашей повседневной жизни. По сравнению с традиционными устройствами ЧМВ, жесты являются менее навязчивым, простым, более удобными и естественным способом взаимодей^ ствия для пользователей. Тем не менее, выразительность жестов все еще остается недостаточно изученной для решения проблемы человеко-машинного взаимодействия.

В последние годы появилась и начала быстро развиваться тенденция использования жестов, особенно жестов руки, как способа взаимодействия с компьютерной системой. Распознавание жестов, таким образом, стало важнейшей частью в ЧМИИ и начало привлекать множество исследователей. Кроме того, разработанные в ЧМИИ технологии также находят применение в других областях, таких как управление роботами, телеконференции, перевод языка жестов (для глухих), управление компьютерными играми, и т.д. В числе пионеров в области распознавания жестов и построения интерфейса на основе жестов можно выделить КиПепЬасИ. С., НиЫееп Е., Кепс1оп А., ()иек, Маре б £). J.,

Moshell M. J., Kobayashi Т., Haruyama S., Krueger M., Kanade Т., Tomasi C., Petrov S., Triesch J., Malsburg C., Rehg J.M., Imagawa K., Baudel Т., Beaudouin-Lafon M.

Для использования человеческой руки в качестве естественного устройства 4MB, применяются перчатки данных, такие как Киберперчатка (Cyber-Glove) [23, 93, 140], окрашенные перчатки [61, 68]. Они применяются для того, чтобы захватить движения рук. Значения углов и пространственного положения руки могут быть измерены непосредственно перчаткой с помощью прилагаемых датчиков. Однако перчатка данных и прилагаемые к ней провода являются неудобными для практического применения пользователями. Кроме того стоимость перчатки данных часто слишком дорога для регулярных пользователей. Разработанный фирмой Microsoft комплекс Kinect позволяет пользователю взаимодействовать с игровой приставкой ХЬох 360 без помощи игрового контроллера через устные команды, позы тела и показываемые объекты или рисунки. Этот игровой «контроллер без контроллера» представлен для консоли ХЬох 360. Комплекс Kinect основан на специальном периферийном устройстве ZCam, которое является разновидностью ГО/^-камеры (Time-of-Flight Camera - время-пролетная-камера)"позволяющей _получать трёхмерную видеоинформацию. Требование специального дорогого устройства и само назначение ограничивает возможность широкого использования Kinect для обычных пользователей.

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

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

5

»

ния, повышенной производительности компьютеров, и также популярности и высокого качества недорогих видеокамер. При этом важным является тот факт, что системы распознавания жестов на основе компьютерного зрения обеспечивают более интуитивный и натуральный канал взаимодействия человека с компьютером. Перспективность данного направления подтверждается результатами исследований авторов Kölsch M., Turk M., Lienhard R., Maydt J., Rittscher J., Blake A., Bradski G., Viola P., Jones M., Isard M., Davis J., Bobick A., Comaniciu D.

*

В настоящее время существуют различные подходы к решению задачи распознавания жестов. Большинство этих подходов воспринимает жест как целую сущность и пытается извлечь соответствующее математическое описание из большого количества обучающих примеров (Campbell L., Kobayashi T., Manresa С., Oka К, Wren С., Wu Y., Yang J.). Эти подходы анализируют жесты рук, не раскладывая их на составные элементы, применение которых могло бы упростить сложность жестов. В результате большинство существующих подходов характеризуются недостаточной скоростью, точностью, надежностью и ограниченным количеством распознанных жестов. В существующих методах также часто требуются специальные условия использования (без других объектов на фоне камеры, постоянное освещение, ношение специальных приборов, и т.д.). Примерами таких систем могут быть «расширенный стол» (Ока и др.), «визуальная панель» (.Zhang и др.), «HandVu» (.Kölsch и Turk), «Pfinder» (Wren и ДР-)-

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

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

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

1. Разработать алгоритм распознавания поз руки (hand posture), способный функционировать в режиме реального времени и инвариантный к аффинным преобразованиям и изменению освещения.

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

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

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

Апробация работы. Основные результаты работы обсуждались и докладывались на следующих симпозиумах, конференциях и семинарах: IV Всероссийская научно-практическая конференция «Научная инициатива иностранных студентов и аспирантов российских вузов» (Томск, 2010); Международная научно - практическая конференция «Интеллектуальные информационно - телекоммуникационные системы для подвижных и труднодоступных объектов» (Томск, 2010); XIX Всероссийский семинар «Нейроинформатика, ее приложения и анализ данных» (Красноярск, 2011);

Основное содержание диссертации отражено в 9 работах, в том числе 4 статьи в изданиях из перечня ВАК, 2 статьи в рецензируемом журнале, 2 доклада на Всероссийских и Международных и конференциях, и одно свидетельство об официальной регистрации программы распознавания жестов для ЭВМ «Hand Recognitor».

Кратко изложим основное содержание работы.

В первой главе приведено общее понятие жестов и популярные таксономии жестов в лингвистике и 4MB, понятие распознавания жестов и интерфейса

на основе жестов. Так же дано новое определение «жеста», «позы», и «движе-

7

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

Во второй главе приведено детальное описание предложенной архитектуры комплексного алгоритма распознавания жестов, реализованного алгоритма обнаружения руки и алгоритма трекинга, разработанного алгоритма распознавания поз руки, и созданного алгоритма распознавания глобального движения. Представлен новый комплексный алгоритм распознавания жестов на видеопоследовательностях в реальном времени, который может распознавать автономных и интерактивных жестов. Предложена двухуровневая архитектура для комплексного алгоритма распознавания жестов, содержащая на первом уровне шаги получения последовательных кадров из видеокамеры, предобработки полученных кадров, и обнаружение руки на видеокадре. На втором уровне выполняется слежение за рукой во времени, распознавание позы и распознавание глобального движения. Предложено применение алгоритма Джонса-Виолы для обнаружения руки в видеопотоке с возможностью функционирования в реальном времени. Алгоритм работает на основе признаков Хаара, интегрального изображения, и каскадного Ас1аВоо51 классификатора. Изложен метод САМ-БЫА для трекинга руки на основе использования цветовой информации кожи. Предложен и реализован алгоритм распознавания позы руки в видеопотоке на основе использования Зб^Р-дескрипторов, алгоритма ^-средних, и многослойной нейронной сети. Создан алгоритм распознавания глобального движения руки в видеопотоке с использованием многослойной нейронной сети.

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

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

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

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

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

9

3. Разработан новый алгоритм распознавания жестов (hand gesture) на основе детектора Джонса-Виолы, трекера CAM-Shifit, предложенных алгоритмов распознавания поз и движения руки, позволяющий распознавать жесты на видеопос�