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

2020.01.11

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

【テンプレートマッチングとは】特徴、種類や違い

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

■入力画像（左）とテンプレート画像（右）

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

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

【手法1】SSD(Sum of Squared Difference)

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が最小となる走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

【手法1】SAD(Sum of Absolute Difference)

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と比べて以下の特徴があります。

– SADの特徴
1 計算量が少ない（メリット）
2 外れ値の影響を受けにくい（メリット）
3 照明の影響をかなり受けやすい（デメリット）

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

【手法3】NCC（Normalized Cross Correlation）

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の特徴
1 照明の影響を受けにくい（メリット）
2 計算量が多い（デメリット）

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

【手法4】ZNCC（Zero means Normalized Cross Correlation）

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に最も近くなった走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

– ZNCCの特徴
1 照明変化に対するロバスト性が高い（計算過程で平均値を引くため、比較する2つの画像領域の平均値が異なっていても類似度が変化しません。つまり、NCCよりも明るさの変動に対してよりロバストとなります。）
https://algorithm.joho.info/programming/python/opencv-template-matching-zncc-py/
algorithm.joho.info

計算例（例題）

次のような入力画像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の部分がテンプレート画像と最も類似する部分ということになります。

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

Python版OpenCVによる実装例

【Python/OpenCV】テンプレートマッチングの実装（SSD、SAD、NCC、ZNCC）
PythonとOpenCVで画像のテンプレートマッチング（SSD）を行う方法をソースコード付きで解説します。
python.joho.info

関連ページ

【画像処理入門】アルゴリズム＆プログラミング
この記事では、画像処理における基本的なアルゴリズムとその実装例（プログラム）についてまとめました。
algorithm.joho.info
2019.08.25

コメント

  1. 加納勝博 より:
    2020年5月10日 12:44 AM

    お世話になります。

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

    の方法②を試してみたのですが、

    # 入力画像の読み込み
    img = cv2.imread(“C:/github/sample/python/opencv/template-matching/input.png”)
    temp = cv2.imread(“C:/github/sample/python/opencv/template-matching/temp.png”)

    と、

    # 結果を出力
    cv2.imwrite(“C:/github/sample/python/opencv/template-matching/sad2.png”, img)

    の、（　）内のファイルを、そこからダウンロードした暮井慧の絵や手持ちの写真に置き換えて
    runさせたのですが、次のようなエラーが発生しました。

    何か設定しないといけないようなところがあるのでしょうか？
    原因がわからないので教えてください。

    返信
  2. 加納勝博 より:
    2020年5月10日 12:50 AM

    すみません。エラー内容の記述を忘れました。以下の通りです。
    よろしくお願いします。

    Traceback (most recent call last):
    File “D:/P&Q&A/テンプレートマッチング００１.py”, line 33, in
    gray = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)
    cv2.error: OpenCV(4.2.0) C:\projects\opencv-python\opencv\modules\imgproc\src\color.cpp:182: error: (-215:Assertion failed) !_src.empty() in function ‘cv::cvtColor’

    返信
    • 管理人 より:
      2020年5月10日 10:38 AM

      加納様
      コメントありがとうございます。
      入力画像データが空のようですね。
      cv2.imread()の引数には、入力画像のファイルパスを指定しますが、そちらが正しくない可能性が高いと思います。

      返信
  3. 匿名 より:
    2022年2月4日 4:25 PM

    NCCは照明変化に対して頑健でないといった方向がされている論文があります. 筆者様はどうしてNCCが照明変化に対して頑健であると考えられたのでしょうか.

    返信