Project Reading 8

MathPad2: A system for the creation and exploration of mathematical sketches

Citation:

LaViola, Jr., J. J., and Zeleznik, R. C. Mathpad2: A system for the creation and exploration of mathematical sketches. ACM Trans. Graph. 23, 3 (Aug. 2004), 432–440

Summary:

MathPad is the system that Identifies structure of a given mathematical expression by parsing and analysis of input string. It is a tool for Mathematical problem solving and visualization. Mathematical sketching, a novel, pen-based, modeless gestural interaction paradigm for mathematics problem solving is presented. With a mathematical sketch, users can also leverage their physical intuition by watching their hand-drawn diagrams animate in response to continuous or discrete parameter changes in their written formulas. Mathematical sketching can also support computational tools for graphing,

manipulating and solving equations and initial feedback from a small user group of our mathematical sketching prototype application. MathPad2 introduces a new concept of combinations of handwritten mathematics and free-hand diagrams– that allow rapid animated visualization of mathematical formulations.

Discussion:

There is a restriction of the current prototype to closed-form expressions while drawing mathematical sketches if you need to use MathPad. Thus, the restriction does not make it for generic people. I think drawing restrictions should not be posed while making a system whose base is sketching.

Project Reading 7

                   MathBrush: A Case Study for Pen-based Interactive Mathematics

Citation:

Labahn, G., Lank, E., Marzouk, M., Bunt, A., MacLean, S., and Tausky, D. Mathbrush: A case study for pen-based interactive mathematics. In Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling, Eurographics Association (2008), 143–150.

Summary:

MathBrush recognizes mathematical expressions and facilitates problem solving using backend computer algebra systems. Current generations of computer algebra systems require users to transform two-dimensional math expressions into one-dimensional strings, to master complex sets of commands. Then analysis can be done on the output strings. MathBrush provides a pen-based interface to many of the features of computer algebra systems. The observations in this paper validate aspects of the current design of MathBrush, suggest areas for refinement, and inform the design of future pen-math systems. 

Discussion:

For MathBrush to be used, users need to modify their writing to adjust to the tolerances of recognition. The adaptations included slowing down the timing, taking additional care with symbol spacing, and altering the way that we draw certain characters. These are very basic writing techniques and we should be developing a system which takes care of these and not changes these. Thus, this aspect of the paper should be improved in my view.

Project Reading 6

MathPaper: Mathematical Sketching with Fluid Support for Interactive Computation

Citation:

Zeleznik, R., Miller, T., Li, C., and Laviola Jr, J. J. Mathpaper: Mathematical sketching with fluid support for interactive computation. In Smart Graphics, Springer (2008), 20–32.

Summary:

This paper presents a framework called MathPaper. It represents a system for fluid pen-based entry and editing of mathematics which also has the support for interactive computation. 

Writing on MathPaper interface is just like writing on a paper, in which multiple mathematical expressions and even algorithms can be entered anywhere on the page. It also talks about modification of Mathematical expressions using simple deletion and dragging gestures along with real-time recognition and computation feedback. 

MathPaper also supports extended notations and gestures for controlling computational assistance, simplifying input, and entering algorithms, making MathPaper a user-friendly system for mathematical sketching and computation.

Discussion:

This paper also presents the idea of writing mathematical equations on paper and not on the computer, which is the idea we are trying to work on in our term project. It also talks about modification of mathematical expression modification which we are also performing in our project.

Project Reading 5

Designing a Sketch Recognition Front-End: User Perception of Interface Elements

Citation:

Wais, P., Wolin, A., and Alvarado, C. Designing a sketch recognition front-end: User perception of interface elements. In Proceedings of the 4th Eurographics Workshop on Sketch-based Interfaces and Modeling, SBIM ’07, ACM (New York, NY, USA, 2007), 99–106.

Summary:

This paper focusses on presenting a user study which investigates critical sketch recognition user Interface issues in systems that recognize hand-drawn diagrams. There are four critical sketch recognition user interface issues:

1) how users integrate the process of triggering recognition into their work.

2) when users prefer to indicate which portions of the diagram should be recognized.

3) how users prefer to receive recognition feedback.

4) and how users perceive recognition errors.

The paper believes that programs that can recognize students’ hand-drawn diagrams can revolutionize education. This is because they break down the barriers between diagram creation and simulation. This paper thus focusses on understanding how to support this new interaction paradigm from a user’s perspective.

Discussion:

