Digital Topology: Fundamentals - Digital Geometry in Image Processing - page 4

voxel is 6 adjacent of v, if its coordinate differs from v by 1 at only one of the
dimensions. It is 18 -adjacent when it is 6 adjacent or the ordinal values in two
of its coordinate dimensions differ by 1, and it is 26 adjacent, when it is 18
adjacent or all the coordinate values differ by 1 from v. They are also called 6,
18, and 26 neighbors of v, respectively. Let us denote the set of neighbors of a
point p in a digital grid as either N(p) in general or N k (p), where k ∈{4,8}
in 2-D and k ∈{6,18,26} in 3-D, to denote a specific type of neighbor.
A binary image in n-D is defined as a function I such that I : G n →
{0,1}. Let us call the grid points with the value 1 as the object or foreground
points, and points with the value 0 the background points. In particular in 2-D
we denote the image P : G 2 → {0,1}, partitioned into its foreground and
background pixels. In 3-D we represent it as V : G 3 →{0,1}. Let us assume
that the border of G n always contains background (0) points.
Using the adjacency relationship, we define a few properties of a set of
grid points from [177], and [118] as follows: A path between two points a
and b in a digital grid is k-adjacent if there exists a sequence of points p 0 (=
a),p 1 ,p 2 ,...,p l (= b), l ≥ 1, such that every two consecutive points p i ,p i+1 ,
0 ≤ i ≤ l − 1 are k-adjacent. Two sets of points S 1 and S 2 are k-connected,
if there exists a pair of points p ∈ S 1 , and q ∈ S 2 , such that p and q are
k-adjacent. A set of grid points S is k-connected, if it cannot be partitioned
into two subsets that are not k-adjacent to each other. A k-component of a set
of grid points S is a non-empty k-connected subset of S that is not k-adjacent
to any other point in S.
1.2.1 Jordan's Theorem on Closed Curves
Let us discuss how Jordan's theorem for a simple closed curve in the Eu-
clidean plane gets extended in a digital grid. The theorem states that [118],
the simple closed curve separates the remainder of the plane into two con-
nected components, one of which is called inside and the other is denoted as
the outside of the curve. It implies that removal of any point from the curve
would make the remainder of the plane connected.
Let us define a curve in a digital grid using the notion of adjacency rela-
tionship between a pair of neighboring points. A path in S is called a simple
arc if all but two of its points (its end points) have exactly two neighbors in
S, while those two end points have exactly one, and a simple closed curve is
a path in S when all its points have exactly two neighbors in S. In a 2-D
digital grid too, a simple closed curve (with foreground pixels) partitions the
remaining background into two connected components. Hence, Jordan's theo-
rem is equally applicable here. However, the definitions of connectivity differ
for the background and foreground pixels in this case. This we elaborate with
the help of an example as shown in Fig. 1.2.
Consider a background pixel (white pixel) p enclosed by four foreground
pixels, which form a curve if they are 8-adjacent. However, the number of
8-connected components of background is also 1, which includes the point p