PaleoSketch

PaleoSketch proposes a new low-level recognition and beautification system that can recognize eight primitives with recognition rates of around 98.56%. Two new features NDDE and DCR along with a new ranking algorithm which help in distinguishing polylines from curves is the major contribution of the paper.

The system returns multiple interpretations which allows recognition errors to be corrected as a simple pen-click could be used to switch to an alternative interpretation. This recognizer can distinguish circle from ellipse and also can recognize spirals and helix which has not been supported in any previous low level recognizers.

Implementation:

 
Prerecognition: After basic prerecognition steps a series of graphs and values are computed for the stroke including direction graph, speed graph, curvature graph etc. Corners are also identified at this step.

NDDE (normalized distance between direction extremes) : Stroke length between the point with the highest direction value (arctangent angle of the change of y over the change of x) and the point with the lowest direction value.
DCR(Direction change ratio) : Maximum direction change divided by the average direction change.
For a polyline NDDE is low and DCR is high, whereas for a curve NDDE is high(nearly 1) and DCR is low.

Hierarchy is needed to sort the interpretations. A new ranking algorithm was introduced which makes use of the corner finding algorithm.

My thoughts: The ranking algorithm introduced is a very good idea. This kind of algorithms can be used in different scenario. NDDE and DCR along with few other features can help in improving the accuracy.

Combining Corners from multiple segmenters

In this paper results of different polyline segmenters are combined using a variation of subset feature selection to achieve a all-or-nothing accuracy of .926. This increases the low level accuracy and benefits systems that rely on geometric languages to describe shapes.

The diagram above shows how 5 different corner finders are combined.

My Thoughts: This method could not produce results in real-time. This can be improved if the process is carried out in parallel. We could also try to reuse the information calculated for one corner finding algorithm in another.

World of workout

This is a mobile role-playing game to motivate people to engage in physical activity. There is a avatar associated with each player and it evolves based on exercises the user performs in reality.

Three levels:

User level: demonstrates how the individual actually interacts with the system, which is performed through mobile phones, a web page, and sensors

Logic level: demonstrates how the application works and is divided into the exercising and gaming engines respectively with added components

Data level: Stores all information and interacts with the program through HTTP and a server

The type and amount of exercise improve the characters speed, strength, and stamina based on the type and amount of exercise performed.

The game makes sure that the exercises are done correctly and in a healthy way. Fatigue factor helps in this.

My thoughts:

Applications can be built which let one know the speed of the car and using GPS locate the position of car and the speed limit allowed in that area which can be used to keep in check the driver's speed when it goes beyond the limit. This will help avoid a lot of accidents. This kind of application could already be present, but I am not aware of any such thing.

KSketch

This paper explains and evaluates the features of an application KSketch, a informal 2D animation sketching system. It was developed to help novices create wide range of animations in a very less time. The research starts off with interviewing of animators and non-animators. The interviews confirmed the importance of informal animation tool. The researchers came up optimization technique to shortlist the features that need to be supported from the list of features that was made after analyzing users interest. The selected features are Translate, Scale, Rotate, Set Timing, Move Relative, Appear, Disappear, Trace, Copy Motion, and Orient to Path. Repeat Playback and Copy Object also have been added.

The interface of K-Sketch has three parts: a tool bar on top, a drawing canvas in the center, and time controls on the bottom. Physical "Alternate" button is used to alternate between modes.

There is no difference between recording and replaying in K-Sketch - edits to a playing animation are recorded and this means that all objects move simultaneously when time advances.

My thoughts: This is a great sketch recognition application whose use case is spread across domains. If the sketch recognition could add beautification also to this it would add a great value.

LADDER

LADDER is a hierarchical symbolic shape based sketching language to describe how sketched diagrams in a domain are drawn, displayed and edited. This domain description is then automatically translated into shape recognizers, editing recognizers and shape exhibitors for use with the customizable base domain independent creating a domain specific sketch interface thet recognizes the shapes in the domain, displaying them and allowing them to edited as specified in the decsription

LADDER descriptions primarily concern shape, stroke order and direction. LADDER consists of predefined shapes, constraints, Editing behaviors and display methods as well as syntax for specifying domain description.