The paper presents a very well conducted user study to understand the drawbacks and limitations of the exisiting systems. They have shown the data for Electrical circuits for the user study. It would have been really helpful to perform the user study in any other domain also.

Project Reading 4

Citation:

LogicPad: A Pen-Based Application for Visualization and Verification of Boolean Algebra. Kang, B., and LaViola, J. Logicpad: A pen-based application for visualization and verification of boolean algebra. In Proceedings of the 2012 ACM International Conference on Intelligent User Interfaces, IUI ’12, ACM (New York, NY, USA, 2012), 265–268. 

Summary:

The paper presents a framework called LogicPad, which a pen-based application for boolean algebra

visualization. It lets users manipulate boolean function representations through handwritten symbol and gesture recognition. It also has a drag-and-drop interface which makes interaction with the interface much easier. LogicPad’s user interface and the general algorithm are discussed in the paper which are used for verifying the equivalence of three different boolean function representations: boolean expressions, truth tables, and logic gate diagrams. A user study is also conducted by the authors evaluating LogicPad’s user interface, visualization techniques, and overall performance.

Discussion:

As per the results, visualizations were generally well-liked and verification results matched

user expectations, which is pretty good. The sketching area on which the users write as they normally would using pen and paper, is very intuitive and which we are trying to follow in our project too.

Project Reading 3

Citation:

A Handwriting-Based Equation Editor. Written by: Steve Smithies, Kevin Novins, James Arvo.

Summary:

Equation editing systems relying on either textbased equation description languages or on interactive

construction by means of structure templates and menus are tedious to use, even for experts, because the user is forced to “parse” the expressions mentally before they are entered. The system described below is a prototype equation editor that is based on handwriting recognition and automatic equation

parsing. 

The recognition system performs Character Recognition, Stroke grouping and Equation parsing. Parsing uses LATEX like notation.The main drawbacks of a graph grammar approach are

the number and complexity of subgraph searches. The system also provides a basic User interface for ease of use. It also provides correcting of stroke grouping errors and correcting of character recognition errors. The next step is providing correction of Equation parsing errors. This system provides a natural and familiar interaction method or recognizing equations.

Discussion:

The time taken for parsing simple formulæ is less than two seconds, though more complicated formulæ may take twenty seconds or more. This time taken for parsing is very less and shows the efficiency this system has.

Project Reading 2

Recognition and retrieval of mathematical expressions

Citation:

Recognition and retrieval of mathematical expressions. Written by: Richard Zanibbi , Dorothea Blostein.

Summary:
This paper surveys recognition and retrieval of mathematical expressions, organized around four key problems in math retrieval (query construction, normalization, indexing and relevance feedback), and four key problems in math recognition (detecting expressions, detecting and classifying symbols, analyzing symbol layout, and constructing a representation of meaning).
The problems arising in Math Notation recognition are:
1) Expression Detection
2) Symbol Extraction or Symbol Recognition
3) Layout Analysis
4) Mathematical content Interpretation

It creates two kinds of trees for equation recognition: Symbol layout tree and Operator tree. The following problems arise in retrieval of Math notation:
1) Query languages and query formulation
2) Normalization
3) Indexing and matching
4) Relevance feedback

In solving the ambiguity of mathematical expressions, we first need to understand the meaning of what do each of the symbols represent.

Discussion:
This paper has given many future work ideas. Also, while doing our project, we felt on the same lines as the author (that solving the ambiguity in Math expressions, we need to understand meaning of each symbol). The use of various tools like MathML and Latex is very intuitive.

Project Reading 1

Mathpad: A Fuzzy Logic-Based Recognition System for Handwritten Mathematics

Citation:

Mathpad: A Fuzzy Logic-Based Recognition System for Handwritten Mathematics

Fitzgerald, J.A. ; Univ. Coll. Dublin, Dublin ; Geiselbrechtinger, F. ; Kechadi, T.

Summary:

A recognition system which enables the users to enter mathematical equations in customized fashion is presented. The approach uses Fuzzy logics and fuzzy rules to extract features, classify symbols and assess spatial relationships. Using all this, the resultant outcome is a tool for Mathematical problem-solving and visualization. 

Two types of fuzzy rules are used for symbol recognition: High-level and low-level fuzzy rules. Mathpad performs syntax checking through Shift Reduce parsing. Some changes made to SRP are in Input attributes, Fuzzy constraints, Semantic rules and Fuzzy Parse trees. This paper then established the use of Fuzzy Shift Reduce parsing. 

Discussion:

