UCF CAP 5937 - Ink Parsing in Sketch-Based Interfaces

Unformatted text preview:

1Fall 2007 CAP 5937 – Topics in Pen-Based User Interfaces ©Joseph J. LaViola Jr.Ink Parsing in Sketch-Based InterfacesLecture #10: Ink ParsingJoseph J. LaViola Jr.Fall 2007Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Recall Pen-Based Interface DataflowRaw StrokeDataPreprocessing SegmentationFeature ExtractionAndAnalysisClassificationInk ParsingSketchUnderstandingMake Inferences2Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Sketch Parsing Often recognition of strokes is insufficient except for gestures Require an understanding of spatial relationships good examples are mathematical expressions Higher level classifications is it a word or a drawing?www.engr.ucr.edu/~stahov/research/acsparc.htmFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Approaches to Sketch Parsing Top down vs. bottom up Focus on mathematical expressions 2D (coordinate) grammars graph rewriting useful for other types of parsing as well (diagrams, tables, lists, etc…) projection profile cutting procedurally coded syntax rules stochastic grammars Other parsing approaches conditional random fields statistical visual languages many others3Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.2D Grammars Grammar + spatial relationship rules useful if a well defined syntax exists looks for key symbols One Approach – Box Grammar divide input into distinct areas based on symbol foundFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Graph Rewriting Expressions represented as nodes and arcs Rewrite rules applied to graph to reduce it progressively rules are also subgraphs graph reduced to single node representing expression4Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Graph Rewriting Example (Blostein and Grbavec 1996) Build add edges between symbols (above, below, left, superscript, subscript) Constrain Apply knowledge of notational conventions remove contradictory associations disambiguate horizontal lines disambiguate dots disambiguate diagonal associations Rank Use information about operator precedence to group symbols into subexpressions Incorporate Interpret subexpressionsFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Projection Profile Cutting Used primarily in document analysis Uses horizontal and vertical projections of expression onto x and y axis subdivides expression recursively Problem with expressions where symbols are close together (no white space)5Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Procedurally Coded Syntax Rules Observations about domain coded programmatically similar to rule based approach for recognition Sample rule for horizontal lineA length threshold of 20 pixels is used to classify a horizontal line as a short or long bar.If it is a long bar and has symbols above and below, it is treated as a division. If there are no symbols above, it is treated as a boolean negation. If a short bar has no symbols above or below, it is treated as minus sign.If it has symbols above or below, the combination symbols such as =, ≤, and ≥ are formed.Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Stochastic Grammars Used to deal with noisy data and spatial ambiguities Probabilities associated with each production rule For any sequence in a given parse –probability can be calculated Requires training6Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.MathPad2Parsing Approach Uses 2D coordinate grammar approach with some syntax rules Basic approach preprocessing step (for functions) sort list of symbols parse functions – use grammar process functions – handle spatial relationship testing intermixed with parse functionsFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Grammar (1)7Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Grammar (2)Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Parse functions High level parse Expression parse Sub-expression parse Symbol specific parsing square root parse integration parse summation parse fraction parse Factor parse Term parse8Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Process functions Provide parse functions important info Deal with spatial relationships implicit operators fractions and square roots summations , derivatives, integrals ConditionalsFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Reducing parsing decisions Use application to reduce decisions Implicit operators (no numbers have subscripts) Correct trig functions 5in -> sin Functions of time f(+) -> f(t)9Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Readings D. Blostein and A. Grbavec, "Recognition of Mathematical Notation," in Handbook of Character Recognition and Document Image Analysis, Eds. H. Bunke and P. Wang, World Scientific, 1997, pp. 557-582.  Chan, Kam-Fai and Dit-Yan Yeung. An Efficient Syntactic Approach to Structural Analysis of On-Line Handwritten Mathematical Expressions. Pattern Recognition, 33(3):375-384, March 2000.  Ye, Ming, and Paul Viola. Learning to Parse Hierarchical Lists and Outlines Using Conditional Random Fields. International Workshop on Frontiers in Handwriting Recognition, 2004.  Michael Shilman, Hanna M. Pasula, Stuart Russell, and Richard Newton, Statistical Visual Language Models for Ink Parsing. In Proc. AAAI Spring Symposium on Sketch Understanding, Stanford, March


View Full Document

UCF CAP 5937 - Ink Parsing in Sketch-Based Interfaces

Documents in this Course
Load more
Download Ink Parsing in Sketch-Based Interfaces
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Ink Parsing in Sketch-Based Interfaces and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Ink Parsing in Sketch-Based Interfaces 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?