相似图片检测：感知哈希算法之dHash的Python实现

某些情况下，我们需要检测图片之间的相似性，进行我们需要的处理：删除同一张图片、标记盗版等。

如何判断是同一张图片呢？最简单的方法是使用加密哈希（例如MD5, SHA-1）判断。但是局限性非常大。例如一个txt文档，其MD5值是根据这个txt的二进制数据计算的，如果是这个txt文档的完全复制版，那他们的MD5值是完全相同的。但是，一旦改变副本的内容，哪怕只是副本的缩进格式，其MD5也会天差地别。因此加密哈希只能用于判断两个完全一致、未经修改的文件，如果是一张经过调色或者缩放的图片，根本无法判断其与另一张图片是否为同一张图片。

那么如何判断一张被PS过的图片是否与另一张图片本质上相同呢？比较简单、易用的解决方案是采用感知哈希算法（Perceptual Hash Algorithm)。

感知哈希算法是一类算法的总称，包括aHash、pHash、dHash。顾名思义，感知哈希不是以严格的方式计算Hash值，而是以更加相对的方式计算哈希值，因为“相似”与否，就是一种相对的判定。

如果我们要计算上图的dHash值，第一步是把它 缩放到足够小 。为什么需要缩放呢？因为原图的分辨率一般都非常高。一张 200*200 的图片，就有整整4万个像素点，每一个像素点都保存着一个RGB值，4万个RGB，是相当庞大的信息量，非常多的细节需要处理。因此，我们需要把图片缩放到非常小，隐藏它的细节部分，只见森林，不见树木。建议缩放为9*8，虽然可以缩放为任意大小，但是这个值是相对合理的。而且宽度为9，有利于我们转换为hash值，往下面看，你就明白了。

(感谢评论区 隔壁万能的小黑 同学，建议在 image.resize 中加上Image.ANTIALIAS参数，加上此参数将会对所有可以影响输出像素的输入像素进行高质量的重采样滤波)

dHash全名为差异值hash，通过计算相邻像素之间的颜色强度差异得出。我们缩放后的图片，细节已经被隐藏，信息量已经变少。但是还不够，因为它是彩色的，由RGB值组成。白色表示为（255,255,255）,黑色表示为（0,0,0），值越大颜色越亮，越小则越暗。每种颜色都由3个数值组成，也就是红、绿、蓝的值 。如果直接使用RGB值对比颜色强度差异，相当复杂，因此我们转化为灰度值——只由一个0到255的整数表示灰度。这样的话就将三维的比较简化为了一维比较。

差异值是通过计算每行相邻像素的强度对比得出的。我们的图片为9*8的分辨率，那么就有8行，每行9个像素。差异值是每行分别计算的，也就是第二行的第一个像素不会与第一行的任何像素比较。每一行有9个像素，那么就会产生8个差异值，这也是为何我们选择9作为宽度，因为8bit刚好可以组成一个byte，方便转换为16进制值。

如果前一个像素的颜色强度大于第二个像素，那么差异值就设置为True（也就是1），如果不大于第二个像素，就设置为False（也就是0）。

我们将差异值数组中每一个值看做一个bit，每8个bit组成为一个16进制值，将16进制值连接起来转换为字符串，就得出了最后的dHash值。

汉明距离这个概念不止运用于图片对比领域，也被使用于众多领域，具体的介绍可以参见Wikipedia。

汉明距离表示将A修改成为B，需要多少个步骤。比如字符串“abc”与“ab3”，汉明距离为1，因为只需要修改“c”为“3”即可。

dHash中的汉明距离是通过计算差异值的修改位数。我们的差异值是用0、1表示的，可以看做二进制。二进制0110与1111的汉明距离为2。

我们将两张图片的dHash值转换为二进制difference，并取异或。计算异或结果的“1”的位数，也就是不相同的位数，这就是汉明距离。

如果传入的参数不是两张图的dHash值，而是直接比较两张图片，那么不需要生成dHash值，直接用Step3中的difference数组，统计不相同的位数，就是汉明距离。

一般来说，汉明距离小于5，基本就是同一张图片。大家可以根据自己的实际情况，判断汉明距离临界值为多少。

https://github.com/hjaurum/DHash

