Two Strategies to Speed up Connected Component LabelingAlgorithms Page: 4 of 23
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
4
de
Wed
~cb~a(a) 8-connected neighborhood (b) Forward scan mask (c) Backward scan mask
Fig. 1. The masks and the neighborhood of pixel e. Notice that all the pixels in the forward and backward scan masks are in
the neighborhood of pixel b.of neighbors visited during scans later in Section
IV.
A. The basic scanning procedure
Given a 2D image stored in a 2D array, the
simplest scanning procedure for performing con-
nected component labeling is to visit each pixel
in turn, and assign a label to each object pixel
that is either a label of its neighbors' or a new
distinct label if its neighbors are all background
pixels. Let I denote the 2D array for an image.
Let I[i, j] = 0 denote a background pixel, and
let I[i, j] = 1 denote an object pixel. We use an
array L with the same size and shape as I for
storing the labels. In our implementation of the
labeling algorithms, we use one array to hold both
I and L. However, for clarity, we will continue to
describe them as two separate arrays. The problem
of connected component labeling is to fill the array
L with (integer) labels so that the neighboring
object pixels have the same label. Note that we have
made an arbitrary choice of denoting a background
pixel by 0 and an object pixel by 1; however, there
are other equally valid choices [11]. For simplicity,
we have also chosen to use integer labels, but it
is possible to use different types of labels as well.
We name the pixel in the scan mask as illustrated
in Fig. 1 as a, b, c, d and e and also use the
same letters in place of their (i, j) coordinates in
the following discussion. With this notation, L[e]
denotes the label of the current pixel being scanned,
and I[b] denotes the pixel value of the neighbor
directly above e in the vertical direction. Let 1 be
an integer variable initialized to 1. The assignment
of a provisional label for e during the first scan can
be expressed as follows:0,
L[e] 1)
min (L[i]),
iE(a,b,c,d) I(i)=1I[e] = 0,
Vi E (a, b, c, d),
I[i] = 0,
otherwise.(1)
The above expression means that L[e] is assigned
0 if I[e] = 0. It is assigned a new label 1, and 1 is
increased by 1, if a, b, c, and d in the scan mask are
all background pixels. Otherwise, it is assigned the
minimum of the provisional labels already assigned
to the scan mask. In later scans, the labels for the
object pixels are modified to be the minimum labels
of their neighboring object pixels, as described by
the following expression (which is the last case of
Equation (1)):
L[e] - min (L[i]),
iE(a,b,c,d)I[i]=1
if I[e] = 1, and Ei E (a, b, c, d) (2)
such that I[i] = 1.
The above formulas can be used for both forward
scan and backward scan. In principle, we can apply
them to any type of scan on any image format. In
a multi-pass algorithm, this basic scanning proce-
dure is repeated until the label array L no longer
changes. After the first scan, the labels may change
because pixels in one connected component could
have been assigned multiple labels. We say that
these labels are equivalent, and we have chosen
arbitrarily to use the smallest label as the repre-
sentative of the equivalent labels. As labels are
discovered to be equivalent during a scan, the pixels
not yet scanned will take on the smaller label.
However, pixels already scanned during this pass
will not change. In general, many scans are required
for converting all equivalent labels to the smallest
one. One successful strategy used for reducing the
number of scans is the use a label connection table
[11], which we briefly describe next.
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Wu, Kesheng; Otoo, Ekow & Suzuki, Kenji. Two Strategies to Speed up Connected Component LabelingAlgorithms, article, November 13, 2005; Berkeley, California. (https://digital.library.unt.edu/ark:/67531/metadc896659/m1/4/: accessed April 26, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.