最近想自己实现一个图片去重的工具，于是就有了这篇文章。这篇文章详细地讲一下 dHash（差值哈希）算法思路和实现。之后讲汉明距离，以及快速检索汉明距离相近的两个图片的方法和实现。
简介，以及同类算法的优缺点
图片相似度判定算法有 aHash、 dHash 、 pHash 、 wHash 等。对于除 pHash 外的三种算法，本文不作详细说明，不过还是简单介绍一下它们的特点。
aHash （ Average hashing , 均值哈希）基于平均值比较，它的原理虽然非常明了，并且速度很快，但是在准确性方面不太好。据说它对平均值过于敏感，我的理解是少部分像素的变化（比如说加个水印）可能对整体的计算结果造成较大的影响，不过我没有针对这个做过实验。
pHash （ Perceptual hashing , 感知哈希）基于离散余弦变换（DCT）。在运算时只取低频信号，忽略高频信号（如噪点、较小的水印）的干扰，而且它的准确性令人满意。不过它的原理相对就没有那么简单易懂了，运算速度也会略逊一筹。
wHash （ Wavelet hashing , 小波哈希）基于离散小波变换（DWT），是 pHash 的改进算法。
dHash （ Difference hashing, 差值哈希）基于图像的变化，是一个简单实用的图像相似度判定算法。它的速度与 aHash 不相上下，但是准确性有很大提升（待考证）。并且它的原理也很简单，这是本次采用这个算法的主要原因。
需要注意的是，虽然这些算法都带一个“hash”，不过这和密码学中的“hash”并不是一个概念。后者是敏感而不容偏差的：哪怕数据只改变了一个比特，最终的散列结果也完全不同。这样的性质显然和图像去重中“模糊匹配”的目的是冲突的，因此不需要把这两种“hash”作为同类算法进行比较。
算法流程
用文字说明图像处理算法，似乎有点枯燥。那么以下举个例子吧。
灰度化与缩放
首先，既然是模糊匹配，我们将忽略图片的细微之处，将其缩放为一个统一尺寸的小分辨率的图片。另外，大部分彩色图片带有红、绿、蓝三个颜色分量，这也不便于我们处理，因此我们需要将其转为灰度图片；其实，若是三个颜色通道分开各自处理也行，不过没有必要。
灰度化和缩放两个算法，虽然平时看着简单，大部分时候我们都使用图像处理库自带的函数，但展开讲又是很多篇幅。并且，关于这两个操作的先后顺序对准确性和效率的影响，我也没有深入研究过，网上也没有说明，这里我暂且当作等价了。如果你了解其中的奥妙，不妨在评论中指点一下我，这里多谢了。
这两步操作是和 aHash 类似的。唯一不同的是，这里我们采用 9×8 的尺寸。宽度比高度多出一个像素，乍看有点奇怪，不过这也是 dHash 的独特之处。多一个像素的原因我们在接下来的操作中就能明白。这个尺寸的选取也是有讲究的，9×8 是常用的尺寸。当然也可以 17×16，3×2，但是要注意尺寸过大算法将过于敏感，过小误差较大（下面会提到）。若是将算法变形一下，8×9 也是可以的。
比较左右相邻的像素
接下来是比较。dHash采用的一行内相邻像素两两比较的方法，因此每行的比较结果会比待比较元素少一个。需要注意的是，某个像素只会和左右的像素进行比较，和上下相邻的像素没有关系。比较的具体操作是，若前一个像素的亮度大于后一个，则输出 1 ，反之输出 0；当然反过来也可以。
比如说在这个例子中，一行有9个像素，第1个与第2个比较，第2个与第3个比较... 最后是第8个与第9个比较，这样共有8个比较，图中的展示应该更加明白一点。一共有8行，我们最终长度为 8×8 = 64 bits 的比较结果，这也就是我们需要的图像特征。
到这里算法流程就结束了。是不是很简单？
Python 实现
实现也很简单。需要引入 Pillow 库。
from PIL import Image
import numpy
def dHash(path, size=8):
bitsLength = size ** 2 # 最终结果的长度
img = Image.open(path) # 打开图片
# 将图片转化为灰度化，再缩放至预定尺寸（默认 9×8 ）
arr = numpy.array(img.convert('L').resize((size + 1, size), Image.ANTIALIAS), 'f')
result = [False] * bitsLength # 初始化结果数组
for i in range(size): # 遍历每一行
startPos = i * size
for j in range(size): # 遍历一行除末尾外的所有像素
if arr[i, j] > arr[i, j + 1]: # 若当前像素的亮度大于右边，则记为 True
result[startPos + j] = True
return result
局限性
为了说明这些问题并非同类算法的通病，这里加入 pHash 的结果作为参照（由 ImageHash 库实现）。
对裁剪过于敏感
这里引入了汉明距离的概念，这会在之后的文章中详细讲述，这里只是一笔带过。简单地来说，就是至少进行多少次比特翻转（0 变成 1，1 变成 0）才可以将一个二进制串变成另一个二进制串，比如说 1001 和 1010 的汉明距离为 2。在图片相似度的判定中，汉明距离和图片差异程度正相关。据我个人测试的结果来看，差异度不大于 0.16（对于 64 位的哈希来说就是汉明距离不大于 10）的时候，可以说两张图片是基本相似的。
由图中的测试结果可以看到，裁剪程度虽然较小，并且保留了图片的主体部分，但是仍可能导致 dHash 算法的计算结果出现较大的偏差。
图片主体较小时敏感程度低
由于 dHash 在缩放操作后得到的图片尺寸是固定的，而且这个尺寸一般很小（比如说本例中的 9×8 ），这样的操作虽然可以避免分辨率不同或是图片噪点带来的干扰，但是也带来一个问题：当图片中主体部分较小（比如说有很大的白边，如上例）时，在缩放后的图片中，主体部分可能只占一个像素，也就是说主体的特征会被忽略掉，导致两张不同的图片被识别为相同的，这是我们所不希望的。相比之下 pHash 算法就聪明许多，因为它的流程中没有缩放的操作。
结言
由于我也是前几天才了解到 dHash 算法，因此文中表述可能有不准确之处，还请各位指正。当然，数据计算或者是错别字之类的也欢迎提出。
还是重复一下开头，之后如果有时间会写关于汉明距离及快速检索相似图片的原理及实现。如果有机会，到时候我会开源一个 Python 实现的、图片去重系统，基于 dHash，数据库使用 万年不变的 sqlite3。
