161

2 つの異なる画像ファイル (どの形式を選択しても) が与えられた場合、一方が他方の違法なコピーであるかどうかを予測するプログラムを作成する必要があります。コピーの作成者は、回転、ネガの作成、些細な詳細の追加 (および画像の寸法の変更) などを行う場合があります。

この種の仕事をするためのアルゴリズムを知っていますか?

4

9 に答える 9

309

これらは単に私が問題について考えていたアイデアであり、試したことはありませんが、このような問題について考えるのは好きです!

あなたが始める前に

写真を正規化することを検討してください。一方の解像度が他方よりも高い場合は、一方を他方の圧縮バージョンにするオプションを検討してください。したがって、解像度を下げると、より正確な結果が得られる可能性があります。

画像のズームされた部分、およびさまざまな位置と回転を表す可能性のある、画像のさまざまな予測領域をスキャンすることを検討してください。画像の 1 つが別の画像の歪んだバージョンである場合、注意が必要になります。これらは、特定して妥協する必要がある一種の制限です。

Matlabは、画像をテストおよび評価するための優れたツールです。

アルゴリズムのテスト

一致が事前にわかっている、人間が分析した大規模なテスト データ セットを (少なくとも) テストする必要があります。たとえば、テスト データに 1,000 枚の画像があり、その 5% が一致する場合、かなり信頼できるベンチマークが得られます。10% の陽性を検出するアルゴリズムは、テスト データで 4% の陽性を検出するアルゴリズムほど良くありません。ただし、1 つのアルゴリズムですべての一致が検出される可能性がありますが、20% という大きな誤検出率もあるため、アルゴリズムを評価する方法はいくつかあります。

テスト データは、現実世界で見られると予想されるダイナミクスのできるだけ多くのタイプをカバーするように設計する必要があります。

各アルゴリズムが有用であるためには、ランダムな推測よりも優れたパフォーマンスを発揮する必要があることに注意することが重要です。そうでなければ、役に立たないのです!

次に、制御された方法でソフトウェアを現実の世界に適用し、生成された結果の分析を開始できます。これは、無限に続くソフトウェア プロジェクトのようなものです。いつでも微調整や改善を加えることができます。終わりのないプロジェクトの罠に陥りやすいため、設計する際にはそのことを念頭に置くことが重要です。

カラーバケット

2 つの写真を使用して、各ピクセルをスキャンし、色を数えます。たとえば、「バケット」がある場合があります。

white
red
blue
green
black

(明らかに、カウンターの解像度が高くなります)。「赤」のピクセルを見つけるたびに、赤のカウンターをインクリメントします。各バケットは、色のスペクトルを表すことができます。解像度が高いほど正確ですが、許容可能な差率で実験する必要があります。

合計を取得したら、それを 2 番目の画像の合計と比較します。各画像には、一致を識別するのに十分な独自のフットプリントがあることがわかる場合があります。

エッジ検出

エッジ検出を使用するのはどうですか。 (出典: wikimedia.org )代替テキスト

2 つの類似した画像を使用すると、エッジ検出により、使用可能でかなり信頼性の高い固有のフットプリントが得られます。

両方の写真を撮り、エッジ検出を適用します。おそらく、エッジの平均的な厚さを測定してから、画像がスケーリングされる可能性を計算し、必要に応じて再スケーリングします。以下は、さまざまな回転にガボール フィルター(エッジ検出の一種) を適用した例です。

代替テキスト

写真のピクセルをピクセルごとに比較し、一致するものと一致しないものを数えます。それらがエラーの特定のしきい値内にある場合は、一致しています。それ以外の場合は、特定のポイントまで解像度を下げて、一致の確率が向上するかどうかを確認できます。

関心領域

一部の画像には、特徴的なセグメント/関心領域がある場合があります。これらの領域はおそらく画像の残りの部分と非常に対照的であり、一致を見つけるために他の画像で検索するのに適したアイテムです. たとえば、次の画像をご覧ください。

代替テキスト
(出典: meetthegimp.org )

青色の建設作業員は関心のある領域であり、検索オブジェクトとして使用できます。この関心領域からプロパティ/データを抽出し、それらを使用してデータ セットを検索するには、おそらくいくつかの方法があります。

