organized by
International Association
for Pattern Recognition
The
University of
Udine |
Andrea Bulgarelli, Luigi Di Stefano (University
of Bologna), "A Simple And Efficient Connected Component
Labeling Algorithm", ICIAP '99, 10th International
Conference on Image Analysis and Processing, September 27-29,
1999, Venice, Italy
We describe a sequential,
two-scan algorithm for labeling connected components in binary
images in raster format. With the classical two-scan approach
equivalences between temporary labels
are registered during the first scan and then, after completion
of the scan, sorted out into
equivalence classes. Instead, the proposed algorithm processes
equivalences during the first scan
by merging equivalence classes as soon as a new equivalence is found.
We show that this significantly
improves the efficiency of the labeling process with respect to
the classical approach. In the proposed algorithm the
data-structure used to support the handling of equivalences is a
simple 1D-array, which allows finding class identifies from
labels as well as merging equivalence classes. This data-structure
renders the more frequent operation of finding class identifiers
very fast, while the less-frequent class-merging operation has a
relatively high computational cost.
|
