c# - 重複する画像の削除

Question

数百ギガのサイズの写真画像のコレクションがあります。多くの写真は視覚的に複製されていますが、ファイルサイズ、解像度、圧縮などが異なります。

特定の画像処理方法を使用して、これらの重複画像を検索して削除することは可能ですか？

score 21 · Accepted Answer

私は最近、PHP イメージギャラリーでこのタスクを達成したいと考えていました。アップロードされた画像の「あいまいな」フィンガープリントを生成し、データベースで同じフィンガープリントを持つ画像をチェックして、それらが類似していることを示し、それらをより詳細に比較して類似度を判断できるようにしたいと考えていました。

アップロードされた画像のサイズを 150 ピクセル幅に変更し、グレースケールに縮小し、各色の値を最も近い 16 の倍数に丸め (0 から 255 までの 17 の可能なグレーの色合いを与える)、それらを正規化して、配列、それによって「あいまいな」色のヒストグラムを作成し、データベースで検索できるヒストグラムの md5sum を作成します。これは、アップロードされたファイルと視覚的に非常に類似している画像を絞り込むのに非常に効果的でした。

次に、アップロードされたファイルをデータベース内の各「類似」画像と比較するために、両方の画像を取得し、16x16 にサイズ変更して、ピクセルごとに分析し、各ピクセルの RGB 値を、対応するピクセルの値から引き離しました。他の画像、すべての値を合計してピクセル数で割ると、平均的な色の偏差が得られます。特定の値よりも小さいものは、重複していると判断されました。

全体は GD モジュールを使用して PHP で記述されており、数千の画像との比較は、アップロードされたファイルごとに数百ミリ秒しかかかりません。

私のコードと方法論はここにあります: http://www.catpa.ws/php-duplicate-image-finder/

score 5 · Accepted Answer

非常に単純なアプローチは次のとおりです。

画像をメモリ内のグレースケールに変換します。これにより、すべてのピクセルは0（黒）から255（白）までの数値になります。
画像を固定サイズに拡大縮小します。適切なサイズを見つけることは重要です。さまざまなサイズを試してみる必要があります。たとえば、各画像を64x64ピクセルに拡大縮小することはできますが、画像を小さくしたり大きくしたりすると、結果が良くなったり悪くなったりする場合があります。
すべての画像に対してこれを行ったら（はい、しばらく時間がかかります）、常に2つの画像をメモリにロードし、それらを互いに減算します。つまり、画像Aのピクセル（0,0）の値を減算し、画像Bのピクセル（0,0）の値を減算し、両方の（0,1）に対して同じことを行います。結果の値は正または負になる可能性があるため、常に絶対値を格納する必要があります（したがって、5は5になり、-8は8になります）。
これで、3番目の画像が画像AとBの「差分画像」（デルタ画像）になります。これらが同一の場合、デルタ画像はすべて黒になります（すべての値がゼロに差し引かれます）。「黒が少ない」ほど、画像の同一性は低くなります。画像が実際に（あなたの目に）同一であっても、スケーリングや明るさの変更などによって、デルタ画像が完全に黒くなることはなく、非常に暗いグレートーンしかないため、適切なしきい値を見つける必要があります。したがって、「平均誤差（デルタ画像の明るさ）が特定の値を下回っている場合でも、同じである可能性は十分にありますが、その値を上回っている場合は、そうではない可能性があります。適切なものを見つける」というしきい値が必要です。しきい値は、適切なスケーリングサイズを見つけるのと同じくらい難しいです。常に誤検知が発生します（画像は同一と見なされ、

このアルゴリズムは非常に低速です。実際には、グレースケール画像を作成するだけでもかなりの時間がかかります。次に、各GSイメージを互いに比較する必要があります。これもまた、何トンもの時間です。また、すべてのGSイメージを保存するには、多くのディスク容量が必要です。したがって、このアルゴリズムは非常に悪いですが、結果はそれほど単純ではありませんが、それほど悪くはありません。結果は驚くべきものではありませんが、私が最初に思っていたよりも優れています。

さらに良い結果を得る唯一の方法は、高度な画像処理を使用することであり、ここでそれは本当に複雑になり始めます。それはたくさんの数学を含みます（それの本当の多く）。これらが実装されている多くのシステムには優れたアプリケーション（重複ファインダー）があるため、自分でプログラムする必要がない限り、これらのソリューションのいずれかを使用することをお勧めします。私はこのトピックに関する多くの論文を読みましたが、これのほとんどは私の視野を超えているのではないかと思います。これらの論文に従って私が実装できるかもしれないアルゴリズムでさえ、それを超えています。つまり、何をする必要があるかは理解していますが、なぜそれが機能するのか、実際にどのように機能するのかわかりません。それは単なる魔法です;-)

