几乎重复的图像检测
image
image-processing
8
0

用给定的一组图像彼此之间的相似度排序的快速方法是什么。

目前,我有一个可以在两个图像之间进行直方图分析的系统,但这是一个非常昂贵的操作,而且看起来过于矫kill过正。

理想情况下,我正在寻找一种算法,该算法将给每个图像一个分数(例如整数分数,例如RGB平均),并且我可以按该分数排序。相同分数或彼此相邻的分数可能重复。

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

每个图像的RGB平均差,有类似的东西吗?

参考资料:
Stack Overflow
收藏
评论
共 8 个回答
高赞 时间 活跃

您必须确定什么是“相似”。对比?色调?

图片是否与同一图片上下颠倒“相似”?

我敢打赌,通过将图像分成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进行加权。则权重最高的是绿色,然后是红色,然后是蓝色,以符合人类的视觉敏感性。

收藏
评论

关于图像搜索和相似性度量的研究很多。这不是一个容易的问题。通常,一个int不足以确定图像是否非常相似。您的假阳性率会很高。

但是,由于已经进行了很多研究,因此您可以看一下其中的一些内容。例如, 本文 (PDF)提供了一种紧凑的图像指纹算法,该算法适用于快速查找重复图像而无需存储大量数据。如果您想要强大的功能,这似乎是正确的方法。

如果您正在寻找更简单但绝对是临时的东西,那么这个SO问题有一些不错的想法。

收藏
评论

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

快速多分辨率图像查询的作用是根据YIQ颜色空间将图像分为3个部分(比RGB更好地匹配差异)。然后,基本上使用小波算法压缩图像,直到每个颜色空间中只有最突出的特征才可用。这些点存储在数据结构中。查询图像经过相同的过程,并且查询图像中的突出特征与存储的数据库中的特征相匹配。匹配次数越多,图像相似的可能性就越大。

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

Retrievr比我的软件印象深刻得多,它使您可以尝试使用Flickr图像作为源的FMIQ算法。很酷!通过草图或使用源图像进行尝试,您可以看到其效果。

收藏
评论

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

收藏
评论

问题识别相似图像的好方法?似乎为您的问题提供了解决方案。

收藏
评论

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

如果对图像进行二维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

收藏
评论

有一个C库(“libphash” - http://phash.org/ ),将计算出的图像的“感知哈希”,并允许您通过比较散列(检测类似的图像,因此您不必每次图像进行比较直接与所有其他图像相对),但不幸的是,当我尝试使用它时,它似乎不太准确。

收藏
评论

图片具有许多功能,因此除非您将自己缩小到一个范围(例如平均亮度),否则您将要处理n维问题空间。

如果我要求您为世界各城市分配一个整数,这样我就可以分辨出哪个城市比较近,结果将不会很好。例如,您可以选择时区作为单个整数,并在某些城市获得良好的效果。但是,即使位于北极的另一个城市和位于北极的另一个城市也可以位于同一时区,即使它们位于地球的相对两端。如果我使用两个整数,则经度和纬度都可以得到很好的结果。对于图像相似性,问题是相同的。

综上所述,有些算法会尝试将相似的图像聚类在一起,这实际上就是您所要求的。当您使用Picasa进行面部检测时,就会发生这种情况。甚至在您识别任何面孔之前,它都会将相似的面孔聚集在一起,因此很容易遍历一组相似的面孔,并为大多数面孔赋予相同的名称。

还有一种称为“主成分分析”的技术,该技术使您可以将n维数据减少到任意数量的维。因此,具有n个特征的图片可以简化为一个特征。但是,这仍然不是比较图像的最佳方法。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题