The system does not change its computation method based on complexity of equation written. Also, the results of ME recognition rate are better, but I think there still is a scope for improvement. I really liked the idea of using Fuzzy logics in understanding and parsing the equation.

Reading 27

Reading 27: Visual Symbolic Recognizer

Citation

Tom Y. Ouyang and Randall Davis. 2009. A visual approach to sketched symbol recognition. In Proceedings of the 21st international jont conference on Artifical intelligence (IJCAI'09), Hiroaki Kitano (Ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1463-1468.

Direct Link: http://dspace.mit.edu/openaccess-disseminate/1721.1/71572

Summary

The paper presents a sketched symbol recognition that focuses on the visual appearance of the symbols. It uses a new symbol classifier that is computationally efficient and invariant to rotation and local deformations. It evaluates performance on following three domains: handwritten digits, PowerPoint shapes, and electrical circuit symbols.

The paper represents symbols as feature images rather than as geometric primitives. It also proposes a set of visual features which captures on-line stroke properties (eg. orientation, endpoint location). The paper introduces a computationally efficient classification technique which is robust to rotation and local deformations. The paper then talks about it exceeding performance on all of the three datasets evaluated. 

Four reference angles are used as orientation features correspond. The endpoint feature identifies stroke endpoints. The stroke is then sent for smoothening and Downsampling. 

IDM Distance between two symbols I1 and I2 is represented as:

D2 = X x,y min dx,dy ||I1(x + dx, y + dy) − I2(x, y)||2 

Discussion

Getting good accuracy in three different domains is appreciable. There still is some scope of improvement as SVM-linear seems to perform better. Probably it can be combined with SVM-linear and used as a collaborative system.

Reading 26

Reading 26: Shape Context

Citation

Oltmans, Michael. Envisioning sketch recognition: a local feature based approach to recognizing informal sketches. Diss. Massachusetts Institute of Technology, 2007.

Direct Link: http://rationale.csail.mit.edu/publications/Oltmans2007Envisioning.pdf

Summary

Discussion

Reading 25

Reading 25: Who Dotted That i?

Citation

Eoff, Brian David, and Tracy Hammond. "Who dotted that'i'?: context free user differentiation through pressure and tilt pen data." Proceedings of Graphics Interface 2009. Canadian Information Processing Society, 2009.

Publication Link: http://dl.acm.org/citation.cfm?id=1555916

Summary

The paper presents  a system that shows that the creator of an individual pen strokes can be determined with high accuracy. 
The paper presents following as the benefits of unobtrusive user differentiation:
1) Security and Verification
2) Improving sketch recognition through user modelled recognition
3) Collaboration
Multiple experiments which have been done for developing this system have been described in the paper. In a collaborative sketch environment, the authors are able to identify the creator of individual strokes without forcing the user to use a specific pen, or to select a specific mode to indicate who is drawing, which is very impressive.

Regarding the features, it says that even poor features hold some value when determining user differentiation. Also, there is no single feature which could be used as a discriminator for different users. 

Discussion

This paper presents a good point about some features being better than the others in differentiating one user from the other. The idea of giving some score to even the poor features is intuitive and useful.

Reading 24

Reading 24: SketchREADPaperAlvarado, Christine, and Randall Davis. "SketchREAD: a multi-domain sketch recognition engine." Proceedings of the 17th annual ACM symposium on User interface software and technology. ACM, 2004.Publication Link: http://dl.acm.org/citation.cfm?id=1029637

Summary:This paper aims at recognizing freely hand drawn diagram sketches. It uses a hierarchical shape description language to describe shapes in a domain. Definition of a shape has its sub-shapes and constraints. From the description of a shape and domain pattern, a Bayesian network is constructed to indicate causal relationships. While sketch recognition, an interpretation network is also generated. Hypothesis generation has 3 steps:1) Bottom up: As user draws, system parses the strokes into primitives using domain independent recognition toolkit.2) Top down: System re-interprets the strokes and attempts to find missing sub-shapes from partial interpretations3) Pruning: System removes unlikely interpretations

Discussion:It gives examples of a really complicated domain, like physics. This seems really challenging and exciting at the same time. Also the fact that it is multi-domain is really impressive. As it performs stoke parsing while user is drawing, it seems pretty effective

Reading 23

Paper

Rabiner, Lawrence R. "A tutorial on hidden Markov models and selected applications in speech recognition." Proceedings of the IEEE 77.2 (1989): 257-286.

Direct Link: http://www.robots.ox.ac.uk:5000/~vgg/rg/papers/hmm.pdf

