基于颜色方差的图像相似检索算法研究*

尹玉梅，彭 艺，祁俊辉

（昆明理工大学 信息工程与自动化学院，云南 昆明 650000）

0 引 言

图像相似检索指对指定图像进行相似图像的匹配工作，是图像处理领域的一项综合研究。特别是随着互联网时代的发展，图像数据愈来愈多，图像相似检索被广泛应用于目标识别、照片过滤等场景。

2001年，Ton Kalker[1]等人提出感知哈希（Perceptual Hashing）的概念，并吸引了很多学者[2-4]。后期也有很多学者对其进行了改进工作，如Swaminathan A[5]等人提出一种基于图像边缘的感知哈希算法；张慧[6]、赵玉鑫[7]等人基于小波变换对其进行改进，提出了一种结构化数字签名的方法；Khelifi F[8]等人提出了一种基于分块灰度直方图的感知哈希算法，建议挑选图像块的灰度统计属性，如均值、方差，生成感知哈希序列。近几年，也出现了类似于差异值哈希（Deference Hash）的算法，如黄嘉恒[9]等人针对多种哈希算法进行对比工作；李雨佳[10]等人对感知哈希中DCT矩阵进行改进；宋博[11]等人将快速特征提取方法与感知哈希相结合，以提升执行效率。不仅如此，干丽萍[12]、王宁邦[13]、魏辉[14]、张洪帅[15]等人还将感知哈希应用于作业相似检测、资产图片核对、舰船图片相似度检索、场景分类等领域。

就目前大部分图像相似检索算法而言，多数是对图像进行压缩、量化等工作提取图像的特征，进而比较图像之间的差异。针对均值哈希算法而言，在对图像进行处理时，往往会造成图像内容信息严重丢失、图像特征难以区分等情况。基于此，本文考虑到一行数据或一列数据的波动程度可以用方差表示，为尽可能提高图像相似检索的准确性，提出了颜色方差算法。

1 均值哈希算法介绍

均值哈希算法（Average Hash，AHash）是一种相似性距离度量方法，主要用来处理相似图像的检索工作。均值哈希通常将图像按照一定规则生成Hash值，针对不同图像计算其Hash值确定是否相似。

算法1：均值哈希算法

输入：图像X。

输出：图像X的AHash值AHashX。

步骤1：将图像X的大小压缩至M×M，通常令M=8；

步骤2：将压缩后的图像X转化为256阶灰度图像，并表示为矩阵形式IX，其中IX(i, j),i∈[1,M],j∈[1,M]为矩阵元素值；

步骤3：通过式（1）计算矩阵IX的元素平均值uX；

步骤4：根据式（2）生成新矩阵TX，其中TX(i, j),i∈[1,M], j∈[1,M]为矩阵元素值；

步骤5：将矩阵TX按照从上至下（i=1→M）、从左至右（j=1→M）的规则，连接生成图像X的AHash 值 AHashX。

通常，由算法1将图像生成AHash值后存储至数据库中，在进行相似图像检索时，只需计算图像的AHash值之间海明距离，即可确定图像之间是否相似。

2 颜色方差算法介绍

虽然均值哈希算法使用时非常简便，但在实践中往往达不到预有的效果。究其原因，根本原因有两点：

（1）该算法需将图像的大小压缩至M×M（通常令M=8），在进行平均值对比时会造成图像内容信息严重丢失；

（2）该算法基于海明距离判断图像之间是否相似，若生成的AHash值长度较短，则图像特征将难以区分。

基于此，考虑到一行数据或一列数据的波动程度可以用方差表示，为尽可能提高图像相似检索的准确性，提出了颜色方差算法。

算法2：颜色方差算法

输入：图像X。

输出：图像X的横向方差向量Varc-X、纵向方差向量Varl-X。

步骤1：将图像X的大小压缩至M×M，通常令M=8；

步骤2：将压缩后的图像X转化为256阶灰度图像，并表示为矩阵形式IX，其中IX(i, j),i∈[1,M],j∈[1,M]为矩阵元素值；

步骤3：通过式（3）计算矩阵IX的行元素平均值uc-X(i),i∈[1,M]、列元素平均值ul-X( j), j∈[1,M]；

步骤4：将矩阵按照从左至右（j=1→M）的规则，根据式（4）进行方差计算，得到矩阵IX的横向方差向量Varc-X，其中Varc-X( j), j∈[1,M]为向量元素值；

