This paper presents two new strategies that can be used to greatly
improve the speed of connected component labeling algorithms. To assign
a label to a new object, most connected component labeling algorithms
use a scanning step that examines some of its neighbors. The first
strategy exploits the dependencies among them to reduce the number of
neighbors examined. When considering 8-connected components in a 2D
image, this can reduce the number of neighbors examined from four to one
in many cases. The second strategy uses an array to store the
equivalence information among the labels. This replaces the pointer
based rooted trees used to store the same equivalence information. It
reduces the memory required and also produces consecutive final labels.
Using an array instead of the pointer based rooted trees speeds up the
connected component labeling algorithms by a factor of 5 ~ 100 in
our tests on random binary images.© (2005) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.