Parallel Execution of a Connected Component Labeling Operation on a Linear Array Architecture

Abstract

This work presents a novel parallel algorithm and architecture for finding connected components in an image. Simulation results indicate that the proposed algorithm has an execution time of N 2 +6N-4 cycles for an N×N image using an architecture containing 4 parallel processors. The proposed hardware can process a 128 × 128 image in 0.8574 ms and uses only 4 processors, compared to 0.85 ms and 128 processors for the work of Ranganathan et al. [14], and 94.6 ms and 16384 processors for the MPP [22]. Among the advantages of the novel architecture are modularity, expandability, regular data flow, and simple hardware. These properties are extremely desirable for VLSI implementations. Additionally, the execution time of the algorithm is independent of its image content; thus, it is quite flexible.