問題タブ [locality-sensitive-hash]

これは私の最初の画像処理アプリケーションです。この不潔な農民に親切にしてください。

アプリケーション:

映画のポスターを含む写真 (携帯電話で撮影) が指定されたデータセットで最も類似した写真を見つけ、類似度スコアを返す高速なアプリケーション (精度よりもパフォーマンスが重要)を実装したいと考えています。データセットは、同様の写真 (映画のポスターを含む携帯電話で撮影) で構成されています。画像はさまざまなサイズ、解像度にすることができ、さまざまな視点から撮影できます (ただし、ポスターは常に右向きであると想定されているため、回転はありません)。

このようなアプリケーションの実装方法に関する提案は、すべて受け入れられます。

OPENCV の機能説明:

私は OpenCV を使用したことがなく、OpenCV による機能の検出と説明に関するこのチュートリアルを読みました。

私が理解していることから、これらのアルゴリズムはキーポイント (通常はコーナー) を見つけ、最終的に記述子 (各キーポイントを記述し、2 つの異なる画像の照合に使用される) を定義することになっています。それらのいくつか（FASTなど）はキーポイントのみを提供するため、「最終的に」を使用しました。

最も類似したイメージの問題と LSH:

上記の問題は、「画像が与えられたときに、データセット内で最も類似した画像をすばやく見つける方法」という問題を解決しません。それを行うために、以前のアルゴリズムのいずれかによって取得されたキーポイントと記述子の両方を使用できます。上記の問題は最近傍問題のように見えます。ローカリティ センシティブ ハッシングは、高次元空間でこの問題の近似解を見つけるための高速で一般的なソリューションです。

質問：

私が理解していないのは、LSH で以前のアルゴリズム (つまり、キーポイントと記述子) の結果を使用する方法です。

この問題の実装はありますか?

Kernelized Locality-Sensitive Hashingを読んでいます。これは明らかに、空間、関数、およびデータに適用されるカーネルの概念に基づいています。

私は数学と画像処理のこの概念にも自信がありません (それは私のドメインではないため、素朴で申し訳ありません)。

Locality Sensitive Hashing に関する元の論文を読みました。

複雑さはパラメータ ε の関数ですが、それが何であるかはわかりません。

その意味を教えてください。

LSH に関するこのペーパーのセクション 5. 、特に生成されたハッシュをバケット化する方法を理解しようとしています。リンクされた論文を引用：

それぞれ d ビットで構成されるビット ベクトルが与えられた場合、N = O(n 1/(1+epsilon) ) のビットのランダム順列を選択します。各ランダム置換 σ に対して、σ によって置換されたビットの辞書式順序で、ビット ベクトルのソートされた順序 O σ を維持します。クエリ ビット ベクトル q が与えられると、次の手順を実行して近似最近傍を見つけます。各順列 σ について、O σ でバイナリ検索を実行して、q に最も近い 2 つのビット ベクトルを見つけます (得られた辞書式順序で)。 σ によって並べ替えられたビットによって)。ここで、q に一致する最長のプレフィックスの長さの順に、バイナリ検索によって返された位置の上下の要素を調べて、ソートされた順序 O σ のそれぞれで検索します。これは、ソートされた順序 O σ ごとに 2 つのポインターを維持することによって実行できます (1 つは上に移動し、もう 1 つは下に移動します)。各ステップで、一致するプレフィックスが最も長い要素に対応するポインターの 1 つを上下に移動します。(ここで、O σ で一致する最長のプレフィックスの長さは、σ によって並べ替えられたビットを使用して q に対して計算されます)。このようにして 2N = O(n 1/(1+epsilon) ) ビットベクトルを調べます。調べたすべてのビット ベクトルの中で、q へのハミング距離が最も小さいものを返します。

私はこのアルゴリズムに混乱しており、その仕組みを理解できていないと思います。

トピックに関するこの質問はすでに見つけましたが、コメントの答えがわかりませんでした。また、ポイント2のこの質問でも同じアルゴリズムが説明されていますが、その仕組みがわかりません。

できるだけシンプルにするために、段階的にどのように機能するかを説明してもらえますか?

わからないことをリストにしてみましたが、実際は下手すぎてほとんどの文章がわかりません！

gsamarasの回答後に編集：

私は答えをほとんど理解しましたが、まだいくつかの疑問があります：

