Parallel algorithms for image template matching on hypercube SIMD computers
No Thumbnail Available
Authors
Fang, Zhixi
Li, Xiaobo
Ni, Lionel M.
Advisors
Issue Date
1987-11
Type
Article
Keywords
Communication networks , Computer networks , Concurrent computing , Data communication , Hypercubes , Mesh networks , Multiprocessor interconnection networks , Parallel algorithms , Reflective binary codes
Citation
Fang, Zhixi; Li, Xiaobo; Ni, Lionel M.; , "Parallel Algorithms for Image Template Matching on Hypercube SIMD Computers," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.PAMI-9, no.6, pp.835-841, Nov. 1987
doi: 10.1109/TPAMI.1987.4767990
Abstract
This correspondence presents several parallel algorithms for image template matching on an SIMD array processor with a hypercube interconnection network. For an N by N image and an M by M window, the time complexity is reduced from O(N2M2) for the serial algorithm to O(M2/K2 + M * log2 NIK + log2 N * log2 K) for the N2K2-PE system (1 s K . M), or to O(N2M2/L2) for the L2-PE system (L < N). With efficient use of the inter-PE communication network, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the time complexity is greatly reduced.
Table of Contents
Description
Click on the DOI link below to access the article (may not be free)
Publisher
IEEE
Journal
Book Title
Series
Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.PAMI-9, no.6, pp.835-841
PubMed ID
DOI
ISSN
0162-8828