Image Processing Reference
In-Depth Information
p
p
(a)
(b)
FIGURE 1.4: Masks for 4-connected component labeling: (a) during forward
scan, and (b) during reverse scan.
the neighboring points, which are to be checked for labeling are shown with
shaded boxes around the point p. Using these masks the labels of the visited
neighbors for a foreground point, if any, are checked and decisions are taken
as follows:
1. If none of the visited neighbors is a foreground point, and if the point is
unlabeled, a unique label (a non-zero positive integer value) is assigned
to p.
2. The distinct labels of its visited neighbors (including the point itself)
are declared as equivalent, and the minimum of them is assigned to the
point. In a subsequent scan, all equivalent labels are renumbered with
the minimum of the set.
At the end of the two scans, a candidate label is chosen from each equivalent
set of labels, and each component of the image gets a unique identification
label. A similar algorithm exists in 3-D.
1.3.2 Containment
Let us define the property of containment between two sets of points in a
digital picture. Let X and Y be two sets of points in (U,m,n,S), such that
X is connected. In that case, X surrounds Y , if each point in Y is contained
in a finite component of U −X. The relation is described as X surrounds Y .
It is an asymmetric and transitive relation, and it induces a partial order on
the connected subsets of U. In a finite digital picture, the infinite background
component surrounds the set of all foreground points. Consider an example
as shown in Fig. 1.6. The black pixels belong to the foreground, whereas
the white pixels belong to the background. Let us consider a set of pixels
(colored orange in the figure). This set is surrounded by the connected set of
foreground pixels. We should note that in this example the corresponding pair
of adjacency types is given by (8,4).
