The analysis/recognition subject of graph (or business graph) structures aims to distinguish individual composite elements structurally, identify their constructive relationships logically, and extract the interpretative information semantically. Namely, the objective is almost similar to that in currently investigated document image understanding issues. Of course, the final goal is not only to extract individual elements meaningfully but also to extract the semantic information interpretatively. Ordinarily, the graph structure is designed under some composition means though the composite elements are complicatedly organized with each other: the connective and neighboring relationships/locations among some composite elements are definitely specified. Many of constructive elements are often allocated to appropriately predefined positions according to the illustrated structures of individual graphs. Thus, we can construct a layout knowledge for graph structures with respect to the connective/neighboring relationships among some composite elements. Of course, this layout structure is different from that in the traditional document image understanding because the structures are very varied in point of drawing methods of illustrators.
In this paper, we address a recognition problem of bar-graph [gif file, 12Kb] structures, which are one of various types of graphs, because this type of graphs are the most basic. We represent the layout knowledge of bar-graph structures, using the network This network is called the layout network [PS file, 62Kb]. In this network, the nodes indicate individual composite elements and the edges point out the connective/neighboring relationships among composite elements. Of course, this layout network does not indicate the structures of bar-graphs deterministically but represents all structural possibilities for bar-graph illustrations though the physical features of individual composite elements such as positions, forms, lengths, sizes, occurrences, notations, etc. are different one by one and also the logical features among interrelated composite elements such as connectivities, adjacencies, correspondences, etc. are varied individually. Thus, we introduce the rules to control the link interpretation mechanism for navigating nodes along edges.
Our bar-graph recognition system, as a current version, is composed mainly of two different phases: the first is the decomposition of composite elements, and the second is the identification of graph primitives from composite elements. The graph primitives are defined as composite elements which were corresponded correctly to the nodes in the layout network. In the decomposition phase, various kinds of illustrated elements are extracted individually, using constraints about composite elements. While, in the identification phase, these extracted elements are interpretatively distinguished as graph primitives, using the layout network and rules.
![bar-graph [gif file, 12Kb]](http://www.watanabe.nuie.nagoya-u.ac.jp/student/yokokura/graphs/primitives.gif){kind=link}