python - 更有效的数据结构/算法在数据库中查找相似的图像哈希

Question

我正在编写一个小的 python 程序，它试图找到与数据库中已有的图像足够相似的图像(以检测已调整大小/重新压缩/等的重复项)。我正在使用 imagehash 库和平均散列，并且想知道已知数据库中是否存在汉明距离低于 3 或 4 的散列。

我目前只使用字典将哈希值与文件名进行匹配，并对每个新图像使用暴力破解。但是，要比较数万或数十万张图像，性能开始受到影响。

我相信一定有数据结构和算法可以让我更有效地搜索，但无法找到符合我的特定用例的东西。谁能建议去哪里看？

谢谢!

Answer 1

这是一个建议。您提到了一个数据库，所以最初我会假设我们可以使用它(并且不必先将其全部读入内存)。如果您的新图像的哈希值为 3a6c6565498da525，请将其视为 4 个部分:3a6c 6565 498d a525。对于 3 或更小的汉明距离，任何匹配图像都必须有一个散列，其中至少有一个部分是相同的。因此，您可以从数据库查询开始，查找哈希值包含子字符串 3a6c、6565、498d 或 a525 的所有图像。这应该是完整数据集的一小部分，因此您可以对其进行比较。

要进一步改进，您可以预先计算所有部分并将它们作为附加列单独存储在数据库中。这将允许更高效的查询。

对于更大的汉明距离，您需要将哈希拆分为更多部分(更小，或者您甚至可以使用重叠的部分)。

如果您想在字典中完成所有操作，而不是使用数据库，您可以将这些部分用作每个指向图像列表的键。为简单起见使用单个字典，或者为了更准确的匹配，为每个“位置”使用一个字典。

同样，这将用于获取更小的候选匹配集以运行完整比较。