10

MinHash アルゴリズムを使用して、画像間で類似の画像を見つけています。MinHashアルゴリズムHow can I recognize slightly modified images?を指摘したこの投稿に出くわしました。

このブログ投稿の C# 実装を使用していましたSet Similarity and Min Hash。

しかし、実装を使用しようとしているときに、2 つの問題に遭遇しました。

  • 値をどの値に設定すればよいuniverseですか?
  • イメージ バイト配列を に渡す場合HashSet、個別のバイト値のみが含まれます。したがって、1 ~ 256 の値を比較します。

これuniverseは MinHash で何ですか?
また、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

2 番目の質問を最初に取り上げます。

また、C# MinHash の実装を改善するにはどうすればよいですか?

byte本質的に構造が大きく異なるファイルのレベルで画像を比較しようとしています (TIFF を 1 つの画像として使用し、GIF を別の画像として使用しています)。これらのファイルが視覚的にまったく同じであったとしても、ファイルが同じタイプでない限り、実装によって重複が検出されることはありません。

そうは言っても、ミンハッシュの実装は、署名を作成するためにハッシュする画像の同等の属性に依存する必要があります。

バイトの値は画像の属性であることは間違いありませんが、形式が異なる場合は互いに比較することはできません。

画像の場合、たとえば、画像内の各ピクセルの RGB (および場合によってはアルファ) 値を使用できます。これらの値は、画像の形式に関係なく比較できます (CMYK またはその他の任意の色空間を使用できます)。

ただし、各ピクセルに個別の値を使用すると、悪い結果が得られます。Jaccard 類似度は、各セットの値を比較するために使用されます (何かをハッシュするかどうかに関係なく)。セットには順序が割り当てられていないため、同じ色の同じ数のピクセルを持つが、配置された画像スペースが異なると、誤検出が発生します。

たとえば、次の画像を見てください。

赤、緑 赤、緑

どちらも 100px x 100px で、50 ピクセルの赤と 50 ピクセルの緑があります。

Jaccard 類似度を使用して 2 つを比較すると、次のようになります (値が同じであるため、セットには色ごとに 1 つの要素しか含まれていないことに注意してください。必要に応じて、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 類似性結果 (およびしきい値) を生成するかを決定する必要があります。

さて、あなたの最初の質問に答えます：

宇宙の価値は？

この特定のケースでは、宇宙に存在する可能性のあるアイテムの数です。単一の RGB ピクセルを使用している場合、ユニバースは次のようになります。

255 * 255 * 255 = 16,581,375

シングリングでは、これらのアイテムの組み合わせを扱っているため、価値ははるかに高くなります。理想的には、minhash を実行する一連のハッシュ関数に対して、一連の完全なハッシュ関数を生成する必要があります。ただし、型システムの制限のため (または、別のストレージ メディアに非常に大きな数値を格納したくないため)、衝突を最小限に抑えるハッシュ関数に焦点を当てる必要があります。

アイテムのユニバースで可能なアイテムの数がわかっている場合は、衝突の数を減らすハッシュ関数を生成するのに役立ちます。

参照する実装では、このユニバース サイズを使用して乱数を生成し、それらの数値を渡して、理想的には最小限の衝突を生成するミンハッシング用の複数のハッシュ関数を生成します。

于 2012-08-10T17:23:49.620 に答える