In this paper based on the advantages of both optical transmission and electronic computation, we first provide an O(log log N) bus cycles parallel algorithm for the medial axis transform of an N/spl times/N binary image on a linear array with a reconfigurable pipelined bus system using N/sup 2/ processors. By increasing the number of processors, the proposed algorithm can be modified to run in O(log log/sub q/ N) and O(1) bus cycles using qN/sup 2/ and N/sup 2+1//spl isin// processors respectively, where 1/spl les/q/spl les//spl radic/N, /spl isin/ is a constant and /spl isin//spl ges/1. These results improve on previously known algorithms developed on various parallel computation models. Key Words: Medial axis transform, image processing, image compression, computer vision, parallel algorithms, linear array with a reconfigurable pipelined bus system.

The computation model on which the algorithms are developed is the reconfigurable array of processors with wider bus networks (abbreviated to RAPWBN). The main difference between the RAPWBN model and other existing reconfigurable parallel processing systems is that the bus width of each network is bounded within the range [2,[/spl radic/(N)]]. Such a strategy not only saves the silicon area of the chip as well as increases the computational power enormously, but the strategy also allows the execution speed of the proposed algorithms to be tuned by the bus bandwidth. To demonstrate the computational power of the RAPWBN, the channel-assignment problem is derived in this paper. For the channel-assignment problem with N pairs of components, we first design an O(T + [N//spl omega/]) time parallel algorithm using 2N processors with a 2N-row by 2N-column bus network, where the bus width of each bus network is /spl omega/-bit for 2 /spl les/ /spl omega/ /spl les/ [/spl radic/N] and T = [log/sub /spl omega//N] + 1. By tuning the bus bandwidth to the natural log N-bit and the extended N/sup 1/c/-bit (N/sup 1/c/ > log N) for any constant c and c /spl ges/ 1, two more results which run in O(log N/log log N) and O(1) time, respectively, are also derived. When compared to the algorithms proposed by Olariu et al. [17] and Lin [14], it is shown that our algorithm runs in the equivalent time complexity while significantly reducing the number of processors to O(N).

Computing the moments of a two-dimensional (2-D) image involves a significant amount of multiplications and additions in a direct method. In this paper, we use the suffix sums to compute the 2-D moments instead of using a direct method. This method can reduce the number of multiplications tremendously. By integrating the advantages of both optical transmission and electronic computation, the 2-D moments can be computed in constant time on a 2-D arrays with reconfigurable optical buses (AROB). This result achieves optimal speed-up.

Thresholding is the most commonly used technique in image segmentation. We first propose an efficient sequential algorithm to improve the relative entropy-based thresholding technique. This algorithm combines the concepts of the relative entropy with that of the local entropy and also includes the quadtree hierarchical structure in it. Second, we derive a constant time parallel algorithm to solve this problem on the reconfigurable array of processors with wider bus networks (RAPWBN). The system bus bandwidth determines the capacity of data communication between processors. According to the results as shown by Li and Maresca (1989) and by Maresca and Li (1989), we know that the silicon area used by the switching control mechanism is far less than that used by the processor. Instead of increasing the number of processors, we extend the number of buses to increase the power of a parallel processing system. Such a strategy of utilizing the reconfigurable array of processors with wider bus networks not only has the advantage of saving silicon area but also increases the system power enormously. So, we use the RAPWBN to solve the entropy-based thresholding problem.

Clustering techniques are usually used in pattern recognition, image segmentation and object detection. For N patterns and k centers each with M features, in this paper, we first design an O(kM) time optimal parallel algorithm for one pass process of clustering with the k-means method on a linear array of processors with a wider bus network using N/sup 1+1/c/ processors with one bus network, where c is any constant and c/spl ges/1. Then, based on the proposed algorithm, two O(k) and O(1) time optimal parallel clustering algorithms are also derived using MN/sup 1+1/c/ and kMN/sup 1+1/c/ processors with M row and MN row bus networks, respectively. These results improve the best known bounds and achieve cost optimal in their time and processor complexities.

The parallel computation model upon which the proposed algorithms are based is the hyper-bus broadcast network. The hyper-bus broadcast network consists of processors which are connected by global buses only. Based on such an improved architecture, we first design two O(1) time basic operations for finding the maximum and minimum of N numbers each of size O(log N)-bit and computing the matrix multiplication operation of two N/spl times/N matrices, respectively. Then, based on these two basic operations, three of the most important instances in the algebraic path problem, the connectivity problem, and several related problems are all solved in O(log N) time. These include the all-pair shortest paths, the minimum-weight spanning tree, the transitive closure, the connected component, the biconnected component, the articulation point, and the bridge problems, either in an undirected or a directed graph, respectively.

A cross-bridge reconfigurable array of processors is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm. Based on this architecture, several O(1) time basic operations such as the transpose, the untranspose, the shift, the unshift and the prefix sum of a binary sequence are first proposed. Then, these basic operations can be used to find the kth smallest element of N m bits unsigned integers in O(m) time using N processors and to sort N data items in O(1) time using O(N/sup 5/3/) processors instead of using O(N/sup 2/) processors as those proposed by other researchers.>

A reconfigurable array of processors (RAP) is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm.