Parallel algorithms for generalized image-template operations on mesh processor arrays

Generalized image-template operations generalize conventional convolutions, correlations, and morphological operations. They can be used to concisely describe many image processing algorithms concisely. However, they are computationally expensive. In this paper, we present two efficient algorithms for generalized image-template operations on mesh processor arrays. The algorithm for the general case takes O([m/n]n) time and O(1) local memory, where n is the size of the n×n source image and m is the number of pixels in the result image. The algorithm for a special case that each pixel of the source image contributes to only one pixel of the result image: takes O([m/kn]n) time and O(k) local space, where k is an integer in [1.[m/n]]