画像処理画像処理アルゴリズム

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

画像の中から指定した画像(テンプレート)と似ている位置を探すことを
テンプレートマッチング(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. […] これが書けないと、正規化相関の式が書けない! […]

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

タイトルとURLをコピーしました