基于哈希的图像相似度算法比较研究

黄嘉恒，李晓伟，陈本辉，杨邓奇

（大理大学数学与计算机学院，云南大理 671003）

图片相似度检测是对两张或多张图片的内容相似程度进行分析对比，或检测某张图片的内容是否包含在另一图片内。图片相似度比较被广泛应用于基于图片的搜索引擎、目标检测、照片过滤、文献查重等多个领域。

输入图片到搜索引擎可以检索出搜索引擎数据库中包含目标图片的所有链接。通过提取目标照片特征来检测照片中是否存在目标物体，实现图片内容过滤、图片筛选和分类。在网络安全领域，通过对不雅图片、不良图片（如包含色情、反动标语等的图片）进行采样，提取不雅、不良图片的指纹特征，检测图片中是否存在不雅、不良内容；将图片相似度检测算法应用于网关设备，可以实现基于图片的互联网不良内容检测，净化网络环境。在生态保护领域，利用红外相机对野生动物进行非入侵、无干扰、全天候的实时监控变得越来越受欢迎〔1〕。根据红外相机的触发机制，当动物经过红外相机的镜头视野时会触发相机自动拍摄一组连续的照片，实现对生态保护区野生动物的观测、统计与研究〔2-3〕。但实际应用中，除了动物经过镜头外，镜头内的任何风吹草动也会触发红外相机自动拍摄而产生空照片。实际上，红外监测拍摄到的照片中大部分是没有捕获到动物影像的空照片。Diaz等〔4〕所拍摄到的20万张照片中，成功捕获到动物的照片仅占1%；位于坦桑尼亚西北部的塞伦盖蒂平原的320万张红外监测照片数据集中75%都是空照片〔5〕。当前生态学领域的研究者对红外空照片的分拣都靠人工完成，存在工作效率低、人力成本高、易出错等问题。利用照片相似度比较实现红外空照片自动过滤可以节省大量的人力成本、提高工作效率。

本文研究基于哈希的图像相似度检测算法，通过对均值哈希（Average Hash，aHash）算法、感知哈希（Perceptual Hash，pHash）算法和差异值哈希（Deference Hash，dHash）算法进行分析，研究各算法在图片相似度检测方面的优缺点，并基于相同照片组对不同精度下3个图像哈希算法的检测精度和性能进行细粒度测试，为其他研究者选择基于哈希的图像相似度检测算法提供理论依据和数据参考。

1 相关工作

图像相似度比较被广泛应用于图像搜索、目标识别、照片过滤等领域。邹承明等〔6〕基于颜色直方图提出一种改进的图形特征计算和相似度比较算法。潘楠等〔7〕基于SIFT算法计算图片指纹特征，并根据相似度比较实现犯罪工具图片快速溯源。郭仪权等〔8〕将图像哈希算法应用于多目标跟踪，利用图像哈希算法计算图像指纹，然后通过对比跟踪目标在相邻时刻照片的相似度，实现目标跟踪。李恩等〔9〕利用aHash算法实现人脸特征计算，并通过比较特征来判断人脸相似度。干丽萍等〔10〕利用pHash算法提取学生图片格式作业的特征，检测学生作业的相似度以发现学生抄袭作业的行为。这些研究主要是对算法的直接利用或改进，没有对3个图像哈希算法进行细粒度的比较，无法为算法选择提供参考。姚永明等〔11〕对aHash和pHash算法进行了简单的介绍，并利用MATLAB对两个算法进行了仿真测试，但并没有对两个算法在相似度检测精度和性能方面做出比较，不能为其他研究者在选择算法时提供决策依据。

2 图像哈希算法

图片本质上是一个二维信号，它由多个不同频率成分构成。图片中低频成分对应亮度变化较小的区域，高频成分对应亮度变化较大的区域。低频成分对应图像大块区域，是对整幅图像强度的综合度量；高频成分对应图片的细节，是对图像边缘和轮廓的度量。通过缩小图片可以快速去除图像的高频成分，通常将图片缩小到8×8、16×16、32×32、64×64等尺寸，尺寸越小图像细节保留越少，图像越不清晰。图1分别给出原图及其被缩放到64×64、32×32、16×16、8×8大小后，按相同尺寸显示的图片效果。方便起见，本文用n×n来描述图片缩小后的尺寸。

图1 原图与缩小到不同尺寸的图片

2.1 aHash算法aHash算法设计比较简单，主要利用图片的低频成分，通过缩小图片去除图片的高频成分，保留低频信息，并使用图像灰度方法化去除图像色彩来进一步去除高频成分。在此基础上，计算灰度图的像素平均值。遍历灰度图每一像素，将其与像素均值做比较，若大于均值，则记下1；否则，记下0，得到二进制串即为图像Hash值，也称为图像指纹。具体算法描述如下：

步骤1：将图片缩小到n×n，共n2个像素；

步骤 2：将n×n图片转换为灰度图，记为Ga；