2 つ以上の関心領域がある場合は、それらの間の距離を測定できます。次の簡単な例を見てください。

代替テキスト
(出典: per2000.eu )

明確な関心領域が 3 つあります。領域１と２の間の距離は、２００ピクセル、１と３ ４００ピクセルの間、２と３ ２００ピクセルの間である。

他の画像で同様の関心領域を検索し、距離値を正規化し、一致する可能性があるかどうかを確認します。この手法は、回転およびスケーリングされた画像に適しています。関心のある領域が多いほど、各距離測定値が一致するため、一致の可能性が高くなります。

データセットのコンテキストについて考えることが重要です。たとえば、データ セットが現代美術の場合、関心領域はおそらく最終画像の基本的な部分になるように設計されているため、関心領域は非常にうまく機能します。ただし、建設現場の画像を扱っている場合、関心のある領域は違法なコピー者によって醜いものとして解釈され、自由にトリミング/編集される可能性があります. データセットの一般的な特徴を念頭に置いて、その知識を活用してみてください。

モーフィング

2 つの画像のモーフィングは、一連の手順を経て一方の画像を他方の画像に変換するプロセスです。

代替テキスト

これは、ある画像を別の画像にフェードするのとは異なることに注意してください!

画像をモーフィングできるソフトウェア パッケージは多数あります。これは伝統的にトランジション効果として使用されます。通常、2 つのイメージが途中で何かに変化することはなく、最終的な結果として一方の極端なイメージが他方の極端なイメージに変化します。

なぜこれが役立つのでしょうか？使用するモーフィング アルゴリズムによっては、画像の類似性とモーフィング アルゴリズムのいくつかのパラメータとの間に関係がある場合があります。

非常に単純化された例では、1 つのアルゴリズムは、行う変更が少ないほど高速に実行される可能性があります。これで、これら 2 つの画像が互いにプロパティを共有する可能性が高くなることがわかります。

この手法は、回転、ゆがみ、ゆがみ、ズームなど、あらゆる種類のコピーされた画像に適しています。繰り返しますが、これは私が持っていたアイデアにすぎません。私が知る限り、研究された学界に基づいているわけではありません (私はよく調べていません)。

圧縮

この質問に対する Ow の回答は素晴らしいです。AI を研究するこの種の手法について読んだことを覚えています。コーパス辞書の比較には非常に効果的です。

コーパスを比較する際の興味深い最適化の 1 つは、「The」、「A」、「And」など、あまりにも一般的であると考えられる単語を削除できることです。これらの単語は結果を薄めます。2 つのコーパスの違いを調べたいと思います。したがって、これらは処理前に削除できます。おそらく、圧縮前に取り除くことができる画像には、同様の共通信号がありますか? 調べる価値があるかもしれません。

圧縮率は、2 つのデータセットがどの程度似ているかを判断するための非常に迅速で合理的な方法です。圧縮がどのように機能するかを読むと、なぜこれがそれほど効果的であるかがよくわかります. 高速にリリースするアルゴリズムの場合、これはおそらく良い出発点になるでしょう。

透明度

繰り返しますが、特定の画像タイプ、gif png などの透明度データがどのように保存されているかはわかりませんが、これは抽出可能であり、データ セットの透明度と比較するための効果的な単純化されたカットアウトとして機能します。

反転信号

画像は単なる信号です。スピーカーからノイズを再生し、まったく同じ音量で完全に同期して別のスピーカーで反対のノイズを再生すると、それらは互いに打ち消し合います。

代替テキスト
(ソース: themotorreport.com.au )

画像を反転し、他の画像に追加します。十分なピクセルが白 (または黒? ニュートラル キャンバスと呼びます) である結果の画像が見つかるまで、繰り返し位置をスケーリング/ループして、肯定的な一致または部分的な一致を提供します。

ただし、どちらか一方に明るくする効果が適用されていることを除いて、等しい 2 つの画像を考えてみましょう。

代替テキスト
(ソース: mcburrz.com )

それらの 1 つを反転させてからもう 1 つに追加すると、私たちが目指しているニュートラルなキャンバスにはなりません。ただし、両方の元の画像のピクセルを比較すると、両者の間に明確な関係があることは間違いありません。

