GRAPH MATCHING VERSUS GRAPH PARSING IN GRAPHICS RECOGNITION — A COMBINED APPROACH
- 1 May 2004
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Pattern Recognition and Artificial Intelligence
- Vol. 18 (3), 455-473
- https://doi.org/10.1142/s0218001404003204
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- Symbol recognition by error-tolerant subgraph matching between region adjacency graphsIeee Transactions On Pattern Analysis and Machine Intelligence, 2001
- Architectural symbol recognition using a network of constraintsPattern Recognition Letters, 2001
- Synthesis of Representative Graphical Symbols by Computing Generalized Median GraphLecture Notes in Computer Science, 2000
- Recent Advances in Graph MatchingInternational Journal of Pattern Recognition and Artificial Intelligence, 1997
- A graph grammar programming style for recognition of music notationMachine Vision and Applications, 1993
- Recognizing Hand-Drawn Electrical Circuit Symbols with Attributed Graph MatchingPublished by Springer Science and Business Media LLC ,1992
- TRANSLATION-, ROTATION- AND SCALE- INVARIANT RECOGNITION OF HAND-DRAWN SYMBOLS IN SCHEMATIC DIAGRAMSInternational Journal of Pattern Recognition and Artificial Intelligence, 1990
- HYBRID PATTERN RECOGNITION METHODSPublished by World Scientific Pub Co Pte Ltd ,1990
- A syntactic/geometric approach to recognition of dimensions in engineering machine drawingsComputer Vision, Graphics, and Image Processing, 1989
- PATTERN RECOGNITION BY GRAPH MATCHING—COMBINATORIAL VERSUS CONTINUOUS OPTIMIZATIONInternational Journal of Pattern Recognition and Artificial Intelligence, 1988