局所性に敏感なハッシュまたはpHash？

Question

私は一般的な指紋を実装しようとしていますmemoizator：知的な指紋（画像の場合はpHash、オーディオの場合はchromaprintなど）で表現できるファイルがあり、飾り付けられた（高価な）関数が既に同様のファイルの場合、同じ結果が返されます（高価な計算を避ける）。

Locality Sensitive Hash（LSH）は、高価な多次元空間における問題のために一般的であり、優れた解決策です。

pHashは、画像に対して知覚的ハッシュを実装する優れたライブラリです。

したがって、pHashは多次元入力（画像）を1次元オブジェクト（ハッシュコード）に変換します。これはLSHとは異なります（LSHの多次元オブジェクト）。

私はpHashハッシュ値のための単次元LSHをどのように実装することができますか？または、いくつかの言葉で：どのようにビンに類似のpHash値をグループ化することができますか？古典的なLSHのアプローチ（それがなぜそうでなければ）に代わることができますか？

Answer 1

nrandom projectionsを使用すると、pHash領域を2^nバケットに分割することができます。同様のイメージは同じバケットから見つかる可能性が最も高いです。ハミングウェイト1の64個の可能なすべての整数でハッシュを排他的論理和（XOR）して、隣接するバケットを便利にチェックし、すべての近似マッチを見つけることができるようにすることもできます。

これは、ほぼ同じハッシュ（小さなハミング距離）の画像に興味がある場合にのみ有効です。より大きいハミング距離（8など）を許容したい場合は、すべてのマッチを効率的かつ正確に見つけるのが難しくなります。私はscanning through GPUでテーブル全体を非常に良いパフォーマンスを得て、私の3歳のラップトップのGT 650Mも7億ハッシュ/秒をチェックすることができます！

編集1：あなたの正規のコーナーが（この方法は、その中心が原点である）-1と1に座標が数学が簡単になり、64次元の立方体上の単一のコーナーとして64ビットのハッシュを考えることができます。 mイメージをサイズm x 64の行列M（1行/イメージ、ハッシュ/列の1ビット）として表現できます。 2^n異なるグループにこれを分割する

最も簡単な方法は、n 64次元ベクトルv_0, v_1, ..., v_nを（正規分布N（0,1）からの各ベクトル要素を選択）を生成することであり、これは（サイズ64 x nのマトリックスVのように表すことができます。 1列/ベクトル）。ランダム射影で述べたように直交性の強制があるかもしれませんが、ここでは省略します。

A = (M * V) > 0を計算すると、m x n行列（1つのイメージ/行、1つの投影/列）が得られます。次に、各行のバイナリ表現を数値に変換すると、2^nの可能性が異なり、同様のハッシュは同じバケットに終わる可能性が最も高いです。

このアルゴリズムは、バイナリ文字列だけでなく、データの任意の直交表現（SURF機能など）で機能します。私はバイナリハッシュのためのより簡単な（そして計算上より効率的な）アルゴリズムがあると確信していますが、これはランダム投影を実装する一つの方法です。

イメージが同じハッシュを持たない場合、同じバケットで終わることが保証されないため、XORringを提案しました。元のハッシュから可能性のあるすべての小さな偏差をチェックすることによって、可能性のあるマッチに対して可能な他のビンを見ることができます。

これは、コンピュータゲームエンジンが2Dマップをサイズxのセルのグリッドに分割する方法と似ていますが、半径がxのすべてのユニットを見つけるには、9個のセル1つは点+ 8のセルを含む）を使用して100％正確な答えを得る。