41

類似画像検索問題

  • 何百万もの画像がpHashされ、Elasticsearch に保存されています。
  • フォーマットは "11001101...11" (長さ 64) ですが、変更できます (変更しないほうがよいでしょう)。

対象画像のハッシュ "100111..10" が与えられた場合、ハミング距離 8 以内で Elasticsearch インデックス内のすべての類似画像ハッシュを見つけたいと考えています。

もちろん、クエリは 8 より大きい距離の画像を返すことができ、Elasticsearch または外部のスクリプトは結果セットをフィルタリングできます。ただし、合計検索時間は 1 秒程度以内にする必要があります。

現在のマッピング

images各ドキュメントには、画像ハッシュを含むネストされたフィールドがあります。

{
  "images": {
    "type": "nested", 
    "properties": {
      "pHashFingerprint": {"index": "not_analysed", "type": "string"}
    }
  }
}

私たちの貧弱な解決策

事実: Elasticsearch ファジー クエリは、最大 2 のレーベンシュタイン距離のみをサポートします。

カスタム トークナイザーを使用して、64 ビット文字列を 16 ビットの 4 つのグループに分割し、4 つのファジー クエリで 4 つのグループ検索を実行しました。

アナライザ：

{
   "analysis": {
      "analyzer": {
         "split4_fingerprint_analyzer": {
            "type": "custom",
            "tokenizer": "split4_fingerprint_tokenizer"
         }
      },
      "tokenizer": {
         "split4_fingerprint_tokenizer": {
            "type": "pattern",
            "group": 0,
            "pattern": "([01]{16})"
         }
      }
   }
}

次に、新しいフィールド マッピング:

"index_analyzer": "split4_fingerprint_analyzer",

次にクエリを実行します。

{
   "query": {
      "filtered": {
         "query": {
            "nested": {
               "path": "images",
               "query": {
                  "bool": {
                     "minimum_should_match": 2,
                     "should": [
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "0010100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "1010100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "0110100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "1110100100111001",
                                 "fuzziness": 2
                              }
                           }
                        }
                     ]
                  }
               }
            }
         },
         "filter": {}
      }
   }
}

画像自体ではなく、一致する画像を持つドキュメントを返すことに注意してください。

問題は、他のドメイン固有のフィルターを追加して初期セットを減らした後でも、このクエリが何十万もの結果を返すことです。スクリプトは、ハミング距離を再計算する作業が多すぎるため、クエリに数分かかる場合があります。

予想どおり、3 と 4 に増やすminimum_should_matchと、検索する必要がある画像のサブセットのみが返されますが、結果のセットは小さくて高速です。== 3 では必要な画像の 95% 未満が返されますが、== 2minimum_should_matchの場合と同様に 100% (または 99.9%) が必要minimum_should_matchです。

n-gram で同様のアプローチを試みましたが、結果が多すぎるという同様の方法ではまだあまり成功していません。

他のデータ構造とクエリの解決策はありますか?

編集：

minimum_should_match評価プロセスにバグがあり、 == 2 が 100% の結果を返すことに気付きました。ただし、その後の処理時間は平均5秒かかります。スクリプトを最適化する価値があるかどうかを確認します。

4

7 に答える 7

20

私は可能な解決策をシミュレートして実装しました。これにより、高価な「ファジー」クエリがすべて回避されます。代わりに、インデックス時に、これらの 64 ビットからビットNのランダム サンプルを取得します。これはLocality-sensitive hashingMの例だと思います。したがって、ドキュメントごとに (およびクエリを実行する場合)、サンプル番号は常に同じビット位置から取得され、ドキュメント全体で一貫したハッシュが行われます。x

クエリは、比較的低いしきい値で's句でtermフィルターを使用します。しきい値が低いほど、「あいまいさ」が高くなります。残念ながら、このアプローチをテストするには、すべての画像のインデックスを再作成する必要があります。bool queryshouldminimum_should_match

