Convolution on mesh connected multicomputers
Sanjay Ranka, Sartaj K. Sahni · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1990
Convolution is an important primitive in computer vision and image processing. In this paper, we present an efficient algorithm for convolution on a mesh connected computer with wraparound. Our algorithm does not require a broadcast feature for data values as assumed by previously proposed algorithms. As a result, the algorithm is applicable both to SIMD as well as MIMD meshes. For an NN image and a MM template, the previous algorithms take O (M q) time on an NN mesh connected multicomputer (q is the number of bits in each entry of the convolution matrix). Our algorithms have complexity O (M r) where r = max {number of bits in an image entry, number of bits in a template entry}. So, in addition to not requiring a broadcast capability, our algorithms are faster for binary images.