感知哈希算法是一类哈希算法的总称，其作用在于生成每张图像的“指纹”(fingerprint)字符串，比较不同图像的指纹信息来判断图像的相似性。结果越接近图像越相似。感知哈希算法包括均值哈希（aHash）、感知哈希（pHash）和dHash（差异值哈希）。

aHash速度较快，但精确度较低；pHash则反其道而行之，精确度较高但速度较慢；dHash兼顾二者，精确度较高且速度较快。

在得到64位hash值后，使用汉明距离量化两张图像的相似性。汉明距离越大，图像的相似度越小，汉明距离越小，图像的相似度越大。

a) 缩放图片：为了保留图像的结构，降低图像的信息量，需要去掉细节、大小和横纵比的差异，建议把图片统一缩放到8*8，共64个像素的图片；

b) 转化为灰度图：把缩放后的图片转化为256阶的灰度图；

c) 计算平均值： 计算进行灰度处理后图片的所有像素点的平均值；

d) 比较像素灰度值：遍历灰度图片每一个像素，如果大于平均值记录为1，否则为0；

e) 构造hash值：组合64个bit位生成hash值，顺序随意但前后保持一致性即可；

f) 对比指纹：计算两幅图片的指纹，计算汉明距离。

感知哈希算法可以获得更精确的结果，它采用的是DCT（离散余弦变换）来降低频率。

a) 缩小尺寸

为了简化了DCT的计算，pHash以小图片开始（建议图片大于8x8，32x32）。

b) 简化色彩

与aHash相同，需要将图片转化成灰度图像，进一步简化计算量（具体算法见aHash算法步骤）。

c) 计算DCT

DCT是把图片分解频率聚集和梯状形。这里以32x32的图片为例。

d) 缩小DCT

DCT的结果为32x32大小的矩阵，但只需保留左上角的8x8的矩阵，这部分呈现了图片中的最低频率。

e) 计算平均值

如同均值哈希一样，计算DCT的均值

f) 进一步减小DCT

根据8x8的DCT矩阵进行比较，大于等于DCT均值的设为”1”，小于DCT均值的设为“0”。图片的整体结构保持不变的情况下，hash结果值不变。

g) 构造hash值

组合64个bit位生成hash值，顺序随意但前后保持一致性即可。

h）对比指纹：计算两幅图片的指纹，计算汉明距离。

相比pHash，dHash的速度更快，相比aHash，dHash在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。

a) 缩小图片：收缩至9*8的大小，它有72的像素点；

b) 转化为灰度图：把缩放后的图片转化为256阶的灰度图。（具体算法见aHash算法步骤）；

c) 计算差异值：计算相邻像素间的差异值，这样每行9个像素之间产生了8个不同的差异，一共8行，则产生了64个差异值；

d) 比较差异值：如果前一个像素的颜色强度大于第二个像素，那么差异值就设置为“1”，如果不大于第二个像素，就设置“0”。

e) 构造hash值：组合64个bit位生成hash值，顺序随意但前后保持一致性即可。

f) 对比指纹：计算两幅图片的指纹，计算汉明距离。

1.离散余弦变换

离散余弦变换由于为数据与余弦函数乘积累计，将无规律数列改为规则排列，如图像数据原数据为无规则二维矩阵，离散余弦变换后矩阵左上角包含图像数据的低频信息部分，右下角为高频信息部分，低频信息为图像主体框架，高频信息记录图像细节，去掉50%高频信息存储部分，图像信息量损失不超过5%(未验证此数据)，常用于图像压缩(如jpeg图像)

2.汉明距离

两个字码中不同位值的数目叫汉明距离，即a^b后验证结果的非0个数即为汉明距离

3.均值哈希算法和感知哈希算法

均值哈希算法和感知哈希算法常用于相似图像识别，将基准图缩小为较小尺寸图片，均值哈希算法计算图像平均像素值(未验证添加权值，理论可使图像部分区域具有更大权重)，然后将每个元素点与平均像素值比较，大于或等于均值，记为位1，小于均值记为位0，得到一串哈希值；感知哈希算法先进行离散余弦变换，取矩阵左上角区域数据(图像低频信息区域)，计算均值并将每个数值与均值比较，得到一串哈希值。在原图片中取相同大小图片，计算出另一串哈希值，得到两串哈希值汉明距离，值越小两张图片相似度越高

---