步骤5：将矩阵按照从上至下（i=1→M）的规则，根据式（5）进行方差计算，得到矩阵IX的纵向方差向量Varl-X，其中Varl-X( i),i∈[1,M]为向量元素值。

通常，由算法2将图像生成横向方差向量、纵向方差向量后存储至数据库中，在进行相似图像检索时，只需通过向量距离度量方法计算图像的横向方差向量、纵向方差向量之间距离，即可确定图像之间是否相似。

算法3：相似度量算法

输入：图像A、B的横向方差向量Varc-A、Varc-B和纵向方差向量Varl-A、Varl-B。

输出：图像A、B的相似度Sim(A,B)。

步骤1：通过式（6）计算图像A、B之间基于横向方差向量的相似度Simc(A,B)；

步骤2：通过式（7）计算图像A、B之间基于纵向方差向量的相似度Siml(A,B)：

步骤3：通过式（8）对基于横向方差向量的相似度Simc(A,B)和基于纵向方差向量的相似度Siml(A,B)进行整合归一，得到图像A、B的相似度Sim(A,B)。

3 实验与结果

为验证本文提出的基于颜色方差的图像相似检索算法的准确性、有效性、适应性以及效率性，本文设计了以下实验。实验的主要目的在于通过与对现有其他算法的比较，考察本算法对图像相似检索的有效性、准确性、效率性以及本算法是否能够更准确、完整地检索所有相似图像。

3.1 实验数据

实验采用10 000张大小为256×256、各不相同的鲜花图像作为基准图，在其右下角分别加上如表1所示的水印生成水印图，共计70 000张图像，并编号为1～70 000，其中1～10 000为原图。

为验证方便，实验数据中编号为i的图像，其生成的水印图编号为10 000q+i,q∈[1,6]，且算法2中设置图像压缩大小M=8。编号为1的图像及其加水印生成的相似图像如图1所示。

表1 水印信息

3.2 实验过程

实验采用编号为1～10 000的图像进行相似图像的检索，遍历数据库中所有图像得到结果，并与传统的均值哈希算法（AHash）、感知哈希算法（PHash）、差异值哈希算法（DHash）等进行对比，考察本算法对图像相似检索的有效性、准确性、效率性以及本算法是否能够更准确、完整地检索所有相似图像。实验结果如表2所示，其中“检索出相似图像的个数”指对相似度进行从大至小排序后，前20张图像中所包含的正确相似水印图像的个数，错误相似水印图像不计入内。

图1 编号为1的图像及其加水印生成的相似图像

由于测试数据较大，取样本编号为1～100的实验样本绘制折线图，其检索出相似图像的个数对比图及运行时间对比图分布如图2、图3所示。

从图2可以直观看出，本算法检索出的相似图像个数明显比均值哈希算法（AHash）、感知哈希算法（PHash）、差异值哈希算法（DHash）更完整，具体检索完整性应为“本算法＞感知哈希算法＞差异值哈希算法＞均值哈希算法”。结合表2数据及图3可知，本算法的平均运行时间为1.329 3 s，而均值哈希算法（AHash）、感知哈希算法（PHash）、差异值哈希算法（DHash）的平均运行时间分别为1.781 8 s、2.700 7 s及0.750 8 s。虽然四种算法的时间复杂度均为O(N)，但具体运行时间应为“差异值哈希算法＞本算法＞均值哈希算法＞感知哈希算法”。

综合实验结果说明，本算法的执行效率较均值哈希算法提升了25.4%左右，且检索完整性比均值哈希算法、感知哈希算法、差异值哈希算法都要高。

表2 实验所得结果

图2 本算法与传统AHash/PHash/DHash算法检索出相似图像的个数对比

图3 本算法与传统AHash/PHash/DHash算法运行时间对比

4 结 语

文中针对均值哈希算法中存在的图像内容信息严重丢失、图像特征难以区分等造成的检索准确度不高的情况，提出了基于颜色方差的图像相似检索算法。算法分别对行元素、列元素进行灰度值方差求解，生成图像的横向方差向量和纵向方差向量，再通过余弦定理对其进行相似度计算。

实验结果表明，该算法在图像相似检索中执行效率较均值哈希算法提升了25.4%左右，且较均值哈希算法、感知哈希算法、差异值哈希算法能够更准确、完整地检索所有相似图像，具体检索完整性为“本算法＞感知哈希算法＞差异值哈希算法＞均值哈希算法”，运行效率为“差异值哈希算法＞本算法＞均值哈希算法＞感知哈希算法”。