A Study on Fast Search Algorithm in Large Scale Image Database based on Correlation Analysis

提出了一种在一组配准图像中寻找与目标图像相似的图像的快速算法。假设该组图像预先和离线地被处理为具有所有配准图像对的相关系数。为了设计该算法，我们通过一种间接的方式，通过任意一幅枢轴图像，从数学上推导出了任意配准图像与所给目标图像之间的相关系数的约束不等式。该不等式显示了未知注册图像的估计相关系数的值的范围。主要利用该不等式定义的上界，导出了从总图像集中选择相似度较小的冗余或忽略图像的三个条件，从而加快了搜索的计算速度。将该快速算法应用于1,200幅日文平假名图像的实际搜索问题。对204幅不同相似度的目标图像进行检索，平均效率为8倍，表明了该方法在大规模图像数据库系统、媒体数据库和数据挖掘系统中图像检索的有效性。该算法可与SSDA、随机抽样等现有算法配合使用，以降低计算量。

A rapid algorithm of searching for similar images to an object image in a set of registered images is proposed. The set of images is assumed to be processed to have correlation coefficients for all the pairs of registered images in advance and in offline. For designing the algorithm, by an indirect way through any pivot image, we mathematically derive a constraint inequality about correlation coefficients between any registered images and the object image provided. The inequality shows a range of values of estimated correlation coefficients for unknown registered images. Mainly by use of the upper bounds defined by the inequality, three conditions for selecting redundant or neglected images having small similarity from the total image set can be derived, which enable to quicken computation of searching. The rapid algorithm is applied to real world searching problems with the set of 1,200 images of Japanese characters, Hirakana. Efficiency rate of eight times in average could be obtained for searching 204 object images of various similarities, enabling to show the effectiveness of the proposed method for real world tasks of image retrieval in large scale image database systems, media database, and data mining systems. The proposed algorithm can be applied for decreasing computational cost in cooperation with some existing schemes, such as SSDA, and random sampling.