A symbol spotting approach in graphical documents by hashing serialized graphs

Anjan Dutta, Josep Lladós, Umapada Pal

Research output: Contribution to journalArticleResearchpeer-review

28 Citations (Scopus)


In this paper we propose a symbol spotting technique in graphical documents. Graphs are used to represent the documents and a (sub)graph matching technique is used to detect the symbols in them. We propose a graph serialization to reduce the usual computational complexity of graph matching. Serialization of graphs is performed by computing acyclic graph paths between each pair of connected nodes. Graph paths are one-dimensional structures of graphs which are less expensive in terms of computation. At the same time they enable robust localization even in the presence of noise and distortion. Indexing in large graph databases involves a computational burden as well. We propose a graph factorization approach to tackle this problem. Factorization is intended to create a unified indexed structure over the database of graphical documents. Once graph paths are extracted, the entire database of graphical documents is indexed in hash tables by locality sensitive hashing (LSH) of shape descriptors of the paths. The hashing data structure aims to execute an approximate k-NN search in a sub-linear time. We have performed detailed experiments with various datasets of line drawings and compared our method with the state-of-the-art works. The results demonstrate the effectiveness and efficiency of our technique. © 2012 Elsevier Ltd.
Original languageEnglish
Pages (from-to)752-768
JournalPattern Recognition
Issue number3
Publication statusPublished - 1 Mar 2013


  • Graph factorization
  • Graph matching
  • Graph paths
  • Graph serialization
  • Graphics recognition
  • Hashing
  • Symbol spotting


Dive into the research topics of 'A symbol spotting approach in graphical documents by hashing serialized graphs'. Together they form a unique fingerprint.

Cite this