Accurate Primitive Sketch Recognition and Beautification

Accurate Primitive Sketch Recognition and Beautification

Summary:

The primary contribution of this paper is introducing a low-level sketch recognition and beautification system that uses two new features and a novel ranking algorithm.

The two new features are:

(1) Normalized Distance between Direction Extremes(NDDE): The distance between the point with highest direction value( change of y over change of x ) and the point with lowest direction value, divided by the length of the stroke.

(2) Direction Change Ratio( DCR ): The maximum change in direction divided by the average change in direction.

The novel ranking algorithm is used to assign a score to interpretations of input sketch. The one with lower score is a better interpretation of the input sketch.

The score table of primitives is as follows,

An example about how the ranking algorithm works:

Implementation:

The architecture of the low-level sketch recognizer in this paper:

In pre-recognition stage,

(1)     Remove consecutive, duplicate points from the stroke. These points can occur in systems with a high sampling rate.

(2)     A series of graphs and values are computed for the stroke, including direction graph, speed graph, curvature graph and corners.

(3)     Compute the NDDE and DCR mentioned in Summary Section.

(4)     Remove “tails”( the endpoints of strokes ) before sending the stroke to each of the shape tests.

(5)     Test whether the stroke is overtraced( shapes make multiple revolutions ) and closed.

In test stage,

(1) Line Test

1) Fit a least square line to the stroke points.

2) Determine the least square error, which must below a certain threshold.

3) The feature area of the line is divided by stroke length to get an error which must be within a threshold.

4) Verify the stroke is not overtraced and only contains 3 corners.

(2) Polyline Test

1) Break the stroke into substrokes at the calculated corners.

2) send each sub-stroke to the line test and keep track of the sum of least squares errors as well as the sum of the feature area errors.

3) Check three conditions.

(3) Ellipse Test

1) calculate the ideal major axis, center and minor axis.

2) check to make sure the some conditions apply.

(4) Circle Test

1) calculating an ideal radius, center.

2) pass some conditions

3) verify it is better fit a circle rather than an ellipse by calculating the major/minor axis ratio, which must be near certain threshold value.

4) feature area error verification

(5) Arc Test

1) calculate the ideal center point of the arc.

2) calculate the ideal radius of the arc.

3) test: not closed or overtraced and must have high NDDE value and low DCR value.

4) calculate the feature area of the arc and make sure its error is below a certain threshold.

(6) Curve Test

1) calculate d+1 control points and estimate the control points by solving a system of equations.

2) generate the ideal curve according to the Bezier curve formula.

3) test: low DCR value as well as a low least square error.

(7) Spiral Test

1) break the stroke up at every 2pi interval.

2) test: most be overtraced, NDDE must be high, each sub-stroke is fit to a circle, box radius must be less than a threshold and centers of consecutive sub-strokes must be close to each other

3) calculate the distance between endpoints and divide it by stroke length (helpful for distinguishing spirals from helixes)

(8) Helix Test

1) choose constant radius and the major axis.

2) find the starting and ending center points.

3) find center point for the rest revolutions.

(9) Complex Test

1) break a stroke up into two sub-strokes at the point of highest curvature.

2) each stroke is then recursively sent back into the recognizer.

3) add an additional step: send sub-strokes to a secondary function which attempts to recombine consecutive sub-strokes and check if they can be treated as a single primitive.

4) replace them.

In hierarchy stage,

Sort interpretations of sketch using the ranking algorithm mentioned in Summary Section.

Bibliography:

B. Paulson and T. Hammond. Paleosketch: Accurate primitive sketch recognition and beautification. InIUI ’08: Proceedings of the 13th international conference on Intelligent User Interfaces, pages 1–10, New York, NY, USA, 2008. ACM Press.

What!?! No Rubine Features?: Using Geometric-based Features to Produce Normalized Confidence Values for Sketch Recognition

Using Geometric-based Features to Produce Normalized Confidence Values for Sketch Recognition

Summary:

This paper proposes a hybrid recognition scheme by combining Gesture-based recognition and Geometric-based recognition together. With the hybrid recognition scheme, highly accurate classification will be achieved while maintaining user independence and allowing users to draw freely.

Sketch Recognition Methods:

