A special purpose simd machine for Low-level vision processing

Abstract

The thesis deals with the design of a parallel computer architecture and a performance analysis of a simulated version of the same, for a class of problems in vision using a relaxation labeling paradigm. The motivation comes from the intrinsically parallel architecture of the human vision system.

The problem involved is in low?level vision and the suitability of the relaxation labeling algorithms for their solution is indicated. Through the example of stereopsis, it is shown that low?level vision problems may be classified as continuous labeling problems. The processing requirements of a probabilistic relaxation algorithm are well suited to low?level vision problems.

Further, after a brief survey of existing parallel architectures, it is indicated that SIMD (Single Instruction, Multiple Data) architectures are suited to the present problem of low?level vision. The design of a new SIMD machine tailored to the processing requirements of low?level vision problems is described, progressively from the system level down to the level of designing individual processing elements (PE). Since processing is done in the context of a local neighbourhood, an efficient communication scheme has been designed. It exploits the uniformity of neighbour data accesses across the image array. A machine?level instruction set for the machine is formulated to exploit the special features of the machine. Further, a distributed masking scheme has been incorporated to allow the efficient execution of data?conditional instructions. Both the workability and the adequacy of the instruction set have been verified by simulating the architecture.

The performance of some representative algorithms, with reference to low?level vision problems, has been analysed on the architecture. In particular, to illustrate the suitability of the architecture for low?level vision problems, the stereopsis algorithm has been analysed on the simulated architecture. For an N?processor system the ideal speed?up for the execution of this algorithm is expected to be of the order of N. However, it is shown that this ideal speed?up is not attainable due to the I/O and communication bottlenecks inherent in SIMD systems. One way of reducing the communication overheads is suggested. A similar analysis is performed for the convolution and FFT (Fast Fourier Transform) algorithms. The results of these analyses indicate how the architecture may be efficiently used for other low?level vision and image processing operations.

The basic functions of the architecture, like inter?PE communication, input?output etc., have been compared with some existing architectures like the PASM, MPP and the Connection Machine. The inter?PE communication scheme of the proposed architecture is found to be ideally suited to local processing. Although the architecture sacrifices generality, it is shown to be suited to the requirements of low?level vision processing.

The thesis concludes with some suggestions for future work.