- Presented at the 1993 International Conference on Parallel Processing .

-Appeared in the IEEE Transactions on Pattern Analysis and Machine Intelligence .

Efficient Image Processing Algorithms on the Scan Line Array Processor

We develop efficient algorithms for low and intermediate level image processing on the scan line array processor, a SIMD machine consisting of a linear array of cells that processes images in a scan line fashion. For low level processing, we present algorithms for block DFT, block DCT, convolution, template matching, shrinking, and expanding which run in real-time. By real-time, we mean that, if the required processing is based on neighborhoods of size m by m, then the output lines are generated at a rate of O(m) operations per line and a latency of O(m) scan lines, which is the best that can be achieved on this model. We also develop an algorithm for median filtering which runs in almost real-time at a cost of O(m log m) time per scan line and a latency of m/2 scan lines. For intermediate level processing, we present optimal algorithms for translation, histogram computation, scaling, and rotation. We also develop efficient algorithms for labelling the connected components and determining the convex hulls of multiple figures which run in O(n log n) and O(n log2 n) time, respectively. The latter algorithms are significantly simpler and easier to implement than those already reported in the literature for linear arrays.

PostScript or Compressed PostScript Version of this report.

University of Maryland

Department of Computer Science and Department of Electrical Engineering, and

The University of Maryland Institute for Advanced Computer Studies

For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to:
   David R. Helman
   E-mail: helman@umiacs.umd.edu
   Office phone: (301)405-6757 
   FAX: (301)314-9658

Return to the Experimental Parallel Algorithmics page.