Rule-Based graphics recognition on unconstrained maps
The number of rules in the knowledge source associated with this subsystem is limited.
The subsystem is heavy in procedural computations, and relatively light in rule-based
operations. These rules are mainly designed to direct search mechanisms, modifj
constraints, handle ambiguous situations and dynamically control the spatial data query.
Graphics Recognition
The objective of the graphics recognition subsystem is to find various graphical shapes
based on the extracted primitive vectors and the available knowledge about object models.
Very ofkm, procedural computing methods are employed to directly find straight lines,
circles and ellipses. However, these methods are incapable of finding complex graphics
such as dashed lines, chained lines, hatching regions, and polygonal shapes.
The graphics recognition strategy can be outlined as follows:
- Extract the reliable primitive vectors;
- Index the primitive vectors based their endpoint locations;
- Direct the vector analysis layer to find connected or adjacent neighbors;
- Interpret the returned symbolic results;
- Alter the graphical description of a shape or its construct type;
- Invert search directions or terminate the seamh if necessary;
- Persist valid graphical shape descriptions as they are classified.
The number of rules in the knowledge source associated with this subsystem depends of
the complexity of the object models and the number of objects to be ~cognized. The
subsystem is heavy in both model- and data-driven processing. The rules in the
corresponding knowledge source encode object models, manage administrative tasks,
direct search operations and resolve ambiguities.
Efficient SDatial Querv
The spatial query method is an important component used by every subsystem in Figure
2(a). The conversion system must manipulate, store, retrieve and analyze a set of
geographical data over a two-or tlueedimensional map. The spatial query component of
the system is designed to provide an optimum processing tool for these geometric
operations.
Fast pruning techniques have been popular in GIS image processing and recognition. In
practice, a system relying on these pruning techniques without using objects’ spatial
properties can easily reach its speed bottleneck, especially in processing large data sets
distributed over a wide geographical area. Consequently, a spatial indexing mechanism is
essential.
The spatial query method for the system in Figme 2(a) is an extended kd-tree which
extends the original point indexing structme to a k-dimensional indexing structure. It is
efficient for manipulating both point objects and area objects in multidimensional space as
it avoids object duplication and object mapping.
The basic queries supported by this method include point query, intersection query and
containment query. Dynamic and static index construction and spatial primitive operations
are also supported.
The spatial entities indexed in the various subsystems in Figure 2(a) can be outlined below:
- In the line extraction level, pixel objects, nodes and line segments
- Direct the graphics ~ognition level, line segments and primitive graphical shapes
- In the domain object reasoning level, primitive graphical shapes, textual labels and
semantic objects
Figure 2 System’s architecture (a) and an abstract subsystem (b)
Subsystems such as those found in Figure 2(a) have two possible working models when
integrated with the spatial query component (Figure 3). In each model, the inputs can be
raster images, primitive vectors, primitive graphics and/or intelligent dam, the Conversion
Subsystem can be any one of the three subsystems in Figure 2(a); and the outputs
generated are dependent on the subsystem being used. Moreover, the conversion
subsystem relies on the spatial query component to do dynamic and static index
construction, index updating and query operations. The Access Manager in Figure 3(b) is
employed to enswe the consistency of the spatial indices whenever an external database is
used.
Figure 3 Two working models with spatial query component
Conclusions
A graphics recognition methodology that works el%ciently for very complicated and
degraded maps has been presented in this paper. Firs4 map object layers and knowledge
domain dependency in the conversion system were discussed. Next, the system
architecture and the three subsysterrw derived from the overall system were described.
Major components closely related to graphics recognition-such as line extraction and
spatial object query-were also discussed. The system’s advantages due to better use of
contour and skeleton information, modularized knowledge bases, integration of model- and
data-driven processing, and employment of spatial indexing mechanism for fast data
access were identified.
References
- Hori, O., and Tanigaw% S., July, 1994, Line Fitting Method for Line Drawings Based on
Contours and Skeletons: IEICE Trans. Inf. & Syst., Vol. E77-D, No. 7.
- Kasturi, R., Raman, R., Chennubhotl~ C., and O’German, L., 1990, Document Image
Analysis: An Overview of Techniques for Graphics Recognition: Proc. SSPR90, pp. 192-
230.
- Lu, W., Ohsaw% Y,, Sakauchi, M., 1988, A Database Capture System for Mechanical
Drawings Using an Efficient Multi-dimensional Graphical Data Structure: Proc. 9* ICPR,
pp. 266-269.
- Mayer, H., Heipke, C., and Maderlechner, G., 1992, Knowledge-based Interpretation of
Scanned Large-scale Maps Using Multi-level Modelling: IAPRS (29), B3/111,pp. 578-585.
- Pridmore, T. P., and Jiseph, S. H., 1991, Using Schemmmata to Interpret Images of
Mechanical Engineering Drawings: Proc: 9th ECAI, pp. 515-521.
