Lawrence Berkeley National Laboratory

This paper presents two new strategies to speed up connected component labeling algorithms. The first strategy employs a decision treeto minimize the work performed in the scanning phase of connected component labeling algorithms. The second strategy uses a simplified union-find data structure to represent the equivalence information among the labels. For 8-connected components in atwo-dimensional (2D) image, the first strategy reduces the number of neighboring pixels visited from 4 to7/3 on average. In various tests, using a decision tree decreases the scanning time by a factor of about 2. The second strategy uses a compact representation of the union-find data structure. This strategy significantly speeds up the labeling algorithms. We prove analytically that a labeling algorithm with our simplified union-find structure has the same optimal theoretical time complexity as do the best labeling algorithms. By extensive experimental measurements, we confirm the expected performance characteristics of the new labeling algorithms and demonstrate that they are faster than other optimal labeling algorithms.