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.