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