432

画像のベーステーブルを作成し、それと新しい画像を比較して、新しい画像がベースの正確な（または近い）複製であるかどうかを判断しようとしています。

たとえば、同じ画像の保存を数百回減らしたい場合は、そのコピーを1つ保存して、その画像への参照リンクを提供できます。新しい画像が入力されたら、既存の画像と比較して、重複していないことを確認します...アイデア？

私のアイデアの1つは、小さなサムネイルに縮小してから、100ピクセルの位置をランダムに選択して比較することでした。

4

10 に答える 10

483

以下に、この問題を解決する 3 つの方法を示します (他にも多くの方法があります)。

  • 1 つ目は、コンピューター ビジョンの標準的なアプローチであるキーポイント マッチングです。これを実装するには、ある程度の背景知識が必要な場合があり、遅くなる可能性があります。

  • 2 番目の方法は、基本的な画像処理のみを使用し、最初の方法よりも高速になる可能性があり、簡単に実装できます。ただし、理解しやすさは向上しますが、堅牢性に欠けます。スケーリング、回転、または変色した画像ではマッチングが失敗します。

  • 3 番目の方法は高速で堅牢ですが、実装が最も難しい可能性があります。

キーポイントマッチング

無作為に 100 点を選ぶよりも、重要な点を 100 点選ぶほうがよいでしょう。画像の特定の部分 (特にエッジとコーナー) は他の部分よりも多くの情報を持っており、これらはスマートな画像マッチングに使用する必要がある部分です。Google の「キーポイント抽出」と「キーポイント マッチング」を検索すると、このテーマに関するかなりの数の学術論文が見つかります。最近では、さまざまなスケール、回転、および照明の下で画像を一致させることができるため、SIFT キーポイントは間違いなく最も人気があります。SIFT の実装の一部は、こちらにあります。

キーポイント マッチングの欠点の 1 つは、単純な実装の実行時間です。O(n^2m) です。ここで、n は各画像のキーポイントの数、m はデータベース内の画像の数です。四分木やバイナリ スペース パーティショニングなど、一部の巧妙なアルゴリズムは、最も近い一致をより速く見つけることができます。

代替ソリューション: ヒストグラム法

堅牢性は劣りますが高速になる可能性がある別の解決策は、各画像の特徴ヒストグラムを作成し、ヒストグラムが入力画像のヒストグラムに最も近い画像を選択することです。私は学部生としてこれを実装し、3 つのカラー ヒストグラム (赤、緑、青) と 2 つのテクスチャ ヒストグラム (方向とスケール) を使用しました。以下に詳細を説明しますが、これはデータベースの画像と非常によく似た画像を照合する場合にのみうまく機能することに注意してください。この方法では、再スケーリング、回転、または変色した画像は失敗する可能性がありますが、トリミングなどの小さな変更によってアルゴリズムが壊れることはありません

カラー ヒストグラムの計算は簡単です。ヒストグラム バケットの範囲を選択し、各範囲について、その範囲内の色のピクセル数を集計するだけです。たとえば、「緑」のヒストグラムを考えてみましょう。ヒストグラムに 4 つのバケット (0 ～ 63、64 ～ 127、128 ～ 191、および 192 ～ 255) を選択するとします。次に、各ピクセルについて、緑の値を確認し、集計を適切なバケットに追加します。集計が完了したら、各バケットの合計を画像全体のピクセル数で割り、緑チャネルの正規化されたヒストグラムを取得します。

テクスチャ方向ヒストグラムについては、まず画像のエッジ検出を実行しました。各エッジ ポイントには、エッジに垂直な方向を指す法線ベクトルがあります。法線ベクトルの角度を 0 と PI の間の 6 つのバケットの 1 つに量子化しました (エッジは 180 度対称であるため、-PI と 0 の間の角度を 0 と PI の間に変換しました)。各方向のエッジ ポイントの数を集計した後、テクスチャの方向を表す正規化されていないヒストグラムが得られます。これは、各バケットを画像内のエッジ ポイントの総数で割ることによって正規化されます。

テクスチャ スケール ヒストグラムを計算するために、エッジ ポイントごとに、同じ方向で次に近いエッジ ポイントまでの距離を測定しました。たとえば、エッジ ポイント A の方向が 45 度の場合、アルゴリズムは、方向が 45 度 (または妥当な偏差内) の別のエッジ ポイントが見つかるまで、その方向に進みます。各エッジ ポイントのこの距離を計算した後、それらの値をヒストグラムにダンプし、エッジ ポイントの総数で割って正規化します。

これで、画像ごとに 5 つのヒストグラムができました。2 つの画像を比較するには、各ヒストグラム バケット間の差の絶対値を取得し、これらの値を合計します。たとえば、画像 A と B を比較するには、次のように計算します。

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1|

緑のヒストグラムの各バケットについて、他のヒストグラムについて繰り返し、すべての結果を合計します。結果が小さいほど、一致は良好です。データベース内のすべての画像について繰り返し、結果が最小の一致が勝ちます。おそらく、アルゴリズムが一致が見つからなかったと結論付けるしきい値が必要になるでしょう。

3 番目の選択肢 - キーポイント + 決定木

