<commit_before>\documentclass[a5paper]{article}
\usepackage[a5paper, top=17mm, bottom=17mm, left=17mm, right=17mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[T2A,T1]{fontenc}
\usepackage[colorlinks,filecolor=blue,citecolor=green,unicode,pdftex]{hyperref}
\usepackage{cmap}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts,textcomp}
\usepackage{color}
\usepackage{array}
\usepackage{hhline}
\hypersetup{colorlinks=true, linkcolor=blue, citecolor=blue, filecolor=blue, urlcolor=blue, pdftitle=1, pdfauthor=, pdfsubject=, pdfkeywords=}
% \usepackage[pdftex]{graphicx}
\usepackage{graphicx}
% \usepackage{epigraph}
% Раскомментировать тем, у кого этот пакет есть. Шрифт станет заметно красивее.
%\usepackage{literat}
\usepackage{indentfirst}
\usepackage{multirow}

\sloppy
\pagestyle{plain}
%\pagestyle{empty}

\title{Поддержка жестов мышью в мета-CASE-системах}

\author{<NAME> \and <NAME> \and <NAME>}
\date{}
\begin{document}

\maketitle
\thispagestyle{empty}

\begin{quote}
\small\noindent
Статья рассматривает подходы к поддержке жестов мышью в создаваемых с помощью мета-CASE-инструментария предметно-ориентированных языках визуального моделирования. Приводится численное сравнение алгоритмов распознавания, не использующих предварительное обучение. Делаются выводы о применимости данного класса алгоритмов для повышения эффективности и удобства работы проектировщика, пользующегося визуальным редактором, построенным в мета-CASE-системе. Предложенный подход реализован в мета-CASE-системе QReal.
\end{quote}

\section*{Введение}
Одной из особенностей разработки, управляемой моделями (model-driven development, MDD~\cite{mde}), является активное использование визуальных языков. Практически все действия, выполняемые в CASE-средствах или других используемых инструментах так или иначе сводятся к манипуляциям над элементами этих языков и связями между ними. 

Эффективность любого используемого инструмента определяется тем, насколько удобно и быстро он позволяет выполнять те операции, для которых предназначен. В процессе разработки моделей одними из наиболее часто выполняемых действий над объектами на диаграммах являются их создание и удаление.  В большинстве CASE-средств для того, чтобы создать нужный объект на диаграмме, необходимо найти его либо на панели инструментов, либо выбрать в меню, а затем указать место на диаграмме, где бы мы хотели этот элемент разместить. Также в большинстве инструментариев возможен вариант создания объектов «перетаскиванием» (drag and drop) их из палитры. При этом надо учитывать, что количество видов диаграмм и объектов в палитре каждой диаграммы может быть довольно большим (например, 13 видов диаграмм в UML 2.2). Не всегда возможно оставить в палитре только специфичные для данного типа диаграмм элементы, поскольку может возникать задача быстрого прототипирования с использованием смешанных диаграмм. То есть даже для такой базовой операции, как создание нового элемента, разработчику нужно совершить не только набор чисто механических действий, но ещё и, скажем, вспомнить, на какой вкладке палитры или в каком меню находится нужный ему элемент, тем самым переключая контекст с продумывания иерархии создаваемых моделей на особенности использования выбранного инструмента. Нам кажется, что данную операцию можно и нужно автоматизировать, причём её нужно сделать максимально удобной для пользователей CASE-средств. 

Оптимизация интерфейса под использование жестов особо актуальна в контексте использования CASE-средства на компьютерах с сенсорными экранами или на электронных досках. Такие устройства активно развиваются и уже вошли в повседневную жизнь, например, Microsoft Surface\footnote{http://www.microsoft.com/surface/}.Примерами использования CASE-средств на таких устройствах может являться применение их в процессе обучения или активного обсуждения на совещаниях~\cite{ideogramic}. 

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

Использование визуальных языков общего назначения, таких, как UML, не даёт существенного выигрыша в производительности труда программиста, поэтому всё большую популярность набирают предметно-ориентированные визуальные языки~\cite{theBook, dsm}. Мета-CASE-системы предназначены для быстрого создания языка под конкретную предметную область и порождения CASE-инструмента для работы с этим языком. Одним из примеров мета-CASE-систем является среда QReal~\cite{qreal}, разрабатываемая на кафедре системного программирования СПбГУ. В QReal для быстрой разработки новых редакторов диаграмм имеется метаредактор с графическим редактором формы элементов. Он позволяет создавать метамодели новых языков, описывая имеющиеся на диаграммах элементы и связи между ними, задавать визуальное представление элементов на диаграммах. Созданную метамодель можно скомпилировать в подключаемый модуль и подключить его к QReal прямо в процессе работы.

В последнее время разработкам нетрадиционных подходов к организации человеко-машинного взаимодействия уделяется довольно много внимания, и идея подавать команды программам с помощью жестов мыши уже нашла свое применение во многих приложениях, например, браузер Opera\footnote{http://www.opera.com/}, игры. Некоторые утилиты (такие, как StrokeIt, gMote и др.) даже позволяют внедрить поддержку  жестов мышью в произвольные приложения. Более того, существуют и CASE-системы, использующие подобный подход, например, Visual Paradigm\footnote{http://www.visual-paradigm.com/product/vpuml/}. Но поддержка жестов мышью в таких программах ограничена тем, что набор жестов фиксирован, что недопустимо для расширяемых систем, к которым относятся мета-CASE-системы. В данной статье описывается опыт внедрения жестов мышью в приложение, в котором набор жестов неизвестен априори и может быть расширен.

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

\section{Обзор подходов к распознаванию жестов мышью}

\subsection{Использование жестов мышью в существующих приложениях}

Существует довольно много приложений, в которых использование жестов мыши уже нашло своё применение. Так, например, в веб-браузер Opera встроена поддержка простейших жестов, вызывающих наиболее часто применяемые команды. К примеру, чтобы вернуться к предыдущей странице, можно нажать кнопку ``Back`` в панели браузера, а можно выполнить движение мышью влево при зажатой правой кнопке. Чтобы перейти к следующей странице (кнопка ``Forward``), нужно двигать мышь вправо, для обновления страницы (кнопка ``Reload'') -- вверх-вниз, чтобы открыть новую вкладку -- вниз. Ясно, что при таких абстрактных жестах от алгоритма распознавания не требуется большая точность -- достаточно просто разбить жест на направления и выделить 1-3 вектора наибольшей длины.

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

Также существуют специальные утилиты, с помощью которых можно ввести поддержку жестов мышью в любую программу, такие как strokeIt\footnote{http://www.tcbmi.com/strokeit/}, gMote\footnote{http://www.handform.net/gmote.php}, xstroke\footnote{http://freshmeat.net/projects/xstroke/}, flyGesture\footnote{http://flyingmeat.com/flygesture/}. Их недостаток с точки зрения рассматриваемой задачи состоит в том, что добавляется лишь ограниченное число заранее определённых команд, таких, как сохранение, распечатка, копирование, вставка и т.п. В CASE-системах для полноценной поддержки создания элементов требуется на порядок больше различных жестов. И если в вышеперечисленных утилитах можно обойтись перебором всевозможных путей мыши, по которым вызывается та или иная команда, то в CASE-средстве перебирать придётся слишком много вариантов. Ограничиться простейшими жестами (вверх, вниз, вправо, влево) невозможно, так как объектов слишком много и может возникнуть конфликт между двумя командами, у которых будет один и тот же жест. Возможным решением в таких случаях было бы по жесту предоставлять список команд, из которых пользователь может выбрать. Но если список будет слишком большим или будет вызываться при каждом жесте мышью, то смысл введения жестов пропадает, так как большинство инструментов уже предоставляет пользователю список объектов, которые с помощью операции drag-and-drop можно перетаскивать на рабочее поле.

Отдельно хотелось бы выделить CASE-систему Visual Paradigm, в которой частично реализован предлагаемый в данной статье подход. В Visual Paradigm жесты мышью подразделяются на три типа – жесты, порождающие объект, жесты, вызывающие команду и жесты, создающие связь между объектами. Жесты, порождающие объект и жесты, вызывающие команды задаются набором направлений (вверх, вниз, вправо, влево). Каждая диаграмма имеет отдельный ассоциированный с ней набор жестов, причём жесты имеют не все элементы палитры данной диаграммы, а только наиболее употребимые. Имеется контекстная справка, анимированно показывающая, как рисовать жест. Жесты иногда довольно сильно отличаются от создаваемых ими фигур. Жестов мышью в Visual Paradigm гораздо больше, чем в  утилитах, описанных ранее, но, как и в первых трёх случаях, они жёстко ``зашиты'' в код. 

Аналогичный подход был реализован в инструменте Ideogramic~UML~\cite{ideogramic}, авторы которого особое внимание уделяли распознаванию жестов. Инструмент изначально разрабатывался как среда визуального моделирования для сенсорных экранов и интеллектуальных досок, но возможна работа и с жестами мыши. Версия инструмента, доступная на данный момент, датируется 2002 годом. В рамках же данной работы хотелось бы развить данную идею и предложить расширяемую технологию поддержки жестов мышью в CASE-средствах. 

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

\subsection{Обзор алгоритмов распознавания жестов мышью}
Задача компьютерного распознавания образов не нова --- различные варианты задач идентификации и классификации объектов решаются уже более сорока лет. За это время было разработано множество алгоритмов и подходов к решению самых разных задач распознавания, однако независимо от их класса и предметной области все подходы работают по следующей схеме: 
\begin{itemize}
  \item анализ и/или измерение объектов;
  \item выделение их характеристических признаков;
  \item классификация объектов в соответствии с полученными признаками.
\end{itemize}

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

\subsubsection{Выделение признаков}
Большинство существующих алгоритмов распознавания работают с векторами характеристик объектов, которые позволяют абстрагироваться от несущественных для решаемой задачи признаков, например, таких, как пространственное положение и размеры распознаваемого объекта. В нашем случае каждому жесту соответствует траектория движения курсора мыши --- список точек. Однако, использовать списки точек в качестве характеристических векторов не удаётся, так как при переносе или масштабировании жеста их координаты могут меняться довольно сильно. Мы будем рассматривать методы, предлагающие следующее решение проблемы: некоторым образом сопоставим каждому жесту строку символов (которую далее будем называть строкой-ключом) и будем сравнивать не списки точек траекторий, а соответствующие им ключи. Отметим, что закодировать жест строкой символов можно совершенно разными способами, например, рассмотреть как строку бинарное представление набора точек в пути. Наибольший интерес представляют методы построения ключа, которые сохраняют только существенную информацию о жесте, некоторые такие методы и будут рассмотрены далее.

Наиболее очевидным подходом к построению ключа является отслеживание изменений ориентации сегментов ломаной, соответствующей жесту, относительно выбранной системы координат~\cite{chaosAlgorithm}. Участку жеста соответствует угол на плоскости, который попадает в один из диапазонов, а каждому из диапазонов углов ставится в соответствие символ в алфавите (см. рис.~\ref{chaos}). 

\begin{figure} [ht]
  \begin{center}
    \includegraphics[width=0.9\textwidth, bb=0 0 804 498]{02-chaos.png}
    \caption{Построение ключа по принадлежности направлению}
    \label{chaos}
  \end{center}
\end{figure}

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

Другой алгоритм предлагает рассматривать не принадлежность направлению, а принадлежность прямоугольнику. Вокруг траектории законченного жеста описывается прямоугольник, каждая сторона которого делится на 8 частей (см. рис.~\ref{squares}). Каждому внутреннему прямоугольнику ставится в соответствие символ алфавита. Строка-ключ жеста будет состоять из символов, соответствующих прямоугольникам, по которым проходит траектория жеста. После удаления подряд идущих одинаковых символов из строки получаем окончательный ключ текущего жеста. 

\begin{figure} [ht]
  \begin{center}
    \includegraphics[width=0.8\textwidth, bb=0 0 544 390]{03-squares.png}
    \caption{Построение ключа по принадлежности прямоугольнику}
    \label{squares}
  \end{center}
\end{figure}

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

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

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

Среди используемых подходов к классификации наибольшей популярностью в задачах распознавания пользуются такие математические модели, как искусственные нейронные сети~\cite{neuronet1, neuronet2, neuronet3}, скрытые марковские модели~\cite{hmm1, hmm2, hmm3}, а также классификаторы, получаемые обучением с помощью, например, метода опорных векторов~\cite{svm1, svm2} или алгоритмов AdaBoost/FloatBoost~\cite{boosting1, boosting2}. Принцип работы у всех этих классификаторов примерно одинаковый --- вначале осуществляется фаза обучения, на которой классификатору на вход подаётся набор эталонных объектов, соответствующих каждому классу. В рабочем режиме обученный классификатор сопоставляет входные вектора признаков классу, соответствующему данным объектам.

Наличие этапа обучения для нашей задачи недопустимо, поскольку в процессе метамоделирования новые сущности могут появляться довольно часто, а обучение требует наличия большой базы примеров (например, набора типичных траекторий для каждого жеста). Такую базу невозможно создать в короткие сроки при быстрой разработке предметно-ориентированного языка. Данное ограничение является довольно серьёзным и, к сожалению, не позволяет нам использовать данный вид классификаторов для решения поставленной задачи. Существует несколько открытых реализаций обучаемых классификаторов, например, библиотека AME Patterns\footnote{http://ame4.hc.asu.edu/amelia/patterns/}, но, по указанным причинам, в данной статье мы не будем их рассматривать.

Другим часто используемым в распознавании образов подходом к классификации объектов является так называемая задача поиска ближайшего соседа~\cite{nns1, nns2}, заключающийся в отыскании среди множества элементов, расположенных в некоем метрическом пространстве (в общем случае, многомерном), элементов, близких к заданному, согласно некоторой функции близости, задаваемой статически (в отличие от алгоритмов, основанных на обучении, где функция близости меняется в процессе обучения). В случае представления траекторий строками из некоторого алфавита можно использовать много различных функций близости, но на точность распознавания они влияния не оказывают, поскольку не должны учитывать физические свойства векторов признаков. Наиболее известной такой функцией является расстояние Левенштейна, которое определяется как минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой для превращения одной строки в другую~\cite{levenshtein}. Однако, расстояние Левенштейна обладает следующим недостатком: расстояния между совершенно разными короткими строками оказываются небольшими, а расстояния между похожими длинными словами оказываются значительными. Поэтому обычно используется не само расстояние, а соотношение 

\begin{equation}
\label{levenshtein}
d_{normalized}(s1,s2) = \frac{d(s1,s2)}{min(s1,s2)},
\end{equation}

где d(s1,s2) -- расстояние Левенштейна между строками s1 и s2, а min(s1,s2) -- минимум длин этих строк. Рассматриваемые нами методы построения строки-ключа обладают тем свойством, что незначительно отличающимся жестам обычно соответствуют незначительно отличающиеся строки с точки зрения нормализованного расстояния Левенштейна, поэтому такая функция вполне подходит для наших целей.

\subsubsection{Алгоритм распознавания жестов без генерации строки-ключа}
\label{qtAlgorithm}
При создании QReal использовался инструментарий Qt\footnote{http://qt.nokia.com/}, разработчиками которого предложен свой алгоритм распознавания жестов мышью, не требующий в процессе работы построения строки-ключа и основанный на анализе изменения направлений участков жеста~\cite{qtGestures}. Рассмотрим шаги алгоритма.
\begin{enumerate}
  \item Фильтрация пути мыши.
  \item Сопоставление объекта из списка. Предполагается, что объект в этом алгоритме --- это ломаная.
  \begin{enumerate}
    \item Приближение направлениями. На этом этапе каждый сегмент ломаной приближается одним из заранее определённых базовых направлений. Как правило, их четыре --- вверх, вниз, вправо, влево. Для большей точности количество базовых направлений можно увеличить, при этом удобно брать число, кратное четырём, чтобы четыре базовых направления оставались неизменными, и каждое было биссектрисой двух соседних. При увеличении числа направлений к эталонным жестам можно добавлять сложные многоугольники, стороны которых не обязательно параллельны осям координат, которые было бы невозможно распознать в случае использования только четырёх направлений.
    \item Упрощение списка направлений, заключающееся в том, чтобы найти подряд идущие сонаправленные вектора и объединить их в один вектор, просуммировав длину.
    \item Сопоставление и удаление. Эта часть алгоритма является, пожалуй, наиболее сложной, так как, несмотря на фильтрацию, останутся мелкие сбои вдоль длинных отрезков. На этом шаге полученному списку направлений сопоставляется эталонный жест команды. Если соответствующий эталонный жест не найден, мы удаляем кратчайший отрезок и повторяем попытку. Алгоритм заканчивается, если удалось получить команду, или большая часть первоначального списка направлений была удалена.
  \end{enumerate}
\end{enumerate}
<commit_msg>More about Qt algorithm filtering<commit_after>\documentclass[a5paper]{article}
\usepackage[a5paper, top=17mm, bottom=17mm, left=17mm, right=17mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[T2A,T1]{fontenc}
\usepackage[colorlinks,filecolor=blue,citecolor=green,unicode,pdftex]{hyperref}
\usepackage{cmap}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts,textcomp}
\usepackage{color}
\usepackage{array}
\usepackage{hhline}
\hypersetup{colorlinks=true, linkcolor=blue, citecolor=blue, filecolor=blue, urlcolor=blue, pdftitle=1, pdfauthor=, pdfsubject=, pdfkeywords=}
% \usepackage[pdftex]{graphicx}
\usepackage{graphicx}
% \usepackage{epigraph}
% Раскомментировать тем, у кого этот пакет есть. Шрифт станет заметно красивее.
%\usepackage{literat}
\usepackage{indentfirst}
\usepackage{multirow}

\sloppy
\pagestyle{plain}
%\pagestyle{empty}

\title{Поддержка жестов мышью в мета-CASE-системах}

\author{<NAME> \and <NAME>ин \and <NAME>}
\date{}
\begin{document}

\maketitle
\thispagestyle{empty}

\begin{quote}
\small\noindent
Статья рассматривает подходы к поддержке жестов мышью в создаваемых с помощью мета-CASE-инструментария предметно-ориентированных языках визуального моделирования. Приводится численное сравнение алгоритмов распознавания, не использующих предварительное обучение. Делаются выводы о применимости данного класса алгоритмов для повышения эффективности и удобства работы проектировщика, пользующегося визуальным редактором, построенным в мета-CASE-системе. Предложенный подход реализован в мета-CASE-системе QReal.
\end{quote}

\section*{Введение}
Одной из особенностей разработки, управляемой моделями (model-driven development, MDD~\cite{mde}), является активное использование визуальных языков. Практически все действия, выполняемые в CASE-средствах или других используемых инструментах так или иначе сводятся к манипуляциям над элементами этих языков и связями между ними. 

Эффективность любого используемого инструмента определяется тем, насколько удобно и быстро он позволяет выполнять те операции, для которых предназначен. В процессе разработки моделей одними из наиболее часто выполняемых действий над объектами на диаграммах являются их создание и удаление.  В большинстве CASE-средств для того, чтобы создать нужный объект на диаграмме, необходимо найти его либо на панели инструментов, либо выбрать в меню, а затем указать место на диаграмме, где бы мы хотели этот элемент разместить. Также в большинстве инструментариев возможен вариант создания объектов «перетаскиванием» (drag and drop) их из палитры. При этом надо учитывать, что количество видов диаграмм и объектов в палитре каждой диаграммы может быть довольно большим (например, 13 видов диаграмм в UML 2.2). Не всегда возможно оставить в палитре только специфичные для данного типа диаграмм элементы, поскольку может возникать задача быстрого прототипирования с использованием смешанных диаграмм. То есть даже для такой базовой операции, как создание нового элемента, разработчику нужно совершить не только набор чисто механических действий, но ещё и, скажем, вспомнить, на какой вкладке палитры или в каком меню находится нужный ему элемент, тем самым переключая контекст с продумывания иерархии создаваемых моделей на особенности использования выбранного инструмента. Нам кажется, что данную операцию можно и нужно автоматизировать, причём её нужно сделать максимально удобной для пользователей CASE-средств. 

Оптимизация интерфейса под использование жестов особо актуальна в контексте использования CASE-средства на компьютерах с сенсорными экранами или на электронных досках. Такие устройства активно развиваются и уже вошли в повседневную жизнь, например, Microsoft Surface\footnote{http://www.microsoft.com/surface/}.Примерами использования CASE-средств на таких устройствах может являться применение их в процессе обучения или активного обсуждения на совещаниях~\cite{ideogramic}. 

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

Использование визуальных языков общего назначения, таких, как UML, не даёт существенного выигрыша в производительности труда программиста, поэтому всё большую популярность набирают предметно-ориентированные визуальные языки~\cite{theBook, dsm}. Мета-CASE-системы предназначены для быстрого создания языка под конкретную предметную область и порождения CASE-инструмента для работы с этим языком. Одним из примеров мета-CASE-систем является среда QReal~\cite{qreal}, разрабатываемая на кафедре системного программирования СПбГУ. В QReal для быстрой разработки новых редакторов диаграмм имеется метаредактор с графическим редактором формы элементов. Он позволяет создавать метамодели новых языков, описывая имеющиеся на диаграммах элементы и связи между ними, задавать визуальное представление элементов на диаграммах. Созданную метамодель можно скомпилировать в подключаемый модуль и подключить его к QReal прямо в процессе работы.

В последнее время разработкам нетрадиционных подходов к организации человеко-машинного взаимодействия уделяется довольно много внимания, и идея подавать команды программам с помощью жестов мыши уже нашла свое применение во многих приложениях, например, браузер Opera\footnote{http://www.opera.com/}, игры. Некоторые утилиты (такие, как StrokeIt, gMote и др.) даже позволяют внедрить поддержку  жестов мышью в произвольные приложения. Более того, существуют и CASE-системы, использующие подобный подход, например, Visual Paradigm\footnote{http://www.visual-paradigm.com/product/vpuml/}. Но поддержка жестов мышью в таких программах ограничена тем, что набор жестов фиксирован, что недопустимо для расширяемых систем, к которым относятся мета-CASE-системы. В данной статье описывается опыт внедрения жестов мышью в приложение, в котором набор жестов неизвестен априори и может быть расширен.

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

\section{Обзор подходов к распознаванию жестов мышью}

\subsection{Использование жестов мышью в существующих приложениях}

Существует довольно много приложений, в которых использование жестов мыши уже нашло своё применение. Так, например, в веб-браузер Opera встроена поддержка простейших жестов, вызывающих наиболее часто применяемые команды. К примеру, чтобы вернуться к предыдущей странице, можно нажать кнопку ``Back`` в панели браузера, а можно выполнить движение мышью влево при зажатой правой кнопке. Чтобы перейти к следующей странице (кнопка ``Forward``), нужно двигать мышь вправо, для обновления страницы (кнопка ``Reload'') -- вверх-вниз, чтобы открыть новую вкладку -- вниз. Ясно, что при таких абстрактных жестах от алгоритма распознавания не требуется большая точность -- достаточно просто разбить жест на направления и выделить 1-3 вектора наибольшей длины.

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

Также существуют специальные утилиты, с помощью которых можно ввести поддержку жестов мышью в любую программу, такие как strokeIt\footnote{http://www.tcbmi.com/strokeit/}, gMote\footnote{http://www.handform.net/gmote.php}, xstroke\footnote{http://freshmeat.net/projects/xstroke/}, flyGesture\footnote{http://flyingmeat.com/flygesture/}. Их недостаток с точки зрения рассматриваемой задачи состоит в том, что добавляется лишь ограниченное число заранее определённых команд, таких, как сохранение, распечатка, копирование, вставка и т.п. В CASE-системах для полноценной поддержки создания элементов требуется на порядок больше различных жестов. И если в вышеперечисленных утилитах можно обойтись перебором всевозможных путей мыши, по которым вызывается та или иная команда, то в CASE-средстве перебирать придётся слишком много вариантов. Ограничиться простейшими жестами (вверх, вниз, вправо, влево) невозможно, так как объектов слишком много и может возникнуть конфликт между двумя командами, у которых будет один и тот же жест. Возможным решением в таких случаях было бы по жесту предоставлять список команд, из которых пользователь может выбрать. Но если список будет слишком большим или будет вызываться при каждом жесте мышью, то смысл введения жестов пропадает, так как большинство инструментов уже предоставляет пользователю список объектов, которые с помощью операции drag-and-drop можно перетаскивать на рабочее поле.

Отдельно хотелось бы выделить CASE-систему Visual Paradigm, в которой частично реализован предлагаемый в данной статье подход. В Visual Paradigm жесты мышью подразделяются на три типа – жесты, порождающие объект, жесты, вызывающие команду и жесты, создающие связь между объектами. Жесты, порождающие объект и жесты, вызывающие команды задаются набором направлений (вверх, вниз, вправо, влево). Каждая диаграмма имеет отдельный ассоциированный с ней набор жестов, причём жесты имеют не все элементы палитры данной диаграммы, а только наиболее употребимые. Имеется контекстная справка, анимированно показывающая, как рисовать жест. Жесты иногда довольно сильно отличаются от создаваемых ими фигур. Жестов мышью в Visual Paradigm гораздо больше, чем в  утилитах, описанных ранее, но, как и в первых трёх случаях, они жёстко ``зашиты'' в код. 

Аналогичный подход был реализован в инструменте Ideogramic~UML~\cite{ideogramic}, авторы которого особое внимание уделяли распознаванию жестов. Инструмент изначально разрабатывался как среда визуального моделирования для сенсорных экранов и интеллектуальных досок, но возможна работа и с жестами мыши. Версия инструмента, доступная на данный момент, датируется 2002 годом. В рамках же данной работы хотелось бы развить данную идею и предложить расширяемую технологию поддержки жестов мышью в CASE-средствах. 

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

\subsection{Обзор алгоритмов распознавания жестов мышью}
Задача компьютерного распознавания образов не нова --- различные варианты задач идентификации и классификации объектов решаются уже более сорока лет. За это время было разработано множество алгоритмов и подходов к решению самых разных задач распознавания, однако независимо от их класса и предметной области все подходы работают по следующей схеме: 
\begin{itemize}
  \item анализ и/или измерение объектов;
  \item выделение их характеристических признаков;
  \item классификация объектов в соответствии с полученными признаками.
\end{itemize}

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

\subsubsection{Выделение признаков}
Большинство существующих алгоритмов распознавания работают с векторами характеристик объектов, которые позволяют абстрагироваться от несущественных для решаемой задачи признаков, например, таких, как пространственное положение и размеры распознаваемого объекта. В нашем случае каждому жесту соответствует траектория движения курсора мыши --- список точек. Однако, использовать списки точек в качестве характеристических векторов не удаётся, так как при переносе или масштабировании жеста их координаты могут меняться довольно сильно. Мы будем рассматривать методы, предлагающие следующее решение проблемы: некоторым образом сопоставим каждому жесту строку символов (которую далее будем называть строкой-ключом) и будем сравнивать не списки точек траекторий, а соответствующие им ключи. Отметим, что закодировать жест строкой символов можно совершенно разными способами, например, рассмотреть как строку бинарное представление набора точек в пути. Наибольший интерес представляют методы построения ключа, которые сохраняют только существенную информацию о жесте, некоторые такие методы и будут рассмотрены далее.

Наиболее очевидным подходом к построению ключа является отслеживание изменений ориентации сегментов ломаной, соответствующей жесту, относительно выбранной системы координат~\cite{chaosAlgorithm}. Участку жеста соответствует угол на плоскости, который попадает в один из диапазонов, а каждому из диапазонов углов ставится в соответствие символ в алфавите (см. рис.~\ref{chaos}). 

\begin{figure} [ht]
  \begin{center}
    \includegraphics[width=0.9\textwidth, bb=0 0 804 498]{02-chaos.png}
    \caption{Построение ключа по принадлежности направлению}
    \label{chaos}
  \end{center}
\end{figure}

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

Другой алгоритм предлагает рассматривать не принадлежность направлению, а принадлежность прямоугольнику. Вокруг траектории законченного жеста описывается прямоугольник, каждая сторона которого делится на 8 частей (см. рис.~\ref{squares}). Каждому внутреннему прямоугольнику ставится в соответствие символ алфавита. Строка-ключ жеста будет состоять из символов, соответствующих прямоугольникам, по которым проходит траектория жеста. После удаления подряд идущих одинаковых символов из строки получаем окончательный ключ текущего жеста. 

\begin{figure} [ht]
  \begin{center}
    \includegraphics[width=0.8\textwidth, bb=0 0 544 390]{03-squares.png}
    \caption{Построение ключа по принадлежности прямоугольнику}
    \label{squares}
  \end{center}
\end{figure}

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

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

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

Среди используемых подходов к классификации наибольшей популярностью в задачах распознавания пользуются такие математические модели, как искусственные нейронные сети~\cite{neuronet1, neuronet2, neuronet3}, скрытые марковские модели~\cite{hmm1, hmm2, hmm3}, а также классификаторы, получаемые обучением с помощью, например, метода опорных векторов~\cite{svm1, svm2} или алгоритмов AdaBoost/FloatBoost~\cite{boosting1, boosting2}. Принцип работы у всех этих классификаторов примерно одинаковый --- вначале осуществляется фаза обучения, на которой классификатору на вход подаётся набор эталонных объектов, соответствующих каждому классу. В рабочем режиме обученный классификатор сопоставляет входные вектора признаков классу, соответствующему данным объектам.

Наличие этапа обучения для нашей задачи недопустимо, поскольку в процессе метамоделирования новые сущности могут появляться довольно часто, а обучение требует наличия большой базы примеров (например, набора типичных траекторий для каждого жеста). Такую базу невозможно создать в короткие сроки при быстрой разработке предметно-ориентированного языка. Данное ограничение является довольно серьёзным и, к сожалению, не позволяет нам использовать данный вид классификаторов для решения поставленной задачи. Существует несколько открытых реализаций обучаемых классификаторов, например, библиотека AME Patterns\footnote{http://ame4.hc.asu.edu/amelia/patterns/}, но, по указанным причинам, в данной статье мы не будем их рассматривать.

Другим часто используемым в распознавании образов подходом к классификации объектов является так называемая задача поиска ближайшего соседа~\cite{nns1, nns2}, заключающийся в отыскании среди множества элементов, расположенных в некоем метрическом пространстве (в общем случае, многомерном), элементов, близких к заданному, согласно некоторой функции близости, задаваемой статически (в отличие от алгоритмов, основанных на обучении, где функция близости меняется в процессе обучения). В случае представления траекторий строками из некоторого алфавита можно использовать много различных функций близости, но на точность распознавания они влияния не оказывают, поскольку не должны учитывать физические свойства векторов признаков. Наиболее известной такой функцией является расстояние Левенштейна, которое определяется как минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой для превращения одной строки в другую~\cite{levenshtein}. Однако, расстояние Левенштейна обладает следующим недостатком: расстояния между совершенно разными короткими строками оказываются небольшими, а расстояния между похожими длинными словами оказываются значительными. Поэтому обычно используется не само расстояние, а соотношение 

\begin{equation}
\label{levenshtein}
d_{normalized}(s1,s2) = \frac{d(s1,s2)}{min(s1,s2)},
\end{equation}

где d(s1,s2) -- расстояние Левенштейна между строками s1 и s2, а min(s1,s2) -- минимум длин этих строк. Рассматриваемые нами методы построения строки-ключа обладают тем свойством, что незначительно отличающимся жестам обычно соответствуют незначительно отличающиеся строки с точки зрения нормализованного расстояния Левенштейна, поэтому такая функция вполне подходит для наших целей.

\subsubsection{Алгоритм распознавания жестов без генерации строки-ключа}
\label{qtAlgorithm}
При создании QReal использовался инструментарий Qt\footnote{http://qt.nokia.com/}, разработчиками которого предложен свой алгоритм распознавания жестов мышью, не требующий в процессе работы построения строки-ключа и основанный на анализе изменения направлений участков жеста~\cite{qtGestures}. Рассмотрим шаги алгоритма.
\begin{enumerate}
  \item Фильтрация пути мыши. Работает на этапе формирования пути по данным с мыши и не допускает записи в путь слишком коротких отрезков. Этот шаг необходим, поскольку последующие шаги алгоритма могут работать некорректно, если отрезок в пути слишком короткий, кроме того, это снижает зависимость алгоритма от особенностей аппаратной части.
  \item Сопоставление объекта из списка. Предполагается, что объект в этом алгоритме --- это ломаная.
  \begin{enumerate}
    \item Приближение направлениями. На этом этапе каждый сегмент ломаной приближается одним из заранее определённых базовых направлений. Как правило, их четыре --- вверх, вниз, вправо, влево. Для большей точности количество базовых направлений можно увеличить, при этом удобно брать число, кратное четырём, чтобы четыре базовых направления оставались неизменными, и каждое было биссектрисой двух соседних. При увеличении числа направлений к эталонным жестам можно добавлять сложные многоугольники, стороны которых не обязательно параллельны осям координат, которые было бы невозможно распознать в случае использования только четырёх направлений.
    \item Упрощение списка направлений, заключающееся в том, чтобы найти подряд идущие сонаправленные вектора и объединить их в один вектор, просуммировав длину.
    \item Сопоставление и удаление. Эта часть алгоритма является, пожалуй, наиболее сложной, так как, несмотря на фильтрацию, останутся мелкие сбои вдоль длинных отрезков. На этом шаге полученному списку направлений сопоставляется эталонный жест команды. Если соответствующий эталонный жест не найден, мы удаляем кратчайший отрезок и повторяем попытку. Алгоритм заканчивается, если удалось получить команду, или большая часть первоначального списка направлений была удалена.
  \end{enumerate}
\end{enumerate}

{'fraction_non_alphanumeric': 0.045044193411164155, 'fraction_numerical': 0.003497660348820721, 'mean_word_length': 6.209916510478787, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 10, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2535827', 'n_tokens_mistral': 16063, 'n_tokens_neox': 20259, 'n_words': 4894}