score 5 · Accepted Answer

私は実際に、まさにこれを行うアプリケーションを作成しました。

基本的なレーベンシュタイン距離アルゴリズムを使用して画像の類似性を計算する以前のアプリケーションから始めましたが、その方法は多くの理由で望ましくありません。間違いなく、画像の類似性を判断するために見つけようとしている最速のアルゴリズムは、平均二乗誤差または平均絶対誤差のいずれかです(両方の実行時間は O(n) です。ここで、n は画像内のピクセル数であり、いずれかのアルゴリズムの実装をさまざまな方法でスレッド化することも簡単です)。Mecki の投稿は、実際には、私のアプリケーションが実行できる平均絶対誤差の実装にすぎません (必要に応じて、ブラウジングを楽しむためにコードも利用できます)。

いずれにせよ、このアプリケーションでは、まず画像をダウンサンプリングし (たとえば、すべてを 32*32 ピクセルにスケーリングします)、次にグレースケールに変換し、結果の画像を比較アルゴリズムで実行します。また、画像をさらに正規化するためのより高度な前処理アルゴリズムにも取り組んでいますが、まだ完成していません。

SSIMのように、MSE/MAE よりも確実に優れたアルゴリズムがあります (実際、視覚情報に適用されるこれら 2 つのアルゴリズムの問題は十分に文書化されています)が、コストがかかります。輝度、コントラスト、色のヒストグラムなど、画像の他の視覚的品質を比較しようとする人もいますが、単純にエラー信号を測定するのに比べて費用がかかります。

これらのフォルダーにある画像の数によっては、私のアプリケーションが機能する可能性があります。マルチスレッド (比較を実行する 8 つのプロセッサコアを完全にロードするのを見たことがあります) ですが、数百の画像を超える画像データベースに対してテストしたことはありません。数百ギガの画像は法外に大きく聞こえます。(単にディスクから読み取り、ダウンサンプリングし、グレースケールに変換し、メモリに格納するだけで、すべてを保持するのに十分なメモリがあると仮定しますが、おそらくそうではありません)。

score 5 · Accepted Answer

同じ寸法の 2 つの画像を比較するには、PerceptualDiffを試してください。X 個のピクセルのみが異なる画像を視覚的に区別できないと見なすなどのしきい値を許可します。

スケーリングやファイルタイプの違いにより視覚的な複製のサイズが異なる場合は、比較用の標準フォーマットを作成することをお勧めします。たとえば、ImageMagick を使用してすべての画像を 100x100 にスケーリングし、PNG ファイルとして保存します。

score 4 · Accepted Answer

これはまだ研究領域だと思います。時間があれば、関連するキーワードを以下に示します。

イメージコピーの検出
コンテンツベースの画像検索
画像の索引付け
画像重複除去

基本的に、各画像は処理 (索引付け) されて「画像署名」を生成します。類似の画像には類似の署名があります。画像が再スケーリングされた場合、おそらくそれらの署名はほぼ同じであるため、適切にクラスター化されます。一般的な署名のいくつかは、MPEG-7 記述子です。クラスター化するには、K-Means またはそのバリアントのいずれかで十分だと思います。ただし、おそらく何百万もの画像を処理する必要があるため、これが問題になる場合があります。

ウィキペディアのメインエントリへのリンクは次のとおりです:
http://en.wikipedia.org/wiki/CBIR

お役に立てれば。

score 1 · Accepted Answer

画像の類似性は、おそらく画像処理/AIのサブフィールドです。

優れた（つまり、パフォーマンスが高くスケーラブルな）ソリューションを探している場合は、論文からアルゴリズム/式を実装する準備をしてください。

すばやく汚いものが必要な場合は、Googleで画像の類似性を検索してください

これがあなたが望むことをするかもしれないC＃画像類似性アプリです。

基本的に、すべてのアルゴリズムは特徴を抽出して比較します。彼らが「特徴」をどのように定義するかは、彼らが基づいている数学モデルに依存します。

score 1 · Accepted Answer

これを簡単にハックするには、各画像の平均ピクセルの値をグレースケールで計算し、この値で並べ替えて、視覚的に比較するプログラムを作成します。非常によく似た画像が、並べ替えられた順序で互いに近くに表示されるはずです。

score 1 · Accepted Answer

非常に多くのデータを処理するには、コマンドラインツールが必要です。

考えられるすべての画像ペアを比較しても、そのような大規模な画像セットには対応できません。隣接する画像でのみさらなる比較が必要になるように、何らかのメトリックに従って画像のセット全体を並べ替える必要があります。

単純なメトリックの例は、画像内のすべてのピクセルの平均値であり、単一のグレースケール値として表されます。これは、複製に視覚的な変更がない場合にのみ機能します。非可逆ファイル形式を使用すると、視覚的な変更が生じる可能性もあります。

