Efficient search algorithm based on constraint inequality on correlation coefficients and its applications
Takahiro Mae, Shun’ichi Kaneko · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2003
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.