Playing with Error-Tolerant Subgraph Isomorphism in Line Drawings

Josep Lladós, Enric Martí

Computer Vision Center - Dep. d'Informàtica - Edifici O - Universitat Autònoma de Barcelona.

08193 Bellaterra (Barcelona)



This paper describes an error-tolerant matching algorithm which has been applied to find line-based figures embedded into hand drawn sketches. Line drawings can be efficiently represented by attributed graphs, however a matching procedure using these graphs appears to be computationally expensive and highly sensitive to local distortions. We propose a matching algorithm in terms of graph regions. Not only does this reduce the amount of information to analyse but also is more stable under distortion. Region Adjacency Graphs (RAG) are built from graphs representing documents and a set of edit operations to transform one RAG into another one are defined. String matching techniques are used to measure region similarity. Experimental results on various kinds of documents show the reliability of the proposed method.

Keywords: Graph Matching, String Matching, Line Drawings, Document Analysis.

Get a postscript version of the paper