Both top-down and bottom-up recognition is used for sketch recognition using LADDER.

two types of constraints are used - hard and soft. Hard constraints must be satisfied. Soft can aid recognition by specifying relationships that usually occur.

Shape definition: Definition of shape consists of following: Components, constraints, aliases, editing, display. The shapes can be defined hierarchically. Also, it is possible to define abstract shapes.

The language consists of predefined shapes, constraints, editing and display methods.

Steps in recognition
Primitive recognition: This is domain independent and can produce more than one interpretation. All interpretations are sent to higher level recognizer

Domain shape recognizer: It is performed by Jess rule based system.

The system was evaluated by using it for multiple domains: UML class diagram, mechanical engineering, COA, flow charts.

My thoughts: This is a very important progress in sketch recognition. The exponential time here can be avoided here using the technique used in  paper "Recognizing Interspersed Sketched Quickly" where the sub trees are pruned.

Am image based, trainable symbol recognizer for hand-drawn sketches

Characteristics of recognizer

1. Template representation: Uses an image-based recognition system. Input symbols are described as down-sampled bitmap images which we call "templates".

Advantages: Pen stroke segmentation is eliminated.

Suita able for recognizing sketchy symbols

Symbols drawn with multiple strokes or varying orders so not pose difficulty.

2. Learning from a single example: Enables users users to create, extend and update their own library of symbols without the need for extensive training. Single prototype is enough for system to work.

Advantage: users can seamlessly train new symbols.

 remove or overwrite existing ones on the fly

existing symbols do not need to be retrained or adjusted upon the introduction of a new symbol

3. Multiple classifiers: Four classifiers were used in combination which outperforms the individual classifier

4. Achieving rotation invariance invariably: The system uses polar coordinate to determine best alignment angle for comparing. The rotations on screen coordinates become translation using polar coordinates.

5. Two step recognition: Polar coordinates eliminates a large number of unlikely matches. This is followed by a detailed evaluation of the reduced set of candidates in screen coordinates.

6. System Architecture:

Preprocessing: A template is formed of size 48 x 48 preserving the aspect ratio.

Template matching using multiple classifiers

1. Hausdorff distance:

H(A,B) = max(h(A,B), h(B,A)) where h(A,B) = max( min ||a-b||)) - directed hausdorff distance

Maximum of all the distances one can measure from each point in A to closest point in B.

2. Modified Hausdorff distance :

hmod(A,B) = i/N sum(min||a-b||)

N is number of points in A

3. Tanimoto coefficient:

T(A,B) = nab/(na+nb-nab)

where na is total number of black pixels in A

nb = total number of black pixels in B

nab= total number of overlapping black pixels

T(A,B) specifies the number of matching points in A and B, normalized by the union of the two point sets.

maximum similarity = 1

minimum similarity =0

Two pixels are overlapping if they are at a distance of 1/15th of image's diagonal length. For 48 x 48 it is 4.5 pixels.

4. Yule coefficient :

maximum value = 1, minimum value = -1.

Distance transform:

It is a morphological operation that converts a binary bitmap image into an image in which each pixel encodes its distance (we use the Euclidean distance) to the nearest black pixel in the same image. The resulting image is called a distance map. This is done during preprocessing.

Polar coordinates are used to rotate the sketch.

User Studies:

Two experiments: using 20 graphic symbols and digits

Limitation: Insensitive to translation, rotation and uniform scaling but sensitive to non-uniform scaling . Square and rectangle would be treated different. But not always advantageous. For example, a cantilever having different length will be classified as two distinct sketches though practically they are same in most cases.

 Quantization of input into template may wash out minute details

Recognizing Interspersed Sketched Quickly

This paper present a high-level recognition algorithm that allows for complete interspersing freedom, running in real-time through effective sub-tree pruning. Shapes are indexed as they are drawn using geometric properties and are inserted into hash table. This allows us to search quickly for all possible subsets of shapes facilitating higer level recognition.

