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

Yang Yang, Dapeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)459-472
Number of pages14
JournalImage and Vision Computing
Issue number5
Publication statusPublished - 1 May 2003


  • Connected components labeling
  • Connectivity
  • Image processing
  • One-pass
  • Parallel processing

ASJC Scopus subject areas

  • Signal Processing
  • Computer Vision and Pattern Recognition


Dive into the research topics of 'A novel line scan clustering algorithm for identifying connected components in digital images'. Together they form a unique fingerprint.

Cite this