速く簡単な画像ハッシングアルゴリズム

Question

私は（できれば簡単で高速な）画像ハッシングアルゴリズムが必要です。ハッシュ値はルックアップテーブルで使用され、暗号化には使用されません。

画像の一部は、実線で塗りつぶされた矩形、ラスタライズされたテキストなどですが、妥当なノイズ振幅で、豊かな色のスペクトル、主に滑らかな画像も含まれています。

また、特定の画像部分にハッシュアルゴリズムを適用できるようにしたいと思います。つまり、イメージはグリッドセルに分割でき、各セルのハッシュ関数はこのセルの内容にのみ依存する必要があります。 2つの画像に共通の領域がある場合（適切に配置されている場合）、すばやく検出することができます。

注：私は2枚のだけの画像（またはその一部）が同じあるかどうかを知る必要があります。つまり、類似の画像に一致させる必要はなく、フィーチャー認識、相関、その他のDSP技術は必要ありません。

好きなハッシュアルゴリズムは何ですか？

グリッドセル内のすべてのピクセルを単にXORする「写真」画像の場合は、多かれ少なかれです。異なる画像に対する同じハッシュ値の確率はかなり低く、特に（ほぼ白色の）ノイズの存在がすべての潜在的な対称性を壊すためです。さらに、そのようなハッシュ関数のスペクトルはよく見えます（ほぼ同じ確率で任意の値が可能です）。

しかし、このような単純なアルゴリズムは、「人工的な」グラフィックスでは使用できません。同一ピクセル、繰り返しパターン、幾何学的オフセット不変性は、そのような画像には非常に一般的です。すべてのピクセルをXORすると、同じピクセルの偶数の画像に対して0が与えられます。

CRT-32のようなものを使用すると若干有望に見えますが、もっと速く何かを見つけたいと思います。私は、このオプションに傾いてるようモジュロ素数を行う

hashValue = (hashValue * /*something*/ | newPixelValue) % /* huge prime */ 

おそらく、良好な分散を与える必要があります。私は、新しい各ピクセルは、このような現在のハッシュ値が、変異し、反復式を考えました。しかし、私はより良いvariansがあるかどうかを知りたいです。

ありがとうございます。

Answer 1

非常に高速にしたい場合は、画像全体を読み取らないようにピクセルのランダムな部分集合を取ることを検討する必要があります。次に、それらのピクセルの値のシーケンスに対してハッシュ関数を計算します。ランダムサブセットは、固定シードを持つ確定的擬似乱数生成器によって選択されるべきであり、その結果、同一画像は同一のサブセットおよび結果として同一のハッシュ値を生成する。

これは人工的な画像であってもうまくいくはずです。しかし、画像の画素数が少ない場合、ハッシュ衝突が発生します。反復回数が増えるほど信頼性が向上します。このような場合、たとえば、画像セットに1つの異なるピクセルとのペアが存在する可能性が高い場合は、ハッシュ値を計算するためにすべてのピクセルを読み取る必要があります。疑似ランダム係数との単純な線形結合を取ることは、人工的な画像に対してさえも十分である。

単純なアルゴリズム

Random generator = new generator(2847) // Initialized with fixed seed 
int num_iterations = 100 

int hash(Image image) { 
    generator.reset() //To ensure consistency on each evaluation 
    int value = 0 
    for num_iteration steps { 
     int nextValue = image.getPixel(generator.nextInt()%image.getSize()).getValue() 
     value = value + nextValue*generator.nextInt() 
    } 
    return value 
} 

Answer 2

の擬似コードは、密接に一致する画像を検索するために使用されphashアルゴリズムhttp://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.htmlに、このチュートリアルを見てください。