基于图论的视觉显著模型的图像哈希算法

凌 曼，陈秀明，王先传，齐保峰，刘争艳

（1.安徽工商职业学院 信息工程学院，安徽 合肥 231131；2.阜阳师范大学 计算机与信息工程学院，安徽 阜阳 236037）

图像哈希又被称为图像摘要或图像指纹，可以用一段序列表示图像信息，它通常被用来检测网络空间中有许多热门事件的图像副本，还被广泛应用于图像索引、图像质量评价、图像检索、图像取证等方面。图像哈希算法可以将任意一幅图像映射成一串短小的字符序列或者数字。通常，图像哈希算法需要具备两个基本性质：鲁棒性和唯一性。鲁棒性是指哈希算法需要具备抵抗图像压缩、图像增强、噪声干扰等正常数字操作的能力。这是因为经历这些操作后的图像，其视觉内容与原图像基本一致，图像哈希应该基本相同。唯一性是指，对于视觉内容差异较大或者完全不同的图像，用哈希算法计算得到的哈希值应完全不同，良好的唯一性意味着将不同图像判断为相似图像的错误率较低。一个高性能的算法应该在鲁棒性和唯一性之间达到很好的平衡。近年来，学者们提出并研究了许多哈希算法来提高图像的鲁棒性和唯一性。Tang[1]等提出了一种基于光谱残差（SR）模型和低秩表示（LRR）相结合的图像哈希算法，该算法对大角度旋转具有较好的鲁棒性，但是唯一性有待提高。He[2]等提出了一种无监督双向离散矩阵分解哈希算法（BDMFH），其具有良好的鲁棒性和快速的计算速度。Zhou[3]等提出了一种基于深度森林的哈希学习方法，通过多粒度扫描和级联森林生成一个深层森林集成分类器来逐层处理数据，以实现高效的图像检索。但是对于较长二进制码的处理，其性能有待提高。Qin[4]等提出了一种基于纹理和结构特征相结合的图像哈希算法，该算法具有较好的稳健性，但是在唯一性方面有待提高。凌曼[5]等提出了基于Itti视觉显著模型和LLE的图像哈希算法，该算法在鲁棒性和唯一性之间可以达到良好的平衡。Tang[6]等利用随机Gabor滤波器和DWT提取图像特征的哈希算法，该算法的分类性能较好且运算速度也比常见DWT的哈希算法快。Shen和Zhao[7]提出了一种基于局部和全局特征的图像哈希算法，其利用中心对称局部二值模式（CS-LBP）提取图像特征，具有较好的鲁棒性。Yuan和Zhao[8]提出了一种结合三维全局特征和局部能量特征的哈希算法，其利用不同三维视角下图像各层统计特征之间的关系生成全局特征哈希，该算法不仅提高了哈希算法的分类性能还加快了运算效率。张春艳[9]等设计了一种基于DWT和感知哈希的检索方案。该方案利用Henon映射对图像进行频域加密运算，然后对医学密文图像进行DWT并生成逼近原图的子图，通过比较DCT系数与系数均值的关系得到图像的感知哈希序列。该算法对于常规的几何攻击具有良好的鲁棒性，但是其运行速度和唯一性有待提高。

从上面的综述可以发现，大多数算法在鲁棒性和唯一性之间没有达到很好的平衡。针对这个问题，本文提出了一种基于图论的视觉显著（GBVS）模型的图像哈希算法，该算法的主要贡献如下。

（1）利用GBVS模型提取的显著性图来计算预处理图像的视觉表示。由于显著性图可以表示人类的视觉注意，使用显著性图的视觉表示可以有效地描述图像的显著区域，在计算效率和检测性能方面有较好的优势，所以具有可视化表示的哈希生成可以提高算法的鲁棒性。

（2）通过对中间哈希进行数据加密，由混沌函数随机生成序列，使得最终哈希具有安全性。

1 相关工作

1.1 基于图论的视觉显著（GBVS）模型

