|   | 
Author Muhammad Muzzamil Luqman; Jean-Yves Ramel; Josep Llados; Thierry Brouard
Title Subgraph Spotting Through Explicit Graph Embedding: An Application to Content Spotting in Graphic Document Images Type Conference Article
Year 2011 Publication 11th International Conference on Document Analysis and Recognition Abbreviated Journal
Volume Issue Pages 870-874
Abstract We present a method for spotting a subgraph in a graph repository. Subgraph spotting is a very interesting research problem for various application domains where the use of a relational data structure is mandatory. Our proposed method accomplishes subgraph spotting through graph embedding. We achieve automatic indexation of a graph repository during off-line learning phase, where we (i) break the graphs into 2-node sub graphs (a.k.a. cliques of order 2), which are primitive building-blocks of a graph, (ii) embed the 2-node sub graphs into feature vectors by employing our recently proposed explicit graph embedding technique, (iii) cluster the feature vectors in classes by employing a classic agglomerative clustering technique, (iv) build an index for the graph repository and (v) learn a Bayesian network classifier. The subgraph spotting is achieved during the on-line querying phase, where we (i) break the query graph into 2-node sub graphs, (ii) embed them into feature vectors, (iii) employ the Bayesian network classifier for classifying the query 2-node sub graphs and (iv) retrieve the respective graphs by looking-up in the index of the graph repository. The graphs containing all query 2-node sub graphs form the set of result graphs for the query. Finally, we employ the adjacency matrix of each result graph along with a score function, for spotting the query graph in it. The proposed subgraph spotting method is equally applicable to a wide range of domains, offering ease of query by example (QBE) and granularity of focused retrieval. Experimental results are presented for graphs generated from two repositories of electronic and architectural document images.
Address Beijing, China
Corporate Author Thesis
Publisher Place of Publication Editor
Language (up) Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1520-5363 ISBN 978-1-4577-1350-7 Medium
Area Expedition Conference ICDAR
Notes DAG Approved no
Call Number Admin @ si @ LRL2011 Serial 1790
Permanent link to this record