私は何年も色を研究しておらず、色スペクトルが線形スケールであるかどうかはわかりませんが、両方の写真の色差の平均係数を決定した場合は、この値を使用してデータを正規化してから処理することができますこのテクニック。

ツリー データ構造

最初は、これらは問題に合わないように見えますが、うまくいくと思います。

画像の特定のプロパティ (カラー ビンなど) を抽出することを考えて、ハフマン ツリーまたは同様のデータ構造を生成することができます。2 つのツリーの類似性を比較できる場合があります。これは、たとえば色のスペクトルが大きい写真データではうまく機能しませんが、漫画やその他の減色セット画像ではうまくいく可能性があります。

これはおそらくうまくいかないでしょうが、それはアイデアです。Trie データ構造は、辞書などのレキシコンの格納に優れています。プレフィックスツリーです。おそらく、レキシコンに相当する画像を作成して (ここでも色しか思い浮かびません)、トライを作成することは可能です。たとえば、300x300 の画像を 5x5 の正方形に縮小した場合、各 5x5 の正方形を一連の色に分解すると、結果のデータからトライを構築できます。2x2 の正方形に含まれる場合:

FFFFFF|000000|FDFD44|FFFFFF

24 レベルを拡張するかなりユニークなトライ コードがあり、レベルを増減すると (IE はサブ スクエアのサイズを縮小/拡大します)、より正確な結果が得られる可能性があります。

トライ ツリーの比較はかなり簡単で、効果的な結果が得られる可能性があります。

その他のアイデア

衛星画像の分類に関する興味深い論文の概要を偶然見つけました。概要は次のとおりです。

考慮されるテクスチャ測定値は、共起行列、グレーレベル差、テクスチャ トーン分析、フーリエ スペクトルから得られる特徴、およびガボール フィルターです。一部のフーリエ機能と一部のガボール フィルターは、特に単一の周波数帯域が分類に使用された場合に、適切な選択であることがわかりました。

これらの測定値をより詳細に調査することは価値があるかもしれませんが、それらの一部はデータ セットに関連しない場合があります。

その他の考慮事項

この種のことについてはおそらく多くの論文があるので、それらのいくつかを読むと、非常に技術的なものになる可能性があります. これは、コンピューティングにおいて非常に難しい領域であり、多くの人が同様のことを試みて無駄な時間を費やしています。シンプルに保ち、それらのアイデアに基づいて構築することが最善の方法です。ランダム一致率よりも優れた一致率を持つアルゴリズムを作成することは、かなり難しい課題であるはずであり、それを改善し始めることは、実際に達成するのが非常に難しくなり始めています.

それぞれの方法をテストして徹底的に微調整する必要があるでしょう。チェックする画像の種類に関する情報があれば、これは役に立ちます。たとえば、広告の多くにはテキストが含まれているため、テキスト認識を行うことは、特に他のソリューションと組み合わせた場合に、一致を見つけるための簡単でおそらく非常に信頼性の高い方法になります. 前述のように、データ セットの共通のプロパティを活用してみてください。

より正確な結果を生成するシステムを作成する方法の 1 つは、(その有効性に応じて) 重み付けされた投票を行うことができる代替の測定と手法を組み合わせることです。

この回答の冒頭で述べたように、複数のアルゴリズムを使用する場合、すべての陽性を見つけることができますが、偽陽性率は 20% です。別のものから返された誤検知を排除するのに効果的であること。

終わりのないプロジェクトを完成させようとすることに陥らないように注意してください。頑張ってください!

于 2010-08-10T00:05:35.473 に答える
36

論文を読んでください: Porikli、Fatih、Oncel Tuzel、Peter Meer。「リーマン多様体の平均に基づくモデル更新を使用した共分散追跡」。(2006) IEEE コンピュータ ビジョンとパターン認識。

このホワイト ペーパーで紹介した手法を使用して、隣接する Web カメラからキャプチャされた画像の重複領域を検出することに成功しました。私の共分散行列は、ソーベル、キャニー、スーザンのアスペクト/エッジ検出出力と、元のグレースケール ピクセルで構成されていました。

于 2008-08-23T03:57:38.857 に答える
34

