which facilitate interactive manipulation and editing of cartographic 
raster data. These data structures and techniques will serve as an 
interface between multicolor raster scanned map data and the feature 
oriented manipulations normally found in a cartographic compilation 
and revision system. The goal of our effort is to provide an 
enhanced raster editing capability without incurring the overhead of 
raster to vector processing or being limited to current raster editing 
techniques based on individual pixel or color manipulations. 
In order to achieve this goal it was necessary to acquire a knowledge 
base of raster data to have a solid foundation upon which to develop 
data structures and manipulation algorithms. In doing this, we 
investigated past Department of Defense cartographic research programs 
and extended our research into several disciplines including pattern 
recognition, image processing, scene analysis, and pictorial data 
bases. The research team performed a data structure survey which 
focused upon the central three levels of spatial data organization; 
information structures, data structures, and storage structures. At 
the information structure level, the spatial properties of cartographic 
objects can be described as either attributes or relationships 
(Nyerges, 1980). Those spatial relationships which are of primary 
concern to this study are commonly referred to as topologic properties. 
Topology is the study of the properties of shapes which remain 
invariant under rubber-sheet transformations. A topological trans 
formation exists when there is one-to-one correspondence between 
points in one image and points in another image; and when open sets 
in one image correspond to open sets in the other. The open sets 
are then said to be topologically equivalent. Properties of an image 
which remain unaffected by spatial warpings include: adjacency, 
connectivity, component parts, holes, boundaries, and neighbors. 
Of these properties, the one we will most fully explore is that of 
connectivity among pixels. A set of pixels is connected if any 
two pixels in the set can be joined by a path. A figure without 
disjointed parts which is joined by a path is termed a connected 
component. The computation of connected components and the labeling 
of these components are necessary steps prior to any other carto 
graphic manipulations. Algorithms for calculating connected com 
ponents and assigning unique label numbers are given by (Milgram, 1979), 
(Rosenfeld and Pfaltz, 1966), and (Rosenfeld,1970). 
TOPOLOGY OF DISCRETE IMAGES 
The issue of connectivity is subject to topological uncertainties in 
the raster domain. True topological equivalency may not be possible 
in comparison between analog and discrete images. Pavlidis introduced 
the definition of analog image and sampling grid compatibility, which 
implies the preservation of topology. Pavlidis offers the following 
definitions to introduce the notion of topological compatibility 
between analog images and discrete images.