Journal directory listing - Volume 31-41 (1986-1996) - Volume 40 (1995)
Directory

Constant-Time Algorithms for the Area and Perimeter of Image Components on Processor Arrays with Reconfigurable Bus Systems
Author: Shun-Shii Lin(Department of Information and Computer Education, National Taiwan Normal University)

Abstract:

In this paper, we present O(l) time algorithms to determine the area and the perimeter of each component of an n*n image. This problem has not been solved in O(l) time before, even in the idealistic CRCW PRAM model. For large-sized problems, it is desirable to have fast hardware solutions. Our algorithms are based on the proces-sor arrays with a reconfigurable bus system (abbreviated as PARBS) that consists of a processor array and a reconfigurable bus system. In order to solve this problem with constant time complexity, we first propose the concept of iterative-PARBS [13], which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through itself several times. We can think of it as a "hardware subroutine". Based on this novel scheme, we are able to explore constant-time parallel algorithms on PARBS. The fol-lowing new results are derived in this study:
(1)The area of each component of an n*n image with p components can be computed in O(l) time on a PARBS with O(p*n2+ε) processors for any fixed ε >0.
(2)The perimeter of each component of an n*n image with p components can be com-puted in O(l) time on a PARBS with O(max{n,p}*n2+ε) processors for any fixed ε >0.

Keywords:Area and perimeter of image components, computation model, image processing, parallel processing, reconfigurable bus system

《Full Text》