18

現在、画像の分類に使用する画像ライブラリを拡張しています。重複する画像、変換された画像、および他の画像を含む、または他の画像に含まれる画像を検索したいと思います。
OpenCVからのSIFT実装をテストしましたが、非常にうまく機能しますが、複数のイメージではかなり遅くなります。スピードが速すぎる他の多くの画像関連のメタデータがすでにそこに保持されているので、特徴を抽出してデータベースに保存できると思いました。

新しい画像の特徴をデータベースの特徴と比較するための最速の方法は何でしょうか？
通常、比較は、kd-trees、FLANN、またはSOの別のスレッドで見つけたPyramid Match Kernelを使用してユークリッド距離を計算することで行われますが、まだあまり調べていません。

データベース内のkdツリーを効率的に保存および検索する方法がわからないため、現在3つのオプションしか表示されていません。
*確かに、データベース内のすべてのフィーチャまでのユークリッド距離をMySQLに計算させます。数枚以上の画像には不当な時間がかかります。
*最初にデータセット全体をメモリにロードし、kdツリーを構築します。これはおそらく高速ですが、非常にメモリを消費します。さらに、すべてのデータをデータベースから転送する必要があります。
*生成されたツリーをデータベースに保存してすべてをロードするのが最速の方法ですが、新しいイメージの場合と同様に、kdツリーを再構築してサーバーに送信する必要があるため大量のトラフィックも生成します。

私はOpenCVのSIFT実装を使用していますが、完全に設定されているわけではありません。このタスクにより適した（そしてほぼ同等に堅牢な）特徴抽出器があれば、誰かが提案してくれればうれしいです。

4

4 に答える 4

15

だから私は基本的にこれと非常によく似たことを数年前にしました。 検討したいアルゴリズムは、David Nister によって数年前に提案されたもので、論文は「ボキャブラリー ツリーによるスケーラブルな認識」です。彼らは、何百万もの画像にスケーリングできる問題に対する正確な解決策をほとんど持っています.

ここにアブストラクトへのリンクがあります。タイトルをググってダウンロード リンクを見つけることができます。 http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

基本的なアイデアは、階層的な k-means アルゴリズムを使用してツリーを構築してフィーチャをモデル化し、そのツリー内のフィーチャの疎な分布を利用して最近傍をすばやく見つけることです...またはそのようなものです。それから数年が経ちました私はそれに取り組みました。著者のウェブページでパワーポイントのプレゼンテーションを見つけることができます: http://www.vis.uky.edu/~dnister/Publications/publications.html

その他の注意事項:

  • ピラミッド マッチ カーネルを気にするつもりはありません。これは、複製/変換された画像の検出よりも、オブジェクトの認識を改善するためのものです。

  • この機能を SQL データベースに保存することはありません。アプリケーションによっては、密に計算するとサイズが元の画像サイズを超える可能性があるため、その場で機能を計算する方が効果的な場合があります。ボキャブラリ ツリー内のノードへのフィーチャまたはポインタのヒストグラムは、はるかに効率的です。

  • SQL データベースは、大規模な浮動小数点ベクトル計算を行うようには設計されていません。 データベースに何かを保存することはできますが、それを計算のツールとして使用しないでください。 SQLiteでこれを一度試してみましたが、非常にうまくいきませんでした。

  • これを実装することに決めた場合は、論文を詳細に読み、実装中にコピーを手元に置いておいてください。アルゴリズムを効率的に機能させるために非常に重要な細かい点がたくさんあるからです。

于 2010-08-19T17:53:55.970 に答える
2

重要なのは、これが SIFT の質問ではないということです。近似最近傍探索についての質問です。画像マッチングと同様に、これも未解決の研究課題です。「近似最近傍検索」をグーグルで試して、利用可能な方法の種類を確認できます。正確な結果が必要な場合は、「正確な最近傍検索」を試してください。

これらすべての幾何学的データ構造 (kd ツリーなど) のパフォーマンスは、次元数が増加するにつれて低下するため、重要なのは、SIFT 記述子をより少ない次元数 (代わりに 10-30 など) で表現する必要があるかもしれないということです。 256 ～ 1024 の範囲) を使用して、非常に効率的な最近傍検索を行います (たとえば、PCA を使用します)。

これができたら、データがMySQLに保存されるかどうかは二次的なものになると思います。

于 2010-08-18T13:29:12.037 に答える
1

ここでは速度は主な問題ではないと思います。主な問題は、機能を使用して必要な結果を得る方法です。

画像を分類したい場合 (例: 人物、車、家、猫)、Pyramid Match カーネルは一見の価値があります。これは実際にはローカルの特徴記述子のヒストグラムであるため、個々の特徴を相互に比較する必要はありません。「bag of words」として知られるアルゴリズムのクラスもあり、局所的な特徴を集めて「視覚的な語彙」を形成しようとします。この場合も、「ビジュアル ワード」を取得したら、SIFT 記述子のすべてのペア間の距離を計算する必要はありませんが、代わりに、各機能がどのクラスターに属しているかを判断します。一方、ある画像が別の画像に含まれているかどうかを判断したり、画像間の変換を計算したりするなど、画像のペア間の点の対応を取得したい場合は、

また、SIFT以外にもローカル機能があります。たとえば、SURF は SIFT に似た機能ですが、より高速に抽出でき、特定のタスクでより優れたパフォーマンスを発揮することが示されています。

重複を見つけることだけが目的の場合は、カラー ヒストグラムなどのグローバル イメージ記述子を使用して、明らかに異なるイメージを除外することで、検索を大幅に高速化できます。2 つのカラー ヒストグラムの比較は、それぞれが数百の SIFT 特徴を含む 2 つのセットを比較するよりも桁違いに高速です。カラー ヒストグラムを使用して候補の短いリストを作成し、SIFT を使用して検索を絞り込むことができます。

于 2010-08-18T15:56:39.513 に答える
1

ここで遊ぶことができるPythonのツールがいくつかあります。基本的には、SIFT 変換されたベクトルを使用し、各 128d シフト ベクトルの最も近い格子ハッシュを計算するパッケージです。ハッシュは重要な部分です。これは、局所性に敏感であるためです。つまり、R^n 空間に近いベクトルが同等のハッシュ衝突確率をもたらすことを意味します。私が提供する作業は、LSH の正確な検索リストをプルーニングするためのクエリ適応ヒューリスティックと、ハッシュ関数の最適化された CUDA 実装を提供するAndoniの拡張です。私はまた、すべてbsdの下で、素敵な視覚的フィードバックで画像データベース検索を行う小さなアプリを持っています（例外は、いくつかの追加の制限があるSIFTです）。

于 2011-12-20T19:23:14.990 に答える