图像哈希指纹碰撞（dHash）

Question

我在一个非常庞大的图像集中使用dHash (http://www.hackerfactor.com/blog/index.php?url=archives/529-Kind-of-Like-That.html)。默认的调整大小为8像素：

def dhash(image, hash_size=8):
    """
    Difference Hash computation.
    following http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html
    @image must be a PIL instance.
    """
    image = image.convert("L").resize((hash_size + 1, hash_size), Image.ANTIALIAS)
    pixels = numpy.array(image.getdata(), dtype=numpy.float).reshape((hash_size + 1, hash_size))
    # compute differences
    diff = pixels[1:, :] > pixels[:-1, :]
    return ImageHash(diff)

如果我们将这个算法应用于大量图像，那么由于短哈希指纹，我不会遇到碰撞吗？

最好的hash_size是多少？hash_size越大不是更准确吗？它选择8是因为有特殊原因吗？

- user1618465

Answer 1

我最近查看了几百万个dhashes的统计数据。分布非常接近均匀，也就是说，至少我的数据集没有任何模式，比如图像倾向于在上半部分更亮等。

这意味着碰撞的概率接近每个位的独立二项式情况。如果我没记错的话，8x8像素意味着您保存的哈希值为64位。有264 = 1.8 x 1019种可能的哈希值，这很多。生日悖论再次使我们失望，因此您预计将在第40亿张图像中看到第一个碰撞。

- Matthias Winkelmann

Answer 2

你可以通过计算Y值上的差异来创建一个次要的DHash，而不是像你在这里做的那样计算X值：

pixels[1:, :] > pixels[:-1, :]

使用两个DHash可以减少碰撞的可能性（但不能完全消除）。

如果您想更进一步，甚至可以将PHash（更精确但速度较慢的算法）加入到混合中。在这种情况下，如果有任何碰撞，则创建两个图像的PHash进行比较。

最后，您可以使用比8x9更大的图像计算哈希。这将减少误报的可能性，但也会增加忽略图像的机会。

- Isaac Paul