In general, there are two approaches for sketch recognition. One is gesture-based. The other is geometric-based. Gesture-based recognition focuses on how a sketch is drawn. It takes the sampling points(x,y,t) of a stroke as input and then classifies the stroke into a set of pre-defined gestures. This kind of recognition scheme is fast but it needs user-dependent feature sets and requires individual training by each user. Geometric-based recognition focuses on what a sketch looks like. So it is more user-independent. However, geometric-based recognizer usually uses numerous thresholds and heuristic hierarchies which are hard to analyze and optimize in a systematic fashion.

Unlike gestural recognizers using statistical classifiers, geometric recognizer uses error matrix to compare a sketched shape and its ideal version with a series of geometric tests and formulas.

Hybrid Recognition Scheme:

The hybrid recognition scheme remains the strength and avoids the drawbacks of the two recognition methods mentioned in last section by taking a few features from each of the two methods. The overall picture of all features in hybrid recognizer is as follows,

The first 31 features are geometric features. The last 13 features are Rubine gestural features. The bold ones are the optimal feature set after feature subset selection using sequential forward selection technique. It is discovered that gestural features are less significant in aiding freely sketch recognition.

Bibliography:

Paulson, Brandon, Pedros Devalos, Pankaj Rajan, Ricardo Guitierrez, and Tracy Hammond. "Texas A&M : OBJECT 1237321989 : Hammond Cv." Texas A&M : OBJECT 1237321989 : Hammond Cv. N.p., n.d. Web. 12 Feb. 2013.

Visual Similarity of Pen Gestures

Visual Similarity of Pen Gestures:

Introduction:

         Supporting Pen Gestures is a desirable feature for user interface because it is fast by means of specifying both operands and operation in one stroke. However, it is difficult to design excellent gestures. Sometimes, gestures are hard to be remembered by users. Sometimes, they are misrecognized by computers. The primary contribution of this paper is to provide 22 possible predictors for similarity of features obtained through gesture similarity experiments.

What are excellent features:

Similar operations with a clear spatial mapping, such as scroll up and scroll down, should be assigned similar gestures. Conversely, gestures for more abstract operations that are similar, such as cut and paste, may be easily confused if they are visually similar.

Similarity Trial One: 

The data set of trial one consists of gestures that are varied widely in terms of how people perceive them.

The purpose of trial one is

(1)to determine what measurable geometric properties of the gestures influenced their perceived similarity

(2)to produce a model of gesture similarity. When given two gestures, the model could predict how similar people would perceive those two gestures to be

After analysis, the following 22 possible predictors for similarity are given,

As we can see from table 2, for this widely varied data set in trial one, Curviness and Total Angle Traversed/Total length is most important in determine the similarity of two gestures.

Similarity Trial Two:

The purpose of trial two is exploring how systematically varying different types of features would affect perceived similarity.

The data sets used in trial two are as follows,

After analyzing the result of trial two, the authors conclude that Log( aspect ) and density to be the main factors in determine the similarity of two gestures.

Bibliography:

Long A C, Jr, Landay J A, etal. Visual Similarity of Pen Gestures[D]. Berkeley, California:Department of Electrical Engineering and Computer Science, University of California at Berkeley, April, 2000.

“Those Look Similar!” Issues in Automating Gesture Design Advice

“Those Look Similar!” Issues in Automating Gesture Design Advice

    This paper primarily talks about the concept of advising interface designers unsolicitedly on how to make their new input gestures less similar with existing ones if they are perceived to be similar by machines. The authors developed a tool, called Quill, to realize the concept. With the help of quill, it will be easier for interface designers to generate excellent gesture sets and incorporate gesture recognition into the interface they want.

    In the second section, the paper introduces the satisfactory experimental outcome for Quill. It turns out, when inputting a pair of non-similar gestures, Quill will perceive them to be non-similar with an accuracy of 99.8%. Although sometimes a pair of similar gestures may be perceived as non-similar (about 22.4%), the overall accuracy of 87.7% is still acceptable.

    In the third section, the paper introduces 10 to 15 gesture examples of each gesture class are needed to train Quill gesture recognizer. The gesture classes will be organized into gesture groups. Quill uses similarity metrics to predict whether people will perceive two gestures to be similar.

Figure 1.Training:10-15 gesture examples for each gesture class

Figure 2.The new drawn gesture is perceived to be similar to the copy class

    The last section of the paper is about three advice-related UI challenges, implementation challenges and a similar metric challenge.

• Advice-related challenges:

    ---Advice Time:

    The drawbacks of early advice time: Distract users; Advice may become stale as user works.

    Quill gives advice when designer begins to test a gesture. Testing is a sign that designer has already completed entering a new class.

    ---How much advice:

    Quill shows a concise message initially. It is a hyperlink and can be opened for detailed information.

    ---What advice:

    English prose supplemented with drawings.