GBVS模型是Harel[10]等提出的一种新的自底向上的视觉显著性模型，是在经典的Itti模型[11]基础之上，运用马尔科夫随机场的特点构建二维图像，并对二维图像的马尔科夫链求平衡分布后得到的显著图，GBVS模型具有较好的显著性检测效果。GBVS模型[12-14]的基本思想是：图像的显著性体现在特征图中，若能有效地生成特征图，则可以得到效果较好的显著图。GBVS模型生成显著图的方法与Itti模型相似，图像提取三个底层特征的方法也相同，特征图的融合也相同。不同的是GBVS特征图是通过先构造马尔可夫矩阵，然后用幂法计算其最大谱对应的特征向量，最后利用图谱的方法来生成图，并且仅采用了Itti的前四层高斯金字塔分解图，即σ=[0,1,2,3]。本文只介绍GBVS模型与Itti模型不同之处，相同之处就不在此赘述。

1.2 构造马尔科夫矩阵

假设M用来表示原始图像的灰度，图像中两个不同像素点的坐标位置分别用(i,j)和(p,q)来表示，M(i,j)代表(i,j)坐标位置的像素点灰度值，M(p,q)代表(p,q)坐标位置像素点的灰度值，则M(i,j)和M(p,q)之间的差异性定义为

把M的像素点看作图GM的结点，利用公式（2）构造权重矩阵来作为图GM的邻接矩阵，它可反映其它结点与GM中任意结点的联系。

其中，σ为常数，一般取值是图像宽度的1/10到1/5，在此区间取值对输出结果影响较小。如式（2）所示，结点(i,j)与(p,q)连接成边的权重与结点之间的差异对比性及相隔距离成正比。相反方向则拥有同样的权重：

其中，GM是一个无向图。将构造出的权重矩阵按列进行归一化后得到的矩阵称之为马尔可夫矩阵，该矩阵可以充分反映每个像素点与其周边像素点间的差异对比性。

1.3 计算最大谱对应的特征向量

GBVS是通过幂法来计算最大谱对应的特征向量。假设M有X1,X2,X3,…,Xn个线性无关的特征向量，对应的特征值为λ1,λ2,λ3,…,λn，且

设U0为任取一非0向量，并且与M进行迭代，

得到向量序列{Uk}，k=1,2,3…。

由于X1,X2,X3,…,Xn是线性无关的特征向量，则n维非0向量U0可线性表示为

则有

并且|λ2/λ1|≤1,|λ3/λ1|≤1,|λ4/λ1|≤1,…,|λn/λ1|≤1，且a1≠0，Uk≈λk1a1X1是非0向量，当k足够大时，只有λk1a1X1为非0，其余各项全部接近于0。因此，Uk可以近似视为λ1所对应的特征向量。

2 具体采用的哈希算法

基于图论的视觉显著模型的图像哈希算法主要可分为三个步骤（图1）：第一步，首先对输入的图像进行预处理，目的是建立规范化图像；第二步，利用GBVS模型提取图像的视觉显示图，并压缩量化成中间哈希；最后，对中间哈希进行数据加密以得到最终的哈希值。

图1 本文所提的哈希算法示意图

2.1 预处理

预处理的主要操作就是通过双线性插值[15]将输入的图像转换为相同尺寸。通过该操作可以对图像边缘进行柔化处理，使图像边缘更加平滑，确保所提的哈希算法能够抵抗较小的图像缩放，并且可以使输入的不同图像的哈希长度相同。

2.2 提取视觉显著图

在预处理生成规格化图像后，运用GBVS模型计算图像的视觉显著区域，并将提取出的视觉显著图记为J。具体步骤如下：首先，将输入的归一化图像表示为无向完全图，并将图的节点视为像素。然后，计算任意两个像素之间的差值与比率，且作为其对应结点连接边的权重；接着，通过随机游走算法[16]将访问频率较低的结点找出，并给其对应像素赋予较大的显著值。由于在随机游走过程中，图像中显著性较大的像素点与其他像素差异对比度较大，因此被访频率很低，这使得GBVS能够从全局的角度来很好地定位显著目标物对象。图2是一幅彩色图像及其视觉显著图。

图2 彩色图像及其视觉显著图。（a）原图像；（b）GBVS视觉显著图

为了得到较短的中间哈希序列，对上文提取的视觉显著图J进行非重叠分块，分块大小为m×m，其中m可以被M整除，即n=M/m，于是得到n×n个图像块，同时，计算每个图像块的均值，并用该均值表示原图像块，因此可得到大小为n×n的均值图像L。通过串联图像L上所有均值，于是得到一个包含n2个元素的序列V=[V(1),V(2),V(3),…,V(n2)]。

