10

我正在使用 MinHash 算法来查找图像之间的相似图像。我遇到过这篇文章，How can I recognize slightly modified images?它指向了MinHash算法。

我正在使用这篇博文中的 C# 实现，Set Similarity and Min Hash.

但是在尝试使用该实现时，我遇到了两个问题。

  • 我应该将值设置为什么值universe？
  • 将图像字节数组传递给HashSet时，它只包含不同的字节值；因此比较 1 ~ 256 的值。

universeMinHash 中这是什么？
我可以做些什么来改进 C# MinHash 实现？

由于HashSet<byte>包含高达 256 的值，因此相似度值始终为 1。

以下是使用 C# MinHash 实现的源代码Set Similarity and Min Hash：

class Program
{
    static void Main(string[] args)
    {
        var imageSet1 = GetImageByte(@".\Images\01.JPG");
        var imageSet2 = GetImageByte(@".\Images\02.TIF");
        //var app = new MinHash(256);
        var app = new MinHash(Math.Min(imageSet1.Count, imageSet2.Count));
        double imageSimilarity = app.Similarity(imageSet1, imageSet2);
        Console.WriteLine("similarity = {0}", imageSimilarity);
    }

    private static HashSet<byte> GetImageByte(string imagePath)
    {
        using (var fs = new FileStream(imagePath, FileMode.Open, FileAccess.Read))
        using (var br = new BinaryReader(fs))
        {
            //List<int> bytes = br.ReadBytes((int)fs.Length).Cast<int>().ToList();
            var bytes = new List<byte>(br.ReadBytes((int) fs.Length).ToArray());
            return new HashSet<byte>(bytes);
        }
    }
}
4

2 回答 2

11

先回答你的第二个问题：

我可以做些什么来改进 C# MinHash 实现？

您正在尝试在byte级别上比较本质上结构非常不同的文件的图像（您将 TIFF 用作一个图像，将 GIF 用作另一个图像）。即使在视觉上这些文件完全相同，您的实现也永远不会找到重复项，除非这些文件属于相同类型。

也就是说，您的minhash实现应该依赖于您散列以创建签名的图像的可比较属性。

虽然字节的值绝对是图像的属性，但如果它们采用不同的格式，则无法相互比较。

例如，对于图像，您可以使用图像中每个像素的 RGB（可能还有 alpha）值。无论图像采用何种格式（您可以使用 CMYK 或您想要的任何其他颜色空间），这些值都是可比较的。

但是，为每个像素使用单独的值会给您带来糟糕的结果。Jaccard 相似度用于比较每个集合中的值（无论您是否散列任何内容），并且因为集合没有分配任何顺序，所以图像具有相同数量的相同颜色但排列在不同的空格会导致误报。

以以下图像为例：

红色, 绿色 红色, 绿色

它们都是 100px x 100px，带有 50 像素的红色和 50 像素的绿色。

使用 Jaccard 相似度比较两者，您会得到以下结果（请注意，由于值相同，因此该集合中每种颜色仅包含一个元素。如果需要，您可以使用Jaccard 袋子比较来比较具有同一项目的多次计数，但在这种情况下，结果将是相同的）：

Legend:
    g = green
    r = red

left image = { r, g }
right image = { r, g }

similarity = intersection(left, right) / union(left, right)

similarity = 1 / 1 = 100%

right image = { r, g }关于: 因为集合是无序的表示的注释，所以它们实际上是相同的，即使没有计算 Jaccard 比较，这一点也很明显{ r, g }。{ g, r }

但显然，这些图像并不相同。

这就是为什么通常使用shingling来在集合中找到不同的小区域，这些小区域可以共同用于唯一地标识一个项目。

对于图像，您可以使用固定长度的连续 RGB 值（在这种情况下，从左到右、从上到下，当边缘被击中时环绕）来生成带状疱疹。在这种情况下，假设带状疱疹长度为三，您的集合看起来像这样（注意我使用方括号来表示属性/向量，因为带状疱疹本身并不是集合）：

left image = { [r, r, r], [r, r, g], [r, g, g], [g, g, g] }
right image = { [g, g, g], [g, g, r], [g, r, r], [r, r, r] }

并为您提供以下 Jaccard 相似性：

intersection(left, right) = 2
union(right, left) = 6

similarity(left, right) = 2 / 6 = 33.33%

这是对这些图像与原始图像的相似程度（因为它们不是）的更接近的估计。

请注意，带状疱疹可以是您选择的任何长度。您必须决定哪些带状疱疹会产生适当的 Jaccard 相似性结果（和阈值）回答“这些相似度如何？”的问题。

现在，回答你的第一个问题：

什么是宇宙价值？

在这种特殊情况下，它是宇宙中可能存在的项目数。如果您使用单个 RGB 像素，则宇宙将是：

255 * 255 * 255 = 16,581,375

使用 shingling，价值要高得多，因为您正在处理这些项目的组合。理想情况下，您希望为您的 minhash 哈希函数集生成一组完美的哈希函数。但是，由于类型系统的限制（或者，因为您不想在另一个存储介质中存储非常大的数字），您的重点应该放在最小化冲突的哈希函数上。

如果您知道项目宇宙中可能项目的数量，那么它可以帮助您生成减少冲突数量的散列函数。

在您引用的实现中，此全域大小用于生成随机数，然后传递这些数字以生成多个散列函数以进行 minhashing，理想情况下，这将产生最小的冲突。

于 2012-08-10T17:23:49.620 回答
0

简而言之，单独使用 Minhash 是寻找相似图像的糟糕解决方案。当与适当的图像特征提取结合使用时，它应该可以很好地工作。但这远非直截了当。我会解释：

从广义上讲，Minhash 根据共享特征的数量计算相似度。选择合适的特征来生成你的 minhashes 是至关重要的。在您的情况下，您必须选择可能由相似图像共享（但不太可能由不同图像共享）的特征。通过“共享”，我的意思是在两个图像中发现相同的特征。

对于文本文档，这很容易：使用的特征通常是文本的瓦片，例如“the cat sat”、“cat sat on”、“sat on the”、“on the mat”。这些很容易生成并且很可能在相似文档之间共享。

有了图像，这要困难得多。您无法比较字节的运行，因为同一图像的 JPEG 和 PNG 将具有完全不同的字节模式。您也不能比较像素颜色值的运行，因为这些颜色值在 JPEG 和 PNG 图像之间会略有不同。然后考虑如果一张图像被轻微缩放、模糊、轻微旋转或调整其色彩平衡会发生什么：这些都是相似性检测应该具有鲁棒性的所有类型的修改，但其中任何一个都会导致变化对于所有像素，因此如果特征仅基于像素运行，则图像将被视为完全不相似。

图像相似性检测很复杂，并且依赖于使用不会随缩放、旋转、裁剪、模糊或大量颜色调整而改变的特征。有许多技术，它们通常检测图像中广泛的形状和颜色关系。这不适合新手，您需要愿意阅读计算机视觉领域的一些相当数学的论文。一旦你可以检测到这些特征，它们就可以有用地输入到 minhash 算法中并给出良好的结果。

MinHash 中的这个宇宙是什么？

该博客的作者显然打算universeSize成为可能存在的不同功能的数量，但没有对价值做任何明智的事情。他们只是用它来减少散列函数的随机性，这总是一个坏主意。出于所有实际目的，宇宙应该被认为是无限的，并且没有理由在 minhash 实现中使用这样的变量。我在该代码中看到了很多问题。

于 2017-09-26T00:27:15.327 回答