Anjan Dutta2013
Proceedings
2013
12th International Conference on Document Analysis and Recognition
1078-1082
Anjan Dutta
Josep Llados
Horst Bunke
Umapada Pal
ICDAR
Near Convex Region Adjacency Graph and Approximate Neighborhood String Matching for Symbol Spotting in Graphical Documents
This paper deals with a subgraph matching problem in Region Adjacency Graph (RAG) applied to symbol spotting in graphical documents. RAG is a very important, efﬁcient and natural way of representing graphical information with a graph but this is limited to cases where the information is well deﬁned with perfectly delineated regions. What if the information we are interested in is not conﬁned within well deﬁned regions? This paper addresses this particular problem and solves it by deﬁning near convex grouping of oriented line segments which results in near convex regions. Pure convexity imposes hard constraints and can not handle all the cases efﬁciently. Hence to solve this problem we have deﬁned a new type of convexity of regions, which allows convex regions to have concavity to some extend. We call this kind of regions Near Convex Regions (NCRs). These NCRs are then used to create the Near Convex Region Adjacency Graph (NCRAG) and with this representation we have formulated the problem of symbol spotting in graphical documents as a subgraph matching problem. For subgraph matching we have used the Approximate Edit Distance Algorithm (AEDA) on the neighborhood string, which starts working after ﬁnding a key node in the input or target graph and iteratively identiﬁes similar nodes of the query graph in the neighborhood of the key node. The experiments are performed on artiﬁcial, real and distorted datasets.