8
Computer Vision: Mar 2000
the image while doing so. Other algorithms were designed for larger images that may not t
in memory and work on only tworows of the image at a time. Still other algorithms were de-
signed for massively parallel machines and use a parallel propagation strategy.We will lo ok
at two dierent algorithms in this chapter: the recursive search algorithm and a row-by-row
algorithm that uses a special union-nd data structure to keep track of components.
A Recursive Lab eling Algorithm
Suppose that
B
is a binary image with
M axRow
+1 rows and
M axC ol
+ 1 columns. We
wish to nd the connected components of the 1-pixels and produce a labeled output image
LB
in whichevery pixel is assigned the lab el of its connected comp onent. The strategy,
adapted from the Tanimoto AI text, is to rst negate the binary image, so that all the 1-pixels
become -1's. This is needed to distinguish unpro cessed pixels (-1) from those of component
label 1. We will accomplish this with a function called
negate
that inputs the binary image
B
and outputs the negated image
LB
, which will become the labeled image. Then the process
of nding the connected components becomes one of nding a pixel whose value is -1 in LB,
assigning it a new lab el, and calling procedure
search
to nd its neighbors that havevalue -1
and recursively repeat the pro cess for these neighbors. The utility function
neighbors(L,P)
is given a pixel position dened by L and P. It returns the set of pixel positions of all of its
neighbors, using either the 4-neighborhoo d or 8-neighborho od denition. Only neighbors
that represent legal p ositions on the binary image are returned. The neighbors are returned
in scan-line order as shown in Figure 3.7. The recursive connected components labeling
algorithm is a set of six procedures, including
negate
,
print
, and
neighbors
, which are left
for the reader to co de.
1
2 * 3
4
1 2 3
4 * 5
6 7 8
a) four-neighborhood b) eight-neighborhood
Figure 3.7: Scan-line order for returning the neighbors of a pixel.
Figure 3.8 illustrates the application of the recursive connected components algorithm
to the rst (top leftmost) comp onent of the binary image of Figure 3.6.
ARow-by-Row Labeling Algorithm
The classical algorithm, deemed so because it is based on the classical connected components
algorithm for graphs, was described in Rosenfeld and Pfaltz (1966). The algorithm makes
two passes over the image: one pass to record equivalences and assign temp orary labels and
the second to replace each temporary label by the lab el of its equivalence class. In between
the two passes, the recorded set of equivalences, stored as a binary relation, is processed to
determine the equivalence classes of the relation. Since that time, the
union-nd
algorithm,
which dynamically constructs the equivalence classes as the equivalences are found, has been
widely used in computer science applications. The union-nd data structure allows ecient
construction and manipulation of equivalence classes represented by tree structures. The
addition of this data structure is a useful improvement to the classical algorithm.