A linked list run-length-based single-pass connected component analysis for real-time embedded hardware

• Published in: Journal of real-time image processing 2018-06, Vol.15 (1), p.197-215
• Main Authors: Tang, Jia Wei, Shaikh-Husin, Nasir, Sheikh, Usman Ullah, Marsono, M. N.
• Format: Article
• Language: English
• Subjects: Algorithms; Blanking; Computer Graphics; Computer Science; Embedded systems; Equivalence; Hardware; Image Processing and Computer Vision; Labeling; Labels; Multimedia Information Systems; Pattern Recognition; Pixels; Raster scanning; Real time; Recycling programs; Signal,Image and Speech Processing; Special Issue Paper
• ISSN: 1861-8200; 1861-8219
• DOI: 10.1007/s11554-016-0590-2

Conventional connected component analysis (CCA) algorithms render a slow performance in real-time embedded applications due to multiple passes to resolve label equivalences. As this fundamental task becomes crucial for stream processing, single-pass algorithms were introduced to enable a stream-oriented hardware design. However, most single-pass CCA algorithms in the literature inhibit maximum streaming throughput as additional time such as horizontal blanking period is required to resolve label equivalence. This paper proposes a novel single-pass CCA algorithm, using a combination of linked list and run-length-based techniques to label and resolve equivalences as well as extracting the object features in a single raster scan. The proposed algorithm involves a label recycling scheme which attains low memory requirement design. Experimental results show the implementation of the proposed CCA achieves one cycle per pixel throughput and surpasses the most memory-efficient state-of-the-art work up to 25 % reduction in memory usage for 7680 × 4320  pixels image.