A Product Graph Based Method for Dual Subgraph Matching Applied to Symbol Spotting
Anjan Dutta
author
Josep Llados
author
Horst Bunke
author
Umapada Pal
author
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.
Product graph
Dual edge graph
Subgraph matching
Random walks
Graph kernel
DAG; 600.077
exported from refbase (http://refbase.cvc.uab.es/show.php?record=2698), last updated on Wed, 16 Dec 2015 10:41:32 +0100
text
http://refbase.cvc.uab.es/files/DLB2014.pdf
10.1007/978-3-662-44854-0_2
Admin @ si @ DLB2014
Graphics Recognition. Current Trends and Challenges
Bart Lamiroy
editor
Jean-Marc Ogier
editor
2014
Springer Berlin Heidelberg
monographic
book
8746
7
11
978-3-662-44853-3
0302-9743
LNCS