21

我有一个非常大的 jpeg 图像数据库，大约 200 万张。我想对这些图像中的重复项进行模糊搜索。重复图像是两个图像，它们的许多（大约一半）像素具有相同的值，其余的 R/G/B 值相差约 +/- 3。图像与肉眼相同。这是您从重新压缩 jpeg 获得的那种不同。

我已经有一种万无一失的方法来检测两个图像是否相同：我将所有像素的增量亮度相加并与阈值进行比较。这种方法已被证明 100% 准确，但对 200 万张照片进行 1 张照片的速度非常慢（每张照片需要数小时）。

我想以一种可以比较哈希表中的指纹的方式对图像进行指纹识别。即使我可以可靠地将需要比较的图像数量减少到仅 100 个，我也可以很好地比较 1 到 100 个。什么是一个好的算法呢？

4

5 回答 5

19

查看 O. Chum、J. Philbin 和 A. Zisserman，近重复图像检测：min-hash 和 tf-idf 加权，在英国机器视觉会议论文集，2008 年。他们解决了您遇到的问题并演示了146k 图像的结果。但是，我对他们的方法没有第一手经验。

于 2010-01-31T17:55:44.547 回答
3

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

于 2010-01-30T18:18:03.597 回答
2

基于 minHash 的思想...

我的想法是使用数据库中当前的所有图像制作 100 个查找表。查找表从特定像素的亮度映射到在同一像素中具有相同亮度的图像列表。要搜索图像，只需将其输入哈希表，获取 100 个列表，并在每个图像出现在列表中时为每个图像打分。每张图片都会有一个从 0 到 100 的分数。得分最多的图片获胜。

如何在合理的内存限制内执行此操作以及如何快速执行此操作存在许多问题。在磁盘上存储需要适当的数据结构。也可以调整散列值、表数等。如果需要更多信息，我可以对此进行扩展。

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

于 2010-02-04T14:14:01.703 回答
1

我不认为这个问题可以通过散列来解决。困难在于：假设您有一个红色像素，并且您希望 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处插入。有时所有 3 将相等，并且总是 2 of 3 将相等。但是以 3/8 的概率，您将出现图像的边缘数量增加一倍。根据事情的深入程度，您可能会有很多额外的节点。 B/8(B-3)/8(B+3)/8

其他人将不得不进行数学运算，看看您是否必须除以大于 8 的值才能防止图像重复过多。好消息是，即使真正的扇出仅在 4 左右而不是 32 左右，您也只需要深度为 10 的树。10 中的 4 次重复可以让您在叶子处获得多达 3200 万张图像。我希望你有足够的内存供你使用！如果没有，您可以将树放入文件系统中。

让我知道这是怎么回事！

于 2010-01-31T04:59:11.513 回答
1

缩略图中的散列也很好：可以识别缩放的重复项（几乎没有修改）

于 2010-01-31T05:13:20.027 回答