Summary:

This paper provides detailed explanation of Hidden Markov Models. It reviews the theory of discrete Markov chains and concept of hidden states. It depicts that observation(which is a fucntion of state) can be used effectively. Example of markov chain with 5 states is discussed along with state transitions. Then the weather example with different possibilities is discussed. Models are represented as doubly embedded stochastic processes in extension to HMMs. Elements of HMM:

1) Number of states in model.

2) Number of distinct observation symbols per state

3) State transition probability distribution function

4) Observation symbol probability distribution state

5) Initial state distribution

HMMs have three issues:

1) How to compute probability of observation sequence, given the model

2) How to choose corresponding state sequence

3) How to adjust the model parameters

Discussion:

This paper looks like a very good tutorial on HMMs, hence justifying its title. But, it seems like a little bit long to analyse it completely!

Reading 22

Reading 22: HMM Recognizer
PaperSezgin, Tevfik Metin, and Randall Davis. "HMM-based efficient sketch recognition." Proceedings of the 10th international conference on Intelligent user interfaces. ACM, 2005.
Publication Link: http://dl.acm.org/citation.cfm?id=1040899

Summary:
This paper has used HMM for recognising strokes. Generally it is done in two steps:
1) Encoding: Sketches are encoded to generate observations using Sketch Processing Toolkit.
2) Segmentation and recognition: Interpretation of a complex scene involves generating hypotheses for the whole scene. For this optimization problem, dynamic programming is used and implemented in the form of shortest path problem. By computing shortest path, the sum of negative likelihoods is minimized i.e. likelihood of observation is maximised.
Discussion:
This paper is very concise and easy to understand. A little bit more information about how the probabilistic models and what an HMM model is, would have proven more helpful. Viewing and analysing sketch as intuitive process is very intuitive and necessary.

Reading 21

LADDER

Paper:

Hammond, Tracy, and Randall Davis. "LADDER, a sketching language for user interface developers." Computers & Graphics 29.4 (2005): 518-532.
Publication Link: http://www.sciencedirect.com/science/article/pii/S0097849305000865

Summary:
LADDER  is a symbolic language to describe how shapes are drawn. The definition of shape has the following parts: List of components, Geometric constraints, Set of aliases, Editing behavior, Display methods. It also creates an abstract behavior as in an abstract class, which is very easy to extend. Some primitive shapes are already defined like path, line, arc etc. Sample constraints are leftOf, horizontal, centeredBelow etc. Vectors are maintained for variable number of components in a shape. 
For primitive shape recognition, low-level recognition is performed on the stroke. If it does not provide correct interpretation, domain recognizer will never be able to recognize it. For domain shape recognition, Jess rule is defined to recognize the shape. It is then passed through a constraint solver.


Discussion:
The idea of creating a symbolic language to describe the process of drawing shape is very amazing. It presents a novel idea of creating an abstract behavior as in an abstract class, which is very easy to extend. 

Reading 20

Multi Stroke primitives

Paper

Hammond, Tracy, and Brandon Paulson. "Recognizing sketched multistroke primitives." ACM Transactions on Interactive Intelligent Systems (TiiS) 1.1 (2011): 4.

Publication Link: http://dl.acm.org/citation.cfm?id=2030369

Summary

This paper uses 5 steps in its implementation:

1) Graph Building: This step constructs the graph of spatially close strokes. Also, it adds the edges in graph which were originally connected in stroke. It checks for Euclidean distance divided by stroke length < 0.1 and Euclidean distance divided by average width of bounding box < 0.15 as thresholds.

2) Graph Searching: It checks for Strongly Connected components in graph. It uses Tarjan's algorithm which is a DFS algorithm running in linear time. 

3) Stroke Merging: It generates a ranking of graphs based on number of nodes present. Then it greedily iterates through list of possible merges. There can two issues: The order in which stroke is drawn and the connection of end points of two different strokes.

4) False Positive Removal: It follows 5 principles: Avoid complexity, Shapes should maintain constant linearity, Minimal effect of touch-up strokes, Continuation should maintain consistency and complexity, Impose confidence constraints on shapes.

5) Arrow Detection: It loops through the polylines formed and checks if endpoints of stroke is any way near to it. 

Discussion

The idea of even primitive strokes being drawn as multistroke was quite shocking. Some of the user results are very surprising, like some very simple primitive shapes being drawn as multi stroke whilst complex shapes being drawn as single stroke. In this case, this kind of user data has a huge impact I believe. 

