itmai Sep 15 2020 at 16:36

Tangible user interface: распознавание объектов при работе с multi-touch системой

11 min

1.6K

IT-центр МАИ corporate blogAlgorithms*Interfaces*C#*

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

Заметка от партнера IT-центра МАИ и организатора магистерской программы “VR/AR & AI” — компании PHYGITALISM.

При решении научных, образовательных или бизнес-задач, часто возникает проблема поиска наиболее простой и понятной визуализации сложных процессов и данных. Сейчас эта проблема решается посредством компьютерных технологий и мобильных устройств. Один из подходов для взаимодействия человека с цифровой информацией — tangible user interface (TUI) или осязательный интерфейс пользователя.

В реальности мы изменяем наше окружение физически, передвигаем/расставляем/деформируем объекты и понимаем, как наши действия повлияют на их состояние. TUI позволяет, аналогично с реальностью, посредством привычного влияния на физические объекты, взаимодействовать с цифровой информацией, что делает его интуитивным и естественным интерфейсом.
Именно поэтому мы использовали TUI в одном из наших проектов — Phygital Platform для Лаборатории Касперского. Было необходимо доступно показать работу сложной кибер-физической системы и привлечь к продукту наибольшее внимание лидеров производственных компаний.

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

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

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

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

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

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

Установка и данные

В данном проекте мы использовали рамку G5S (Ultra-Slim) Multi-Touch Screen, способную фиксировать 32 касания одновременно. С помощью TUIO протокола можно получать информацию о точках касания (курсорах). Нам будут необходимы следующие поля:

 {"Id":15237,
     "Timestamp":397449,
     "Touches":[{
                    "Id":0,
                    "Position":{
                        "X":0.480208337,
                        "Y":0.5842593},
                    "Acceleration":{
                        "X":0.00208333344,
                        "Y":0.00370370364},
                    "Type":1},
                 {  
                    "Id":1,
                    "Position":{
                        "X":0.4859375,
                        "Y":0.484259248},
                    "Acceleration":{
                        "X":0.00208333344,
                        "Y":0.00370370364},
                    "Type":0},
                {
                    "Id":2,
                    "Position":{
                        "X":0.5140625,
                        "Y":0.551851869},
                    "Acceleration":{
                        "X":0.00208333344,
                        "Y":0.00370370364},
                    "Type":0}],
     "Count":3}

ID события (апдейта);
Id (уникальный идентификационный номер курсора);
Position координаты курсора (по оси X и Y);
Type тип курсора, может принимать три значения (0 новый курсор; 1 касание продолжается, курсор продолжает быть зарегистрированным; 2 курсор пропадет на следующей итерации);
Count количество курсоров

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

Длины сторон маркера при вращении, измеряемые в нормированных координатах.

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

Очевидно, что рамка не 100% точно определяет координаты на протяжении сессии. Для корректного сравнения величин и подбора порога мы проанализировали данные сессии движения курсоров.

$MAD = \frac{1}{n}\sum_{i=1}^n|L_{i} - \overline{L}|$

$\overline{L} = \frac{1}{n}\sum_{i=1}^n L_{i}$

$D = \underset{i}{\operatorname{\max {L_i}}} - \underset{i}{\operatorname{\min {L_i}}}$

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

Изменение расстояния между ножками маркера во время сессии.

Если аналогичным образом проанализировать результаты для всех маркеров, станет понятно, что среднее абсолютное отклонение в среднем составляет 2–3 пикселя. Благодаря тому, что в дальнейшем, после распознавания, маркеры отслеживаются по Id, алгоритм будет устойчив к колебаниям сторон даже в 20 пикселей.

Алгоритм

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

Регистрация маркера

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

Регистрация нового маркера.

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

Для описания уникальных треугольников возьмем следующие элементы:

Длины трех сторон;
Ориентация треугольника (по часовой стрелке или против часовой стрелки).

Треугольник, ориентированный против часовой стрелки.

Треугольник, ориентированный по часовой стрелке.

Рассмотрим треугольник $inline$ ( $inline$ — shortest, $inline$ — longest). Ориентация определяется путем взятия самой длинной стороны треугольника $inline$ и проверкой, с какой стороны от нее лежит вершина, образующая самую короткую сторону $inline$ . Если вершина $inline$ расположена слева от самой длинной стороны, треугольник обозначается ориентированным по часовой стрелке.

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

$\begin{vmatrix} (V_{lx} - V_{0x}) & (V_{ly} - V_{0y})\\ (V_{sx} - V_{0x}) & (V_{sy} - V_{0y}) \end{vmatrix} > 0 \Rightarrow$

$(V_{lx} - V_{0x})(V_{sy} - V_{0y}) - (V_{ly} - V_{0y})(V_{sx} - V_{0x}) > 0$

При таком выборе элементов учитывается чувствительность к увеличению и отражению.

Детектирование зарегистрированных маркеров

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

Кластеризация точек

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

Построение треугольников.

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

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

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

Для поиска компонент связности в графе, образованном курсорами, можно использовать обход в ширину или в глубину. Предварительно нужно построить ребра между курсорами, расстояние между которыми меньше d. Запуская обход для каждой непосещенной вершины-курсора, получим компоненты связности. Ниже представлен пример поиска компонент связности в графе на основе обхода в глубину. Сложность решения будет $inline$ , где $inline$ — количество вершин, $inline$ — количество ребер.

Поиск компонент связности в графе:

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

Обход в глубину из вершины $inline$ :

