TY - JOUR

T1 - Graph matching versus graph parsing in graphics recognition - A combined approach

AU - Lladós, Josep

AU - Sánchez, Gemma

PY - 2004/5/1

Y1 - 2004/5/1

N2 - Symbol recognition is a well-known challenge in the field of graphics recognition. Due to the representational power of graph structures, a number of graph-based approaches are used to answer whether a known symbol appears in a document and under which degree of confidence. In this paper, we review the particularities of graph structures representing technical drawings and we classify them in two categories, depending on whether the structure that they represent consists of prototype patterns or repetitive patterns. The recognition is then formulated in terms of graph matching or graph parsing, respectively. Since some symbols consist of two types of structures, the main contribution of this work is to propose a combined strategy. In addition, the combination of graph matching and graph parsing processes is based on a common graph structure that also involves a graph indexing mechanism. Graph nodes are classified in equivalence classes depending on their local configuration. Graph matching indexes in such equivalence classes using the information of model graph nodes as local descriptors, and then global consistency is checked using the graph edge attributes. On the other hand, representatives of equivalence classes are used as tokens of a graph grammar that guides a parsing process to recognize repetitive structures.

AB - Symbol recognition is a well-known challenge in the field of graphics recognition. Due to the representational power of graph structures, a number of graph-based approaches are used to answer whether a known symbol appears in a document and under which degree of confidence. In this paper, we review the particularities of graph structures representing technical drawings and we classify them in two categories, depending on whether the structure that they represent consists of prototype patterns or repetitive patterns. The recognition is then formulated in terms of graph matching or graph parsing, respectively. Since some symbols consist of two types of structures, the main contribution of this work is to propose a combined strategy. In addition, the combination of graph matching and graph parsing processes is based on a common graph structure that also involves a graph indexing mechanism. Graph nodes are classified in equivalence classes depending on their local configuration. Graph matching indexes in such equivalence classes using the information of model graph nodes as local descriptors, and then global consistency is checked using the graph edge attributes. On the other hand, representatives of equivalence classes are used as tokens of a graph grammar that guides a parsing process to recognize repetitive structures.

KW - Graph grammars

KW - Graph matching

KW - Graphics recognition

U2 - 10.1142/S0218001404003204

DO - 10.1142/S0218001404003204

M3 - Review article

SN - 0218-0014

VL - 18

SP - 455

EP - 473

JO - International Journal of Pattern Recognition and Artificial Intelligence

JF - International Journal of Pattern Recognition and Artificial Intelligence

IS - 3

ER -