2021年3月计算机工程与设计Mar.2021第42卷第3期COMPUTER ENGINEERING AND DESIGN Vl42No.3基于差分的图像感知哈希算法 刘帆12!王颖闫国玉蒋遂平1
(1中国航天科工集团第二研究院七O六所，北京100854；
2.西安电子科技大学网络与信息安全学院，陕西西安710071)
摘要：现有图像感知算法侧重于减少相似图像感知哈希值间的差异性！较少关注增大不同图像感知哈希值间的差异性问题。针对这一局限性！提出并实现循环贯序差分和拉普拉斯算子两种基于差分的图像感知哈希算法！并分别在小规模相似图像集合和大规模不同图像集合上进行测试&与现有图像感知哈希算法相比！所提算法体现了图像像素点间的局部关联性！增加了不同图像哈希值间的差异！显著提升了不同图像的区分概率。 关键词：云计算；可搜索加密方案；图像检索；图像匹配；图像感知哈希
中图法分类号：TP391文献标识号：A文章编号：1000-7024((021)03-0782-08
doi：10.16208/j.issnl000-7024.202103.027
Imageperceptualhashingbasedonimagedi f erential
LIU Fan12,WANG Ying1,YAN Guo-yu1,JIANG Sui-ping1
(1.Institute706,Second Academy of China Aerospace Science and Industry Corporation,Beijing100854,China；
2.School of Cyber Engineering,Xidian University,Xi'an710071,China)
Abstract：The existing image sensing algorithms focus on reducing the difference between similar image perceptual hashing va-lues&andpaylessa t entontoCncreasCngthedC f erencebetweendC f erentCmageperceptualhashCngvalues0InvCewofthCslmta-ton&twodC f erencebasedCmageperceptualhashCngalgorthms&namelySeqpHashandLaplacepHash&wereproposedandCm-plemented&andtheyweretestedonsma l-scalesCmlarCmagesetsandlarge-scaledC f erentCmagesets0ComparCngwththeexs-tngCmageperceptualhashCngalgorthms&theproposedalgorthmembodCesthepartalcorrelatonbetweenCmagepCxels&Cncrea-sesthedC f erencebetweentheperceptualhashCngvaluesofdC f erentCmages&sCgnfcantlyCmprovestheprobabltyofdCstngus-hCngdC f erentCmages0
Keywords：cloudcomputng；searchableencryptonscheme；CmageretrCeval；CmagematchCng；CmageperceptualhashCng
1引言
图像感知哈希(perceptual hashing,pHash)1* 从一幅图像导出并可表征图像特征指纹。图像pHash算法与密码学哈希(cryptographic hashing,cHash)2*算法不同。在cHash算法中，假设输入为一幅图像，则该图像的微小变化会通过雪崩效应引起输出结果即cHash值的巨大变化；而图像pHash算法则要求输入图像在视觉上相似时，输出的图像pHash值也相似。
近年来，随着云存储技术的发展，图像pHash算法对于图像文件的内容识别、完整性验证和水印技术起到重要作用。图像pHash算法被广泛用于可搜索加密方案中的相似性检索，并因为其能同时保证查询效率和结果精确度的优点，使其成为图像安全去重的重要技术之一$4*。
云存储和去重应用，要求pHash算法具有计算简单、一定的不同图像区分能力等特性。为此，本文提出并实现了循环贯序差分和拉普拉斯算子等两种基于差分的图像感知哈希算法。针对设计的算法，分别在小规模相似图像集合和大规模不同图像集上进行了测试。与现有复杂性类似的图像感知哈希算法相比，所提出的算法体现了图像像素点间的局部关联性，增加了不同图像哈希值间的差异，显著提升了不同图像的区分概率。
收稿日期：20200421；修订日期：20200921
作者简介：刘帆(1993-)，男，陕西宝鸡人，硕士研究生，研究方向为云计算和图像识别；王颖(1986-)，女，福建南平人，硕士，高级工程师，研究方向为物联网、射频识别应用；闫国玉$981-)，男，山西运城人，硕士，研究员，研究方向为计算机技术和物联网；蒋遂平(1966-)，男，四川遂宁人，博士，研究员，研究方向为射频识别和物联网。E-mail：wangying_706@16$
第42卷第3期刘帆，王颖，闫国玉，等：基于差分的图像感知哈希算法•783•
1相关的工作
自从图像pHash的概念提出以来，研究人员已经提出了多种pHash算法。根据算法运行机制的不同，主要分为 以下3类：
⑴基于图像灰度的pHash算法：利用图像灰度值与图像灰度均值的差或者利用相邻像素的灰度差等信息来计算pHash值。应用比较广泛的主要有均值pHash算法(average pHash,Avg pHash))5］&主要利用亮度变化小的区域即图像低频成分来描述整幅图像所含有的信息，计算复杂度低，但是进行图像相似性检测的准确率较低；块均值pHash算法5，采用重叠阻塞和旋转操作来增强图像对几何失真的鲁棒性，在稳健性和可辨识性方面表现出比其它现有算法更高的性能并且实现简单；差分pHash算法5基于渐变实现，考虑了图像的局部特征。
(2)基于图像正交变换的pHash算法：对图像进行正交等方式的变换，利用变换后的系数与系数平均值的差计算pHash值。刘颖等归提出一种基于离散余弦变换(discrete cosine transform&DCT)和奇异值分解(singular value decomposition，SVD)相结合的pHash算法，首先需要将图像进行分块DCT变换，然后将低频系数的组合进行SVD变换，最后将二值水印嵌入到奇异值所对应的矩阵上，这使得当嵌入较高强度的水印时也能具有较好的视觉不可感知性。Sheth等)7］提出了一种基于DCT、离散小波变换(discrete wavelet transformation，DWT)和密码技术组合的算法，对水印图像和原始图像提供强大的鲁棒性和感知透明度，以抵抗诸如裁剪、噪声和缩放之类的不同类型的攻击。
(3)基于图像特征点的pHash算法：通过提取图像特征点来表示图像。欧阳君林等凶提出了一种基于四元数Zemike (quaternionZernikemoments，QZMs%变变换(scale invariant feature transform，SIFT)的鲁棒图像哈希方案用于图像认证。所提出的方法可以定位篡改区域并检测修改的性质，包括对象插入、移除、替换、复制、移动、剪切和粘贴等操作。然而此方案对于图像噪声以及图像亮度变化较为敏感，使得其对该类型的图像篡改识别准确率较低。杨宁等切提出了一种基于SIFT特征和角度相对距离的图像配准算法，该算法充分利用了图像正确匹配特征点对之间存在的角度关系，实现了特征点之间的精确匹配。
基于图像灰度的pHash算法主要使用图像低频成分表征图像信息，计算复杂度不高，但精度较低。基于图像正交变换的pHash算法，对图像进行正交等方式的变换来获取图片的低频成分，只要图像之间
的相互空间关系不变，即能提供良好的相似图像识别效果。但是该类算法的pHash值，大多能表示率平均值比
一个估计值，并不能提供图像真实的低频性质。基于图像特征点的pHash算法，生成的图像哈希序列维数较高，算法复杂度高，计算开销大，响应速度低，故这类pHash算法在图像快速相似性检索中很少使用。
此外，上述pHash算法的研究和应用中，重点考虑的何觉pHash值，法现pHash值对不同图像的分辨程度。常用pHash算法在实际用中，大觉为，
带来的通信开销很大。因此，需要解决感知哈希算法在应用过程中所带来的计算复杂度高、不同图像区分概率太低和通信开销大这一问题。
2图像pHash算法
2.1图像pHash值的计算流程
图像pHash值的计算流程如下：
(1)将$行“列像素点的大图像缩小为8X8、16X16、32X32即m&m等尺寸的小图像。
(2)彩小图像转换为灰度小图像，此时图像可以表示为m阶图像灰度像素矩阵。使用如下规则
Gray6P X0.299+G X0.587+1X0.114(1)式中：Gay代表图像像素点的灰度值，R、G和I分别代表红、绿和蓝3种颜通道的值，取值范围［0,255*。
(3)灰度小图像二值化，像素取值0或1，组成m阶二值像素矩阵。城市社会学论文
(4)二值小图像像素按某种顺序串接为64、256、1024等长度的比特序列，作为图像的pHash值。
各种pHash算法的主要差异在于(3)，例如，均值pHash计算平均灰下
------- —AC⑴Gray(i,j)
Gray二亠十'N⑵
式中：GO；代表图像的平均灰度值，i和丿分别代表m阶像素矩阵上的行和列，取值范围为［l,m*,Grayii,j)代表m 阶像素矩阵中第i行j列的图像灰度值，N代表m阶像素矩阵元素个数。
值化方法下
(0Grayii，jj%Gray
60_-(3)
⑴Gray ii,j),Gray
式中：h(.i,j)代表m阶二值像素矩阵第i行j列的值。如果灰大平均灰&值化果为1&为
0。同样地，在DCTpHash算法中，首先计算图像DCT系数，如果像素矩阵中第i行j列上的系数大于等于所有系数的均值，则该位置像素二值化结果就为1否则为0。
2.2图像二值化方法改进
针对图像pHash值的计算流程，提出了循环贯序差分pHash(Seq pHash)算法和拉普拉斯算子pHash(Laplace pHash)算法，并主要基于步骤(3)即图像二值化方法进行改进。
・784・
计算机工程与设计
2021 年
(1) Seq pHash ：在SeqpHash 算法中进行二值化时，
图像中 按从上到下、从左到右的顺序依次排列。对而言，如果当
灰度值大
者 一
个像素的灰度值时，则对应的二值像素为1，否则为0(当
中 一
，则当
一个
为 中第一
图#给岀了一个8X8小图像的例子，将小图像中的像 素按照图1中的序号顺序可以排成一个序列，这是Seq
pHash 的顺序性。如果序列中一个像素A 的灰度大于等于
一 B 灰 ， 这 A
氢气
值化 果为
1，否则为0。如果一个像素A 是序列中的最后一个像素，
A 一
B 序 中第 一 B ， 这 Seq
pHash 的循环性。例如在图#中，64号像素的后一个像素
1 。
(2) Laplace pHash ：在 Laplace pHash 算法中，对图
像灰度值 值化并使用 下规
=1 Gray (i, j) X (”+1) , — Gray (e ,;)
(a ，C )#d
h(i,j )= <
0 Gray ii j) X (”+1) % — GrayE ;)
>
E ，yj #D
C
⑷
式中:”为邻接像素的个数，D 为m 阶像素矩阵中第。行j 列
元素邻 点构成的集合，Gray (i ，)为m 中
第i 行j
邻
点的灰度值。设有一个灰度值为
220
风速计算A 。如果像素A 为图像中间像素，则其有8个邻接像素，此时5=8，如图2 (a )所示。如果像素A 在图
4个角上，则其有$个邻接像素，此时”=$，
2
(b)〜图2 (e)所示。如果像素A 在图像4个边缘，则有 5 邻 ， 此 5=5， 2 (f %〜 2 (i % 示。
(a)中间像素
220E0
224
E]
220
226
EJ 0
(b)左上角像素1 220
s 0
(c)右上角像素
218220
220
219
(f)左边缘像素200
210
190195180
205
(g)右边缘像素
205
210180
200
190
190
(d)左下角像素
220
公安情报学
1 220
(e)右下角像素
E
220
1
210200180220
Ld
195
220210170
230
张远国200
240
(h)上边缘像素
(i)下边缘像素
图2 Laplace pHash 中邻接像素
在Laplace pHash 算法中，仅使用了 Laplace 的一阶 微分形式，并没有采用先计算Laplace ，再计算过
零点获得边缘 值化的方法)0*。这是因为图像二值化 ，较大
tough2压缩为 ，边缘效果已经不明显，利用Laplace 算子计算边缘已经没有 多大意义。
2 3 pHash 值的相似性度量
汉明距离(Hamming distance )11*是衡量两个字之间距 离的一种方法。它通过统计两
位不数 计算 间 ，进一步达到
性：的
目的。若E = E l E 2，…E ”}和y = {y # ,y 2，…，y ”1分别表 示两个有限长度的字符串，以D (，y )
表示两个字符串
第42卷第$期刘帆！王颖！闫国玉，等：基于差分的图像感知哈希算法・785・
e,y之间的汉明距离，则相似性度量过程可表示如下
N
D(e,;)=—QE,y)(5)
A=1
式中：Q(y)取值有如下规则
[0E n=y n
QE y)=0(6)
1E n(；n
为加快字符比较效率，将汉明距离
作一化。归一化明可为
—N⑴QEr y)/、
DE e；)=I t n(7)特别的是&可以通过异或运算的方式来计算二进制字符串间明距离其中㊉代表运算符，如下
N
D b=—E㊉；)(8)
A=1
因此，可以使用所获得的两个字符串之间的汉明距离来确定其相似性。为了识别&通置汉明距离的阈值，表示为
如果DE e;)=0，则E和y被认为是相同的字符串。
如果DEy)3＜，则e和y被认为是相似的字符串。
如果DEy)〉＜则e和y被认为是不相似的字符串。
两幅pHash值用汉明距离
由于pHash值是比特序列，故汉明距离计算更加方便，只需两个比特序，计算其中的比特1的数目即可。
3实验分析
使用图像pHash算法进行图像文件的相似性判断，本按照视觉性&为与传。式中，事，事物的特征差距较大[⑵。因此，对于图像pHash算法，应该具有以下两个性质：
(1)类内聚合性：同一幅图像及其微小变形图像的pHash值差异应该较小。
(2)类间分离性：视觉上不同的两幅图像的pHash值差异应该较大，这样可以降低pHash冲突率。pHash冲突率，用pHash值衡性时&不同为率。
利用收集到数据集&从上述两个性质上，分析本文提岀的pHash算法，并与常用的Avg pHash算法和DCT pHash算法进行对比。接下来，将进一步介绍具体实验果。
3.1类内聚
类内聚合性测试的图像集合来自开源代码pHash库(https：///download/)o图像集合中有2$幅不同的图像，每幅图像有4个版本：基准版本(misc)、模糊版本(blur)、压缩版本(compr)、旋转版本(rotd)，中blur版本高声和椒盐噪声 见信号的处理；compr版图像经过联合图片专家组(joint photo-graphicexpertsgroup,JPEG)制准压算法
;rotd中心为定点并作轻微旋
中1幅4本3示。
©压缩(d)旋转
图$部分测试图像
分别在不同算法和不同比特数目下，计算每幅基准、模糊、压旋本pHash值，进一步得到汉明平均值和方差&表1。在表1栏目数「域，有两行数值&第一行数值是平均值&第数值是方差。例如，在$2X32图像尺寸1024比特数目下&计算幅基准AvgpHash算法下的pHash值。然后，求取两个pHash值间的汉明距离&则2$组图像产生2$个汉明距离。接下来，对该2$个汉明距离值求取平均值和方差，分别为2.782609和3.463556。
从表1可以看岀，在这个小规模图像集合上，随着图，这4种pHash算法计算 pHash值一种现象。每幅基准与、压缩、旋本图像pHash值&这意味着类内聚性“越来越好，然而这是一种假象，因为伴随压缩率高，损失的信息O也会越来越多，再去比
似性已经没有任何意义。因此，计算图像的pHash值时，比特数，否则容易 别为相同
。
此，AvgpHash算法一变化本，计算pHash值，SeqpHash算法、Laplace pHash算法和DCT pHash算法计算岀的pHash值差异较大。因此，可以得下结论：即AvgpHash
算法在类内
•786•计算机工程与设计2021年
表1基准图像与其它版本图像的汉明距离均值和方差
pHash比特数算法名称模糊压缩旋转均值和方差
2.782609 1.95652249.39130418.043478
AvgpHash
3.463556 2.88139932.33753929.099746
21.13043533.826087137.82608764.260870
SeqpHash
11.01897323.13975060.81307964.687577
102432X32)
18.78260933.478261161.39130471.217391
LaplacepHash14.17271327.64663666.09791176.679243
14.43478311.565217183.00000069.666667
DCTpHash
6.914547 5.08900090.41161995.775351
0.5652170.39130411.000000 3.985507
AvgpHash
1.0140790.82034610.6689317.944541
2.347826
3.26087021.9565229.188406
SeqpHash
2.460270
3.17897211.50228111.451568
256(16X16)
1.826087 3.39130423.0869579.434783
LaplacepHash 1.809448 2.83976610.57031511.602696
1.3043480.8695652
2.1304358.101449
DCTpHash
1.4275180.9465891
2.63984212.356005
0.2173910.043478 1.9565220.739130
AvgpHash
0.4124710.203931 2.404312 1.656364
0.3478260.347826 3.869565 1.521739
SeqpHash
0.4762800.633053 2.786682 2.356666
64(8X8)
0.2608700.173913 3.173913 1.202899
LaplacepHash0.528936
0.379035 2.631782 2.096095
0.3043480.260870 2.695652 1.086957
DCTpHash
0.6209940.605582 2.835103 2.055316
聚合性上更有优势。但是，既然相似图像的pHash值差异较小，不相同图像的pHash值差异也可能较小，即不相同的图像也可能被判断为相同或相似的图像，再次说明图像分类中关于类间分离性的讨论很有必要。
3.2类间分离性
为进一步分析pHash算法的类间分离性，采用CI-FAR-100(http：//o.edu/〜kriz/)的开源图像集合进行实验。CIFAR-100开源图像集合由32X32图像尺寸大小，共100个类的彩图像组成。其中每个类包含600幅图像，500幅用于训练的图像和100幅用于测试的图像。以下是该图像数据集合中的类，以及每个类中的一些随机图像，如图4所示。
比较图像在256比特数目下的pHash值差异。选取CI-FAR-100开源图像集合中的训练集，即100类不同景物的50000幅不同彩图像，作为本次实验的数据集。接下来，两两图像形成一对，那么这50000幅图像可以组成1249975000个图像对。采用不同pHash算法，求取每个图像对pHash值之间的汉明距离，并统计小于等于某个汉明距离的图像对的累计分布情况。
5pHash算法下数目随明
分布情况。可以看出，当汉明距离为50时，DCTpHash 算法和Avg pHash算法便开始有数量比较可观的不相同图像对被判定为相似图像对，而在此情景下，Seq pHash算法和Laplace pHash算法所对应的汉明距离为90。相对而言，Seq pHash算法和Laplace pHash算法有较高的容错率。
为进一步观察不同pHash算法下汉明距离小于50时图像对数目上存在的差距，图6给出了不同pHash算法下汉明距离小于50时图像对数目随距离分布的对数坐标变化趋势，图7给出了不同pHash算法下汉明距离小于50时图像对累计数目随距离分布情况。可以看出，Seq pHash值LaplacepHash值明50
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议