約 200 万枚の jpeg 画像の非常に大きなデータベースがあります。それらの画像の重複をファジー検索したいと思います。重複画像とは、ピクセルの多く (約半分) が同じ値で、残りの R/G/B 値が約 +/- 3 ずれている 2 つの画像です。画像は肉眼と同じです。これは、jpeg を再圧縮することで得られる違いのようなものです。
2 つの画像が同一であるかどうかを検出する簡単な方法は既にあります。すべてのピクセルの差分輝度を合計し、しきい値と比較します。この方法は 100% 正確であることが証明されていますが、200 万枚に対して 1 枚の写真を作成するのは非常に時間がかかります (写真 1 枚あたり数時間)。
ハッシュテーブルでフィンガープリントを比較できるように、画像のフィンガープリントを取得したいと思います。比較する必要がある画像の数を確実に 100 に減らすことができたとしても、1 と 100 を比較するのに最適な状態になるでしょう。このための適切なアルゴリズムは何でしょうか?
O. Chum、J。Philbin、およびA. Zisserman、ほぼ重複した画像の検出：min-hashおよびtf-idfの重み付け、Proceedings of the British Machine Vision Conference、2008をご覧ください。これらは、あなたが抱えている問題を解決し、実証します。 146k画像の結果。しかし、私は彼らのアプローチを直接経験したことはありません。
単純なアイデア: 小さなサムネイル (50x50 ピクセル) を作成して「おそらく同一」の画像を見つけ、サムネイルのサイズを大きくしてより多くの画像を破棄します。
minHashのアイデアに基づいて構築...
私の考えは、現在データベースにあるすべての画像を使用して、100 個のルックアップ テーブルを作成することです。ルックアップ テーブルは、特定のピクセルの明るさから、同じピクセルで同じ明るさを持つ画像のリストにマッピングします。画像を検索するには、画像をハッシュ テーブルに入力し、100 個のリストを取得して、リストに表示された画像ごとにポイントを獲得します。各画像には 0 ～ 100 のスコアが付けられます。ポイントが最も多い画像が勝ちです。
合理的なメモリ制約内でこれを行う方法と、迅速に行う方法には多くの問題があります。ディスクに保存するには、適切なデータ構造が必要です。ハッシュ値やテーブル数などの微調整も可能です。さらに情報が必要な場合は、これを拡張できます。
私の結果はとても良かったです。1 台のコンピューターで約 24 時間で 100 万枚の画像のインデックスを作成でき、1 秒あたり 20 枚の画像を検索できます。私が知る限り、精度は驚異的です。
サムネイルからのハッシュについても良い: スケーリングされた重複が認識されます (ほとんど変更されていません)。
この問題はハッシュで解決できるとは思いません。ここに難点があります: 赤いピクセルがあり、3 と 5 を同じ値にハッシュしたいとします。では、5 と 7 を同じ値にハッシュし、7 と 9 なども同様に... すべてのピクセルを同じ値にハッシュするチェーンを作成できます。
代わりに私が試すことは次のとおりです。
200 万のノードすべてがツリーに挿入され、2 つのイメージは同じノードにある場合にのみ複製されます。右？違う！2 つの画像のピクセル値が 127 と 128 の場合、一方は外端 15 に入り、もう一方は外端 16 に入ります。したがって、実際にピクセルで区別する場合、その画像を 1 つまたは 2つの子に挿入できます。
B挿入します。3 つすべてが等しい場合もあれば、常に 3 つのうち 2 つが等しい場合もあります。しかし、3/8 の確率で、画像が現れるアウトエッジの数を 2 倍にします。物事がどれだけ深くなるかに応じて、多くの余分なノードを持つことができます。 B/8(B-3)/8(B+3)/8他の誰かが計算を行い、画像が重複しすぎないように 8 より大きい値で割る必要があるかどうかを確認する必要があります。良いニュースは、真のファンアウトが 32 ではなく約 4 であっても、必要なのは深さ 10 のツリーだけです。自由に使える十分な RAM があることを願っています。そうでない場合は、ツリーをファイルシステムに配置できます。
これがどうなるか教えてください！