score 1 · Accepted Answer

常識にとらわれずに、画像メタデータを使用してデータセットを絞り込むことができる場合があります。たとえば、画像には、画像が撮影された日時を秒単位で表示するフィールドがある場合があります。重複は同じ値を持つ可能性があります。exiv2などのツールを使用して、このデータをより便利で並べ替え可能なテキスト形式にダンプできます (バッチ/シェルスクリプトの知識が少しあれば)。

カメラのメーカーやモデルなどのフィールドでさえ、1,000,000 枚の画像のセットを 10,000 枚の画像の 100 セットに減らすために使用できます。これは大幅な改善です。

score 0 · Accepted Answer

最も重要な部分は、ファイルを比較可能にすることです。

一般的な解決策は、すべての画像を特定の固定サイズとグレースケールにスケーリングすることです。次に、後で参照できるように、結果の画像を同じ名前の別のディレクトリに保存します。その後、ファイルサイズで並べ替えて、隣接するエントリを視覚的に比較することができます。

結果として得られる画像は、プログラムで類似性を検出するために特定の方法で定量化される場合があります（ブロック、線などの平均化）。

score 0 · Accepted Answer

gqviewプログラムには重複を見つけるためのオプションがあるので、そこで探してみてください。ただし、これは絶対確実ではないため、手動で確認するために、人間に複製を提示するヒューリスティックとしてのみ適しています。

score 0 · Accepted Answer

最もスケーラブルな方法は、各画像に指紋を保存することだと思います。次に、新しい画像が追加されたときに、重複をチェックするのは簡単なケースですSELECT id FROM photos where id='uploaded_image_id'(または、すべての画像のフィンガープリントを取得してから、重複のクエリを実行します)。

明らかに、実際のコンテンツが異なるため、単純なファイルハッシュは機能しません..

音響フィンガープリンティング/これには多くの実装があるため、このペーパーはコンセプトの良い出発点になる可能性があります。これは、画像フィンガープリンティングに関する論文です。

そうは言っても、もっと簡単なことでうまくいくかもしれません。画像のサイズを同じ幅または高さに変更し、から減算image_aしimage_b、差を合計するなどの基本的なこと。差の合計がしきい値を下回る場合、画像は重複しています。

これに関する問題は、すべての画像を他のすべての画像と比較する必要があることです。所要時間は指数関数的に増加します..

score 0 · Accepted Answer

少しのお金があれば、おそらく最初のパスを実行してどの画像が一致するかを判断したら、Amazon の Mechanical Turk のテストを作成できます。

https://www.mturk.com/mturk/welcome

基本的には、AMT が実際の人間のユーザーに表示する小さなウィジェットを作成し、ユーザーは基本的に「これらの 2 つの画像は同じですか?」という質問に答える必要があります。または、たとえば 5x5 の画像のグリッドを表示して、「これらの画像のどれが一致しますか?」と尋ねることもできます。次に、データを収集します。

もう 1 つのアプローチは、Luis Von Ahn ( http://www.cs.cmu.edu/~biglou/ ) によって最も有名に支持されているヒューマンコンピュテーションの原則を reCaptcha で使用することです。光学式文字認識を介して実行され、書籍のデジタル化に役立ちます。ユーザーに画像の改良を手伝ってもらうよう求めるキャプチャを作成できます。

score 0 · Accepted Answer

三角形の不等式に従う画像を比較する方法を考え出すことができる場合 (たとえば、d(a,b) が画像 a と b の差である場合、d(a,b) < d(a,c) +すべての a,b,c に対して d(b,c)) を使用する場合、BK ツリーは画像をインデックス化する効果的な方法であり、O(n) 時間ではなく O(log n) 時間で一致を見つけることができます。それぞれの画像。

圧縮/サイズ変更などの量を変えた後、一致が同じ画像に制限されている場合は、標準的なサイズ/カラーバランスなどに変換し、各ピクセルの差の二乗を単純に合計することが良い指標になる可能性があります。は三角形の不等式に従うため、BK ツリーを使用して効率的にアクセスできます。

score -1 · Accepted Answer

プログラミングの問題ではなく、手続き上の問題のように聞こえます。誰が写真をアップロードしますか? あなたか顧客か？写真をアップロードする場合は、寸法を固定の縮尺とファイル形式に標準化してください。そうすれば、比較が容易になります。ただし、現状では、数日または数週間の自由時間がない限り、画像を視覚的に比較して、自分またはチームが手動で重複画像を削除することをお勧めします。

観光用の画像なので、場所ごとに画像をグループ化する必要があるかもしれません。

c# - 重複する画像の削除

15 に答える 15

Related

Reference