12

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

画像の一部は「コンピューター グラフィック」です。つまり、単色で塗りつぶされた四角形、ラスタライズされたテキストなどです。一方、「写真」画像もあります。豊富なカラー スペクトルを含み、ほとんどが滑らかで、妥当なノイズ振幅があります。

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

注: 2 つの画像 (またはその一部) が同一であるかどうかを知る必要があるだけです。つまり、類似した画像を照合する必要はありません。特徴認識、相関、およびその他の DSP 手法は必要ありません。

好ましいハッシュアルゴリズムは何だろうか。

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

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

CRT-32 のようなものを使用することはやや有望に見えますが、より高速なものを見つけたいと考えています。反復式について考えました。新しいピクセルごとに、次のように現在のハッシュ値が変化します。

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

モジュロ素数を実行すると、おそらく適切な分散が得られるはずなので、このオプションに傾いています。しかし、より良いバリアントがあるかどうか知りたいです。

前もって感謝します。

4

2 に答える 2

7

密接に一致する画像を見つけるために使用されるphash アルゴリズムhttp://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.htmlに関するこのチュートリアルをご覧ください。

于 2012-07-05T14:00:54.257 に答える
7

非常に高速にしたい場合は、画像全体を読み取らないように、ピクセルのランダムなサブセットを取得することを検討する必要があります。次に、これらのピクセルの値のシーケンスでハッシュ関数を計算します。同一の画像が同一のサブセットを生成し、結果として同一のハッシュ値が生成されるように、ランダムなサブセットは、固定シードを使用する決定論的疑似乱数ジェネレーターによって選択する必要があります。

これは、人工的な画像でもかなりうまく機能するはずです。ただし、少数のピクセルで互いに異なる画像がある場合、ハッシュの衝突が発生します。反復回数が多いほど、信頼性が向上します。その場合、たとえば、画像セットに 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
}
于 2012-07-05T13:50:43.930 に答える