{ "term": { "phash.0": true } }平均して各フィルターがドキュメントに一致するため、クエリがうまく機能しなかったと思い50%ます。16 ビット/サンプルでは、​​各サンプル2^-16 = 0.0015%がドキュメントに一致します。

次の設定でテストを実行します。

  • 1024 サンプル / ハッシュ (doc フィールドに保存"0"- "ff")
  • 16 ビット/サンプル (shortタイプに格納doc_values = true)
  • _source4 つのシャードと 100 万のハッシュ/インデックス、約 17.6 GB のストレージ (元のバイナリ ハッシュのみを保存およびサンプルしないことで最小化できます)
  • minimum_should_match= 150 (1024 のうち)
  • 400 万件のドキュメント (4 つのインデックス) でベンチマーク

サンプル数が少ないほど速度が速くなり、ディスク使用量が少なくなりますが、ハミング距離が 8 から 9 の間のドキュメントは十分に分離されていません (私のシミュレーションによると)。should1024が節の最大数のようです。

テストは、単一の Core i5 3570K、24 GB RAM、ES 用に 8 GB、バージョン 1.7.1 で実行されました。500 クエリの結果(以下の注を参照してください。結果は楽観的すぎます) :

Mean time: 221.330 ms
Mean docs: 197

Percentiles:
   1st = 140.51ms
   5th = 150.17ms
  25th = 172.29ms
  50th = 207.92ms
  75th = 233.25ms
  95th = 296.27ms
  99th = 533.88ms

これを 1,500 万のドキュメントに拡張する方法をテストしますが、100 万のドキュメントを生成して各インデックスに保存するには 3 時間かかります。

minimum_should_matchマッチの失敗と不正確なマッチの間の望ましいトレードオフを得るには、どのくらい低く設定する必要があるかをテストまたは計算する必要があります。これは、ハッシュの分布によって異なります。

クエリの例 (1024 フィールドのうち 3 つを表示):

{
  "bool": {
    "should": [
      {
        "filtered": {
          "filter": {
            "term": {
              "0": -12094,
              "_cache": false
            }
          }
        }
      },
      {
        "filtered": {
          "filter": {
            "term": {
              "_cache": false,
              "1": -20275
            }
          }
        }
      },
      {
        "filtered": {
          "filter": {
            "term": {
              "ff": 15724,
              "_cache": false
            }
          }
        }
      }
    ],
    "minimum_should_match": 150
  }
}

編集：さらにベンチマークを開始したとき、異なるインデックスに対して非常に似ていないハッシュを生成したことに気付きました。新しく生成されたドキュメントは、約 150 ～ 250 の一致/インデックス/クエリという結果になり、より現実的なものになるはずです。

前のグラフに新しい結果が表示されています。ES 用に 4 GB のメモリがあり、OS 用に残りの 20 GB のメモリがありました。1 ～ 3 個のインデックスを検索すると、パフォーマンスは良好でした (中央時間は 0.1 ～ 0.2 秒) が、これより多くを検索すると、大量のディスク IO が発生し、クエリに 9 ～ 11 秒かかるようになりました。これは、ハッシュのサンプルを少なくすることで回避できますが、再現率と精度率はそれほど良くありません。代わりに、64 GB の RAM を搭載したマシンを使用して、どこまで到達できるかを確認することもできます。

検索されたさまざまな数のインデックスに対するクエリ時間のパーセンタイル (ミリ秒単位)。

編集 2:_source: falseハッシュ サンプル (未加工のハッシュのみ) を使用してデータを再生成しました。これにより、ストレージ スペースが 60% 削減され、約 6.7 GB/インデックス (100 万ドキュメント) になりました。これは、小さなデータセットのクエリ速度には影響しませんでしたが、RAM が十分ではなく、ディスクを使用する必要がある場合、クエリは約 40% 高速になりました。

検索されたさまざまな数のインデックスに対するクエリ時間のパーセンタイル (ミリ秒単位)。

