n
random 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%正確な答えを得る。
「pHashスペースを2^nバケットに分割する」とはどういう意味ですか?あなたは例を挙げていただけますか? – justHelloWorld
さらに、ハミングウェイトが1の場合は、64ビット全体の意味であり、1が0と異なる場合。なぜ、ハッシュをXORして隣接するバケットをチェックし、すべての近似マッチを見つけられるのでしょうか?あなたもこの事例の例を教えてください。 – justHelloWorld
[this](http://stackoverflow.com/q/37802137/4480180)の質問をご覧ください。 – justHelloWorld