画像比較 - 高速アルゴリズム 質問する

以下に、この問題を解決するための 3 つのアプローチを示します (他にも多くのアプローチがあります)。

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

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

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

キーポイントマッチング

ランダムに 100 個のポイントを選択するよりも、重要なポイントを 100 個選択する方がよいでしょう。画像の特定の部分には、他の部分よりも多くの情報が含まれています (特に端と角)。これらの部分こそ、スマートな画像マッチングに使用する必要があります。Google "キーポイント抽出" そして "キーポイントマッチング「このテーマに関する学術論文は数多くあります。最近では、SIFT キーポイントSIFTは、異なるスケール、回転、照明の下で画像を一致させることができるため、おそらく最も人気があります。いくつかのSIFT実装は、ここ。

キーポイント マッチングの欠点の 1 つは、単純な実装の実行時間です: O(n^2m)。ここで、n は各画像のキーポイントの数、m はデータベース内の画像の数です。四分木やバイナリ空間分割などの巧妙なアルゴリズムを使用すると、最も近い一致をより速く見つけられる可能性があります。

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

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

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

テクスチャ方向ヒストグラムについては、まず画像のエッジ検出を実行しました。各エッジ ポイントには、エッジに垂直な方向を指す法線ベクトルがあります。法線ベクトルの角度を 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 の論文は、特に画像のマッチングに関するものではなく、領域ラベル付けに関するものです。マッチングを行う元の論文は次のものです。ランダムツリーを使用したキーポイント認識また、以下の論文はアイデアをさらに発展させ、最先端の研究成果を表しています（2010 年頃）。

• ランダムシダを使用した高速キーポイント認識- Lepetit 06よりも高速でスケーラブル
• 概要: バイナリロバスト独立基本特徴 - 堅牢性は劣るが非常に高速 - ここでの目標はスマートフォンやその他の携帯機器でのリアルタイムマッチングであると思う