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*n^2+ε) 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}*n^2+ε) processors for any fixed ε >0.

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

《Full Text》