アイデア：

  1. キーポイント検出器を使用して、画像内のいくつかの点のスケール不変および変換不変の記述子を見つけます (たとえば、SIFT、SURF、GLOH、または LESH)。
  2. キーポイントを両方の画像から同様の記述子に揃えるようにして (パノラマ スティッチのように)、必要に応じて画像の変換を可能にします (拡大縮小と回転、伸縮ストレッチなど)。
  3. 多くのキーポイントが適切に整列している場合 (そのような変換が存在し、そのキーポイントの整列エラーが低い、または変換の「エネルギー」が低いなど)、同様の画像が得られる可能性があります。

ステップ 2 は簡単ではありません。特に、スマート アルゴリズムを使用して、他の画像で最も類似したキーポイントを見つける必要がある場合があります。通常、ポイント ディスクリプタは非常に高次元 (100 個のパラメーターなど) であり、調べるポイントが多数あります。ここでは kd-trees が役立つかもしれませんが、ハッシュ ルックアップはうまく機能しません。

バリアント:

  • ポイントの代わりにエッジまたはその他の特徴を検出します。
于 2010-08-12T12:12:22.613 に答える
15

実際、見た目よりもはるかに単純ではありません:-) ニックの提案は良いものです。

まず、価値のある比較方法は基本的に、画像を別の形式に変換することによって機能することを覚えておいてください。これにより、同様の機能を簡単に選択できるようになります。通常、このようなものは非常に軽い読み物にはなりません...


私が考えることができる最も単純な例の 1 つは、単純に各画像の色空間を使用することです。2 つの画像の色分布が非常に類似している場合は、それらが同じものを示していると確信できます。少なくとも、フラグを立てたり、さらにテストを行ったりするのに十分な確実性を持つことができます。色空間で画像を比較すると、回転、スケーリング、トリミングなどにも抵抗します。もちろん、画像の大幅な変更や大幅な色の変更には耐えられません (単純な色相の変更でさえ、多少注意が必要です)。

http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace


別の例には、ハフ変換と呼ばれるものが含まれます。この変換は、基本的にイメージを線のセットに分解します。次に、各画像で「最も強い」線をいくつか取り、それらが一致しているかどうかを確認できます。回転とスケーリングを補正するために追加の作業を行うこともできます。この場合、数行を比較することは、画像全体に対して同じことを行うよりも計算作業がはるかに少ないため、それほど悪くはありません。

http://homepages.inf.ed.ac.uk/amos/hough.html
http://rkb.home.cern.ch/rkb/AN16pp/node122.html
http://en.wikipedia.org/wiki/ハフ変換

于 2008-09-17T03:22:28.140 に答える
8

In the form described by you, the problem is tough. Do you consider copy, paste of part of the image into another larger image as a copy ? etc.

What we loosely refer to as duplicates can be difficult for algorithms to discern. Your duplicates can be either:

  1. Exact Duplicates
  2. Near-exact Duplicates. (minor edits of image etc)
  3. perceptual Duplicates (same content, but different view, camera etc)

No1 & 2 の方が解決しやすいです。No 3. は非常に主観的で、まだ研究テーマです。No1 & 2 のソリューションを提供できます。どちらのソリューションも優れた画像ハッシュ ハッシュ ライブラリを使用します: https://github.com/JohannesBuchner/imagehash

  1. 完全な重複 完全な重複は、知覚ハッシュ測定を使用して見つけることができます。phash ライブラリはこれに非常に優れています。私は定期的にそれを使用して、トレーニング データをクリーンアップします。使用方法 (github サイトから) は次のように簡単です。
from PIL import Image
import imagehash

# image_fns : List of training image files
img_hashes = {}

for img_fn in sorted(image_fns):
    hash = imagehash.average_hash(Image.open(image_fn))
    if hash in img_hashes:
        print( '{} duplicate of {}'.format(image_fn, img_hashes[hash]) )
    else:
        img_hashes[hash] = image_fn
  1. ほぼ正確な重複 この場合、しきい値を設定し、互いの距離についてハッシュ値を比較する必要があります。これは、画像コンテンツの試行錯誤によって行う必要があります。
from PIL import Image
import imagehash

# image_fns : List of training image files
img_hashes = {}
epsilon = 50

