テンプレートマッチングによる物体検出の原理（SAD, SSD, NCC, ZNCC）

テンプレートマッチングによる物体検出の原理について、計算式や計算例も踏まえて解説します。

テンプレートマッチングとは?

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

■左から順に入力画像、テンプレート画像、出力画像

テンプレートマッチングでは、入力画像の一部分とテンプレート画像の類似度を求めます。
その類似度の計算方法には種類がいくつかあります。
今回は、その代表例である「SSD」「SAD」「NCC」「ZNCC」の4つを解説します。

動画解説版

本ページの内容は以下動画でも解説しています。

SSD(Sum of Squared Difference)

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

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

$ SSD(d_x, d_y)={\displaystyle \sum_{x=0}^{w-1}} {\displaystyle \sum_{y=0}^{h-1}} (I(d_x+x,d_y+y)-T(x,y))^2 $

例えば、テンプレート画像の幅$w=2$、高さ$h=2$のとき、$SSD(1, 0)$の計算式は以下になります。
$ SSD(1, 0)={\displaystyle \sum_{x=0}^{1} \sum_{y=0}^{1}}(I(1+x,y)-T(x,y))^2 $

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

計算例

以下の入力画像$I$とテンプレート画像$T$で$SSD$を計算します。

① 走査位置$I(0, 0)$で計算すると、以下のとおり$SSD=43$となります。

② 走査位置$I(1, 0)$で計算すると、以下のとおり$SSD=25$となります。

③ 走査位置$I(0, 1)$で計算すると、以下のとおり$SSD=18$となります。

④ 走査位置$I(1, 1)$で計算すると、以下のとおり$SSD=1$となります。

⑤ $SSD$の値が最小となるのは走査位置$I(1, 1)$なので、このときの探索範囲がテンプレート画像と最も類似していると判断できます。

SAD(Sum of Absolute Difference)

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

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

$ SAD(d_x, d_y)={\displaystyle \sum_{x=0}^{w-1} \sum_{y=0}^{h-1}}|I(d_x+x,d_y+y)-T(x,y)| $

SADが最小となる走査位置が、テンプレート画像に最も類似する部分の左上座標となります。
SADはSSDと比べて以下の特徴があります。

• 計算量が少ない（メリット）
• 外れ値の影響を受けにくい（メリット）
• 照明の影響をかなり受けやすい（デメリット）※SSDもそれなりに影響を受ける

計算例

以下の入力画像$I$とテンプレート画像$T$で$SAD$を計算します。
ただし、入力画像$I$は、元画像Hが照明変化により全ての画素値が4増加したものと仮定します。

① 走査位置$I(0, 0)$で計算すると、以下のとおり$SAD=6$となります。

② 走査位置$I(1, 0)$で計算すると、以下のとおり$SAD=9$となります。

③ 走査位置$I(0, 1)$で計算すると、以下のとおり$SAD=14$となります。

④ 走査位置$I(1, 1)$で計算すると、以下のとおり$SAD=15$となります。

⑤ $SAD$の値が最小となるのは走査位置$I(0, 0)$なので、このときの探索範囲がテンプレート画像と最も類似していると判断されます。
このように、SADは照明変化の影響を受けやすいことがわかります。

NCC（Normalized Cross Correlation）

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

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

$ 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} } $
ここで、

$ \sum \sum = {\displaystyle \sum_{x=0}^{w-1} \sum_{y=0}^{h-1}} $

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

• 照明の影響を受けにくい（メリット）
• 計算量が多い（デメリット）

NCCは、テンプレート画像と入力画像の部分領域の輝度値を正規化します。これにより、画像の相対的な輝度パターンを比較することができます。
また、テンプレート画像と入力画像の部分領域の内積を計算します。内積は、ベクトルの方向を比較するものであり、ベクトルの大きさ（輝度の絶対値）には依存しません。これらの理由により、「照明変化に比較的強い」という利点があります。

ZNCC（Zero means Normalized Cross Correlation）

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

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

$ 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} } $

ここで、

$ \sum \sum = {\displaystyle \sum_{x=0}^{w-1} \sum_{y=0}^{h-1}} $

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

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

お借りした画像：プロ生ちゃん（暮井 慧）

Python版OpenCVによる実装例

【Python/OpenCV】テンプレートマッチングの実装（SSD、SAD、NCC、ZNCC）

PythonとOpenCVで画像のテンプレートマッチング（SSD）を行う方法をソースコード付きで解説します。

python.joho.info

関連ページ

【画像処理入門】アルゴリズム＆プログラミング

この記事では、画像処理における基本的なアルゴリズムとその実装例（プログラム）についてまとめました。

algorithm.joho.info

2019.08.25