Combining Graph Matching and Hough Transform for Hand-Drawn Graphical Document Analysis. Application to Architectural Drawings

Josep Lladós PhD Dissertation.

November, 1997.



The large number of existing documents, the production of a multitude of new ones, and the progress in the paperless office applications, have enlarged the set of requirements within the field of document analysis. New research interests have been stated about text, symbols, maps, document structure, etc. One of the most promising fields within the vaste domain of document analysis is concerned about graphics recognition. In this thesis we have studied two of the major problems of graphics recognition, namely, hatched pattern discrimination and symbol recognition. Both goals have been addressed under distortion conditions of the input data. The development of algorithmic solutions to solve the stated goals involves a further study of two well-know techniques of Computer Vision: the Hough transform and the Graph matching theory. An application illustrates the proposed methods: a system to understand hand drawn architectural floor plans as an alternative CAD input technique.

A document, after a vectorization stage, is represented by an attributed graph structure where graph nodes represent characteristic points (junction, inflexion and end points), and graph edges approximate segments by straight lines or circumference arcs. The attributes associated to graph nodes and edges allow to preserve the geometrical and topological properties of the document.

Hatched patterns are detected in terms of their defining attributes: orientation, length and frequency of the filling segments. A Hough-based transform is defined to map the edges of a graph to a parameter space where clusters define the attribute values of the hatched areas. Also, the range of tolerance for these attributes is computed from the parameter space clusters. The main advantage of this method is its flexibility since the attribute values of hatched patterns are computed from the document itself and they are not previously set.

The heart of this thesis work is the development of a symbol recognition algorithm using graph matching techniques. Since symbols to be recognized and the input document are represented by attributed graphs, symbol recognition is performed by looking for a subgraph isomorphism between model and input graphs. Moreover, the documents, and even the model symbols, are freehand designed, thus, both, model and input graph may present some distortions and an exact graph matching procedure would never succeed. Our algorithm actually looks for an error-tolerant subgraph isomorphism. An error model underlying the matching is designed in terms of a set of graph edit operations which transform one graph to another one. To increase the robustness of the method against distortions, and also its performance, the graph matching is computed between region adjacency graphs instead of plain graphs. This involves the definition of a region similarity criterion in terms of the string edit distance between region boundary strings.

Finally, a last contribution of this thesis is the design of a simple and fast method to detect perfect and distorted rotational and reflectional symmetries of 2D objects.  The boundary of a shape is polygonally approximated and represented as a string. Rotational symmetries are found by cycling string matching between two identical copies of the shape string. The set of minimum cost edit sequences that transform the shape string to a cyclically shifted version of itself define the rotational symmetry and its order. A modification of the algorithm is proposed to detect reflectional symmetries.

Keywords: Graphics recognition, Hough transform, graph matching, string matching, symmetry.

Get a postscript version of the paper