Year

1995

Degree Name

Doctor of Philosophy

Department

Department of Computer Science

Abstract

Much of the information contained in scientific documents comes in the form of graphs and line diagrams such as circuit diagrams or chemical structure diagrams. If the contents of such documents are to be properly represented in computerized information systems, then these diagrammatic data must somehow be converted to computermanipulable and searchable form.

In general, it is possible to convert structural diagrams into "graphs" with labelled nodes and edges. Graphs are easily represented as data structures within computer programs and searches of collections of such data are possible using graph matching ("isomorphism") algorithms.

This thesis addresses the general problem of converting, into such computer manipulable graphs, the data presented in structural diagrams on scanned images of pages taken from scientific documents.

The interpreter system developed as part of this thesis uses a multi-step process extract information from scanned images. The original image data are transformed through several preprocessing steps to obtain a representation in terms of line segments and arcs. These data are then processed using a general purpose matching system that uses "templates" which define those groupings of graphic elements that are significant within a particular domain. These groupings become the nodes of the graph. Other elements extracted from the image become the edges.

In domains where line diagrams are used extensively, there are specific grouping of lines and arcs that are semantically meaningful: For example, a combination of parallel lines and complex arcs that represents a transformer. These groupings, or "templates", are specified by a domain expert, and are stored in a dictionary. Each template represents a standard component as used in a particular problem domain, and is defined in terms of a finite set of primitives and their topological relationships.

We have implemented and tested the idea of templates on different types of diagrams including circuit diagrams, chemical structures, flowcharts, and even cursive script writings. Although these sorts of diagram are very different in appearance and application, they could all be interpreted by defining appropriate templates.

The thesis presents the results for a variety of applications and reviews some of limitations of the approach taken.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.