A cost optimal parallel algorithm for histogram image matching
K. V. Arya, P. Gupta, Prem Kumar Kalra · 2004
This paper presents a parallel algorithm for histogram image template matching using an SIMD array processor with a hypercube interconnection network. For an N/spl times/N image and M/spl times/M template window, the time complexity is shown to be reduced to O(M+log/sup 2/M+logN) as compared to O(N/sup 2/M/sup 2/) for the sequential algorithm, for the N/sup 2/ processing element (PE) multiprocessor systems. Each PE requires only a small local memory. The algorithm is shown to be cost optimal with total cost of computation is O(N/sup 2/M+N/sup 2/log/sup 2/M+N/sup 2/logN).