步骤 3：计算灰度图Ga的像素平均值，记为pavg；

步骤4：遍历Ga中每一个像素pi，并将pi与pavg进行比较，若pi≥pavg，则记下1，否则记下0，得到n2个比特的二进制串即为图片aHash值，记为Ha；

步骤 5：计算两张图片哈希值的海明距离，距离越小图片越相似，距离越大图片差异性越大。

2.2 pHash算法任何图像都可以用频率域表示，将图像表示为由不同频率分量叠加而成的形式。图像转换到频率域后，大部分频率分量对应的系数很小，只有少数频率分量对应的系数较大，且系数较大的值一般集中在系数矩阵的左上角，沿对角线方向越往右下角则系数矩阵元素值越小。因此，左上角部分保留了图片的绝大多数信息。

pHash算法首先利用离散余弦变化（Discrete Cosine Transform，DCT）将图像从像素域变换为频率域，再保留其频率系数矩阵的左上角区域元素来计算图像哈希，能增加更多的图像细节。DCT变换如（1）所示：

其中x，y是像素域中元素的坐标，f(x,y)是对应元素的值，n是像素矩阵的阶。u，v是频率域中元素的坐标，F（u，v）是转换后频率域的系数矩阵的元素，将系数矩阵记为Mn×n，如（2）所示，其中mk×k，为左上角k×k矩阵。

pHash算法描述如下：

步骤1：将图片缩小到n×n，共n2个像素；

步骤2：将n×n图片转换为灰度图，记为Gp；

步骤3：进行DCT变化并取系数矩阵左上角的k×k矩阵，Mn×n=DCT（Gp），mk×k=Top_left（Mn×n）。

步骤 4：计算mk×k矩阵元素的平均值，记为eavg；

步骤 5：遍历mk×k中每一个元素ei，并将ei与eavg进行比较，若ei≥eavg，则记下1，否则记下0，得到k2个比特的二进制串即为图片aHash值，记为Hp；

步骤 6：计算两张图片哈希值的海明距离，距离越小图片越相似，距离越大图片差异性越大。

2.3 dHash算法dHash算法基于像素域，根据相邻像素之间的差异（即像素值间的大小关系）来计算图片哈希，若两幅图的像素间关系越接近，则说明两幅图越相似。相邻像素的比较在像素矩阵的同一行进行，若左边的像素值大于右边的像素值，则记为1，否则为0。因此，对比完像素矩阵的所有行后即得到图像的哈希值。为了得到k2个比特的哈希值，需要将图片缩小为（k+1）×k大小，因为k+1个元素之间有k个不同的差异，一共k行，可以产生k2个差异值，对应k2个比特的二进制串。dHash算法描述如下：

步骤1：将图片缩小到（k+1）×k；

步骤 2：将（k+1）×k图片转换为灰度图，记为Gd；

步骤3：遍历像素矩阵每一行，从左到右比较相邻两个像素值，若左边大于右边，则记下1，否则记下0，遍历完所有行后，得到一个k2个比特的二进制串即为图片dHash值，记为Hd；

步骤 4：计算两张图片哈希值的海明距离，距离越小图片越相似，距离越大图片差异性越大。

3 算法分析与测试

3.1 算法分析aHash、pHash和dHash 3个算法都可用于计算图片的特征指纹、检测图片相似度。

aHash算法基于像素域设计，原理简单，实现速度快，图片尺寸缩放对图片哈希值的影响较小；但图像进行伽马校正或直方图均衡对图像哈希值影响较大。更适用于根据缩略图检索原图。

pHash算法基于频域实现，通过离散余弦变换极大地保留了图片中低频成分，相比于aHash算法，pHash保留了更多的细节。pHash算法能够容忍对图片做出少量的修改，只要保持图片的整体结构不变，则其哈希值基本保持不变，能够避免伽玛校正或颜色直方图调整的影响。但相对来说，离散余弦变换比较耗时，因此，3个算法中，pHash速度最慢。

dHash算法设计是基于渐变实现的。在识别效果方面，dHash算法优于aHash算法，但不如pHash算法。在实现速度方面，dHash算法优于pHash算法，但不如aHash快。

3.2 算法测试算法测试包括相似度检测效果测试和性能测试两个方面。为了对3个算法的识别效果和实现速度进行细粒度的比较，本文从位于坦桑尼亚西北部的塞伦盖蒂平原红外监测照片数据集中挑选了6组照片进行测试，分别标记为a、b、c、d、e、f，如图2所示。每组包含2张照片，a（1），a（2）为一组，记为a；b（1），b（2）为一组，记为b；以此类推。为了尽可能进行全面的比较，测试照片既有白天拍摄的，也有夜间拍摄的，还有意选择了一组动物移动较快的照片。图2中的照片均为红外相机自动拍摄的照片，其中c、d两组照片在夜间拍摄，其他均在白天拍摄。第c组照片动物正在移动且速度较快，照片部分区域比较模糊。

