如何识别稍微修改过的图片？

Question

我有一个非常大的JPEG图像数据库，大约有200万张。 我想在这些图像中进行模糊搜索以查找重复图像。 重复图像是指两个图像具有许多（大约一半）像素具有相同值，其余像素的R / G / B值相差约+/-3。 肉眼无法区分这些图像。 这是重新压缩JPEG所产生的差异。

我已经有一种绝对可靠的方法来检测两个图像是否相同：我对所有像素的亮度差进行求和并将其与阈值进行比较。 这种方法已被证明100％准确，但是针对200万张图片的处理速度极慢（每张图片需要几小时）。

我希望以某种方式对图像进行指纹识别，以便只需比较哈希表中的指纹即可。 即使我可以可靠地将需要比较的图像数量缩小到只有100张，我也可以轻松地将1张与100张进行比较。 有什么好的算法可以做到这一点吗？

- Eyal

Answer 1

请查看O. Chum、J. Philbin和A. Zisserman在2008年英国机器视觉会议上所发表的论文《近似重复图像检测：min-hash和tf-idf加权》，链接为http://www.robots.ox.ac.uk/~vgg/publications/papers/chum08a.pdf。他们解决了您所面临的问题，并演示了对146k张图像的结果。然而，我对他们的方法没有亲身经历。

- Malte Clasen

---

很高兴在 Stack Overflow 上看到同行评议的出版物。+1 - Norman Ramsey

我使用了min-Hash并取得了惊人的结果。简而言之：24小时内索引了100万张照片。每秒分类20张图片。感谢指引！ - Eyal

这是代码：https://blogs.msdn.microsoft.com/spt/2008/06/10/set-similarity-and-min-hash/ - dadhi

对于阅读论文并想知道什么是视觉单词的其他人（假定您已经知道）... https://towardsdatascience.com/bag-of-visual-words-in-a-nutshell-9ceea97ce0fb - AnotherHowie

Answer 2

天真的想法：创建一个小缩略图（50x50像素）来查找“可能相同”的图像，然后增加缩略图大小以丢弃更多的图像。

- Carlos Gutiérrez

---

我不明白。我尝试比较小图像，25x25，它们也有肉眼看不见的差异。 - Eyal

@Eyal - 如果在25x25的两个图像看起来相同，它们可能仍然不同，但如果它们看起来不同，它们就是不同的。您已经有了一个检测相同图像的算法，但速度很慢。因此，我的建议是首先创建一个子集，其中在25x25处看起来相同的图像，并且丢弃其余的图像。然后创建该子集的50x50图像并再次进行比较，更多的图像将被丢弃。然后再在100x100处进行比较，以此类推。每次迭代的想法是对于每个图像，您都会有一个更加CPU/磁盘密集型的过程，但是图像数量更少（如果我没有理解您的问题，对不起）。 - Carlos Gutiérrez

你需要限制色彩空间。RGB 图像有 2^(38) == 16777216 种颜色。降低分辨率的图像颜色会略微不同并产生不同的哈希值。尝试将颜色空间限制在例如 2^(32) == 64 种颜色。然而，这也不是理想的，因为图片中的小变化可能会使像素进入不同的缩小后的颜色。也许还可以加权平均颜色变化，如果它们没有超过阈值，则报告匹配。也许像 YUV420 这样的 YUV 色彩模型变体更适合人眼感知差异的方式。 - nalply

Answer 3

在MinHash的基础上，我的想法是使用数据库中所有图像来创建100个查找表。这些查找表将亮度相同的特定像素映射到具有该像素相同亮度的图像列表。要搜索图像，只需将其输入哈希表，获取100个列表，并在每次图像出现在列表中时为其评分一次。每个图像的得分从0到100不等，得分最高的图像获胜。

如何在合理的内存限制内快速完成此操作存在许多问题。需要适当的数据结构来进行磁盘存储。还可以调整哈希值、表格数量等。如果需要更多信息，我可以进一步扩展。

我的结果非常好。我能够在一台计算机上约24小时内索引一百万张图像，并且我可以每秒查找20张图像。根据我所知，准确性令人惊叹。

- Eyal

---

我希望看到你写一篇关于它的博客文章。 - Lothar

Answer 4

我认为这个问题无法通过哈希解决。难点在于：假设你有一个红色像素，并且您想要3和5哈希到相同的值。那么，您还希望5和7哈希到相同的值，以及7和9等等...您可以构建一个链表，表示您希望所有像素都哈希到相同的值。

相反，我会尝试以下方法：

1. 建立一个庞大的B树，每个节点具有32路分支，其中包含所有图像。
2. 树中所有图像尺寸相同或不重复。
3. 为每个彩色像素赋以唯一编号，从零开始。左上角可能会被编号为R、G、B分量的0、1、2，或者使用随机排列可能更好，因为您将按照该编号顺序比较图像。
4. 第n层的内部节点按照像素n除以8的值进行32路区分（这可以去除附近像素中的一些噪声）。
5. 叶节点包含少量图像，比如10到100张。或者，图像数是深度的递增函数，所以如果有500张图像的副本，经过一定的深度后您就停止尝试区分它们。

当树中插入了一百万个节点时，只有在它们位于同一节点时，两个图像才是重复的。对吗？错了！如果两个图像的像素值分别为127和128，则一个进入outedge 15，另一个进入outedge 16。因此，实际上，当您根据像素进行区分时，您可能会将该图像插入到一个或两个子节点中：

• 对于亮度B，请在B/8、(B-3)/8和(B+3)/8处插入。有时所有3个值都相等，而总有2个值相等。但是，有3/8的概率会使图像出现在额外的outedges上。根据深度的不同，您可能会有很多额外的节点。

别人需要计算一下，看看是否需要除以比8更大的数，以避免图像重复太多。好消息是，即使真正的扇出只有4而不是32，你只需要一个深度为10的树。在10次重复中，将你带到了叶子节点的3200万个图像。我希望你有足够的RAM可供使用！如果没有，你可以把树放在文件系统中。

让我知道进展如何！

- Norman Ramsey

---

你的推理表明，对于任何基于相似性的哈希函数，必须存在一些具有不同哈希值的相似图像。希望大多数相似的图像不会出现这种情况。此外，适当的哈希函数可以为您提供一种计算两个图像之间“距离”的有效方法，使得相似的图像比不相似的图像具有更小的距离。 - augurar

Answer 5

关于缩略图的哈希算法还有一个好处：即使稍作修改，也能识别出缩放后的重复图片。

- Jared Pochtar