• Implementation challenges:

   ---Background Analysis:

   For user-initiated analyses, Quill disables all user actions that would change any state during advice computation.

   For system-initiated analyses, Quill allows any action, but if a change happens that affects analysis, analysis will be canceled. After that, canceled analyses will be automatically restarted.

   

   ---Advice for hierarchies:

   In quill, all notices(i.e., pieces of advice) that apply to an object are stored in a list property of the object.

• Similarity metric challenges:

   ---The models Quill uses to predict human-perceived similarity are not perfect, and participants rightly disagreed with it at times. The model seemed especially prone to overestimate similarity.

Bibliography:

Long A C, Landay J A, Rowe L A. “Those Look Similar!” Issues in Automating Gesture Design Advice[D]. Orlando:Carnegie Mellon University,University of California at Berkeley, 2001.

Specifying Gestures by Example

Blog on paper: Specifying Gestures by Example

Summary:

    Although the creative HCI by means of gestures is appealing, it is not rapidly developed due to the difficulty to create gestures and the code complexity of gesture recognizer. Therefore, this paper primarily talks about GRANDMA (Gesture Recognizers Automated in a Novel Direct Manipulation Architecture), with which gesture recognizer can be created automatically from example gestures, removing the need for complicated hand coding.

    Each recognizer is rapidly trained from a small number of examples of each gesture. The attributes of these gestures should be meaningful and be considered in gesture classification.

    Then this paper refers to GDP, which is a gesture-based drawing program built with GRANDMA. All gestures in GDP are arranged in hierarchy view classes, as shown in Figure 1.

 Figure 1. GDP view classes and associated gesture sets

    Next, it tells us how to add a new gesture into GDP’s initial click-and-drag interface.
(1)Create a new gesture handler and associate it with the GraphicObjectView class in Figure 1. The gesture handler window is shown in Figure 2.

Figure 2. 4 new gesture class in gc6 – gc9

(2) Enter training examples for each new gesture class. Figure 3 shows the process of entering 7 training examples for “Delete” gesture class( gc9 ). Typically, 15 training examples per gesture class is perfect.

Figure 3. 7 training examples for “delete” gesture

    After introducing how to add new gestures, the paper begins to talk about gesture recognition. The essential of gesture recognition is given a input gesture g, determine from a set of C gesture classes, to which g belongs.

    Each gesture is represented by an array of sample points:

g_p = ( x_p, y_p, t_p ), 0<=p<=P, 

P: total number of sample points, t_p: the time specific point is drawn

    Feature is an important aspect to classify gestures. There are three principles for the selection of features:

(1)They should be incrementally computable in constant time per input point.

(2)They should be meaningful so that it can be used in gesture semantics and for recognition.

(3)There should be enough but not too many features to provide differentiation for all gestures.

    The following 13 features, shown in Figure 4, are a good selection to identify strokes:

A few noticeable points:

(1)cos(α) and sin(α) are used as a feature instead of the α itself to avoid a discontinuity as the angle passes through 2pi and warps to 0.

(2)The initial angle features are computed from the first and third mouse point because the result is generally less noisy than when computed from the first two points. Nowadays, because of the enhancement in sampling precision, we may take the first and the fifth point as measurement points.

Gesture Classification formula:

Training:

    The purpose of training is to determine the weight of Wc0 and Wci

from example gestures.

Rejection:

    The purpose of rejection is to rejecting ambiguous gestures and outliers.

Eager recognition and multi-finger recognition:

    Eager recognition: the recognition of gestures as soon as they are unambiguous. In this recognition, classification occurs on every mouse point.

    Multi-finger recognition: the recognition of gestures made with multiple fingers simultaneously. By treating the multi-finger input as multi-path data, the single-stroke recognition algorithm may be applied to each of the path individually and the result combined to classify the multi-path gesture.

Bibliography:

Specifying Gestures by Example, Dean Rubine, Information Technology Center, Carnegie Mellon University, Pittsburgh, PA, SIGGRAPH 91, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, Pages 329-337, ACM New York, NY, USA 1991. http://dl.acm.org/citation.cfm?id=122753

Gestures without Libraries, Toolkits or Training: A $1 Recognizer for User Interface Prototypes

Gestures without Libraries, Toolkits or Training: 

A $1 Recognizer for User Interface Prototypes

