Symbol recognition by error-tolerant subgraph matching between region adjacency graphs

Josep Lladós, Enric Martí, Juan José Villanueva

    Research output: Contribution to journalArticleResearchpeer-review

    166 Citations (Scopus)


    In this paper, we propose an error-tolerant subgraph isomorphism algorithm formulated in terms of Region Adjacency Graphs (RAG). A set of edit operations to transform one RAG into another one are defined. Regions are represented by polylines and string matching techniques are used to measure their similarity. The algorithm follows a branch and bound approach driven by the RAG edit operations. This formulation allows matching computing under distorted inputs and also reachong a solution in a near polynomial time. The algorithm has been used for recognizing symbols in hand drawn diagrams.
    Original languageEnglish
    Pages (from-to)1137-1143
    JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
    Publication statusPublished - 1 Oct 2001


    • Graph edit distance
    • Graph isomorphism
    • Graph matching
    • Inexact graph matching
    • Subgraph isomorphism
    • Symbol recognition


    Dive into the research topics of 'Symbol recognition by error-tolerant subgraph matching between region adjacency graphs'. Together they form a unique fingerprint.

    Cite this