在固定长度的六角形列表中找到最小汉明距离的最快方法

Question

我在 Python 中使用 Imagehash 来生成大约 30,000 张图像的 48 位十六进制哈希值，我将其存储在字典列表中（phashes 以及其他一些图像属性）。例如：

[{"name":"name1", "phash":"a12a5e81127d890a7c91897edc752b506657233f56c594b7e6575e24e457d465"},
 {"name":"name2", "phash":"a1aa7e011367812a7c9181be9975a9e86657239f3ec09697e6565a24e50bf477"}
 ...
 {"name":"name30000", "phash":"a1aa7e05136f810afc9181ba9951a9686617239f3ec4d497e6765a04e52bfc77"}]

然后我从 Raspberry Pi 获得视频输入，该视频已被分段，并将该哈希与该数据库进行比较（考虑到 Pi 相机的性质，来自视频流的测试哈希永远不会匹配数据库中的哈希值）。现在我正在做一个愚蠢的循环，它需要大约 5 秒来循环并检查 ~30,000 个预先计算的哈希值中每个哈希值的汉明距离，这太慢了。我使用的 Imagehash 库意味着汉明距离可以简单地通过 dbHash1 - testHash 来计算。显然排序和做 bisect 不是解决这个问题的方法，因为排序与汉明距离无关。所以，我认为必须有更快的方法来完成这项工作？我已经阅读了 this question 关于度量空间的内容，但我想检查是否有人知道（相对）简单的 Python 实现。

Answer 1

Scipy's pairwise distance function 支持汉明距离。我会试试的。

Answer 2

我从 ImageHash 背后的人那里得到了答案，Johannes Buchner。

我可以将数据库存储为二维矩阵：

arr = []
for dbHash in db:
    arr.append(dbHash.hash.flatten())
arr = numpy.array(arr)

然后我可以同时对所有人进行比较：

binarydiff = arr != testhash.hash.reshape((1,-1))
hammingdiff = binarydiff.sum(axis=1)
closestdbHash_i = numpy.argmin(hammingdiff)
closestdbHash = db[closestdbHash_i]

在固定长度的六角形列表中找到最小汉明距离的最快方法

Quickest way to find smallest Hamming distance in a list of fixed-length hexes

python

hamming-distance