CHAPTER 1: DIGITAL TOPOLOGY 3
Remark 1.1:
At this stage, digital images are studied as set of discrete points. However, the
problem of mapping a continuous image onto a binary digital image will be studied
in depth in Chapter ~.
From now on, the binary image is represented by a set of discrete points lying
on a regular lattice. With each point is associated a 0-1 value which indicates
the colour of its corresponding (white or black) pixel. We lay down a theoretical
context for the study of digital image processing operators by first defining a
topology on this set of points. At this stage, the lattice is considered as infinite
(rather than finite) in order to avoid dealing with specific cases that arise close
to the border of a finite lattice.
1.2 Neighbourhoods
It is commonly known that the discrete topology defined by pure mathe-
matics cannot be used for digital image processing since in its definition every
discrete point (i.e. a pixel in the image processing context) is seen as an open
set. Using this definition, a discrete operator would only consider the image as
a set of disjoint pixels, whereas in image processing, the information contained
in the image is stored in the underlying pixel structure and the neighbourhood
relations between pixels.
Alternative definitions have been proposed. In contrast with classic dis-
crete topology, digital image processing is based on digital topology [21, 64, 138].
The definition for digital topology is based on a neighbourhood for every point.
Neighbourhoods in digital topology are typically defined by referring to
the partition dual to the lattice considered. For a given point, defining its neigh-
bouring points is equivalent to defining a relationship between the corresponding
pixel areas in the partition. The simplest instance is when the neighbours of a
pixel are defined as the pixels whose areas share a common edge with the pixel
area in question (direct neighbours). Extensions for this principle are also con-
sidered. In this section, the three possible regular lattices (triangular, hexagonal
and square) are investigated. For each case, commonly used neighbourhoods are
presented. Section 1.3 completes these definitions by deriving properties on the
neighbourhoods.
1.2.1 Triangular lattices
In the particular case of a triangular lattice, the neighbours of a point are
defined as the six direct neighbours of this point on the lattice. By duality, it
is equivalent to consider neighbouring (hexagonal) pixel areas as the ones which
have a common edge with the pixel area in question. This neighbourhood is
4 BINARY DIGITAL IMAGE PROCESSING
referred to as 6-neighbourhood on the triangular lattice. The notation N6(p)
will be used for the 6-neighbourhood of point p. In Figure 1.3, the point p is
linked to its 6-neighbours by bold lines. The triangular lattice is represented
with thin lines. The dotted lines show the pixel areas dual to the triangular
lattice.
....
Figure 1.3 N6(p): 6-neighbourhood of the point p on the triangular lattice
1.2.2 Hexagonal lattices
A similar definition to the one above for the hexagonal lattice leads to
the 3-neighbours of p on the hexagonal lattice (see Figure 1.4(A)). However, in
Section 1.3, it will be shown that this neighbourhood is too coarse to satisfy basic
properties in digital topology. Therefore, we extend this to the 12-neighbourhood
as follows.
The 3-neighbours of a point p are defined as the points which are associated
with the pixel areas that share a common edge (i.e. a one-dimensional object)
with the pixel area in question. Following this principle, nine extra neighbours
can be defined as the pixel areas that share a common corner (i.e. a zero-
dimensional object) with the central pixel area (indirect neighbours). Combining,
we obtain the 12-neighbourhood of the point p. By analogy with the previous
section, N3(p) and N~2(p) will denote the 3- and 12-neighbourhoods of a point
p, respectively.
Figure 1.4(B) illustrates the 12-neighbourhood of the point p. The (trian-
gular) partition is also shown as dotted lines to illustrate relations between the
corresponding pixel areas.
Remark
1.2:
In contrast to the 3- and 12-neighbourhoods, we can note that the 6-neighbourhood
defined in the Section 1.2.1 readily contains such an extension. In other words,
on triangular lattices, there is no possible definition for indirect neighbours. Fig-
ure 1.3 shows that all the possible connections between the central hexagonal area
and its neighbours are exploited.

Get Binary Digital Image Processing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.