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

00461

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

Зырянов Александр Владимирович

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

05.13.18 - математическое моделирование, численные методы и комплексы программ

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

- 7 ОПТ

Екатеринбург — 2010

004609877

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

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

Авербух Владимир Лазаревич

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

профессор

Сесекин Александр Николаевич

доктор физико-математических наук, профессор

Мазуров Владимир Данилович

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

учреждение высшего профессионального образования "Южно-уральский государственный университет"

Защита диссертации состоится «20» октября 2010 года в 15 часов на заседании диссертационного совета Д 212.286.10 по защите докторских и кандидатских диссертаций при ГОУ ВПО «Уральский государственный университет им, A.M. Горького» по адресу: 620000, г. Екатеринбург, пр. Ленина, 51, комн. 248.

С диссертацией можно ознакомиться в научной библиотеке ГОУ ВПО "Уральский государственный университет им. А.М. Горького",

Автореферат разослан «jj-Г.» сентября 2010 года.

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

В.Г. Пименов

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

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

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

За последние десять лет было создано (и продолжают создаваться) большое количество новых средств ввода. Исследования и разработки активно ведутся в таких научных центрах, как Массачусетский технологический институт, Мэрилендский университет, Оксфордский университет, университет города Осака, Стэнфордский университет, Торонтский университет, а также исследовательские центры таких компаний как Apple, Microsoft, Nintendo, Sony. В России подобные работы выполняются, к примеру, в МГТУ им. Н.Э. Баумана.

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

модействии при помощи интерфейса, а на взаимодействии с самим интерфейсом.

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

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

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

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

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

1. Разработана новая методика определения положения объекта в пространстве, на основе распознавания в кадре источника света, закреплённого на объекте. Для эффективной работы данного метода достаточно использовать простые аппаратные средства (веб-камера и фонарик в качестве источника света).

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

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

4. Разработана программная библиотека реализующая все созданные алгоритмы. Данная библиотека позволяет создавать простой, удобный и легко расширяемый пользовательский интерфейс, который может успешно применяться как при работе на персональном компьютере, так и при работе с «большими» экранами.

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

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

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

Апробация работы. Результаты диссертации были представлены на X и XI международном семинаре по супервычислениям и

математическому моделированию (Саров, 2008, 2009), третьей международной конференции «Информационно-математические технологии в экономике, технике и образовании» (Екатеринбург, 2008) и международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2009)» (Нижний Новгород, 2009).

Публикации. Основные результаты диссертации изложены в 8 работах, список которых приведён в конце автореферата. Из них 2 опубликованы в ведущих рецензируемых научных журналах, определеных ВАК. Результаты работ получены диссертантом самостоятельно.

Структура и объём диссертации. Диссертация состоит из введения, 5 глав, заключения и списка литературы. Объём диссертации составляет 119 страниц, включая библиографический список из 43 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

4. Устройство ввода должно быть простым с технической точки зрения (простота установки устройства ввода и лёгкость его повседневного использования) и, по возможности, недорогим.

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

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

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

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

ВО ВТОРОЙ ГЛАВЕ описывается разработанный метод ввода трёхмерных жестов, приводится алгоритм вычисления положения маркеров в пространстве и доказывается теорема о вычислительной сложности данного алгоритма. Также описываются результаты исследования качества работы алгоритма, как при помощи тестовых замеров, так и с участием потенциальных пользователей.

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

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

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

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

V (*2 — хх)2 + (Уг — У1)2

л/(*2-*1)2 + (У2-У1)2

__СгУУ_

2 ~ Л*2-*1)г + (У2-У1)г где АВ - самая длинная диагональ эллипса, О - центр эллипса,

