我有大约 150.000 张图片，其中一些是重复的。我认为 SSIM 算法是比较两张图片并查看它们是否重复的不错选择。但是，如果我想以这种方式查找重复项，我将不得不比较 150.000 * 149.999 张图片，这将永远耗时。
所以我现在正在寻找的是一种快速有效的算法，可以为每张图片创建一个平均值，然后只比较接近平均值的图像。
简而言之：我正在寻找一种对图片进行分类的有效方法！
我计划使用 C++ CImg 库来完成这项任务，因为它速度很快。
谢谢！
问问题
550 次
4 回答
3
有些图片的高度不同，但基本上是相同的图片，只是底部有一个不相关的框，可以改变高度。
如果两个副本的图片顶部始终相同，您可以尝试根据图像中应该非常安全的 N 行像素计算哈希值（即底部的框不会在那些行）。
对所有文件进行哈希处理后，您可以对哈希值进行排序并更精确地比较具有相同哈希值的图片。
于 2012-12-17T19:40:12.153 回答
2
我会尝试类似哈希/指纹的方法：
为每个图像生成指纹，还包含相关的图像属性，例如元文件或数据库的大小和组件数量。指纹可以从公共子图像中计算出来，这可能是有损压缩频谱图、包含 FFT 频率箱的简单向量、直方图或其他技术（我不知道什么更适合，这是最可能非常依赖于内容）。
正如 littlestewie 所提到的，预先使用图像属性（例如大小和颜色分量的数量）进行分组将大大减少（二进制）比较的数量，这将是
(n*(n-1))/2针对每个组的。将指纹与适当的容差进行比较以进行进一步的子分组（注意覆盖其中一张图像在多个组中匹配的情况）。
OpenCV 可以做最后的比赛：
有关使用 OpenCV 进行图像比较的相关问题：
于 2012-12-17T19:50:45.997 回答
2
在这里使用任何形式的散列都是毫无意义的，因为即使是几乎相同的图像也会给出非常不同的散列值。正如评论中指出的那样，两个“重复”图像可能略有不同（例如考虑 JPEG 压缩造成的影响），因此感兴趣的是检测几乎重复的图像。此外，正如评论中所指出的，仅考虑相同宽度的图像是减少二次比较次数的第一步。如果所有图像的宽度相同，则没有改进。
您必须解决的第一个问题是丢弃具有不同高度的几乎相同图像的底部框。为什么会有这个盒子？它是统一的背景颜色吗？预处理您的图像以删除此类底部框，如果这样做有问题，请解释原因。我会考虑从现在开始这些盒子已经被删除了。
SSIM（结构相似性）可能是检测几乎重复的好方法，但它没有机会比更简单的算法更快，例如Comparing image in url to image in filesystem in python 中描述的 NRMSE 。因此，一种可能加快该过程的方法（尽管在本质上它仍然是二次的）是首先将给定图像转换为灰度，并且只考虑其中的一个小中心窗口，例如 50x50。在这个中央窗口上应用一个高斯滤波器，这样小的结构（例如噪音）大部分都被抑制了。因为你有很多图像要比较，我会在这个平滑的中央窗口中应用粗略的二值化，形式如下：如果一个值v大于可能的最大值的一半，则将其变为白色，否则将其变为黑色。现在每个图像都有 2500 位。下一步可能如下：计算从这 2500 位到公共位模式的汉明距离，2500 位 1 将在这里工作。对所有图像重复此过程。对于每个图像，您都有一个汉明距离。
现在让我们找到几乎相同的图像。首先，考虑将发现的汉明距离分箱到k不同的槽中。因此，将进一步考虑落在同一 bin 中的所有图像进行比较。这样，如果图像a落在 bin 中k_i并且图像b落在 bink_j中i != j，我们将丢弃a为与 相似b。如果同一个 bin 中有太多图像，则上述过程需要改进和/或需要减少每个 bin 的间隔。为了进一步加快这个过程，考虑首先在同一个 bin 中的所有图像之间应用 NRMSE，只有那些给出高值的图像才会最后由 SSIM 进行比较。
于 2012-12-17T23:16:49.420 回答
0
MarvinLabs 已经指出了散列前 N 行的想法。
如果您在前 N 行（比如 20 行）上使用良好的散列（如 MD5），您可以非常确定散列冲突识别相同的图像。将散列与其他唯一图像标识符（文件名？）一起放入 std::multimap。这个多图将花费你大约 10MB 到 100MB 的路径长度，并且可以很容易地保存在内存中。你可以在散列后做你的报告。如果您是偏执狂，您可以对碰撞进行另一次图像比较。除非所有图像都来自同一个闭路电视摄像机，否则误报的机会小于从磁盘读取错误的机会。
于 2012-12-17T20:50:39.657 回答