Image Processing Reference
In-Depth Information
the geometry in this space is called digital geometry. However, we should note
that this geometry is not unique. In different ways, digital geometry may be
defined depending upon the neighborhood definition of a point in the space.
Digital images from different imaging technologies such as CT Scan, MRI,
PET, etc. are also available in 3-D integral coordinate space. Hence, it is also
necessary to understand the geometry in such a 3-D space. This topic addresses
several aspects of digital geometry, such as different metric spaces and shapes
of hyperspheres in those spaces, analysis of discrete curves, straight lines and
surfaces, Medial Axis Transform (MAT), etc. It also discusses how these con-
cepts are used in developing image processing algorithms. In this chapter, we
provide a brief introduction to digital topology and related concepts. This will
help a beginner to understand the subject matter in subsequent chapters.
In digital topology, we study the topological properties in a digital space.
In particular, we study these properties with respect to relationships among
the pixels, and voxels of binary images in 2-D and 3-D, respectively. Several
image processing operations, such as connected component labeling, contour
following, thinning, etc., are defined using the concepts of digital topology.
Various models, such as graph theoretic modeling [177], abstract cellular com-
plex [121], etc., are proposed in studying the topology in a discrete space. In
this text, we restrict our discussion to the topology modeled by a graphical
representation over a rectangular lattice (or grid) in Euclidean space.
1.1 Tessellation of a Continuous Space
A tessellation is an aggregate of cells that covers the continuous space
without overlapping. The dimension of each unit cell is the same as that of
the space. A tessellation provides the digitization of space, so that each cell
is represented by a unique tuple of integers. Usually, a cell in a tessellation is
restricted to be a convex set, and there is a homogeneity in the occurrences
of cells of identical shapes. For example, in a 2-D plane, every vertex of a
homogeneous tessellation shares r regular polygons of sides a
1
, a
2
, ..., a
r
. Such
a tessellation is denoted by the crystallographic set {a
1
,a
2
,...,a
r
}. There are
only 11 different homogeneous tessellations of the plane, called Archimedean
Tilings. In only three, all the cells are uniform. We refer to them as regular
tessellations. They are shown in Fig. 1.1, namely triangular (Fig. 1.1(a)),
rectangular (Fig. 1.1(b)), and hexagonal tessellations (Fig. 1.1(b)).
Similarly, in 3-D we define a regular tessellation, in which the space is par-
titioned by a regular polyhedron. However, in contrast to 2-D, there is only
one type of regular tessellation in 3-D, which is composed of cubic cells, a
three-dimensional form of rectangular tessellation. In higher dimensions too,
rectangular tessellations are regular. In fact, except in 4-D, in all other di-
mensions rectangular tessellation is the only form of regular tessellation. In
