我们收集了数百张大小的照片图像。大量照片在视觉上是重复的,但文件大小、分辨率、压缩等不同。
是否可以使用任何特定的图像处理方法来搜索和删除这些重复的图像?
我们收集了数百张大小的照片图像。大量照片在视觉上是重复的,但文件大小、分辨率、压缩等不同。
是否可以使用任何特定的图像处理方法来搜索和删除这些重复的图像?
我最近想为 PHP 图像库完成这项任务。我希望能够为上传的图像生成“模糊”指纹,并检查数据库中是否存在具有相同指纹的任何图像,表明它们相似,然后更仔细地比较它们以确定相似程度。
我通过将上传的图像大小调整为 150 像素宽,将其减小为灰度,将每种颜色的值四舍五入到最接近的 16 倍数(在 0 到 255 之间给出 17 种可能的灰度阴影),将它们标准化并将它们存储在一个数组,从而创建一个“模糊”颜色直方图,然后创建一个直方图的 md5sum,然后我可以在我的数据库中搜索它。这对于缩小与上传文件在视觉上非常相似的图像非常有效。
然后将上传的文件与数据库中的每个“相似”图像进行比较,我拍摄了两张图像,将它们调整为 16x16,并逐个像素地分析它们,并将每个像素的 RGB 值与其他图像,将所有值相加并除以像素数,得出平均颜色偏差。任何小于特定值的都被确定为重复。
整个过程是使用 GD 模块用 PHP 编写的,与数千张图片的比较每个上传的文件只需要几百毫秒。
我的代码和方法在这里: http: //www.catpa.ws/php-duplicate-image-finder/
尝试PerceptualDiff比较具有相同尺寸的 2 个图像。允许阈值,例如考虑仅具有 X 个不同像素的图像在视觉上无法区分。
如果视觉副本可能由于缩放或不同的文件类型而具有不同的尺寸,您可能需要制作标准格式以进行比较。例如,我可能会使用 ImageMagick 将所有图像缩放到 100x100 并将它们保存为 PNG 文件。
一个非常简单的方法如下:
在内存中将图像转换为灰度,因此每个像素只是 0(黑色)和 255(白色)之间的数字。
将图像缩放到固定大小。找到合适的尺寸很重要,你应该尝试不同的尺寸。例如,您可以将每个图像缩放到 64x64 像素,但使用更小或更大的图片可能会得到更好或更差的结果。
为所有图像完成此操作后(是的,这将需要一段时间),请始终在内存中加载两个图像并将它们彼此相减。那就是将图像 A 中的像素 (0,0) 的值减去图像 B 中的像素 (0,0) 的值,现在对两者中的 (0,1) 执行相同的操作,依此类推。结果值可能是正数或负数,您应该始终存储绝对值(因此 5 会导致 5,-8 但会导致 8)。
现在您有了第三张图像,它是图像 A 和 B 的“差异图像”(增量图像)。如果它们相同,则增量图像全黑(所有值都将减为零)。它的“黑色越少”,图像就越不一样。你需要找到一个好的阈值,因为即使图像实际上是相同的(对你的眼睛而言),通过缩放、改变亮度等,增量图像也不会是全黑的,而是只有非常深的灰色调。所以你需要一个阈值,上面写着“如果平均误差(增量图像亮度)低于某个值,它们仍然很有可能是相同的,但是如果高于该值,它们很可能不是。找到正确的阈值与找到正确的缩放大小一样难。您将始终有误报(图像被认为是相同的,
这个算法非常慢。实际上,仅创建灰度图像需要大量时间。然后,您需要将每张 GS 图像相互比较,再一次,大量的时间。存储所有 GS 图像也会占用大量磁盘空间。所以这个算法很糟糕,但结果并没有那么糟糕,尽管它很简单。虽然结果并不令人惊讶,但它们比我最初想象的要好。
获得更好结果的唯一方法是使用高级图像处理,在这里它开始变得非常复杂。它涉及很多数学(真的很多);许多系统都有很好的应用程序(欺骗查找器)已经实现了这些,所以除非你必须自己编程,否则最好使用这些解决方案之一。我阅读了很多关于这个主题的论文,但恐怕其中大部分都超出了我的视野。甚至我根据这些论文可能能够实现的算法也超出了它;这意味着我了解需要做什么,但我不知道它为什么起作用或它实际上是如何起作用的,这只是魔术;-)
我实际上写了一个应用程序来做这件事。
我从以前的应用程序开始,该应用程序使用基本的Levenshtein 距离算法来计算图像相似度,但由于多种原因,这种方法是不可取的。毫无疑问,您要找到的用于确定图像相似度的最快算法是均方误差或平均绝对误差(两者的运行时间均为 O(n),其中 n 是图像中的像素数,并且以多种不同的方式线程化任一算法的实现也是微不足道的)。Mecki 的帖子实际上只是一个平均绝对误差实现,我的应用程序可以执行(如果您愿意,代码也可用于您的浏览乐趣)。
无论如何,在我们的应用程序中,我们首先对图像进行下采样(例如,将所有图像缩放为 32*32 像素),然后转换为灰度,然后通过我们的比较算法运行生成的图像。我们还在研究一些更高级的预处理算法,以进一步规范化图像,但是……还没有。
肯定有比 MSE/MAE 更好的算法(事实上,这两种算法应用于视觉信息的问题已得到充分证明),例如SSIM,但它是有代价的。其他人试图比较图像中的其他视觉质量,例如亮度、对比度、颜色直方图等,但与简单地测量误差信号相比,这一切都是昂贵的。
我的应用程序可能会工作,具体取决于这些文件夹中有多少图像。它是多线程的(我已经看到它完全加载了八个处理器内核来执行比较),但我从未针对大于几百张图像的图像数据库进行测试。几百演出的图像听起来大得令人望而却步。(只需从磁盘读取它们、下采样、转换为灰度并存储在内存中——假设你有足够的内存来保存所有内容,而你可能没有——可能需要几个小时)。
我相信这仍然是一个研究领域。如果您有一些时间,一些相关的关键字是:
基本上,每个图像都经过处理(索引)以产生“图像签名”。相似的图像具有相似的签名。如果您的图像只是重新缩放,那么它们的签名可能几乎相同,因此它们聚集得很好。一些流行的签名是 MPEG-7 描述符。对于聚类,我认为 K-Means 或其任何变体可能就足够了。但是,您可能需要处理数百万张图像,这可能是个问题。
这是维基百科主要条目的链接:
http ://en.wikipedia.org/wiki/CBIR
希望这可以帮助。
一个快速的破解方法是编写一个程序,该程序将计算每个图像中的平均像素值,以灰度显示,按此值排序,然后在视觉上比较它们。非常相似的图像应该按排序顺序彼此靠近。
您将需要一个命令行工具来处理如此多的数据。
比较每对可能的图像不会扩展到如此大的图像集。您需要根据某些指标对整组图像进行排序,以便仅对相邻图像进行进一步比较。
一个简单度量的示例是图像中所有像素的平均值,表示为单个灰度值。这只有在副本没有任何视觉变化时才有效。使用有损文件格式也会导致视觉上的改变。
跳出框框思考,您也许可以使用图像元数据来缩小数据集的范围。例如,您的图像可能包含显示图像拍摄日期和时间的字段,精确到秒。重复项可能具有相同的值。可以使用诸如exiv2之类的工具将这些数据转储为更方便和可排序的文本格式(对批处理/shell 脚本有一点了解)。
甚至相机制造商和型号等字段也可以用于将一组 1,000,000 张图像减少到 100 组 10,000 张图像,这是一个显着的改进。
gqview 程序有一个查找重复项的选项,因此您可以尝试在那里查找。然而,它并不是万无一失的,所以它只适合作为一种启发式向人类呈现重复项,以进行手动确认。
最重要的部分是使文件具有可比性。
一个通用的解决方案可能是将所有图像缩放到某个固定大小和灰度。然后将生成的图像保存在具有相同名称的单独目录中以供以后参考。然后可以按文件大小排序并直观地比较相邻条目。
生成的图片可能会以某些方式量化,以编程检测相似性(块、线等的平均)。
我想最可扩展的方法是为每个图像存储一个指纹。然后,当添加新图像时,这是一个简单的例子,SELECT id FROM photos where id='uploaded_image_id'
检查重复(或指纹所有图像,然后查询重复
显然,由于实际内容不同,简单的文件哈希将不起作用..
声学指纹/本文可能是这个概念的一个良好开端,因为它有很多实现。这是一篇关于图像指纹识别的论文。
也就是说,您也许可以摆脱一些更简单的事情。一些基本的东西,比如将图像大小调整为相等的宽度或高度,减去image_a
,image_b
然后求和。如果总差异低于阈值,则图像是重复的。
这样做的问题是您需要将每张图像相互比较。所需时间将成倍增加..
如果你能想出一种比较遵循三角不等式的图像的方法(例如,如果 d(a,b) 是图像 a 和 b 之间的差异,那么 d(a,b) < d(a,c) + d(b,c) 对于所有 a,b,c),那么BK-Tree将是索引图像的有效方法,这样您就可以在 O(log n) 时间而不是 O(n) 时间内找到匹配项每个图像。
如果在不同程度的压缩/调整大小/等之后您的匹配仅限于同一图像,那么转换为一些规范的大小/颜色平衡/等并简单地将每个像素的差异平方相加可能是一个很好的指标,这服从三角不等式,因此您可以使用 BK-tree 进行有效访问。
如果你有一点钱可以花,也许一旦你运行第一遍以确定哪些图像可能匹配,你可以为亚马逊的 Mechanical Turk 编写一个测试。
https://www.mturk.com/mturk/welcome
本质上,您将创建一个小部件,AMT 将向真正的人类用户展示,然后他们基本上只需要回答“这两个图像是否相同?”的问题。或者你可以向他们展示一个 5x5 图像的网格,然后问他们“这些图像中的哪一个匹配?”。然后,您将收集数据。
另一种方法是使用 Luis Von Ahn ( http://www.cs.cmu.edu/~biglou/ ) 最着名的人类计算原理和 reCaptcha,它使用验证码答案来确定不可读的单词已通过光学字符识别运行,从而有助于将书籍数字化。您可以制作一个验证码,要求用户帮助优化图像。
这听起来像是程序问题而不是编程问题。谁上传照片?你还是客户?如果您要上传照片,请将尺寸标准化为固定比例和文件格式。这样比较会更容易。但是,就目前而言,除非您有几天甚至几周的空闲时间,否则我建议您改为手动删除重复的图像,由您自己或您的团队通过视觉比较图像。
也许您应该按位置对图像进行分组,因为它是旅游图像。