超立方体 SIMD 计算机上图像模板匹配的并行算法。

Parallel Algorithms for Image Template Matching on Hypercube SIMD Computers.

机构信息

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.

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 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 只需要少量的本地内存，消除了许多不必要的数据传输，大大降低了时间复杂度。