Binary Digital Image Processing

180 BINARY DIGITAL IMAGE PROCESSING

the original foreground label. Dial's procedure is therefore initiated from so and

results in the shortest path spanning tree shown in Figure 6.5(B). The grid graph

is not shown in Figures 6.5(B) and (C) for clarity. All vertices in this tree are

then labelled with the value of the component counter ~ = 1. This counter is

incremented and the vertex scan restarts at vertex S l and vertex s2 is met as

another vertex associated with the original foreground label. The shortest path

search procedure is used again and results in a second spanning tree, based on

the vertices of a separate component (Figure 6.5(C)). At this stage, the rest of

the vertices are scanned and, since all vertices are included in either of the two

spanning trees, their labels have been updated during the tree construction and

the procedure terminates.

Since arc lengths are set to unity, Dial's shortest path search procedure

proves efficient in this case and leads to an overall complexity of

O(W.H)

for

an image of size W x H. It is important to emphasise the fact that, since only

foreground pixels are to be mapped onto vertices in G, after the grid graph

construction (i.e.

O(W.H)

procedure), the complexity of the labelling procedure

does not depend on the form of connected components. Moreover, it is easily

seen that global information such as the number of pixels in a component can

readily be accessed by this approach (see also Section 6.3). By contrast, other

approaches require a final scan for obtaining such information.

6.2 Noise reduction

Binary images considered for analysis generally result from the digitisation

of some continuous images. Similarly, such binary images can be created by

thresholding the grey-level at each pixel in grey scale images. This processing

represents the most basic operation in the class of

segmentation processes.

Global

or local adaptive thresholds can be considered. For an extended account on these

techniques, the reader is referred to the relevant literature (e.g. [62]). Depending

on parameters such as resolution and grey-level threshold, the binary image may

be altered by noise. In this section, noise refers to either black or white pixels

added randomly to the image (i.e. salt and pepper noise) or a group of (black

or white) pixels added to the image. The first type of noise typically arises in

an acquisition process, whereas the second type of noise typically results from

an inaccurate thresholding process.

In both cases, this noise is to be removed from the binary digital image

for accurate analysis. Noise removal is based on the knowledge of the type of

features present in the image. For example, it can be required that all con-

nected components are discrete convex. Different approaches are possible and

are briefly reviewed here. The first approach presented in Section 6.2.1 uses the

concept of discrete masks introduced in Section 5.2.1 to represent local proper-