[解決済み] 画像比較 - 高速アルゴリズム

質問

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

例：同じ画像を100回以上保存するのを減らしたい場合、そのコピーを1つ保存して、それへの参照リンクを提供することができます。 新しい画像が入力されたとき、既存の画像と比較して、重複していないことを確認したい・・・アイデアはありませんか？

私のアイデアのひとつは、小さなサムネイルに縮小して、100ピクセルの場所をランダムに選んで比較することでした。

解決方法は？

以下は、この問題を解決するための3つのアプローチです（他にも多くのアプローチがあります）。

• 1つ目は、コンピュータビジョンの標準的なアプローチであるキーポイントマッチングです。 これは、実装に背景知識が必要であったり、時間がかかったりすることがあります。

• 2つ目の方法は、初歩的な画像処理しか行わないため、1つ目の方法よりも高速になる可能性があり、実装も簡単である。 しかし、拡大縮小、回転、変色した画像ではマッチングに失敗するなど、わかりやすさの反面、頑健さに欠ける。

• 3つ目の方法は、高速かつ堅牢ですが、実装が最も困難な方法です。

キーポイントマッチング

100個のランダムな点を選ぶより、100個の点を選ぶ方が良い 重要 点です。 画像の特定の部分（特にエッジやコーナー）は、他の部分よりも情報量が多く、スマートな画像マッチングに利用したい部分です。 Google "で検索してください。 キーポイント抽出 "と" キーポイントマッチング をクリックすると、このテーマに関するかなりの数の学術論文を見つけることができます。 最近では SIFTキーポイント は、異なるスケール、回転、照明の下で画像をマッチングさせることができるため、間違いなく最も人気があります。 SIFTの実装をいくつか紹介する。 こちら .

キーポイントマッチングの欠点は、素朴な実装では実行時間がかかることです。O(n^2m), ここで n は各画像のキーポイントの数、m はデータベース内の画像の数です。 4分木や2分空間分割のような賢いアルゴリズムであれば、より速く最も近いマッチングを見つけることができるかもしれません。

代替案 ヒストグラム法

もう1つの堅牢性に欠けるが高速化できる可能性のある方法は、各画像の特徴ヒストグラムを構築し、入力画像のヒストグラムに最も近いヒストグラムを持つ画像を選択することです。 私は学部生時代にこれを実装し、3つのカラーヒストグラム（赤、緑、青）と、2つのテクスチャヒストグラム（方向とスケール）を使いました。詳細は後述しますが、これはデータベース画像と非常によく似た画像をマッチングする場合にのみうまく機能することを指摘しておきます。 再スケール、回転、変色した画像はこの方法で失敗することがありますが、トリミングのような小さな変更ではアルゴリズムは壊れません。

ヒストグラムバケットの範囲を決め、それぞれの範囲について、その範囲に含まれる色を持つピクセルの数を集計すればよいのです。 例えば、quot;green" ヒストグラムを考えてみましょう。0-63、64-127、128-191、192-255の4つのバケットをヒストグラムに選んだとします。 そして、各ピクセルについて、緑の値を調べ、適切なバケツに集計を追加します。 集計が終わったら、各バケツの合計を画像全体のピクセル数で割って、緑チャンネルの正規化ヒストグラムを得ます。

テクスチャ方向ヒストグラムでは、まず、画像のエッジ検出を行いました。 各エッジ点には、エッジに垂直な方向を指す法線ベクトルがあります。 法線ベクトルの角度を0〜PIの6つのバケットに量子化します（エッジは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の論文は、特に画像マッチングについてではなく、領域のラベリングについてです。マッチングを行う元の論文はこちらです。 ランダムツリーを用いたキーポイント認識 . また、以下の論文もアイデアを発展させ続けており、最新の状況を表しています（2010年現在）。

• ランダムファーンによる高速キーポイント認識 - Lepetit 06 よりも高速でスケーラブル
• BRIEF バイナリロバスト独立素性 - スマートフォンやその他のハンドヘルド端末でのリアルタイムマッチングが目的だと思われます。