Пометить $inline$ как посещенную;
Добавить вершину к компоненте связности $inline$ ;
Для каждой смежной к v вершине $inline$ :
Если $inline$ еще не посещена, выполнить для нее обход $inline$ .

Идентификация маркеров

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

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

$s_k = \frac{1}{3}\sum_{i=1}^3|L_{ki} - \overline{L_{i}}|$

$RecognizedMarkerNumber = \underset{k}{\operatorname{argmin}} (s_k)$

где $L_{ki}$ —длина стороны зарегистрированного маркера, $L_{i}$ — длина стороны распознанного маркера.

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

Одни и те же курсоры не могут принадлежать разным распознанным маркерам.

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

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

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

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

Состояние и положение маркеров

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

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

Обновление состояния маркеров

Классификация зарегистрированных маркеров

Классификация	Описание
Active	Все распознанные маркеры
Passive	Все нераспознанные маркеры

Сначала введем состояния, в которых могут находиться маркеры.

Будем называть зарегистрированными маркерами все, которые были зарегистрированы; распознанными те, которые распознаны алгоритмом на данном шаге. Все зарегистрированные маркеры поделим на Active (активные = зарегистрированные распознанные) и Passive (пассивные = зарегистрированные нераспознанные). Такое деление удобно для того, чтобы понимать, какие маркеры отправлять на распознавание, так как маркеры уникальны.

Для работы с распознанными маркерами введем следующие состояния: Added, Updated, Unstable, Removed. Эти состояния необходимы для отображения маркеров, обработки случаев отрыва ножек.

Описание состояния маркеров

Состояние маркера	Описание	Отправлять курсоры на детектирование	Обновлять положение и угол маркера	На следующем шаге может перейти в состояние
Added	Новый распознанный маркер, не отображенный на экране. Отправляется в UI для добавления и отображения на экране.	Нет	-	Updated
Updated	Распознанный маркер, отображенный на экране, был установлен на предыдущих шагах.	Да	Да	Updated, Unstable, Removed
Unstable	Распознанный маркер, отображенный на экране, но у которого пропала одна или две ножки.	Да	Нет	Unstable, Updated, Removed
Removed	Распознанный маркер, отображенный на экране, у которого пропали все три ножки. Отправляется в UI для удаления с экрана, после чего удаляется	-	-	-

Пример изменения состояний маркеров и курсоров

Логика перехода между состояниями

Состояние к началу шага n	Состояние к началу шага n+1	Условие
Added	Updated	Всегда
Updated	Removed	Потеряны все три ножки
Updated	Updated	Не выполнено ни одно из двух условий
Unstable	Updated	Оставшиеся стабильные курсоры маркера вошли в новый распознанный маркер с прежним ID
Unstable	Removed	Потеряны все ножки
Unstable	Unstable	Потеряны одна или две ножки
Removed	-	Маркер удален. Зарегистрированный маркер отправлен на распознование

В связи с тем, что на детектирование отправляются только курсоры, не входящие в маркеры и курсоры нестабильных маркеров (см. рис. 10), их, в свою очередь, также удобно разделить по статусу: см. таблицы 4,5.

Логическое состояние курсоров

Логическое состояние курсоров	Описание	Отправлять курсоры на детектирование
Marker	Курсоры, принадлежащие стабильным маркерам	нет
Passive	Курсоры, принадлежащие нестабильным маркерам и не принадлежащие маркерам	да

Физическое состояние курсоров

Физическое состояние курсоров	Описание
New	Новые курсоры, Type = 0
Active	Обновленные курсоры, Type = 1
Lost	Курсоры, которые исчезнут на следующем шаге, Type = 2

Пример изменения состояний маркеров и курсоров.

Положение маркера

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

Положение центра маркера

Построения для нахождения центр маркера.

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

На каждом шаге достаточно вычислять координаты центра окружности по трем точкам:

$x = \frac{m_a m_b(y_1 - y_3) + m_b(x_1 + x_2) - m_a(x_2 + x_3)}{2(m_b - m_a)}$

$y = -\frac{1}{m_a} (x - \frac{(x_1 + x_2) } {2}) + \frac{(y_1 + y_2)} {2},$

где m — угол наклона прямых, проходящих через точки:

$m_a = \frac{y_2-y_1}{x_2-x_1}$

$m_b = \frac{y_3-y_2}{x_3-x_2}$

Поворот маркера

Обозначим как φ разницу между начальным и текущим углом. За начальный угол α₁ возьмем угол маркера между самой длинной стороной и осью Oy во время регистрации. Соответственно, текущий угол — это угол между самой длинной стороной и осью Oy на данном шаге. Пусть $V_{lx}, V_{ly}$ — это координаты вершины $inline$ в декартовой системе координат, если вектор $inline$ (длинную сторону) перенести в начало координат. Тогда угол $\varphi$ можно найти как:

$\varphi = \alpha_1 - \alpha_2$

$alpha = \arctan{\frac{v_x}{v_y}}$

Причем угол $\alpha$ , измеренный в радианах, такой, что $inline$

Угол поворота маркера, вычисляемый относительно длинной стороны.

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

Теперь, если вы решите использовать TUI в своем проекте, вам не придется разбираться с задачей с нуля — вы сможете написать свою прослойку для распознавания и отображения маркеров, или воспользоваться нашим проектом (репозиторий с кодом на C#).

Будем рады обратной связи — делитесь своими комментариями и экспериментами!

Tags:

Hubs: