- Thank you very much.
So I'm here to present CircGR,
which is an interactive, multi-touch
gesture recognition using circular measurement.
Little bit of an introduction,
so ever since the introduction of the iPhone
way back in the early 2007, multi-touch
has become more and more ubiquitous,
to the point that most users already have an innate sense
of what a gesture is supposed to look like,
as well as a set of standard gestures
which they believe should be supported on all devices.
This type of prevalence of such gestures
has created an output for research
into classifiers and recognition techniques
for multi-touch.
And that gives the illusion that multi-touch
is almost a soft problem, as if there's already
enough solutions out there.
Why should we create more?
But that is an illusion, because multi-touch
still has many issues.
Some classifiers work excellent in some domains,
not so much in others.
For example, they might have great recognition
for a gesture when there's,
for symbols, or they have gestures
that are specifically online or offline.
Or for example if an interface requires
multimodal input methods, then recognition
doesn't work quite as well.
So that was our motivation for creating
an interactive multi-touch recognizer
that provides fast, very fast gesture recognition
for non-symbolic gestures,
so gestures that don't depend on any particular symbol,
specifically for capacitor screens, so touch screens.
And that's what is CircGR.
CircGR is an attempt to provide a solution
for very fast gesture recognition.
It is a template-based matching algorithm.
So it depends on templates and requires
as little as one template per gesture.
And it focuses, once again, on non-symbolic gestures,
so nothing like an A or an arrow,
but rather movements, like tap, swipe, rotations,
and pinch zooming.
Give you a little bit of context where CircGR stands,
when it comes to recognizers, you usually have
two main approaches to gesture recognition.
You usually have a formal gesture recognition language,
where you define a gesture according to some syntax
or some structure.
And then if a gesture or an input meets that structure,
then it's classified as that.
You have examples with XML, JSON, and even RegEx
when it comes to Proton and Proton plus plus.
This offers a great ability to define
exactly what gesture you wanna capture,
where a gesture either meets that definition or not.
So it can be a little bit tricky getting
just the right definition.
The other approach is to specify by example,
which generally means that you set up
some kind of model where there is a hidden Markov model
or a finite state machine or some statistical model,
even something like a neural network
or a machine learning approach.
These approaches typically require more training data
to establish a model for each particular gesture
that you wanna recognize.
And it also includes classifiers
that employ near, neighbor-like approaches,
such as the dollar standard, which is a very
well-known type of classifier.
And it's kind of our inspiration for CircGR.
So CircGr falls within the second approach.
So templates-based matcher, which we specify
each gesture in our gesture set by one example.
All right, so what is it that we hope
to contribute with this paper and with this work?
We wanna contribute a linearithmic algorithm
for multi-touch gesture recognition
with a high accuracy rate, over 99%,
and a Matthews correlation coefficient of 0.95.
For those that don't know, Matthews correlation coefficient
ranges from negative one to one,
one being perfect classification,
zero being no better than random,
and negative one being almost completely at odds
with the data.
We hope that this algorithm also demonstrates
early detection of gestures, which means
that we detect gestures from the get-go
rather from later on in the gesture's execution cycle.
And once again, we demonstrate that this one
performs with 99% accuracy and 0.86 MCC
when it comes to early recognition.
We subjected this algorithm to a study with 60 subjects
and over 12,000 gestures to evaluate
and arrive at these metrics.
So let's talk a little about CircGR itself.
So the main feature, the main data point
that you capture with CircGR is the circular measure,
which is the polar angle.
The polar angle is just part of the polar coordinate,
which represents a unit vector, as shown over here.
And a bunch of those angles put together in a set
can be averaged out into a resultant vector.
So this represents an average of polar angles,
and it's usually calculated by some
of the sines and cosines.
These are very, very simple calculations,
which is part of the reason why CircGR
is as quick as it is.
And the last metric that we really use
is the circular distance.
A circular distance is just the length of the arc
between two particular angles.
And again, very simple calculation.
And whenever I refer to the notion
of a circular distance, I'm talking about this.
And since our classifier, CircGR,
is a nearest neighbor-like template matcher,
what establishes some notion of distance,
this is the distance that we are talking about.
Having known that, you already know
everything you need to know to understand it.
So it's very, very approachable.
All right, so how do we represent a gesture in CircGR?
CircGR, a gesture is essentially just
two sets of angles.
And angles are almost like scalar values.
You don't need complicated data structures.
You have a set of spatial angles
which represent the spatial properties of the gesture
and are derived from the input points
of those, the input points of the traces
that are input.
And we have temporal angles, which represent
just the temporal properties of the gesture
and are derived from the timestamps of the input points.
And both of them together are used in classification.
This is all you need to know
to represent a gesture in CircGR.
So the process begins by receiving a raw input trace.
Again, this is a multi-touch surface.
The user is actuating on a surface.
We take the multi-touch trace, and we interpolate
a fixed amount of points.
So create from a raw trace of however many points
that screen is capturing to a fixed amount
of interpolated points.
And we generate angles as a vector
of equal length between each of those interpolated points.
This is how we generate spatial angles in CircGR.
And again, it's a very, very simple operation,
which happens very fast.
And it's done as you're resampling.
You might have a possibility that a user
inputs a trace which contributes no movement
or very little movement.
And those traces are labeled as anchors.
So we're able to capture traces that move,
and we're able to capture traces that do not move
and use them towards recognition.
All right.
Temporal angle generation is also done at the same time
that spatial angles are generated.
And they represent moments
within the interval of the gesture.
The best way to describe is that you have
to start the gesture and the duration of the gesture,
and an angle represents a moment in time
of that gesture.
If I were to say an angle pi,
I'm talking about roughly halfway in the gesture's interval.
And we use this to mark certain points
within the gesture, as certain events happen
within that gesture.
And those events come in the form of labels.
So each angle is generated by CircGR.
It's assigned three labels.
It's assigned a propagation label,
a centripetal label, and a clock label.
And these labels are tracked across time
using the temporal angles.
So these are all generated from spatial angles,
but they're tracked across time of the gesture
with temporal angles.
As you can see, this is an example of the propagation label.
The propagation label is one of the cardinals
or the intercardinal directions.
And it's just decided where alpha falls in the sector.
If it falls within this sector, it's right.
If it falls within the upper sector, it's up.
And these are arbitrary distinctions.
Doesn't matter where you begin looking for these,
as long as it's consistent throughout recognition.
Additional labels are centripetal and clock labels,
which once again are generated just as quickly,
as they're generated from the propagation label
to add more sorting and more tracking
in terms of what the gesture is doing.
So at the end of this entire process,
we have a set of angles.
And each of those set of angles have a label
applied to it that helps us both separate
the angles meaningfully and track
what the gesture does during the execution of the gesture.
So classification follows simply from these processes.
We have the input trace is resampled.
The angles are generated, and the classification
is done via template comparison.
As a template matcher, you have an input trace,
which is compared to various templates
which you have put into the system
as what you want to recognize.
And the template angles, of course,
are compared into the input angles.
Angles are compared on labels.
So ups are compared with up,
down are compared with down,
things that are labeled in or out
are compared accordingly.
If there are angles that do not match,
for example you have a gesture that goes straight up
and a template that goes straight down,
then you levy the penalties.
So part of the reasons we create the labels
is to compare angles meaningfully.
During these steps, the angles are usually ordered
and paired off sequentially, so it's a very simple
comparison process, which once again
makes it a very fast comparison process,
which is why this CircGR has a bottom limit
or a fast limit of linearithmic,
because it does a comparison.
A comparison can only be as fast as in linearithmic time.
We evaluated CircGR, as I mentioned,
over 60 participants with 12,000 gestures
over this gesture set.
We gave them this gesture set,
and we asked them to articulate it for us
on a capacitor touch screen.
Let's see if I can show you guys
that small video.
Okay.
Okay, this is a video of how we do the experiment.
Now, the user is forming gestures, that,
and then we have the live classification on the side,
tracking their movements.
Excellent.
At a certain point you saw a box on the screen.
That was to get the user to articulate
different parts of the screen.
It didn't have an effect on classification.
It was just so that they wouldn't do it
at the same point consecutively.
All right, let's resume.
Okay, these are the results of our experiment.
This is a confusion matrix of all the gestures
that we compute.
This is of course the concentration of values.
It's represented in our color scale.
As you can see, it's a very large concentration
in the diagonal, which of course means
that it was very, very, very good classification overall.
From here we have an accuracy of 99%
and a Matthews correlation coefficient of 0.95.
We wanted to see how the classifier performed
during the execution of the gesture.
These gestures are captured as a series of windows.
So as the user is executing a gesture,
it'll capture a certain amount of points and classify,
another certain amount of points and classify,
another certain amount.
We wanted to see how it performed
during each of those windows,
because users did different amount of windows.
And it was kinda hard to predict
which window was gonna yield
the highest classification rate.
And we also wanted to track if each window
was doing at an accepted level.
We actually used Cohen's kappa for this.
And for all windows, up to 10 windows,
we can see the Cohen's kappa does not dip below 0.80.
And 0.80 is a very good value for Cohen's kappa.
Typically the range for Cohen's kappa
is once again from negative one to one.
0.4 to 0.75 typically indicates a good agreement.
And anything higher than 0.75 typically indicates
almost perfect agreement.
So we had a very good agreement rate
through each window of capture for CircGR.
After the experiment, we decided to do
a post-hoc evaluation over the data
captured in the experiment and compare it
to dollar P, which is another very popular part
of the dollar family classifier
and also an inspiration for this classifier.
We wanted to compare it with that
not only on metrics but on the amount of time
it took to classify all 12,000 gestures
and the average time classified per gesture.
As we can see, CircGR had significantly higher
rates of accuracy and MCC.
These numbers are actually statistically significant,
even though they're close.
They're statistically significantly different.
The batch time, it took CircGR about
almost a little under four seconds
to classify 12,000 gestures, while it took
dollar P about 125 seconds.
That's an order of magnitude of difference.
And P filter in dollar P, with the benefit
of filtering templates that don't match
on finger amount.
So if it was four finger versus three fingers,
it'd be invalidated completely.
And since that's a very trivial addition to make,
we added the dollar P and called the P filter.
We can see that it sped it up quite a lot,
but not nearly as much.
On a per gesture time, CircGR can classify
a gesture, on average, less than one millisecond,
compared to P filter, which is about 3.2 milliseconds
and dollar P, which is about 19 milliseconds.
So in a realtime application context,
CircGR would be very good cause it's very,
very, very, very quick classification.
I talked about early detection.
This is a picturized version of early detection.
As we have time, we know that amount of points
is constantly increasing as the user
enters more and more points.
And here you can see the different windows being captured.
We wanted to evaluate how accurate it was
just after the first window, not after the user's been
actuating for a while, but just the first window.
And at the first window, once again,
we got an accuracy of 99% and a Matthews correlation
coefficient of 0.86.
A little bit lower, but still great.
And this is at a window of 64 points,
which is generated very quickly
in modern touch screens.
Our future work will imply not only applying
this algorithm to applications that involve
navigation in 3D environments,
but also expanding this work to three-dimensional contexts
as well as improving the early detection
aspects of this algorithm.
A future study may evaluate the degradation of accuracy
in CircGR when we omit sorting.
During classification, we sort angles
so that we can compare them more effectively.
If we skip that step, it becomes a linear classifier
instead of a linearithmic classifier.
So we want to investigate what happens
when we do that at an experiment level.
Other material is available at CircGR.com:
the code, the paper, appendix, and even the video.
We have the data set available for our experiment,
and we will be having a demo today and tomorrow
if you want to go see it.
And any questions?
(applause)
- [Man] I guess we have time for
one or two short questions.
Any?
Okay, there's lots you can think about.
I have one question for you.
You had your angular bins in sections, right?
Or up, left, right, and so on and so forth.
- Those are-
- [Man] So how did you choose them,
and did you evaluate the effects of other
angular binning schemes?
- Can you repeat the question?
- [Man] So you had your angular bins, right,
or your, on one slide, where you classified-
- Right, right, right, since this is in
a two-dimensional surface, up, down,
left, and right are relative.
- [Man] You had these eight?
- Eight, yes, eight in cardinal directions.
- [Man] If you evaluate other amount of bins,
did you evaluate other binning amounts,
other amounts of bins?
- We did not, because we felt that eight was,
it was working empirically.
We observed that it was working.
So we haven't subdivided that further.
The point of labels such as up, down,
left, or right is to group angles significantly, right,
and to group them meaningfully.
The labels themselves are arbitrary, really.
- [Man] Yeah, I'm aware of that.
Yeah, but I meant the number of angles, okay,
but you didn't, and it was working fine, so-
- Yeah, it was working fine, so empirically,
we decided not to add more,
because it was working fine, yes.
- [Man] Okay, thank you so much.
- We got a question.
- [Man] One, okay, one short question.
(audience member talking quietly)
- I'm sorry, you're gonna have to speak up a little bit
because I'm-
(audience member talking quietly)
- [Man] Please speak up a little bit.
- [Audience Member] Thank you,
so if you're with those bins that you have,
vertical, horizontal, and all that,
because those are absolute in space.
Something that you are going to pass
is that once you compute the angle,
you compute the difference in angle
to the next one, and the difference in angle
to the next one.
So if you remove that, could be
rotationally valued, right?
You could start the gesture model
just from here, or I could start it here
and do it over there.
Is that-
- Are you talking about the labels across?
(man talking quietly)
- [Audience Member] And the followup would be
would it be possible to actually have these labels
related to the initial orientation
that you have in the first segment,
cause my up could be dependent on where I start,
the direction in which I start.
That would be another way of still keeping
your labels, having it rotational.
(man talking quietly)