Optimal Speed-Up Parallel Image Template Matching Algorithms on Processor Arrays with a Reconfigurable Bus System,

摘要

The image template matching problem is one of the fundamental problems of and has many practical applications in image processing, pattern recognition, and computer vision. It is a useful operation for filtering, edge detection, image registration, and object detection [13]. In this paper, we first design twoO[(M2/p2)log logM] andO[(M2/p2)+(M/p)log logp] time parallel image template matching algorithms on a 3-D processor array with a reconfigurable bus system usingp2N2processors with each processor containingO(1) andO(M/p) restricted memory for 1 ≤p≤M≤N, respectively, for anN×Ndigital image and anM×Mtemplate. By increasing the number of processors, these two proposed algorithms can be run inO(M2/p2) time for speeding up the time complexity usingp2M1/cN2andp2+1/cN2processors, respectively, wherecis a constant andc≥1. Furthermore, anO(1) time can be also obtained from these two proposed algorithms by usingM2+1/cN2processors. These results improve the best known bounds and achieve both optimal and optimal speed-up in their time and processor complexities.