Indexing Algorithm:
1. Domain-independent primitive recognition: uses Sezgin paper
2. Domain independent constraint indexing : All shapes are inserted into hash tables based on their geometric properties as soon as they are drawn or recognized.
3. High-level recognition: Each time a new line is drawn system checks if it can be part of any known shape built from it and all previous lines. It does this by putting the new line in each possible slot in each template, putting all uninterpreted previously drawn lines in other slots and treating problem as constraint satisfaction problem with geometric constraints refining values

Speedup of algo due to:
1. Heavy computing is performed in indexing stage(linear)
2. Subtrees are pruned as they are generated
3. Smart ordering of constraints.

Two tests were conducted
Stress Test
Multi domain test

My thoughts:
The idea of using hash table to store all shapes with similar properties is very innovative. 

HMM in sketch recognition

In this paper, sketches are considered as interactive and incremental process rather than collection of strokes or images. It is a polynomial algorithm.

Stroke ordering is an important source of knowledge in recognition which has been used in the paper. This is called sketching style.

Three tasks for sketch recognition:

Segmentation: Grouping strokes so that all those from same object are in one group
Classification: Which object each group represents
Labeling: Assigning labels to components of recognized objects

Dynamic properties of sketches( interactive, incremental and highly stylized) is used in this paper. Analysis was done to find the extent to find the extent to which people have sketching styles. Also sketching style diagrams were constructed.

The user input is encoded to generate observation sequences and this is used to compare to its model of how a user draws.

Modeling with HMM
Encoding: The strokes are converted to give geometric primitives. This is then encoded into sequences using 13 symbols.

Since instances of the same object sketched in different styles may have encodings of different lengths, two frameworks were used - modeling with fixed and variable input length HMM. This is used to segment and classify the objects. It not only gives the best classification but also the the next k-best segmentation.

For testing four domains were used- domains of geometric objects, military course of action diagrams, stick-figure diagrams, and mechanical engineering drawings.

The system does not require that the user finish drawing the current object before it can be run (i.e., it
doesn’t need to be told that user is done sketching). It can be run after each stroke is added to the surface.

My thoughts: Recognizing the drawing even before completing could be a very interesting feature in the application for the user using it. One disadvantage that I think is present in this model is that it is user dependent and needs the system to be trained for the user

ShortStraw

ShortStraw is a polyline corner finder that finds the minimum set of points such that, if a polyline is split at those points, the resulting primitives would consist only of lines.

Implementation:
1. Resampling: Interspacing between points = Diagonal Distance/Constant. Constant=40
2. Corner finding: It used both bottom up and top-down strategy

Bottom up : Straw for a point pi is calculated as
straw(i) = |pi-W􀀀; pi+W|
As a stroke bends around a corner, the straws of points will begin to shorten, and the local minimum straw at point index k is a likely corner.
Any point k is a corner if its straw(k) is local minimum below threshold t.
Threshold = .95*median of all straws

Top-Down:
a. Check to see if each consecutive pair of corners passes a line test.
r = DISTANCE(points,a,b)/PATH-DISTANCE(points,a,b)
If r is above 0.95, then segment between a and b is considered line

If stroke segment between two consecutive corners do not form a line, then there is a corner between them. The corner is approximately halfway between the points. the threshold is relaxed to find the corner.

b. Collinear check is run on sets of three consecutive corners. If it passes the test, the middle corner is removed.

Two measures to determine accuracy of each corner finder :
1. Correct corners found - does not penalize for false negatives. Accuracy is 1 if every point is returned as a corner.
2. All or nothing : Number of correctly segmented strokes / Total number of strokes.

Advantages: Doesn't use temporal info, Complexity is less.

My thoughts: It is an extremely simple and intuitive method used. We can use few more features along with this and use it for multi-stroke polyline corner finding. 

KimCHI: A Sketch-Based Developmental Skill Classifier to Enhance Pen-Driven Educational Interfaces for Children

KimCHI is a  specialized sketch recognition technique to ananlyse children's sketches to asses their developmental progress. It distinguishes between developmental stage within age group and also gender among children.


