使用MinHash查找2个图像之间的相似性

Question

我正在使用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);
        }
    }
}

Answer 1

先回答你的第二个问题:

我该怎么做才能改进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 }:因为集合是无序的,所以它们是{ r, g }相同的{ g, r },所以它们是相同的,即使没有计算Jaccard比较,这一点也很明显.

但显然,这些图像并不相同.

这就是为什么通常采用重叠以便在集合内找到可以共同用于唯一地识别物品的不同迷你区域的原因.

对于图像,您可以使用固定长度的连续RGB值(在这种情况下,从左到右,从上到下,在边缘被击中时缠绕)以生成带状疱疹.在这种情况下,假设一个木瓦长度为3,你的集合看起来像这样(注意我使用方括号来表示属性/向量,因为带状疱疹本身不是集合​​):

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相似性结果(和阈值)回答"这些有多相似？"的问题.

现在,回答你的第一个问题:

什么是宇宙价值？

在这种特殊情况下,它是Universe中可能存在的项目数.如果您使用单个RGB像素,则Universe将为:

255 * 255 * 255 = 16,581,375

当你处理这些项目的组合时,价值要高得多.理想情况下,您希望为minhash的哈希函数集生成一组完美的哈希函数.但是,由于类型系统的限制(或者,因为您不希望在另一个存储介质中存储非常大的数字),您应该关注最小化冲突的哈希函数.

如果您知道项目世界中可能的项目数,那么它可以帮助您生成减少冲突数量的哈希函数.

在您引用的实现中, Universe大小用于生成随机数,然后传递这些数字以生成用于minhashing的多个哈希函数,理想情况下,这将产生最小的冲突.