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

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

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

汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。例如:

1011101与1001001之间的汉明距离是2。 2143896与2233796之间的汉明距离是3。 "toned"与"roses"之间的汉明距离是3。

aHash

  1. 缩放图片:为了保留图像的结构,降低图像的信息量,需要去掉细节、大小和横纵比的差异,建议把图片统一缩放到8*8,共64个像素的图片;
  1. 转化为灰度图:把缩放后的图片转化为256阶的灰度图;

    灰度图相关算法(R = red, G = green, B = blue) 对于彩色转灰度,其基础的心理学公式为: Gray = R0.299 + G0.587 + B0.114,部分变种也很流行:

    • 浮点算法:Gray=R0.3+G0.59+B0.11;
    • 整数方法:Gray=(R30+G59+B*11)/100;
    • 移位方法:Gray =(R76+G151+B*28)>>8;
    • 平均值法:Gray=(R+G+B)/3;
    • 仅取绿色:Gray=G;
  2. 计算平均值: 计算进行灰度处理后图片的所有像素点的平均值;

  3. 比较像素灰度值:遍历灰度图片每一个像素,如果大于平均值记录为1,否则为0;

  4. 构造hash值:组合64个bit位生成hash值,顺序随意但前后保持一致性即可;

  5. 对比指纹:计算两幅图片的指纹,计算汉明距离。

pHash

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

  1. 缩小尺寸 为了简化了DCT的计算,pHash以小图片开始(建议图片大于8x8,32x32)。

  2. 简化色彩 与aHash相同,需要将图片转化成灰度图像,进一步简化计算量(具体算法见aHash算法步骤)。

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

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

    DCT变换的全称是离散余弦变换(Discrete Cosine Transform),主要用于将数据或图像的压缩,能够将空域的信号转换到频域上,具有良好的去相关性的性能。DCT变换本身是无损的,但是在图像编码等领域给接下来的量化、哈弗曼编码等创造了很好的条件,同时,由于DCT变换时对称的,所以,我们可以在量化编码后利用DCT反变换,在接收端恢复原始的图像信息。对原始图像进行离散余弦变换,变换后DCT系数能量主要集中在左上角,其余大部分系数接近于零,DCT具有适用于图像压缩的特性。将变换后的DCT系数进行门限操作,将小于一定值得系数归零,这就是图像压缩中的量化过程,然后进行逆DCT运算,可以得到压缩后的图像。 离散余弦变换的原理: 一维DCT变换: 一维DCT变换 其中,f(i)为原始的信号,F(u)是DCT变换后的系数,N为原始信号的点数,c(u)可以认为是一个补偿系数,可以使DCT变换矩阵为正交矩阵。 二维离散余弦变换的正变换公式为: 二维离散余弦变换

  5. 计算平均值 如同均值哈希一样,计算DCT的均值

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

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

  8. 对比指纹:计算两幅图片的指纹,计算汉明距离。

dHash

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

  1. 缩小图片:收缩至9*8的大小,它有72的像素点;
  2. 转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见aHash算法步骤);
  3. 计算差异值:计算相邻像素间的差异值,这样每行9个像素之间产生了8个不同的差异,一共8行,则产生了64个差异值;
  4. 比较差异值:如果前一个像素的颜色强度大于第二个像素,那么差异值就设置为“1”,如果不大于第二个像素,就设置“0”。
  5. 构造hash值:组合64个bit位生成hash值,顺序随意但前后保持一致性即可。
  6. 对比指纹:计算两幅图片的指纹,计算汉明距离。