This report presents the work carried out for the ow chart recognition task in the course of the CLEF-IP 2012 competition. The goal is to obtain structural information of ow charts based on the visual content of the images. To this end, for each ow chart a list of its nodes and their interconnections, i.e. its edges, is extracted and the type of the nodes and edges and attached text is recognized. The automatic recognition task is done in three stages: (1) ow chart image pre-processing using connected component analysis, morphological lters and line segmentation, (2) identi cation of nodes, junction points, end points and edges and (3) recognition of text, geometric node types and edge directions. Examples demonstrate good recognition results obtained for 100 tested ow chart images.
In traditional engineering drawings and diagrams, algorithms, operations and
processes are frequently represented as ow charts. In patents, these drawings
generally are accessible only in image format. For automatic querying the huge
information content of the ow charts available in patents, it is important to
convert the information in the images into a high-level description [
This paper describes our approach for automatically analyzing the visual
structure of ow charts and our participation in the ow chart recognition task [
At this, it is assumed that a owchart can be interpreted as a graph with a set
of nodes and edges [
The rest of this paper is organized as follows: Section 2 describes the applied image processing methods for producing the above mentioned metadata and results are presented in Section 3. 2
A summary of the ow chart recognition process is shown in Figure 2,
understandably a ow chart itself. First, textual descriptions in the input image are
extracted using optical character recognition, followed by pre-processing, line
segmentation and grouping. Next, junctions and end points are detected and
based on that, nodes and their interconnections (edges) are recognized. Finally,
the type of the nodes and the direction of the edges is computed and the visual
information content from the ow chart is provided in a textual graph
representation (for the format see [
The quality of Figure 2 was deliberately modi ed in a way to match the
look&feel and (sometimes bad) image quality of many technical drawings found
in patents. When viewed in full detail, lines are frequently frayed, non-contiguous
and not strictly vertical or horizontal, which clearly presents challenges for
image processing. The following subsections explain the processing steps of our
approach necessary for recognizing the visual structure of ow charts.
(a)
(b)
(c)
Fig. 1. Example showing details of di erent processing steps. The black and white
input image (a) is pre-processed and based on the resulting cleaned and thinned image
(b) the nal visual structure (c) is recognized. It shows nodes (solid colored border),
edges (dashed line), junction points (red lled circle), end points (green lled circle)
and the nodes' IDs (numbers in red boxes). Best viewed in color
A commercial optical character recognition (OCR) software [
First, in the binary input image all connected components with a small number of pixels and aspect ratio typical to characters (as opposed to lines) are removed. Second, the image that is now cleaned from text-like fragments is subjected to a morphological close and binary image thinning operation, see Figure 1(b). Third, edge points are identi ed and linked to segments. By respecting a speci ed minimum line length and maximum deviation from the original data, the pixel image can now represented as a list of linked line segments. 2.3
Detection of Junctions, End Points, Nodes and Connecting Edges Junctions and end points can be easily found by scanning the linked line segments from the previous step for areas where three or more segments meet (junction) or where a segment has no further connection (end point). In many cases, end points are actually the end of wiggly edges that connect the nodes of the owchart with their labels.
Next, the nodes of a ow chart are detected by iteratively nding for each segment another linking segment that is close enough (allowing for nodes with small gaps between segments) and that has the smallest angle between them. A combination of linked segments that meets certain criteria, such as a maximum number of segments per node and sum of angle values, constitutes a node.
Subsequently, connecting edges are derived from the remaining segments that that link nodes, junctions or end points. These edges may obviously consist of multiple segments. 2.4
The goal is to classify 10 types of nodes (oval, rectangle, double-rectangle,
parallelogram, diamond, circle, point, cylinder, no-box and unknown). Their exact
de nition is given in the task description document [
By using 400 annotated examples, discriminating features and their statistics have been empirically determined for each type. The statistics consist of average, standard deviation, minimum and maximum values for each feature and node type. Figure 3 plots 3 features over 3 node types. The characteristics of the data show that it is possible to classify the node types. With help of these statistics a score for each class is calculated and the maximum score results in the classi ed node type. If the maximum score is below 50% the node type is declared as "unknown". An unknown node type is an indication of a possibly inaccurate preceding node detection result and as a consequence the node can be discarded (c.f. runs with node type lter in Section 3).
The edge direction is estimated by comparing the number of black pixels of the edge segments. A window is centered at the end of the edges and the edge is directed if one the windows has clearly more pixels than the other. The related thresholds have been determined using annotations (c.f. Section 3). 3
For the ow chart recognition task of the CLEF-IP 2012 competition [
For evaluating our approach and di erent con gurations thereof, we produced a set of runs described in Table 1.
All of the di erent con gurations of our ow chart recognition system were
applied on a test set of 100 images. Details on the evaluation and the applied most
common subgraph metric can be found in the task description document [
Nevertheless, the examples shown in Figure 4 and 5 should give an impression of the quality of the ow chart recognition system.
(a)
(b)
(c)
(d)
This paper presented the experiments for our participation in the CLEF-IP 2012
ow chart recognition challenge [
This work was supported by the Austrian Research Promotion Agency (FFG) FIT-IT project IMPEx 1 Image Mining for Patent EXploration (No. 825846). 1 http://www.joanneum.at/?id=3922