画像の中から指定した画像（テンプレート）と似ている位置を探すことを
テンプレートマッチング(template matching)と言います。
 |
 |
| テンプレート | 画像 |
このとき、テンプレートと画像データがどれだけ似ているか？という評価値（類似度または相違度）にはいくつかあり、次に示すような値を用います。
以下の式において、テンプレートの輝度値の値をT(i,j)、画像の輝度値の値をＩ(i,j)とします。
座標の（ｉ，ｊ）はテンプレートの幅をｍ画素、高さをｎ画素としたとき、左上（もしくは左下）を（0,0）、右下（もしくは右上）を（m-1、n-1）とします。
SSD(Sum of Squared Difference)
ＳＳＤはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の２乗の合計が用いられます。
ＳＳＤの値が小さいほど、似ている位置となります。
SAD(Sum of Absolute Difference)
ＳＡＤはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の絶対値の合計が用いられます。
ＳＡＤの値が小さいほど、似ている位置となります。
正規化相互相関【NCC:Normalized Cross-Correlation】
テンプレートと画像との類似度として、以下の正規化相互相関を用いられる場合もあります。類似度が１に近いほど、似ている位置となります。
ちなみに、この計算式は内積の式をＣｏｓθ = の式に変形した式と同じ事にお気づきでしょうか？上式を以下のように変形すると、Ｍ×Ｎ次元のＩのベクトルとＴのベクトルの内積に見えてきませんか？
正規化相互相関【ZNCC:Zero-mean Normalized Cross-Correlation】
上記ＮＣＣの相互相関係数ではテンプレートや画像の明るさが変動すると、ＮＣＣの値もふらついてしまうので、テンプレートおよび画像の輝度値の平均値をそれぞれの値から引いて計算することで、明るさの変動があっても安定的に類似度を計算することができます。
ここで、この式はテンプレートの領域内の輝度値の平均値を計算してから、さらに輝度値から平均値を引くため、標準偏差の時にも説明したように、この式でそのままプログラミングすると効率の悪いプログラムとなってしまいます。そのため、今回も同様にＲＺＮＣＣの式を変形します。
テンプレートの平均輝度値およびテンプレートと同じ領域の画像の輝度値の平均は
で求まることから、この値をＲＺＮＣＣの式に代入して整理すると、
となります。この式を用いると、プログラム的には１パスで済むでの計算効率が良くなります。
ΣΣ×××の部分がなんだか難しく見える方は、Ｃ言語に置き換えて
Sum = 0;
for(j = 0; j < N; j++){
for(i = 0; i < M; i++){
Sum += ×××;
}
}
と置き換えて読んで下さい。
ここで説明しておきながら、最近の工業用途では、この正規化相関の方法よりもパターンの輪郭に基づき、回転やスケール変動などにも対応したマッチング（輪郭サーチ）が一般的になってきています。
最近では、さらにカメラが動いてもマッチングする三次元マッチングなども登場してきています。
正規化相関では明るさの変動にも強く優れたアルゴリズムのように聞こえるかもしれませんが、パターンが重なった場合や欠けた場合に意外と弱かったりもします。
また、このテンプレートマッチングでは、テンプレートと画像を重ね合わせたとき、同じ画素の位置の輝度値が明暗がどれだけ似ているか？という事を評価しています。
そのため、例えば顔写真を登録しておいて、撮影した画像の中から似ている人を見つけ出す！みたいな使い方はできません。
人間の感性での似ている事とはズレがある事に注意して下さい。
コメント
[…] 像処理をやった事がある人では、フーリエ変換は、各周波数をテンプレートとしたテンプレートマッチングを行い、相関値がフーリエ変換のパワースペクトルに相当していると思えば、感 […]
はじめまして。
最近仕事でOpenCV使ったりし始めてまして、いつも便利に利用させていただいております。
ちょっと教えていただきたいのですが、一般的なCV_8UC3の画像ですとNCCの計算式の値の範囲は0～1になるような気がしているのですが、どうなんでしょうか。
またZNCCはmatchTemplateの関数の結果と合わなくて泣いてます。分母が0になる場合の処理とかもうまくなくて中々苦戦中です。
がっちゃんさん、はじめまして。
この記事を書いているときには、ざっくりの理解で、「ＮＣＣの相関値 ≒ cos」という認識だったので、－１～１と書いてしまったのですが、実際には、輝度値に負の値が無いので、計算式からも０～１となりますよね。（後程、記事は修正しておきます。）
実質的には０．６～１．０ぐらいでしょうか？
また、ZNCCの値がmatchTemplateの結果と合わないという事ですが、これは、OpenCVのソースコードまで見ないと何とも言えませんが、OpenCV内では処理速度の最適化のため、ZNCCの値そのものは計算結果と多少異なる場合もあるので、値の大小関係が合っていれば（相関値が最大となる場所が合っていれば）良しと考えた方が良いかも？しれません。
今回は、ご指摘ありがとうございました。
ありがとうございます。
いろいろと悩んでみます。
[…] たとえば、画像処理ではパターンマッチングなんかは、ほとんど内積ですし、フーリエ変換も正規直交規定との内積で、 […]
正規化相互相関の式ですが、私にとってなじみの薄い内積の式というよりは、共分散もしくは相関係数をすべてのpixelについてみた、と読めるような気がするのですが、それで良いでしょうか?
共分散はちょっとだけニュアンスが違う（遠くは無い）ような気もしますが、相関係数を計算しているというのは、まさにそのものですね。私にとっては内積の方がなじみがあるもので．．．
[…] これが書けないと、正規化相関の式が書けない！ […]
[…] 事から２つのベクトルの大きさに関係なく、２つのベクトルがどれだけ似ているか？の指標に使われる場合があります。例えば、画像処理では正規化相関が、まさにそのものとなります。 […]