Orthogonal access architectures and reduced meshes for parallel image computations

A class of orthogonal-access parallel organizations is studied for applications in image and vision analysis. These architectures consist of a massive memory and a reduced number of processors which access the shared memory. The memory can be envisaged as an array of memory modules in the k-dimensional space, with each row of modules along a certain dimension connected to one bus. Each processor has access to one bus along each dimension. It is shown that these organizations are communication-efficient and can provide processor-time optimal solutions to a wide class of image and vision problems. In the two-dimensional case, the basic organization has n processors and an n × n memory array which can hold an n × n image, and it provides O(n) time solution to several image computations including: histograming, histogram equalization, computing connected components, convexity problems, and computing distances. Such problems also take O(n) time on a two-dimensional mesh with n² processors. For the general k-dimensional case, a class of orthogonal data movement operations can be implemented on such organizations to yield processor-time optimal image and vision algorithms.