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

    Research output: Contribution to journalReview articleResearchpeer-review

    18 Citations (Scopus)

    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.
    Original languageEnglish
    Pages (from-to)455-473
    JournalInternational Journal of Pattern Recognition and Artificial Intelligence
    Volume18
    Issue number3
    DOIs
    Publication statusPublished - 1 May 2004

    Keywords

    • Graph grammars
    • Graph matching
    • Graphics recognition

    Fingerprint

    Dive into the research topics of 'Graph matching versus graph parsing in graphics recognition - A combined approach'. Together they form a unique fingerprint.

    Cite this