为了实现对大量图片的重复检测，我们用python实现了dHash感知散列算法和漂亮的BK树数据结构。
我们的网站有着近十五万的高清旅游照片，而且还在不断增加。这些照片来自各种来源，并以半自动的方式上传。所以经常有重复或几乎相同的照片，但是我们不希望我们的图片搜索页面充满重复。
所以我们决定使用感知散列算法（perceptual hashing）自动化过滤重复图片。感知散列就如普通哈希一样，它是一个比较大的数据片段的相对小的可比较的指纹。但它与典型的哈希算法不同在于，如果原始图像是相近的，感知散列值也"相近"（或相等）。
差分散列（dHash）
-
我们使用的感知哈希名为dHash，是由Neal Krawetz在他的照片取证工作中开发的。它非常简单而惊人的有效。该算法包含以下步骤（生成一个128位的哈希值）：
- 将图片转为灰阶
- 缩小为9x9平方的灰度值（或者大点为17x17，512位哈希值)）
- 计算"行哈希"：对每一行从左到右移动，如果下一个像素点的灰度值大于或等于上一个，则输出1，否则输出0（每行9个像素点，产生8位的输出）
- 计算"列哈希"：就像行哈希，但对每列从上到下移动
- 将上面计算出的两个64位值串联到一起，合成最终的128位哈希值
dHash很棒，因为它相当准确，而且非常易于理解和实现。它也非常快速（Python可能不擅长位操作，但是灰度化和缩小图像这些艰苦的工作都由C库完成了：ImageMagick+wand 或 PIL，封装好供python使用）
-
下面是形象化的图像处理过程：
灰度化并缩小到9x9（放大了查看）：
以及最后的8x8的行和列的哈希值，也放大了（黑色为0，白色为1）：
dHash的核心代码只是简单的嵌套
for循环：
def dhash_row_col(image, size=8):
width = size + 1
grays = get_grays(image, width, width)
row_hash = 0
col_hash = 0
for y in range(size):
for x in range(size):
offset = y * width + x
row_bit = grays[offset] < grays[offset + 1]
row_hash = row_hash << 1 | row_bit
col_bit = grays[offset] < grays[offset + width]
col_hash = col_hash << 1 | col_bit
return (row_hash, col_hash)
- 它很简单，但也会有几个棘手的案例，所以我们很nice地将代码开源到GitHub以及Python Package Index——只需要
pip install dhash即可使用。
重复的阈值
- 为了判断一个图片是否重复，可以比较它们的dHash值。如果值相同，那么图片几乎是一样的。如果它们的哈希值只有几位不同，那么图片是相似的——所以你需要计算两个值之间位不同的数量（汉明距离），然后判断它是否低于给定的阈值。
-在我们的dhash库中有个辅助函数get_num_bits_different()来计算这个差值。奇怪的是，Python中最快的处理方式是异或两个值，将结果转换为二进制字符串，然后计算'1'的数量（这是因为用C编写的内建函数来做艰苦的工作和循环）:
def get_num_bits_different(hash1, hash2):
return bin(hash1 ^ hash2).count('1')
- 对我们的图片集（总共超过20w），我们设置128位的dHash阈值为2。也就是说，如果哈希值相等或只有1-2位不同，就认为它们是重复的。在我们的测试中，这是一个足够大的差值来捕获大多数重复图片。当我们尝试设置为4或5时，它开始出现异常——看上去十分不同的图像会具有相似的指纹。
-
例如，下面这对图片让我们将阈值定为2——它们只有4位的差异：
MySQL位计数
- 尽管我是PostgreSQL的狂热粉，但是我们在这个项目使用了MySQL，它具有一个干净快捷的小功能，而PostgreSQL不具有， 那就是
BIT_COUNT——计算64位整数的1的位数。因此，如果将128位哈希分解成两部分，你可以使用两个BIT_COUNT()调用来确定二进制哈希列是否在给定哈希的n位之内。 - 这有点迂回，因为MySQL似乎没有办法将二进制列的一部分转换为64位整数。所以我们转换为16进制又转换回来（如果你知道有更好的办法希望能告诉我们）。SQL表中的dHash列名为
dhash8，而dhash8_0和dhash8_1分别是我们进行比较的新哈希值的高低64位字面值。 - 所以这里是我们上传新图像时用来检测重复的查询（嗯，实际上我们用的是SQLAlchemy ORM，不过也没差了）（SQL语句参看）：
SELECT asset_id, dhash8
FROM assets
WHERE
BIT_COUNT(CAST(CONV(HEX(SUBSTRING(dhash8, 1, 8)), 16, 10)
AS UNSIGNED) ^ :dhash8_0) + -- high part
BIT_COUNT(CAST(CONV(HEX(SUBSTRING(dhash8, 9, 8)), 16, 10)
AS UNSIGNED) ^ :dhash8_1) -- plus low part
<= 2 -- less than threshold?
- 以上是一个相对较慢的查询，涉及全表扫描，但是我们只在上传时做一次，所以花费额外的一两秒不是什么大事。
BK树与更快的重复检测
- 但是，当我们在整个图片集中搜索存在的重复时，它很快就变成了一个O(N^2)复杂度问题——对每一个图片要遍历所有其它图片来查找是否重复。对数十万的图片，这太慢了，所以我们需要改进——BK树。
- 一个BK树是一个n元树数据结构，专门为快速找到相近的匹配而设计。例如，找到给定字符串的某个编辑距离内的其它字符串。或者在我们的案例中，找到给定dHash值的某个位距离内的其它dHash值。这将一个O(N^2)问题转化为近于O(logN)问题。(作者的幽默 - We discovered a truly marvelous proof of this, but the margin is too narrow to contain it.)
- BK树在Nick Johnson的"非常酷的算法"系列博客中有阐述。（在国人Matrix67的博客中也有清晰的描述，很容易理解）
- BK树的结构相当简单，特别是在python中，只需要一堆嵌套的字典(与元组)即可。下面是
BKTree.add()函数的代码，用于为BK树添加一个子项：
def add(self, item):
node = self.tree
if node is None:
self.tree = (item, {})
return
while True:
parent, children = node
distance = self.distance_func(item, parent)
node = children.get(distance)
if node is None:
children[distance] = (item, {})
break
- 有一些现成的BK树的实现，不过这一个好像对我们的使用来说有些问题(ryanfox/bktree)，另一个看上去不错但没放在PyPI上 (ahupp/bktree)，所以我们自己弄了个——GitHub与Python Package Index -
pip install pybktree安装。
讨论
- Hacker News 和 reddit Python参与讨论。
