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