2.3 数据加密

从图像的安全应用考虑，图像哈希算法需要由密钥控制，使其具备安全性能。因此，在设计哈希算法时通常会引入密钥，由密钥去控制哈希序列的生成。换言之，对于给定的一幅图像，使用不同的密钥去提取哈希序列，所产生的哈希序列也应该不同。对于有密钥控制的图像哈希函数，只有密钥的所有者才能正确提取哈希值。为了生成安全的图像特征，本文用Logistic混沌映射[17]对中间哈希序列V进行加密处理，并生成最终的图像哈希H。Logistic混沌映射公式如下，

其中，u是Logistic参数，0≤xi≤1，0≤u≤4。研究表明，当xi∈[0,1]时，Logistic映射处于混沌状态，实际中可将初值x0设为密钥。本文通过Logistic混沌公式迭代生成n2个随机数，将这些数依次进行排序，最后对照随机数确定排序前后的位置关系，将中间哈希V的元素重新排列，得到最终的图像哈希H，从而实现数据加密。

2.4 哈希相似度计算

设H1=[H1(1),H1(2),H1(3),…,H1(n2)]和H2=[H2(1),H2(2),H2(3),…,H2(n2)]分别是两幅图像的哈希序列，采用相关系数来测量它们的相似度。计算公式如下，

其中，a1和a2分别为H1和H2的均值，H1(l)和H2(l)分别为H1和H2的第l个元素，Δs是一个接近于0的正常数。相关系数的取值范围为[-1,1]，通常相关系数越大，哈希序列越相似。如果ρ

3 实验结果及分析

实验图像尺寸为512×512，非重叠图像块的大小为64×64，Logistic混沌映射生成的随机数共64个，图像哈希序列为64个整数。下面分别讨论算法的鲁棒性、唯一性、密钥依赖性性及相关性能。

3.1 鲁棒性

本文选择柯达彩色图像库[18]中图像作为测试图像，其包含人像、建筑、花卉和风景等24幅彩色图像。利用MATLAB、Photoshop和Stir-Mark工具对测试图像进行常见的数据操作，以获得视觉相似图像用于鲁棒性测试。MATLAB提供了3×3高斯低通滤波（标准偏差范围为0.3～1.0，步长为0.1）、伽马校正（参 数 为0.75、0.9、1.1和1.25）、椒盐噪声和斑点噪声处理（两个参数范围为0.001～0.01，步长为0.001）。Photoshop提供亮度和对比度调整（参数为±10和±20）。Stir-Mark提供JPEG压缩（质量因子范围为30～100，步长为10）、水印嵌入（强度范围为10～100，步长为10）、图像缩放（缩放比为0.5、0.75、0.9、1.1、1.5和2.0）和图像旋转（旋转角度为±1、±2、±3、±4、±5）。值得注意的是，图像旋转将增加图像大小，并将一些填充像素添加到旋转图像中。通过这些常见数据操作，使得每幅测试图像可以得到74幅相似图像，因此一共得到1 776（24×74=1 776）对视觉上相似的图像。分别提取测试图像与其视觉相似图像的哈希值，并计算哈希相似度，不同鲁棒性攻击的测试结果如图3所示。其中x轴是不同操作的参数，y轴是相关系数。图3中曲线是24幅彩色图像及其类似图像的哈希相关系数的平均值。可以看出，除了旋转、裁剪和缩放，大多数数据操作相关系数均大于0.98。通常相关系数越大，哈希序列越相似。如果没有旋转图像，本文算法可以较好地识别相似的图像，正确检测率高说明了本文算法具有良好的鲁棒性。因此，如果选择阈值T=0.98，本文哈希算法可以抵抗大多数鲁棒性攻击。

图3 不同鲁棒性攻击的测试结果

3.2 唯一性

选用UCID[19]来测试本文算法的唯一性，该数据集包含1 338幅真彩色图像。将本文算法应用于该数据集，提取1 338个图像哈希序列，再计算两两图像哈希序列间的相似度，可得到894 453（1 338×（1 338-1）/2=894 453）个距离，这些相关系数分布结果如图4所示。从图可知，最大相关系数为0.998 3，最小相关系数为-0.238 2，均值为0.822 3，标准差为0.132 6。同时，大多数相关系数都小于上述阈值T=0.98，唯一性表现良好，本文算法能够较好地区分不同图像。实际上，唯一性和鲁棒性与阈值的选取密切相关，不同的阈值将导致不同的性能。