To find the optimal subset features we use BestFirst selection built into weka system with 10 fold croos validation.
Optimal features for classifying preschoolers vs grade schoolers
Average curvature of the stroke (100%)
+ Direction change ratio (100%)
+ The error of the best fit line of the direction graph (100%)
+ The maximum curvature to average curvature value (100%)

Optimal features for classifying preschoolers vs adults
Average curvature of the stroke (100%)
+ Direction change ratio (100%)
+ The angle of the major axis relative to center (100%)
+ The error of the best fit line of the direction graph (100%)
+ The maximum curvature to average curvature value (100%)
+ Slope of the direction graph (100%)

Classifier Set:
Bayes Net, BFTree, ADTree, MultilayerPerceptron, Naive Bayes, Random Tree, Random Forest, and RBFNetwork

Best classifier for recognizing age: Random forest classifier and Bagging.

Optimal features for classifying genders:
Stroke density (100%) +
A density metric for the gesture stroke that uses the stroke’s length
and bounding box size (100%) +
Direction change ratio (70%)

Best Classifier : Bayes Net

My thoughts: This gives us insight of how we can use sketches in psychology. Such recognition techniques should be used in finding disabilities as well. Features like pen pressure, tilt also can be considered to find the developmental stage of children.  

Tahuti: A Sketch Recognition System for UML Class Diagrams

Tahuti is a system designed to recognize UML diagrams. It is a dual view( interpreted view and drawn view), multi-stroke sketch recongition environment. The system recognizes using the geometrical properties.

It is a multilayer framework. Each drawn stroke is interpreted as a line segment. The stokes that are spatially and temporally close are chosen and their line segments are chose are recognized as editing command or viewable object.

In figure (c)
A and B - are furthest point. It is the shaft
C and D - two furthest points on either side of shaft
E - point that is twice the distance from B as from intersection of CD and AB

Each line segment is classified as arrow head, shaft or unclassified. Based on this, each arrow is classified as dependency, inheritance, aggregation, or unclassi fied.

My thought

It is a very simple technique and can be extended to other domains where such simple objects are used like flowcharts. It would be a good idea to be able to allow the classes move in the interpreted mode and reposition them. The paper does not speak much of the editing commands that have been provided,
   

Fitts' Law

My presentation:

https://drive.google.com/file/d/0B23tu6kgHWPGR3JYRWhibDUxeG8/view?usp=sharing

Using Entropy to Distinguish Shape versus Text in Hand drawn Diagrams

Entropy rate is typically higher for text strokes an can be used to distinguish shape and text strokes. Using this single feature, zero-order entropy, a high accuracy was obtained.

Approach

Handwritten text strokes are more randomly structured which increases their entropy measure. Entropy is defined as measure of uncertainty associated with a random variable.

Entropy Model : Each hand drawn stroke is represented as string of the letters from alphabets.  Each point in the stroke is assigned a symbol depending on the angle it makes with its neighboring points. This symbol in the random variable based on which entropy is calculated. The entropy model in the paper has 7 symbols. Each symbol corresponds to a range of angles. The total range is [0,pi).

SYMBOL RANGE
A [0, /6)
B [ /6,2 /6)
C [2 /6,3 /6)
D [3 /6,4 /6)
E [4 /6,5 /6)
F [5 /6, )
X End points

Algorithm:

1. The diagram is classified into stroke groups. All strokes which are below spatial and temporal threshold are grouped together. Temporal threshold is 100 or 400 ms.
2. The strokes are resampled to smoothen the substroke angles and to makes points equidistant from each other.( 4 pixels)
3. Each stroke is assigned a string of symbols from the entropy model.
4. Probability estimate of each symbol is calculated by dividing the number of occurrences of that symbol by the total number of symbols. We sum the probabilities of symbols assigned to the points according to the formula
H(S) = -k∑_SP(xi) log(P(xi))
where P(xi) is the probability of label assignment of label(xi) to point xi in the stroke and k is a constant.
5. The resulting value is divided by the bounding box diagonal and this is the entropy rate of the stroke group.

A stroke  group is either classified as text, shape or unclassified. For unclassified strokes the entropy values lie between the text and shape entropy values.

