Reading #7 Early Processing of Sketch

Reading #7  Early Processing of Sketch  

Comments on:
Yue Li

Summary:

This paper aims to find ways to process the freehand sketches in the early phase. This include three parts: stroke approximation, beautification and basic recognition

In the stroke approximation steps, this paper deals differently with lines and curves.

The stroke was process in order to find the vertexes of the lines   (which are also treated as corners). In order to achieve this, the curvature graph and speed graph are made. Intuitively, the maxima of curvature and minima of speed have a great possibility of being a corner. In addition, the authors use the mean of each date as threshold to filter the candidate corners.  The authors also combine the curvature and speed graph to increase the accuracy of finding the correct corners. This is done by generating the hybrid fits and selecting the fit that has error below a threshold and with the fewest vertices.

For curves, firstly, the authors use the ratio between the actual lengths of the stroke segment with the Euclidean distance between its endpoints. (Ratio significantly higher than 1 is treated as a signal of being a curve). In order to efficiently find the control points of the curve, this paper choose to recursively divided the curve in the middle and compute their control points until the error is below the threshold.

In the beautification steps, the author chooses to rotate the lines around their middle point to make the lines within the same cluster to have the same slope.

This paper also implements some basic recognition algorithm for some basic shapes like rectangle and oval.

Discussion:

This paper offers a good way to find the corners of a stroke. The authors beautify the lines based on the slopes. However, this paper doesn’t say much about how to beautify a curve. And, the basic object recognition is too simple. And I hope to know how this early process would facilitate the later works of sketch recognition.

Reading #6 Protractor: An enhanced $1 using angular distance

Reading #6 Protractor: An enhanced $1 using optimal angular distance

Comments on: 
Jianjie Zhang

Summary:

Li designed Protractor using a angular distance to calculate the similarity between candidates and templates. It is essentially similar with $1, both of them are template based recognizer. Compared with parametric recognizer(like Rubine’s method), template based recognizer  (1) does not need many training data; (2) do not have to choose features(which is not easy) to represent the parametric  model, therefore can be easily customized as long as the user provided related samples. However, template recognize is time and space consuming caused by many comparison needed.

In spite of the similarity, Protractor has many differences from $1:

(1)    Protractor can be orientation-sensitive, it rotate the stroke to one of the 8 base orientations which require minimum rotation.

(2)    Choose N=16 instead of N=64 to improve the computing speed and decreases the storage needed.

(3)    Using optimal angular distance rather than Euclidian distances to compute of similarity from certain template.

(4)    Because the size of stroke is irrelevant to compute angular distance, Protractor does not resize the stroke.

(5)    As for searching the optimal rotation, Protractor uses a closed-form solution to compute the optimal rotation rather than the time-consuming iterative approach used in $1 recognizer.

Discussion:

Protractor is a modification of $1 in many details, the biggest change is that it use angular distance rather than Euclidean distance. He also shows, when the critical distance computing method is changed, the supplementary processing of the strokes may also changes. I think, on the other side, the insight of how to preprocessing of the stroke can also lead to some new ways to compute the distances.  

 As indicated by the author, parametric recognizer is based on a parametric model and it is not easy to find a great model to include all the aimed gesture and exclude unrelated gestures.  Does it mean that this kind of method is not promising along with the improvement of computer speed and storage?

Reading #2 Rubine’s Linear Recognizer

Reading #2 Rubine’s Linear Recognizer

Comments on:
Amir

Summary: 

In this paper (in 1991), Rubine introduces GRANDMA as  a toolkit to easy the programmer of gestural interface. He uses GDP as an example of gesture based application. It defines some gestures and their related operations, using GRANDMA to recognize the input and then perform specified manipulation on graph. GRANDMA can only recognize single-stroke gestures.

Then, Rubine explains his gesture recognizer. His recognizer has two steps: first, calculate some features of the stroke. Then, using a linear machine, the stroke is classified as the class which returns the maximum value.

The author wants these features:

(1) can be computed in O(1) per input;

(2) to be meaningful, Among the 13 features chosen subjectively (or empirically) by Rubine, the first 11 are about the geometry character of a stroke and the last two are about speed.

(3) of course, be able to differentiate strokes.

A linear evaluation is computed to classify gestures. It simple adds all the features multiplied with different weights to give a value which can represent the fitness of being certain class.

The weights’ assignment is the critical part of the classification. They are obtained from training data as:

Rubine also introduce two ways to reject a classification result:

And Mahalanobis distance:

Rubine also discuss the tradeoff between rejection and undo in the gesture application.

Discussion:

Compare with $1 dollar, Rubine’s recognizer is more efficient after the training. It has limitation in the case that not enough data is offered (as Rubine’s analysis, 15 samples are needed to give a good accuracy).  Another one is it can only deal with single-stroke gesture.

The interesting thing is Rubine mention multi-finger input at the end of his paper. Does it has any relation with the Jeff Han’s multi-touch screen  technologies?

Reading #5 $1 Recognizer

Reading #5  $1 Recognizer

Comments on: 
Wenzhe Li

