Rule-Based graphics recognition on unconstrained maps
To interpret of a document, a priori knowledge of the document must be used. This
knowledge can be divided into the following two categories:
- Domain-dependent knowledge
- Domain-independent knowledge
Domain-dependent knowledge refers to any information regarding the specific map
conversion being performed. This includes information regarding how devices or other
objects in the system connect and interact, as well as information ~garding the particular
graphic presentation of the domain objects. Domain-independent knowledge refers to any
information regarding shapes that will be recognized, such as circles, sqwues, etc. The
range of possibilities that maybe encountered on a particular document is certainly limited
but a circle on one map is a circle on any other map.
The separation of knowledge based on its domain dependency reduces m-engineering
efforts and increases the system’s flexibility when the system is used to convert documents
from different domains.
System Architecture
A multi-layer system architecture for building a rule-based data conversion system to
extract information from a raster image of a document is depicted in Figure 2(a). The
layers of the architecture are:
- Image processing library: this layer contains C++ routines for image processing,
geometric computation, constrained search and spatial tracking.
- Vector analysis: this layer interfaces with the low-level image processing layer and has
a knowledge source associated with it. This layer directs the image analysis operations
and interprets the results repoxted horn the bottom layer. Based on the reports received
and the rules in its knowledge source, it either modifies the current low-layer operations
or continues the ongoing ones. Taken together, this layer and the image processing
library form a line extraction subsystem.
- Graphics recognition: this layer interfaces with the vector analysis layer and has a
knowledge source attached to it. This layer directs the primitive vector extraction,
thereby indirectly controlling low-level image analysis. This layer also interprets the
processing nmdts from the vector analysis layer and modifies the current low-level
operations as necessary. This layer and the lower two layers constitute a graphics
recognition subsystem.
- Domain object reasoning: this is the top layer of the whole system which directly
interfaces with the graptics recognition layer. The knowledge source related to this
layer is mainly domain dependent. The layer directs the graphics recognition and
interprets the resulted symbolic labels of graphical shapes. The overall map conversion
system comprises this layer and the three lower layers. For the ease of notation, this
overall system is called domain object reasoning subsystem.
The three subsystems derived from the above four processing layers are represented in
Figure 2(b). The control unit corresponds to a subsystem’s top layer, and the processing
unit represents the subsystem’s remaining lower layer(s).
The line extraction subsystem implements model- and data-driven processing, producing
domain-independent vectors. Primitive vectors ate persisted in the vector analysis layer as
they are validated. Thus, domain-independent knowledge is appropriate and essential to the
subsystem. Further, because of the characteristics of heavy procedural processing in this
stage, the related rule set is kept small and simple. The subsystem’s processing is largely
data-driven.
The graphics recognition subsystem also implements model- and data-driven processing,
producing domain-independent graphical shapes. Validated primitive graphical shapes are
persisted in the graphics recognition layer. The roles in this subsystem’s knowledge source
are generally domain independent due to the invariant natwe of graphical shapes. These
rules encode the models of the commonly encountered shapes. Processing is heavy in both
model- and data-driven processing.
The domain object reasoning subsystem aims at generating domain-dependen4
semantically rich objects. Its knowledge source is generally domain dependent, and its
processing is largely model driven.
Note that in the abstract subsystem in Figue 2(b), the spatial processing and n4ated
symbolic processing are completely separated although the meaning of symbolic
processing varies with subsystem. The subsystem’s spatial focus depends on the
processing unit. The subsystem’s symbolic focus is managed by the control unit; this
includes things such as the current hypothesis and the state of the interpretation as well as
what series of events and symbols will need to happen in order to the interpretation to
succeed.
System Components
Precise Line Extraction
As noted before, the lower two layers of the system in Figure 2(a) forms a precise line
extraction and image preprocessing subsystem. The objectives of the subsystem are to fmd
reliable line segments and their thickness.
Traditionally, either the skeleton- or contour-based method has been used in a particular
line extraction system. Skeleton-based methods such as thinning are strong in representing
dominant points, but weak in dealing with various intersections. Contour-based methods
have the advantage of providing diable line thickness information, but m incapable of
dealing with intersections.
Since skeleton- and contour-based methods provide complementary information for
determining a line segment and its thickness, the line extraction subsystem illustrated in
Figure 2(a) uses both methods. The comprehensive extracting strategy can be outlined as
follows:
- Detect the boundary contours of line regions;
- Extract the skeletons of line regions, and generates the connected node graph (CNG) of
the skeleton segments;
- Index the contours and skeletons based on spatial locations;
- Forma data structure describing the contour-skeleton segment correspondence;
- Sort the skeleton segments in decreasing order of segment length;
- Search the sorted skeleton segments and the contour-skeleton data structure for
growing lines.
