パターンマッチング（正規化相関など）

メインページ ＞ 画像処理

画像の中から指定した画像（テンプレート）と似ている位置を探すことを
テンプレートマッチング(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 += ×××;
     }
}
と置き換えて読んで下さい。

---

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

正規化相関では明るさの変動にも強く優れたアルゴリズムのように聞こえるかもしれませんが、パターンが重なった場合や欠けた場合に意外と弱かったりもします。

輪郭ベースのマッチングは、ちょっと難しい（というか、理解できていない、ノウハウが無い）もので．．．