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.