"Optimizing Connected Component Labeling Algorithms"
Kesheng Wu, Ekow Otoo and Arie Shoshani
Lawrence Berkeley National Laboratory, Berkeley, CA, USA

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 labeling algorithms use a scanning step that examines some of its neighbors. The first strategy exploits the dependencies among the neighbors 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 based 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.

Keywords: Connected component labeling, Union-Find, optimization

Posted by helloktk

댓글을 달아 주세요