Parallel Algorithms for Image Template Matching on Hypercube SIMD Computers

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(N²M²) for the serial algorithm to O(M²/K²+ M * log₂N/K + log₂N * log₂K) for the N²K²-PE system (1≤ K ≤ M), or to O(N²M²/L²) for the L²-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.