1. 順列をそれぞれソートする必要があるため、N順列を実行するための総コストはO(Nnlogn)

2. 上記の順列 + 並べ替えプロセスは、前処理中に 1 回だけ実行されるか、クエリごとにq実行されますか? 前処理でもすでにかなりコストがかかるようO(Nnlogn)です。クエリ時にこれを行う必要がある場合、それは惨事です:D

3. v0とv4を比較する最後のポイントで、qそれらの置換されたバージョンまたは元のバージョン (置換前) を比較します。

LSH に関するいくつかの論文を読みましたが、それが近似 k-NN 問題の解決に使用されていることを知っています。アルゴリズムを 2 つの部分に分けることができます。

1. D任意の値の次元 ( whereDは大きい) のベクトルを指定すると、一連のN( where N<<D) ハッシュ関数を使用してN次元のバイナリ ベクトルに変換します。

2. ハミング距離を使用して、フェーズ 1 から取得した特定のバイナリ コードのセットに検索手法を適用して、k-NN を見つけます。

N重要な点は、 XOR を使用すると次元のベクトルのハミング距離を高速に計算できることです。

とにかく、私は2つの質問があります：

1. ポイント 1. ORB のようなバイナリ記述子を使用する場合は、まだ必要ですか? ORB の記述子は既にバイナリであり、それらを比較するためにハミング距離を使用するのに、なぜ最初のポイントを実行する必要があるのでしょうか?

2. SIFT で記述された画像の変換はどのように行われますか? 各 SIFT 記述子は 128 ビットで、各画像は一連の記述子によって記述されます。そのため、行列descX128(descは使用される記述子の数) がありますが、LSH は通常、ベクトルを入力として受け入れます。

ローカリティ センシティブ ハッシュ (LSH) の重要な考え方は、近隣ポイントvは同じバケットにマッピングされる可能性が高く、互いに離れたポイントは異なるバケットにマッピングされる可能性が高いということです。ランダム射影を使用する場合、データベースにそれぞれ高次元 d の N 個のサンプルが含まれている場合、理論では、ランダムに生成された k 個のハッシュ関数を作成する必要がありますg(**v**) = (h_1(v),h_2(v),...,h_k(v))。したがって、任意のベクトル ポイントvについて、そのポイントは g 関数を使用して k 次元ベクトルにマッピングされます。この場合、ハッシュ コードは長さ / 次元 k を短縮したベクトルであり、バケットと見なされます。さて、衝突の確率を高めるために、理論によると、L 個のそのような g 関数g_1, g_2,...,g_Lをランダムに持つ必要があります。これは私が理解していない部分です。

質問 : 複数のハッシュ テーブルを作成する方法を教えてください。ハッシュ テーブルにはいくつのバケットが含まれていますか?

Sparse Projections for High-Dimensional Binary CodesYan Xiaらの論文に記載されているコードに従っています。al コードへのリンク

ファイル内Coding.m

X_queryはそれぞれ次元 d のクエリ データのセットで、1000 個のクエリ サンプルがあります。Rはランダムな射影で、bit はターゲットの縮小次元です。との出力は、B_query0 /1 の値を取る長さの文字列です。この方法で複数のハッシュ テーブルが作成されますか。つまり、ハッシュ テーブルの数ですか。どうしようか迷っています。詳しい解説とても参考になります。B_baseNkN

flannIndexin openCV は、バイナリ記述子を介して 2 つの画像を照合するように設計されています。

とにかく、LSHはCBIRで「2つの画像を比較する」のではなく、「データセット内で最も類似した画像を見つける」ために多用されていますが、これは明らかに異なるものです。

OpenCVでそのようなことをどのように実装できますか?

E2LSHマニュアルを引用します（この特定のライブラリに関することは重要ではありません。この引用は一般的なNNの問題に当てはまるはずです）：

E 2LSH を使用して最近傍問題を解くこともできます。この場合、クエリ q が与えられた場合、q に最も近い P 内の点をレポートするデータ構造が必要になります。これは、R = R1、R2、. . . Rt 。ここで、Rt は任意のクエリ ポイントからその最近傍までの最大距離よりも大きくする必要があります。次に、半径の昇順でデータ構造をクエリし、最初のポイントが見つかるたびに停止することで、最近傍を復元できます。

誰かがこれを言い換えてもらえますか? この手順は、R-near neighbor アプローチを使用して最近傍を見つけるためのものではありません。