for img_fn1, img_fn2 in zip(image_fns, image_fns[::-1]):
    if image_fn1 == image_fn2:
        continue

    hash1 = imagehash.average_hash(Image.open(image_fn1))
    hash2 = imagehash.average_hash(Image.open(image_fn2))
    if hash1 - hash2 < epsilon:
        print( '{} is near duplicate of {}'.format(image_fn1, image_fn2) )

If you take a step-back, this is easier to solve if you watermark the master images. You will need to use a watermarking scheme to embed a code into the image. To take a step back, as opposed to some of the low-level approaches (edge detection etc) suggested by some folks, a watermarking method is superior because:

It is resistant to Signal processing attacks ► Signal enhancement – sharpening, contrast, etc. ► Filtering – median, low pass, high pass, etc. ► Additive noise – Gaussian, uniform, etc. ► Lossy compression – JPEG, MPEG, etc.

It is resistant to Geometric attacks ► Affine transforms ► Data reduction – cropping, clipping, etc. ► Random local distortions ► Warping

透かしアルゴリズムについていくつかの調査を行うと、問題を解決するための正しい道を歩むことができます. (注: STIRMARKデータセットを使用してメソッドのベンチマークを行うことができます。これは、このタイプのアプリケーションの標準として認められています。

于 2010-08-12T05:02:45.463 に答える
5

これは単なる提案であり、うまくいかない可能性があります。私はこれについて呼ばれる用意があります。

これにより、偽陽性が生成されますが、偽陰性ではないことを願っています。

  1. 両方の画像のサイズを変更して、同じサイズにします (両方の画像で幅と長さの比率が同じであると仮定します)。

  2. 可逆圧縮アルゴリズム (gzip など) を使用して、両方のイメージのビットマップを圧縮します。

  3. ファイル サイズが似ているファイルのペアを見つけます。たとえば、ファイル サイズの類似度でファイルのすべてのペアを並べ替えて、上位の X を取得できます。

私が言ったように、これは間違いなく偽陽性を生成しますが、うまくいけば偽陰性は発生しません. これは 5 分で実装できますが、Porigil et. アル。おそらく大がかりな作業が必要になるでしょう。

于 2009-08-26T01:00:00.267 に答える
4

考えられるすべての向きと否定的なバージョンにアプローチを適用する意思がある場合、(信頼性の高い) 画像認識の良いスタートは固有顔を使用することだと思います: http://en.wikipedia.org/wiki/Eigenface

別のアイデアは、両方の画像をそれらのコンポーネントのベクトルに変換することです。これを行う良い方法は、x*y 次元 (x は画像の幅、y は高さ) で動作するベクトルを作成し、各次元の値を (x,y) ピクセル値に適用することです。次に、一致する場合と一致しない場合の 2 つのカテゴリを使用して、K-Nearest Neighbors のバリアントを実行します。元の画像に十分近い場合は一致カテゴリに収まりますが、そうでない場合はそうではありません。

K Nearest Neighbours(KNN) はここで見つけることができます。ウェブ上にも他の良い説明があります: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

KNN の利点は、元の画像と比較するバリアントが多いほど、アルゴリズムがより正確になることです。欠点は、最初にシステムをトレーニングするために画像のカタログが必要なことです。

于 2010-08-09T23:36:25.980 に答える
1

画像の違法コピーを検出するためのまったく別のアプローチを検討する場合は、透かしを検討できます。(1.4から)

...品質を損なうことなく著作権情報をデジタル オブジェクトに挿入します。デジタル オブジェクトの著作権が疑わしい場合は常に、この情報を抽出して正当な所有者を特定します。元の購入者の身元を著作権所有者の身元とともにエンコードすることも可能で、これにより、不正コピーの追跡が可能になります。

複雑な分野でもありますが、透かし情報を全体的な画像の変更を通じて保持できるようにする手法があります: (1.9 から)

... 妥当な強度の信号変換では、透かしを削除できません。したがって、透かしを取り除こうとする著作権侵害者は、ドキュメントの価値を著しく低下させて商業的利益をもたらさない限り、成功しません。

もちろん、よくある質問ではこのアプローチの実装について「...非常に難しい」としていますが、成功すれば、確率ではなく、画像がコピーであるかどうかについて高い信頼性が得られます。

于 2009-04-03T14:10:43.900 に答える