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-

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.