DocumentCode :
796290
Title :
Convolution on mesh connected multicomputers
Author :
Ranka, Sanjay ; Sahni, Sartaj
Author_Institution :
Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA
Volume :
12
Issue :
3
fYear :
1990
fDate :
3/1/1990 12:00:00 AM
Firstpage :
315
Lastpage :
318
Abstract :
An efficient parallel algorithm is presented for convolution on a mesh-connected computer with wraparound. The algorithm does not require a broadcast feature for data values, as assumed by previously proposed algorithms. As a result, the algorithm is applicable to both SIMD and MIMD meshes. For an N×N image and a M×M template, the previous algorithms take O (M2q) time on an N×N mesh-connected multicomputer (q is the number of bits in each entry of the convolution matrix). The algorithms have complexity O(M2r), where r=max {number of bits in an image entry, number of bits in a template entry}. In addition to not requiring a broadcast capability, these algorithms are faster for binary images
Keywords :
computational complexity; computerised picture processing; parallel processing; MIMD meshes; SIMD meshes; computerised picture processing; convolution matrix; efficient parallel algorithm; mesh connected multicomputers; wraparound; Broadcasting; Computer science; Computer vision; Convolution; Filtering; Image edge detection; Image processing; Image registration; Object detection; Parallel algorithms;
fLanguage :
English
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Publisher :
ieee
ISSN :
0162-8828
Type :
jour
DOI :
10.1109/34.49056
Filename :
49056
Link To Document :
بازگشت