- высота и ширина кадра в пикселях соответственно, С[ и с2 -константы, задающие чувствительность ввода (рис. 1).

Теорема 1: Если количество используемых источников света не превышает VлЩ то вычислительная сложность алгоритма определения положения источников света в пространстве составляет 0(МЫ), где MxN - разрешение камеры.

Рис. 1 - Эллипс светового пятна

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

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

В ТРЕТЬЕЙ ГЛАВЕ рассматривается проблема создания пользовательского интерфейса, который бы одновременно обладал богатыми возможностями и обеспечивал бы непосредственное взаимодействие. В главе приводится алгоритм распознавания трёхмерных жестов и доказывается, что данный алгоритм обладает наименьшей вычислительной сложностью.

Существует различные виды и классификации жестов. В нашем случае, жест С - это траектория перемещения рук пользователя в пространстве. Т.к. мы снимаем кадры с какой-то частотой, данная траектория дискретизирована, т.е. представлена в виде последовательности трёхмерных точек: (хь уь г,), (х2, у2, 22), ... , (хп, уш т^). Распознавание жеста состоит в вычислении расстояния между жестом в и каждым из базовых шаблонов Вх, В2,... , Вш. (которые также представляют собой последовательность трёхмерных точек). Допустимые преобразования, метрики расстояния и алгоритмы, находящие эти метрики, могут быть самыми различными. Критериями того, какой метод лучше, как правило, являются скорость работы и процент ошибок распознавания.

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

Выделение жестов в непрерывном пользовательском вводе осуществляется следующим образом. Каждый раз, когда появляются новые данные (т.е. каждый кадр), мы предполагаем, что пользователь только что завершил ввод жеста, и пытаемся его распознать. Таким образом, конец траектории - это последняя введённая точка. Начало траектории — это какая-то точка в прошлом, которая может быть определена лишь по косвенным признакам. Эксперимент показал, что равномерное разбиение (в качестве начал берутся точки, расположенные с шагом 1/8 секунды) позволяет уверенно распознавать вводимые пользователем траектории. Такой подход также гарантирует, что если мы ограничим продолжительность жеста, то число запусков алгоритма распознавания будет ограничено константой.

В качестве основы алгоритма распознавания жестов используется "$1 Gesture Recognizer Algorithm", предложенный Jacob О. Wobbrock, Andrew D. Wilson, Yang Li. Данный алгоритм был выбран в качестве основы, поскольку он обладает очень высокой точностью (более 97% при использовании единственного шаблона для каждого жеста и более 99% при использовании трёх шаблонов для каждого жеста), высокой скоростью работы и модульной структурой, позволяющей производить модификации.

Поскольку "$1 Gesture Recognizer Algorithm" умеет распознавать лишь двумерные жесты, была выполнена модификация, позволившая работать данному алгоритму и в трёхмерном пространстве. Тот факт, что человеческие жесты хорошо укладываются на плоскость либо вообще выполняются вдоль одной прямой, позволяет существенно упростить модифицированный алгоритм.

Алгоритм распознавания жестов состоит из 7 шагов:

1. На основе траектории жеста G, представленной в виде последовательности точек (xi, у и zj), (х2, у2, Z2), ... , (х„, у„, zj, построим новую траекторию Р состоящую ровно из 64 точек: (x'i, y'i, z'O, (х'2, у'2, z'2),..., (х'б4, у'64, z'M) таким образом, чтобы:

a. (x'i,y'i,z'i) = (xi,yi,z1)

b. (х'64) у'б4, z'm) = (zn, уп, zn)

c. L(i,i+l) = L(jj+I) V i,j = 1, ...,63, где L(/,i+J) -расстояние между точками / и i+1 траектории Р вдоль ломанной, образуемой последовательностью точек из G.

2. Найдём центр траектории C{x0,yQ, zQ) = 1ЩА

3. Построим набор векторов К, = (х i - Xq, у, - у0, z'i - Zq) и упорядочим их по убыванию длины. Обозначим = (х i - Хо, у i - уо, z'i - Zo).

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

4.1. Найдём вектор 5 = £?=iPM(^)> где PM(V) возвращает V, если

сумма координат V положительна, и — V в противном случае.

—♦

4.2. Если Vi = 1, ...,64 угол между векторами Ц и S отличается от 0° или 180° не более чем на 10°, то жест G считается линейным. Иначе жест G считается двумерным.

5. Если жест двумерный, то вычисляется плоскость наилучшего приближения при помощи метода наименьших квадратов, и находится её нормальный вектор N. Если жест линейный, то данный шаг пропускается.

6. Для каждой базовой траектории соответствующего типа (линейная/двумерная) производится следующее:

6.1. Для линейного жеста вычисляется угол между векторами S (базовой и пользовательской траекторий). Для двумерного вычисляется угол между векторами N. Если найденный угол превышает 45°, то дальнейшие сравнения с данной базовой траекторией не производятся.

6.2. В случае двумерного жеста построим ортонормированные ба-

-1 f

зисы для пользовательской и базовой траекторий из векторов N,

[ЛГ(|Ц где Т = W — Kl ^ a(N, W) - угол между векторами,

_ —* . —»

[а,Ь] - векторное произведение а и Ь. Далее, найдём матрицу перехода М из базиса пользовательской траектории в базис базовой траектории. Вычислим Qt = М\f.

В случае линейного жеста найдём матрицу поворота М вокруг вектора [¿польз", 5баз'] на угол Вычислим Q( = М%

6.3. Найдём к - значение максимальной по модулю координаты среди всех Qi- Если k < Cmin, где Спш - некоторая константа, то сравнение не производится. Иначе вычислим Ql; где С - константа.

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

иска золотого сечения». Поиск оптимального угла выполняется в диапазоне [-45°, 45°] с шагом 2°. Вращение выполняется вокруг 5баз (линейный случай) или N¿33 (двумерный случай). Расстояние между траекториями вычисляется по формуле:

где В, - ьая точка траектории, получаемой из базовой траектории, путём применения к ней преобразований, описанных в пунктах 1, 2, 3, 4,5 и б.З данного алгоритма.

6.5. Вычисляется степень похожести в процентах по формуле:

Если г < 0, то г = 0.

7. Среди всех г выбирается максимальная т^. Если это значение превышает минимальный порог, то введенная пользователем траектория считается распознанной. Значение гтах и номер траектории, которому данное значение соответствует, являются результатами работы данного алгоритма.

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

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

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

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

64

I

/=1

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

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

В ЧЕТВЁРТОЙ ГЛАВЕ рассматривается проблема калибровки оптических камер. Приводится алгоритм автоматической калибровки камер, не требующий от пользователя выполнения каких-либо специальных действий. Данный метод не накладывает никаких ограничений на камеры, умеет корректировать результаты калибровки в процессе работы, и выполняется на три порядка быстрее традиционных методов. Показывается, что при использовании данного метода задача калибровки является вычислительно устойчивой. Также доказывается теорема о вычислительной сложности алгоритма.

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

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

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

Р1хз _ ^зхз

+ С-

1X3

где М - матрица поворота камеры, С - координаты центра камеры, f - фокусное расстояние камеры, I - числовой коэффициент. Параметры М, С и £ определяются в процессе калибровки, параметр 1 вычисляется в процессе работы путём сопоставления кадров с разных камер (выполняется триангуляция). Что же касается, собственно, калибровки, то различных методов и алгоритмов существует достаточно много. В общем случае калибровка сводятся к решению следующей задачи:

Имеется множество координат (*/(&), у/(Дс)), где I - индекс точки на изображении камеры номер j во время к-ой демонстрации эталонного объекта. Необходимо найти такие С\ £ и ^(к), чтобы:

для всех к и цФг. Иными

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

2. Количество различных значений во множестве

х&У

1. г'ч(к)м1 Ф 4(к)М1 у/ад

и \ //

]Лк)м1

х{(кУ •у

у! (к) + С'

1// /

не превышает количества использу-

емых при калибровке маркеров для каждого значения к.

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

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

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

Г*1

Р3Х1 = /Мзхз

+ С

3X1

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

Пусть имеются две камеры: камера 1 откалибрована (т.е. известны М(1), С(1) и f(l)), а камера 2 не откалибрована (т.е. М(2), С(2) и f(2) не известны). Пусть обе камеры наблюдают за перемещение маркера в течение какого-то времени. Мы получим два упорядоченных по времени множества координат {(х,(1), yi(l), z,(l))} и {(Xj(2), у;(2), z,(2))}. Выберем q, г, s, t таким образом, чтобы матрицы

0. *г(0

т =

У,С О 1

уЛ о

zr(ï) 1

у»(0

Zs(ï)

*t(0' Ус (О Zt(0 1

, где i=l, 2, имели ранг 4.

Пусть а = /М, и матрица Б получается из матрицы А путём присоединения к ней справа матрицы С, т.е. Озх4=[А С]. Тогда:

где

У 2

.1.

P = fM

+ с

-0

+ C = D

Следовательно Откуда находим:

Û(1)N(1) = D(2)N(2)

D(2) = D(1)WC1)A^(2)_1 Зная D(2) мы получаем А(2) и С(2). Зная А(2), мы, из условия det(M)=l, находим М(2) и {(2). Таким образом, мы нашли все неизвестные параметры, выполнив калибровку за единственную итерацию.

Необходимость найти четыре точки такие, чтобы ранг матрицы N равнялся 4, не является существенной проблемой, поскольку этому

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

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

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

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

Будем описывать каждую камеру следующим набором параметров:

* Положением в абсолютной системе координат С3х1.

* Матрицей перехода из системы координат камеры в абсолютную систему координат А3!(3.

* Набором историй перемещения источника света за последние

пять секунд. История перемещения - это множество пар

,£ , где

I - момент времени, в который были зафиксированы координаты

В

Каждая история находится в состоянии «активна» или «не активна».

* Состоянием «откалибрована»/«не откалибрована».

* Степенью недоверия к камере Ь (неотрицательное целое число). Первую подключенную камеру примем в качестве точки отсчёта:

ГО] [1 О , А= 0 1

Ь=0,0

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

* Положение в абсолютной системе координат Р.

* Состояние «свободен»/«не свободен».

* Группа, с которой связан источник света (если он находится в состоянии «не свободен»).

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

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

* Состояние «активна»/«пассивна».

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

Процедура 1. Цикл работы системы.

Всякий раз, когда новые данные поступают с одной из камер (назовём её Саш), выполняются следующие действия:

1. Новые положения

и текущий момент времени I обозревае-

мых камерой Сат источников света записываются в соответствующие истории перемещения. Изменённые истории переходят в состояние «активна»; все остальные истории этой камеры - в «не активна».

2. Из всех историй перемещения («активных» и «не активных») камеры Сат удаляются устаревшие данные - элементы, I которых отличается от текущего момента времени более чем на 5 секунд.

3. Если камера находится в состоянии «не откалибрована», то:

3.1. Строится список Б историй перемещения, в который включается все «активные» истории перемещения камеры Саш.

3.2. Строится список Ь историй перемещения, в который включается все «активные» истории перемещения всех откалиброванных камер.

3.3. Для каждой пары значений из списков Б и Ь выполняется процедура калибровки (см. далее).

4. Если камера Саш находится в состоянии «откалибрована», то выполняется процедура вычисления абсолютного положения источников света в пространстве (см. далее).

5. Для всех откалиброванных камер, у которых Ь>0, происходит уменьшение степени недоверия на единицу. Степень недоверия первой камеры уменьшается на пять единиц. Отрицательное значение заменяется на ноль. Если в системе осталась лишь одна откалибро-ванная камера, то её степень недоверия выставляется на ноль.

6. Среди всех откалиброванных камер, у которых Ь>15, случайно выбирается одна. Выбранная камера переходит в состояние «не откалибрована».

Процедура 2. Процедура калибровки.

На вход подаются две истории: для откалиброванной камеры С и не откалиброванной камеры и. Истории представляют собой набор пар (Р„ У, где Р1 - положение источника света в пространстве в момент времени Ъ. Необходимо выяснить, соответствуют ли эти наборы одному и тому же источнику света, и, если возможно, произвести калибровку камеры. Делается это следующим образом:

1. Если в истории есть пропущенные кадры (камера не видела источник света), то история усекается до последнего пропущенного кадра. Кадр считается пропущенным, если промежуток времени между двумя соседними элементами истории перемещения в 1.5 раза превышает частоту кадров данной камеры. Например, если история состоит из кадров 1,4, 7, 8 и 9, то в результате усечения мы получим историю из кадров 7, 8 и 9. Также из истории камеры и удаляются все пары (Р„ ^ у которых г, меньше минимального значения t в истории камеры С.

2. Производится синхронизация историй путём вычисления положений источника света для камеры и в моменты времени из истории камеры С на основе линейной интерполяции. В результате мы получаем два множества положений источника света в пространстве относи-

тельно каждой из камер. Эти множества будут синхронизированы по времени. Обозначим их как PU={pu^} и РС={рс^}.

3. Найдём sc = —'. su = ^ р"'. Затем построим множества век-

п ___ п_ ___

торов VU={vu,} и VC={vq}, где vut = рщ - su, vc[ = рс[ — sc.

4. Среди всех возможных пар индексов (j, к), где 1 ^ /, к < п, выбираются те, которые удовлетворяют следующим условиям:

* Длины векторов vu}, ШЦ, vcj и превышают 30 единиц.

* Угол между векторами щ и ищ лежит в пределах [45°, 135°].

* Угол между векторами vcj и vc£ лежит в пределах [45°, 135°].

Для каждой найденной пары индексов строятся базисы

BU=(vUj, ШЦ, [щ, рщ]) и ВC=(vcJ, vcZ, \ус], vc£]), где [а,Ь] - векторное произведение а и Ь. Затем вычисляется матрица перехода М из базиса BU в базис ВС. И наконец, вычисляется значение

и = —--— где |а| — длина вектора а, А(С) - матрица перехода откалиброванной камеры С.

Из всех найденных D выбирается минимальное Dmj„ (этому значению соответствует матрица перехода Мгаш). Если D^ - превышает максимальный порог, или подходящих пар индексов (j, к) не было найдено, то калибровка не производится (камеры наблюдают разные фонарики или перемещения фонарика слишком малы). Если Dmm - не превышает максимальный порог, и для всех D S Dmin + Clt где Ci -некоторая константа, выполняется

\mmin — ^ С2(0 - Dmin~), где т1' - элементы матрицы М, С2 - некоторая константа, то камера U переходит в состояние «откалибрована», а её параметры выставляются следующим образом:

* Матрица перехода из системы координат камеры в абсолютную систему координат A(U)=A(C)Mmin

* Абсолютное положение камеры C(U) = С(С) + A(U)su - A(C)sc

* Степень недоверия камере b(U)=0.

Процедура 3. Процедура вычисление абсолютных положений источников света в пространстве.

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

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

1. Для каждого обозреваемого камерой Сат источника света про-

гХл

изводится вычисление абсолютного положения Р = А

+ С.

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

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

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

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

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

6. Все «пассивные» группы удаляются. Входившие в эти группы источники света помечаются как «свободные».

Теорема 3: Процедура калибровки камер является вычислительно устойчивой.

Теорема 4: Вычислительная сложность алгоритма составляет 0(1^(С) +/9Л где С - количество используемых камер, ^ - количество используемых источников света. Если все камеры откалиброваны, то вычислительная сложность составляет 0(Р*(С+Р2)).

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

Время, необходимое на калибровку 16 камер составляет примерно 0.1 секунды, что на три порядка быстрее, чем при использовании стандартных методов. Также эксперименты показали, что система из 16 камер и двух источников света способна работать на обычном ноутбуке в реальном времени (в том числе и выполнять калибровку) с частотой порядка 200 кадров в секунду. На перекалибровку уходит столько же времени, сколько и на первоначальную калибровку, каких-либо провалов в производительности перекалибровка не вызывает.

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

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

В ПЯТОЙ ГЛАВЕ производится сравнение разработанных методов с существующими решениями и приводится описание программной библиотеки, реализующей все описанные в диссертации алгоритмы.

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

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

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

Все предложенные в диссертации алгоритмы реализованы в виде dll библиотеки на Microsoft Visual Studio 2008 .NET. Данная библиотека содержит 2 публичных класса, 13 публичных процедур, 6 публичных событий и 13 публичных свойств. Также было разработано приложение для создания шаблонов жестов, позволяющее задавать шаблон как путём ввода координат точек, так и при помощи источника света. Общее количество строк кода, написанное в рамках работы над данным проектом, превышает десять тысяч.

В ЗАКЛЮЧЕНИИ формулируются основные результаты работы, перечисляются возможности разработанных алгоритмов и интерфейса и рассматривается вопрос применимости созданных методов и алгоритмов помимо программ математического моделирования.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. В.Л. Авербух, A.B. Зырянов. Методы манипуляций объектами в трёхмерных визуальных средах. // Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2009 г., Вып. 3, стр. 58-69.

2. Зырянов A.B. Самокалибрующаяся масштабируемая система ввода трёхмерных жестов // Системы управления и информационные технологии, 1.1(39), 2010 г. стр. 135-139.

ДРУГИЕ ПУБЛИКАЦИИ

3. Зырянов А. В., Авербух В. Л. Интерфейс на основе жестов для взаимодействия с виртуальными средами. // X международный семинар по супервычислениям и математическому моделированию. 29 сентября - 3 октября 2008 г. Тезисы докладов, стр. 73-74.

4. Зырянов, A.B. Методы ввода и распознавания жестов для взаимодействия с виртуальными средами. // Третья международная конференция "Информационно-математические технологии в экономике, технике и образовании". 20-22 ноября 2008 г., стр. 282-283.

5. Зырянов, A.B. Использование языка жестов для манипуляций с трёхмерными объектами в системах научной визуализации. // Параллельные вычислительные технологии 2009: Труды международной научной конференции. 30 марта - 3 апреля 2009 г., стр. 485-489.

6. Зырянов, A.B. Интерфейс на основе жестов для манипулирования трёхмерными виртуальными объектами и его применение в системах научной визуализации. // XI международный семинар по супервычислениям и математическому моделированию. 5-9 октября 2009 г. Тезисы докладов, стр. 70-71.

7. Зырянов A.B. Самокалибрующаяся масштабируемая система ввода трёхмерных жестов // Информационные технологии моделирования и управления, №1,2010 г. стр. 42-49.

8. Авербух В.Л. Байдалин А.Ю., Бахтерев М.О., Васёв П.А., Зырянов A.B., Казанцев А.Ю., Манаков Д.В. К обоснованию проекта визуализационной компоненты виртуального испытательного стенда

3/0

// Параллельные вычислительные технологии (ПаВТ'2010): Труды международной научной конференции (Уфа 29 марта - 2 апреля 2010 г.). — Челябинск. Издательский центр ЮУрГУ. стр. 378-386

Подписано в печать 07.09.2010 г. Формат 60 * 84 х 16. Бумага офсетная. Усл. печ. л. 1,5, Заказ № 132. Тираж 100.

Отпечатано в типографии ИПЦ

«Издательство УрГУ». г. Екатеринбург, ул. Тургенева, 4.

Введение.

Глава первая. Обзор существующих решений.

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

Методы ввода трёхмерных жестов без использования манипуляторов.

Методы калибровки систем оптического захвата движений.

Выбор метода захвата движений для «хорошего» интерфейса.

Глава вторая. Аппаратная составляющая интерфейса.

Интерфейс фонарика.

Испытание №1: точность ввода и скорость работы.

Испытание №2: взаимодействие с объектами.

Глава третья. Пользовательский интерфейс на основе жестов.

На пути к распознаванию жестов.

Алгоритм сравнения двух траекторий.

Распознавание жестов.

Пользовательский интерфейс на основе жестов.

Испытание №3: пример интерфейса.

Глава четвёртая. Алгоритм автоматической калибровки оптических камер.

От персонального компьютера к большим экранам.

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

Калибровка камер и интерфейс фонарика.

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

Итоговая схема «Интерфейса фонарика».

Глава пятая. Сравнение с существующими решениями.

Сравнение с существующими решениями.

Сравнение интерфейса фонарика и мыши.

Описание программного комплекса.

На пути к идеальному интерфейсу

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

Командная строка — это первый интерфейс, который не просто сохранился до настоящего времени, но и продолжает активно использоваться. Пользовательский ввод осуществляется путем набора текстовых команд; вывод — путём выдачи на экран текстовых сообщений. В качестве команд используются глаголы действия (copy, rename и прочее), предложения, содержащие такие глаголы (show ip route), либо просто названия (telnet). Подобный подход существенно облегчал жизнь тем, кто владел английским языком. Остальным же по-прежнему приходилось запоминать (ввод) и интерпретировать (вывод) непонятные последовательности символов.

В конце прошлого века на смену командной строке пришел графический интерфейс. Графические интерфейсы состоят из меньшего набора примитивов (кнопка, подпись и тому подобное против примитивов «имя команды»), а сами примитивы, за счет графической составляющей, отличаются друг от друга гораздо сильнее, чем одна команда от другой (скажем, remove и rename). Отсутствия языковой привязки и использование универсальных метафор (вроде папок с документами) делает графический интерфейс интернационально доступным языком. И всё же, несмотря на массу преимуществ, графический интерфейс — это по-прежнему искусственный язык, который пользователь должен освоить для того, чтобы общаться с компьютером. И устранить этот недостаток можно лишь одним путём: научив компьютер понимать язык человека.

Согласно [12] человеческое общение может быть разделено на три составляющие: текстовое сообщение, голосовая интонация и, наконец, мимика и жесты. Для обеспечения полноценного взаимодействия на естественном языке (т.е. без длинного перечня запрещённых к употреблению слов, без чёткого синтаксиса, без запрета на иронию и так далее) необходимо в полном объёме реализовать понимание компьютером каждой из трёх составляющих. Иными словами, требуется создание человекоподобного искусственного интеллекта. Подобные работы велись и продолжают вестись, но пока что они далеки от полного завершения.

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

Проблема манипулирования объектами в трёхмерных визуальных средах

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

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

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

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

Проблема пользовательского интерфейса для «больших» экранов

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

За последние десять лет было создано (и продолжают создаваться) большое количество новых средств ввода. Исследования и разработки активно ведутся в таких научных центрах, как Массачусетский технологический институт, Мэрилендский университет, Оксфордский университет, университет города Осака, Стэнфордский университет, Торонтский университет, а также исследовательские центры таких компаний как Apple, Microsoft, Nintendo, Sony. В России данной проблемой занимается, в частности, Институт Проблем Управления РАН. Новые средства ввода (и связанные с ними новые пользовательские интерфейсы) гораздо лучше подходят для взаимодействия с «большими» экранами, однако и они не лишены тех или иных недостатков.

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

Актуальность работы

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

Данную задачу активно пытаются решать как путём улучшения интерфейсов при помощи новых метафор взаимодействия (например, [43]), так и путём создания новых методов ввода трёхмерных жестов (например, [21]). Вместе с тем, метафоры — это абстракции, которые не позволяют взаимодействовать с объектом так, как если бы он находился прямо перед нами. Что же касается методов ввода трёхмерных жестов, то они с большим трудом масштабируются для работы с большими экранами (либо не масштабируются вовсе) из-за проблемы калибровки.

Цель работы

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

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

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

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

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

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

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

Заключение

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

Основными результатами данной работы являются:

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

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

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

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

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

Алгоритм распознавания вводимых пользователем жестов основан на $1 Gesture Recognizer Algorithm, и унаследовал от него высочайшую точность (более 99%), низкую ресурсоёмкость и отсутствие обучения алгоритма под конкретного пользователя. Созданную модификацию также отличает способность выделять жесты в непрерывном пользовательском вводе, т.е. распознавать несколько вводимых подряд (т.е. без паузы) жестов, а также находить моменты перехода от простых перемещений к целенаправленному жесту.

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

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

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

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

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

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

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

Отдельные элементы интерфейса фонарика могут применяться и за пределами взаимодействий с трёхмерными виртуальными объектами. Определение положений фонариков в пространстве можно использовать в обучающих и игровых программах (как метод взаимодействия) или, к примеру, для отслеживания положения объекта в пространстве при использовании инерциального или механического Motion Capture. Распознавание жестов можно использовать вместе с другими методами ввода движений, а также применительно к двумерным интерфейсам (например, сенсорным экранам). Метод калибровки можно использовать для калибровки оптических камер и за пределами интерфейса фонарика, хотя при этом мы лишимся возможности коррекции результатов калибровки по ходу работы.

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

1. B.JI. Авербух, A.B. Зырянов Методы манипуляций объектами в трёхмерных визуальных средах // Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2009 г. Вып. 3. стр. 58-69.

2. Девятков В.В., Алфимцев А.Н. Распознавание манипулятивных жестов. Сер. Приборостроение // Вестник МГТУ им. Н.Э.Баумана. Москва : 2007. Вып. 3 : Т. 68. стр. 56-75.

3. Зырянов А.В Самокалибрующаяся масштабируемая система ввода трёхмерных жестов // Системы управления и информационные технологии. 2010 г. 1.1(39). стр.135-139.

4. Зырянов А.В. Самокалибрующаяся масштабируемая система ввода трёхмерных жестов // Информационные технологии моделирования и управления. Воронеж : Научная книга, 2010 г. 1. стр. 42-49.

5. Adam Brown, Auckland Institute of Studies The use of nonverbal features in teaching phonetics.http://www.phon.ucl.ac.ulc/ptlc/proceedings/ptlcpaper24e.pdf.

6. B. Gutemberg Optical Motion Capture: Theory and Implementation, http ://ranger.uta.edu/~guerra/Guerra-Fi lhoRITAO 5 optical .pdf.

7. Barbara Tversky, Sandra Lozano Gestures Augment Learning in Communicators and Recipients.http://spatiallearning.org/bibliographypdfs/tverskylozanogesture.pdf.

8. Bernd Froehlich, Jan Hochstrate, Verena Skuk, Anke Huckauf. The

9. GlobeFish and the GlobeMouse: Two New Six Degree of Freedom Input Devices for Graphics Applications // Proceedings of the SIGCHI conference on Human Factors in computing systems. Montreal, Quebec, Canada : SIGCHI, 2006 г. стр. 191-199.

10. Callgraph. http://sourceforge.net/projects/callgraph/.

11. Carlo Colombo, Alberto Del Bimbo, Alessandro Valli Visual capture and understanding of hand pointing actions in a 3-D environment // IEEE Transactions on Systems, Man, and Cybernetics, Part В 33(4). 2003 г. стр. 677-686.

12. Grow Ch., Gordon I., Stuart R. D., Adalja A. Motion Capture as a Means for Data Acquisition.http://vizproto.prism.asu.edu/datacapture/motioncapture 1 /.

13. Jacob O. Wobbrock, Andrew D. Wilson, Yang Li Gestures without Libraries, Toolkits or Training: A $1 Recognizer for User Interface Prototypes // Symposium on User Interface Software and Technology. Newport, Rhode Island, USA. 2007 г. стр. 159 168.

14. Jakub Segen, Senthil Kumar Look ma, no mouse! // Communications of the ACM. July 2000 г. Volume 43 , Issue 7. стр. 102-109.

15. Jan Ciger Mario Gutierrezy, Frederic Vexoz, Daniel Thalmannx The Magic Wand // Proceedings of the 19th spring conference on Computer graphics. 2003 г. стр. 119-124.

16. JavaScript $1 Unistroke Recognizer. http://depts.washington.edu/aimgroup/proj/dollar/.

17. Karam M. and schraefel, m. c. A Taxonomy of Gestures in Human Computer Interactions // Technical Report ECSTR-IAM05-009, Electronics and Computer Science, University of Southampton. 2005 г.

18. M. Furniss Motion Capture. http://web.mit.edu/cormn-fomm/papers/furniss.html.

19. Maletsky L. Junyi Sun, Morton Ni. Accuracy of an optical active-marker system to track the relative motion of rigid bodies // Journal of Biomechanics. 2007 г. №3 : Т. 40. стр. 682-685.

20. Malik S., Ranjan, A. and Balakrishnan, R. Interacting with large displays from a distance with vision-tracked multi-finger gestural input // in Proc. UIST. 2005 г. стр. 43-52.

21. Martin Hachet, Pascal Guitton, Patrick Reuter, Florence Tyndiuk The

22. CAT for efficient 2D and 3D interaction as an alternative to mouse adaptations // Proceedings of ACM SIGGRAPH 2004. Volume 23, Issue 3. August 2004 r.

23. MilIer N., Jenkins, O. C., Kallmann, M., Matric, M. J. Motion capture from inertial sensing for untethered humanoid teleoperation. // Proceedings of International Conference of Humanoid Robotics. Nov 2004. Los Angeles : CA. CTp. 547-565.

24. Motion capture. http://en.wikipedia.org/wiki/Motioncapture. 30.0ptical Motion Capture Systems, http://www.metamotion.com/motioncapture/optical-motion-capture-1 .htm.

25. Philip A. Tresadern, Ian D. Reid Camera calibration from human motion // Image and Vision Computing. June 2008 r. Volume 26, Issue 6. CTp. 851862.

26. Project Natal. http://www.xbox.com/en-US/live/projectnatal/.

27. Project Natal. http://en.wikipedia.org/wiki/ProjectNatal.

28. Project Natal, http://www.gametrailers.eom/game/project-natal/l 1397.

29. Stanford Markerless Motion Capture Project.www.stanford.edu/~stefanoc/Markerless/Markerless.html. 37.Svoboda Tomas A Software for Complete Calibration of MultiCamera Systems // Talk given at MIT CSAIL. Jan 25, 2005 r.

30. The Wand Company, http://thewandcompany.com.

31. Tomas Svoboda, Daniel Martinec, and Tomas Pajdla A convenient multicamera self-calibration for virtual environments // PRESENCE: Teleoperators and Virtual Environments. 14(4), August 2005 r. CTp. 407-422.

32. Wan-Ning Wu, Yen-Liang Wu, Ching-Chien Lin, June-Hao Hou, Hua-Lun Liang, Yu-Tung Liu 3D User Interface Study in the VR Cave. http://www.arch.nctu.edu.tw/works/pdf/publish/caadria2006379.content.pdf.

33. Wii Remote. http://en.wikipedia.org/wiki/WiiRemote.

34. Yagci Enver 3D Stylus: an Intuitive 3D Pointer for Volumetric Radiological Data. http://www.vavlab.ee.boun.edu.tr/pubs/Thesis-Reports/3DstylusThesis.pdf.

35. Yusuke Tomozoe, Takashi Machida, Kiyoshi Kiyokawa, Haruo Takemura Unified Gesture-Based Interaction Techniques for Object Manipulation and Navigation in a Large-Scale Virtual Environment // IEEE Virtual Reality Conference 2004 (VR 2004).