image - ほぼ重複した画像の検出

Question

特定の一連の画像を相互の類似性によって並べ替える高速な方法は何ですか。

現時点では、2 つの画像間でヒストグラム分析を行うシステムを使用していますが、これは非常にコストのかかる操作であり、やり過ぎに思えます。

最適には、各画像にスコア (たとえば、RGB 平均などの整数スコア) を与えるアルゴリズムを探しており、そのスコアで並べ替えることができます。同一のスコアまたは隣り合ったスコアは重複の可能性があります。

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

画像ごとのRGB平均は最悪です。似たようなものはありますか?

score 71 · Accepted Answer

画像検索と類似性測定に関する多くの研究が行われています。簡単な問題ではありません。一般に、画像が非常に似ているかどうかを判断するには、単一のint画像では十分ではありません。偽陽性率が高くなります。

ただし、多くの調査が行われているため、その一部を確認してください。たとえば、この論文(PDF) では、大量のデータを保存せずに重複する画像をすばやく見つけるのに適したコンパクトな画像フィンガープリンティングアルゴリズムが提供されています。堅牢なものが必要な場合は、これが正しいアプローチのようです。

よりシンプルで、よりアドホックなものを探している場合は、この SO の質問にいくつかの適切なアイデアがあります。

score 50 · Accepted Answer

RGB ヒストグラムだけを使用することから離れることを検討することをお勧めします。

画像の 2 次元 Haar ウェーブレットを取得し (思ったよりもずっと簡単で、係数の重み付けに多くの平均化と平方根を使用するだけです)、最大の k を保持すると、画像のより優れたダイジェストを取得できます。ウェーブレットの重み付き係数をスパースベクトルとして正規化し、それを保存してサイズを縮小します。少なくとも事前に知覚重みを使用して RG と B を再スケーリングするか、YIQ (または量子化ノイズを回避するために YCoCg) に切り替えることをお勧めします。これにより、クロミナンス情報を重要度を下げてサンプリングできます。

これらのスパースな正規化されたベクトルの 2 つの内積を、類似性の尺度として使用できるようになりました。最大の内積を持つ画像ペアは、構造が非常に似ています。これには、サイズ変更、色相シフト、および透かしに対してわずかに耐性があり、実装が非常に簡単でコンパクトであるという利点があります。

k を増減することで、ストレージと精度をトレードオフできます。

単一の数値スコアによる並べ替えは、この種の分類問題では扱いにくくなります。考えてみると、画像が 1 つの軸に沿ってのみ「変更」できる必要がありますが、そうではありません。これが、特徴のベクトルが必要な理由です。Haar ウェーブレットの場合、画像内で最も鋭い不連続が発生するおおよその場所です。ペアごとに画像間の距離を計算できますが、距離メトリックしかないため、線形順序付けでは、すべて同じ距離にある 3 つの画像の「三角形」を表現する方法がありません。(つまり、すべて緑の画像、すべて赤の画像、すべて青の画像を考えてみてください。)

つまり、問題に対する実際の解決策には、所有している画像の数で O(n^2) 操作が必要です。一方、メジャーを線形化することが可能であれば、O(n log n)、またはメジャーが基数ソートに適している場合は O(n) だけを必要とする可能性があります。つまり、O(n^2) を費やす必要はありません。実際には、セット全体をふるいにかける必要はなく、あるしきい値よりも近いものを見つけるだけでよいからです。したがって、スパースベクトル空間を分割するいくつかの手法の 1 つを適用することで、すべての画像をすべての画像と単純に比較するよりも、「特定のしきい値よりも類似している画像の k 個を見つける」問題の漸近線をはるかに高速に取得できます。あなたが必要とする可能性があります...正確にあなたが求めたものではないにしても。

いずれにせよ、私は数年前にこれを使用して、保存していたさまざまなテクスチャの数を最小限に抑えようとしたときに個人的に良い効果をもたらしましたが、この分野ではその有効性を示す多くの研究ノイズもありました (この場合、それをより洗練された形のヒストグラム分類に変換します):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

より正確な検出が必要な場合は、minHash および tf-idf アルゴリズムを Haar ウェーブレット (またはヒストグラム) と共に使用して、編集をより確実に処理できます。

http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

最後に、スタンフォードは、ウェーブレットからより多くの特徴抽出を行い、画像の回転またはスケーリングされたセクションなどを見つけることに基づいて、この種のアプローチのよりエキゾチックな変形に基づく画像検索を行っていますが、それはおそらくあなたの作業量をはるかに超えています.したいです。

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

score 15 · Accepted Answer

私は、高速多重解像度画像クエリと呼ばれる非常に信頼性の高いアルゴリズムを実装しました。そのための私の（古くてメンテナンスされていない）コードはhereです。

高速多重解像度画像クエリが行うことは、YIQ 色空間に基づいて画像を 3 つの部分に分割することです (RGB よりも違いを一致させるのに適しています)。次に、各色空間の最も顕著な特徴のみが利用可能になるまで、ウェーブレットアルゴリズムを使用して画像が基本的に圧縮されます。これらのポイントは、データ構造に格納されます。クエリ画像は同じプロセスを通過し、クエリ画像の顕著な特徴が保存されたデータベースの特徴と照合されます。一致が多いほど、画像が類似している可能性が高くなります。