編集 3:fuzzy 3,000 万のドキュメントのセットに対して編集距離 2 で検索をテストし、それをハッシュの 256 のランダム サンプルと比較して、おおよその結果を取得しました。これらの条件下では、メソッドはほぼ同じ速度ですがfuzzy、正確な結果が得られ、追加のディスク容量は必要ありません。このアプローチは、ハミング距離が 3 を超えるような「非常にあいまいな」クエリにのみ役立つと思います。

于 2015-10-07T17:27:11.280 に答える
11

また、ラップトップの GeForce 650M グラフィックス カードでも CUDA アプローチを実装し、いくつかの良い結果が得られました。Thrustライブラリで実装は簡単でした。コードにバグがないことを願っています (徹底的にテストしていません) が、ベンチマークの結果に影響を与えるべきではありません。少なくとも、高精度タイマーthrust::system::cuda::detail::synchronize()を停止する前に呼び出しました。

typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;

// Maybe there is a simple 64-bit solution out there?
__host__ __device__ inline int hammingWeight(uint32_t v)
{
    v = v - ((v>>1) & 0x55555555);
    v = (v & 0x33333333) + ((v>>2) & 0x33333333);

    return ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

__host__ __device__ inline int hammingDistance(const uint64_t a, const uint64_t b)
{
    const uint64_t delta = a ^ b;
    return hammingWeight(delta & 0xffffffffULL) + hammingWeight(delta >> 32);
}

struct HammingDistanceFilter
{
    const uint64_t _target, _maxDistance;

    HammingDistanceFilter(const uint64_t target, const uint64_t maxDistance) :
            _target(target), _maxDistance(maxDistance) {
    }

    __host__ __device__ bool operator()(const uint64_t hash) {
        return hammingDistance(_target, hash) <= _maxDistance;
    }
};

線形検索は次のように簡単でした

thrust::copy_if(
    hashesGpu.cbegin(), hashesGpu.cend(), matchesGpu.begin(),
    HammingDistanceFilter(target_hash, maxDistance)
)

検索は 100% 正確で、ElasticSearch の回答よりもはるかに高速でした。CUDA は 50 ミリ秒で 3500 万のハッシュをストリーミングできました! 新しいデスクトップ カードは、これよりもはるかに高速であると確信しています。また、より多くのデータを処理するにつれて、非常に低い分散と検索時間の一貫した線形成長が得られます。ElasticSearch は、サンプリング データが膨らむため、大規模なクエリでメモリ不良の問題に遭遇しました。

ここでは、「これらの N ハッシュから、1 つのハッシュ H から 8 ハミング距離内にあるものを見つけてください」の結果を報告しています。これらを 500 回実行し、パーセンタイルを報告しました。

検索パフォーマンス

カーネル起動のオーバーヘッドはいくらかありますが、検索スペースが 500 万ハッシュを超えると、検索速度は 7 億ハッシュ/秒とかなり安定します。当然、検索するハッシュ数の上限は GPU の RAM によって設定されます。

検索パフォーマンス

更新: GTX 1060 でテストを再実行すると、毎秒約 38 億のハッシュがスキャンされます :)

于 2015-10-27T08:28:20.300 に答える
2

これは、機能ハッシュを個々のブールフィールドに分解して、次のようなクエリを実行できるようにする必要がある、エレガントではありませんが正確な（ブルートフォース）ソリューションです。

"query": {
    "bool": {
      "minimum_should_match": -8,
      "should": [
          { "term": { "phash.0": true } },
          { "term": { "phash.1": false } },
          ...
          { "term": { "phash.63": true } }
        ]
    }
}

これが fuzzy_like_this に対してどのように機能するかはわかりませんが、FLTの実装が非推奨になっている理由は、編集距離を計算するためにインデックス内のすべての用語にアクセスする必要があるためです。

（ここ/上記では、Luceneの基礎となる逆インデックスデータ構造と最適化されたセット操作を活用していますが、おそらくかなりまばらな機能を持っているため、有利に機能するはずです）

于 2015-09-29T15:18:17.123 に答える