Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol.19 No.2, pp.353-370 (March 2003)

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

Kuang-Bor Wang, Tsorng-Lin Chia*, Zen Chen+ and Der-Chyuan Lou
Department of Electrical Engineering
Chung Cheng Institute of Technology
Taoyuan, 335 Taiwan
*Department of Information Management
Ming Chuan University
Taoyuan, 333 Taiwan
+Institute of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, 300 Taiwan

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 N2+6N-4 cycles for an NXN image using an architecture containing 4 parallel processors. The proposed hardware can process a 128 X 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.

Keywords: connected component labeling, parallel algorithm, parallel processing, linear array, processing element

Full Text () Retrieve PDF document (200303_08.pdf)

Received June 1, 2001; revised December 24, 2001; accepted February 1, 2002.
Communicated by Kuo-Chin Fan.