Optimal Image Computations on Reduced VLSI Architectures

We consider a communication-efficient parallel organization with a reduced number of processors for problems in image processing and computer vision. The organization consists of n processors having row and column access to an n X n array of memory modules which stores an n X n image. It can be looked upon as a reduced Mesh-of-Trees organization in which the n2 leaf processors are replaced by n2 memory locations and each row (column) tree is replaced by a single processor with a row (column) bus. The class of image problems considered here requires dense data movement as well as global operations on image pixels. Examples include histogramming, image labeling, computing convexity and nearest neighbors. It is shown that while such problems can be solved in O(n) time on a twodimensional mesh-connected computer (2MCQ) with n2 processors, they can be also solved on the proposed organization in O(n) time using n processors only. In addition, all of the parallel solutions presented here are processor-time optimal.