テンプレートマッチングの原理・計算式・例題(SAD, SSD, NCC)

この記事では、テンプレートマッチングによる探索の原理や特徴、計算式・例題についてまとめました。

テンプレートマッチング

テンプレートマッチング(Template matching)とは、入力画像中からテンプレート画像(部分画像)と最も類似する箇所を探索する処理です。

■入力画像(左)とテンプレート画像(右)

テンプレートマッチングでは、入力画像の一部分とテンプレート画像の類似度を求めます。
そして、類似度が最も大きい場所を探索します。

その類似度の計算方法には種類がいくつかあります。
今回はその代表例である「SSD」「SAD」「NCC」の3つを紹介します。

SSD

SSD(Sum of Squared Difference)では、「画素値の差分の二乗和(二乗誤差)」で類似度を評価します。
この場合、値が最小になる場所が類似度が最も高いことになります。

入力画像の画素値をI(x,y)、テンプレート画像の画素値をT(x,y)とします。
また、テンプレート画像の幅をw, 高さをhとします。
走査位置がdx,dyの場合、SSDの値は次式で計算できます。

(1) \begin{eqnarray*} SSD(d_x, d_y)=\sum_{x=0}^{w-1} \sum_{y=0}^{h-1} (I(d_x+x,d_y+y)-T(x,y))^2 \end{eqnarray*}

SSDが最小となる走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

実装例

【Python/OpenCV】テンプレートマッチング(SSD)の実装例

SAD

SAD(Sum of Absolute Difference)では、「画素値の差分の絶対値の和」で類似度を評価します。
この場合も値が最小になる場所が類似度が最も高いことになります。

入力画像の画素値をI(x,y)、テンプレート画像の画素値をT(x,y)とします。
また、テンプレート画像の幅をw, 高さをhとします。
走査位置がdx,dyの場合、SADの値は次式で計算できます。

(2) \begin{eqnarray*} SAD(d_x, d_y)=\sum_{x=0}^{w-1} \sum_{y=0}^{h-1}|I(d_x+x,d_y+y)-T(x,y)| \end{eqnarray*}

SADが最小となる走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

特徴

SADはSSDと比べて以下の特徴があります。

・計算量が少ない(メリット)
・外れ値の影響を受けにくい(メリット)
・照明の影響をかなり受けやすい(デメリット)

※SSDもそれなりに影響を受ける

実装例

【Python/OpenCV】テンプレートマッチング(SAD)の実装例

NCC

NCC(Normalized Cross Correlation)では、「正規化相互相関」で類似度を評価します。

入力画像の画素値をI(x,y)、テンプレート画像の画素値をT(x,y)とします。
また、テンプレート画像の幅をw, 高さをhとします。
走査位置がdx,dyの場合、NCCの値は次式で計算できます。

(3) \begin{eqnarray*} NCC(d_x, d_y)&=&\frac{ \sum \sum [ I(d_x+x,d_y+y)T(x,y)] } { \sqrt{\sum \sum [I(d_x+x,d_y+y)]^2} \sqrt{ \sum \sum [T(x,y)]^2} }\\\ \end{eqnarray*}

ここで、

(4) \begin{eqnarray*} \sum \sum &=& \sum_{x=0}^{w-1} \sum_{y=0}^{h-1} \end{eqnarray*}

NCCの値は-1.0~1.0に収まり、最大値1.0に最も近くなった走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

特徴

・照明の影響を受けにくい(メリット)
・計算量が多い(デメリット)

NCCは、画像をベクトルとみなして内積を計算するため、値がベクトルの長さに対して影響を受けません。
そのため、「照明変化に強い」という優れた特徴があります。

実装例

【Python/OpenCV】テンプレートマッチング(NCC)の実装例

ZNCC

ZNCC(Zero means Normalized Cross Correlation)では、「零平均正規化相互相関」と呼ばれる統計量で類似度を評価します。

入力画像の画素値をI(x,y)、テンプレート画像の画素値をT(x,y)とします。
また、テンプレート画像の幅をw, 高さをhとします。
走査位置がdx,dyの場合、ZNCCの値は次式で計算できます。

(5) \begin{eqnarray*} ZNCC(d_x, d_y)&=&\frac{ \sum \sum [ (I(d_x+x,d_y+y)-\mu_I)(T(x,y)-\mu_T] } { \sqrt{\sum \sum [I(d_x+x,d_y+y)-\mu_I]^2} \sqrt{ \sum \sum [T(x,y)-\mu_T]^2} }\\\ \end{eqnarray*}

ここで、

(6) \begin{eqnarray*} \sum \sum &=& \sum_{x=0}^{w-1} \sum_{y=0}^{h-1} \end{eqnarray*}

\mu_I, \mu_Tは、入力画像とテンプレート画像の平均値です。
ZNCCの値は-1.0~1.0に収まり、最大値1.0に最も近くなった走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

特徴

計算過程で平均値を引くため、比較する2つの画像領域の平均値が異なっていても類似度が変化しません。
つまり、NCCよりも明るさの変動に対してよりロバストとなります。

実装例

【Python/OpenCV】テンプレートマッチング(ZNCC)の実装例

計算例(例題)

次のような入力画像Iとテンプレート画像Tが与えられたときのSAD(1, 1)の値を求めます。

(7) \begin{eqnarray*} I= \left[ \begin{array}{ccccc} 10& 12 & 11 & 10\\ 10& 35 & 26 & 10\\ 11& 26 & 38 & 10\\   9& 11 &  7 & 10\\ \end{array} \right], T= \left[ \begin{array}{ccccc} 35 & 25\\ 27 & 35 \\ \end{array} \right] \end{eqnarray*}

解答例

テンプレート画像の幅w=2、高さh=2なので、SAD(1, 1)は次のようにして計算できます。

(8) \begin{eqnarray*} SAD(1, 1)&=&\sum_{x=0}^{1} \sum_{y=0}^{1}|I(1+x,1+y)-T(x,y)|\\  &=&|I(1,1)-T(0,0)|+|I(1, 2)-T(0,1)|\\  &+&|I(2,1)-T(1,0)|+|I(2,2)-T(1,1)|\\  &=&|35-35|+|26-25|+|26-27|+|38-35|=5 \end{eqnarray*}

ちなみに残りのSADをすべて計算し、大小を比較するとSAD(1, 1)が最小になります。
よって、入力画像の画素値が35, 26, 26, 38の部分がテンプレート画像と最も類似する部分ということになります。

お借りした画像:プロ生ちゃん(暮井 慧)

【関連記事】
【画像処理入門】アルゴリズム&プログラミング

シェア&フォローお願いします!