research-article

Tools for the efficient generation of hand-drawn corpora based on context-free grammars

Authors:

Mirette MarzoukAuthors Info & Claims

SBIM '09: Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling

Pages 125 - 132

https://doi.org/10.1145/1572741.1572763

Published: 01 August 2009 Publication History

Get Access

Abstract

In sketch recognition systems, ground-truth data sets serve to both train and test recognition algorithms. Unfortunately, generating data sets that are sufficiently large and varied is frequently a costly and time-consuming endeavour. In this paper, we present a novel technique for creating a large and varied ground-truthed corpus for hand drawn math recognition. Candidate math expressions for the corpus are generated via random walks through a context-free grammar, the expressions are transcribed by human writers, and an algorithm automatically generates ground-truth data for individual symbols and inter-symbol relationships within the math expressions. While the techniques we develop in this paper are illustrated through the creation of a ground-truthed corpus of mathematical expressions, they are applicable to any sketching domain that can be described by a formal grammar.

References

[1]

{BA69} Blackwell F. W., Anderson R. H.: An on-line symbolic mathematics system using hand-printed two-dimensional notation. In Proceedings of the 1969 24th national conference (New York, NY, USA, 1969), ACM, pp. 551--557.

Digital Library

Google Scholar

[2]

{BCZ02} Blostein D., Cordy J. R., Zanibbi R.: Applying compiler techniques to diagram recognition. In ICPR '02: Proceedings of the 16th International Conference on Pattern Recognition (ICPR'02) Volume 3 (Washington, DC, USA, 2002), IEEE Computer Society, pp. 127--130.

Digital Library

Google Scholar

[3]

{BSB08} Beusekom J. v., Shafait F., Breuel T. M.: Automated ocr ground truth generation. In Document Analysis Systems, 2008. DAS '08. The Eighth IAPR International Workshop on (Sept. 2008), pp. 111--117.

Digital Library

Google Scholar

[4]

{HBAT07} Heroux P., Barbu E., Adam S., Trupin E.: Automatic ground-truth generation for document image analysis and understanding. In Document Analysis and Recognition, 2007. ICDAR 2007. Ninth International Conference on (Sept. 2007), vol. 1, pp. 476--480.

Digital Library

Google Scholar

[5]

{JZ04} Jr. J. J. L., Zeleznik R. C.: Mathpad2: a system for the creation and exploration of mathematical sketches. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2004) 23, 3 (2004), 432--440.

Digital Library

Google Scholar

[6]

{KBNJ06} Kumar A., Balasubramanian A., Namboodiri A., Jawahar C.: Model-Based Annotation of Online Handwritten Datasets. In Tenth International Workshop on Frontiers in Handwriting Recognition (Oct. 2006), Guy Lorette, (Ed.), Universit&#233; de Rennes 1, Suvisoft.

Google Scholar

[7]

{LaV06} LaViola Jr. J. J.: An initial evaluation of a pen-based tool for creating dynamic mathematical illustrations. In Third Eurographics Workshop on Sketch-Based Interfaces and Modeling (SBIM) (New York, NY, USA, 2006), ACM, pp. 157--164.

Digital Library

Google Scholar

[8]

{LC82} Levy H. M., Clark D. W.: On the use of benchmarks for measuring system performance. SIGARCH Comput. Archit. News 10, 6 (1982), 5--8.

Digital Library

Google Scholar

[9]

{LLM*08a} Labahn G., Lank E., MacLean S., Marzouk M., Tausky D.: Mathbrush: A system for doing math on pen-based devices. The Eighth IAPR Workshop on Document Analysis Systems (DAS) (Sep 16--19 2008).

Digital Library

Google Scholar

[10]

{LLM*08b} Labahn G., Lank E., Marzouk M., Bunt A., MacLean S., Tausky D.: Mathbrush: A case study for interactive pen-based mathematics. Fifth Eurographics Workshop on Sketch-Based Interfaces and Modeling (SBIM) (June 11--13 2008).

Digital Library

Google Scholar

[11]

{Mac09} MacLean S.: Parsing handwritten mathematics. Master's thesis, David R. Cheriton School of Computer Science, University of Waterloo, 2009.

Google Scholar

[12]

{OP00} Okun O., Pietikainen M.: Automatic ground-truth generation for skew-tolerance evaluation of document layout analysis methods. In Pattern Recognition, 2000. Proceedings. 15th International Conference on (2000), vol. 4, pp. 376--379 vol. 4.

Digital Library

Google Scholar

[13]

{SNA99} Smithies S., Novins K., Arvo J.: A handwriting-based equation editor. In Graphics Interface (1999), pp. 84--91.