Reading 19

PaperLi, Wenzhe, and Tracy Anne Hammond. "Recognizing text through sound alone." Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011.
Direct Link: http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/download/3791/4119

Summary

 This paper presents a sound based algorithm for recognizing sketch. It is able to recognize 26 English alphabets. The main steps are

1) Noise Reduction : It performs two types of Endpoint noise removal. First by taking signal energy f first 150 ms and it represents noise. Each 45 ms frame is then calculated for mean energy. Other one calculates Gaussian probability function for the first 200 ms and then obtain parameters. If at least half of all the segments within the frame are valid, it is marked as valid else marked as silence. 

2) Normalization : Mean amplitude 

3) Feature extraction: Mean amplitudde, each frame is taken at 45 ms and size as 30 ms, along with overlapping. MFCC convert the fourier transform to logs of powers and then again back to signal.

3) Template matching: It uses dynamic time warping to calculate distance between query and template.

Discussion

This paper presents a very unique and innovative idea of using sound as a medium for recognizing sketches. This method if combined with other recognizers can be used for getting some good results. A little more explanation on what the feature set is, would have been better for understanding.

Reading 18

Geometry Review:

Citation:

Paper copy only

Summary:

This book chapter provides a summary of all the useful mathematical formulas we have learnt so far in the course. It talks about cosine formula and parallelograms. It also talks about determinant, cofactor and adjoint matrices. It touches on relationship between polygons and matrices also.

Discussion:

The chapter is a good way to brush up all the formulae. It has been formulated in a way which is very easy to understand. 

Reading 17

Citation:

Paulson, Brandon, and Tracy Hammond. "PaleoSketch: accurate primitive sketch recognition and beautification." Proceedings of the 13th international conference on Intelligent user interfaces. ACM, 2008.Publication Link:http://dl.acm.org/citation.cfm?id=1378775

Summary:

This paper aims to recognize low level primitves and then hierarchically construct higher level shapes. As part of pre-recognition this paper has introduced two features: NDDE and DCR. NDDE is calculated as (stroke length between highest and lowest direction points/Total stroke length). DCR is calculated as (maximum change in direction/Average change in direction). NDDE is higher for curves and lower for polylines. This is vice versa for DCR. 

The algorithm determines whether stroke is overtraced or not by computing total number of revolutions the stroke makes diving by 2π. It performs recognition for following shapes:

1) Line

2) Polyline

3) Ellipse

4) Circle

5) Arc

6)Spiral

7) Helix

8) Complex shape

It also assigns hierarchy for all these shapes where it assigns rank for the primitive shapes. Rank of line is 1, arc is 3 and all others have rank of 5. Algorithm suggests the shape with lowest rank.

Discussion:

This paper introduces a lot of threshold values without providing any insight on how they have been derived. The number of threshold values should have been either less, or explained more about. Correct shapes were determined 99.89% of times, which is pretty impressive. Integration with LADDER could have been given more explanation.

Reading 16

Citation:

Wolin, Aaron, Martin Field, and Tracy Hammond. "Combining corners from multiple segmenters." Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling. ACM, 2011.

Publication Link: http://dl.acm.org/citation.cfm?id=2021185

Summary:

This paper combines polyline corner results from different segmenters by using a variation of feature subset selection. It overcomes the drawbacks that individual segmentation algorithms have. It has two steps in corner subset selection: Segmenters used and subset selection. It uses a cmbination of 5 segmenation algorithms. 

In subset selection, tt starts with all the vertices found from all five algorithms. Then at each step, it removes one corner which affects the mean squared error the least . It is done by the Floating backwards selection technique. It also does bookeeping and thus checks for previously removed corners also. Terminates when only two corners are left and the elbow point is the optimal number of vertices. We have a threshold set for the elbow point. Then training and testing are performed on the median values instead of the mean values. This is done because mean values for gaussian were having large fluctuations.

Why not start with all points? All points initally have MSE to be 0.0 aand then after removing each corner, it gives large spikes in the data. Thus, no appropriate threshold could be found.

Discussion:

This paper gives promising result as All-or-nothing accuracy is concerned. I do not understand the need of going till the two points, as if elbow point occurs before we can just stop there. This is because there is only one elbow point in the MSE curve. What will happen if we start from zero corners and then add corners from each segmenter is also a way to explore.

Reading 15

CITATION

Xiong, Yiyan, and Joseph J. LaViola Jr.

Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling. ACM, 2009.

