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

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

doi:https://doi.org/10.1109/34.954603

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

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

Research output: Contribution to journal › Article › Research › peer-review

163 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	1137-1143
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	23
DOIs	https://doi.org/10.1109/34.954603
Publication status	Published - 1 Oct 2001

Keywords

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

Access to Document

https://doi.org/10.1109/34.954603

Fingerprint 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

@article{de45dd838e2c41fabe10d49de23f5fdf,

title = "Symbol recognition by error-tolerant subgraph matching between region adjacency graphs",

abstract = "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.",

keywords = "Graph edit distance, Graph isomorphism, Graph matching, Inexact graph matching, Subgraph isomorphism, Symbol recognition",

author = "Josep Llad{\'o}s and Enric Mart{\'i} and Villanueva, {Juan Jos{\'e}}",

year = "2001",

month = oct,

day = "1",

doi = "https://doi.org/10.1109/34.954603",

language = "English",

volume = "23",

pages = "1137--1143",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

}

TY - JOUR

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

AU - Lladós, Josep

AU - Martí, Enric

AU - Villanueva, Juan José

PY - 2001/10/1

Y1 - 2001/10/1

N2 - 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.

AB - 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.

KW - Graph edit distance

KW - Graph isomorphism

KW - Graph matching

KW - Inexact graph matching

KW - Subgraph isomorphism

KW - Symbol recognition

U2 - https://doi.org/10.1109/34.954603

DO - https://doi.org/10.1109/34.954603

M3 - Article

VL - 23

SP - 1137

EP - 1143

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

SN - 0162-8828

ER -