对比分析发现，如果选择阈值T=0.98，此时有0.79%的不同图像被误判成相同图像；若阈值选择T=0.95，则有9.28%的不同图像被误判成相同图像，降低了算法的唯一性和鲁棒性。因此，可以选择T=0.98作为阈值，可以使总错误率较小。将图4中大于0.98的相关系数取出，并除以总的相关系数，再乘以100%，可得到不同图像被误判成相似图像的比率。

图4 不同图像间哈希距离分布

3.3 密钥依赖性

为了测试本文算法的安全性，仍然选择柯达图像数据库中的图像作为测试图像，用不同的密钥来生成同一幅测试图像的哈希值，并计算其在不同密钥下哈希序列的相关系数，结果发现所有相关系数取值都较小，则同一幅图像由于密钥的不同而被判断成不同图像，这说明哈希依赖于密钥。下面列举一个典型示例进行说明。首先，使用一组密钥提取测试图像的图像哈希。其次，利用另外100组不同的密钥生成同一图像的哈希。在实验中，仅更改密钥，其他参数保持不变。图5显示了由不同密钥控制的哈希间相关系数，可以看出，最大相关系数是0.4，远小于阈值T=0.98，说明哈希依赖于密钥，即本文的图像哈希算法具有较好的密钥依赖性。

图5 不同密钥的哈希序列间相关系数

3.4 算法性能比较

为了验证哈希算法的优越性，将本文算法与一些文献的图像哈希算法进行比较。选择的对比算法有基于视觉模型的低秩图像哈希算法[1]（Sr-Lrr）、基于视觉显著模型和局部线性嵌入的图像哈希算法[5]（Itti-Lle）和基于混合特征的哈希算法[4]（Hybrid feature）。数据集采用3.1和3.2节的测试图像库，图像大小调整为512×512，其他参数设置不变。同时，对比算法的哈希相似测度仍然保持与原论文一致，即Sr-Lrr、Itti-Lle和Hybrid feature采用L2范数。为了直观地比较算法性能，采用接收机操作特性[20]（ROC）曲线来分析本文算法和对比算法的分类性能，并计算正确率PTPR和误判率PFPR。

其中，n1是相似图像的正确判断数，N1是相似图像的总数；n2是不同图像的误判数，N2是不同图像的总对数。PTPR和PFPR分别描述唯一性和鲁棒性，PFPR越小，唯一性越好；PTPR越大，鲁棒性越好。因此，在ROC曲线图中，靠近左上角的ROC曲线优于距离左上角较远的曲线，其算法的整体分类性能越好。图6对比了各种哈希算法的ROC曲线，其中，本文哈希算法的曲线最靠近左上角，其他对比算法的ROC曲线均在其下方，说明本文哈希算法优于Sr-Lrr、Itti-Lle和Hybrid feature算法。

图6 不同哈希算法的ROC曲线

实际上，本文算法之所以优于其他三种算法，主要归功于精心的设计步骤和合适的相似性度量。通过GBVS模型求解马尔可夫链的平稳分布且对图像进行显著性检测，对具有复杂背景的图像有很好的适应性，提升了算法的鲁棒性。同时，文献[12]对多种显著性算法的优劣进行了评价，结果表明，GBVS模型在背景复杂、目标结构清晰的图像中比Sr模型和Itti模型更具优势。而Hybrid feature算法通过提取纹理和结构这两类特征后，再进行降维来生成图像哈希，会失去某些局部信息，从而导致唯一性降低。

4 结语

本文提出了基于图论视觉显著模型的图像哈希算法，使鲁棒性和唯一性之间达到了较好的平衡。该算法的主要贡献是利用GBVS模型提取的显著性图来突出显著区域，提高了算法的鲁棒性；再通过Logistic混沌映射生成位置映射数组，并对该数组进行数据加密以得到最终的哈希值，从而确保哈希算法具有安全性。通过验证，本文算法具有较好的鲁棒性与唯一性。同时，ROC曲线也表明，该哈希算法优于Sr-Lrr、Itti-Lle和Hybrid feature算法。在接下来的工作中，可将深度学习算法引入到哈希算法中并扩大数据集验证。