CONSTANT-TIME HOUGH TRANSFORM ON THE PROCESSOR ARRAYS WITH RECONFIGURABLE BUS SYSTEMS

We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a computation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS 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 it several times. We can think it as a ''hardware subroutine''. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study: 1) The sum of n bits can be computed in O(1) times on a BARBS with O(n(1+epsilon)) processors for any fixed epsilon > O. 2) The weights of each simple path of an n * n image can be computed in O(1) time on a 3-D PARBS with O(n(2+epsilon)) processors for any fixed epsilon > O. 3) The p angle Hough transform of an n*n image can be computed in O(1) time on a PARBS with O(p*n(2+epsilon)) processors for any fixed epsilon > O with p copies of the image pretiled. 4) The p angle Hough transform of an n*n image can be computed in O(1) time on a BARBS with O(p*n(3)) processors. AMS Subject Classifications: 68U07, 68Q22