A run-length based connected component algorithm for FPGA implementation

Abstract

This paper introduces a real-time connected component labelling algorithm designed for field programmable gate array (FPGA) implementation. The algorithm run-length encodes the image, and performs connected component analysis on this representation. The run-length encoding, together with other parts of the algorithm, is performed in parallel; sequential operations are minimized as the number of runs are typically less than the number of pixels. The architecture is designed mainly on Block RAM (i.e. internal RAM) of the FPGA. A comparison with the multi-pass algorithm in hardware and software is presented to show the advantages of the algorithm. The algorithm runs comfortably in real-time with reasonably low resource utilization, making integration with other real-time algorithms feasible.