Parallel Algorithms for Image Template Matching on Hypercube SIMD Computers
- 1 November 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. PAMI-9 (6) , 835-841
- https://doi.org/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 N/K + log2 N * log2 K) for the N2K2-PE system (1 ≤ 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.Keywords
This publication has 6 references indexed in Scilit:
- The cosmic cubeCommunications of the ACM, 1985
- Algorithms for concurrent processorsPhysics Today, 1984
- Parallel Processing Approaches to Image CorrelationIEEE Transactions on Computers, 1982
- PASM: A Partitionable SIMD/MIMD System for Image Processing and Pattern RecognitionIEEE Transactions on Computers, 1981
- Parallel Matrix and Graph AlgorithmsSIAM Journal on Computing, 1981
- The cube-connected-cycles: A versatile network for parallel computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979