We propose an efficient template matching algorithm for binary image search. When we use template matching techniques, the computation cost depends on size of images. If we have large size images, we spend a lot of time for searching similar objects in scene image to template image. We design a scanning-type upper limit estimation that can be useful for neglect correlation calculation. For calculating the scanning-type upper limits, template and scene images are divided into two regions: R-region and P-region. In R-region, an upper limit of correlation coefficients can be derived as an interval estimation based on mathematical analysis of correlations of the object image and a pivot image. In P-region, another upper limit is formalized based on the number of white and black pixels in a template and the object image. By use of these upper limits, the scanning-type upper limit estimation of correlation coefficients can be formalized for the efficient matching algorithm. This upper limits estimation isn't over true values of correlation, so the accuracy of search by conventional search is the same as one by conventional search. The experiments with document images show the effectiveness and efficiency of the proposed matching algorithm. In these experiments, computation time by the proposed algorithm is between 5 and 20% compare of the conventional search.
An efficient algorithm for searching similar images from databases of a large set of images is proposed. For designing the algorithm, all the correlation coefficient values of registered images are calculated in advance to online computation and they are memorized as a set of keys for efficient search. We theoretically derive an interval estimation of any correlation coefficient between an object image and arbitrary registered images in terms of a pivot image that is one of candidates of the unique solution image and can be simply selected. Using the interval estimations on all the other registered images, some conditions for selecting redundant images from the registered images can be derived and evaluated and then those who has any smaller similarity than the one computed by the pivot image can be skipped away from correlation computation, which efficiently enables to save a lot of computational cost for search. The algorithm was applied to real searching problems in an image database of 1,200 images taken from the real world and to search in multiple template matching problems, for example rotation invariant matching and a search problem on binary maps, resulting the efficiency of the proposed method for the real problems.