Publication Link: http://dl.acm.org/citation.cfm?id=1572759

SUMMARY:

This paper first presents a summary and shortcomings of Shortstraw implementation. It lists 6 limitations in shortstraw and fixes them:

1) First three and last three points do not have straw values in shortstraw. The first two and last two are defined here.

2) Lack of timing and speed information in shortstraw. Istraw takes timing data and resamples the whole stroke.

3) Unreliable triplet collinear check. It reduces the chances of missed correct corner in Istraw. It does so by having two passes.

4) Fix threshold. The threshold is dynamic and is dependent on stroke length.

5) Noise: It avoids noise due to sharp angles.

6) No curve detection. It introduces curve detection by taking the difference between two different resampled points. 14-33 angle difference is taken as corner.

After all these improvements, the time complexity is still the same which is O(M+N^2+C).

DISCUSSION:

The results are very impressive and the results are surely very much more improved than the shortstraw implementation. Overall I just feel that threshold and the angle values, if varied rather than kept constant can create bigger impacts.

Reading 14

Citation:

Wolin, Aaron, Brian Eoff, and Tracy Hammond Proceeding SBM'08 Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling

Link:http://dl.acm.org/citation.cfm?id=2386301.2386308&coll=DL&dl=GUIDE&CFID=550427120&CFTOKEN=14778671

Summary:

This algorithm is a very efficient algorithm for corner finding. The very first step is to re-sample the points. The re-sampling distance is calculated from the length of the bounding box diagonal divided by 40. The next steps involve two approaches- bottom up and top down. It also defines concept of straw which seems very intuitive.

The bottom up approach uses straws to calculate the distance between points pi-w and pi+w where w is a constant window defined. It is taken as 3 here. The median of all straw lengths is taken. A threshold value on straw distances is defined for classifying corners. It is empirically chosen to be as median*0.95.

Next step is Top down approach. It removes false positives and missing corners. A line test is performed to find missing corners. If the ratio of chord distance and total path distance lies below a threshold, then there exists a missed corner between them. If two vertices do not pass a line test, a new vertex is declared at the point where the mid point of two end points is. Also, a collinear test  is performed between every three points. If the test passes, the center point is removed.

Discussion:

The best thing about this paper is its simplicity and the intuitive idea of using straws. I believe this idea comes straight from geometry and hence very easy to follow. The fixed window size if varied, I think can produce better results in case of corner finding as the space between the straws will increase when we move away from a corner much faster than when we move away from a line.

Reading 13

CITATION

Bo Yu, Shijie Cai

GRAPHITE '03 Proceedings of the 1st international conference on Computer graphics and interactive techniques in Australasia and South East Asia

Publication Link: http://dl.acm.org/citation.cfm?id=604499

Summary:

This paper allows the users to draw in a very natural way. The process is divided into two steps: imprecise stroke approximation and post-process. In imprecise stroke approximation, it divides the work in four steps: Vertex detection, Line segment approximation, curve approximation and self-Intersection strokes. The feature area here can be calculated here to a line, to a point or to an arc. The vertex detection and primitive shape approximation is divided into an incremental procedure. Feature area verification is done while identifying line segment, Curves are identified with help of their direction graph and the value of slope. It follows two heuristic rules: simpler is better and specific is better.

Post process involves simple relation retrieval, cleanup and basic object recognition. It eliminates false noisy elements. It specifies the rules for identifying whether or not to remove  or shorten or merge a line/arc,

Discussion:

The method provides good accuracy for polylines and primitive shapes, but the accuracy drops very much while dealing with hybrid shapes. I like the fact that the system and metrices used are easy to follow and use.

Reading 12

Sketch based interfaces: early processing for sketch understanding

Paper

Sezgin, Tevfik Metin, Thomas Stahovich, and Randall Davis. "Sketch based interfaces: early processing for sketch understanding." ACM SIGGRAPH 2006 Courses. ACM, 2006.

Publication Link: http://dl.acm.org/citation.cfm?id=

Summary:

In this paper, the authors are using following three phases: approximation, beautification and basic recognition. In Stroke approximation phase, vertex detection is performed first. Vertices can be detected by either speed minima or maxima of curvature. Using only one of them does not provide accurate results and thus we use average based filtering. Extremas in those portions are looked for threshold values(mean in curvature and 90% of mean in speed data). We generate a hybrid fir based on the data. 