おそらく他の 2 つよりもはるかに高速な 3 つ目のアプローチは、セマンティック テクストン フォレスト(PDF) を使用することです。これには、単純なキーポイントを抽出し、コレクション決定木を使用して画像を分類することが含まれます。これは、コストのかかるマッチング プロセスを回避するため、単純な SIFT キーポイント マッチングよりも高速であり、キーポイントは SIFT よりもはるかに単純であるため、キーポイント抽出ははるかに高速です。ただし、ヒストグラム法に欠けていた重要な機能である、回転、スケール、および照明に対する SIFT 法の不変性が保持されます。

更新：

私の間違いです。Semantic Texton Forests の論文は、特に画像マッチングに関するものではなく、領域のラ​​ベル付けに関するものです。マッチングを行う元の論文はこれです: Keypoint Recognition using Randomized Trees . また、以下の論文はアイデアを発展させ続けており、最新技術を表しています (c. 2010):

于 2009-05-09T21:27:43.247 に答える
96

私が知っている最善の方法は、知覚ハッシュを使用することです。このようなハッシュの優れたオープン ソース実装が次の場所で入手できるようです。

http://phash.org/

主なアイデアは、元の画像ファイルの顕著な特徴を識別し、それらの特徴のコンパクトな表現をハッシュすることによって (画像データを直接ハッシュするのではなく)、各画像を小さなハッシュ コードまたは「指紋」に縮小することです。これは、画像を小さな拇印サイズの画像に縮小して拇印を比較するなどの単純なアプローチよりも、偽陽性率が大幅に低下することを意味します。

phash はいくつかのタイプのハッシュを提供し、画像、オーディオ、またはビデオに使用できます。

于 2011-11-09T22:17:32.530 に答える
8

カートマンが指摘したように、正確な重複を見つけるために任意の種類のハッシュ値を使用できます。

近い画像を見つけるための 1 つの出発点は、ここにあります。これは、CG 制作会社が、修正された画像が本質的に同じシーンを表示しているかどうかを確認するために使用するツールです。

于 2009-05-09T20:47:03.390 に答える
7

私には、うまくいく可能性があり、非常に高速である可能性が最も高いアイデアがあります。画像をサブサンプリングして 80x60 解像度または同等の解像度にし、グレースケールに変換できます (サブサンプリング後は高速になります)。比較する両方の画像を処理します。次に、2 つの画像 (クエリ画像と db からのそれぞれ) 間の正規化された差の二乗和を実行します。または、両方の画像が類似している場合は、より良い正規化相互相関を実行して、応答を 1 に近づけます。次に、画像が類似している場合は、より洗練された手法に進み、同じ画像であることを確認できます。明らかに、このアルゴリズムはデータベース内の画像の数に関して線形であるため、最新のハードウェアでは毎秒 10000 画像まで非常に高速になります。回転に対する不変性が必要な場合は、この小さな画像に対して支配的な勾配を計算できます。その後、座標系全体を正規の向きに回転できますが、これは遅くなります。いいえ、ここではスケーリングに対する不変性はありません。

より一般的なもの、または大きなデータベース (数百万の画像) を使用するものが必要な場合は、画像検索理論を調べる必要があります (過去 5 年間に大量の論文が発表されました)。他の回答にはいくつかの指針があります。しかし、それはやり過ぎかもしれません。提案するヒストグラムのアプローチでうまくいきます。多くの異なる高速アプローチの組み合わせはさらに優れていると思いますが。

于 2009-06-11T21:22:11.020 に答える
6

画像のサイズをほぼアイコンのサイズ、たとえば 48x48 に落としてから、グレースケールに変換してから、ピクセル間の差、またはデルタを取得するとうまくいくと思います。実際のピクセルの色ではなく、ピクセルの色の変化を比較しているため、画像が少し明るくても暗くても問題ありません。明るすぎる/暗すぎるピクセルは失われるため、大きな変更は重要です。これを 1 つの行に適用することも、精度を上げるために好きなだけ適用することもできます。匹敵するキーを形成するために、最大で 47x47=2,209 の減算を行う必要があります。

于 2011-11-05T13:04:01.037 に答える
3

100 個のランダムなポイントを選択すると、類似した (場合によっては類似していない) 画像が同じとしてマークされる可能性がありますが、これはあなたが望むものではないと思います。画像の形式が異なる場合 (png、jpeg など)、サイズが異なる場合、またはメタデータが異なる場合、MD5 ハッシュは機能しません。すべての画像をより小さなサイズに縮小することは良い賭けです。適切な画像ライブラリ/高速言語を使用していて、サイズが十分に小さい限り、ピクセル単位の比較を行うのにそれほど時間はかかりません。

それらを小さくしてみることができます。それらが同じ場合は、より大きなサイズで別の比較を実行します-速度と精度の適切な組み合わせになる可能性があります...

于 2009-05-09T20:31:03.337 に答える
2

多数の画像がある場合は、ブルームフィルターを調べてください。ブルームフィルターは、確率的ですが効率的な結果を得るために複数のハッシュを使用します。画像の数が多くない場合は、md5のような暗号化ハッシュで十分です。

于 2009-05-09T20:26:42.893 に答える
1

大まかに重複と呼んでいるものは、アルゴリズムが識別するのが難しい場合があります。重複は次のいずれかになります。

  1. 正確な重複
  2. ほぼ正確な重複。(画像等の微修正)
  3. 知覚的重複 (コンテンツは同じですが、ビュー、カメラなどが異なります)

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) )
于 2021-04-15T01:53:49.927 に答える