@PhdThesis{JoanMas2010,
author="Joan Mas",
editor="Gemma Sanchez
and Josep Llados",
title="A Syntactic Pattern Recognition Approach based on a Distribution Tolerant Adjacency Grammar and a Spatial Indexed Parser. Application to Sketched Document Recognition",
year="2010",
publisher="Ediciones Graficas Rey",
abstract="Sketch recognition is a discipline which has gained an increasing interest in the last20 years. This is due to the appearance of new devices such as PDA, Tablet PC{\textquoteright}sor digital pen \& paper protocols. From the wide range of sketched documents wefocus on those that represent structured documents such as: architectural floor-plans,engineering drawing, UML diagrams, etc. To recognize and understand these kindsof documents, first we have to recognize the different compounding symbols and thenwe have to identify the relations between these elements. From the way that a sketchis captured, there are two categories: on-line and off-line. On-line input modes referto draw directly on a PDA or a Tablet PC{\textquoteright}s while off-line input modes refer to scana previously drawn sketch.This thesis is an overlapping of three different areas on Computer Science: PatternRecognition, Document Analysis and Human-Computer Interaction. The aim of thisthesis is to interpret sketched documents independently on whether they are capturedon-line or off-line. For this reason, the proposed approach should contain the followingfeatures. First, as we are working with sketches the elements present in our inputcontain distortions. Second, as we would work in on-line or off-line input modes, theorder in the input of the primitives is indifferent. Finally, the proposed method shouldbe applied in real scenarios, its response time must be slow.To interpret a sketched document we propose a syntactic approach. A syntacticapproach is composed of two correlated components: a grammar and a parser. Thegrammar allows describing the different elements on the document as well as theirrelations. The parser, given a document checks whether it belongs to the languagegenerated by the grammar or not. Thus, the grammar should be able to cope withthe distortions appearing on the instances of the elements. Moreover, it would benecessary to define a symbol independently of the order of their primitives. Concerning to the parser when analyzing 2D sentences, it does not assume an order in theprimitives. Then, at each new primitive in the input, the parser searches among theprevious analyzed symbols candidates to produce a valid reduction.Taking into account these features, we have proposed a grammar based on Adjacency Grammars. This kind of grammars defines their productions as a multisetof symbols rather than a list. This allows describing a symbol without an order intheir components. To cope with distortion we have proposed a distortion model.This distortion model is an attributed estimated over the constraints of the grammar and passed through the productions. This measure gives an idea on how far is thesymbol from its ideal model. In addition to the distortion on the constraints otherdistortions appear when working with sketches. These distortions are: overtracing,overlapping, gaps or spurious strokes. Some grammatical productions have been defined to cope with these errors. Concerning the recognition, we have proposed anincremental parser with an indexation mechanism. Incremental parsers analyze theinput symbol by symbol given a response to the user when a primitive is analyzed.This makes incremental parser suitable to work in on-line as well as off-line inputmodes. The parser has been adapted with an indexation mechanism based on a spatial division. This indexation mechanism allows setting the primitives in the spaceand reducing the search to a neighbourhood.A third contribution is a grammatical inference algorithm. This method given aset of symbols captures the production describing it. In the field of formal languages,different approaches has been proposed but in the graphical domain not so much workis done in this field. The proposed method is able to capture the production froma set of symbol although they are drawn in different order. A matching step basedon the Haussdorff distance and the Hungarian method has been proposed to matchthe primitives of the different symbols. In addition the proposed approach is able tocapture the variability in the parameters of the constraints.From the experimental results, we may conclude that we have proposed a robustapproach to describe and recognize sketches. Moreover, the addition of new symbolsto the alphabet is not restricted to an expert. Finally, the proposed approach hasbeen used in two real scenarios obtaining a good performance.",
optnote="DAG",
optnote="exported from refbase (http://refbase.cvc.uab.es/show.php?record=1334), last updated on Fri, 17 Dec 2021 14:03:51 +0100",
isbn="978-84-937261-4-0"
}