Confidence measure was introduced to reflect the authority with which each classification was made.

C(x | TEXT) = 0.5 + (arctan(x- b))/pi
C(x | SHAPE) = 1 – C(x | TEXT)
b represents the entropy value for which classification of text is 0.5.

Tesing was done in two domains - military course of action and free body diagram. A ten-fold cross validation was used on COA and a accuracy of 99.56% was obtained on the produced classification which was 77.51%. For free body diagrams the threshold obtained from COA was used to measure the performance on unseen domains. In this case classification rate was 71.06% with overall accuracy 96.42%.
When the system was required to produce a classification always the accuracy was 96.02%.

Problem with zero-order entropy
Zero-order will not capture patterns which are repeating such as resistor and produce high values of entropy. This misclassification can be mitigated using low confidence values.

Sketch Based Interfaces

Author: Tevfik Metin Sezgin, Thomas Stahovich, Randall Davis

This paper describes a system where users can sketch naturally and this can be processed to have the sketches understood.

System:
The pen motion is sampled at 30 to 150 points/second. Early processing consists of approximation, beautification and basic recognition.

Approximation:
It is to approximate the stroke with compact and abstract description while minimizing error and avoiding over-fitting. It consists of identifying vertices at end of line segments and detecting and characterizing curved segments.
Vertex detection: Vertices are detected by looking for points that are minima of speed and maxima of absolute value of curvature. Average based filtering is used to find extrema corrponding to vertices while avoiding those due to noise. Mean of each data set is used as threshold and we look for extrema in those portions of curvature and speed data that lie beyond this threshold.   We use information from both sources generating hybrid fits by combining set of candidate vertices derived from curvature data and speed data.

Generating Hybrid Fits:
1. Computing vertex certainties: For curvature candidate vi, it is the scaled magnitude of curvature in its local neighborhood around the point.

|d_i-k-d_i+k|/l, where l is the curvature length between Si-k and Si+k. 

For speed fit, a certainty is a measure of pen slowdown at the point give by 1-vi/vmax, where vmax is maximum pen speed of the stroke.

Candidate vertices are sorted by certainty within each fit. The initial hybrid H0 is intersection of Fd and Fs. The highest scoring curvature and speed candidates are appended to Hi successively. Two new fits(one with best remaining speed fir and another with best remaining curvature fit) are created and their least square error metric(average of sum of squares of distances to the fit from each point in stroke S) is found. The vertex giving lesser error is added to Hi.

Handling curves:Curved regions are approximated with Beizer curves using two end points and two control points. Let u = Si and v= Sj, where i<j and Si and Sj are end points of the curve.  Control points are 

ˆt1 and ˆt2 are the unit length tangent vectors pointing inwards at the curve segment to be approximated. 

Beautification: 

This is done to ensure that lines which are apparently meant to have same slope end up being parallel. Using simple single window, we look for cluster of slopes. Each line in cluster is rotated around its mid point to make its slope be equal to weighted average of all slopes in cluster. The new vertices are the points of intersection of rotated lines. 

Basic Object Recognition: 

This is done with hand tailored templates that examine similar properties.

Evaluation: The system's identification was 96% of times correct for the 10 figures that were used to study.  The users found the system very easy and convenient to use. 

$1 Recognizer

$1 recognizer is a gesture recognizer to enable novice programmers to incorporate gestures into  UI prototypes. 

Algorithm:

The gestures are compared against already recorded templates.

Resample the point path : Resample gestures such that the path defined by their original M points is defined by N equidistantly spaced points. N=64 was adequate. 32<= N <=64 works well.

Rotate once based on Indicative Angle: We rotate the gesture to make its indicative angle 0. Indicative angle is the angle formed between the centroid of the gesture  and gesture's first point. 

Scale and Translate: Scaled to a reference square and translate the centroid to (0,0).

Find optimal angle for best score: Path distance between template Ti and C(candidate) is calculated using the following: 

Template Ti with lease di is selected. This minimum path distance is converted to a [0.. 1] score using 

Aligning template and candidate

