A product graph based method for dual subgraph matching applied to symbol spotting

Anjan Dutta, Josep Lladós, Horst Bunke, Umapada Pal

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

Abstract

©Springer-Verlag Berlin Heidelberg 2014. Product graph has been shown as a way for matching subgraphs. This paper reports the extension of the product graph methodology for subgraph matching applied to symbol spotting in graphical documents. Here we focus on the two major limitations of the previous version of the algorithm: (1) spurious nodes and edges in the graph representation and (2) inefficient node and edge attributes. To deal with noisy information of vectorized graphical documents, we consider a dual edge graph representation on the original graph representing the graphical information and the product graph is computed between the dual edge graphs of the pattern graph and the target graph. The dual edge graph with redundant edges is helpful for efficient and tolerating encoding of the structural information of the graphical documents. The adjacency matrix of the product graph locates the pair of similar edges of two operand graphs and exponentiating the adjacency matrix finds similar random walks of greater lengths. Nodes joining similar random walks between two graphs are found by combining different weighted exponentials of adjacency matrices. An experimental investigation reveals that the recall obtained by this approach is quite encouraging.
Original languageEnglish
Pages (from-to)11-24
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8746
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • Dual edge graph
  • Graph kernel
  • Product graph
  • Random walks
  • Subgraph matching

Fingerprint Dive into the research topics of 'A product graph based method for dual subgraph matching applied to symbol spotting'. Together they form a unique fingerprint.

Cite this