Image Processing Reference
In-Depth Information
(a)
(b)
FIGURE 1.3: Topological configurations on the same set of foreground pixels
with (a) (8,4), and (b) (4,8). (See color insert.)
points containing the border, the infinite background component. So, any finite
connected background component is called a hole in 2-D (or a cavity in 3-D).
For the same set of points, how the topological configuration varies on
account of different pairs of adjacency types is shown in Figs. 1.3 (a) and (b),
respectively. In the configuration with (8,4) connectivity, there is only one
component of foreground pixels containing two holes (refer to Fig. 1.3 (a)),
whereas with (4,8) connectivity there are three components, the largest of
them is shown with orange color, and the remaining two with black. There is
no hole in the latter (refer to Fig. 1.3 (b)).
1.3.1 Component Labeling
In various applications, the distinct components in an image must be de-
termines. This computation is called component labeling. A component could
be obtained from a point p by accumulating the set of points connected to it.
This may be achieved by recursively visiting a neighboring point and labeling
the visited point with the component number. The recursion terminates if
there exists no unvisited neighboring point. The algorithm primarily employs
the strategy of the depth first search (DFS) in a graph for obtaining its con-
nected component from a vertex. Though the algorithm runs in linear time
complexity, it requires a large stack size, and because the computing environ-
ment may not permit stack building beyond a certain limit, it is not suitable
to handle large images.
There exists an e
cient computation, which is performed by scanning the
image twice (for 2-D images), namely, the forward scanning (from left to right
and top to bottom) and the reverse scanning (from right to left and bottom to
top). In each scan, a separate mask identifying the adjacent points in the grid
is used. In Figs. 1.4 and 1.5, masks for forward and reverse scans for labeling
connected components in grids (4,8), and (8,4) are shown. In these figures,