このアルゴリズムは、「スケッチによるクエリ」機能によく使用されます。私のソフトウェアでは、URL 経由でクエリ画像を入力することしか許可されていなかったため、ユーザーインターフェイスはありませんでした。ただし、サムネイルをその画像の大きなバージョンに一致させるには、非常にうまく機能することがわかりました.

私のソフトウェアよりもはるかに印象的なのは、 Flickr 画像をソースとして使用してFMIQアルゴリズムを試すことができる retrievr です。とてもかっこいい！スケッチまたはソースイメージを使用して試してみると、うまく機能することがわかります。

score 10 · Accepted Answer

写真には多くの特徴があるため、平均的な明るさのように 1 つに絞り込まない限り、n 次元の問題空間を扱っていることになります。

世界の都市に単一の整数を割り当てるように頼んだら、どの都市が近いかがわかりますが、良い結果にはなりません。たとえば、単一の整数としてタイムゾーンを選択すると、特定の都市で良い結果が得られる場合があります。ただし、北極に近い都市と南極に近い別の都市は、地球の反対側にある場合でも、同じタイムゾーンにある可能性があります。2 つの整数を使用できるようにすると、緯度と経度で非常に良い結果が得られます。問題は、画像の類似性についても同じです。

そうは言っても、似たような画像をまとめようとするアルゴリズムがあり、これは事実上、あなたが求めているものです. Picasa で顔検出を行うと、このようになります。顔を識別する前であっても、似たような顔をまとめてクラスタ化するため、似たような顔のセットを簡単に調べて、それらのほとんどに同じ名前を付けることができます。

また、主成分分析と呼ばれる手法もあり、n 次元のデータを任意の次元数に減らすことができます。したがって、n 個の特徴を持つ画像を 1 つの特徴に減らすことができます。ただし、これはまだ画像を比較するための最良の方法ではありません。

score 8 · Accepted Answer

画像の「知覚ハッシュ」を計算し、ハッシュを比較することで類似の画像を検出できるようにするCライブラリ（「libphash」-http://phash.org/ ）があります（したがって、各画像を比較する必要はありません）。他のすべての画像に対して直接）が、残念ながら、私が試したときはあまり正確ではなかったようです。

score 5 · Accepted Answer

5

Web サービスの時代にhttp://tineye.comを試すことができます

于 2009-07-02T06:16:39.800 に答える

score 5 · Accepted Answer

「似ている」とは何かを判断する必要があります。対比？色相？

画像は同じ画像を上下逆さまにしたものと「似ている」か?

画像を 4x4 のピースに分割し、各グリッドセルの平均色を取得することで、多くの「ヒヤリハット」を見つけることができると思います。画像ごとに 16 のスコアがあります。類似性を判断するには、画像間の差の二乗和を計算するだけです。

色相、明るさ、コントラストなどの単一の概念に反しない限り、単一のハッシュは意味がないと思います。

これがあなたのアイデアです：

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

まず、これらは R*(2^16)+G*(2^8)+B などの 10 進数であると仮定します。赤が過度に重み付けされているため、明らかにそれは良くありません。

HSV空間に移動する方が良いでしょう。HSV のビットをハッシュに分散させることも、H または S または V を個別に解決することも、画像ごとに 3 つのハッシュを持つこともできます。

もう一つ。R、G、B の重み付けを行う場合は、人間の視覚感度に合わせて、緑の重み付けを最も高くし、次に赤、次に青の重み付けを行います。

score 2 · Accepted Answer

質問類似画像を識別する良い方法は? あなたの質問に対する解決策を提供しているようです。

score 1 · Accepted Answer

他の重複画像検索ソフトウェアが画像に対して FFT を実行し、さまざまな周波数の値をベクトルとして保存すると仮定しました。

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

次に、2 つの画像の重みベクトル間の距離を計算することで、2 つの画像を比較して等しいかどうかを確認できます。

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

score 1 · Accepted Answer

ほぼ重複した画像の検出を検出するための最新のアプローチのほとんどは、興味深い点の検出と、そのような点の周囲の領域を記述する記述子を使用します。多くの場合、 SIFTが使用されます。次に、記述子を量子化し、クラスターをビジュアルワードボキャブラリとして使用できます。

したがって、これらの画像のすべての視覚的な単語に対する 2 つの画像の共通の視覚的な単語の比率を見ると、画像間の類似性が推定されます。興味深い記事がたくさんあります。それらの 1 つは、ほぼ重複する画像の検出です: minHash および tf-idf 重み付け

score 1 · Accepted Answer

たとえば、IMMI 拡張機能と IMMI を使用すると、画像間の類似性を測定するさまざまな方法を調べることができます。 for-rapidminer-5

いくつかのしきい値を定義し、いくつかの方法を選択することで、類似性を測定できます。

score 1 · Accepted Answer

解決策の 1 つは、バブルソートを実行するために必要なすべてのペアの画像に対してRMS/RSS比較を実行することです。次に、各画像に対してFFTを実行し、軸の平均化を行って、並べ替えのインデックスとして使用する各画像の単一の整数を取得できます。無視する差異の小ささと必要なスピードアップに応じて、元のサイズを変更した (25%、10%) バージョンで比較を行うことを検討してください。これらのソリューションが興味深いかどうか教えてください。議論したり、サンプルコードを提供したりできます。

image - ほぼ重複した画像の検出

12 に答える 12

Related

Reference