After rotating the indicative angles of all gestures to 0°  there is no guarantee that two gestures C and Ti will be aligned optimally. We therefore must fine-tune C’s angle so that C’s path-distance to Ti is minimized. 

Brute force - Rotate C +1 degree for all 360 degree and take best result. It is slow and processor intensive

Hill Climbing - Path-distance graph has no local minima. Rotate +/- 1 degree until C's path-distance to Ti decreases.

Optimal angle - 4.2 degree from indicative angle. 

Indicative angle is a good approximation. But it is not efficient for dissimilar gestures. 

Golden Selection Search - The algorithm finds minimum value in the range using golden ratio. 

GSS loses |10.0–7.2|=2.8 iterations to hill climbing for similar gestures, it gains |10.0–53.5|=43.5 iterations for dissimilar ones

Limitations:

Cannot distinguish gestures whose identities depend on specific orientations, aspect ratio or locations. Does not use time and hence cannot distinguish based on speed.

$1, DTW and Rubine were compared for the gesture set designed for $1 recognizer. 

Rubine was less successful in recognizing compared to the other two recognizers.

Using Geometric-based features to produce normalized confidence values for sketch recognition

This paper discusses the hybrid approach of combing geometric-based and gesture-based recognition to produce a system with high recognition rate and providing normalized confidence values for alternative interpretations. It takes advantage of positive aspects of each.

Gesture-based Recognition: It focuses on how a sketch is drawn, not how the final sketch looks like. It takes an input stroke and classifies each one into pre-defined gestures.
Advantage: Fast classification along with normalized confidence values
Disadvantage: Features are user-dependent and require individual training.

Geometric-based Recognition: It focuses on how the sketch looks like and less on how it is actually drawn.  It takes single stroke as input and classifies them as one of predefined geometric primitives using formulas based on geometry. Primitives are combined to give more complex shapes using grammars.
Advantage: More user and style independent
Disadvantage: Use thresholds and heuristic hierarchies which are difficult to analyze and optimize in a systematic fashion. Inferences about generalization are hard to determine
Inferences about generalization is hard to determine because classification isn' statistical
Ranking alternative measure becomes difficult because of use of multiple error measure.

Ranking alternative interpretations with normalized confidence value aids in higher level recognition system which has access to context to resolve ambiguity in lower level interpretation.

The author combines the features of both gesture-based Rubine and geometric-based PaleoSketch giving a total of 44 features(31 from PaleoSketch and 13 from Rubine) and uses quadratic classifier.

Experiment: Data was collected from 20 users, each user giving 90 samples. The quadratic classifier was used to classify single stroke sketched primitives using 44 features.

Feature subset selection: Optimal subset selection was done using Sequential forward selection. 10 folds of SFS was performed using rrandom50 user splits giving 10 subsets. To determine the final optimal feature 25 folds of classification using random 50/50  was performed on each of 10 subsets. 10 other subsets were created. The first of this has features that were present in all 10 folds of subset collection, the second had features that were present in at least 9 of 10 folds and so forth. The best performance was of the subset with features that were present in atleast 50% of subset selection process.

Using this subset we achieved 97.44% of accuracy, close to PaleoSketch(98.56%). The classification difference between this approach and PaleoSketch is insignificant.

The susbet consists of 14 features, 13 from PaleoSketch and only one from Rubine.

Advantages of this approach: Faster classification because it uses lesser features.

Design Principles

Design Principles

1.Should be interactive

2. The recognition of shapes/gestures should be independent of user.

3. Should be able to identify single as well as multi strokes

4. Should make use of intuitive gestures while designing a gesture based system

5. Should give automated feedback and guidance

6. Should make use of features of a normal application in computer like copy/paste, undo/redo, changing thickness of the lines, switching colors of pen

7. The system should respond quickly

8. A single system can be made to respond to all kinds of input - mouse, finger, stylus

9. The gestures should be easy to learn and remember.

10. Rejection of the strokes/gestures/shapes should not be too much. It is better to ask users to redo than identifying shapes wrongly

11. Can learn from each user and improve the quality of the system on fly

12. Along with the use of gestures, can have the traditional menus to make the system more powerful. For example, in the K-Sketch system, we can have an option of entering the relative speeds of two objects while are moving in same direction(translation)

