近似重复图像检测[关闭]

StackOverflow https://stackoverflow.com/questions/1034900

题

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

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

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

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

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

有帮助吗？

解决方案

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

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

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

其他提示

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

如果您拍摄图像的2d Haar小波（它比声音更容易，它只需要很多平均值和一些用于加权系数的平方根），就可以获得更好的图像摘要。将小波中的k个最大加权系数作为稀疏向量，对其进行归一化，并将其保存以减小其大小。您应该至少预先使用感知权重重新缩放R G和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/纸/ chum_bmvc08.pdf

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

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

我为此实现了一个非常可靠的算法快速多分辨率图像查询。我的（古老的，未维护的）代码是这里。

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

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

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

图片有很多功能，所以除非你把自己缩小到一个，比如平均亮度，否则你正在处理一个n维问题空间。

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

所有这一切都说，有些算法试图将相似的图像聚集在一起，这实际上就是你所要求的。这是使用Picasa进行面部检测时发生的情况。甚至在你识别出任何面孔之前，它就会将相似的面部聚集在一起，这样就可以很容易地通过一组相似的面孔并给它们大多数相同的名称。

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

有一个C库（“libphash” - http://phash.org/ ）将计算一个“感知散列”一个图像，允许你通过比较哈希来检测相似的图像（所以你不必将每个图像直接与每个其他图像进行比较）但不幸的是，当我尝试它时，它似乎不是很准确。

你必须决定什么是“相似”。对比？色相？

图片是否“相似”？相同的图片倒置？

我打赌你可以找到很多“近距离通话”通过将图像分成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的重量，重量绿色最高，然后是红色，然后是蓝色，以匹配人类的视觉灵敏度。

问题 识别类似图片的好方法？ 似乎为您的问题提供了解决方案。

我假设其他重复图像搜索软件对图像执行FFT，并将不同频率的值存储为矢量：

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

然后你可以通过计算两个图像的权重向量之间的距离来比较相等的两个图像：

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

一种解决方案是对每对进行 RMS / RSS 比较执行冒泡排序所需的图片。其次，您可以对每个图像执行 FFT 并进行一些轴平均以检索单个整数对于您将用作排序依据的索引的每个图像。您可以考虑对原始大小（25％，10％）版本进行任何比较，具体取决于您选择忽略的差异以及您需要多少加速。让我知道这些解决方案是否有趣，我们可以讨论或者我可以提供示例代码。

检测近似重复图像检测的大多数现代方法使用有趣的点检测和描述这些点周围区域的描述符。通常使用 SIFT 。然后，您可以对描述符进行量化，并将群集用作视觉词汇词汇。

因此，如果我们看到两个图像的常见视觉词与这些图像的所有视觉词的比率，您可以估计图像之间的相似性。有很多有趣的文章。其中一个是近似重复图像检测：minHash和tf-idf加权

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top