Digital Library

Google Scholar

Cited By

View all

Taranta EMaghoumi MPittman CLaViola JRekimoto JIgarashi TWobbrock JAvrahami D(2016)A Rapid Prototyping Approach to Synthetic Data Generation for Improved 2D Gesture RecognitionProceedings of the 29th Annual Symposium on User Interface Software and Technology10.1145/2984511.2984525(873-885)Online publication date: 16-Oct-2016
https://dl.acm.org/doi/10.1145/2984511.2984525
Maclean SLabahn G(2013)A new approach for recognizing handwritten mathematics using relational grammars and fuzzy setsInternational Journal on Document Analysis and Recognition10.1007/s10032-012-0184-x16:2(139-163)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s10032-012-0184-x
Zhen JBlagojevic RPlimmer BSingh KKara L(2012)Automated labeling of ink stroke dataProceedings of the International Symposium on Sketch-Based Interfaces and Modeling10.5555/2331067.2331078(67-75)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.5555/2331067.2331078
Show More Cited By

Index Terms

Tools for the efficient generation of hand-drawn corpora based on context-free grammars
1. Computing methodologies
  1. Machine learning

Recommendations

Lexicalized context-free grammars
ACL '93: Proceedings of the 31st annual meeting on Association for Computational Linguistics

Lexicalized context-free grammar(LCFG) is an attractive compromise between the parsing efficiency of context-free grammar (CFG) and the elegance and lexical sensitivity of lexicalized tree adjoining grammar (LTAG). LCFG is a restricted form of LTAG that ...
Ordered Context-Free Grammars
Implementation and Application of Automata
Abstract
We propose a new unambiguous grammar formalism, referred to as ordered context-free grammars, which is identical to context-free grammars, apart from the property that it also places an order on parse trees. Since only a minor modification to ...
LR(k)-parsing of Coupled-Context-Free Grammars
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 1

Coupled-Context-Free Grammars are a generalization of context-free grammars obtained by combining nonterminals to parentheses which can only be substituted simultaneously. Referring to the generative capacity of the grammars we obtain an infinite ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SBIM '09: Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling

August 2009

168 pages

ISBN:9781605586021

DOI:10.1145/1572741

Editors:
Dieter Fellner
TU Darmstadt & Fraunhofer IGD, Germany
,
Stephen Spencer
The University of Washington
,
General Chairs:
Nathan Carr
Adobe Systems
,
Faramarz Samavati
University of Calgary, Canada
,
Program Chairs:
Cindy Grimm
Washington University in St. Louis
,
Joseph J. LaViola
University of Central Florida

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

SBIM '09

Sponsor:

SIGGRAPH
EUROGRAPHICS

SBIM '09: SBIM '09 - Sixth Eurographics Symposium on Sketch-Based Modeling and Interaction

August 1 - 2, 2009

Louisiana, New Orleans

Acceptance Rates

Overall Acceptance Rate 20 of 36 submissions, 56%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
154
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Taranta EMaghoumi MPittman CLaViola JRekimoto JIgarashi TWobbrock JAvrahami D(2016)A Rapid Prototyping Approach to Synthetic Data Generation for Improved 2D Gesture RecognitionProceedings of the 29th Annual Symposium on User Interface Software and Technology10.1145/2984511.2984525(873-885)Online publication date: 16-Oct-2016
https://dl.acm.org/doi/10.1145/2984511.2984525
Maclean SLabahn G(2013)A new approach for recognizing handwritten mathematics using relational grammars and fuzzy setsInternational Journal on Document Analysis and Recognition10.1007/s10032-012-0184-x16:2(139-163)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s10032-012-0184-x
Zhen JBlagojevic RPlimmer BSingh KKara L(2012)Automated labeling of ink stroke dataProceedings of the International Symposium on Sketch-Based Interfaces and Modeling10.5555/2331067.2331078(67-75)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.5555/2331067.2331078
MacLean STausky DLabahn GLank EMarzouk MDo ELeon JHammond TNealen A(2011)Is the iPad useful for sketch input?Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling10.1145/2021164.2021166(7-14)Online publication date: 5-Aug-2011
https://dl.acm.org/doi/10.1145/2021164.2021166
Tausky DLank EMann RLabahn GPu PPazzani MAndré ERiecken D(2011)Analyzing sketch content using in-air packet informationProceedings of the 16th international conference on Intelligent user interfaces10.1145/1943403.1943476(403-406)Online publication date: 13-Feb-2011
https://dl.acm.org/doi/10.1145/1943403.1943476

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Lexicalized context-free grammars

Ordered Context-Free Grammars

LR(k)-parsing of Coupled-Context-Free Grammars