Mechanix Improvements

1. Should have an option of saving the assignment and getting back from the point where the student left the previous time

2. Conversion of units. For example, if a student gives the answer in kN instead of N, the system should be capable of doing conversion and respond.

3. When I put "10N" instead of "10 N" for the forces in the diagram, the input is marked in red though the answer is accepted

Visual Similarity of Pen Gestures

Citation : http://dl.acm.org/citation.cfm?id=332458

Authors: A. Chris Long, Jr., James A. Landay, Lawrence A. Rowe, and Joseph Michiels


This paper describes about a tools to help designers of sketch recognition systems to improve their gesture set and make it easier for the user. It will notify designer about the similar gestures, the gestures that are difficult to learn and remember and those that may be misrecognized by computer.

Two experiments were conducted to determine the features that affect gesture similarity.
Experiment 1: A wide range of gestures of different orientation was used. The user had to choose one of the three gestures which looked different from the other two in a triad. MDS and regression was used to analyse the data. From analysis using MDS it was found that ordinal model and eucledian distance gave the best fit and hence they were used for subsequent analysis.Regression analysis provided weights for each feature and correlation of the feature with similarity.

Experiment 2: Three new gesture sets, to explore total absolute angle and aspect, length and area, rotation related features, each of nine gestures were created to determine how a feature would affect perceived similarity. A fourth set consisting of two gestures from these three was created to compare three sets against one another. Data from each of the sets were analysed independently to determine how targeted features affected similarity.

Results of experiment 1 were used to predict similarities of gestures of experiment 2.

One important observation from both experiments was that neither length nor area were a significant feature for similarity. Experiment 1 predicts the data slightly better and  uses more features helping capture more about underlying psychological model

Specifying Gestures by Example

The paper discusses GRANDMA(Gesture Recognizers Automated in Novel Direct Manipulation Architecture) and GDP(Gesture-based drawing program) which was built using GRANDMA. With GRANDMA one can create gesture recognizers from example gestures, removing the need for hand-coding. In already existing gesture-based applications, the recognizer was hand coded which makes it difficult to create, maintain and modify.

GDP: The user begins the gesture by placing the mouse cursor and pressing the mouse button. The the user draws by moving the mouse. The end of gesture can be either by just releasing the mouse button in which case the gesture is recognized and drawn or can stop moving the mouse for given time  while pressing the button in which case the  recognized gesture is drawn and it allows dragging to resize and reshape the recognized shape. This is two-phase interaction, gesture collection followed by classification and manipulation. The gestures in GDP are all single strokes. This avoids segmentation problem which would be present with multi-stroke character recogniton and allows shorter timeouts to be used.\

GRANDMA is object oriented toolkit used to build click-and-drag interface and the application.  The following is the GDP's the view class hierarchy.

It is MVC like system. A single input handler may be associated with a view class and shared between instances of the class. Using GRANDMA one can easily add new gestures and give training samples for it. The semantic of each gesture can be changed by entering expressions for each of recog(which is evaluated when gesture is recognized), manip(which is evaluated on subsequent mouse points) and done(which is evaluated when mouse button is released)

Gesture recognition: A vector of features is extracted from input and it is classified as one of the C possible gestures via a linear machine. The features for this tool should be chosen considering following:

Small change in input should result in small change in each feature.

There should be enough features to differentiate gestures but there should not be too many that it starts affecting efficiency

Feature should be incrementally computable in constant time per input point.

Gesture classification : Gesture class c has weights wci for 0<i<=F where F is the total number of features. The classification of gesture is the one which maximizes the vc.

Training: Training is to determine wci from example gestures. A well-known closed formula was used.

Rejection: Ambiguous gestures and outliers should be rejected. Gestures having P(g was classified correctly)<0.95 are rejected. Another method uses Mahalanobis distance to determine standard deviation and rejects gestures having (standard deviation)^2 > (1/2)F^2. Rejection should be disabled in applications since it increases number of gestures that need to be redone. 

Thoughts:

User should be allowed to define his own features.

