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.