图2 塞伦盖蒂平原红外监测照片

相似度检测效果测试：

分别比较图2中每一组中两张照片的相似度（以百分比记）。表1中第一列a、b、c、d、e、f分别对应图2中的6组照片。对每一组内的两张照片，分别用aHash、pHash和dHash 3个算法进行测试。测试时，对于3个图像哈希算法，本文均将图片分别缩放到8×8、16×16、32×32和64×64 4种不同的尺寸进行测试比较。表1中具体行、列对应的元素值表示该行对应的组内两张照片，在该列对应的图像哈希算法和缩放尺寸下的相似度（单位为%）。从表1可以发现：①缩放8×8尺寸的照片后，3种算法比较出来的相似度均偏高，这是因为原图被缩小太多后，多数细节信息已经丢失的原因；②随着缩放尺寸的增大，图片保留的信息增加，相似度呈减小趋势，说明了两个不完全相同的图片保留的细节越多差异越大；③aHash算法对图片的区分度较小，pHash和dHash两个算法对图片的区分度明显优于aHash；④dHash算法相似度取值区间比较集中，pHash算法相似度取值区间比较分散；⑤pHash和dHash均能较好的反映图片之间的相似程度，但随着缩放尺寸的增大，pHash算法能更好地反映图片之间的真实相似程度。

表1 图像哈希算法在不同缩放尺寸下的相似度比较（%）

性能测试：

对aHash、pHash和dHash算法在8×8、16×16、32×32和64×64这4种不同尺寸下的实现速度进行测试及比较。测试环境使用普通的台式计算机，其主要硬件配置为：i5-4690K 3.50 GHz四核CPU，8 GB内存；计算机操作系统为Windows 8.1 64位，编程语言使用Python 3.5。

测试数据集仍然采用塞伦盖蒂平原红外监测照片数据集，随机选择了50组、100组、300组、600组和1 200组照片进行组内照片比较，每组有3张照片（该数据集拍摄时红外相机参数设置为每次连续拍摄3张照片），每组均进行3次比较，则对应的相似度计算次数分别为150次、300次、900次、1 800次和3 600次。

性能测试如图3所示，图3（a）、图3（b）分别表示原图被缩小到8×8、16×16时3个算法的时间花费。可以发现，在图片尺寸较小、计算次数较少时，3个算法时间花费差别并不明显，随着计算次数增加计算性能才逐渐有所区分。图3（c）、图3（d）分别表示原图被缩小到32×32、64×64时3个算法的时间花费，可以看出，计算次数超过900次后，pHash算法时间花费明显高于aHash和dHash，但aHash与dHash算法时间花费差别仍然不明显。

图3 3种算法在不同尺寸下时间花费比较

4 结束语

理论分析和实验结果均表明，3个图像哈希算法在图像相似度检测方面各有优缺点。本文通过原理分析和实验测试的方式对3个算法在图像相似度检测方面的效果和性能进行了全面的评估，给出了相关的实验数据，为其他学者提供数据参考。根据实验测试数据及具体应用领域对识别效果和检测速度要求，可以为不同的应用选择合适的算法。也可以结合3个算法的设计原理和实验数据，对3个算法在精度和速度方面进行改进。

〔1〕HARRIS G，THOMPSON R，CHILDS J L，et al.Auto⁃matic storage and analysis of camera trap data〔J〕.The Bulletin of the Ecological Society of America，2010，91（3）：352-360.

〔2〕PIDGEON A M，RADELOFF V C，FLATHER C H，et al.Associations of forest bird species richness with housing and landscape patterns across the usa〔J〕.Eco⁃logical Applications，2007 ，17：1989-2010.

〔3〕 BOWKETT A E，ROVERO F，MARSHALL A R.The use of camera-trap data to model habitat use by ante⁃lope species in the udzungwa mountain forests，tanza⁃nia〔J〕.African Journal of Ecology，2008，46（4）：479-487.

〔4〕 DIAZ-PULIDO，GARRIDO A P，ESTEBAN.Densidad de ocelots（leopardus pardalis） en los llanos colombia⁃nos〔J〕.Mastozoologia Neotropical，2011，18（1）：63-71.

〔5〕 NOROUZZADEH M S，NGUYEN A，KOSMALA M.Automatically identifying wild animals in camera trap imageswithdeeplearning 〔EB∕OL〕. 〔2017-01-05〕.https:∕∕arxir.org∕abs∕1703.05830V1.

〔6〕邹承明，薛栋，郭双双，等.一种改进的图像相似度算法〔J〕. 计算机科学，2016，43（6）：72-76.

〔7〕潘楠，阚立峰，刘益.犯罪工具图片快速溯源技术研究〔J〕.昆明理工大学学报（自然科学版），2017，42（3）：52-59.

〔8〕郭仪权.基于哈希的多目标跟踪算法的研究〔D〕.合肥：安徽大学，2017.