A novel line scan clustering algorithm for identifying connected components in digital images

In this paper, the Line-Scan Clustering (LSC) algorithm, a novel one-pass algorithm for labeling arbitrarily connected components is presented. In currently available connected components labeling approaches, only 4 or 8 connected components can be labeled. We overcome this limitation by introducing the new notion n-ED-neighbors. In designing the algorithm, we fully considered the particular properties of a connected component in an image and employed two data structures, the LSC algorithm turns to be highly efficient. On top of this, it has three more favorable features. First, as its capability to be processed block by block means that it is suitable for parallel processing, improving the speed when multiple processors are used. Second, its applicability is extended from working on binary images only to directly work on gray images, implying an efficiency gain in time spent on image binarization. Moreover, the LSC algorithm provides a more convenient way to employ the labeling result for conducting processing in later stages. Finally we compare LSC with an efficient connected labeling algorithm that is recently published, demonstrating how the LSC algorithm is faster. (C) 2003 Elsevier Science B.V. All rights reserved.