475 
Digitization Resolution. The size of the sampling grid cells must 
be sufficiently small to preserve the shape of the regions. 
Preservation of Shape. Connected sets in the analog image must be 
topologically equivalent to connected sets in the discrete image. 
However, preservation of topology does not guarantee preservation of 
shape. 
Topological Equivalence. Two sets are topologically equivalent if 
there is a one-to-one mapping between them and the mapping and its 
inverse are continuous. In the discussion to follow, we are concerned 
only with topological properties of discrete images. 
CONNECTIVITY DEFINITIONS 
The manipulation of connected components in raster images above the 
pixel level can be facilitated by a data structure that allows for 
the connectivity of pixels that constitute connected components. To 
enhance the discussion of this data structure, a few definitions are 
necessary. 
Neighbors. Two pixels are direct neighbors (d-neighbors) if they 
each share a side, and are indirect neighbors (i-neighbors) if they 
are adjacent only at a corner. 
An N-neighbor denotes the pixel whose position is marked with N as 
depicted below. There are many existing algorithms that utilize this 
neighborhood numbering convention. 
d-neighbors are those with N even 
i-neighbors are those with N odd 
Connectivity. A set of pixels belonging to property set S are 
connected if for every pair of pixels in S, there is a path between 
them. A path is a sequence of pixels such that Pi-1 is a neighbor 
of pi and pi-1 is a neighbor of pi. The usual convention for bilevel 
images is to use i-connectivity (corner touching allowed) for the 
black intensity and d-connectivity (only side touching) for the white 
intensity. This convention can be extended to color images in which 
the foreground intensity is i-connected and the background intensity 
(all other colors) is d-connected. The d-connectivity requirement 
ensures no ambiguities can exist. 
Simple Path. A path such that no pixel has more than two 
d-neighbors in the path. A closed path is where the first and last 
pixel are identical. 
Contour (i-contour) of a connected set R is the set of all pixels 
in R, which have at least one d-neighbor not in R. 
Interior of a connected set R is the set of all pixels in whose 
d-neighbors are also in R. 
Line is a set of pixels such that all belong to the contour of the 
set. A line is a non-empty set that has an empty set of interior 
pixels.