ほぼ重複した画像の検出[終了]
https://stackoverflow.com/questions/1034900
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
特定の画像セットを互いに類似度で並べ替える高速な方法は何ですか。
現時点では、2つの画像間でヒストグラム分析を行うシステムがありますが、これは非常に費用のかかる操作であり、やり過ぎです。
最適には、各画像にスコア（たとえば、RGB平均などの整数スコア）を与えるアルゴリズムを探していますが、そのスコアで並べ替えることができます。同一のスコアまたは隣り合うスコアは重複する可能性があります。
0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994
画像あたりのRGB平均は最悪ですが、似たようなものはありますか？
解決
他のヒント
RGBヒストグラムの使用から離れることを検討することをお勧めします。
画像の2d Haarウェーブレット（音よりもずっと簡単で、平均化が多く、係数の重み付けに使用される平方根）を取得すると、画像のより良いダイジェストを取得できますウェーブレット内のk個の最大重み係数をスパースベクトルとして、正規化して保存し、サイズを縮小します。少なくとも事前に知覚的な重みを使用してR GとBを再スケーリングするか、重要性を減らしてクロミナンス情報をサンプリングできるように、YIQ（またはYCoCg、量子化ノイズを回避する）に切り替えることをお勧めします。
これらのスパース正規化ベクトルの2つのドット積を、類似性の尺度として使用できるようになりました。最大のドット積を持つ画像のペアは、構造が非常に似ています。これには、サイズ変更、色相のシフト、透かし入れに対してわずかに耐性があり、実装が簡単でコンパクトであるという利点があります。
kを増減することにより、ストレージと精度をトレードオフできます。
単一の数値スコアによるソートは、この種の分類問題では扱いにくいものになります。考えてみると、画像は1つの軸に沿ってのみ「変更」できる必要がありますが、変更はできません。これが特徴のベクトルが必要な理由です。 Haarウェーブレットの場合、画像で最もシャープな不連続が生じるおおよその場所です。ペアワイズで画像間の距離を計算できますが、距離メトリックのみであるため、線形順序付けでは、すべて等しい距離にある3つの画像の「三角形」を表現する方法がありません。 （つまり、すべてが緑の画像、すべてが赤の画像、すべてが青の画像について考えてください。）
つまり、問題の実際の解決策には、所有する画像の数でO（n ^ 2）操作が必要です。一方、メジャーを線形化することが可能であった場合、O（n log n）、またはメジャーが基数ソートに適している場合はO（n）のみが必要になる場合があります。ただし、実際にはセット全体をふるいにかける必要はないため、O（n ^ 2）を費やす必要はありません。あるしきい値よりも近いものを見つける必要があるだけです。したがって、いくつかの手法のいずれかを適用してスパースベクトル空間を分割することにより、すべての画像をすべての画像と単純に比較するよりも、「特定のしきい値よりも類似している画像のkを見つける」問題のはるかに速い漸近線を取得できますおそらく必要なのは...正確にあなたが求めたものではない場合。
いずれにせよ、私は数年前にこれを使用して、保存していたさまざまなテクスチャの数を最小限に抑えようとしたときに個人的に良い効果を出しましたが、このケースでは、より高度な形式のヒストグラム分類と比較しています）：
http://www.cs.princeton.edu/cass/papers/ spam_ceas07.pdf
より正確な検出が必要な場合は、Haarウェーブレット（またはヒストグラム）でminHashおよびtf-idfアルゴリズムを使用して、より堅牢に編集を処理できます。
http://cmp.felk.cvut.cz/~chum/ papers / chum_bmvc08.pdf
最後に、スタンフォードは、この種のアプローチのよりエキゾチックな変形に基づいた画像検索を行っています。ウェーブレットからより多くの特徴抽出を行って、画像の回転またはスケーリングされたセクションなどを見つけます。あなたがしたい仕事の。
http://wang14.ist.psu.edu/cgi- bin / zwang / regionsearch_show.cgi
高速多重解像度画像クエリという非常に信頼性の高いアルゴリズムを実装しました。そのための私の（古代の、メンテナンスされていない）コードはこちらです。
高速多重解像度画像クエリは、画像をYIQ色空間に基づいて3つの部分に分割します（RGBよりもマッチングの方が優れています）。次に、各色空間から最も顕著な特徴のみが利用可能になるまで、画像は基本的にウェーブレットアルゴリズムを使用して圧縮されます。これらのポイントはデータ構造に保存されます。クエリ画像は同じプロセスを経て、クエリ画像の顕著な特徴が保存されたデータベースの特徴と照合されます。一致が多いほど、画像が似ている可能性が高くなります。
このアルゴリズムは、「スケッチによるクエリ」によく使用されます。機能。私のソフトウェアでは、URLを介したクエリ画像の入力のみが許可されていたため、ユーザーインターフェイスはありませんでした。しかし、サムネイルをその画像の大きなバージョンに一致させるのに非常にうまく機能していることがわかりました。
私のソフトウェアよりも印象的なのは、 retrievr で、Flickrイメージを使用してFMIQアルゴリズムを試すことができます。ソースとして。とてもかっこいい！スケッチまたはソース画像を使用して試してみると、どのように機能するかを確認できます。
画像には多くの特徴があるため、平均的な明るさのように1つに絞り込まない限り、n次元の問題空間を扱っています。
世界の都市に単一の整数を割り当てるように頼んだら、どの都市が近いかわかりますが、結果は良くありません。たとえば、単一の整数としてタイムゾーンを選択し、特定の都市で良い結果を得ることができます。ただし、北極の近くの都市と南極の近くの別の都市は、惑星の両端にある場合でも同じタイムゾーンにある可能性があります。 2つの整数を使用すると、緯度と経度で非常に良い結果を得ることができます。問題は画像の類似性でも同じです。
とは言っても、同様の画像を一緒にクラスター化しようとするアルゴリズムがありますが、これは事実上あなたが求めているものです。これは、Picasaで顔検出を行うと発生します。顔を特定する前であっても、類似した顔をまとめて、類似した顔のセットを簡単に調べて、ほとんどの人に同じ名前を付けることができます。
Principle Component Analysisと呼ばれる手法もあります。これにより、n次元データをより少ない次元数に減らすことができます。したがって、n個の特徴を持つ画像は1つの特徴に縮小できます。ただし、これは画像を比較するための最良のアプローチではありません。
Cライブラリ（＆quot; libphash＆quot;- http://phash.org/ ）が計算されます。 「知覚的ハッシュ」ハッシュを比較することで同様の画像を検出できます（したがって、各画像を他のすべての画像と直接比較する必要はありません）が、残念ながら、私が試したときはあまり正確ではなかったようです。
「類似」を決定する必要があります。コントラスト？色相？
画像は「類似」です同じ写真に逆さまになりますか？
多くの「クローズコール」が見つかるはずです。画像を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つのハッシュを作成します。
もう1つ。 R、G、Bの重みを付けた場合、緑の重みが最も高く、次に赤、青の順に重みが人間の視覚感度に合わせます。
Webサービスの時代には、 http://tineye.com
を試すことができました。質問 同様の画像を識別するための良い方法 は質問に対する解決策を提供しているようです。
iは、他の重複画像検索ソフトウェアが画像に対して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);
最近の重複画像検出のアプローチでは、興味深い点の検出と、そのような点の周囲の領域を記述する記述子を使用します。多くの場合、 SIFT が使用されます。次に、記述子を定量化し、クラスターを視覚的な語彙として使用できます。
したがって、2つの画像の共通の視覚的な単語とこれらの画像のすべての視覚的な単語の比率を見ると、画像間の類似性を推定できます。興味深い記事がたくさんあります。それらの1つは重複画像の検出の近く：minHashとtf-idfの重み付け
たとえば、IMMI拡張とIMMIを使用すると、画像間の類似性を測定するさまざまな方法を調べることができます。 http：/ /spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension-for-rapidminer-5
しきい値を定義して何らかの方法を選択することにより、類似性を測定できます。
