テンプレートマッチング(template matching)

シェアする

  • このエントリーをはてなブックマークに追加
最近の記事
  • 7/6 【参考書籍】画像処理・機械学習プログラミング OpenCV 3対応
  • 6/20 【Python,matplotlib】動くグラフをAnimationGifに保存する方法
  • 6/17 シグモイド関数の微分
  • 6/15 シグモイド関数
  • 6/13 合成関数の微分
  • 6/12 WordPressで数式エディタ風に数式を入力したい
  • 6/11 PythonをVisual Studioでインストールする方法
  • 6/9 【Python】OpenCVをAnacondaでインストール(Windows編)
  • 6/6 【Python】Anacondaで複数バージョンの環境切り替え
  • 6/6 画像センシング展2017に出展します。
  • 6/1 【Office365】Web版Outlookのフォントサイズ変更
  • 6/1 【Anaconda】モジュールのアップデートでエラー発生
  • 6/1 【Anaconda】コマンドリストの表示
  • 5/29 Windows10パソコン購入
  • 5/24 Anacondaのアンインストール
  • 5/24 【Jupyter Notebook】新規プログラムの作成
  • 5/23 【Python】開発環境の構築
  • 5/23 Pythonはじめました
  • 4/6 【Office365】Web版Outlookのスレッド表示を解除する方法
  • 4/5 【Excel】フーリエ解析(FFT)
  • 3/20 Canny edge detection
  • 3/20 【Excel2016】分析ツールの表示
  • 3/5 【Visual Studio】黒い背景色を白に変更する方法
  • 2/8 【Windows10】拡張モニタに表示されたウィンドウを元に戻す
  • 2/7 複素数の計算
  • 1/18 【Excel】棒グラフの横軸の目盛を0始まりにする
  • 1/16 【Excel】フーリエ変換
  • 1/6 【OpenCV】疑似カラー(カラーマップ)
  • 11/8 【Visual Studio】検索結果のウィンドウ表示
  • 11/3 ニコン 一眼レフカメラ D5500レビュー
  • 10/26 カラーカメラはモノクロカメラを兼ねない
  • 9/6 (Free Soft)Animation GIF Builder
  • 8/30 【C#】タブの無いTabControlっぽいものを作る
  • 8/29 【OpenCvSharp】サンプルプログラムの公開
  • 8/28 【PowerPoint】部分的にカラーにする(セレクトカラー処理)
  • 8/27 【C#】引数の値渡し、参照渡し(ref, out)
  • 8/26 【Word/Excel】図形内に文字を挿入する
  • 8/25 【C#】NumericUpDownコントロール
  • 8/24 ニコン D3400 VS D5500 仕様比較
  • 8/22 【C#】MDIフォームにリサイズ可能なPanelを設置する
  • 8/20 【Visual Studio 2015】文字の色が変、かすむ
  • 8/20 【Visual Studio】行のコピー、切り取り、貼り付け
  • 8/20
  • 8/16
  • 7/7 標準偏差のよくある誤解
  • 6/17 ホーム
  • 6/15
  • 6/15
  • 6/15
  • 6/15

  • 画像の中から指定した画像(テンプレート)と似ている位置を探すことを
    テンプレートマッチング(template matching)と言います。

    テンプレート画像 画像
    テンプレート 画像

    このとき、テンプレートと画像データがどれだけ似ているか?という評価値(類似度または相違度)にはいくつかあり、次に示すような値を用います。

    以下の式において、テンプレートの輝度値の値をT(i,j)、画像の輝度値の値をI(i,j)とします。
    座標の(i,j)はテンプレートの幅をm画素、高さをn画素としたとき、左上(もしくは左下)を(0,0)、右下(もしくは右上)を(m-1、n-1)とします。

    SSD(Sum of Squared Difference)

    SSDはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の2乗の合計が用いられます。
    SSDの値が小さいほど、似ている位置となります。

    SSD(Sum of Squared Difference)

    SAD(Sum of Absolute Difference)

    SADはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の絶対値の合計が用いられます。
    SADの値が小さいほど、似ている位置となります。

    SAD(Sum of Absolute Difference)

    正規化相互相関【NCC:Normalized Cross-Correlation】

    テンプレートと画像との類似度として、以下の正規化相互相関を用いられる場合もあります。類似度が1に近いほど、似ている位置となります。

    正規化相互相関【NCC:Normalized Cross-Correlation】

    ちなみに、この計算式は内積の式をCosθ = の式に変形した式と同じ事にお気づきでしょうか?上式を以下のように変形すると、M×N次元のIのベクトルとTのベクトルの内積に見えてきませんか?

    正規化相互相関【NCC:Normalized Cross-Correlation】

    正規化相互相関【ZNCC:Zero-mean Normalized Cross-Correlation】

    上記NCCの相互相関係数ではテンプレートや画像の明るさが変動すると、NCCの値もふらついてしまうので、テンプレートおよび画像の輝度値の平均値をそれぞれの値から引いて計算することで、明るさの変動があっても安定的に類似度を計算することができます。

    正規化相互相関【ZNCC:Zero-mean Normalized Cross-Correlation】

    ここで、この式はテンプレートの領域内の輝度値の平均値を計算してから、さらに輝度値から平均値を引くため、標準偏差の時にも説明したように、この式でそのままプログラミングすると効率の悪いプログラムとなってしまいます。そのため、今回も同様にRZNCCの式を変形します。

    テンプレートの平均輝度値およびテンプレートと同じ領域の画像の輝度値の平均は

    テンプレートの平均輝度値 画像の平均輝度値

    で求まることから、この値をRZNCCの式に代入して整理すると、

    正規化相互相関【ZNCC:Zero-mean Normalized Cross-Correlation】

    となります。この式を用いると、プログラム的には1パスで済むでの計算効率が良くなります。

    ΣΣ×××の部分がなんだか難しく見える方は、C言語に置き換えて

    Sum = 0;
    for(j = 0; j < N; j++){
      for(i = 0; i < M; i++){
        Sum += ×××;
      }
    }

    と置き換えて読んで下さい。

    ここで説明しておきながら、最近の工業用途では、この正規化相関の方法よりもパターンの輪郭に基づき、回転やスケール変動などにも対応したマッチング(輪郭サーチ)が一般的になってきています。

    最近では、さらにカメラが動いてもマッチングする三次元マッチングなども登場してきています。
    正規化相関では明るさの変動にも強く優れたアルゴリズムのように聞こえるかもしれませんが、パターンが重なった場合や欠けた場合に意外と弱かったりもします。

    また、このテンプレートマッチングでは、テンプレートと画像を重ね合わせたとき、同じ画素の位置の輝度値が明暗がどれだけ似ているか?という事を評価しています。
    そのため、例えば顔写真を登録しておいて、撮影した画像の中から似ている人を見つけ出す!みたいな使い方はできません。
    人間の感性での似ている事とはズレがある事に注意して下さい。

    画像処理アルゴリズムへ戻る

    コメント

    1. […] 像処理をやった事がある人では、フーリエ変換は、各周波数をテンプレートとしたテンプレートマッチングを行い、相関値がフーリエ変換のパワースペクトルに相当していると思えば、感 […]

    2. がっちゃん より:

      はじめまして。
      最近仕事でOpenCV使ったりし始めてまして、いつも便利に利用させていただいております。
      ちょっと教えていただきたいのですが、一般的なCV_8UC3の画像ですとNCCの計算式の値の範囲は0~1になるような気がしているのですが、どうなんでしょうか。

      またZNCCはmatchTemplateの関数の結果と合わなくて泣いてます。分母が0になる場合の処理とかもうまくなくて中々苦戦中です。

      • akira より:

        がっちゃんさん、はじめまして。
        この記事を書いているときには、ざっくりの理解で、「NCCの相関値 ≒ cos」という認識だったので、-1~1と書いてしまったのですが、実際には、輝度値に負の値が無いので、計算式からも0~1となりますよね。(後程、記事は修正しておきます。)
        実質的には0.6~1.0ぐらいでしょうか?
        また、ZNCCの値がmatchTemplateの結果と合わないという事ですが、これは、OpenCVのソースコードまで見ないと何とも言えませんが、OpenCV内では処理速度の最適化のため、ZNCCの値そのものは計算結果と多少異なる場合もあるので、値の大小関係が合っていれば(相関値が最大となる場所が合っていれば)良しと考えた方が良いかも?しれません。
        今回は、ご指摘ありがとうございました。

      • がっちゃん より:

        ありがとうございます。
        いろいろと悩んでみます。

    3. […] たとえば、画像処理ではパターンマッチングなんかは、ほとんど内積ですし、フーリエ変換も正規直交規定との内積で、 […]

    4. 賀数 康弘 より:

      正規化相互相関の式ですが、私にとってなじみの薄い内積の式というよりは、共分散もしくは相関係数をすべてのpixelについてみた、と読めるような気がするのですが、それで良いでしょうか?

      • akira より:

        共分散はちょっとだけニュアンスが違う(遠くは無い)ような気もしますが、相関係数を計算しているというのは、まさにそのものですね。私にとっては内積の方がなじみがあるもので...

    5. […] 事から2つのベクトルの大きさに関係なく、2つのベクトルがどれだけ似ているか?の指標に使われる場合があります。例えば、画像処理では正規化相関が、まさにそのものとなります。 […]