TY - JOUR
T1 - Parallel Algorithms for Image Template Matching on Hypercube SIMD Computers
AU - Fang, Zhixi
AU - Li, Xiaobo
AU - Ni, Lionel M.
PY - 1987/11/1
Y1 - 1987/11/1
N2 - 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 * log2N/K + log2N * log2K) 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.
AB - 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 * log2N/K + log2N * log2K) 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.
UR - https://www.webofscience.com/wos/woscc/full-record/WOS:A1987K673500011
UR - https://openalex.org/W2070161486
UR - https://www.scopus.com/pages/publications/0023455228
U2 - 10.1109/TPAMI.1987.4767990
DO - 10.1109/TPAMI.1987.4767990
M3 - Journal Article
SN - 0162-8828
VL - PAMI-9
SP - 835
EP - 841
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
IS - 6
ER -