The tool can extend to include animation gestures too.

Different kinds of interfacing like finger touch  can be used.

Who Dotted the 'i'?

This paper describes a system which can automatically determine a stroke's owner in a collaborative environment even when strokes are drawn using the same pen, in close proximity and in close timing. It identifies user purely based on physical mannerisms of how the strokes are made. The mannerisms are tilts of the pen, pressure of the pen and the speed at which the pen moves.

Unobtrusive user differentiation can be used for security and verification, improved sketch recognition through user-modelling recognition and collaboration.

Two experiments were conducted using a drawing application created in Cocoa for Mac OS X and Cintiq which was used to collect data such as tilt and pressure of the pen. First experiment had six participants and its purpose was to determine if certain features could be used to disambiguate users and how to disambiguate using tilt and pressure. The result showed that users are fairly consistent with physical manner in which they sketch and their mannerisms are distinct from one another. Experiment two was conducted using 10 participants to determine if a classifier could be created that can accurately determine creator of a stroke from set of possible creators. The classifier used 24 features and a variety of learners like Linear classifier, Quadratic classifier. K nearest neighbor gave the best results. The influence of size of the creator set on accuracy to determine the creator was also tested. The identification rate was 97.5% and 83.5% for two and ten users, respectively.

By using additional context the accuracy can be improved.

Mechanix

Authors: Stephanie Valentine, Francisco Vides, George Lucchese, David Turner,
Hong-hoe Kim, Wenzhe Li, Julie Linsey, Tracy Hammond

Citation:http://www.aaai.org/ojs/index.php/aimagazine/article/view/2437

This paper describes about Mechanix which is a sketch-based tutoring and grading system for free-body diagram. It can recognize, correct and provide real-time feedback on a student's sketch that is compared with the instructor-entered key sketch. It is capable of understanding the student sketches and solve students' trusses without an instructor-provided sketch.

There are two modes supported by Mechanix - Student mode and Instructor mode. The interface of student mode contains text at the top center describing the problem, tool panel, checklist providing step-by-step guide to solve the problem, drawing panel, pullout notepad to make notes, equation panel. The system also has a feedback bar. The instructor mode allows instructors to add problem statement in form of simple text and explanatory images. They can also sketch a solution which the system uses to compare the student solutions. Instructors label nodes and forces and Mechanix generates equations and values for reaction forces. One can continually modify and edit their drawings using round menu, buttons and freehand erasure like on pen and paper.

Geometric Recognition is used in Mechanix. It uses bottom-up approach. The various steps involved are preprocessing, primitive recognition to identify basic shapes like lines, arcs or circles and  high-level recognition that uses constraints to determine complex shapes from the basic shapes. Mechanix uses cusp detector to identify strokes and a low-level recognizer called PaleoSketch which supports more than 10 basic shapes. Primitive recognition is also used to give visual feedback. For example, shape recognized as forced is changed to lime green indicating student may enter relevant meta data.

Mechanix supports truss diagram, non-truss diagram and creative response problems. Mechanix identifies trusses and compares with the instructor's values to give appropriate feedback. For non-truss body diagrams, a generic closed-shape comparison technique is used to compare student solutions with that of instructor. The other kind of problem that Mechanix supports is Creative response. Here it uses artificial intelligence to check the student-created truss. It creates linear system of equation and a system of equation is formed for each beam in truss. The Mechanix will use the values to compare to a set of constraints that the instructor previously entered and provides feedback.

The system keeps track of log of mistakes that a student commits while solving the problem. The answers are checked in a server to prevent cheating and feedback is sent to the client installed on student device. XML over HTTP is used to transfer data between server and client.


Thoughts:
The idea of having an application that allows students to solve assignments, gives continuous feedback and corrects the solution submitted is very helpful to both students and instructors. It would motivate the students to solve the assignments and instructors don't have to waste time in correcting each student's solution.

The most impressive feature is freehand erasure. The interface is similar to what one would do in real life when one makes a mistake while drawing and has no patience to use eraser. Other idea that I think are pretty cool are that of visual feedback(changing of the color of the force to get student's input value of force).