logo标签列表

需要一个好的算法来对8GB的图片进行分类

c++imagejpegcimg
9
我有大约15万张图片，其中一些是重复的。 我已经确定SSIM算法是比较两张图片并查看它们是否重复的不错选择。然而，如果我想要以这种方式找到重复项，我将不得不比较150,000 * 149,999张图片，这需要很长时间。
所以现在我正在寻找一个快速有效的算法来为每个图片创建一个平均值，然后仅比较接近其平均值的图像。
简而言之：我正在寻找一种有效的方法来分类图片！
我计划使用C++ CImg库来完成此任务，因为它很快。
谢谢！
图片可能存在细微差异，但宽度必须相同，高度可以不同。 - moccajoghurt
你能不能按照宽度对图像进行排序呢？只有宽度相同的图像才需要相互比较。 - jalf
@jalf：我可以想象很多图像可能都有相同的宽度，可能所有的图像都是这样...我的问题更多是为了帮助选择可以使用的算法类型。 - Vincent Mimoun-Prat
然而，如果这是一次性操作，我认为第一步应该是查看图片宽度的分布情况。对于那些只有可管理数量图像宽度的宽度，您可以运行所有n ^ 2比较。如果还有任何太大而无法处理的组（例如，如果一半的图像具有相同的宽度），请考虑进行需要实际思考的操作；-) - Steve Jessop
@user1910856：它们是“基本上”相同的图片，还是除了底部的框之外完全相同的图片？我问这个问题是因为根据答案，适当的技术将会有很大不同。 - Yaniv
显示剩余4条评论
4个回答
3
如果有不同高度但基本相同的图片，只是底部有一个无关的框，导致高度不同。如果两个重复图片顶部始终相同，您可以尝试根据图像中N行像素计算哈希值，这些行应该相对安全（即底部的框不会在这些行中）。一旦您对所有文件进行了哈希处理，就可以对哈希值进行排序，并更精确地比较具有相同哈希值的图片。
2
我会尝试一种哈希/指纹的方法：

  • 为每个图像生成一个指纹，其中包含元文件或数据库的大小和组件数量等相关图像属性。指纹可以从共同的子图像计算得出，这可能是一个有损压缩的频谱图，一个简单的向量，包含FFT的频率箱，直方图或另一种技术（我不知道哪种更适合，这很可能与内容有关）。

  • 如littlestewie所提到的，预先使用图像属性（如大小和颜色组件数量）进行分组将大大减少（二进制）比较的数量，对于每个组，比较次数为(n*(n-1))/2。

  • 使用适当的容差比较指纹以进行进一步的子分组（注意覆盖那些一个图像在多个组中都有匹配的情况）。

  • OpenCV可以进行最终匹配：

    How to detect the Sun from the space sky in OpenCv?

有关使用OpenCV进行图像比较的相关问题：

2
在这里使用任何形式的哈希都是毫无意义的，因为即使是非常相似的图像也会产生非常不同的哈希值。正如评论中指出的那样，两个“重复”的图像可能有微小的差异（例如JPEG压缩引起的效果），因此我们要检测几乎重复的图像。另外，正如评论中所指出的那样，只考虑相同宽度的图像是减少你二次比较数量的第一步。如果所有图像都具有相同的宽度，则没有改进。
您需要解决的第一个问题是丢弃高度不同的几乎相同图像的底部框。为什么会有这个框？它是统一的背景颜色吗？如果删除这些底部框有问题，请解释原因并预处理您的图像以删除它们。从现在开始，我将认为这些框已被删除。
SSIM（结构相似性）可能是检测几乎重复的最佳方法，但它没有比诸如NRMSE之类的简单算法快的机会，该算法在Comparing image in url to image in filesystem in python中描述。因此，可能加快该过程的一种方法（尽管本质上仍然是二次的）是首先将给定的图像转换为灰度，并仅考虑其一个小中央窗口，例如50x50。在这个中央窗口上应用高斯滤波器，因此大多数结构（例如噪声）都被抑制。由于您有相当多的图像要进行比较，因此我建议在这个平滑的中央窗口中应用粗略的二值化，形式为：如果值v大于可能的最大值的一半，则将其变为白色，否则将其变为黑色。现在，每个图像有2500位。下一步可能是：从这些2500位到一个公共位模式的汉明距离，2500位1在这里可以起作用。对所有图像重复此过程。对于每个图像，您都有一个汉明距离。
现在让我们找到几乎相同的图像。首先，考虑将找到的汉明距离分成k个不同的插槽。因此，落入同一箱中的所有图像会进一步进行比较。这样，如果图像a落在箱k_i中，而图像b落在箱k_j中，则i！= j，我们将a丢弃为与b相似。如果同一箱中有太多图像，则需要改进上述过程和/或减少每个箱的间隔。要进一步加快该过程，请首先在同一箱中对所有图像应用NRMSE，然后仅比较SSIM给出高值的那些图像。
我不同意哈希是毫无意义的观点。确切的哈希可能是毫无意义的，但是局部敏感哈希实际上是这类问题的一个很好的选择。 - Yaniv
所以我们都认为哈希是无意义的。现在，对于我使用的任何其他单词，我相信可以找到一些“变体”-“blah”，它们与原始单词“blah”执行不同的操作。如果您能有意义地描述“变体”-“哈希”在这里的应用，我会同意您的想法。 - mmgp
你断言任何形式的哈希都是无意义的；我只是指出 一些 形式的哈希实际上在这里非常有用。维基百科页面提到图像相似性识别是其中之一的应用。至于如何应用，考虑您上面描述的 SSIM 技术和位采样以生成多个 LSH 哈希。然后，您可以使用图像之间匹配哈希数作为它们可能是近似重复项的信号。这可能比上述分桶更快。 - Yaniv
SSIM只在之前提到的所有步骤完成后应用，所以你的建议中存在一些矛盾。二进制分组方法可以在线性时间内完成，我真的怀疑你能否从初始图像开始在（次）线性时间内完全应用LSH。现在，在我看来，你的建议的最后部分是将LSH应用于我得到的那2500个位。如果是这样的话，那可能会有用，但作为整个比较方案的第一步它依然无用。所以要么我误解了你所说的一切，要么这只适用于方法在到达二进制表示之后。 - mmgp
我认为我们基本上是同意的，看起来的分歧只是不同解释的问题。 - Yaniv
0

MarvinLabs已经提出了对前N行进行哈希的想法。

如果您使用一个好的哈希函数（如MD5）对前N（比如20）行进行哈希，您可以相当确定哈希冲突会识别出相同的图像。将哈希值与其他唯一的图像标识符（文件名？）放在std::multimap中。这个multimap将花费您大约10MB到100MB的路径长度，可以轻松地保存在内存中。您可以在哈希之后进行报告。如果您很谨慎，可以对冲突进行另一次图像比较。除非所有图像都来自同一CCTV摄像机，否则误判的几率比从磁盘读取错误小。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接