Summary:

    This paper primarily introduces $1 recognizer, which is an easy, cheap, and usable recognizer consisting of about 100 lines. Although it is a simple recognizer, it can still achieve excellent recognition accuracy, even better than more complicated recognizer, such as Rubine recognizer.

The $1 gesture recognizer:

    The ultimate aim of $1 recognizer is to determine which set of previously recorded template points Ti most closely matches the set of candidate points C from user’s gesture result. However, this is not easy with a few concerns between templates and candidate, such as different size, angle, drawing speed and so forth. Keep these concerns in mind and the desire for simplicity, there are several requirements to $1 recognizer:

(1)Be resilient to variations in sampling due to movement speed or sensing;

(2)Support optional and configurable rotation, scale, and position invariance;

(3)Require no advanced mathematical techniques (e.g., matrix inversions, derivatives, integrals);

(4)Be easily written in few lines of code;

(5)Be fast enough for interactive purposes (no lag);

(6)Allow developers and application end-users to “teach” it new gestures with only one example;

(7)Return an N-best list with sensible [0..1] scores that are independent of the number of input points;

(8)Provide recognition rates that are competitive with more complex algorithms, such as Dynamic Time Warping and Rubine.

    With these requirements in mind, $1 recognizer is realized with a simple 4-step algorithm.

A simple 4-step algorithm:

(1) Resample the Point Path

The purpose of this step is to eliminate the influence of movement speed to the number of input points in a gesture. For example,

Figure 1 The relationship between articulation speed and number of input points

Usually, we resample gestures such that the path defined by their original M points is defined by N equidistantly spaced points( 32<=N<=256 ).

Figure 2 The effect of different number of resampling point

Figure 2 shows that when N = 32, the sampling points are too sparse to identify path. However, when N = 128, it is so dense that will add time to path comparisons.

A common way to solve this problem is:

(1)Calculating the total length of the M-point path.

(2)Dividing the length by (N-1) to obtain the length of each increment L between N new points.

(3)Step through the path such that when the distances covered exceeds L, add a new point.

(2)Rotate Once Based on the “Indicative Angle”

We define “Indicative Angle” as the angle formed by the centroid and starting point of a gesture. Find this angle and rotate the gesture so that the angle is at 0 degree. The process just like the following figure shows,

Figure 3 Rotate gesture so that indicative angle is zero

(3)Scale and Translate:

Considering the difference in the size of candidate and template, the candidate will be scale into a reference square.

After scaling, the gesture is translated to a reference point so that the centroid is exactly at the reference point.

(4) Find the Optimal Angle for the Best Score:

A key to determine match or not between candidate and template is the following equation:

It defines the path-distance between candidate and template. The template with the minimum path-distance to candidate is the result of the recognition.

After di is computed, we converted it into a range [0,1] score using:

The variable size is the length of a side of the reference square.

An analysis of Rotation Invariance:

In step 2, adjusting “indicative angle” to 0 degree cannot guarantee the minimum path-distance between candidate and template. It is just an approximation. However, there exist a few approaches to help us achieve the minimized path-distance. One is “seed and search”, this brute force approach simply rotate candidate by +1 degree for all 360 degree and take the best result. An improvement to this approach is called “hill climbing”. It rotates candidate by +/- 1 degree for as long as candidate’s path-distance to template decreases. Nevertheless, hill climbing is not so effective for dissimilar ones. Another improvement called Golden Section Search guarantees it will finish after exactly 10 iterations, regardless of whether or not two gestures are similar.

Figure 4 Path-distance as a function of angular rotation away from zero indicative angle for similar and dissimilar gestures

Limitation of the $1 recognizer:

(1)$1 recognizer cannot distinguish gestures whose identities depend on specific orientations, aspect ratios, or locations. For example, separating squares from rectangles, circles from ovals, or up-arrows from down-arrows is not possible without modifying the algorithm.

(2)horizontal and vertical lines are abused by non-uniform scaling

(3)$1 recognizer does not use time, so gestures cannot be differentiated on the basis of speed.

Conclusion from evaluation:

(1)Medium articulation speed is more accurate than slow and high articulation speed for Rubine, $1, and DTW.

(2)The more number of templates, the more accurate the recognition will be.( Rubine will have most significant improvement with the increase of template )

Bibliography:

Gestures without Libraries, Toolkits or Training: A $1 Recognizer for User Interface Prototypes, Jacob Wobbrock and Yang Li, The Information School, University of Washington, Seattle, Washington, Andew D Wilson, Microsoft Research, Redmond, Washington, UIST 2007, Proceedings of the 20th annual ACM symposium on User Interface Software and Technology, Pages 159-168, ACM New York, NY, USA 2007
http://dl.acm.org/citation.cfm?id=1294238

Blog on Sketchpad---A man-machine graphical communication system

Ivan Sutherland's main accomplishments in terms of modern day topics of current research in computer science:

(1)Ivan Sutherland created a new way for people to interact with computers through drawing on the screen and some ancillary buttons, switches and knobs. The popular touch screen/pad control of a bunch of electronic devices nowadays is derived from the idea of Ivan Sutherland.

(2)His Sketchpad can be considered to be the ancestor of modern computer-aided drafting (CAD) programs as well as a major breakthrough in the development of computer graphics in general. For example, the Graphic User Interface was derived from the Sketchpad as well as modern object oriented programming.

What I learnt through this paper:

(1)  Sketchpad is a computer program that realizes human-computer interaction through line drawings instead of cumbersome typed words.

(2)  With sketchpad, we can draw as we wish with the help of a light pen, turning knobs and function switches.

(3)  Sketchpad’s usefulness:

(3.1)For storing and updating drawings

(3.2)For gaining scientific or engineering understanding of operations that can be described graphically

(3.3)For circuit simulations as a topological input device

(3.4)For highly repetitive drawings

(4)  Three general elements of Sketchpad system, they are sub-pictures, constraints and definition copying. Sub-pictures are symbols drawn by users. Constraints are kind of relationship between picture parts( such as perpendicular, parallel, of equal size, lying on the other parts and so forth ). Definition copying means composite operation.

(5)  Structures:

(4.1)Ring structure:

In my opinion, this structure is just like a circular double linked list. By following pointers in the line block, not only will the end points of a line segment be found, but all the line segments terminating on a particular point will be found by following a string of pointers that starts within the point block.

(4.2)Generic structure:

The n-component elements( such as line blocks ) are collected under a generic header, which contains all the information that makes this type different from other types. It is a hierarchy structure.

(6)  Uses of light pen:

(5.1)Positioning picture parts: indicate the coordinate a new picture part should be.

(5.2)Demonstrative parts: point to existing picture parts for a possible change. To accurately pointing to a picture part, the part should not be too far from the center of the light pen in order to be identified by the sketchpad system.

(7)  The information for display spot:

Each display spot has 36 bits information. 20 of them give the coordinates of the spot in display system. The rest give the address of the n-component element which is responsible for adding that spot to the display. All the spots in a line are tagged with the ring structure of that line and all the spots in a sub-picture are tagged as belonging to that sub-picture.

(8)  The difficulty of magnification of pictures:

After magnifying the picture, only a portion of the original picture can be shown on screen. Sktechpad system will compute which part will appear on screen and generate relevant display spots. The difficulty lies on the edge detection problem.

(9)  Display of abstraction:

The abstraction that can be displayed is either constraints or the value of a set of digits.

Constraints: the fact that the start and end points of a circle arc should be equidistant from the circle center.

(10)  Recursive functions of Sketchpad

(9.1)Expansion of sub-pictures: sub-pictures within sub-pictures to as many levels as desired.

(9.2)Recursive deletion: If one thing on which another thing depend is deleted, the dependent things will also be deleted.

(9.3)Recursive merging:

If two things of the same type which are independent are merged, a single thing of that type results, and all things which depended on either of the merged things depends on the result of the merger.

(11)  Other functions:

Copy function: Once a sub-picture is copied, it loses its identity as a single part and the individual parts of the original sub-picture may be deleted at will.

(12)  Constraints satisfaction:

The advantage of Sketchpad system over traditional pencil work is, once a constraint is added, the already drawn parts will be automatically satisfied by the computer to make the drawing take the exact shape desired.

(13)  Constraint type definition:

A subroutine that computes the existing values of the variables of a particular constraint of that type, and the error introduced into the system by that particular constraint.

(14)  Engineering and Artistic application of Sketchpad:

Patterns, linkages, dimension lines, bridges, artistic drawings and so forth.

Bibliography:

             Sutherland, Ivan E. "Sketch Pad a Man-machine Graphical Communication System." Sketch Pad a Man-machine Graphical Communication System DAC '64 Proceedings of the SHARE Design Automation Workshop (1964): 6.329-.346. Print