Summary:

$1 recognizer includes four steps:

1.  Resample the points of the stroke to a specific number N. This is achieved by adding new point at every distance of L/N along the path, where L is the length of the path.

2. Rotate the path by adjusting the angle formed between centroid and first point to ‘0’.

3. Scale and translate: expand or contract the original path into a square with width of ‘size’. Then, adjust its centroid to (0, 0).

4. Compute the sum of counterpart points’ distance (path distance) between the candidate and each template. Then, convert it to a score of matching to each template.

In order to find the optimal rotation angle which minimizes the path distance, the author also analyzes the usefulness of hill-climbing and GSS for similar comparison and dissimilar comparison. The result shows GSS is more efficient than Hill-climbing.

The four steps of $1 recognizer also prevent it from recognizing gestures that are sensitive on orientation, aspect ratios or position.

Discussion:

The advantage of hill-climbing in finding the optimal rotation angle is the number of iterations is small for similar pairs. And its drawback is the large number of iterations when used on dissimilar pairs. Since the suboptimality only decrease the possibility of mistake matches, why not just set a threshold, (e.g. 10)? The result of Hill-climbing could be as efficient as GSS as well as possibly increase our accuracy.

Reading #14 Using Entropy to Represent Curvature

Reading #14 Using Entropy to Represent Curvature

Comments on:

Summary:

This paper proposes an important feature that distinguished shape from text. That is, the entropy of stokes.  This paper thinks the text strokes are more randomly structured than common shapes. Therefore, we can use entropy measure to show their differences.

This paper defines an Entropy Model ‘Alphabet’. According to the angle with adjoining points, this paper matches each point to a one of seven symbols in the ‘alphabet’(six of them represent range of angle, and the last one represent ‘End point’). Then, we get an alphabet representation of ink strokes which can be computed entropy.

The implementation of this method firstly uses thresholds (spatial and temporal) to group the strokes in order to classify them later. Then resample the strokes, convert them into alphabet representation and compute their entropy using Shannon’s formula. After these steps, this paper classifies the strokes by the threshold obtained from training dataset. Except from test symbol and shapes, this paper’s method marks the strokes as “unclassified” when their entropies fall into neither of shape’s and text’s range.

This paper also computes the confidence of every classification by the distance of its distance from the threshold.

The results show that the accuracy changes along with the change of percentage of ‘unclassified’ strokes allowed. Also, the threshold shows reliablity when used on different domains.

Discussion:

I think the insight below the entropy method is that the curvature is an important feature that distinguishes text from shapes.  That is, the test symbols tend to have larger curvature changes on average length. Then, what is the advantage of using entropy instead of directly using curvature?
Also, I doubt that the entropy rate can be treated as a domain-independent feature to distinguish shape and text. For example, some languages may have text more like a shape.

Reading #3 Let's help the desingers

Comments on:

Wenzhe Li

Summary:

The problem of similarity always confuses people and computer as well. However, it is difficult for interface designers to solve this problem by themselves. This paper provides a tool named “quill”, which will automatically give advices to designers when it thinks is necessary.

Based on the similarity metrics that the author built from three experiments, quill predicts when the similarity problem would occur and offers unsolicited warnings and advices to designers.

The author found interface challenges in three areas: when to advice, how much to advice and what to advice. During the implementation stage, the author chose different strategies for user-initiated and system-initiated analyses. And because of the similarity metric, quill inclines to overestimate similarity when dealing with letter related gestures.

Discussion:

The author shows almost all the matters of developing software: what is its aim, the challenges of interface, implementation and underlying model (not perfect in this case). I realize that there is many things to consider when developing a software rather than just finishing its core algorithm and then being happy and satisfied. The author concerned a lot about details, which may not be very interesting and exciting but still need thorough consideration.

Reading #1 Gesture Recognition

Reading #1 Gesture Recognition


COMMENTS ON:

youyou wang
SUMMARY:

This paper is an introduction to gesture recognition and its three representative methods. In order to recognize gestures, the gesture recognition asks their path to remain the same, which is a main limitation.

Among the shown tree method, Rubine’s method and Long’s are based on features of the path. Rubine lists 13 features and the last two describe the feature of the max speed and the time used. While Long do not think these two feature is insightful and replace them with another 11 features. And both of these two gesture recognition need training set for their linear classifier to wok well.

Wobbrock’s recognizer is to transform the original gesture (in order to better comparing the template) and then match it to specific template (by calculating their “distance”).

DISCUSSION:

The computer needs to know enough information of the gesture in order to recognize it. This information can be achieved through two different ways: The computer learns it from its experiences or directly given by the user. Rubine and Long follow the former one, defining the feature that they thought adequate to recognize a path and then throwing input to train the recognizer. While Wobbrock chose to give the computer a database of some candidate templates, transform the input and try to match it to the database.

So which way is a better way? And is accuracy the only criteria? Wobbrock’s method tends to perform better but cost more time and show limitation when facing the variation of the same gesture. So, “to teach people to learn is more important than to teach people to know” also applies on gesture recognition?