Noise and variety in angle changes, both pose a problem on the credibility of a single data. Using only speed, vertices might be missed and just using curvature data, extra vertices may be counted. Hybrid fit is generated by intersection of both points and then point from each is added to see which point leads to lesser OSDQ error value. For curves, ratio of Euclidean distance and arc length is used. The curve is recursively subdivided in the middle. Next steps are beautification and Basic object recognition.

Discussion:

The paper could have discussed more about how the values of threshold are calculated and why the 90% is chosen in case of speed data. The idea of using minimal feature set i.e only two (speed and curvature) is very promising

Reading 11

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

Citation:

Paulson, Brandon, et al. "What!?! no Rubine features?: using geometric-based features to produce normalized confidence values for sketch recognition." HCC Workshop: Sketch Tools for Diagramming. 2008.

Link: https://www.cs.auckland.ac.nz/research/conferences/skekchws/proceedings/vlhcc_stws_p57.pdf

Summary:

This paper proposes a hybrid approach combining two aspects of sketch recognition: Gesture based and Geometric based recognition. It also uses a statistical classifier which is quadratic classifier and combines feature set from both the recognition methods. It initially had 44 features: 33 from geometric based and 11 Rubine features. The classifiers were trained offline and the dataset contained 1800 sketches. Subsets were selected based on greedy sequential forward selection. The results show that optimal features show highest accuracy. These happen to be 14 optimal features from geometric based and only one Rubine feature.

Discussion:

It came as a surprise that only one Rubine feature could perform close to 14 geometric features. I think if this is the ratio of efficiency in recognition, there should be more experiments done for geometric features. Also, the surprising part is that some of the important seeming Rubine features like stroke length, sine cosine did not even make it to the top 15. I think there should be some evidences for extending the experiments to some more classes.

Reading 10

Visual Similarity of Pen Gestures

Citation:

Long Jr, A. Chris, et al. "Visual similarity of pen gestures." Proceedings of the SIGCHI conference on Human Factors in Computing Systems. ACM, 2000.

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

Summary:

Multidimensional scaling is used for reducing the dimensionality so that the matrices can visualized better for similarity. Regression analysis is done to find out which dimension represents what. 22 features were used to identify gestures, 11 of which were inherited from Rubine. 

This paper suggests that aspect is much more powerful than length and width of bounding box diagonal. The impact it creates is much higher. Also, the length and arc of shape have much lower impact. The log of aspect creates more sense than log because the values are normalized and easy to visualize for differences. 

Density metric is used for differentiating between coloring and scribbling. The curviness is measured with a threshold angle of 19 degree, which is got by summing small difference in angles.

Discussion:

I found the observation that log creates a better perception very intuitive. It certainly eases the comparison between two similar looking figures. Also, the selection of 19 degrees for the value f curviness could be explained a little bit more.

Reading 9

Citation:

Gesture Recognition Overview. 

No Link available.

Summary:

This chapter presents all the features used for linear classification in Rubine. The sampling rates are higher nowadays and because of that we might get points which give us the same location or time stamp. Thus, the corresponding divide by zero error needs to be handled by pre-processing. This may be either removing the first point or the second point or just altering the time stamp we have. The features like rotations, stroke lengths and the angle scenarios are used for identifying particular aspect of the gestures.

Long and Quill have used 11 of the 13 features of Rubine(removing the time features), but the performance improvement is not significant.

Discussion:

The chapter requires refinement in terms of explanation of Rotational measure and arctan discontinuity that it just goes over very rapidly. The way open questions are posed in the chapter is really thought provoking.

Reading 8

Specifying gestures by example

Citation:

Rubine, Dean. Specifying gestures by example. Vol. 25. No. 4. ACM, 1991.

Link: http://dl.acm.org/citation.cfm?id=122753

Summary:

Paper introduces an application called GRANDMA which is a toolkit for rapidly adding gestures to direct manipulation interfaces. Another application GDP, which is a gesture based application is also introduced in this paper.

GDP is also a single stroke recognizer, while it can be a pain in identification but it also avoids segmentation problems. The input gesture is classified into one of the C classes of gestures. Then, features are extracted from template and matched using a linear classifier. The paper also describes the Rubine's 13 features.

Discussion:

This paper could have used and tried more features along with Rubine features. The input technique provided by this paper is very promising. In my opinion, the major limitation is the identification of only single stroke gestures.

Reading 7

Citation:

$1 recognizer for user interface prototypes

Wobbrock, Jacob O., Andrew D. Wilson, and Yang Li. "Gestures without libraries, toolkits or training: a $1 recognizer for user interface prototypes."Proceedings of the 20th annual ACM symposium on User interface software and technology. ACM, 2007.

