近似重复图像检测

Question

通过它们彼此的相似性来对一组给定图像进行排序的快速方法是什么.

目前我有一个系统在两个图像之间进行直方图分析,但这是一个非常昂贵的操作,似乎太过分了.

最理想的是,我正在寻找一种能够为每个图像提供分数的算法(例如整数分数,例如RGB平均值),我可以按该分数进行排序.相同的分数或分数彼此相邻可能是重复的.

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994 

每张图像的RGB平均值很糟糕,有类似的东西吗？

Answer 1

对图像搜索和相似性度量进行了大量研究.这不是一个容易的问题.通常,单个单元int不足以确定图像是否非常相似.你的假阳性率很高.

但是,由于已经进行了大量的研究,你可能会看一些它.例如,本文(PDF)提供了一种紧凑的图像指纹识别算法,该算法适用于快速查找重复图像而无需存储大量数据.如果你想要一些强大的东西,这似乎是正确的方法.

如果你正在寻找一些更简单的东西,但绝对是更特别的,这个问题有一些不错的想法.

Answer 2

我建议考虑不再使用RGB直方图.

如果你拍摄图像的2d Haar小波(它比声音更容易,它只是很多平均值和一些用于加权系数的平方根),你可以获得更好的图像摘要,并保留最大的k将小波中的加权系数作为稀疏向量,对其进行归一化,并将其保存以减小其大小.您应该至少预先使用感知权重重新调整RG和B,或者我建议切换到YIQ(或YCoCg,以避免量化噪声),这样您就可以以较低的重要性对色度信息进行采样.

您现在可以使用这些稀疏归一化向量中的两个的点积作为相似性的度量.具有最大点积的图像对在结构上将非常相似.这具有稍微抵抗调整大小,色调偏移和水印,并且非常容易实现和紧凑的优点.

您可以通过增加或减少k来折衷存储和准确性.

对于这种分类问题,按单个数字分数排序将是难以处理的.如果你考虑它,它将要求图像只能沿一个轴"改变",但它们不能.这就是你需要一个特征向量的原因.在Haar小波的情况下,它大致出现图像中最尖锐的不连续性.您可以成对地计算图像之间的距离,但由于您拥有的是距离度量,因此线性排序无法表达3个图像的"三角形",这些图像都是相同的距离.(即想象一个全绿色的图像,一个全红色的图像和一个全蓝色的图像.)

这意味着您的问题的任何真正解决方案都需要在您拥有的图像数量中进行O(n ^ 2)次操作.然而,如果可以线性化度量,那么如果度量适合于例如基数排序,则可能只需要O(n log n)或O(n).也就是说,你不需要花费O(n ^ 2),因为在实践中你不需要筛选整个集合,你只需要找到比某个阈值更接近的东西.因此,通过应用几种技术中的一种来划分稀疏矢量空间,您可以获得更快的渐近性,因为"找到比给定阈值更相似的图像",而不是天真地将每个图像与每个图像进行比较,为您提供了什么你可能需要......如果不是你所要求的.

无论如何,几年前我在尝试最小化我存储的不同纹理的数量时使用了这个效果,但是在这个空间中也有很多研究噪点显示它的功效(在这种情况下比较它是一种更复杂的直方图分类形式):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

如果您需要更高的检测精度,minHash和tf-idf算法可以与Haar小波(或直方图)一起使用,以更有力地处理编辑:

http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

最后,斯坦福基于这种方法的更奇特的变体进行图像搜索,基于从小波中进行更多特征提取以找到旋转或缩放的图像部分等,但这可能远远超出了你的工作量我想做.

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

Answer 3

我实现了一种非常可靠的算法,称为快速多分辨率图像查询.我的(古老的,未维护的)代码就在这里.

快速多分辨率图像查询的作用是根据YIQ颜色空间将图像分割成3个部分(更好地匹配差异而不是RGB).然后使用小波算法对图像进行基本压缩,直到只有每个颜色空间中最突出的特征可用.这些点存储在数据结构中.查询图像经历相同的过程,查询图像中的突出特征与存储的数据库中的突出特征相匹配.匹配越多,图像越相似.

该算法通常用于"通过草图查询"功能.我的软件只允许通过URL输入查询图像,因此没有用户界面.但是,我发现将缩略图与该图像的大版本匹配非常有效.

比我的软件更令人印象深刻的是retrievevr,它允许你使用Flickr图像作为源来尝试FMIQ算法.很酷!通过草图或使用源图像进行尝试,您可以看到它的工作情况.

Answer 4

图片有很多功能,所以除非你把自己缩小到一个,比如平均亮度,你就要处理一个n维问题空间.

如果我要求你为世界各城市分配一个整数,那么我可以分辨哪些是接近的,结果不会很好.例如,您可以选择时区作为单个整数,并在某些城市获得良好的结果.然而,北极附近的城市和南极附近的另一个城市也可以在同一时区,即使它们位于地球的两端.如果我让你使用两个整数,你可以用纬度和经度获得非常好的结果.图像相似性的问题是相同的.

总而言之,有些算法试图将相似的图像聚集在一起,这实际上就是你所要求的.这是使用Picasa进行面部检测时发生的情况.甚至在您识别任何面部之前,它就会将相似的面部聚集在一起,这样就可以轻松地通过一组相似的面部,并为它们提供相同的名称.

还有一种称为主成分分析的技术,它允许您将n维数据减少到任何较小数量的维度.因此,具有n个特征的图片可以简化为一个特征.但是,这仍然不是比较图像的最佳方法.

Answer 5

有一个C库("libphash" - http://phash.org/)将计算图像的"感知哈希",并允许您通过比较哈希来检测相似的图像(因此您不必比较每个图像直接对抗所有其他图像)但不幸的是,当我尝试它时似乎并不是非常准确.

Answer 6

你必须决定什么是"相似的".对比？色调？

图片是否与同一张图片"相似"倒置？

我打赌你可以通过将图像分成4x4片并获得每个网格单元的平均颜色来找到很多"近距离调用".每张图片有16个分数.要判断相似性,您只需要对图像之间的差异进行求和.

我不认为单个散列是有意义的,除非它反对像色调,亮度或对比度这样的单个概念.

这是你的想法:

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

首先,我将假设这些是十进制数,即R*(2 ^ 16)+ G*(2 ^ 8)+ B,或类似的东西.显然这并不好,因为红色是非常重要的.

进入HSV空间会更好.您可以将HSV的位扩展到散列中,或者您可以单独解决H或S或V,或者每个映像可以有三个散列.

还有一件事.如果你做R,G和B的重量.重量绿色最高,然后是红色,然后是蓝色以匹配人类视觉灵敏度.

Answer 7

在网络服务时代，您可以尝试http://tineye.com