Department of Computer Science, Wichita State University, Wichita, KS 67208.
IEEE Trans Pattern Anal Mach Intell. 1987 Jun;9(6):835-41. doi: 10.1109/tpami.1987.4767990.
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.
这篇通信介绍了几种在具有超立方体互连网络的 SIMD 阵列处理器上进行图像模板匹配的并行算法。对于 N 乘 N 的图像和 M 乘 M 的窗口，时间复杂度从串行算法的 O(N2M2)降低到 N2K2-PE 系统（1 <= K <= M）的 O(M2/K2 + M * log2 N/K + log2 N * log2 K)，或者 L2-PE 系统（L <= N）的 O(N2M2/L2)。通过有效利用 PE 之间的通信网络，每个 PE 只需要少量的本地内存，消除了许多不必要的数据传输，大大降低了时间复杂度。
