An efficient algorithm for image-template product on SIMD mesh connected computers

Convolutions and correlations are fundamental operations in computer vision and image processing. The image-template product expresses convolutions and correlations. In this paper, the authors present an efficient algorithm for the image-template product on SIMD mesh connected computers. The image-template product is computed along disjoint convolution paths of the template. For an M × N image and a template of T elements, the simple algorithm for the image-template product on an M × N mesh connected computer takes O(T) time and requires O(1) local memory per processing element. Compared with the previously proposed algorithms, the algorithm works for both invariant and variant templates without any restrictions on the template shapes. Furthermore, it does not broadcast template weights and does not have partial result movement