A syntactic approach based on distortion-tolerant Adjacency Grammars and a spatial-directed parser to interpret sketched diagrams

J. Mas, J. Llados, G. Sanchez, J. A.P. Jorge

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

This paper presents a syntactic approach based on Adjacency Grammars (AG) for sketch diagram modeling and understanding. Diagrams are a combination of graphical symbols arranged according to a set of spatial rules defined by a visual language. AG describe visual shapes by productions defined in terms of terminal and non-terminal symbols (graphical primitives and subshapes), and a set functions describing the spatial arrangements between symbols. Our approach to sketch diagram understanding provides three main contributions. First, since AG are linear grammars, there is a need to define shapes and relations inherently bidimensional using a sequential formalism. Second, our parsing approach uses an indexing structure based on a spatial tessellation. This serves to reduce the search space when finding candidates to produce a valid reduction. This allows order-free parsing of 2D visual sentences while keeping combinatorial explosion in check. Third, working with sketches requires a distortion model to cope with the natural variations of hand drawn strokes. To this end we extended the basic grammar with a distortion measure modeled on the allowable variation on spatial constraints associated with grammar productions. Finally, the paper reports on an experimental framework an interactive system for sketch analysis. User tests performed on two real scenarios show that our approach is usable in interactive settings. © 2010 Elsevier Ltd. All rights reserved.
Original languageEnglish
Pages (from-to)4148-4164
JournalPattern Recognition
Volume43
Issue number12
DOIs
Publication statusPublished - 1 Dec 2010

Keywords

  • Adjacency Grammars
  • Diagram understanding
  • Incremental parsing
  • Sketched diagrams
  • Spatial directed parsing
  • Symbol recognition
  • Syntactic Pattern Recognition

Fingerprint Dive into the research topics of 'A syntactic approach based on distortion-tolerant Adjacency Grammars and a spatial-directed parser to interpret sketched diagrams'. Together they form a unique fingerprint.

Cite this