Publication Link: http://dl.acm.org/citation.cfm?id=1294238

Summary:

1$ recognizer is an easy to use, and very cheap gesture recognizer and is very efficient for template matching. 16 different types of gestures which can recognized by the recognizer have been discussed in the paper. 

The paper matches previously recorded template points to new candidate points generated by the gesture at that time. 1$ recognizer has implemented algorithm in four steps: Resample the point path, Rotate once based on indicative angle, Scale and translate and lastly finding the optimal angle for best score. It converts the minimum path to a particular score which is further used for recognition. It is rotation invariant.  Both sides arrows are really different and thus path being identical is very important. 

The major limitation is that it is a  geometric template matcher, and thus candidate strokes are compared to previously stored templates. Also, it cannot distinguish between gestures whose identities depend on specific orientations. Also, it has to be single stroke for it to be recognized.

Discussion:
There should be some more test cases presented for more number of templates to give a better idea to the reader. Just three templates make the test data too small I believe. The idea of looking at centroid of gesture and not any other random point is really impressive.

Reading 6

Paper:

Link: Using Entropy to Distinguish Shape Versus Text in Hand-Drawn Diagrams

Citation:

Bhat, Akshay, and Tracy Hammond. "Using Entropy to Distinguish Shape Versus Text in Hand-Drawn Diagrams." IJCAI. Vol. 9. 2009.

Summary:

Distinguishing between text and shape is a critical task. The approach followed for it in this paper is finding the entropy of each thing and generally the entropy of text is much higher. This is because entropy measure is generally the measure of randomness of an information source. Also, handwritten text is more difficult to describe than common shapes. A zero order entropy is used.

In the entropy model used, each symbol corresponds to a range of angles. The first step in the classification process is to group the strokes. This step uses using the intuition that strokes that are part of the same entity should be close to each other and drawn within a small amount of time. After strokes are grouped, strokes are re-sampled to smooth and sub-stroke angles so that all points are equidistant from each other. Probability estimate is calculated by dividing the total number of occurrence of a symbol the total number of points. Then, all the probabilities within a stroke group are added.

Based on a threshold calculated from training dataset, the input stroke group is classified as either shape, text, or unclassified. Confidence is measured and modeled by using arctan function.

Discussion:

The paper is written in a very easy to read and understand way. The accuracy of the system with maximum accuracy mode is 95% and with more classification mode is 92%, which are pretty impressive results. I think it should be tested with more misclassification symbols also other than a resistor or a dot for better results. Also, some more inputs and results for higher order entropy models would have explained the situation a lot better.

Reading 5

Citation

 L. Kara, T. Stahovich. An Image-Based, Trainable Symbol Recognizer for Hand-Drawn Sketches. Computers & Graphics 29.4 (2005): 501-517.

 Link: http://www.sciencedirect.com/science/article/pii/S0097849305000853

Summary:

A trainable hand drawn symbol recognizer is described. The approach is useful for sketchy inputs as it is based on binary templates. This paper is designed around four different similarity methods to enhance recognition accuracy. These are Hausdorff distance, Modified Hausdorff distance, Tanimoto coefficient and Yule coefficient. During matching, distance maps are used as look-up tables for the closest distances. Polar coordinate transformation technique is used for rotation invariant recognition. Next step is examining remaining definitions in screen coordinates.

Discussion:

The idea of use of polar coordinate transformation for rotation invariant recognition is very impressive. The accuracy achieved, which is 95% is really commendable. The sensitivity to non-uniform scaling portrays the importance of topology over shape.

Reading 4

Citation:

Davis, Richard C., Brien Colwell, and James A. Landay. "K-sketch: a'kinetic'sketch pad for novice animators." Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2008.

Link: http://dl.acm.org/citation.cfm?id=1357122

Summary:

K-sketch is a general purpose 2D animation sketching system. It is able to provide quick and powerful animations meant to be used by novices. Then, a definition of an optimization problem was done to maximize the number of features supported. At the same time, it minimized the number of steps needed to complete each animation feature, thus making it optimized. Evaluations comparing with simple tools such as Powerpoint and Flash were done. This implies the ease of use of the system.

Discussion:

The ease of use makes K-sketch a very optimal choice of system to use. The fact that ease of use of User interface could be compared with Powerpoint really amazed me. Also, considering animation as a step wise procedure, it shows the main purpose of the system is Novice users and their ease of use.